16
$\begingroup$

My question is about choosing the rotation values in ARX design such as SIMON-like or SPECK-like ciphers to provide optimal differential and linear immunity. According to this, the selection of $a$ and $b$ values (shown in SIMON-like figure below) must comply with the condition $\text{gcd}(n, a-b) = 1$ where $n$ is the size. Attached ARX structures with $2/4$ branches of SPECK and Marx (Mix + arx).

How have the rotation values been selected? Was the selection it ad-hoc (then tested against common cryptanalysis such as differential/linear or rotational) or systematic such as the selection of $a$ and $b$ in SIMON-like? does the size of plaintext size (32/64/128 bit) influence the round constants?

simon-likespeck-likemarx

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I can speak regarding Simon, but that is a specific case. In the case of Simon, it was picked for the 8-bit CPUs that we used in embedded system. There's a discussion in the Simon design document $\endgroup$
    – b degnan
    Aug 30, 2018 at 0:35
  • 3
    $\begingroup$ @bdegnan You cannot speak regarding Simon ... in the case of Simon. Did you mean to write "Speck" in the first sentence? $\endgroup$
    – Maarten Bodewes ♦
    Oct 20, 2018 at 1:56
  • $\begingroup$ These questions are often hard to answer because we cannot look into the mind of the authors of the schemes. One thing that works remarkably often is to ask the authors of the schemes themselves. So send them a well worded email, and if anywhere possible, direct them to the site (otherwise post the response yourself). $\endgroup$
    – Maarten Bodewes ♦
    Nov 27, 2018 at 13:04
  • $\begingroup$ I already emailed some of them but unfortunately no response until now. $\endgroup$
    – hardyrama
    Dec 4, 2018 at 9:14

1 Answer 1

Reset to default
9
$\begingroup$

Leaving besides that the designers (NSA) of Simon and Speck did not provide an initial design rational for their ciphers/parameter choices, they added some notes later after pressure from the cryptographic community/ISO. There they mention that they selected the round constants to be

... optimal with respect to resistance against 8-round differential and linear attacks...

and

...many of these led to poor performance on software devices (especially 8-bit microcontrollers) and so were rejected...

There are some other ARX ciphers like for example Chaskey and MergeMAC who argument the choice of the round constants with

... our choice of constants, implementation on 8- and 16-bit microcontrollers will be more efficient than had these constants been chosen at random ...

and

The rotation constants in our permutation are chosen to be optimal for microcontrollers which often only allows efficient rotations/shifts by one or two bits, and byte-permutations by 8-bits.

So one of the reasons for the choice of rotation parameters is that they are optimal for implementations.

Another point for choosing the rotation parameters comes from a security point of view regarding differential/linear attacks. The non-linearity of ARX ciphers only comes from the modular addition. If we look closer into modular addition, we can see that the non-linearity actually just stems from the carry propagation (more details i.e. here), as the sum is simply just an XOR (which is linear). In general, for ARX ciphers the best rotation constants would shift a difference to a position where it reaches the msb last (as a difference in the msb is not counted in the calculation for the probability). Therefore, one can ensure that the differences quickly build up and are not canceled out.

Moreover, regarding the rotation constants for Speck, the designers of the block cipher Sparx mention in their paper

While it is possible to choose the rotations used in Speckey in such a way as to slightly decrease the differential and linear bounds, such rotations are more expensive on small microcontrollers which only have instructions implementing rotations by 1 and by 8 (in both directions)

and they also provide the different rotation constants that actually would improve the differential/linear bounds of Speck (for the cost of less efficiency):

Both can be lowered by a factor of 2 if we choose rotations (9,2),(9,5),(11,7) or (7,11) instead of (7,2).

The size of the plaintext influences the choice of round constants indirectly, as one would have to choose a constant such that it is obviously between 1 and the wordsize = plaintext size/number of branches. This is because a rotation of 0 won't change anything and a rotation large then the wordsize would just be the same as a rotation modulo the wordsize.

Improve this answer
$\endgroup$

Your Answer

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

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