2
$\begingroup$

I tried a number of different inputs and keys and checked their respective hamming distances after each round. It seems PRESENT has an ideal or near ideal hamming distance (31 to 33) after only a few rounds. Indeed, some of the later rounds have worse hamming distances, e.g. 38 to 41. So why is it necessary to have so many rounds?

$\endgroup$
4
  • $\begingroup$ what do you mean by hamming distances ? between what and what ? $\endgroup$
    – Biv
    Jul 4 '17 at 11:28
  • 2
    $\begingroup$ Are you sure your findings about hamming distance getting worse(I assume you mean average moving away from n/2 with that?) with increasing rounds are statistically significant? $\endgroup$ Jul 4 '17 at 12:03
  • $\begingroup$ I observed hamming distances between an input M and each of the corresponding 32 outputs. I repeated this with several distinct inputs M. I also tried the same idea but with different keys K. In all cases the hamming distance were in the range 31 to 33 after only a few rounds, even just one or two rounds in some cases. $\endgroup$
    – Red Book 1
    Jul 5 '17 at 5:16
  • $\begingroup$ Not all later rounds were worse, but many were. For example, some hamming distances were in the range 29 to 34 by the end of the eighth round, but 36 to 41 several rounds later. $\endgroup$
    – Red Book 1
    Jul 5 '17 at 5:23
2
$\begingroup$

I think that the reason for 31 rounds is in their paper, Section 5.1. Bogdanov et al. have approximated a small $2^{−43}$ bias that occurs after 28 rounds of linear analysis. Therefore they added another 3 rounds to arrive at a slightly unusual odd number of rounds.

This is how ciphers are designed. There are no specific rules passed down through the generations on how many rounds a cipher should have. We do know that more rounds improves resistance to analysis. A very simple primitive can be easily strengthened by the addition of more rounds, and this fact is explicitly stated in the design notes for Skien and Threefish. And preventing a designer from having 1000 rounds is the need to achieve a speed /performance for their target market. So they compromised at 31.

Singular increases in the round count work for PRESENT. It's worth adding that sometimes its not possible to increase the round count by any arbitrary value. The number of rounds has to match the key schedule and sometimes the schedule is designed more inflexibly than the main algorithm.

$\endgroup$
5
  • 1
    $\begingroup$ I am guessing that due to the "lightweight" cipher class of PRESENT; they also made 31 rounds because you can get the load state for free, not to mention the cryptographic safety margin. I used a $2^5$ counter and then ended up with the loading state as the zero reset, and then the completion was the overflow I do not know if that was their intention, but it was much nicer than the craziness on AES with only 14 rounds from a counter perspective. $\endgroup$
    – b degnan
    Jul 4 '17 at 12:52
  • 1
    $\begingroup$ @bdegnan Yes, AES looks like one of those ciphers that can have arbitrary key expansions, so I guess that you could have my 1000 rounds. Speed (like always) was a major winning factor. I wonder who would have won if there had been a server only category, or if security had been weighted well above performance... $\endgroup$
    – Paul Uszak
    Jul 4 '17 at 13:04
  • $\begingroup$ Would the bias be different (better) if the permutations were different for each of the 31 rounds? And what if each of the permutations also changed dynamically after each full encryption? $\endgroup$
    – Red Book 1
    Jul 8 '17 at 1:08
  • $\begingroup$ @RedBook1 The bias would certainly be different. I think that's all I can say in such a hypothetical case. It might not be measurable at all. It might be hugely worse for a poor permutation choice. Thing is, PRESENT is about as light weight as theoretically possible in that it has the bare minimum of a substitution bit, permutation bit and a round key bit. 31 unique round permutations would require a (relatively) massive code increase to inject all that additional entropy. And the code for dynamic permutation? It wouldn't be PRESENT much... $\endgroup$
    – Paul Uszak
    Jul 8 '17 at 1:46
  • $\begingroup$ Yes. I take your point. However, let's assume for a moment that we are not so interested in how 'lightweight' the ciphers is. Assume we are only interested in security. In fact, I have made a PRESENT-like cipher that includes randomly generated permutations for each round and after every full encryption they all change again. When I compared the hamming distances between M and each of the 32 outputs, my cipher has similar hamming distances to PRESENT (original). So my question is, since my perms are random and dynamic might it be a good case for fewer rounds with the same level of security? $\endgroup$
    – Red Book 1
    Jul 8 '17 at 12:15

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.