Can we replace IV increasing from addition to XOR in CTR mode? In CTR mode (not nonce-based), if we have ${IV}\stackrel{\$}{\leftarrow}\{0,1\}^{128}$ and want to encrypt message blocks $M_1, M_2, ..., M_\ell \in\{0,1\}^{128}$:

The ciphertext is $IV\parallel C_1\parallel C_2\parallel...\parallel C_\ell$, where $C_i=AES_k(IV+i-1)\oplus M_i$.

Note that $IV$ is random here.

How about changing the CTR mode into the following algorithm?

The ciphertext is $IV\parallel C_1\parallel C_2\parallel...\parallel C_\ell$, where $C_i=AES_k(\boxed{IV\oplus(i-1)_{128}})\oplus M_i$.

Here, $(i-1)_{128}$ means a 128-bit block that has $(i-1)$ in its lower bits.

Such a change has a benefit: it is easier to implement $(IV\oplus1)$ than implement $(IV+1)$ using CPU instructions or in garbled circuits.

I wonder whether there is any security proof showing such a construction is equal to CTR. Currently, I don't even find the good keyword for that.

Note: one answer How do we compute IV+1 in CTR mode? mentions this change. I feel some security discussion is needed.

A fairly common way to implement CTR mode is to construct the IV by taking a per-message nonce of, say, 96 bits and appending 32 zero bits to the right of it.  These 32 least-significant bits are then incremented by one for each cipher block in the message.

This method has the useful property that if the nonces are never reused, and if no message contains more than 232 cipher blocks, then the counter values can be guaranteed to never repeat.

For your purposes, another useful feature of this method is that, as long as the above conditions hold (i.e. as long as $i \le 2^{32}$ and the lowest 32 bits of the IV are all zero), then $IV + (i-1) = IV \oplus (i-1)$.  Thus, it makes no difference at all whether you combine the IV and the block counter using addition or XOR, or even just concatenate the nonce directly with the 32-bit block counter.


How can I plot graphs of CP-ABE scheme using charm crypto? Can I use charm crypto tool to run it over my datasets for CPABE scheme and plot graphs using its Benchmarking tool ?
Or, how can I use Charm Crypto tool with CPABE toolkit ?

1) Yes, you can use charm as a benchmarking tool for bandwidth performance, for CP-ABE, but not for computational performance, as charm is basically python over the PBC-library (https://crypto.stanford.edu/pbc/). We used charm for Dual-Policy ABE evaluation, but for subjective policies that becomes identical to CP-ABE, see http://dx.doi.org/10.1109/MILCOM.2016.7795382.

2) Bethencourt's cpabe toolkit and charm are actually parallel frameworks. You probably could tweak charm to use PBC via the cpabe toolkit, but there's no reason, as you can use PBC directly from charm as well (easier, in my opinion)


RNG Source Combining I'm planning on combining RNGs from several sources (Windows, Linux, OpenBSD, etc.) for generating one time pads but I have some questions that I don't know how to answer regarding xoring the outputs of those random number generators together. Trying to search for answers to these is not doing well either.

Suppose we have 2 random number generators, g and h. If g is secure and h is not (an attacker can find some kind of pattern to predict future outputs or an attacker can influence or gather output data from said generator), is g ^ h secure? I believe this one is yes since if we have bits g1 and h1 and an attacker knows h1, g1 ^ h1 will be effectively random to said attacker since he does not know what g1 is.

Suppose we have an unbiased random number generator g and a biased (biased such that p(1) != p(0) and p(1) = C for some constant C) random number generator h. Is g ^ h unbiased? I sort of think this is yes but at the same time I'm not sure since then we should be able to just xor any biased (constant) random number generator output with 0xAA and get an unbiased one.

To go along with the previous question suppose we have a biased (constant like h in the previous question) random number generator and we xor every other output bit with 1. Is the output unbiased?

Yes combining anything with the output of a good RNG will result in good random numbers (as long as they don't have information from your RNG)
Yes it would remove the bias (but there are other ways to do this whitening also)
No that doesn't really do anything interesting, but a simple way to unbias your numbers is a Von Neumann extractor

Also try to find non deterministic sources, be suspicious of random data from strangers.


How do RSA and ElGamal key sizes compare? I have a rather silly question regarding the comparison of RSA with ElGamal over integers. If you want to compare their performance in the same level of security, does the modulus of both of them need to be the same size, or does RSA have to be double the size of ElGamal?

RSA and ElGammal are about equally secure at the same modulus size (assuming, of course, intelligent parameter selection in both cases).

For RSA (assuming you use good padding), the best known-attack is to factor the modulus with NFS.

For ElGammal (assuming you use a subgroup with a large enough prime factor), the best known-attack is to compute the discrete log of the public key with NFS.

Now, the version of NFS to compute discrete logs is somewhat more complicated than if it were used to factor; however I don't believe that extra complication adds a significant time to the time taken.


Can the encrypt-and-authenticate method result in secure authenticated encryption if the MAC scheme has unique tags（non-deterministic）？ If we use non-deterministic MACs in encrypt-and-authenticate approach， is it secure？

Not necessarily.  Let $M$ be a secure deterministic MAC like HMAC-SHA256.  Define the randomized MAC $M'_{k, \rho}(m) := M_k(m) \mathbin\| \rho$; that is, $M'$ just appends the randomization to the MAC.  Then encrypt-and-authenticate with $M'$ still leaks message equality, even though the MAC is technically randomized.


Where can I learn the basics of AES? I was tasked with making an expo about AES and its steps, but I still can't grasp it, especially when it comes to "key schedule".

Does anyone know some good material to start learning? Or can someone give me good explanations about AES? I tried Wikipedia and some random PDFs but nothing really fit the bill.

First of all, AES is like an alias for a winner of a contest that has started in 1997 and finishes in 2000 with the announcement of Rijndael's win. A nice document to learn AES is the link given by Richie Frame in the comments of this question.

Trying to do an small summary, there are two main families of symmetric ciphers and Rijndael is a member of the Substitution-Permutation Network (SPN). The other family is the Feistel Networks with DES as a highlighted member (the AES predecessor).

The main goal of a symmetric cypher is to provide enough confusion and diffusion (Shannon properties) and often this is provided by a set of rounds where different operations are applied on each of them. The key shall be applied in those rounds, and in the case of Rijndael is not the key itself, but parts of a Key Derivation Function.

Long a go I've wrote something, and perhaps the image I've made could help you to understand the iterative process of the KDF in Rijndael. It had a mistake and I'm placing here a fixed version of the image. That is for 128 bit keys, but it's not hard to imagine how different it is with the other key sizes.

Rijndael have some good characteristics like efficiency in software and in hardware, specially because in the lowest level all the operations are bit xors (but this has been already pointed in the comments). Perhaps one cons would be the complexity to protect against side channel attacks.


Certificate Signature Algorithm differs from Signature Algorithm Negotiated for Connection With the upcoming sunsetting of SHA-1 by browsers I was checking signature algorithms for sites I visit. I'm using Firefox 43.0.2 on Windows.

I noticed something interesting when I visited the site Origin Energy site: https://online.originenergy.com.au.

The site's (leaf) certificate uses the SHA-2/SHA-256 signature algorithm. See certificate details dialog screenshot.

Where as the connection cipher suite appears to use SHA-1. See page info dialog screenshot.

I have a few questions:

Q1. Are the Certificate Signature Algorithm and signature algorithm in the negotiated connection cipher suite used for different purposes?

If these signature algorithms are used for different purposes.

Q2. Does the upcoming sunset for SHA-1 relate to the Certificate Signature Algorithm and signature algorithm in the connection cipher suite?

and

Q3. The SSL Labs scan for the site shows the web service cipher suite lists supports SHA-2 and SHA-1 algorithms.

If I'm using the latest version of Firefox why does the server/client negotiation not use the preferred SHA-2 algorithm for the connection?

Are the Certificate Signature Algorithm and signature algorithm in the
  negotiated connection cipher suite used for different purposes?

Yes they are.
The hash negotiated in the cipher suite is completely irrelevant to the certificate. The verification of the certificate and the signatures in the TLS handshake use the hash / signature pair negotiated in the signature_algorithms extension. The hash from the cipher suite is called the Pseudorandom Function (PRF) which is used for authentication (in HMAC-mode) for CBC cipher suites and to derive the [master_secret][4] from the pre_master_secret.

  Does the upcoming sunset for SHA-1 relate to the Certificate Signature
  Algorithm and signature algorithm in the connection cipher suite?

The sunset of SHA-1 only affects the use of SHA-1 in certificates. The SHA-1 based cipher suites will still be available as HMAC-SHA-1 isn't broken by collisions on SHA-1.

  If I'm using the latest version of Firefox why does the server/client
  negotiation not use the preferred SHA-2 algorithm for the connection?

Usually the server picks the cipher suites himself, i.e. the server picks the cipher suite it considers strongest and unfortunately most clients (including Firefox) don't support AES-256-GCM but AES-256-CBC so AES-256-CBC gets picked. As for why it picks SHA-1 over SHA-2 then, it's again the support question. Firefox only supports CBC with SHA-1 but not with SHA-2 so SHA-1 gets picked because of the stronger key size.

In your case the server prefers DHE_RSA_* over everything else. It prefers DHE_RSA_AES_*_GCM_* first, but Firefox doesn't support them (Firefox only supports GCM with ECDHE_*) so it picks the next suite in the list which is DHE_RSA_WITH_AES_256_CBC_SHA.

From the comments:

  [D]oes it alert on intermediate certs as SHA-1 may impact on the clients
  ability to validate the trust chain?

Yes, the browser automatically trusts intermediate certificates signed by a trusted root CA. Thus it may not have seen the exact certificate before, meaning if somebody could find a colliding certificate and somehow make the root CA sign it, you're trusting a malicious certificate (this is the same with leaf certificates).

  Also why not alert on the root cert?

The browser or the OS have a so-called "certificate store" where they store trusted root certificates. There are three reasons why it collisions on SHA-1 don't matter for root certificates.

If the root certificate is sent by the server, the browser may just compare this one byte-by-byte to the local copy and thus any change would cause the alert, but the SHA-1 hash isn't verified explicitely.
If the root certificate is sent by the server, the browser may just compute the hash of the received certificate and compare with the hash of the stored certificate. You'd need a second-preimage on SHA-1 to break this which is considered infeasible as of now.
Usually the root certificate isn't sent by the server. In this case the browser looks at the issuer of the intermediate certificate and check if this one is in the trust store and accepts it if it is in there.


What is the original SKID3 protocol? While searching for a mutual authentication protocol I often stumbled upon SKID3. However I encountered different variations of it.

The basic structure is the following:

(1) $A \rightarrow B: r_A$

(2) $B \rightarrow A: r_B || \operatorname{MAC}(r_B||r_A||A)$

(3) $A \rightarrow B: \operatorname{MAC}(r_B||r_A||B)$

where $A$ and $B$ are the identifiers of the senders and recipients, '$||$' means concatenation and $r_A$, $r_B$ are challenges(e.g. random numbers).

Sometimes the concatenation order of $r_A$ and $r_B$ is inverted between step 2 and 3 (page. 19) . Some other time $r_A$ is omitted in step 3 (slide 23) . But the authors never explain why those parts are designed that way.

To me it looks like those variations don't introduce any problems. So do you think those variations offer the same level of security?
Something that all variations have in common is that in step 2 in the MAC function $r_B$ (the "own" challenge) always comes first (maybe a coincidence?). Doesn't look to me like it makes a difference whether $r_B$ or $r_A$ comes first. What do you think?
Is SKID3 actually a standardized protocol or is it just a scheme that can be used or built upon? I couldn't find it in any document defined as a standard.

I know that the identifiers in step 2 and 3 are used in order to thwart a reflection attack and the concatenation of $r_B$ and $r_A$ in step 2 is necessary to prevent a parallel session attack. But the above questions are still unclear to me.

SKID (Secret-Key IDentification protocol), by Walter Fumy and Markus Dichtl, originates from a research effort in Europe in 1992 (Research and Development in Advanced Communication Technologies in Europe, RIPE Integrity Primitives: Final Report of RACE Integrity Primitives Evaluation (R1040), RACE, June 1992), also available in the Springer's LNCS-series, vol. 1007.

Unfortunately, the original text seems to be unavailable in the web. The part I of the book can be found here: http://oai.cwi.nl/oai/asset/5295/5295D.pdf. However, SKID was sent for standardization in ISO/IEC, and is essentially the same as ISO/IEC 9798-4:1999(E)-standard's three-pass authentication mechanism for mutual authentication. This standard seems to be plentifully available via simple googling despite the apparent IPR issues.

SKID-2 means a unilateral (two-pass) auth.protocol, while SKID3 means the (three-pass) mutual authentication (ISO 9798-4, Chapter 5.2.2).

There are indeed some variations on the protocol. Most notably there is confusion on whether $B$ (resp. $A$) should include $B$'s (resp. $A$'s) identity in Step 2 (resp. Step 3) or vice versa. Notably Schneier's Applied Cryptography orders the identities differently (2nd ed. Chapter 3.2 about SKID).

The "original" version of SKID3 (where $B$ will include $A$'s identity inside the MAC in Step 2 and $A$ will include $B$'s identity in Step 3) is correct, at least from the point of view of protecting against reflection attack: adding the identity inside the MAC means that the sending party (here: $B$) is able to distinguish between messages sent by $B$, $A$ and other possible parties $A'$. If the message includes merely $B$'s own identity, such a distinction cannot be made.

The actual questions:

Order of $r_A$ and $r_B$. Within one message it is indeed the same, in which order the nonces appear. However, they need to be in a different order from Step 2 to Step 3, or (as one variation goes) leave out $r_A$ in Step 3. There is a type of attack against a public-key authentication protocol featured in ISO 9798-3 authentication mechanisms called Canadian attack (e.g. p.112 of Boyd and Mathuria's Protocols for Authentication and Key Establishment), which is applicable here as well, if the MACs are too similar. In essence, the attacker may try to fool B to accept a token from Step 2 as a token from Step 3, unless they are dissimilar.
The omitting of $r_A$ does not expose the protocol to typical attacks including reflection, parallel sessions and MitM. This is basically due to the reason that it is difficult for an attacker to get through to Step 3, since Step 2 already includes both nonces and the token is unique in construction and format in the protocol. Other attacks may apply, though.
Even though SKID3 can be considered as a standard mechanism, one will still have to be careful to consider the circumstances where to use the protocol. The protocol does assume a pre-shared secret between $A$ and $B$ and is used for entity authentication only. The notion of universal composability for protocols only came around in 2000 by Canetti, so SKID has been designed on a per-attack basis rather than general security.


Are attributes of an access structure visible or guessable in a CP-ABE ciphertext? Suppose that Alice has attributes A, B and C. I have a ciphertext with this policy: A AND C.

Can an adversary guess the attributes and then decrypt the ciphertext? What is the probability of guessing attributes in a ciphertext policy attribute based encryption?

In CP-ABE, the policy (i.e. which attributes are required to decrypt) is usually public. So Alice knows whether her A, B, C satisfy the policy or not. If not, Alice knows for example, D and E are required, but she does not have. She does not need to guess. She cannot decrypt the ciphertext however, because she does not have the private key corresponding to the missing attributes. The private keys are issued by a trusted party who will only issue to keys after verifying the requesting party does possess the attributes.


Setting MAC field to all-zero to indicate unencrypted data I'm currently working on a project where we transmit data between two systems. The data is generally encrypted before transmission, however there are certain transmissions that are unencrypted.

We use the following data format for transmission:

Encrypted-Data [64Bytes] | MAC [16 Bytes]

The receiving system first decrypts and verifies the authenticity of the messages origin, then the data is processed further.

My solution to this problem is setting all bits of the MAC to zero before transmission, to indicate that the message is unencrypted.

Now my questions:

can a MAC calculation result in zero (we use Poly1305)?
is it good practice to use the MAC set to zero to indicate unencrypted data?

Yes, a MAC can of course have an all zero result. But that doesn't matter, because the chance of that happening should be the same as taking a random choice out of a set where each element has the same probability, i.e. has a uniform distribution.

So the chance of an all zero popping up should - in this case - be about $1$ in $2^{128}$, assuming of course that the message changes every time (without pre-knowledge the chance would be the same, but identical input will of course result in identical MAC-values, so there's that). Now that is the same chance of guessing an AES-128 key in one go, i.e. the chance that it will happen is negligible. So in practice your scheme could be used fine.

Remind yourself though that using magical values should be avoided as a general principle. Even worse is of course that you remove all security provided by the MAC if the message is not encrypted. The integrity and authenticity provided by the MAC have value for unencrypted messages as well.

So yeah, you could certainly use the scheme, but I would rather sacrifice any other bit for this. I would not call it good practice. I'd only use the scheme if there was no other bit to sacrifice (i.e. the protocol is already established and I now have to perform a hack to put in extra options).

[EDIT] Note that an adversary in a scheme with optional MAC can send you any (unencrypted) message. Generally we require a MAC to avoid that situation.


What are some disadvantages of homomorphic encryption schemes? I'm doing some self-teaching / research for my own benefit in homomorphic cryptography.

I've studied both additive and multiplicative schemes (Paillier and RSA respectively), but all I can seem to find are the benefits of the schemes.

Are there any disadvantages to these schemes being used for homomorphic operations (minus their obvious limitations in not being fully homomorphic)? If so, where should I be looking, and which key-words have I not been searching for?

The multiplicatively homomorphic variant of RSA is not semantically secure. This is a major disadvantage. ElGamal is a semantically secure, multiplicativey homomorphic cipher. Paillier is a semantically secure, additively homomorphic cipher.

As described by tylo, all homomorphic ciphers are malleable by definition. Chances are, however, if you are interested in homomorphic ciphers, however, malleability is probably not a concern.

Homomorphic ciphers typically do not, in and of themselves, do not provide verifiable computing. In words, you encrypt your data, send it to the cloud and let the cloud compute on it for you. How do you know the cloud performed the correct computation? To get this sort of guarantee, other machinery is needed.

Performance is often a disadvantage. Ciphertexts in the ciphers you mention are much larger than the plaintexts, so communication requirements typically go up. The computations on these large ciphertexts are typically slower than if you just performed the computation on the plaintext itself. Because of this, in the outsourcing computation model, we typically see a requirement that encrypting inputs and decrypting outputs should be faster than performing the computation itself. In the case of multiple parties with individual inputs this seems to be less of a concern as privacy, not efficiency is the concern.

In the case of multiple, participating parties, guaranteeing fairness (which means everyone who is suppose to get an output, gets it) is often difficult and requires extra machinery (e.g., threshold decryption) and more assumptions (threshold of honest parties, etc). Another concern in the multiple, participating parties model is how the parties privately input their values for the computation. If one party knows the private key, they can decrypt the inputs and violate another party's privacy. So in this case, threshold decryption is often used. This in itself is a disadvantage as generating threshold keys is a non-trivial task.


Multi-party decryption, no central decrypter Recently a bank had a costly mistake that resulted in their master private key being exposed.
Through this thread, I learned about multi-party key storage with Adi Shamir's secret sharing scheme as the basis, very cool.
In the naive setup, there's still a person/machine that must do the final decryption which knows the full key.
What scheme(s) allows no central decrypter?
A guess I have is two or more 'groups/keys' separately encrypt/decrypt the message so no one group can ever have the keys to the kingdom.
Or is there a way for the final decrypter to decrypt w/o actually knowing the master key such that only one Adi Shamir scheme is necessary?
Thanks!

I just wanted to give you a hint, but since I cannot write comments under your question, I write it here:
I think you are searching for a scheme that whenever the secret is reconstructed, the participant's keys dont reveal. We have such schemes, please see this Lecture Note Chaper 6.

Lecture Note information: Lecture Notes, Cryptographic Protocols, Version 1.21
September 13, 2016, Berry Schoenmakers
The name of the protocol is: Threshold Elgamal Cryptosystem  But the whole chapter that I mentioned is more informative than just this protocol.


Randomized stream cipher using multivariant quadratic equations This is an idea I had for cipher that I thought might reduce to a known hard problem. It is efficient (compared to something like BBS) in terms of time but not in terms of space.

Here's the algorithm:

Produce 128 real random streams equal in length to the plain-text. (These do not need to be secret, they can be published with the cipher text.)
Let each bit of the 128-bit streams define the terms of a multi-variant quadratic polynomial in 128 variables over GF(2). One way to do this would be to label each stream as defining a specific term to multiply.
Split the secret key in to 128-bit 1 bit variables and substitute in to the equation take from step 2.
The resultant bit is then XORed with the plain-text to produce cipher-text.
Repeat for all bits in the plain-text and transmit the cipher-text plus the 128-bit key-streams.

My security argument is that solving systems of multivariant quadratic equations in a lot of variables is a known hard problem. In the average case, it is meant to be NP Hard.

All I've done is randomized the selection of the specific instance of the problem. Of course, very quickly the system would become over-determined which might aid solution of the problem.

My question is whether I've made a mistake somewhere or misunderstood something?

Summary. This scheme is insecure.  It can be cryptanalyzed using standard methods from the cryptanalytic literature.  It also has poor performance.

Your algorithm. To summarize your scheme, in your algorithm a one-bit message $m \in GF(2)$ is encrypted by picking a random quadratic polynomial $p(x_1,\dots,x_{128})$ in $GF(2)[x_1,\dots,x_{128}]$, setting $c = m \oplus p(k)$, and transmitting $p(x_1,\dots,x_{128})$ and $c$.  Here $k \in GF(2)^{128}$ is the key, and $k$ remains fixed for all messages (while in contrast $p$ is chosen afresh for each message).

Performance.  This scheme expands the length of the message by a huge amount: by a factor of 16384 or so.  That's an enormous overhead.  Existing schemes don't have that problem.  Also, I expect that it would be very slow (compared to state-of-the-art stream ciphers), since for each bit encrypted, you have to pick 16384 pseudorandom bits and then evaluate the polynomial.

Algorithmic background: solving multivariate equations. There has been a lot of work in the cryptographic literature on the hardness of solving a system of multivariate equations.  One of the fundamental techniques is relinearization.

If you have $n^2$ systems of equations, where each equation is of degree $\le 2$ (i.e., a multivariate quadratic equation) and where you have $n$ unknowns, then relinearization can solve the system of equations in polynomial time (approx. $O(n^6)$ time or less).

Actually, you don't even need relinearization to solve this problem: simple linearization is sufficient.  In particular, if $x_1,\dots,x_n$ denote the unknowns, then for each pair $x_i,x_j$ of unknowns, you introduce a new variable $y_{i,j} = x_i x_j$.  Now we treat the $y_{i,j}$'s as additional unknowns.  With these additional unknowns, each equation is now a linear equation (in the $x_i$'s and $y_{i,j}$'s).  How many unknowns are there now?  Well, there are about $n^2/2$ of the $y_{i,j}$'s, and another $n$ of the $x_i$'s.  Consequently, we have $n^2$ linear equations in $\approx 0.5 n^2$ unknowns.  Since there are more equations than unknowns, we can use standard linear algebra to solve these linear equations.  The answer provides a solution to our original system of quadratic equations.

Relinearization is a generalization of this idea that works with a smaller number of equations, at some cost in running time.

For more on this subject, see the following research paper:

Cryptanalysis of the HFE Public Key Cryptosystem.  Aviad Kipnis and Adi Shamir.  CRYPTO 1999.

Cryptanalysis. With this background, it then becomes easy to see how to cryptanalyze your system.  Each bit of ciphertext reveals one quadratic equation on 128 unknowns, where the unknowns are the bits of the key $k$.  If we're given 16384 bits of known plaintext, then we have $16384 = 128^2$ quadratic equations in 128 unknowns.  Now we can apply linearization to recover the key.  (With relinearization, we could reduce the amount of known-plaintext required, but 16384 bits of known plaintext is already a very modest requirement, so the simple linearization attack is already devastating.)

Therefore, this algorithm falls to a simple known-plaintext attack.  For that reason, it does not meet the standard security requirements and is not suitable for use.


DSA, RSA, ECDSA etc - which one is cheapest for signing? For a protocol where the server presents its signature to prove authenticity (e.g. IKE/SIGMA/STS with only one party authenticated), it's essential that the signing is extremely cheap, while verification can be almost arbitrarily expensive.

RSA appears to be the worst alternative, but what about DSA vs. ECDSA? Is there some other signing algorithm that could be even better (i.e. consume even less CPU to calculate)?

From these three, ECDSA is faster - it does arithmetic with smaller numbers, and is thus faster. (RSA verification is faster than ECDSA, even though it uses larger numbers, because it computes a exponentiation by a small number.)

Still, elliptic curve Schnorr signature should be around 5-10% faster than ECDSA (or even more in a side-channel resistant implementation) since it does not require an inversion modulo the curve order. And as mentioned, there is also Ed25519, which uses a special, non-standard curve in order to be more efficient.


Normalization of points on an Elliptic Curve The Bouncy Castle source code (Java edition) has a ECPoint.normalize() function. It seems to calculate the modular inverse of a coordinate of a point on the curve. Without it point compression - for instance - seems to fail.

It seems that usually this normalization is performed as part of Elliptic Curve calculations automatically when other libraries are concerned.

So I've got the following questions:

After which operations is normalization required for elliptic curves?
What's this normalization about, is it just calculating the coordinates with a "positive" Y value on the curve?
Could leaving out the normalization of points trigger invalid calculations, or is this just about the representation of the point on the curve?

If there is any reference material available then I'd be interested to know about it.

For reference, the Java source code of Bouncy Castle:

/**
 * Normalization ensures that any projective coordinate is 1, and therefore that the x, y
 * coordinates reflect those of the equivalent point in an affine coordinate system.
 *
 * @return a new ECPoint instance representing the same point, but with normalized coordinates
 */
public ECPoint normalize()
{
    if (this.isInfinity())
    {
        return this;
    }

    switch (this.getCurveCoordinateSystem())
    {
    case ECCurve.COORD_AFFINE:
    case ECCurve.COORD_LAMBDA_AFFINE:
    {
        return this;
    }
    default:
    {
        ECFieldElement Z1 = getZCoord(0);
        if (Z1.isOne())
        {
            return this;
        }

        return normalize(Z1.invert());
    }
    }
}

ECPoint normalize(ECFieldElement zInv)
{
    switch (this.getCurveCoordinateSystem())
    {
    case ECCurve.COORD_HOMOGENEOUS:
    case ECCurve.COORD_LAMBDA_PROJECTIVE:
    {
        return createScaledPoint(zInv, zInv);
    }
    case ECCurve.COORD_JACOBIAN:
    case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
    case ECCurve.COORD_JACOBIAN_MODIFIED:
    {
        ECFieldElement zInv2 = zInv.square(), zInv3 = zInv2.multiply(zInv);
        return createScaledPoint(zInv2, zInv3);
    }
    default:
    {
        throw new IllegalStateException("not a projective coordinate system");
    }
    }
}

protected ECPoint createScaledPoint(ECFieldElement sx, ECFieldElement sy)
{
    return this.getCurve().createRawPoint(getRawXCoord().multiply(sx), getRawYCoord().multiply(sy), this.withCompression);
}

This is just about the representation of the point on the curve.

In the affine form of elliptic curve points, $(x,y)$ is the representation of points. But in the projective coordination, points are in the form $(X:Y:Z)$. Let $K$ be a field, and let $c$ and $d$ be positive integers and $\lambda\in K^*$. In this representation $(X:Y:Z)\sim (\lambda ^cX:\lambda ^dY:\lambda Z) $. That is, any element of an equivalence class can serve as its representative. In particular, if $Z\ne 0$ then  $(\frac{X}{\lambda ^c}:\frac{Y}{\lambda ^d}:1) $ is a
representative of the projective point $(X:Y:Z)$, and in fact is the only representative
with $Z$-coordinate equal to $1$. In this state, affine form of points is $(x,y)=(\frac{X}{Z ^c},\frac{Y}{Z ^d})=(X,Y)$.

For more details you can see page $86$ of "Guide to elliptic curve cryptography", Hankerson, ....


RSA Proof of Correctness Can anyone provide an extended (and well explained) proof of correctness of the RSA Algorithm?

And why is it needed?

I can't say that this or this helped me much, I'd like a more detailed and newbie like explanation, if you don't mind too much... ;)

After a couple of hours of detailed study I've come to an answer.

As we all know the RSA algorithm works as follows:

Choose two prime numbers $p$ and $q$,
Compute the modulus in which the arithmetic will be done: $N = pq$,
Pick a public encryption key $e \in Z_n$,
Compute the private decryption key as $d$ such that $ed = 1 \bmod{\phi(N)}$,
Encryption of message $m$: $c = m^e \bmod{N}$,
Decryption of crypto message $c$: $m = c^d \bmod{N}$.

While these statements and equations can stand true for some fixed values of $p$, $q$, $m$, $e$, $d$ in order to define the RSA as a general cryptographic algorithm we must prove their generality for any message $m$ we wish to encrypt.

This is therefore the reason why the proof of the correctness of the RSA algorithm is needed.

Getting to the proof we can formalise it as follows:

Hypothesis:

$\gcd(p,q) = 1$
$N = pq$
$ed = 1 \bmod{\phi(N)}$

Thesis:

$ (m^e)^d = m \bmod{N}$, for all $m \in Z_n$

  NOTE:The important part is ^^^^^^^^^ the for all part...

Proof:

Being $m \in Z_n$ there are only two possible cases to analyse:

  1) $\gcd(m, N) = 1$

In this case Euler's Theorem stands true, assessing that
$$ m^{\phi(N)} = 1 \bmod{N}\text{.}$$

As for the Thesis to prove, because of Hypothesis number 3, we can write:

$$(m^e)^d = m^{ed} = m^{1 + k\phi(N)}\text{,}$$

furthermore

$$ m^{1 + k\phi(N)} = m\cdot m^{k\phi(N)} = m \cdot (m^{\phi(N)})^k,$$

and for Euler's Theorem

$$m \cdot (m^{\phi(N)})^k = m \bmod{N}$$

Proving that the thesis stands in this case.

  2) $\gcd(m, N) \neq 1$

In this case Euler's Theorem does not stand true any more.

For a result of the Chinese Remainder Theorem (check this SO question - Chinese Remainder Theorem and RSA - or just wiki it) it is true that if $\gcd(p,q) = 1$ then:

$$ x = y \pmod{p} \land x = y \pmod{q} \Rightarrow x = y \pmod{pq}$$

So by proving the following two statements we would have finished:

$ (m^e)^d = m \bmod{p}$
$ (m^e)^d = m \bmod{q}$

Because $\gcd(m, N) \neq 1$ one between $\gcd(m, N) = p$, and $\gcd(m, N) = q$ must stand true. I will demonstrate that both the above statements stand true in the case $\gcd(m, N) = p$, being it absolutely identical (by switching letters) to prove it for $\gcd(m, N) = q$ as well.

So let it be $\gcd(m, N) = p$, this implies that $m = kp$ for some $k > 0$ which means that $m \bmod{p} = 0$. By concerning the first statement we also have

$$ (m^e)^d = ((kp)^e)^d$$

which therefore results to be a multiple of $p$, and so it is equal to zero.

So the first statement becomes $0 = 0$ and is proven to be satisfied.

Concerning the second statement we have that Euler's Theorem results to be proved in $Z_q$, since $\gcd(m,q) = 1$, so:

$$ m^{\phi(q)} = 1 \bmod{q}\text{.}$$

This implies that we can write:

$$\begin{align}
 (m^{e})^d &= m^{ed} \\
&= m^{ed - 1}m\\
&= m^{h(p-1)(q-1)}m\\
&= (m^{q-1})^{h(p-1)}m\\
&= 1^{h(p-1)}m = m \bmod{q}.
\end{align}
$$

which definitively proves the second statement and theorem.


Keeping IV secret for AES CFB mode I'm developing a security/encryption software and I'm using AES CFB (block size: 16 and key size: 32 bytes).

I want to know, if I also keep IV (32 bytes) secret like the key itself (32 bytes), would it add to security or not?

Encryption key and IV will not be specified by user, it will be generated and then encrypted with RSA and stored in safe storage. So I'm thinking to generate randomly key and IV. So if I also keep IV and key (both generated) in secure place would it make my crypto stronger or it's preferred to make IV constant in my application code?

Actually, for CFB mode, the IV is the same size as the block size, 16 bytes.

As for your question "does keeping the IV secret help security", the answer is "not really".

CFB mode processes the message in blocks, and for each block of plaintext, combines that with the previous block of ciphertext to generate the next block of ciphertext.  What the IV is used for is for the initial block of plaintext; there is obviously no previous ciphertext block, and so you use the IV instead.

What this means that if you keep the IV secret, it doesn't really hinder any particular attack in any way.  One way to see that is to assume the contrary; let us assume that, if we expose the IV to the attacker, that he can exploit some weakness.  If we assume that, then the attacker can use that weakness to attack a CFB mode encrypted text without the IV; what he does is take the ciphertext (without the IV), and treat the initial ciphertext block as the IV, and the rest of the ciphertext as the "real" ciphertext; the plaintext this corresponds to is the normal plaintext with the initial block omitted.

Because of this, if exposing the IV with CFB mode lead to a weakness, CFB mode in general is weak.  Now, written this way, this might not sound very comforting; however athat statement is logically equivalent to "if CFB mode is strong, then CFB mode with the IV mode exposed is strong", which is really what we want to show.

In addition, you ask whether:

  It's preferred to make IV constant in my application code

It is absolutely a bad idea to have a constant IV with CFB mode; he's why: the initial ciphertext block is:

$C_0 = P_0 \oplus AES( IV )$

What this means is that if an attacker sees two encrypted messages with the same IV and key, then he knows the above and also knows:

$C'_0 = P'_0 \oplus AES( IV )$

Even though is might not know what the IV is, he can combine the two equations to form:

$C_0 \oplus C'_0 = P_0 \oplus P'_0$

In other words, by examining the bit differences between the two initial ciphertext blocks, he can deduce the bit differences between the two initial plaintext blocks; that is far more information than we want an attacker to know.

Instead, you are far better off either using random IVs or possibly using a counter (if randomness is a problem for you).


ECDSA: How to retrieve a non-random k I have a question regarding the random $k$ number of ECDSA encryption. As far as I know, it is possible to retrieve $k$ (and thus the private key) from two signed messages if both used the same $k$. This was done for the PlayStation 3 hack. I'm now trying to reproduce it in Python, using this library.

My problem is that the hack only works in some cases (at least I think so). I've not been able to reproduce it, so I hoped you could help me.

Initially we have two equations:
$$
s_1 = k^{-1} * (z_1 + y) \mod n \\
s_2 = k^{-1} * (z_2 + y) \mod n \\
$$
(where $y = r*\mathrm{privatekey}$)

We want to get rid of y and figure out k. In all explanations I've seen so far, they'll do something like this:
$$ \begin{align}
s_1 - s_2 &= k^{-1} * (z_1 + y) - k^{-1} * (z_2 + y) \\
s_1 - s_2 &= k^{-1} * (z_1 - z_2) \\
\frac{s_1 - s_2}{z_1 - z_2} &= k^{-1} \\
k &= \frac{z_1 - z_2}{s_1 - s_2} \\
\end{align} $$

This doesn't work in my code, because in this hack, the modulo operation at the beginning is just ignored. If I we don't ignore it, the equation should look like this:
$$
i*n + s_1 = k^{-1} * (z_1 + y) \\
j*n + s_2 = k^{-1} * (z_2 + y) \\
$$

I got rid of the modulo by adding $x*n$ to the left side, where x (i or j) is unknown. With this equation I'll just do the same thing as above but keep the $+ x*n$:
$$ \begin{align}
i*n + s_1 - j*n - s_2 &= k^{-1} * (z_1 - z_2) \\
\frac{s_1 - s_2 + n*(i-j)}{z_1 - z_2} &= k^{-1} \\
k &= \frac{z_1 - z_2}{s_1 - s_2 + n*(i-j)} \\
\end{align} $$

Obviously we do not know $i$ and $j$. We can ignore them if $i = j$ (as we did in the first calculation), which is only the case when $z_1$ and $z_2$ are close together or $k^{-1}$ is very small (so that it pulls the result down and therefore prevents $z_1$ or $z_2$ from making too much difference).

In theory $k^{-1}$ is pretty small (since it's $\frac{1}{k}$) and therfore the exploit works. But in practice I've seen that $k^{-1}$ is not used, but instead the smallest inverse modulo of $k \mod n$ that is a whole number is used. This number can be really large, which actually amplifies the difference between $z_1$ and $z_2$, making $i-j$ pretty large. With this implementation, I can't use the exploit as explained in theory, because I never get my exact $k$.

My questions are:

Mathematically, is there another way to retrieve $k$, even if the $k^{-1}$ part is really large? Maybe using some inverse modulo?
Why is it that many implementations use the inverse modulo instead of $k^{-1}$? (I've seen it in two libraries so far)
Why doesn't it work when I change the implementation to use $k^{-1}$?

Since this is part of an assignment for Uni, retrieving $k$ still has to work somehow. But I already spent too much time on it without any results.
Any gurus out there that can help me? :)

I believe you are being confused by what $k^{-1}$ means.  It doesn't mean "interpret $k$ as a real number, plug it into a calculator, and hit the $1/x$ button".

When we use the $k^{-1}$ notation, what we mean to say is that $a = k^{-1}$ is equivalent to saying that $a \times k = 1$.

You will say "doesn't that mean doing exactly what a calculator does?".  Well, it would, if the multiplication was performed in the field of the reals.  However, we're doing everything modulo $n$ (within the field $GF(n)$, as $n$ is prime), and so the multiplication is done modulo $n$; hence we really have $a \times k = 1 \pmod{n}$.

In this context, when we write $k^{-1}$, we really do intend the modular inverse.  And, when we derive $k = \frac{z_1 - z_2}{s_1 - s_2}$, we're not ignoring the modulo operation; it's been assumed implicitly; what we really mean is $k = (z1 - z2) \times (s_1 - s_2)^{-1} \bmod n$, there $(s_1 - s_2)^{-1}$ is the multiplicative inverse (modulo $n$) of $s_1 - s_2$.

When you derive $k = \frac{z_1 - z_2}{s_1 - s_2 + n*(i-j)}$, well, since everything is done modulo $n$, including the internal additions, we effectively have $n=0$ (because, modulo $n$, those are the value), and so $i$ and $j$ drop out, and we're left with the original derivation.

Since you explicitly asked questions, I'll answer them (even if they ought to be obvious once the above has been clarified):

  Mathematically, is there another way to retrieve $k$, even if the $k^{−1}$ part is really large? Maybe using some inverse modulo?

Yes, an inverse modulo is precisely what you're looking for.

  Why is it that many implementations use the inverse modulo instead of $k^{−1}$? (I've seen it in two libraries so far)

The inverse modulo that the libraries do is what is meant by $k^{-1}$

  Why doesn't it work when I change the implementation to use $k^{−1}$?

The mathematics of ECDSA assume that the math works out in one specific field (the field $GF(n)$); if you do the computations in a different field (say, the field of real numbers), well, it won't work.


Significance of rotation constants in SHA-512? In a single round of SHA-512, in the operations $\Sigma_0(A)$, $\Sigma_1(E)$ why are the constants $28$, $34$, and $39$ used for the number of rotations? What significance do these numbers have? What if they are changed?

The SHA-2 family is built from a block cipher in a Davies-Meyer construction, where the message is considered they key, and the current hash value the plaintext. The 2nd set of constants in the SHA-512 round function is 14, 18, and 41. Rotations are also performed in the message expansion (key schedule), and are also important.

The block cipher at the center of the compression function must behave in a secure manner, and the rotational constants were chosen in such a way that the block cipher is resistant to standard cryptographic attacks. The round count was then fixed to meet the security requirement of the hash digest, plus some wiggle room for new attacks.

SHA-2 was developed in secret at the NSA, so the above is partly speculative, however we do have good examples of how improper choice of rotational constants can weaken a hash function. During the SHA-3 competition, the Skein hash function was successfully attacked using rotational cryptanalysis, and a change in the rotational constants was made to prevent the attack. The attack with the old rotational constants was 22 rounds more effective than the best attack on Skein with the new constants; that is 30% of the full round count, which is substantial.

The attack seemed to exploit the specific combination of rotations and modular addition, both of which are heavily used in the SHA-2 compression functions. The continued lack of highly effective attacks on SHA-2 implies that its rotational constants were chosen well. The way that rotations are used in SHA-2 and Skein differ, but poor constants would still have prevented proper diffusion within the round, or in the key schedule. The best attacks are still reduced round differential and biclique attacks, and are not practical.


Existing works on pre-computing ElGamal ephermal keys I was playing around with a problem in e-voting schemes that use additive homomorphic encryption to tally votes, namely that at the end of the day somebody (or somebodies, if the secret material has been broken up somehow) has to be trusted to decrypt the final tally.
Looking at ElGamal's additive variant, reproduced here for reference:

$M$ is a modulo field in which all computation happens
$g$ is a generator for $M$
private key = $k_2$ = random number < $M$
public key = $k_1$ = $g^{k_2}$
$m$ is a member of the modulo field $M$
$x$ is the plaintext
$r$ is a random number < $M$, different for each call to E

this is the ephemeral key, used in the second $D(...)$

$E(k_1, x) = <g^r, m^x * k_1^r> = <c_1, c_2>$
$D(k_2, c_1, c_2) = c_2 * ({c_1^{k_2}})^{-1}$
$D(r, k_1, c_1, c_2) = c_2 * (k_1^r)^{-1}$

In e-voting schemes*, every vote is represented as a 1 or 0 plaintext and tallying is a simple matter of multiplying all the ciphertexts together and decrypting the result.
The following scheme eliminates the need to release the private key to decrypt the final tally:
Prior to the "election"

precompute a large list of random numbers $R = [R_1, ... , R_n]$ where $n$ is  the number of possible voters
let $A = [A_1, ..., A_n] = [R_1, A_1+R_2, A_2+R3, ... , A_{n-1}+R_n]$
publish the hashes of each member of A in order

When encrypting "ballots"

when choosing an $r$ for a $E(k_1, x)$, choose the first unused member of R

After the election

publish all the ciphertexts (the "ballots")
publish $A_y$ where $y$ is the number of ballots cast

$A_y$ would be the ephemeral key for the tally, but wouldn't allow for the decryption of any other ballots (like the private key would).  The correctness of $A_y$ is achieved by the polling authority committing to its value by publishing hashes before hand.

In a nutshell, it's just publishing a commitment (via hashing) for all possible ephemeral keys for the final tally; then releasing the singular relevant ephemeral key.  Everyone can tally, and decrypt that tally but decrypting individual "ballot" values shouldn't be possible.
I built a little proof of concept program that actual does this (using some open source implementations of additive ElGamal), and it works.
Of course, simply working isn't sufficient; I'm curious about the security of the scheme.
My question, are there any publications or other work related to this approach?
This seems like a pretty simple extension to the well documented additive ElGamal e-voting schemes, but my Google-Fu is failing to find anything and I'm personally unfamiliar with any such material.
(This approach [the pre-computed ephemeral key part, specifically] being broken and why, also acceptable naturally)
*Simplified greatly from actual schemes, but this is the heart of the crypto bits.

It seems you want to decrypt the final value without revealing the private key. First, if someone knows the private key, they can issue a very simple non-interactive zero knowledge proof that the plaintext is a decryption of the ciphertext (the ciphertext being the accumulation of all the ballots) without revealing the actual value of the key. This is the standard way of approaching the problem. (I can add the proof if you are interested).

Second, the approach of pre-committing to the random factors for Elgamal has been examined in the literature however for completely different reasons. There is a worry that if a voting machine chooses the randomness, they could try a few values until the ciphertext comes out with a certain pattern (e.g., the 5th bit is a 0 if the vote is for Alice and a 1 if it is for Bob). Your scheme incidentally avoids this. A more thorough approach is considered in On Subliminal Channels in Encrypt-on-Cast Voting Systems
.

If you insist on your approach, note that you never need to use $c_1$ at all. $c_2$ alone is a simpler primitive called a Pedersen commitment. The approach of encoding votes with Pedersen commitments, adding them up (under commitment), and then revealing the sum of the random factors is considered in Improving Helios with Everlasting Privacy Towards the Public. The difference is that voters choose the random factor and submit an encryption of it rather than using factors chosen for them. (It also is being done for totally different reasons: Pedersen commitments have a property called everlasting privacy).

In terms of the security of your approach, it is not clear who knows R and how voters get their value of R. For example, if I give voter 5 the value ($R_5$ - 1) and give voter 6 the value ($R_6$ +1), they will still add up to the correct value of $R$. However voter 5's message will be $m^x/k_1$ and voter 6's will be $m^x*k_1$. These may be sensible values for a vote: for example say that $k_1=m^2$. If voter 5 votes for 0, then this can be counted as a -1 and if voter 6 votes for 1, it can be counted as a +3. In other words, you end up with 2 votes for candidate 1 instead of one vote for each.

It may be sufficient to choose $m$ in such a way that no one knows the discrete logarithm between $k_1$ and $m$ but I'd have to think about it some more before endorsing it.


Explanations for the complexity values for second preimage attack on GOST? I've been reading the article "A (second) preimage attack on the GOST hash function" by F. Mendel et al (link) and I'm having some difficulty to grasp some of the values of complexities/probabilities in the attack. Specifically:

On page 228, how is the probability that two pairs lead to the corresponding values $x_1$, $x_2$, and $x_3$ amount to $2^{-192}$?
On page 230, how is $2^{128}$ used in the calculation of the complexity of the compression function?
On page 230, why construct $2^{32}$ pseudo-preimages for the last iteration of GOST?
On page 231, how was the value for the probability of finding the right $M_{257}$ in the list $L$ obtained?
Finally, on another issue, what operation is referred to by the squared $\ominus$ symbol on page 231: $\Sigma^m = \Sigma^t \ominus M_{257}$. [My guess: subtraction modulo $2^{256}$ -- am I right?]

Thanks very much.

Preliminary: Almost the same article is available for free without breaking any law, nor downloading 5GB (formatting is shifted by at most one third of a page). It is also (as well as all other articles of IACR crypto conferences from 2000-2011) in the IACR Online Proceedings, specifically in the FSE 2008 section, but then you need to subtract about 223 from the page numbers quoted in the question to get the page number in the PDF. For this reason it is best to use section (rather than page) numbers to designate a section of an article.

I have now answered all the points (and learned along the way), but anyone remains welcome to improve that answer, made community wiki.

1) In section 3, why does the probability that two pairs lead to the corresponding values $x_1$, $x_2$, and $x_3$ amount to $2^{−192}$?

By construction, $x_i$, $y_i$, $z_i$, $s_i$ are 64-bit. We assume that the process that uncovered each pair, being independent of the relations $x_i=y_i\oplus z_i\oplus s_i$ for $i\in\{1,2,3\}$ (only concerned with that relation for $i=0$), makes each of these relations for $i\in\{1,2,3\}$ true with odds about $2^{-64}$; hence makes the three true with odds about $2^{-192}$ (again, without proof of independence).
That's typical in cryptanalysis: we assume odds that $a=b$ holds with odds $2^{-n}$ when $a$ and $b$ are $n$-bit with at least one of these quantity produced by a process that is engineered for a purpose independent of matching that relation, and that process's output or the other quantity has no clear bias. That probability would follow from assuming either quantities is uniformly distributed.

2) In section 4.1, how is $2^{128}$ used in the calculation of the complexity?

In section 4.1 it is considered a multicollision of $t=256$ message blocks, with for each block a pair of values that can be used interchangeably without changing the result in $H_{256}$:

For each of $t$ message blocks, the pair is found by the birthday attack on the output of $f$, which has $n=256$ bits, thus with about $2^{n/2}$ evaluations of $f$ using a technique such as Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications. Here comes the $2^{n/2}=2^{128}$ term!
The total cost of finding the multicollision is about $t\cdot2^{n/2}=2^{136}$. Notice that this is already totally impracticable in a foreseeable future: we are discussing a theoretical attack

3) In section 4.2, why construct $2^{32}$ pseudo-preimages for the last iteration of GOST?

That's a compromise between the work required in 4.2, which increases proportionally to the number $w$ of pseudo-preimages made; and the work required in 4.3, which decreases proportionally to $w$. The sum of work required for the two steps is thus of the form $a\cdot w+b/w$, and the minimum for that is for $w=\sqrt{b/a}$.
Here $a=2^{192}$, and $b=2^{256}$ (not quite in the same unit unless I err, but since this is a purely theoretical attack, that does not matter much), and it comes $w=2^{32}$ for the minimum.
In other words: one can change $2^{32}$ a little, the attack will still (theoretically) work. With an increase of that to say $2^{33}$, the expected work in 4.3 will be halved, but that's at the price of twice more work in 4.2, and twice more memory. Thus if we increase too much the work will be raised overall (dominated by 4.2), and if we decrease too much the work will be raised overall (dominated by 4.3). The value $2^{32}$ balances the work in 4.2 and 4.3, and is in the right ballpark for a minimum overall attack effort.

4) In section 4.3, how was the probability of finding the right $M_{257}$ in the list $L$ obtained?

The list $L$ contains $w=2^{32}$ pairs $(H,M)$ with $H$ of $n=256$ bits (distinct with high odds since $w\ll2^{n/2}$, under the standard assumption that the $H$ are random-like for reasons discussed in 1).
We want to find an $M_{257}$ that makes $H_{258}$ matching the $H$ of some $(H,M)$ in $L$. $H_{258}$ is next to uniformly distributed (no matter how we enumerate distinct $M_{257}$, because that's a design goal for $f$) thus each value tried has odds $2^{-n}$ to match any particular $H$ in the list, thus odds (only very slightly above) $2^{-n}\cdot w=2^{-224}$ to match one $H$ in the list, and that's the probability we wanted.
That part of the attack alone is expected to require trying $2^{224}$ values of $M_{257}$, thus $2^{225}$ evaluations of $f$, and that's also the stated cost of the attack: at this degree of impracticality, it is common to consider $u+v\approx u$ whenever $v<u$ and we repeat such approximation only a few times.

5) What operation is referred to by the $\boxminus$ symbol?

Indeed, $\boxminus$ (written $\boxminus$ on this website) is used in this article for subtraction modulo $2^{256}$. That is quite clear in the context of use of section 4.3 of the paper, given the definition of $\boxplus$ ($\boxplus$) in section 2 as addition modulo $2^{256}$. Note: to determine how to render a symbol in $\TeX$, I often try a detexifyer, and in that case it worked.

6) In Section 3, why does the system of equations with $5⋅64$ equations in $8⋅64$ variables results in $2^{192}$ solutions?

A linear system of $x$ linearly independent equations in $y>x$ variables is under-determined, and $y-x$ variables can be fixed to any value. If these are binary variables, that leads to $2^{y-x}$ solutions. We obtain $2^{192}$ as $2^{8⋅64-5⋅64}$.
The same occurs when solving the system of equations with $6⋅64$ equations in $8⋅64$ variables leading to $2^{128}$ solutions: we obtain $2^{128}$ as $2^{8⋅64-6⋅64}$.


Key Exchange MAC encryption order of events? Problem I want to write the sequence of events of how a MAC encryption works for documentation at work.
For this purpose I have a document (given by my boss to me) in German and I am trying to translate it into english. However I think there might be a mistake on step 4. I am not sure and some how cannot find anything on the Internet.

MAC Master Key generated

MAC Master Key given to the partner (by hand or by certificate protected mail)

MAC Slave Key generated

Encryption of the MAC Slave Key with the MAC Slave Key and sent to the partner (this transaction will be safe since only the partner has the Master Key for decryption)

Is the fourth step really encryption of a MAC slave key with the same MAC slave key and sending it to partner? Shouldn't we encrypt the MAC slave key with the MAC Master key?
I am sorry if it is a rookie question because I don't know much about MAC cryptography.
Please can someone also explain how Master key and Slave keys are connected to each other? If it matters I am using MAC 91.2 & D.96A

You're right, it seems like there is a typo in Step 4. The MAC Slave Key should be encrypted with the MAC Master Key, as that is the information that is shared between partners. This is alluded to in the parenthetical, noting that only the partner has the Master Key to decrypt it.


Is a number generator based on hashing an incremental string considered random? Consider the following system

1 - fixed string as a seed, example "something"

2 - concat an increment number "something-1"

3 - hash it, assume it is "9f2054ea4d2c"

4 - take the first 3 digits to get a number between 0 and 4095 for example

The next number will be taken from the hash of "something-2" and so on

No, the next number in the sequence of the generator in the question cannot be safely considered unpredictable. At least one reason for that: we can infer from the example seed value "something" that the seed is not entropic enough. An adversary knowing the method, the hash, and the first 3 outputs or so could very plausibly enumerate likely seeds from a dictionary of common English words, find one that matches known output, and use that to predict further outputs with fair confidence. Even with less output, the adversary can get a slight advantage compared to a random guess.

The scheme proposed would be computationally indistinguishable from true random under some reasonable but unstated hypothesis:

The counter never cycles or otherwise resets, which is not trivial to ascertain in practice (e.g. when adversaries can cut power at any time).
The computations are performed secretly and correctly; no untold leak of seed or intermediary results, or fault, occurs. This is hard to ascertain in practice (for a start, who knows there's no trojan in that computer? Also, side-channel/fault attacks are a real thing).
The seed is secret, large and random-enough that it can not in practice be found by enumeration using the computational power available to an adversary. It is acknowledged that 128-bit entropy is safe with current technology, and twice that more than safe enough even assuming hypothetical quantum computers usable for cryptanalysis. 128-bit entropy can be obtained with $\lceil128/\log_2(26)\rceil=28$ lowercase letters chosen independently and uniformly at random.
The hash is computationally indistinguishable from a Pseudo Random Function. As far as we know SHA-256 would be good enough in practice, especially with truncation of the output as we have here. SHA-512 would be even safer. Further, the HMAC construction could be used (instead of hashing the hash of a concatenation) to combine seed (used as key) and counter (used as the data input) in a manner giving more assurance against hypothetical attacks on the hash.
Note; standard properties of hash funcions are lesser than being a PRF, and do not even include having near equidistributed output for random input.
Leading zeroes in the hash are kept (which is not entirely clear in the question's statement), so that integers less than 256 are not underrepresented.


Friedman Index of Coincidence, pruning multiples of the keylength I'm trying to write a Vigenere decipher script. I defined a couple of possible keylengths using the Kasiski method, using roughly this method:

find recurring strings in the ciphertext between 3 and 12 characters
make a list of the distances between them
loop through the list of distances and calculate the greatest common denominator between each distance[n] and distance[n+1]
count the GCDs and send the top 3 to the Friedman function

In the Friedman function:

For each of the GCDs (= possible keylengths) that my Kasiski function returns I calculate the IC, but sometimes a multiple of the keylength is closer to the standard English IC than the actual keylength. This is usually a difference of only 1-3%. Since I do not weigh them by the amount of times the keylength came out in the GCDs counter, it sometimes happens that for a key of 3 characters my function returns 6 as the most likely keylength.

My question is, should I:

Preserve the amount of times a GCD was established between two distances in the Kasiski function, weighing the outcome of the Friedman function with it  to prefer the most occurring GCD
In the Friedman function, check if a possible keylength is a multiple of another possible keylength, comparing the ICs and discarding the multiple if the difference is (for example) less than a few %
Both, neither, anything else?

I suspect, when the IC was invented, it was typically used together with human judgement, so there might not be any standard rules to address this issue.

Anyway, it seems like there are two plausible solutions:

It might be easy to add a special case for this situation: choose the keylength with the highest IC, except that if it has a divisor whose IC is within 10% of it, choose the divisor.
Another plausible solution would be to try running the rest of your attack on both candidates.

I would imagine either of these might work fine.


How long would it take on average to perform a timing attack on HMAC over brute forcing a 32bit tag if the hash is good? How long would it take on average to perform a timing attack on HMAC over brute forcing a 32bit tag if the hash is good?

For example, let's take the hash: 79b7cdc3 to calculate the first byte you have to try:

00 000000
01 000000
02 000000
.........   n^256
FE 000000
FF 000000

total number of guesses and thus 79 would be the 79th guess.

So would the probability of guessing the first byte be, n^256 ?

Or am I going about this wrong?

Yes, if you have a 100% certainty that you can measure each timing then this is the way to go about it, approximately.

You'd have 128 tries on average per byte, so you'd need 128 * 4 = 512 tries, or $2^9$ bits of security to break, that's next to nothing. This is of course an average, the attacker may be lucky or unlucky, the maximum amount of tries would indeed be 256 * 4 = 1024 tries (or 1020 really, as you don't need to test the last byte value due to the power of deduction) and 1 in case of extreme luck.

There are however a few things wrong in your question:

timing attacks often require a large number of retries to find just one correct value - timing attacks usually rely on statistic, instead of an oracle that immediately tells you if you're correct or not.
you don't need to bother with the exponentiation of 2; there are just a maximum number of tries per byte: 256 (or 255), so the probability of guessing the first byte is just $1/256$, next guesses however will have a higher probability (as the number of untested values goes down).


P256 Key size and validation Given a public key on the P-256 Curve is it correct to say that the public key is 64 bytes long ie. (x,y)?

Secondly is the private key 32 bytes long? if so, how is the private key generated and why is it shorter than the public key?

The private key can be anything within the group order, if you take the key more than 32 bytes, then your key will work, but due to the cyclic nature of the group, your public key will be equal to the remainder of the key from the group order (modulo the group order).

As for the public key, it will not necessarily be 64 bytes (two numbers are the x and y coordinates, modulo the final field p), because, for example, the x or y coordinate can be less than 32 bytes, which ultimately will give public key less than 64 bytes.

The private key is generated using complex random cryptographic functions. You can also flip a coin 256 times and write 0 or 1 when an eagle or tails falls out, so you get a 256 bit (32 byte) random number, or you can use the random number generation functions that many cryptography protocols have.

Here my answer for private key more 32 byte for secp256k1, but the meaning is the same


Modes of encryption for hard drives? What are the currently recommended modes of encryption for large disks? Basic requirements would seem to be that you can update an encrypted sector independently of others, which rules out most standard modes of operation except CTR. For example are there any problems with taking the counter to be the current block number + some initial offset that could be stored for example on the first block.

What security models are usually considered for disk encryption? Is IND-CPA-security (as offered by CTR) enough?

The standard for full-disk encryption (FDE) is XTS mode or ESSIV-AES-CBC.

XTS tweaks each block within each sector differently (and hence avoids ECB's problems) and is considered the best choice available at the moment.

ESSIV-AES-CBC works by using AES-CBC with the IV being the hash of the sector index. The problem with this mode is that you can flip bits at arbitrary positions if you can accept the previous block being "destroyed"(completely scrambled), which you can  very often. F.ex. one could tweak down attack security critical bits and hence compromise the online-security of the system.

CTR would be a really bad idea for disk-encryption as you'd have the same problems as with CBC but you'd also loose "poor-man's-authentication" (-> at least one block gets scrambled), as you can know flipped bits at arbitrary positions without any problems.

What would be optimal for disk encryption would be a mode that turns a small block blockcipher (->AES) into a very large block cipher without too much speed penalties. (2 calls at max) That's was Bitlocker's elephant diffuser tried.

The best solution in my eyes would be to simply have a blockcipher with a very large blocksize that is considered secure. In my personal opinion, Threefish(-512/-1024) would be a nicer option than AES, but it isn't adopted.

You might be interested in this.


The problem of 'Common DH Primes' NSA crack multiple encrypted channel by some tricks on 'Common DH Primes', which is a old news, but how actually they crack it? I still can't get the concept why using a 'Common DH Primes' will comprise a system. Can someone explain the process to crack a encrypted channel by using 'Common DH Primes'?

I'm assuming you're referring to logjam.

Using a common DH prime doesn't by itself compromise a system. But using a DH prime that is potentially within computational reach of an organization, especially one that is widely used, is. The authors estimated that cracking a 1024 bit prime might be possible for an organization such as the NSA, given a huge amount of resources (several hundred million dollars) and time (1 year).

Attacking DH is done by computing the discrete log, using an algorithm called NFS. It turns out that for the classical DH (using the multiplicative group of integers, modulo a prime $p$), the attack can be amortized over all discrete logs in a group. In other words, most of the work needed to solve the discrete log using NFS only requires knowledge of the group (defined by the prime $p$), and not the computed value $g^a$ (different for every connection). This means that the attacker can do a huge amount of precomputation and then attack individual connections very quickly.

So the authors suggest that since most of the internet uses only 1 or 2 specific 1024 bit primes, an organization could invest heavily to do the necessary precomputation. Then individual connections can be broken quickly, by computing the last step in NFS. If you want to know how that works, read the link K.G. gave, or learn how NFS (Number Field Sieve) for the discrete log works.

All this can be prevented in a couple of ways. One, simply use larger primes. Even if the entire world used one specific 2048 bit prime, it would (probably) be impossible for an organization to crack encryption in this manner, amortization or not. Better yet, switch to elliptic curve DH. Elliptic curves don't suffer from the same precomputation woes, meaning attacks on parameters that are barely within computational reach only compromise one connection, rather than all those using that group.


Privacy of randomness using extractors and PRGs The Wikipedia article on randomness extraction states that they are different to pseudo random number generators but the distinction is very hazy. Both seem to take in some input quasi-randomness and produce a uniformly random output.

I'm interested in the security aspect of the generated output. I want my final randomness to be private. For PRGs, knowing the seed completely compromises the generated output. Is this also the case for extractors i.e. they are only as secure as the privacy of the input randomness?

More generally, if I have no control over the privacy of my source of randomness, is there any way I can generate (assuming a public protocol that I follow) a private and random string?

Yes, a true random number generator (TRNG) is only as secure as the privacy of the input randomness.  We call the input randomness entropy. You're conflating a TRNG and a pseudo random number generator (PRNG) with a randomness extractor.

A randomness extractor is simply a statistical combobulation and transmogrification of an arbitrary input distribution to a uniform distribution.  And to reduce inevitable correlation to negligible amounts. It's a component downstream of an entropy source or state. That's it. So an extractor might convert a correlated and normally distributed set of physical samples to an uncorrelated and uniformly distributed set.

There's no strict cryptographic security involved other than (input entropy) > (output). The security of the TRNG comes from the fact that since less entropy is output than input, it is mathematically impossible to discover  the original entropy.  Some people like to use cryptographic functions as the basis of randomness extractors, but that's not really necessary. However since this is a crypto forum...

Two examples:-

Have a 128 bit counter as a state. Repetitively increment that state.  Then encrypt that state with a keyed cipher like AES. You could argue that the encryption part forms a randomness extractor in a PRNG.  However, this is not a common paradigm.
Have some physical process generating a truly random digital signal with a wonky distribution.  Use some matrix multiplication or cryptographic hashing to produce a uniform distribution with an output bias < $2^{-64}$. This multiplication /hashing component is the randomness extractor part of a TRNG.

Now of course if someone knew the original state /entropy, the output sequence would be predictable. Unless you encrypted it with another cipher using a private key, or hashed it with a concatenated private IV. But what would the advantage be over a common PRNG in that case? It would be tantamount to example 1, but worse in that you'd have no idea of prejudice in the public sequence.


How can IND-CPA encryption be identity revealing? This is problem 10 of Chapter 4 "Symmetric Encryption" (pdf) from Lecture notes by Bellare and Rogaway:

  An IND-CPA secure encryption scheme might not conceal identities, in
  the following sense: given a pair of ciphertexts C, C′ for
  equal-length messages, it might be “obvious” if the ciphertexts were
  encrypted using the same random key or were encrypted using two
  different random keys. Give an example of a (plausibly) IND-CPA secure
  encryption scheme that has this is identity revealing. Then give a
  definition for “identity-concealing” encryption. Your definition
  should imply IND-CPA security but a scheme meeting your definition
  can’t be identity-revealing.

How can a scheme that is identity revealing be IND-CPA? I understand that the view of changing the key is not the same as changing the message but the point of ensuring security is to make sure that no additional information is revealed.

Consider an IND-CPA secure scheme that has the setup, encrypt and decrypt functions as $S_{secure}$, $E_{secure}$ and $D_{secure}$ respectively. Consider another scheme with setup, encrypt and decrypt functions as $S_{IR}$, $E_{IR}$ and $D_{IR}$ respectively.

Let $S_{IR}$ be the same as $S_{secure}$ to produce the key $K$. Let $E_{IR}$ run $E_{secure}(K, x)$ to get the ciphertext $C$, and return $C||H(K)$ where $H(x)$ is a collision resistant one way hash function. Let $D_{IR}$ simply discard the hash part of the ciphertext and use $D_{secure}$ to decrypt.

If, $S_{secure}$, $E_{secure}$ and $D_{secure}$ form an IND-CPA secure encryption scheme, $S_{IR}$, $E_{IR}$ and $D_{IR}$ also form an IND-CPA secure scheme, but the latter is identity revealing.

Note that no additional information about any of the messages is revealed in this case, and this is the only thing that IND-CPA security wants to control for. The IND-CPA security notion does not care if some information about the key is revealed.


Confusion about definition of homomorphic encryption I am trying to better understand homomorphic encryption, but I feel like I keep getting inconsistent information in the papers that I am reading.

One of the papers I am reading says the following:

  Earlier, homomoprhic encryption was defined as a form of encryption
  where a specific algebraic operation performed on plaintext is
  equivalent to another algebraic operation performed on its ciphertext

Meanwhile, another paper says the following:

  For now, a homomorphic cryptosystem can be thought of as an oracle, or
  black box, that, when given two ciphertexts and an operation, returns
  an encryption of the result of that operation on the two
  corresponding plaintexts.

The wording of the first one makes it seem as though the operation does not have to be the same (it says "another"), but the wording of the second one makes it seem as though the operation IS the same.

Can somebody clear up which one is correct?

The operation does not have to be the same. For example, with Paillier, we multiply ciphertexts to get the addition of the plaintexts.

That said, I think what the 2nd quotation is saying is that the operation that is passed to the oracle is the desired operation in the plaintext domain. The oracle knows how to translate that operation into something that, when performed on the ciphertexts, results in the desired operation in the plaintext domain.


Is there a term for cryptographic attacks where you can verify decryption without assuming any known structure on the plaintext? The questions https://security.stackexchange.com/questions/1696/if-someone-breaks-encryption-how-do-they-know-theyre-successful and https://security.stackexchange.com/questions/119887/how-to-know-if-a-file-is-decrypted-or-not on Information Security SE both ask how someone can verify whether they've successfully decrypted a ciphertext. The answers to both questions (as well as this old article by Bruce Schneier) all give the following complementary answers:

In the overwhelming majority of practical cases where someone's bothering to use encryption, the plaintext has some known structure and recognizing it is easy in practice.
If for some reason you encrypt truly random data, then the ciphertext can't be cracked, because the plaintext can't be recognized.

However, both of these answers seem wrong to me. (I think) a simple counterexample to both is given by one of the single most common cryptography protocols in the world today: the key encapsulation part of hybrid cryptosystems, which are extremely common. For example, a common cryptosystem uses RSA to encrypt an AES symmetric key and publicly transmit the encrypted key, which is then decrypted and subsequently used to encrypt and decrypt the data itself.

In this case, the "message" in the first stage (the key encapsulation using RSA) is an AES symmetric key, which is indeed a completely random bitstring. Contrary to claim 1 above, people encrypt completely random plaintext all the time.
Fortunately for the attacker, claim 2 above is wrong as well. If you manage to factor the RSA public key and then decrypt the message, then you can easily tell that you've obtained the correct plaintext without even looking at it, let alone verifying that it's structured. All you have to do is multiply the two numbers in the private key together and verify that their product is the public key.

My question is twofold:

Is my understanding correct? Is there something that I'm missing that makes these answers correct?
If my understanding is correct, is there a term for a cryptographic attack (like factoring an RSA public key, but unlike guessing a one-time pad) where there exists some method of checking the attack's success without assuming any known structure on the plaintext?

You're missing that using a KEM for hybrid is not encrypting random garbage.
Say you have a chain of ciphertexts $C_1||C_2||\dots|| C_n$, where $C_1 = \mathsf{Enc}_K(k)$, where $k$ is an AES key, and $C_2||\dots||C_n$ is the result of encrypting some stream of plaintexts under the AES key $k$ in some mode of operation.

If we can compute $k = \mathsf{Dec}_K(C_1)$, we can easily check if we decrypted correctly by decrypting $C_2||\dots||C_n$ under the aforementioned mode of operation.
Assuming this data has any structure (or any way to distinguish it from random garbage essentially), one can bootstrap that to a method to distinguish $\mathsf{Dec}_K(C_1)$ from random garbage.

If someone did encrypt (using the block cipher mode of operation) some sequence of random data $P_3||\dots||P_n$ (one block is used for the IV in the mode of operation), we could no longer use the aforementioned method to distinguish a correct AES key.
Then the linked comments would still be problematic (from the perspective of an attacker) --- there's no way to distinguish a bunch of random garbage from random (provided its distributed the same), so its essentially hopeless to ask.

This is essentially making the point that just because $k$ is (hopefully) uniformly random on some domain by itself, the rest of the ciphertext blocks are highly dependent on it, which can be utilized to develop a "correctness test" for guessing $k$.
So $C_1$ satisfies the "random garbage" property, but $C_1||\dots||C_n$ (jointly) doesn't.

Your second question is interesting, but I can only comment on the first question unfortunately.


What does "a 15360-bit RSA key is the equivalent to a 256-bit symmetric key" mean? NIST key management guidelines suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys. If a 15360-bit RSA key is the equivalent to a 256-bit symmetric key, does that mean a 15360-bit RSA key can prevent factoring  by the strongest quantum computers in the next 100 years or so? If not, how can the following statement be true?

  …a 15360-bit RSA key is the equivalent to a 256-bit symmetric key.

So, a 256-bit symmetric key could be reduced to 128-bit with Quantum computers (Grover's algorithm). Even if it takes 20 years or so from now to develop a strong enough quantum computer, once quantum computers become strong enough, a 256-bit symmetric key would still be strong enough to prevent brute forcing when the keys are random enough. So, do they think a strong quantum computer can factor 15360-bit RSA keys using Shor's algorithm (or any similar algorithm) in 100 years or so from now?

The statement

  a 15360-bit RSA key is the equivalent to a 256-bit symmetric key

does not take into account quantum algorithms. In fact, it is based on a specific computation model.

It is just based on the fact that there exist sub-exponential algorithms for factoring and therefore you need longer keys than when using symmetric-key crypto where it is believed that there is no attack that is more efficient than exhaustive search.

I'm not 100% sure, but I think the NIST standard is based on a paper by Lenstra and Verheul (PDF).


RSA CRT modulo reduction I am working on RSA CRT and there is a point that I don't understand :

So we have $n=pq$ and $c = m^e \bmod n$ an encrypted message.

To decrypt $c$ with RSA CRT, we have to compute :

$d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$

Why do we have to do a reduction $\bmod (p-1)$ and not $\bmod p$ ? (Same for $(q-1)$ and $q$)
Plus, next computations are made $\bmod p$ and $\bmod q$, right ?
($m_p = c^{d_p} \bmod p$ and $m_q = c^{d_q} \bmod q$)

To reduce modulo $p$ instead of $(p-1)$ to compute $d_p$ could allow attacks for example ?

Thank you in advance :)

RSA CRT (with $N$ the product of two distinct primes $p$ and $q$) implements the $x\to y=x^d\bmod N$ private-key function by computing $y_p=x^d\bmod p$ and $y_q=x^d\bmod q$; then combining $y_p$ and $y_q$ into the desired $y$ by constructing the solution to the equations $y\equiv y_p\pmod p$, $y\equiv y_q\pmod q$, $0\le y<N$, with that last step requiring comparatively little computing effort. It is beneficial from a computational perspective because (assuming $p$ and $q$ have the same bit size, or nearly so)

we can compute $y_p=x^d\bmod p$ as $y_p={(x\bmod p)}^d\bmod p$; this computation multiplies numbers half as wide as $x^d\bmod N$ would do, hence requires (asymptotically) 4 times less elementary operations when using standard multiplication algorithms; so total computational effort can be reduced by a factor of (near) 2;
it is easy to run the two sub-calculations in parallel, so elapsed time can be reduced by a further factor of (near) 2.

So, in RSA with CRT, we do not have to compute $d_p=d\bmod(p-1)$ and $d_q=d\bmod(p-1)$ as stated in the question; we can do it for additional savings, as explained below.

One form of Fermat's Little Theorem states that if integer $x$ is not a multiple of prime $p$, then $x^{p-1}\equiv1\pmod p$. If we set $d_p=d\bmod(p-1)$, or more generally chose any $d_p\equiv d\pmod{(p-1)}$, then by definition $d=k\cdot(p-1)+d_p$ for some integer $k$, thus
$$x^d\equiv x^{k\cdot(p-1)+d_p}\equiv(x^{p-1})^k\cdot x^{d_p}\equiv1^k\cdot x^{d_p}\equiv x^{d_p}\pmod p$$
Noticing that the above equation also holds when $x$ is a multiple of $p$ provided that $d>0$ and $d_p>0$, we can thus compute $y_p=x^d\bmod p$ as $y_p=x^{d_p}\bmod p$, or rather $y_p={(x\bmod p)}^{d_p}\bmod p$. The reduced exponent $d_p$ is less wide than $d$ by a factor of (nearly) 2, with about that saving in computational effort and time (combinable with the aforementioned savings).

Note: It may turn out that $d_p=k\cdot(p-1)+(d\bmod(p-1))$ for some $k$ (possibly negative) with small $|k|$ would be a more efficient choice than $d_p=d\bmod(p-1)$. That's typically only a tiny extra saving; exactly when will depend on the particular exponentiation algorithm used, and for negative $k$ on the cost of computing a modular inverse $\pmod p$.

Note: RSA CRT also has drawbacks, e.g. different vulnerability to fault injection and side-channel attacks.

As to why $d_p=d\bmod p$ does not work: there is no reason that it would, and experiment with small values proves that it does not in the general case.


Formal verification of elliptic curves. Depence on the equation form I'm doing formal verification of the group properties of elliptic curve addition in Weiertrass form. I was taking as a reference this and this articles. The first does the verification for Weiertrass form and the second does it for Curve22519, a Montgomery curve, but his approach can be generalized to Weiertrass form.

My question is, can I proof the group properties for the Weiertrass form and then translate the operation from this form to Montgomery form or Edwards form? I believe the three of them present some "equivalent" families of curves. Would this approach preserve the good properties of each family?

For instance, say I do the verification for Weiertrass form and then I "convert" the results to Edwards form. Would this be still side-channel attacks resistant?

For instance, say I do the verification for Weiertrass form and then I "convert" the results to Edwards form. Would this be still side-channel attacks resistant?

Well, if you have a Weierstrass form and an Edwards form of the same curve, they're actually the same group, with an easily computable isomorphism between the two, and so any group property (including things such as the difficulty of the discrete log problem) would be preserved.

However, you specifically asked about side channel resistance; that's not a group property.  Instead, it is a property of the implementation (as a side channel attack listens into internals of the implementation as it computes).  If you have two different implementations of the same curve (for example, a Weierstrass implementation and an Edwards form implementation), then proving that one of your implementations is resistant to a specific side channel attack says nothing about whether your other implementation is.


Universal Circuits in Indistinguishability Obfuscation Candidate Construction I am currently working on an implementation of the candidate construction for an indistinguishability obfuscator that was recently proposed by Garg et al. The relevant paper can be found here. Specifically I am only implementing the construction for circuits in NC1, because the construction for polynomial-sized circuits requires homomorphic-encryption.

In the construction of the indistinguishability obfuscator, they transform a universal circuit into a branching program and fix parts of its input to obtain the obfuscation of the original circuit. Since universal circuits can be quite big and tedious to generate, I am wondering, why it's even necessary to use them. In how far is a universal circuit with partially fixed inputs different from the original circuit? Would it not be possible to simply transform the original circuit into a branching program and apply the whole obfuscation process to it?

The proof of security in the paper is not trivial to me, so it's not clear for me, in how far the security relies on the usage of the universal circuit. I'd be thankful for any enlightenment on the issue :)

As @D.W. guessed, the branching program for a circuit essentially reveals the original circuit.  It's not clear what you mean by "apply the whole obfuscation process to the circuit-revealing branching program," but the prospects for that do not seem good: evaluating the branching program is highly sequential (polynomial depth), and you would need to obfuscate that procedure.  In all, you've reduced the goal of "obfuscate a log-depth circuit" to "obfuscate a poly-depth circuit" – that's negative progress!

By contrast, the universal circuit has a fixed branching program, so it obviously reveals nothing about the circuit to be obfuscated (except an upper bound on its size).  Also, the UC's input (the circuit to be obfuscated) is "concealed" by the multilinear map.


Is there any proof for ECDSA signature algorithm? Related: Is there an interactive version of ECDSA signature protocol like the Schnorr identification protocol?

As pointed out by @SEJPM, you can read more about security proofs for DSA/ECDSA family on this thread.
As for whether there exists an interactive protocol corresponding to DSA/ECDSA à la Schnorr identification/Schnorr signature, not that I am aware of. I would add that this is unlikely for two reasons:

The (unfortunate) reason for coming up with DSA/ECDSA was to bypass the patent on Schnorr signatures. Therefore its design was supposed be different enough from Schnorr.
If there were some kind of a sigma protocol then it is very likely that this would lead to a security proof (at least in the random-oracle model) as there exist standard methods to construct signatures from identification. Since we don't know a proof, one could say that there probably isn't an interactive protocol either (but this argument is very hand-wavy).


Are there any homomorphic first and second preimage resistant (cryptographic) hash functions? Are there any homomorphic cryptographic hash functions that satisfy $\text{H(A + B)} = \text{H(A)} + \text{H(B)}$ which maintaining pre-image resistance

Fix a finite group $G$ of order $\ell$, written additively, in which discrete logarithms are difficult.  Fix a standard base point $P \in G$ of large prime order.  The function $H\colon \mathbb Z/\ell \mathbb Z \to G$ given by $$H(n) := [n]P = \underbrace{P + \cdots + P}_{\text{$n$ times}}$$ is a preimage-resistant homomorphism: $H(n + m) = H(n) + H(m)$, and finding preimages is exactly finding discrete logarithms.

Of course, if $\ell$ is prime, then $H$ is injective and so doesn't compress its input at all; while if $\ell$ is composite, then $H$ is not collision-resistant since $H(n + \operatorname{ord} P) = H(n)$ for all $n$.  See the linked answers to address collision resistance.


Algorithm/Technique for Steganography What is the most used Algorithm/Technique in Steganography? I made some research about the algorithm/technique and I think Least Significat Bit(LSB) is the most used algorithm, is there any more efficient algorithm/technique that can be use for Steganography aside from LSB?

I'm assuming you're referring only to static image manipulation, as that's the common fear these days (terrorists are hiding data in eBay images!)  But it's a mistake to think that images are the only potential carriers of hidden data.  Data can hide wherever information moves, including audio files, DNS requests, TCP port knocking, error codes, URLs, Unicode, spam, anywhere.

LSB is often used in stego demonstrations because it's a simple and understandable example of the idea, but it has a lot of weaknesses that make it less than perfect for real world use.  For one thing, it works directly on bitmaps, but not compressed images.  If the message is short and modifies only the first half of the picture, the top of the image will have a "static" appearance that magically cleans up in the bottom half.  Also, BMPs may themselves be suspicious, as most people use compressed formats such as JPG or PNG.

Using LSB on an ordinary GIF would give you crazy incorrect colors, but you could use a modified palette with 128 duplicated colors to hide the data invisibly.

Both of these are easy experiments to perform and demonstrate to an audience.  You can show them a before and after picture.  You can show them a photo of a clear blue sky over the ocean, then mar the top third with an LSB stego message.  Then show them how a photo of a forest of autumn leaves or a field of wheat makes the effects of LSB stego almost invisible.  Show them how LSB messes with GIF images, then show them a reduced palette image followed by the same image with an LSB stego message.

Messing with JPEG and TIFF formats is technically much more difficult, but in the real world would probably do a better job of remaining hidden.  But they're still detectable to someone looking for them.  Each camera and image manipulation software package uses a custom "quantization table" that says how a block of pixels will be encoded.  Canon's are distinct from Nikon's.  Both are distinct from Adobe's, GIMP's, ImageMagick's, etc.  If your image has some quantized blocks that match those from Canon, but others that aren't recognizable, an eavesdropper might determine it was tampered with.  For a start to more information, see http://www.imagemagick.org/Usage/quantize/

A long time ago, the program OutGuess did a good job at spotting steganographically altered images encoded in many different image formats, but as far as I know the author never released the source.