1
$\begingroup$

Recently, I was reading about Blake2B and its properties regarding randomness and security, and its connection to Daniel Bernstein's CHA CHA digest. As a budding cryptographer, I find it doable to implement those algorithms, but I find it very hard to grasp why the specific functions were chosen. From wikipedia, this is Blake2's mixing function:

Function Mix
   Inputs:
        Va, Vb, Vc, Vd       four 8-byte word entries from the work vector V
        x, y                two 8-byte word entries from padded message m
   Output:
        Va, Vb, Vc, Vd       the modified versions of Va, Vb, Vc, Vd

   Va ← Va + Vb + x          with input
   Vd ← (Vd xor Va) rotateright 32

   Vc ← Vc + Vd              no input
   Vb ← (Vb xor Vc) rotateright 24

   Va ← Va + Vb + y          with input
   Vd ← (Vd xor Va) rotateright 16

   Vc ← Vc + Vd              no input
   Vb ← (Vb xor Vc) rotateright 63

   Result ← Va, Vb, Vc, Vd
End Function Mix

The two most important questions I have are:

  1. How exactly did the designer come to these specific steps?
  2. How exactly did the designer come to the specific constants and more importantly - if I were to take some operation and change it slightly, how would it affect the security of the algorithm? If, for example, I were to rotate right by 61 instead of 63 and 25 instead of 24, how would it affect the security of the algorithm as a whole? Extension - how did the designer (and presumably many researchers) fine-tune these constants till they reached the final Blake2b?

I know, for a non-related instance, that choosing the right polynomial in these kinds of applications is very critical, but I do not see how any value could be called "optimal" in the above mentioned context - one value which may work well for some kinds of data may not work well with other kinds of data.

If possible, can you please explain it in an intuitive way, going if needed into technical details, very slowly? Any answer will be appreciated very much!

$\endgroup$
2

1 Answer 1

0
$\begingroup$

TL;DR: the values of the rotation selected allow for a speedup on some platforms, while conjectured to not badly impact security.

This is clear in the article introducing BLAKE2b.

BLAKE2b (or just BLAKE2) is optimized for 64-bit platforms—including NEON-enabled ARMs—and produces digests of any size between 1 and 64 bytes

Rotations optimized for speed
The G function of BLAKE-512 performs four 64-bit word rotations of respectively 32, 25, 16, and 11 bits. BLAKE2b replaces 25 with 24, and 11 with 63:

  • Using a 24-bit rotation allows SSSE3-capable CPUs to perform two rotations in parallel with a single SIMD instruction (namely, pshufb), whereas two shifts plus a logical OR are required for a rotation of 25 bits. This reduces the arithmetic cost of the G function, in recent Intel CPUs, from 18 single cycle instructions to 16 instructions, a 12% decrease.
  • A 63-bit rotation can be implemented as an addition (doubling) and a shift followed by a logical OR. This provides a slight speed-up on platforms where addition and shift can be realized in parallel but not two shifts (i.e., some recent Intel CPUs). Additionally, since a rotation right by 63 is equal to a rotation left by 1, this may be slightly faster in some architectures where 1 is treated as a special case.

As to why the new values are unlikely to impact security too badly: diffusion is only mildly reduced. Notice that ignoring the carries, with three rotations by 32, 24 and 16, a change in any bit of each byte diffuses to each bit of the same rank of each other 7 bytes of a 64-bit word. Admittedly, 11 was better than 63 is from the standpoint of intra-byte diffusion (12 would allow a change in any bit of each quartet to diffuse to each bit of the same rank of each other 15 quartets of a 64-bit word). However the additions and the 63 contribute to mixing bits of each byte reasonably effectively.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.