4
$\begingroup$

It seems there are few books on PRESENT and even fewer that give any reasoning behind the mechanics of the key schedule.

I understand how it works to the extent that I made a simple Excel program of it. I can clearly see all the steps and I assume it works as it matches test vectors.

However, I do not understand why certain bits were XORed rather than others, or why the round counters have to be in order $1-31$. My questions are:

  1. In simple terms, how does the key schedule protect it from key related attacks?
  2. What if (for instance) we changed the step $S[b_{78}b_{77}b_{76}b_{75}]$ to something else, such as $S[b_{74}b_{73}b_{72}b_{71}]$ or anything else. Would that make it weaker? Stronger? No different?
  3. What if the round counters were not in the order $1,2,\ldots,31$? What if the round counters were any order of $1-31$? Again, would this make it weaker, stronger or no different?

Thx.

$\endgroup$
1
$\begingroup$

Question 1

In simple terms, how does the key schedule protect it from key related attacks?

According to the paper "Lightweight Block Ciphers Revisited: Cryptanalysis of Reduced Round PRESENT and HIGHT", the non-linearity of the key schedule contributes to resistance to related key attacks:

Related-key differential attacks, on the other hand, are also believed to be inapplicable because of the sufficient non-linearity due to [sic] key scheduling algorithm.

The above quote then points to a reference to New Types of Cryptanalytic Attacks Using Related Keys, which mentions the following:

These attacks are based on the observation that in many blockciphers we can view the key scheduling algorithm as a set of algorithms, each of which extracts one particular subkey from the subkeys of the previous few rounds. If all the algorithms of extracting the subkeys of the various rounds are the same, then given a key we can shift all the subkeys one round backwards and get a new set of valid subkeys which can be derived from some other key. We call these keys related keys.

Then, the description of the key schedule they give is:

The subkeys for each round are derived from the user-provided secret key by the key scheduling algorithm. We provide only the details of the key scheduling algorithm of Present-128 as it is the main target of this paper: 128-bit secret key is stored in a key register $K$ and represented as $k_{127}k_{126}\dots k_0$. The subkeys $K_i (0 ≤ i ≤ 31)$ consist of 64 leftmost bits of the actual content of register $K$. After round key $K_i$ is extracted, the key register $K$ is rotated by 61 bit positions to the left, then S-box is applied to the left-most eight bits of the key register and finally the round counter value, which is a different constant for each round, is XORed with bits $k_{66}k_{65}k_{64}k_{63}k_{62}$...

So the S-Box in the key schedule provides some non-linearity. And the addition of the counter may also serve to make the key schedule function for each round different and provide some resistance to the attack in [2] - If this is in fact the case, it is not explicitly stated anywhere that I can find.

Question 2

What if (for instance) we changed the step $S[b_{78}b_{77}b_{76}b_{75}]$ to something else, such as $S[b_{74}b_{73}b_{72}b_{71}]$ or anything else. Would that make it weaker? Stronger? No different?

I presume this is about the main round function and not about the key schedule, since these indices don't appear to be a part of the key schedule.

The S-Box is applied on each group of 4 contiguous bits in parallel, so the answer is that both $S[b_{78}b_{77}b_{76}b_{75}]$ and $S[b_{74}b_{73}b_{72}b_{71}]$ are both performed. Swapping one for the other would have no effect.

As for why the 4-bit wide S-Box would be applied on contiguous sections of 4 bits in parallel, the answer is because it is really the only way to do it. The bit permutation that follows the S-Box scrambles the indices so that successive applications of the S-Box are applied to different groupings of bits. But these are separate steps, and doing something like $S[b_{73}b_{71}b_{72}b_{74}]$ simply re-arranges the permutation step to come before the application of the S-Box, rather than after it, and the S-Box would still be applied on 4 contiguous bits in parallel.

Question 3

What if the round counters were not in the order 1,2,…,311,2,…,31? What if the round counters were any order of 1−311−31? Again, would this make it weaker, stronger or no different?

The reason they are in this order is for performance. If you examine the assembly instructions, using the round counter this way is the cheapest way to implement the operation. Using a permuted order of values 1-31 would require additional MOV/ADD operations. You want to minimize MOVs when designing a fast permutation.

The job of the counter is to ensure each round is different. So long as it is unique for each round, it does not matter so much what the actual literal value is, and so you may as well simply use the most efficient sequence available.

$\endgroup$
  • 1
    $\begingroup$ That was an incredible answer. If only I could offer 'two' ticks. $\endgroup$ – Red Book 1 Feb 20 '18 at 15:56

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.