Friday, June 23, 2017

Algorithm and Key Size Document

The ECRYPT Algorithm and Key Size document is probably the most high impact output from our ECRYPT projects. It is referenced and used throughout the world, to guide the uses of cryptography in practice. The current version of the document can be found here

We are requesting input for the next edition of this document. To do this we have created a Slack channel where people can debate inputs.

We encourage everyone to get involved by sending us your email so we can add you. Once added you can add other people to the channel as you see fit. Please email Nigel Smart or Saartje Verheyen to be added if you do not know someone who is already involved.

We ask you to add comments to the slack channel of corrections and new text to add (including where you think it should go). After you have presented some input, other people can then comment on your text, and add further corrections. 

At the end of September we will freeze the discussion and start the process of incorporating all the suggestions into the final document. 

If you have contributed to the Slack discussion in a positive manner we will include you as an author on the final document as a contributor. That way you get to claim you have contributed to a high impact document (carrot); if you do not contribute however then you cannot complain if we say something you disagree with (stick). 

Of course in the end it is a community effort, and in case of disagreement the editors will need to take one side or another.

Friday, June 16, 2017

Boomerang Attacks

In cryptography, a boomerang attack is a method of cryptanalysis that is based on differential cryptanalysis.

Boomerang attacks were first introduced by Wagner and allow an adversary to concatenate two high probability differential trails to attack a cipher. This is especially useful if there is a lack of long differentials with sufficient probabilities. The adversary can therefore decompose the encryption function $F$ in two subciphers $f$ and $g$ such that $F = f \circ g$. Then the adversary can search for high probability trails $\Delta \rightarrow \Delta^*$ with probability $p$ for  $f$ and  $\nabla \rightarrow \nabla^*$ with probability $q$ for $g$. The differential trails can then be combined in a chosen plaintext/adaptive chosen ciphertext attack to mount a boomerang distinguisher and then a key recovery attack based on this distinguisher to recover the secret key.

A boomerang distinguisher

The basic attack works as follows:

  1. The adversary chooses a random plaintext $X_1$ and calculates $X_2 = X_1 \oplus \Delta$.
  2. The adversary requests the ciphertexts for $X_1$ and $X_2$ from an encryption oracle which are $Y_1 = F(X_1)$ and $Y_2 = F(X_2)$
  3. Calculate ciphertexts $Y_3 = Y_1 \oplus \nabla$ and $Y_4 = Y_2 \oplus \nabla$.
  4. Request the decryptions of $Y_3$ and $Y_4$ to obtain $X_3 = F^{-1}(Y_3)$ and $X_4 = F^{-1}(Y_4)$.
  5. If the difference between $X_3$ and $X_4$ is the same as between $X_1$ and $X_2$, namely $\Delta$ we obtain a correct quartett $(X_1, X_2, X_3, X_4)$.

Calculating a correct quartet requires an attacker to consider both plaintext pairs $(X_1, X_2)$ and $(X_3, X_4)$ and results in a total probability of (pq)^2.
For an attack to succeed, for the probability of the boomerang distinguisher it must hold that $(pq) > 2^{n/2}$. For N plaintext pairs, an adversary expects about $N\cdot(pq)^2$ correct quartets in an attack, while there are only $N\cdot2^{-n}$ (where n is the blocksize) correct quartets for an ideal primitive.