14
$\begingroup$

The md5 specification gives a series of 4 rounds to execute over a 16-word block.

Each round has a repeating sequence of 4 shift amounts (s in [abcd k s i]) :

  • 7, 12, 17 and 22 for the round 1
  • 5, 9, 14 and 20 for the round 2
  • 4, 11, 16 and 23 for the round 3
  • 6, 10, 15 and 21 for the round 4

The specification only says:

The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

How did they find these shift amounts? Is it a sequence like $u_n = (u_{n-1} + j) \; mod \; k$ ? What guarantees the "avalanche effect"?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ They were probably found by empirical testing. XORs and additions are replaced with ORs then you set block to all null but one, full diffusion happens when block is all ones. Look at schneier.com/skein1.3.pdf "Appendix D NIST SHA-3 Round 2 Tweak: Rotation Constants" and "D.1 Deprecated Skein Rotation Constants". $\endgroup$ – LightBit Dec 23 '14 at 21:10
  • $\begingroup$ if you do find an answer, please come back and write it, it's interesting! $\endgroup$ – David 天宇 Wong Dec 25 '14 at 17:15
  • $\begingroup$ For the sine based stuff and the h0-h3, I think this question and answers apply. Specifically the "nothing-up-my-sleeve" point. For the shift amounts, it may be the same, but I'd need to verify. $\endgroup$ – mikeazo Oct 6 '15 at 15:52
  • $\begingroup$ I have seen that post and I read the "nothing-up-my-sleeve" point, however it only gives examples of 'good constants' and not of 'bad constants'. e.g. he says which numbers CAN be used as constants (pi), but not which ones CANT. $\endgroup$ – Thomas Wagenaar Oct 6 '15 at 16:03
2
$\begingroup$

By trying all the 128 different bit position on the state, 19 rounds (over the 64) are required for a full avalanche effect (source code).

round  0: 00000000000000000000000000000001 00000000000000000000000010000000 00000000000000000000000000000000 00000000000000000000000000000000
round  1: 00000000000000000000000000000000 00000000000000010000001000000000 00000000000000000000000010000000 00000000000000000000000000000000
round  2: 00000000000000000000000000000000 00000010100000000000000000000001 00000000000000010000001000000000 00000000000000000000000010000000
round  3: 00000000000000000000000010000000 01010000001000000101000000100000 00000010100000000000000000000001 00000000000000010000001000000000
round  4: 00000000000000010000001000000000 10100001010100101010000101010010 01010000001000000101000000100000 00000010100000000000000000000001
round  5: 00000010100000000000000000000001 11110011111100111111001101110011 10100001010100101010000101010010 01010000001000000101000000100000
round  6: 01010000001000000101000000100000 11110011111100111111001101110011 11110011111100111111001101110011 10100001010100101010000101010010
round  7: 10100001010100101010000101010010 11111111001111110011111100110111 11110011111100111111001101110011 11110011111100111111001101110011
round  8: 11110011111100111111001101110011 11111111111111111111111101110111 11111111001111110011111100110111 11110011111100111111001101110011
round  9: 11110011111100111111001101110011 11111111111111111111111101110111 11111111111111111111111101110111 11111111001111110011111100110111
round 10: 11111111001111110011111100110111 11111111111111111111111111111111 11111111111111111111111101110111 11111111111111111111111101110111
round 11: 11111111111111111111111101110111 11111111111111111111111111111111 11111111111111111111111111111111 11111111111111111111111101110111
round 12: 11111111111111111111111101110111 11111111111111111111111111111111 11111111111111111111111111111111 11111111111111111111111111111111
round 13: 11111111111111111111111111111111 11111111111111111111111111111111 11111111111111111111111111111111 11111111111111111111111111111111

As for the exact answer to the question, only Rivest will be able to say how he found his values. However as LightBit stated it is likely that

they were probably found by empirical testing. XORs and additions are replaced with ORs then you set block to all null but one [bit], full diffusion happens when blocks are all ones.

As for how to measure the avalanche effect, multiple statistics can be used (see section 4.2).

Improve this answer
$\endgroup$
6
$\begingroup$

The rotation countsr (together with the order of access of the 4 words of the state) are engineered for fast diffusion, as documented in RFC1321:

The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect". The shifts in different rounds are distinct.

The general idea is to move bits to a 32-bit position on which they previously had no or little influence (limited to the effect of carry propagation in 32-bit addition, which works only to the left, and has odds like $2^{-n}$ to influence the $n$th bit on the left of a particular one); also, the choice made should facilitate efficient propagation in the next few steps. Among particularly bad choices would be to change the constants r to a mix of 1 and 31; or to all 16.

I do not know if the choice made for MD5 turned out to prevent or facilitate attacks on collision-resistance.

All the other constants in the question are chosen with a nothing-up-my-sleeve rationale; that is, convincingly unlikely to have been chosen according to a hidden property. That includes numbers computed according to a simple formula unrelated to the rest of the context (like floor(abs(sin(i + 1)) × 2^32) is); or numbers matching an obvious pattern (like being the representation of the hex string 0123456789ABCDEFFEDCBA9876543210 according to the endianness used in the context).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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