[Paper Review] Non-uniform cracks in the concrete: the power of free precomputation

Again, another paper discussion. It is the paper from D.J. Bernstein and T. Lange that will be presented on the Asiacrypt this year. It is a very special paper with the titel "Non-uniform cracks in the concrete: the power of free precomputation". It subtle criticizes the way security proofs are made in the area of provable cryptography. They describe that the current proofs do not cover the free will of an attacker correctly. E.g., they argue, that the proofs do not consider the possibility of precomputation or the option for an attacker to trade success probability for an easier to find algorithm.

# Background #

Koeblitz and Menenzes did something similar before and they were criticized due to scratching at the base elements of provable cryptography. From my point of view, i can understand both sides and i don't like blaming the other side for having a different opinion.

All the achievements in provable cryptography gave us nice and beautiful tools to work with. These tools seem to work very well and having them in the toolbox are by far better than having nothing at hand. However, trying to enhance a current situation in order to give people even better tools at hand, can not be bad at all. And whenever there is an argument that could falsify some theorems systematically (not just because of bad / wrong proofs), one has to somehow incorporate those arguments. Are they correct, are they relevant? Could previous definitions slightly changed to cover those new arguments to increase the security strength to a higher level?

The attacks presented in the paper are not efficient enough to pose a security risk in practise, but show that the theoretical lower bounds from given standard assumptions/theorems can be beaten significantly.

# An example from the paper # 

Let me restate the first example from their paper. Since the paper is very long, you better read the rest for yourself.  

In their first attack, they show that the output blocks of $\mathsf{AES}$ (or any other block cipher) could be distinguished from a uniform distribution with a much higher probability than previously assumed. 

W.l.o.g. they chose $\mathsf{AES}$-128 bit. Normally one would expect, that for a given random plaintext block $b$ and uniformly distributed $128$-bit keys $\mathcal{k}$, the output blocks $c = \mathsf{AES}_\mathcal{k}(b)$ are also uniformly distributed in the $\{0,1\}^{128}$ cipher space. But that's not what Bernstein and Lange directly attacked. Instead they argued that the concatenation of $\mathsf{AES}_\mathcal{k}(b_i)|\mathsf{AES}_\mathcal{k}(b_{i+1})$ is far away from being uniformly distributed in the $\{0,1\}^{256}$ space. Surely, the concatenation $$ S_1 := \mathsf{AES}_\mathcal{k}(b_i)|\mathsf{AES}_\mathcal{k}(b_{i+1}) $$ is only capable to produce $2^{128}$ possible $256$-bit strings. The reason is, that even if the first part, $\mathsf{AES}_\mathcal{k}(b_i)$, is able to produce $2^{128}$ different string, the second part depends on the key of the first part and hence there is only one possible encryption for $\mathsf{AES}_\mathcal{k}(b_{i+1})$. They compare that string with the output of a function $P$ that executes a random permutation a given $128$-bit string. So the concatenation $$ S_2 := P(0)|P(1) $$

produces $2^{128}\cdot 2^{128} - 2^{128} $ $256$-bit strings. The subtraction term is due to the fact that $P(0)$ and $P(1)$ do execute never the same permutation. But, how to distinguish the distribution of the $S_1$ strings from the distribution of the $S_2$ strings?

What they did is: They pick the $\mathsf{MD5}$ hash function and feed it with the strings $S_1$ and $S_2$. Actually, they replaced the first bit of $\mathsf{MD5}$ with a uniform function from $\{0,1\}^{256} \rightarrow \{0,1\}$. Then they argue that, since $S_2$ is picked from the uniform distribution

• The first bit of $\mathsf{MD5}(S_1|S_2)$ will be $0$ or $1$ with almost nearly $50\%$ probability.
• The first bit of $\mathsf{AES}_\mathcal{k}(b_i)|\mathsf{AES}_\mathcal{k}(b_{i+1})$ may diverge from being $0$ or $1$ with $50\%$ probability, since the $\mathsf{AES}$ operation chooses a random subset of size $2^{128}$ from $2^{256}$ and that could result into a slightly predomination of $0$ or $1$, according to which subset was chosen.

Comment: I guess another way to show this, is to utilize the birthday-paradox. In the distribution of $S_1$ string you are likely more to see an element appear twice than in the distribution of $S_2$ string. After a certain amount of detected collisions, you can distinguish this two distributions probably with a much higher probability than $2^{-128}$.

Then they present method to increase the success probabilities of such attacks, e.g., by precomputing certain values. They show similar attacks also regarding the NIST P-256 elliptic curve, DSA-3072, RSA-3072.

# Rescue Strategy #

In the later part of the paper, they present ideas how to overcome the disadvantages of the previous definitions. They suggest to make the following changes:

1. switching the defi nitions from the RAM metric used in [...] to the NAND metric, an "alternative" mentioned in [...]
2. switching the de finitions to the AT metric, a standard hardware-design metric formally de fined by Brent and Kung in [..]
3. adding constructivity to the de finitions, by a simple trick that we have not seen before (see Appendix B.4);
4. adding uniformity to the de finitions.

I am curious to see, if this new suggestions are going to be used by the rest of the community in the future.