How does a non-prime modulus for Diffie-Hellman allow for a backdoor? Recently someone found that a Diffie-Hellman modulus used in a unix tool (socat) was not prime. This led some people to shout "backdoor".

What I don't understand is, how could this allow for a backdoor?

I'm guessing the problem could be small subgroup attacks. But this can be as much of a problem as when the modulus is prime. Or better: a non-prime group could have a big prime subgroup while a prime group could have small prime subgroups.

Thoughts?

It seems like Pohlig–Hellman could be one answer: you can compute the discrete log in a smooth order group. Someone started testing small factors of the non-prime modulus and found 3684787 = 271 x 13597 as a factor. It doesn't seem like any other "easy" factors are findable, so does this mean Pohlig–Hellman wouldn't work even if the adversary knows the factorization? (He needs small factors, not only known factors.)

How could this allow for a backdoor?

Well, if you do DH modulo a composite, an attacker can recover the shared secret if they can solve the DH problem (or the DLog problem) modulo each of the primes that make up the composite.

There are a couple of ways that could be used by someone who knows the factorization to solve the DLog problem easier than expected.

Each prime could be set up to admit to a small subgroup attack (that is, each of the primes $p, q$ has $p-1, q-1$ smooth; however that also makes it easier to factor (as Samuel notes). On the other hand, one could have a $p$ and $q$ "partially smooth"; say, both $p-1$ and $q-1$ would include a factor circa 64 bits.  This would give a DLog that takes $O(2^{32})$ time (annoying, but quite feasible); while the $p-1$ factoring method would likely take $O(2^{64})$ time (which is likely that no one would bother trying).

A variant of this approach (if one can select $g$ as well) is to select $p-1 = 2p_1p_2$, where $p_1$ is a (say) 32 bit prime, and $p_2$ is a 479 bit prime, and select $g$ so that (mod $p$) is generates a subgroup of order $p_1$.  And, of course, you do the same for $q$.  The DLog problem that you actually see would take $O(2^{16})$ work, and $pq$ would be hard to factor (unless someone guesses $p_1$, and computes $gcm(pq, g^{p_1}-1)$; the backdoor-installer would be hoping that no one would think of trying that)

Another way would be for have the composite be (say) a factor of 4 256 bit primes, which need not admit to small subgroups.  In that case, to someone knowing the factorization can solve the DLog problem by solving 4 problems modulo 256 bit primes; a bit more effort than what a small group attack can do; however it's still practical (and the composite would still be difficult to factor).

A third method is to select primes $p$ and $q$ to be SNFS friendly; that is, both of the form $r^e + s$, for $r, s$ small.  If $p$ and $q$ use different values for $r$, this would not be immediately apparent.

So, yes, the composite modulus could be a backdoor.


Discrete Logarithm in a specific group I am considering a setting similar to the one of the Paillier cryptosystem, where we sample two distinct odd primes $p,q$, we set $n=pq$, we generate $a \leftarrow \mathbb{Z}_{n^2}^*$ and finally we set $g = (n+1) a^n \mod{n^2}$.

My question now is if the discrete log with the parameters $(g, \mathbb{Z}_{n^2}^*)$ is known to be hard, i.e. if given $(g, g^x)$, one can simply recover $x$, where let's say $x \in \mathbb{Z}_n$.

I know that we can apply Chinese Remainder Theorem in this case, but is this alone sufficient for breaking the Discrete Log?

Thank you very much!

Discrete logarithm can be hard in Paillier group. One case for example is when $p$ and $q$ are safe primes, i.e. $p=2p'+1$ and $q=2q'+1$ where $p',q'$ are themselves prime.

You can find more information about the critieria in this paper (and from its references): On the Portability of Generalized Schnorr Proofs, by Camenisch et al, Eurocrypt 2009


One-way hash on encrypted data, result hidden from hasher I'm looking for a one-way hash function that can be performed by A on an encrypted piece of data E(D) provided by B, without the performer A able to figure out D or H(D). This similar to HMAC(Message, Key), except the output hash cannot be known by A.

Usage:

B encrypts data D => E(D)
B sends E(D) to A
A contains a secret key SK
A performs F(E(D), SK) => E(H(D))
A sends E(H(D)) to B
B decrypts E(H(D)) => H(D)

Constraints:

A cannot recover D
A cannot recover H(D) from E(H(D))
B cannot recover SK from E(H(D)) or H(D)

I believe there may be a solution involving public/private key cryptography, but I'm not about to roll my own.

If you are not limited to HMAC, blind signatures would meet your requirements.

In RSA, you can do blind signatures as follows:

Let $M$ be the message to be signed (probably the hash of a message) and let $e,N$ be A's public key, $d$ is A's private key.

B computes $M' = M\cdot r^e \bmod{N}$ and sends $M'$ to A.
A computes $S' = M'^d\bmod{N}$ and sends it to B.
B computes $S = S'\cdot r^{-1}\bmod{N} = M^d\bmod{N}$ (i.e., $M$ signed with A's private key).

I am not aware of any libraries that support this scheme out of the box, but it wouldn't be too hard to add the functionality. Also, other cryptosystems would support this idea too.

Homomorphic Encryption
Using fully homomorphic encryption, this would be very possible to do. You would just need to implement a homomorphic version of a hash function and build it up into an HMAC function. Given current public-key homomorphic technology, it would be very slow. Still, though, this technology is too new for deployment.

Garbled Circuits
Another option for implementing HMAC that should meet the requirements you have stated is garbled circuits. Garbled circuits can evaluate AES privately much faster than even the most optimized version of homomorphic AES. Which suggests that a hash function could be practical to compute using a garbled circuit.


RSA key generation gives d=1 I was reviewing RSA by hand.
I picked 53 and 59 as my primes.
For e I picked 5.
When I solved for d using extended euclid, I got 1 which obviously doesn't decrypt anything.
I checked my answers online using calculators and got the same result.
Did I pick e or a prime wrong? How do I make sure I don't get 1 as d?

No, your values for $e$ and primes are fine (well, at least for a toy example); $e$ is relatively prime to both $p-1$ and $q-1$, and that's the only hard requirement (not counting the security related ones, of course).

I get $d=905$, as $5 \times 905 \equiv 1 \pmod{ \operatorname{lcm}((53-1),(59-1))}$; alternatively, you might get $d=2413$, if you do the computation $\bmod (53-1) \cdot (59-1)$.

I can only suspect that you're doing Extended Euclidean wrong; however without knowing exactly what you did, I really can't say exactly where you erred.


Does Microsoft use Dual_EC_DRBG by default? So, as we all know, Dual_EC_DRBG contains an NSA back door. At this point, there is no reason to call it a "potential" or even an "alleged" back door; the presence is obvious even to the NY Times.

As we also know, RSA BSAFE has been using Dual_EC_DRBG by default, with a justification so stupid it can only be translated as "because NSA paid us to".

This comment on Ars Technica asserts that Microsoft also uses this generator. But I have seen claims to the contrary. Thus my questions are:

What PRNG does Windows Server use to generate private keys for Certificate Signing Requests?

What PRNG does Internet Explorer on Windows use to generate session keys? How about Chrome and Firefox on Windows?

What PRNG does IIS on Windows use to generate ephemeral key material for PFS?

I am most interested in the latest versions of all of these products, and certainly only those released after 2007. References or at least an air of authority are preferred.

The September 2013 supplemental ITL bulletin released by NIST has drawn attention to NIST publication SP 800-90A, Random Number Generation using Deterministic Random Number Generation; specifically the trustworthiness of the Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG) algorithm.  As a result, NIST strongly discourages the use of Dual EC DRBG until concerns with it are addressed in a future revision of SP 800-90A.

The Windows CNG cryptographic infrastructure provides an implementation of DUAL_EC_DRBG applications may use. The Windows Crypto development team has reviewed supported version of Windows and determined that no features or components included in Windows specifically uses Dual EC DRBG.

Windows has a mechanism for configuring the default RNG algorithm to be used by various parts of the system. The default configurations for Windows 8.1, Windows Server 2012R2, Windows 8, Windows Server 2012, Windows 7 and Windows Server 2008R2 do not use Dual EC DRBG as the default random number generator algorithm.  The default random number generator algorithm for these versions of Windows is AES_CTR_DRBG from SP800-90a.

DRBGs rely on entropy to provide secure random number generation.  Good entropy typically depends on hardware and other factors to ensure its randomness.  Most applications rely on the platform to provide secure random numbers. I would expect that Chrome and Firefox would use the BCryptGenRandom to generate secure random numbers on Windows; however, each respective development team is more authoritative on how they generate random numbers when their browsers run on the Windows platform.

Mike Stephens
Windows Program Manager, Cryptography


Order of twisted curve in pairings We are doing optimal Ate pairings using a Barreto-Naehrig curve, and I am trying to make sure that an observation I made generalizes.

We define $E$ as $y^2 = x^3 + 3$ and use the tower of extensions
\begin{equation}\begin{split}
        \mathbb{F}_{p^2} &= \mathbb{F}_p[u] / (u^2 + 1) \\
        \mathbb{F}_{p^6} &= \mathbb{F}_{p^2}[v] / (v^3 - (u+3)) \\
        \mathbb{F}_{p^{12}} &= \mathbb{F}_{p^6}[w] / (w^2 - v)
\end{split}\end{equation}

and define the twisted curve $E'$ as $y^2 = x^3 + 3/(u+3)$.

Playing around in Sage, tweaking the BN parameters and playing with curves with different prime $p$ and order $r$, I found that the order of $E'$ was $r * (2p - r)$. But I haven't been able to find any confirmation that this is always true. Does anyone know if this is true in general, or if I just found a coincidence with my (very small) sample of curves?

Summary: no, this does not hold for all curves. It does hold for all Barreto-Naehrig curves, though; however, there are some subtleties.

First, some definitions. In order to define the question with all due precision, I must recall some known results.

Let $\mathbb{F}_q$ be a finite field of characteristic neither $2$ or $3$; that is, $q = p^f$ for some prime $p \geq 5$ and some integer $f \geq 1$. We consider curves $E$ over $\mathbb{F}_q$ with short Weierstraß equation $y^2 = x^3 + Ax + B$ for two constants $A$ and $B$ such that $4A^3 + 27B^2 \neq 0$ (if that last property is not fulfilled, there is a singular point with no tangent, hence which cannot be added to itself in a meaningful way, and the curve is not, stricto sensu, a curve).

Curve isomorphisms correspond to affine changes of variables; these are the transforms of the plane that map lines to lines, and therefore conserve point additions. It can be shown that the only possible changes of variables between two curves with short Weierstraß equations are $(x,y) \mapsto (e^2 x, e^3 y)$ for any $e \neq 0$ in $\mathbb{F}_q$. Such a change of variable transforms the curve equation into: $y^2 = x^3 + Ae^{-4}x + Be^{-6}$. We can thus to a large extent "normalize" either $A$ or $B$ to a small set of possible values.

The $j$-invariant of the curve is the field element:
$$ j = 1728 \frac{4A^3}{4A^3 + 27B^2} $$
Each element of $\mathbb{F}_q$ is a possible value for the $j$-invariant. When two curves have the same $j$-invariant, then either they are isomorphic to each other (in the sense explained above), or they are called twists of each other. When two curves are twists, then this means that they are isomorphic in a field extension; that is, there is a degree $k > 1$ such that, lifted into $\mathbb{F}_{q^k}$, the two curve equations become two isomorphic definitions of the same curve (and this then holds also in the algebraic closure of $\mathbb{F}_q$). The twist is called quadratic if $k = 2$, cubic if $k = 3$, and so on.

In the general case, when the $j$-invariant is distinct from $0$ and from $1728$, the curve admits a single twist (up to isomorphism) and it is quadratic. Namely, let $d$ be a non-quadratic-residue in $\mathbb{F}_q$ (i.e. an element with no square root); an equation of the twist is then: $y^2 = x^3 + Ad^2x + Bd^3$. It can be seen that if we "invent" a square root $e$ of $d$, then this yields the isomorphism which was described above. $e$ does not exist, by construction, in $\mathbb{F}_q$; therefore, adjoining $e$ to $\mathbb{F}_q$ yields $\mathbb{F}_{q^2}$, a degree-2 extension (in the usual definition of field extensions with polynomials, we are using the irreducible polynomial $X^2 - d$, and call $e$ one of its roots in the field extension).

It can be shown that if the curve $E(\mathbb{F}_q)$ has cardinal $q+1-t$ (with $t$ being the trace of Frobenius, bounded by Hasse's theorem: $t^2 \leq 4q$), then the twist has cardinal $q+1+t$, i.e. the trace is simply negated. The elementary proof consists in enumerating elements $x$ in $\mathbb{F}_q$:

If $x$ is such that $x^3 + Ax + B$ is the square of $y \neq 0$, then there are two points $(x,y)$ and $(x,-y)$ on $E$. But then, $(dx)^3 + Ad^2(dx) + Bd^3 = d^3 y^2$, and since $d$ is not a square in $\mathbb{F}_q$, this last value is not a square, and there is no point $(dx,y')$ on the twist $E'$.
Conversely, if $x^3 + Ax + B$ is not a square in $\mathbb{F}_q$, then there is no point $(x,y)$ on $E$, but there will be two points $(dx,y')$ on $E'$.
If $x^3 + Ax + B = 0$, then $(x,0)$ is a point on $E$, and $(dx,0)$ is a point on $E'$.

Thus, by enumerating the $q$ possible values of $x$, we obtain always two points: either two on $E$, or two on $E'$, or one of each of $E$ and $E'$. This covers all points of $E$ and $E'$ except the point-at-infinity, which does not have coordinates per se, and is part of both curves. Therefore, $\#E + \#E' = 2q + 2$, from which the result is obtained.

Note that, from the $j$-invariant, a matching curve equation is obtained as:
$$ y^2 = x^3 + \frac{3j}{1728 - j} x + \frac{2j}{1728 - j} $$

If the $j$-invariant is zero, then this corresponds to curves of equation $y^2 = x^3 + B$ (i.e. $A = 0$). There are only six curves with such an equation, up to isomorphisms (i.e. there are exactly six isomorphism classes); moreover, they are all twists of each other. Some of these will be quadratic twists, some will be cubic twists, and some will be sextic twists.

If $q = 2 \bmod 3$ (this may happen only if the characteristic $p$ is itself equal to $2$ modulo $3$, and $q = p^f$ for an odd integer $f$), then every element of $\mathbb{F}_q$ has a single cube root; therefore, for every $y \in \mathbb{F}_q$, there is a single $x$ such that $x^3 = y^2 - B$. It follows that the curve order is $q + 1$, and the curve is supersingular, and the embedding degree of the curve is $2$, and you don't want that for your pairings. Supersingular curves have a bunch of special properties, which I won't detail here.

I now suppose that $q = 1 \bmod 3$. Since $q$ is odd (it is a power of the characteristic, which we supposed was not equal to $2$, and is prime, and therefore odd), it follows that $q = 1 \bmod 6$. This implies that there are non-trivial sixth roots of unity, and that there are elements $\xi$ such that $X^6 - \xi$ is irreducible (there's a short proof of it given in the Barreto-Naehrig article, on page 6). We obtain all curve classes by enumerating the equations:
$$ y^2 = x^3 + \frac{B}{\xi^i} $$
for all $i$ from $0$ to $5$.

With $\xi^0$, we have the curve $E$ itself. With $\xi^3$, we get a quadratic twist of $E$. With $\xi^2$ and $\xi^4$, we obtain two cubic twists of $E$. With $\xi$ and $\xi^5$, we get two sextic twists of $E$.

Now for the group orders. When a curve has $j$-invariant zero, then its group order can only take six values (corresponding to the six isomorphism classes). Consider the integer $4q - t^2$: as indicated above, by Hasse's theorem, this integer is nonnegative. You can make it square-free by removing all prime factors with an even exponent; i.e. you can write:
$$ 4q - t^2 = Dv^2 $$
for integers $D$ and $v$, where $D$ is square-free (i.e. there is no prime integer $z$ such that $z^2$ divides $D$). By unicity of the factorization of integers, $D$ is uniquely defined. For curves of $j$-invariant zero, it so happens that $D = 3$, always; and this also works in the other way: if $D = 3$, then the curve MUST have $j$-invariant zero (this comes from complex multiplication theory, which is, indeed, rather complicated). From the value $v$, we can obtain the orders of the twists of curve $E$. We recall that $\#E(\mathbb{F}_q) = q + 1 - t$; then:

Quadratic twists of $E$ have order $q + 1 + t$.
Cubic twists of $E$ have order $q + 1 - (3v-t)/2$ or $q + 1 - (-3v-t)/2$.
Sextic twists of $E$ have order $q + 1 - (-3v+t)/2$ or $q + 1 - (3v+t)/2$.

For a demonstration and pointers, see The Eta Pairing Revisited, section 4.

The third case is when the $j$-invariant is equal to $1728$. This corresponds to curve equations $y^2 = x^3 + Ax$, i.e. $B = 0$. If $q = 3 \bmod 4$, then this defines a supersingular curve. If $q = 1 \bmod 4$, then you get four isomorphism classes, all twist of each other; such a curve accepts one quadratic twist and two quartic twists (extension degree 4). I won't detail that one, but see the Hess-Smart-Vercauteren article for details.

Another useful result is that, given a curve $E$ defined over field $\mathbb{F}_q$, with order $\#E(\mathbb{F}_q) = q + 1 - t$, the order of $E$ over field extensions can be computed as follows:
$$ \#E(\mathbb{F}_{q^n} = q^n + 1 - (\alpha^n + \overline{\alpha}^n) $$
for all integers $n \geq 1$, where $\alpha$ and $\overline{\alpha}$ are the two (complex) roots of polynomial $X^2 - tX + q$. There is a nice recurrence relation:

$\alpha^0 + \overline{\alpha}^0 = 2$
$\alpha^1 + \overline{\alpha}^1 = t$
$\alpha^{n+1} + \overline{\alpha}^{n+1} = t(\alpha^n + \overline{\alpha}^n) - q(\alpha^{n-1} + \overline{\alpha}^{n-1})$

In particular, $\alpha^2 + \overline{\alpha}^2 = t^2 - 2q$

All of this being stated, let's see your specific problem.

You have a prime $p = 1 \bmod 3$. A curve is defined over $E(\mathbb{F}_p)$, with equation $y^2 = x^3 + B$; this is a curve of $j$-invariant zero. Its order is denoted $r$. This curve has a trace $s$, which is such that $r = p + 1 - s$. In BN curves, $r$ is also prime, but this does not matter here.

You then lift the curve into $\mathbb{F}_{p^2}$. I write $q = p^2$: you are interested in twists of $E$ as defined over $\mathbb{F}_q$, not twists of $E$ as defined over $\mathbb{F}_p$. It is important to be precise about such things; this is the reason why I used $q$ and not $p$ in all the treatment above.

With the results above, you can compute:
$$ \#E(\mathbb{F}_q) = q + 1 - (s^2 - 2p) $$
i.e. the trace of the curve over $\mathbb{F}_q$ is $t = s^2 - 2p$.

Since this is a curve of $j$-invariant zero, it admits 5 twists, two of which being sextic, with orders:
\begin{eqnarray*}
    o_1 &=& q + 1 - \frac{3v + t}{2} \\
    o_2 &=& q + 1 - \frac{-3v + t}{2} \\
\end{eqnarray*}
where $v$ is such that $4q - t^2 = 3v^2$.

The question is then: is it guaranteed that one of these two sextic twists has order exactly $r(2p-r) = (p+1-s)(p-1+s)$?

The answer is: no. Here is a counterexample:

Let $p = 31$. The curve $y^2 = x^3 + 3$ has order $r = 43$, i.e. its trace is $s = -11$. The quadratic extension is $q = 961$; over $\mathbb{F}_q$, the curve $E$ has trace $t = s^2 - 2p = 59$. We note that $4q - t^2 = 363 = 3(11^2)$, thus $v = 11$. The orders of the two sextic twists are then $o_1 = 916$ and $o_2 = 949$. However, $(p+1-s)(p-1+s) = 817$, which is distinct from both $o_1$ and $o_2$.

However, for BN curves, this works. Recall that a BN curve is parameterized by an integer $u$, and:

$p = 36u^4 + 36u^3 + 24u^2 + 6u + 1$
$s = 6u^2 + 1$

The integer $u$ is chosen so that $p$ is prime, and the curve order $r = p+1-s$ is also prime. Under such conditions, one can notice that:
$$ 4p - s^2 = 3(6u^2 + 4u + 1)^2 $$
Hence $s$ is the trace for some curve over $\mathbb{F}_p$ with $j$-invariant zero. We can then lift that curve into $\mathbb{F}_q$ with $q = p^2$, and that one will have two sextic twists.

This choice of $p$ and $s$ implies that $r$ divides $p^{12}-1$, which means that the embedding degree (the crucial property for defining pairings) will be at most $12$, hence the curve will be "pairing-friendly".

With these parameters, you get:

$q = p^2$
$t = -36u^4 - 72u^3 - 36u^2 - 12u - 1$
$4q - t^2 = 3v^2$ with $v = (6u^2+4u+1)(6u^2+1)$

And thus, the two sextic twist orders are:
\begin{eqnarray*}
    o_1 &=& 1296u^8 + 2592u^7 + 3024u^6 + 2160u^5 + 1044u^4 + 360u^3 + 84u^2 + 12u + 1 \\
    o_2 &=& 1296u^8 + 2592u^7 + 3024u^6 + 2160u^5 + 1152u^4 + 432u^3 + 120u^2 + 24u + 4 \\
\end{eqnarray*}

If you compute the expression for $(p+1-s)(p-1+s)$, you will find that you get exactly the same polynomial as $o_1$. Therefore, for any BN curve, it is guaranteed that one of the sextic twists $E'$ of $E$ (over $\mathbb{F}_q$) will have order $(p+1-s)(p-1+s) = r(2p-r)$.

Note: there still are two sextic twists. When you choose your $\xi$ such that $X^6-\xi$ is irreducible over $\mathbb{F}_q$, you might be unlucky and obtain the wrong one. The other twist can be obtained by using $\xi^5$ instead (or you could try again with another $\xi$, since you want one that makes computations easiest to do).


How to determine if a protocol is a Zero knowledge proof If the given protocol is non interactive then how can one prove that the modified protocol is complete and determine whether it is zero-knowledge?
Let $N = p q$ as in an RSA algorithm, with $\text{gcd}(e, \phi(N)) = 1, e$ prime. $P$ wants to prove knowledge of $x \in \mathbb{Z}_N$, where $y = x^e$ is public. $P$ chooses $r \in \mathbb{Z}_N$, and calculates $a = r^e \bmod N$, and sends them to the verifier $V$. $V$ sends $0 \leq c \leq e - 1$ to $P$, and $P$ calculates and sends back $f = rx^c \bmod N$. $V$ accepts this proof if $f^e = ay^c = r^ex^{ec} = (rx^c)^e$.

Let's analyze the correctness, zero-knowledge and soundness properties of this protocol proving the pre-image of a group-homomorphism $(\psi(w):w\rightarrow w^e\bmod{N})$ over a group of unknown order ($\mathbb{Z}^{*}_{N}$)!

Correctness

The correctness of the above protocol is straightforward to see. If the claimed relation, $y=x^e\bmod{N}$, holds then the verifier always accepts the proof. This is because $f^e=(rx^c)^e=r^ex^{ce}=ay^c$. The first equality follows from the definition of $f$ and the last equality follows from the definition of $a$ and $y$.

Zero-knowledge

It is also quite easy to build a simulator for this protocol. The verifier can simulate the protocol transcript on its own, without interacting with a prover as follows. It chooses a random $f'\in_R\mathbb{Z}^{*}_{N}$ and $c'\in_R[0,e-1]$, then $a'=f'^{e}y'^{-c}$. Put differently, the simulated transcript $(a',c',f')$ is computationally indistinguishable from a "real" transcript $(a,c,f)$, i.e., $(a,c,f)\approx_c(a',c',f')$. They are just random integers in $\mathbb{Z}^{*}_{N}$ that also satisfy the verification equation, $f^e=ay^c$.

Soundness

Even though this was not part of the question, but still this is the most interesting part of the analysis of any sigma protocol over groups of unknown order. The knowledge error (the probability that a malicious prover can convince the verifier that $y=x^e\bmod{N}$ without actually knowing $x$) of this sigma protocol is at least $1/d$, where $d$ is the smallest divisor of $e$. Practically speaking, this means that any application relying on this protocol needs to run this protocol multiple times in order to achieve reasonable levels of soundness of the zero-knowledge protocol. For more details on this inherent efficiency, see this work by Bangerter et al.


Not understanding deterministic authenticated encryption (DAE) security definition I have a question regarding the security definition of deterministic authenticated encryption (DAE) as defined by Bellare and Shrimpton. Their definition is reproduced below, and my question pertains to the emphasized part.

Definition 1 Let $\Pi = (\mathcal K, \mathcal E, \mathcal D)$ be a DAE scheme with header space $\mathcal H$, message space $\mathcal X$, and expansion function $e$. The DAE-advantage of adversary $A$ breaking $\Pi$ is defined as
$$\mathbf{Adv}_{\Pi}^{\mathrm{dae}}(A) = \Pr[K \gets \mathcal{K} : A^{\mathcal{E}_K(\cdot, \cdot), \mathcal{D}_K(\cdot, \cdot)} \Rightarrow 1] - \Pr[A^{\\\$(\cdot, \cdot), \bot(\cdot, \cdot)} \Rightarrow 1] $$
On query $H \in \mathcal H,X \in \mathcal X$, the adversary’s random-bits oracle $\\\$(\cdot,\cdot)$ returns a random string of length $|X|+e(H, X)$. As always, oracle queries outside the specified domain return $\bot$. The $⊥(\cdot,\cdot)$ oracle returns $\bot$  on every input.  We assume that the adversary does not ask $(H, Y)$ of its right (ie, second) oracle if some previous left (ie, first) oracle query $(H, X)$ returned $Y$; does not ask $(H, X)$ of its left oracle if some previous right-oracle query $(H, Y)$ returned $X$; does not ask left queries outside of $\mathcal H \times \mathcal X$; and does not repeat a query.  The last two assumptions are without loss of generality, as an adversary that violated any of these constraints could be replaced by a more efficient and equally effective adversary (in the $\mathbf{Adv}_{\Pi}^{\mathrm{dae}}$-sense) that did not.  The first two assumptions are to prevent trivial wins

Basically, I don't see how the last assumption (i.e., no repeated query) is without loss of generalization? More specifically, isn't this assumption needed for any deterministic scheme to be considered secure according to this definition?
Here is how you could break any deterministic scheme according to Def. 1, if queries could be repeated. First, repeat the same query $(H,X)$ to the left oracle (either $\mathcal{E}_K(\cdot, \cdot)$ or $\\\$(\cdot, \cdot)$) and get back $Y_1$ and $Y_2$. If $Y_1 = Y_2$ return 1. It's trivial to see that this attack has DAE-advantage $1-2^{-|X|-e(H,X)}$.
As justification for their WLOG claim, I imagine they had the following reduction in mind. Let $A$ be a DAE-adversary that repeats queries, and let $B$ the following DAE-adversary that doesn't. It runs $A$ and forwards all of $A$'s queries to its own oracles, except whenever $A$ repeats a query, where $B$ instead returns the same response back for that query (which $B$ cached). $B$ outputs the same as $A$. However, this reduction doesn't work! (In particular, it doesn't properly simulate the DAE game).

As I wrote in a comment, the reason your proposed attack does not work is that the random oracle also returns the same result when queried with the same input.
The ideal functionality should clearly still be a (random) function, but I agree that the definition in your reference is not as clear as it could be. It would be more precise to say "uniform random function" rather than "random-bits oracle". For example, see Definition 1 in this paper.


How do I pick variable length passwords uniformly at random? How do I pick passwords uniformly at random when given a min and max length?

It seems that if I first pick a random length, then choose random characters, this procedure will choose shorter length strings preferentially when you consider the number of different strings of a fixed length that are possible.

In practice, it is sufficient to pick a random password with the maximum allowed length.

Assuming that your alphabet has $n$ different usable characters, the total number of passwords of length up to $k$ is $$t(k) = n + n^2 + n^3 + \dotsb + n^k = \sum_{j=1}^k n^j = \frac{n^{k+1}-1}{n-1},$$ and thus the fraction of all passwords that have length less than $k$ is $$\frac{t(k-1)}{t(k)} = \frac{n^k-1}{n^{k+1}-1} \approx \frac 1n.$$

For example, assuming that your passwords are composed of printable ASCII characters ($n = 95$), all the passwords shorter than the maximum length make up only about $1/95 \approx 1.05\%$ of the total password space.

(In any case, if these "passwords" are meant to be memorized by a human, it's generally much more effective to use a passphrase selected by picking random common words from a suitable dictionary.  See diceware for a popular example implementation.  Depending on the size of the dictionary used, each such word can encode about 10 to 13 bits of randomness, whereas two random printable ASCII characters encode a little over 13 bits, but a single meaningful word is much easier for a human to remember than a pair of random characters.  Of course, such passphrases do end up being a couple of times longer than a random character sequence of equivalent entropy, but this is only a serious problem if you're running against some kind of a hard maximum length limit, in which case the existence of such a limit is the real problem.)


In Diffie-Hellman, are $g$ and $p$ universal constants or are they chosen by one party according to a set of rules? I can't find any clarity on this. In textbooks, what I'm reading suggests there's already a standardized $g$ and $p$ that everyone uses, but I can't find what they are.

The closest I've come to is this RFC link.

$g$ and $p$ can be viewed as universal constants. These values are public values so the security isn't affected if an attacker knows $p$ and $g$. They also have to be the same values on both sides for a key-exchange to work.

As explained in Wikipedia (section Security):

  [$\ldots$] For this reason, a Sophie Germain prime $q$ is sometimes used to calculate $p = 2q + 1$, called a safe prime, since the order of $G$ is then only divisible by $2$ and $q$. $g$ is then sometimes chosen to generate the order $q$ subgroup of $G$, rather than $G$, so that the Legendre symbol of $g^a$ never reveals the low order bit of $a$. A protocol using such a choice is for example IKEv2.

So these are infact default values, for example the Java documentation (might be outdated for 2019) lists the following values for 512-bit keys:

p = fca682ce 8e12caba 26efccf7 110e526d b078b05e decbcd1e b4a208f3
    ae1617ae 01f35b91 a47e6df6 3413c5e1 2ed0899b cd132acd 50d99151
    bdc43ee7 37592e17
g = 678471b2 7a9cf44e e91a49c5 147db1a9 aaf244f0 5a434d64 86931d2d
    14271b9e 35030b71 fd73da17 9069b32e 2935630e 1c206235 4d0da20a
    6c416e50 be794ca4

Normally such default values are used, but it is also possible to choose new $p$ and $g$ values if you want to.


Why does 3DES need private key to decrypt? I create two files, my.cer and my.pem ( include certificate and private key), I encrypt a file with my.cer, I use openssl smime -encrypt command. When decrypting data, it needs my.pem.

I think 3DES is symmetric cryptography so it should just need my.cer. Please explain.

Yes, 3DES is a symmetric cipher and you use a secret key for both encryption and decryption with it. However, that is not the same thing as the keys used in RSA or other public key cryptography – you cannot (and should not) use either of them for 3DES.

Since you are using S/MIME, you are actually using public key encryption. Any reference to 3DES is about the symmetric part of a hybric cryptosystem. That is, you use the public key encrypt/generate a secret key that encrypts the actual message. So you need the private key to decrypt it.


Why does image size increase after steganography? I am working on a steganography technique. Sometimes I need to send my steganographed images online to my friends but in the process the image gets compressed destroying all the data. I found ways to surpass it by using Google Drive or simply mailing them to the destination. But still I am not able to find a reason as why the size of the image increases (nearly to 30%) after the steganography.

Technique used is

Read a character from a file.
Convert that character to a string of binary bits (from its ASCII)
To make it a 6bit binary string, pad it with appropriate 0s
Read two consecutive pixels from an image (left to right)
Impose the first three bits of the binary string onto the LSBit of
RGB of first pixel (first bit on LSBit of R, second bit on G and third bit on B).
Repeat 5 for the next pixel
Repeat from 1

I'll assume the question really is: when I perform low-order-bit steganography on an uncompressed image (inserting 6 bits encoding a character into the low-order bit of 6 bytes coding the R, G and B channels of 2 pixels), I find that compressing the resulting image gives a bigger file than compressing the original image for a given setting of the program used to compress.

The reason likely is that the process which made the original image is such that the low-order bits are very correlated with the other bits (for example this could be because of characteristics of a sensor; or because the original image has been compressed by some lossy algorithm, then decompressed); and that correlation is lost by replacing the low-order bits.

The observed effect will depend on the nature of the compression technique used, and will tend to be be most perceivable for lossless compression techniques (GIF, PNG, lossless JPEG), which are the only ones which allow correct decoding of the hidden message.

If the low-order bits of the original image where random, the observed effect would likely vanish, or even perhaps be inverted (assuming the enciphered message has redundancy).


How does converting character set affect hash entropy? Does mapping a large character-set hash onto a small character-set hash lower entropy for a fixed size substring?

I'm writing a python app that involves generating passwords for websites. During the application I want to convert hexidecimal hashes to alphanumeric strings, and take the first twenty characters of the output. I want to convert to alphanumeric, because most websites at least support the upper-lower alphanumeric character set.

I surjectively map the larger character set of hexadecimal bytes $\{00...\text{ff}\}$ onto the smaller set of upper and lowercase alphanumerics $\{a...z, A...Z, 0...9\}$.

The mapping is done by recycling the 62 alphanumeric elements cyclically to correspond to each element of the 256 bytes

$$00 \rightarrow a$$
$$01 \rightarrow b$$
$$\vdots$$
$$0e \rightarrow 9$$
$$0f \rightarrow a$$
$$\vdots$$

For example, if the world's most secure password - "password" - is sha512 digested as hexadecimal it is unsurprisingly - $128 \times log_2(16) = 512$ bits.

$$
\text{b109f3bbbc244eb82441917ed06d618}\\
\text{b9008dd09b3befd1b5e07394c706a8b}\\
\text{b980b1d7785e5976ec049b46df5f1326}\\
\text{af5a2ea6d103fd07c95385ffab0cacbc}\\
86\\
$$

Since each pair of hex-digits is mapped onto one alphanumeric digit, I assume the entropy of the resultant alphanumeric string is $64 \times log_2(62) = 382.5459$ bits.

$$\text{1j5bcKq8KdvcwVJpuiJj3efBGh5oYSp}\\\text{9
e1D6GB4YeFiLHtMZCUQxdfhpvjhVmWck}\\$$

The new string has half the length but ~75% of the entropy of the original string, so there is more per-character entropy in the alphanumeric projection,
making

$$\text{1j5bcKq8Kd}$$

a better password than

$$\text{b109f3bbbc}$$

Have I made any invalid assumptions, or done the math incorrectly? Any insights into whether or not this surjective mapping is a good idea would be appreciated.
If any clarification or edits are needed I'd be happy to make them - please leave a comment below.

In general, if a function $f$ has collisions, then it may reduce entropy: $$H[f(X)] \leq H[X].$$  The inequality applies to any notion of entropy—min-entropy, Shannon entropy, Hartley entropy, Rényi entropy, etc.  This happens because if $f(x_i) = f(x_j)$ for $x_i \ne x_j$, the probability masses $\Pr[X = x_i]$ and $\Pr[X = x_j]$ both contribute toward the probability mass $\Pr[f(X) = y]$ where $y$ is the common value of $f(x_i)$ and $f(x_j)$.  In particular, the min-entropy is $$-\log_2 \max_y \sum_{x \in f^{-1}(y)} \Pr[X = x].$$  Here the outputs with the most colliding inputs are $\{\mathtt a, \mathtt b, \mathtt c, \mathtt d, \mathtt e, \mathtt f, \mathtt g, \mathtt h\}$, each having five distinct inputs ($f^{-1}(\mathtt a) = \{0,62,124,186,248\}$, etc.), so in the best case, if $X \in \{0,1,2,\dots,255\}$ has uniform distribution, the min-entropy of $f(X)$ is $-\log_2 5/256 \approx 5.678$.  For a string of independent inputs $X_1 \mathbin\| X_2 \mathbin\| \cdots \mathbin\| X_n$, the concatenation $f(X_1) \mathbin\| f(X_2) \mathbin\| \cdots \mathbin\| f(X_n)$ has min-entropy about $5.678n$.  Thus a 64-character string from this will have at most about 363 bits of min-entropy.

Note that this is a bit less than a uniform random string from the same alphabet, which has $\log_2 62$ bits of entropy per character, or about $5.954n$ bits of entropy in a string of $n$ independent characters, which for a 64-character string gives about 384 bits of min-entropy as you calculated.

There are other ways to do roughly what you're doing:

Use base64.  This is an injective map from octet strings to strings of $\{\mathtt a, \mathtt b, \mathtt c, \dots, \mathtt z, \mathtt A, \mathtt B, \mathtt C, \dots, \mathtt Z, \mathtt0, \mathtt1, \mathtt2, \dots, \mathtt9, \mathtt+, \mathtt/\}$ with optional padding.  Of course, you can change the exact character set if need be to comply with mandatory and forbidden special characters.
Use rejection sampling.  From the infinite stream $\operatorname{SHA512}(k \mathbin\| 0) \mathbin\| \operatorname{SHA512}(k \mathbin\| 1) \mathbin\| \operatorname{SHA512}(k \mathbin\| 2) \mathbin\| \dots$, take the acceptable octets (which encode, say, graphic US-ASCII characters) and reject the unacceptable ones until you have a password as long as you want.


Formal description of KDF1 and KDF2 I've seen many descriptions of KDF1 and KDF2 by now, but most documents simply point to specifications that are behind a pay wall. These standards are not specific to the KDF's; they just use these KDF's as sub-part of an algorithm description (key agreement). Does somebody have a formal description of both KDF's that adheres to the standards?

The description should include additional information to derive a key such as OtherInfo field or label, or indicate their absence. Needless to say the other input parameters and the use of the internal counter would be needed for the full algorithm as well.

The standards can be found in IEEE Std 1363-2000, ANSI X9.42 (KDF1) and ISO 18033-2 (KDF2). That last standard defines OID's for them, KDF1 is 1.0.18033.2.5.1 and KDF2 is 1.0.18033.2.5.2 (unprotected links to oid-info.com).

FCD 18033-2
Encryption algorithms — Part 2:
Asymmetric ciphers - the final committee draft (FCD) of ISO/IEC 18033 - by Victor Shoup is publicly available from his website and specifies (in section 6.2) that KDF1 is

For an octet string $x$ and a non-negative integer $l$, $\operatorname{KDF1(x,l)}$ is defined to be the first $l$ octets of
$$\operatorname{Hash.eval}(x || \operatorname{I2OSP}(0, 4)) || ··· || \operatorname{Hash.eval}(x || \operatorname{I2OSP}(k − 1, 4)),$$
where $$k = \lceil l/\text{Hash.len} \rceil $$

The binary counter representation should translate to 4 bytes in big endian.
KDF2 is identical but starts counting from 1 instead of 0.


Generation of N bit prime numbers -> what is the actual range? Short version: When generating a prime number of N bits, should I draw random numbers from the range $[0 , 2^n]$, or $[2^{(n-1)} , 2^n]$?

Context: I'm trying to implement a toy-version of RSA as a hobby, with a Miller-Rabin test to generate primes. Initially, my function to generate the keys had the following signature:

$$generateKeys :: (Range, Seed) \rightarrow (PublicKey, PrivateKey)$$

where Range is the range of numbers in which to generate random numbers to search for primes, which initially I had set to $[2^{16}, 2^n]$ to avoid the $[0-2^{16}]$ range, given that RSA implementation guides recommend avoiding using small primes.

But I started wondering if instead I should specify the number of bits of the

$$generateKeys :: (BitsToUse, Seed)\rightarrow (PublicKey, PrivateKey)$$

And this in turn got me wondering exactly what does a "N bit prime" mean, ie, exactly which range from which to pick the prime is generally desired, specially since the range $[2^{(n-1)}, 2^n]$ is "only" half the size of $[0 , 2^n]$, although I guess primes are a bit less dense in that range.

In the context of RSA, when we say an "N bit prime", we mean that it's a prime in the range $[2^{n-1}, 2^n)$.

In addition, when we say an RSA key is an "N bit key", we mean that it's in the range $[2^{n-1}, 2^n)$.  What this means that if you pick two random $N/2$ bit primes, and multiply them together, you'll get an $N-1$ bit modulus about half the time.  To avoid this, one common practice is to select the primes from the range $(\sqrt{2}\cdot 2^{n/2-1}, 2^{n/2})$ - that way, when we multiply the two primes together, we'll always get an N-bit key.

If you're worried that restricting the primes to this range will make guessing them easier, well, that's actually not a concern.  If we're generating a 1024 bit key (which by today's standards is cutting it close), there are approximately $10^{151}$ primes in the range $(\sqrt{2}\cdot 2^{511}, 2^{512})$-- it's unlikely anyone will happen to guess either one.


Advantages using Diffie-Hellman or ElGamal For what kind of usage should we prefer using Diffie-Hellman in order to exchange keys instead of ElGamal, and most important why should we use one or the other?

I do not see a clear difference between these two algorithms. What are their respective advantages?

Diffie Hellman

Diffie Hellman is a key exchange protocol. It is an interactive protocol with the aim that two parties can compute a common secret which can then be used to derive a secret key typically used for some symmetric encryption scheme.

I take the notation from the link above and this means we have a group $\mathbb{Z}_p^*$ for prime $p$ generated by $g$. Party $A$ chooses random $a\in \mathbb{Z}_p^*$ and sends $g^a$ to $B$ and $B$ chooses random $b\in \mathbb{Z}_p^*$ and sends $g^b$ to $A$ and both compute $g^{ab}$ as their common DH key.

Plain (unauthenticated) Diffie Hellman is known to be susceptible to person-in-the-middle attacks and this can be circumvented (as for instance done in TLS) by authenticating Diffie Hellman
either

by including the static Diffie Hellman paramters $(p,g,g^b)$ of one party (the server in TLS) into a certificate which is signed by a trusted authority (where the static parameters stay the same for all key exchanges) or
by requiring the server to sign the ephemeral Diffie-Hellman key, i.e., $g^b$ where $b$ is chosen randomly for every new interaction, sent to the other party (the client). Thereby, the public verification key corresponding to the signing key is put into a certificate which is signed by a trusted authority.

Using a static DH key is in principle very similar to how ElGamal works, but ElGamal encryption is non-interactive.

 ElGamal Encryption

ElGamal encryption in contrast to DH is a public key encryption scheme and may be seen as a non-interactive DH key exchange where the public key of $B$ is $g^b$ and the computed DH key $g^{ab}$ is used as a one-time-pad to encrypt a message $m\in \mathbb{Z}_p^*$ which is a group element of the respective group used, typically the encryption operation is defined as multiplying the message with the DH key, or xoring the message with a hash of the DH key.

The ciphertext is then a tuple $(c_1,c_2)$ consisiting of the message encrypted with the DH key $m\cdot g^{ab}$ and the part $g^a$ of the DH key computed by the encrypting party. But the entire process is conducted by one party, i.e., the party encrypting the message. This party then sends the tuple $(c_1,c_2)=(g^a,m\cdot g^{ab})$ to the receiver $B$.

In a practical setting, ElGamal encryption does not really give a benefit when using it as an encryption scheme as it is, since it does only support message of size of elements of the group being used and parameters must be chosen carefully in order to obtain IND-CPA security (holds always in elliptic curves but you have to choose a suitable subgroup of $\mathbb{Z}_p^*$ to obtain it). However,
 it can be turned into a hybrid encryption scheme. But when one wants to use such a hybrid encryption scheme IES/ECIES is a better choice. ElGamal encryption, when the paramters are chosen in the right way achieves the weaker notion of indistinguishability under chosen plaintext attacks (IND-CPA), where IES/ECIES achieves stronger security, namely indistinguishability under chosen ciphertext attacks (IND-CCA).

ElGamal still has some benefits, which however, are more interesting when using ElGamal encryption as a building block for "larger" cryptographic protocols. For instance:

It is a homomorphic encryption scheme which allows multiplying plaintext hidden inside of ciphertexts and when
using the homomorphic property with an encryption of the identity element $1$ of the group allows to publicly re-randomize ElGamal ciphertexts, i.e., obtain new ciphertexts for the same message which
are unlinkable to the original ciphertexts. Using exponential ElGamal obtained from ElGamal by encoding the message $m$ as $g^m$, i.e., as exponent of the generator $g$, ElGamal can also be made additively homomorphic for polynomial sized message spaces (since decrypting involves computing discrete logarithms).
There are efficient honest-verifier zero-knowledge proofs of knowledge to prove properties of ElGamal ciphertexts without revealing the plaintext, e.g., equality of plaintexts.
ElGamal can be used to construct a threshold cryptosystem, i.e., there are $n$ parties holding shares of the secret decryption key and a ciphertext can only be decrypted if at least $k$ of these $n$ parties are involved in the decryption process but fewer then $t$ parties will fail in decrypting.

DH or ElGamal

  For what kind of usage should we prefer using Diffie Hellman in order to exchange keys instead of Elgmal, and most important why should we use one or the other ?

That heavily depends on your application scenario. For instance, are sender and receiver on line or not? Do you want to simply encrypt data for confidential storage or communicate with some other guy? One feature that can be achieved for confidential communication  when exchanging keys using a key exchange protocol such as DH is forward secrecy, which you will not have when using asymmetric encryption and sending encrypted messages under a fixed ElGamal/IES/ECIES public key to a receiver.


Do certificates need to be stored as encrypted? The titles says most of what we're confused with. Here's some details:
On an embedded device, we have a microcontroller and external flash memory.  This memory can be easily read and written to in place.  On that memory we store SSL certificates and a private key.
The microcontrollers internal flash memory is secure and can be used to hold fixed encryption keys, even uniquely generated so are only ever known inside the microcontroller.  I cannot store certificates on the internal flash memory.
It seems obvious that the private key should be stored as encrypted but I am not so clear about the certificates.
What is not so obvious is if the certificates used to verify a TLS connection should be stored as encrypted to.  It is likely that the root level certificates will be self signed and have no chain back to a verified root CA.
Thoughts?

What is not so obvious is if the certificates used to verify a TLS connection should be stored as encrypted to. It is likely that the root level certificates will be self signed and have no chain back to a verified root CA.

As DannyNiu stated, there is no issue if someone were able to read the certificates; those are public information, and allowing an adversary to read them is not an issue.
However, there is a potential concern - what if an adversary can overwrite them?  After all, an adversary who can do that could insert his own root certificate, and then establish a TLS connection (based on the root certificate he picked).  This may or may not be a concern for you (can the adversary modify the flash, and then perform a negotiation?); if it is, one approach to prevent this would be to integrity check the certificate.  That is, you would pick a random key, and put that into the internal flash memory; you would use that key to compute a MAC of your certificate; that generates a moderate sized (perhaps 32 byte) string, and write that string alongside the certificate in your external flash.  Then, when it comes time to use the certificate, you would again compute the MAC of that on-flash certificate using the key, and check to see if the 32 byte string you computed was the same as the string that's stored in memory.
An attacker who tries to replace the certificate with his own is unable to compute the 32 byte string (because that depends on the key you have in secure storage); hence any attempt at modification will be detected.


Is this a proper key-exchange implementation? I've been trying to implement Diffie Hellman key exchange so far from my own understandings (I know I could just stick with SSL/TLS, but I want to understand it in depth more), so I created this basic server<->client key exchange:

Generator and modulus are constants, thus same all the time
Generator is 3
Modulus is a 2048bit prime number

Step 1:
  1. Client connects to a server, asks for key exchange
  2. Server generates random 2048bit exponent
  3. Server rises generator to this exponent
  4. Server does modulo on result with 2048bit modulus
  5. Server sends result of modulo operation unencrypted to client

Step 2:
  1. Client receives result from server unencrypted in form of hex number
  2. Client generates random 2048bit exponent
  3. Client rises generator to this exponent
  5. Client sends this number to server unencrypted back
  6. Client rises server's number to client's exponent and does modulo op.
  7. Client remembers result as secret key (2048bit)
  8. Server receives this number, and rises it to it's own exponent and does modulo op.
  9. Server remembers result as secret key (2048bit)

Step3:
  1. Both client and server do SHA256 on secret key and get 256bit integer
  2. This 256bit key is used as private key for further AES/CBC/PKCS5 communication

So my questions are:

Can exponent be random number just like it is now or it should be a prime too?
Is using dynamic modulus and generator better idea?
Is there anything to improve this key exchange or are there any flaws?
Is using SHA256 a proper way to generate 256bit key for AES/CBC?

Edit: purpose of this key exchange is for JSON messaging between server and client and end-to-end encryption in VoIP between clients (it's all for self-educational purpose, I know I could stick with WebRTC/DTLS or any already existing protocol!)

Can exponent be random number just like it is now or it should be a prime too?

There is no particular advantage to be gained in selecting only prime exponents.

  Is using dynamic modulus and generator better idea?

Whether it makes sense to use dynamic modulii is currently under debate.  There are known algorithms that make attacking multiple discrete log problems under the same modulus not that much more expensive than attacking one; hence some people claim that you should vary the modulus (not to give TLAs a single target to attack).  Other people state that if you use a sufficiently large modulus (and 2048 bits would appear to be sufficiently large), this isn't a concern (and in addition, generating random modulii adds complexity, and that in itself is a security concern).

As for generators, we know the answer is "no, it doesn't help". It's provable that one particular base is not (much) weaker than a random based (of the same order); that is, if you can solve either the DLog or the computational Diffie-Hellman problem with one base, you can leverage that to solve the corresponding problem in any base (of the same order).  It's far more important to select a generator that you know has a large prime order (with possibly a small cofactor).

  Is there anything to improve this key exchange or are there any flaws?

Of course there are flaws.

You state that the modulus is "prime"; that's not sufficient for Diffie-Hellman; instead, you need to know the that it contains a subgroup that's a large prime factor (that is, $p-1$ has a large prime factor $q$).

You use the generator "3".  Small generators can be strong (in fact, "2" is a popular choice), however you should make sure that "3" has a large prime order (that is, it generates a subgroup whose size is a large prime).  One obvious way is to select a prime $p=2q + 1$ for prime $q$; and with $p \equiv 11 \pmod{12}$; if both requirements are true, then "3" will generate a group of size $q$.

You use a 2048 bit exponent; that's considerably more expensive than you need; you do the above checks (make sure that the subgroup that $g$ generates is large and prime), then a 256 bit exponent is quite sufficient (and 8 times faster).

You don't do any authentication; this means that someone in the middle that can modify messages can insert themselves into the conversation, and listen in.

You have the server perform the first modular exponentiation, and before any client verification; this opens up an obvious Denial-of-Service attack.

  Is using SHA256 a proper way to generate 256bit key for AES/CBC?

And how are you generating the key for the MAC (you are using a MAC with AES/CBC, aren't you???)


Do I really need to use the same private/public key pair in RSA? So I'm making an Android application, I need my application to be only able to scan my own generated QR codes, and I want to make sure that nobody else can generate fake ones.
The data isn't sensitive, it's very okay to be read by anyone, and even be in plaintext.
The problem comes is that, I need to verify the source of the QR code, I've been suggested to digitally sign it, thus, I have my private key, and I ship my application with a public key, and the application then uses the public key to check the QR code
Some of the things I don't get:

Am I encrypting the whole message using the private key? or I just generate some separate signature that sits next to me message?
As far as I know, with RSA, for example, everytime I encrypt a message, a new private and public key are generated, right? So how is the application going to verify/decrypt the message if the public key is constantly changing per QR code?

Simply said:
My QR code data are something like:
{"a": 1, "b": 2, "c": 3}

And I want my application to make sure that this data comes from an authorized source, and not generated by anyone else.

I've been suggested to digitally sign it, thus, I have my private key, and I ship my application with a public key, and the application then uses the public key to check the QR code

As long as you can live with the requirements for RSA (signature size, computation), that sounds like an excellent idea.

  Am I encrypting the whole message using the private key? or I just generate some separate signature that sits next to my message?

You're generating some separate signature that sits next to your message.  That is, the RSA signature algorithm (which you run) takes the message (and the private key), and spits out a 'signature'.  Then, the RSA verify algorithm (which runs on the phone) takes the message, the signature, and the RSA public key, and then outputs either "signature valid", or "invalid".

You would put into the QR code your message and the signature.

  As far as I know, with RSA, for example, everytime I encrypt a message, a new private and public key are generated, right?

Nope.  There are things known as 'one-time-signatures" where a public/private key can be used only once, but RSA isn't one of them.  Instead, a single RSA private key can sign as many messages as you want.


Is a zk-SNARK the hash of a Linear Interactive Proof? zk-SNARK researcher Eran Tromer came up with the following workflow when describing how these proofs are created:

What I am struggling to understand is how a LIP becomes a zk-SNARK. Is the SNARK a hash of the LIP?

I would appreciate any help, or recommendations for reading materials.

The above figure illustrates the steps that one needs to take to design a zk-SNARK for an arithmetic circuit (computation). As you know, SNARK stands for Zero-Knowledge Succinct Non-interactive ARgument of Knowledge.

So to design a zk-SNARKs form LIP, first one needs to convert a LIP to a Linear Non-Interactive Proof (LNIP) system that can be done in two models including Random Oracle (RO) model and Common Reference String (CRS) model. In the RO model, one uses a hash function to remove the challenge phase (by taking hash of first message in a LIP) in a LIP, and in the CRS model there is a pre-processing (setup) phase which a third trusted party generates some common public parameters that prover and verifier use them to generate and verify a proof.

Once you converted a LIP to a LNIP, you can construct a (succinct) non-interactive argument of knowledge. A nice example can be found in https://eprint.iacr.org/2016/260 which contains the state-of-the-art QAP-based zk-SNARK.

I would recommend to look at Pinocchio zk-SNARK as well.


Is a MAC a valid way to ensure tamper-resistance? According to some government standards I need to be able to ensure some data in a database has not been tampered with.

My current idea is to store a MAC (HMAC-SHA256) next to each instance of the serialized data. The key will be stored in a separate location but the same key will be used for every MAC.

To detect tampering, I will read the data, compute the MAC again with the same key, and compare the computed MAC with the one stored in the DB. If they are equal, the data has not been tampered with, if they are different, than the data has been tampered with.

A weakness I am aware of is that if the key were to be compromised, we no longer can trust the MACs or the data. It would be possible to recompute the MACs, but they would only be valid for the data in the DB which we can no longer trust.

A few questions:

Is this a valid use case for a MAC?
Are there any major or minor flaws with this technique?
Is it OK to reuse the same HMAC key forever?
Would an asymmetric or AEAD solution be preferable?

First, you have to check if the HMAC integrity check complies to the governmental standard. In the USA, for instance, you have to check the FIPS specifications.
If that has been clarified then here are my answers:

  is this a valid use case for a MAC?

Yes.

  Are there any major or minor flaws with this technique?

The one you already stated.

  Is it OK to reuse the same HMAC key forever?

That is seldom a good idea, due to the "break once run everywhere" scenario.
I would instead use a Key derived from a Masterkey. The Key is on the database and the Masterkey on an seperate isolated device. From time to time you should change the Key by a new derivation form the Masterkey and some well known data.

  Would an asymmetric or AEAD solution be preferable?

An asymmetric solution makes less sense here, because you have to store the private key on your database system anyhow.


Deterministic key generation In a situation where it is required to generate n number of keys deterministically from a single piece of seed information can we assume that b breached number of keys, no matter what the quantity would not help an attacker discover the previous nor next key in the set without the original seed data?

My initial thought is that it wont be possible due to the generation of one provably secure key to another provably secure key wouldn't given an attacker leverage leverage. If someone can confirm my thoughts though (or how wrong I am) that would be brilliant. Thanks.

What you want is a key derivation function (KDF).  Here's a fairly thorough list of some standardized ones.

Ps. The suggestion given by user1852723 to use HMAC, with your "seed" as the key and a counter (or other non-repeating sequence) as the input, more or less corresponds to the "Counter mode KDF" construction described in NIST SP 800-108, with HMAC as the underlying PRF.


Method for creating any involutive permutation The Fisher-Yates shuffle can produce any permutation of a set of $n$ elements. Is there anything that can do the same for creating an involutive permutation of $n$ elements where $n$ is an even number? This could be used to create involutive S-boxes.

The Fischer-Yates shuffle can be used to generate random (i.e. uniformly distributed) permutations. As mentioned in the comments, generating "any" permutation is trivial.
So I'll make the assumption that you want an algorithm to generate random involutions on $\{1, \ldots, n\}$, such that each involution has equal probability.

It is easy to see that any involution $\pi \in \mathrm{Sym}_n$ is the product of disjoint transpositions (i.e. all cycles have length at most two). This observation leads to the following simple strategy to generate random involutions: ($I_n$ below denotes the number of involutions on $n$ symbols)

Choose $1$ to be part of a one-cycle (with probability $I_{n-1} / I_n$) or a two-cycle (with probability $1 - I_{n-1}/I_n = (n-1)I_{n-2}/I_n$), i.e. $\pi(1) = 1$ or $\pi(1) = j$ such that $\pi(j) = 1$. In the former case, one can continue in tail-recursive manner by sampling an involution from $\mathrm{Sym}_{n - 1}$. In the latter case, choose $j \in \{2, \ldots, n\}$ uniformly at random and sample an involution from $\mathrm{Sym}_{n - 2}$ (again, recursively).

An important detail in the procedure above is how to sample with probability $I_{n - 1} / I_n$. It's probably best to precompute these probabilities and store them in a table.

I'm sure many references could be found for this simple method. For instance, the procedure above (with minor differences) can be found in Algorithm 9.4 of Jörg Arndt's thesis. An implementation in C++ can also be found there.


deterministic uuidv4 -> uuidv4 I need to copy a graph of elements with uuidv4s each, and separately stored relations containing element uuidv4s.

On copy, I need to change the ids. Of course all relation ids should still point to the correct corresponding location in the copy.

So I need a deterministic f(uuidv4): uuidv4 function.

I can work with a temporarily cached lookup table. But I wonder if there's a hashing function with the same result? This would give the added benefit of establishing a free relation between the original and the copy, which I otherwise will have to model as another relation.

E.g. I could create a new uuidv4 from a truncated sha256 output of the original uuidv4. But it does seem to violate the idea of random uuids for getting the necessary entropy.. Are there some thoughts on how the entropy may be affected?

Java's internal secure random generator works along similar principles, just uses the older SHA1. By rehashing a starting point (seed), you create a ersatz cryptographically secure pseudo random number generator (CSPRNG).  Albeit, you're only creating one output per seed.

The entropy isn't really affected and truncation is okay as we consider all of the SHA256 output bits as independent.  Unless you have very particular requirements and used a true random number generator, the likelihood is that the UUIDs were originally generated by some form of CSPRNG from the underlying OS.  You're just adding another round of processing.

The number of random  UUIDs (of 122 random bits) which need to be generated in order to have a 50% probability of at least one collision is $\approx 2^{\frac{n}{2}}$ or $\approx 2 \times 10^{18}$. There's a little bit more in the wiki article.


Can two different seeds produce the same output from a PRNG? In general, is it possible that two different seeds produce the same output from a PRNG? I'm not sure how many different types of PRNGs there are and maybe it depends on which one we consider. I know that an identical seed produces and identical output, but can different seeds stumble upon the same output (seed collisions)?

Well, yes, but the output should be limited by chance. It's kind of obvious that repetition is possible if you just consider a single bit of output. However, when you request more bits then the chance that the bits are equal should become less.

The seed or seeds are an entropy source for the PRNG. The PRNG should not disregard any bits that contain entropy, so the seed should be integrated into the state of the PRNG. A cryptographically secure PRNG should have quite a large state; the chance that a seed recreates a previously known state should be computationally impossible. The output is created using this state, and the output should therefore be random given a specific seed. So if the output is identical then it is by chance alone.

PRNG's are often constructed from secure hash functions. Getting collisions from output created by a secure hash is a computationally hard problem.

The output of stream ciphers using the same seed / key may not be able to repeat at all, for any amount of data that contains a full block. For instance counter mode encryption will never repeat the same block.

This is inconsequential for any block cipher with a block size of 128 bits or higher, as the likelihood of generating a repeating block by chance is also quite low, even if bounded by the birthday problem.

If a stream cipher has equivalent keys then the key stream may of course repeat if one of the seeds results in equivalent keys being used (as indicated by the comments below the question). Those stream ciphers however should not be considered secure PRNG's.

Note that stream ciphers usually lack procedures for e.g. adding seed material (re-seeding) to the state or extracting the entropy. A stream cipher doesn't fully comply with the interface for DRBG's as stated in NIST SP-800 90Ar1 although they are normally thought of to be PRNG's.


Does ChaCha20/Salsa have the same bit strength as AES for identical key sizes? Does ChaCha20/Salsa have the same bit strength as AES for identical key sizes? In other words, does ChaCha20 with a 128-bit key theoretically require 2^128 attempts to brute force, as with AES-128?

PS: Notwithstanding that ChaCha is a stream cipher.

Attacks on a cryptosystem with a 128-bit key are often much cheaper than $2^{128}$.  If you have the strings $\operatorname{AES}_{k_1}(812738)$, $\operatorname{AES}_{k_2}(812738)$, $\dots$, $\operatorname{AES}_{k_{1000000}}(812738)$, it costs only about $2^{128}/1000000 \approx 2^{108}$ AES evaluations to find one of the $k_i$ keys if you can parallelize it $p \geq n^2$ ways, and it will take the time for about $2^{128}/np \leq 2^{128}/n^3$ sequential AES evaluations.

You should use 256-bit keys, whether with ChaCha or AES or HKDF-SHA256 or KMAC128 or anything else.  The only reason ChaCha supports 128-bit keys at all, on paper, is that eSTREAM wanted to support 128-bit keys, so Salsa20 was made to support 128-bit keys, on paper, and the design carries over to ChaCha.  Hardly anyone ever actually does this.  The eSTREAM profile also specifically selected Salsa20/12, the 12-round version instead of the full 20-round Salsa20/20, also known as just Salsa20; similarly, ChaCha12 formally exists, but hardly anyone uses it instead of ChaCha20, also known as just ChaCha.

Now that we've gotten the generic issue of key size out of the way, there are a number of substantive advantages of ChaCha over AES that don't fit neatly into the glib ‘bits of security’ framework.

AES essentially cannot be computed efficiently in software without timing side channels.  ChaCha was designd for fast software implementation without timing side channels.

To match ChaCha's level of side channel security, AES requires hardware support—and that means you need to audit your entire software stack all the way down from the high-level protocols to the assembly code you're actually executing on all the physical machines you might be using, from spiffy x86 servers to years-old laptops to ARM phones to MIPS tablets.
AES is a pseudorandom permutation family of 128-bit blocks.  ChaCha is a pseudorandom function family from 128-bit inputs to 512-bit outputs.

This is mostly jargon that application developers don't need to concern themselves with, but these different shapes have a significant consequence: In most protocols, it is unsafe to use a single AES key for anywhere near ${\approx}2^{64}$ blocks of data, whereas there are no practical data volume limits per key on ChaCha.

For example, probably the most widespread use of AES is in AES-GCM, which uses it in the forward direction only, to approximate one-time pads, just like the ChaCha stream cipher.  The fact that AES is invertible is not helpful—in fact it makes AES appreciably worse at approximating one-time pads than ChaCha, thanks to the birthday paradox.
AES has a substantial key setup cost.  ChaCha has zero key setup cost.

To mitigate the data volume limits under a single key, or just to make key management simpler for complex applications, you can derive subkeys from a master key with a key derivation function or KDF.  This is how, for example, the XChaCha stream cipher supports a 192-bit nonce: it derives a subkey from 128 bits of the nonce, and then uses ChaCha with that subkey and the remaining 64 bits of nonce.  This is also how AES-GCM-SIV provides reasonable security bounds in spite of AES's $2^{64}$ birthday bound.

AES's high key setup cost means subkeys are expensive, while ChaCha's zero key setup cost means subkeys are essentially free.  For example, AES-GCM-SIV was designed under the premise that you are Google and you can afford to audit your entire software stack all the way down from the high-level protocols to the assembly code you're actually executing on all the servers in data centers that you care about, so you can reliably use hardware support for AES both to mitigate side channel attacks and to ameliorate the key setup cost with subkeys.  For the rest of us who are not Google—and even within Google on the teams that do Android and Chromebook development on a variety of platforms—the tradeoff of relying on AES hardware is not so clear.
The highest number of rounds broken by an attack cheaper than brute force for AES-256 seems to be 7, and for ChaCha also seems to be 7.  (The standard biclique attacks on full AES-128 are not obviously cheaper when you consider space and communication costs.)  But AES-256 has only 14 rounds, while ChaCha has 20.  So ChaCha has a higher ‘security margin’ than AES, which is a very rough fuzzy notion that you shouldn't worry too much about because neither one is broken; it just makes ChaCha come out looking a little sprightlier than AES.


S-box with differential uniformity = 2 I read that we do not know if there exists an 8x8 sbox with differential uniformity = 2.

I suppose we cannot compute every possible sbox because there are $64!$ possible s-boxes. Am I right?

There are 256! possible 8x8 S-boxes (i.e., bijective functions from $\{0,1\}^8$  to $\{0,1\}^8$).  This is an absolutely enormous number.  You couldn't possibly enumerate all of them within the lifetime of the universe.  So, yes, this is one reason why it is not straightforward to determine whether there exists such a S-box with differential uniformity 2.


DHE parameters: which parameters need to be random each time? In DH key exchange, first, both parties need to agree on a generator $g$ and prime $p$. After that each party computes its key (party A: $g^a \bmod p$) and (party B: $g^b \bmod p$), then they exchange these values to compute the shared secret. Can you please clarify which of these numbers should be random for each session (assume it is used with a protocol like TLS)?

TL;DR: $a$ and $b$.

For DHE in the multiplicative group modulo $p$, it is agreed on a large prime $p$ and an element $g$. This is typically long term, and there are standard public parameters, e.g. the 3072-bit MODP group of RFC 3526

After this, each time two parties A and B want a shared secret

party A draws a random $a$ and sends $h_A = g^a\bmod p$ and
party B draws a random $b$ and sends $h_B = g^b\bmod p$.
party A receives $h_B$ and computes $s_A={h_B}^a\bmod p$ and
party B receives $h_A$ and computes $s_B={h_A}^b\bmod p$.

If no message has been altered, $s_A=s_B$ and this is a shared secret $s$. It is typically used as input to a key derivation function or hash in order to generate some shared secret symmetric key(s).

More precisely, if the order of $g$ is a large prime (including when $(p-1)/2$ is prime and $g^{(p-1)/2}\bmod p=1$ and $1<g<p$), and $a$ and $b$ are uniformly random, independent, secret, and large enough, a passive adversary can not distinguish $s$ from a random element of the subgroup generated by $g$. Beware that the party sending its $h$ second can influence $s$ to some degree. Also, when $g$ is a generator of $[1,p)$ as in the question, the order of $g$ is $p-1$, thus even, and the Legendre symbol $\left(\frac sp\right)$ leaks. This is a consideration when using DHE without a key derivation function, discussed there.

The system was published by Withfield Diffie and Martin Hellman: New Directions in Cryptography, in IEEE Transactions in Information Theory, 1976, with some presentations in 1975. See this for how it was discovered but not published by Malcolm John Williamson, working for the GCHQ, in 1974.

Note: Nothing immediately disastrous happens if a single one of $a$ or $b$ is kept constant (making the corresponding $h_A$ or $h_B$ constant). However that static ephemeral setup is generally a bad idea for key exchange, because there remains no protection against a bad RNG on the side responsible for choosing the remaining random. Also, because it is used for a long time, the constant secret is more likely to leak, revealing all shared secrets. These are reasons why TLS 1.3 requires ephemeral ephemeral DHE (see this). When online key exchange is not an option, a secret must nevertheless be fixed: DHE becomes the first step of ElGamal encryption, with the static $h_A$ the public key for A, and $a$ the matching private key.

If we make both $a$ and $b$ static, the shared secret becomes a constant. That can still be useful (e.g. after a key derivation step with a random value), but this static static setup is hardly a key exchange protocol.

Note: In practice, in protocols like TLS, the exchange has extra steps in order to authenticate the parties using public/private key pairs, and guard against active attacks including Man in the Middle. This is Authenticated Diffie-Hellman key Exchange.

Note: the question says "each party computes its key", but $h_A$, $h_B$ are normally not considered "keys" in DHE. Only for static $a$ or $b$ are $h_A$ or $h_B$ said to be "public keys". $s_A$, $s_B$, normally the same, often are called the "shared key", although I prefer "shared secret", to distinguish from the output of a later key derivation step.


Why in one time pad must the key distribution to be truly random One time pad required a truly random key.
Why canwt it be a psudo-random key?
For example, if the key distribution is that for each bit the probability to get 1 is 0.6 and the probability to get 0 is 0.4, and the eavesdropper knows it, how can he decrypt the message (assuming that the key length is at least as big as the message length)?
Thank you

For an OTP to provide perfect secrecy it is required that the key stream is indeed purely random. A pure OTP is largely a theoretical construct because it is almost impossible to generate a key stream that is provably random. Any kind of information on the key stream may leak information on the plaintext, which means it is not perfectly secure. Practical OTP's that provide close to perfect secrecy on the other hand are, on the other hand, relatively common, see the comment from Paul below my answer.

Note that leaking information does not necessarily mean decryption; for instance if I encrypt the same message twice with a block cipher you won't know the input, but you can tell that the same message was encrypted because the resulting ciphertext blocks are identical. Any kind of information about the plaintext is enough for perfect secrecy to be broken.

Of course it is perfectly possible to use a pseudo random stream while maintaining practical security. Basically, this is what a stream cipher or block cipher in stream mode (e.g. CTR mode) does. However pseudo random streams indicate that there is some kind of mathematical relationship between the bits of the key stream. And this could be exploited by an attacker. The fact that such a relationship exists in itself is enough to break perfect secrecy.

There are obviously secure stream ciphers right now. We can however not prove them secure. So we cannot guarantee that they won't be broken in the future. Hence the perfect security premise doesn't hold, so they do not represent OTPs. Fortunately, if they are secure enough they don't need to.

It is possible to use a PRNG to create a practically secure key stream. PRNG and stream ciphers are closely related. Stream ciphers however have been especially designed to provide this functionality; they have advantages with regards to the API (treating the input key as key, having an explicit IV) and efficiency.

Beware that some random functions in programming applications may have implementations of PRNG's that are definitely not suitable for this kind of functionality. The shenanigans around "SHA1PRNG" in Java / Android should provide enough of a warning to anyone.

Way TL;DR: use a secure stream cipher


Find plaintext from two ciphers encrypted with a one-time pad and the same key I'm studying for a cryptography test and I came across this question:

  Assume a language has three letters: A=1111, B=0011 and C=1010. Two words in this language are encrypted with a one-time pad and by using the same binary key sequence. The first four bits for both corresponding cipher texts are, respectively: $C_1= 1110$ and $C_2=1000$. Determine the first letter of both corresponding plain texts as well as the first 4 bits of the key.

Isn't this question impossible to solve without additional information? Because:

  $C_1 = L_1 + K + P_1$

  $C_2 = L_2 + K + P_2$

  Where $C_i$ is the cipher text, $L_i$ is the encrypted letter, $P_i$ is the one time pad and $K$ is the key.

Seeing how $L_1, L_2, P_1, P_2$ and $K$ are unknown, it's not possible to solve this, right? Or am I missing something?

First, there seems to be a misunderstanding: The one-time pad is the key. So your equations simplify to
$$ C_1 = L_1 + K \text, $$
$$ C_2 = L_2 + K \text. $$

At this point, you would be right if the $L_i$ could contain arbitrary bit sequences. However, the question imposes a constraint: $L_i\in\{A=\mathtt{1111},B=\mathtt{0011},C=\mathtt{1010}\}$.

Let's look only at the first bit of all the variables (I'll denote these in lower-case). Since $c_1=c_2$ by observation, you know that $l_1=l_2$ from the equations above. Hence given the alphabet from the question, we know that either both $L_1$ and $L_2$ are $B=\mathtt{0011}$, or they are both not $B$. You can proceed similarly for the next bits, and at some point you should be able to reduce the set of possibilities to one unique solution.


How a chosen prefix collision is more useful than a standard collision concerning hashing functions? Recently a paper has been released about SHA-1 chosen prefix collision.

They present what a chosen prefix collision is, but I don't understand how is it more interesting than a standard collision ? They briefly mention x509 rogue certificate, but I still can't get the point.

Can anyone explain to me how interesting it is compared to standard collisions ? Hopefully with an example a bit more detailed ?

Thanks in advance !

In a chosen-prefixes collision attack, the adversary is able to freely choose two distinct prefixes $P$ and $P'$ of arbitrary content, and is able to find suffixes $S$ and $S'$ with $H(P\mathbin\|S)=H(P'\mathbin\|S')$.Note: It is common to write chosen-prefix when that logically should be chosen-prefixes.

In other types of collision attack the adversary freely chooses only one prefix $P$ (possibly empty) and is able to find distinct suffixes $S$ and $S'$ with $H(P\mathbin\|S)=H(P\mathbin\|S')$.

That makes a critical difference: only chosen-prefixes attacks allow the attacker to freely choose different meaningful content where the colliding messages differ.

Chosen-prefixes attack thus are much more flexible for the attacker. For example, in a pure text document, the prefixes could be the meaningful part of the text at start, with the suffix in the end after a few hundred space characters so that it never shows. That allows the attacker to prepare documents with vastly different contents of his choice (except for the end which does not show), and so that the signature of one will be valid for the other.

By contrast, in other types of collision attack, the attacker typically is unable to make similar forgeries for pure text files, and more generally data formats where insignificant data can only be at the end. Attacks can only target more flexible data formats (like Portable Document Format, Postscript, some compressed image formats, some executable file formats..) such that it is possible to turn the alteration in the suffix into an operationally meaningful difference. This is often hard or infeasible (depending heavily on details of the data format and attack context).

In particular, a chosen-prefixes attack is a near necessity to attack certificate issuance (but this is mostly theoretical: certification authorities could foil all such attacks by using an unpredictable Certificate Serial Number at start of the certificate; and powerful adversaries obtain practically working certificates under any identity they desire without any cryptographic attack, by using complacent certification authorities).

Addition: in practice a trailer can easily be added, so that $H(P\mathbin\|S\mathbin\|T)=H(P'\mathbin\|S'\mathbin\|T)$. The attacker is able to freely choose $P,P',T$, with the constraint $P=P'$ for non-chosen-prefixes collision attacks.


How exactly is the input message of SHA-256 (pre-)processed? I’m very interested how SHA-256 handles messages, but I’ve got 3 questions. (As I have already read in some answers before, SHA-256 is not directly performed on the message but on an array, thanks for that.)

In my understanding after padding the message to a multiple of 512 bit length, we put the message into a

  64 entry message schedule array w[0..63] of 32-bit words

Is this an array with 64 elements, each allowed to be 32 bits long?

  copy chunk into first 16 words w[0..15] of the message schedule array

But then I ask myself, if we have a message that is, for example 4096 bits long and we only fill the first 16 elements of the array with the original message, what happens to the other (4096-16*32 = 3584) 3584 bits of the message?

  s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)

What are the rightrotate and rightshift operators doing to the elements in the array?

So is this an array with 64 elements, each allowed to be 32 bits long?

Yes, although you could also use 128 elements of 16 bits or 256 elements of 8 bits if the (embedded) processor doesn't support 32 bit operations. SHA-256 however operates on 32 bits internally, so that's the most efficient word size.

If the implementation uses anything other than 32 bit operations then the 32 bit operations need to be replicated with one of the other word sizes.

  But then I ask myself, if we have a message that is, for example 4096 bits long and we only fill the first 16 elements of the array with the original message, what happens to the other (4096-16*32 = 3584) 3584 bits of the message?

They'll be processed after that chunk. SHA-256 operates on batches of 512 bits at a time, this is the 16 words as 16 * 32 = 512 bits chunk (Wikipedia pseudo code says: for each chunk).

Each chunk is processed and this updates the h0..h7 state, which provides the start of the next processing of the chunk. The final state is used to produce the output.

  What are the rightrotate and rightshift operators doing to the elements in the array?

Well, they move the bits of the selected word to the right. The rightrotate operation will put the bits that "fall off" the word back on the left. In cryptography we call this transpositioning.

It is possible to emulate any of these operations using bitwise masking operations if they are not directly available in the runtime (Java for instance does not support rotate, only shift).

Processors generally directly support shift and rotation.

Notes

Note that it is important to note that SHA-2 is defined to be big endian and SHA-3 (unfortunately) little endian. This is important when implementing the algorithm on a runtime with a different endianess.

Obviously the wikipedia pseudo code should not be implemented directly. For each chunk it reads:

  create a 64-entry message schedule array w[0..63] of 32-bit words

normally you make sure that SHA-256 implementation only allocates the message schedule array once, after which it can be reused for each chunk. The pseudo code was written to understand the algorithm rather than to provide a hint on how to implement it efficiently.


Question on PKCS11 2.40 spec and AES_CBC wrap PKCS11 cryptoki version 2.40 Current mechanism specification (section 2.8.5), says below statement for AES CBC wrap:

  For wrapping, the mechanism encrypts the value of the CKA_VALUE attribute of the key that is wrapped, padded on the trailing end with up to block size minus one null bytes so that the resulting length is a multiple of the block size

Questions:

if any key has NULL bytes (or zeros) at the end, how the unwrap knows how many padded bytes are added?
Also, I'm the beginner for cryptography so I'm not sure whether any secret key can end up with zeros or not. Please clarify me this also.

if any key has NULL bytes (or zeros) at the end, how the unwrap knows how many padded bytes are added?

PKCS#11 doesn't unpad unless you indicate PKCS#7 padding using _PAD. Decryption will just leave all the zero bytes. This is not a problem if you either know the size in advance, or if you've padded it yourself using a scheme that is compatible with the zero padding such as PKCS#7 compatible padding. PKCS#11's zero padding operation doesn't pad if the input is already a multiple of the block size, after all.

Also, I'm the beginner for cryptography so I'm not sure whether any secret key can end up with zeros or not. Please clarify me this also.

It can, but if you unwrap then the key size of any wrapped secret key is generally known in advance, so it shouldn't matter. You will have to provide the key size yourself in the template during unwrapping (if you use ECB or CBC without _PAD option). To quote the information in the mechanism page of PKCS#11 v2.40, section 2.8.5 AES-CBC:

For wrapping, the mechanism encrypts the value of the CKA_VALUE attribute of the key that is wrapped, padded on the trailing end with up to block size minus one null bytes so that the resulting length is a multiple of the block size. The output data is the same length as the padded input data. It does not wrap the key type, key length, or any other information about the key; the application must convey these separately.
For unwrapping, the mechanism decrypts the wrapped key, and truncates the result according to the CKA_KEY_TYPE attribute of the template and, if it has one, and the key type supports it, the CKA_VALUE_LEN attribute of the template.  The mechanism contributes the result as the CKA_VALUE attribute of the new key; other attributes required by the key type must be specified in the template.

(emphasis mine)
Private keys commonly use ASN.1/DER encoding, so if you wrap those you can calculate the size of the key using the first length field of the initial TLV value. Then you - or the token - can remove the spurious zero valued bytes.

Generally I'd avoid wrapping AES-192 keys, they are just a nuisance as the key size is not a multiple of the block size.
Moreover, I'd be extremely cautious when it comes to (asymmetric) private keys. Many tokens will happily use ECB or zero-IV CBC to encrypt private keys, and that may actually leak information about those wrapped private keys.
PKCS#11 is an old standard, and many of the careless decisions made at the beginning are likely to perpetuate far into the future.


Plain text size limits for AES-GCM mode just 64GB? Based on NIST SP 800-38D section 5.2.1.1, it seems that the maximum length of plaintext is 2^39-256 bits ~ 64 GB.

We've got 100+GB files in genomics that need to be GCM encrypted so are concerned about hitting this.

So two questions:

What's the source of this rather low limitation?
What happens (mathematically, not implementation wise) if you do cross this limit?

The source of the limitation lies in the fact that GCM has a fixed block counter using a 32-bit integer. Since the block size is $2^7$ bits, the total amount that can be encrypted with the CTR component is $2^{39}$ bits.

The first limit reducing this by 128-bits is the fact that the block counter starts at 1 and not 0, at least with a 96-bit nonce. Nonce sizes other than 96-bits are know to have reduced security. The second limit reducing this by 128-bits is because the CTR component is also used to encrypt the final GHASH prior to tag output.

Implementation wise, you should not be allowed to cross this limit. In theory, the security breaks down. There are different security limits for the amount of data encrypted, and for the amount of tags generated. With a long message, an $n$-bit tag provides $n-k$ bits of authentication security for a $2^k$ block message, in your case this brings it down to around $2^{63}$ with a file between 100 and 128 GB when used with a 96-bit tag, much lower than the $2^{128}$ one may expect. The worst case scenario is recovery of the hash subkey $H$, allowing forgery of tags with the same key.

Encrypting a full size 128-bit tag with a separate key in ECB mode should eliminate that problem, as the bits will no longer be malleable. That can be done as a wrapper around a GCM implementation with minimal modification and almost 0 overhead. The implementation would need to be modified to use a larger block counter, and the nonces would need to be shorter. You would no longer be able to call it GCM, but would be able to make use of all the features and code that make GCM implementations fast and timing attack resistant. A 32-bit nonce and a 40-bit block counter (with no additional GHASH) would allow almost 16TB per nonce, without the restriction of changing keys for every message if you encrypt the tag with a second key. If you even consider something like this, a professional consult on both the modifications and the code to do it would be highly recommended, new security proofs would need to be developed.

Other solutions to the problem including not using GCM, but a different mode like Poly1305-AES. OCB mode also has a suggested limit of 64GB per key, CWC mode has the same limit as GCM.


Trying to calculate the strength of a Bitcoin brain wallet created with a custom diceware password I want to create a brain wallet using a custom diceware since I don't like the original one. Instead of 7776 words it has 46656 because I use 6 dice for each word instead of 5, and also it only has words with many characters.

So this is what I got so far, please tell me if I made a mistake:

$$\frac{2 ^ {\log_2(46656) · 5} }{ (1 · 10^{15}) · (60 · 60 · 24 · 365)} = 7 \text{ years}$$

$2 ^ {\log_2(46656) · 5}$ is the entropy for a password of 5 words
$1 · 10^{15}$ is 1 Phash/s, which is the hashing power I'm assuming for this attacker. I don't even know if this makes sense, because an attacker doesn't need to start over for each brain wallet he wants to crack, and also there might have been huge databases of precomputed sha256 hashes before Bitcoin even existed.
$60 · 60 · 24 · 365$ represents a year in seconds.

Generally correct.

It would take approximately 7 years to brute-force all possible keys generated by your brainwallet format, for an attacker with 1Petahash/sec hashing power. For reference, the current hash rate of the entire Bitcoin network is roughly 1 exabyte / second, 1000 times your hypothetical attacker's hash rate.

This means that on average it would take approximately 3.5 years to crack a single brainwallet.

You also mentioned precomputed hashes. For an attacker to precompute all of the given hashes (assuming 32 bytes per SHA256 hash), they would need to store $46656^5 * 32 \approx 7.07 * 10 ^ {24}$ bytes, amounting to 7.07 yottabytes. This is currently an unpractical amount of storage.


How to deal with collisions in Bitcoin addresses? When creating a Bitcoin account, you need to issue a couple of private/public ECDSA keys. Then, you derive your account address by taking a 160-bit hash (through SHA-256 and RIPEMD) of the public key and use a custom Base 58 algorithm to convert it to alphanumeric values (see the picture below, I took it from this page).

My question is that collisions might happen (not necessarily malicious ones, but incidental ones). I would like to know whether there is a specific mechanism in the Bitcoin protocol to sort out these collisions and be ensured that the payment is going to the right place.

In fact, I tried to look through the protocol details but could not find anything dealing with this problem. The only reference I found is on the Bitcoin-wiki and it states that:

  Collisions (lack thereof)

  Since Bitcoin addresses are basically random numbers, it is possible, although extremely unlikely, for two people to independently generate the same address. This is called a collision. If this happens, then both the original owner of the address and the colliding owner could spend money sent to that address. It would not be possible for the colliding person to spend the original owner's entire wallet (or vice versa). If you were to intentionally try to make a collision, it would currently take 2^107 times longer to generate a colliding Bitcoin address than to generate a block. As long as the signing and hashing algorithms remain cryptographically strong, it will likely always be more profitable to collect generations and transaction fees than to try to create collisions.

  It is more likely that the Earth will be destroyed in the next 5 seconds, than that a collision would occur sometime in the next millennium.

I found this explanation extremely unsatisfactory. If any of you have a better explanation than that, or know about a prevention mechanism that has been planted into the Bitcoin protocol, I would be delighted to read about it.

Cryptography (and real security in general) offer quantitative analysis of the security provided - Meaning, real security products will describe how long they will resist a certain class of attack.

With cryptography, we select our parameters such that the time required to perform the best attack would exceed the amount considered to be practical, realistic, or feasible.

With a larger input space then output space, collisions must exist - therefore the only solution is to:

Accept that collisions must exist
Make collisions so rare as to not be a problem

This is exactly what the bitcoin protocol has more or less done. Granted, $2^{80}$ could arguably be a little bit bigger for more comfort; Bitcoin could have used bigger hash functions, but they may have been limited by availability at the time. If you were going to re-design it, I'm sure you would use larger sizes now. But that's always easy to say in retrospect...