How to obtain inverse key stream efficiently on Present cipher?

Question

I was taking a look at the PRESENT lightweight cipher presented here. You can see an implementation of it in Python here. It is basically a Substitution-Permutation (SP) cipher with ultra-lightweight encryption and lightweight decryption.

The algorithm for encryption is the following :

generateRoundKeys()
for i = 1 to 31 do
    addRoundKey(state, k_i)
    sBoxLayer(state)
    pLayer(state)
end for
addRoundKey(state, k_32)

The algorithm for decryption is the following :

generateRoundKeys()
for i=32 to 2 do
    addRoundKey(state, k_i)
    pLayer_inv(state)
    sBoxLayer_inv(state)
end for
addRoundkey(state, k_1)

I have the following question, regarding the decryption process. Of course, given the master key, all the keystream (e.g. the 32 derived keys) can be generated, in either forward or inverse direction. In the case of encryption, the decryption can start without knowing all the keys of the key schedule, which to my knowledge isn't the case for the decryption process. However, in the case of a hardware implementation (which is what this cipher is designed for) I don't think it is efficient to generate all the keystream at first and save it to a ROM and then start the decryption. My questions are, am I missing something algorithmically wise, for how to start the decryption without obtaining all the inverse key schedule first? Is it theoretically safe if the key schedule is circular? For example if $k_1$=$k_{32}$, $k_2$=$k_{31}$, etc. would it require more rounds?

Answer 1

The PRESENT key schedule operates on a register the same length as the key size. The left most 64-bits are extracted as round keys and then the register updated by performing a 61-bit left rotation on the bits; passing the leftmost 4 or 8 bits through the S-box and XORing the round number onto some of the register bits. This key schedule is reversible and allows us to compute the previous round key from the current one by XORing the round number; passing the leftmost 4 or 8 bits through the S-box and then doing a 61-bit right rotation. Thus if one were to pass the final round key to the decryptor, they could run the reverse key schedule using this as a starting point.

The symmetric key schedule that you describe would be very dangerous indeed. Typically in block cipher analysis we make some initial assumption about some bits of round key for the first few or last few rounds. This exhaustive assumption allows us to test statistics on the inner rounds of the block cipher rather than all of the rounds (where the statistics are weaker). When the statistic is strong, we know that our initial assumption is likely to have been correct. Thus for example, one might exhaust over possible values of the first round key of PRESENT, test for a differential or linear statistic on the remaining 30 rounds and select the first round key that produces the strongest statistic. In your structured key schedule my assumption would let me recreate both the first and last rounds and so test for statistics on 29 rounds which would give a much stronger test.

It's also best not to think that such defects can be ameliorated simply by adding rounds. Cryptanalysis of block ciphers can take very close account of the key schedule and changing the key schedule can easily affect the security of the cipher or the worse.