If the permutation is not well thought out, how will this effect the cipher's avalanche effect. For example, if the permutation in PRESENT was in some way different (just made up without any thought) would this adversely affect the avalanche effect? How else might a poorly designed permutation adversely affect PRESENT or other block ciphers?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Related: crypto.stackexchange.com/a/18462/12164 $\endgroup$– e-sushiSep 20, 2017 at 16:49
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
The avalanche effect is the property of a cryptographic primitive, whereby flipping a single input bit causes (on average) 50% of all of the output bits to flip. This can be simply accomplished by an S box. For the avalanche effect to occur, a simple randomly generated S box is all that is required. However for security purposes, a much cleverer design is used.
The problem is that once the primitive's block width exceeds 8 bits it becomes resource intensive to store S boxes that large. They then need to be split up and replicated. PRESENT accomplishes this by having 16 ${\times}$ 4-bit S boxes.
The permutation layer simply glues the S boxes together. They therefore act as a single 64 bit wide S box. This construction is not as computationally efficient as a single box and requires iterative processing to achieve the same effect. Full avalanche effect is typically attained after 2 to 3 rounds of computation (see later).
A poor permutation arrangement might mean that the number of rounds to attain avalanche is increased. In the worst case scenario, whole S boxes might become isolated and ineffective leading to sticky bits in the output. This should be pretty improbable however as I can't foresee such a bad architecture finding it's way into the wild. The 31 rounds in PRESENT should still comfortably achieve full avalanche effect even with a slightly flawed permutation. Excess rounds have been used previously in functions like Skein to overcome algorithmic simplicity or deficiency.
There is an analysis with respect to security implications of what actually might be a permutation problem inside PRESENT:- http://juankenny.blogspot.ch/2012/10/sc-block-ciphers-present.html. I can only comment on avalanche effect though...
answered Sep 20, 2017 at 22:18
-
$\begingroup$ Looking at your reference, it seems that each round of PRESENT would benefit from having distinct permutations, or at least some of them should be different. Would doing that make PRESENT resistant to the Statistical Saturation Attack? If it did, might it then be possible for PRESENT to have fewer rounds and still maintain its security? $\endgroup$ Sep 21, 2017 at 9:16
-
$\begingroup$ @RedBook1 I think that it would be against the spirit of PRESENT to have multiple unique permutations. It's a cipher with minimum footprint. You'd just have to increase the memory footprint. $\endgroup$ Sep 21, 2017 at 20:37
-
$\begingroup$ I understand it may go against the "spirit" of PRESENT, but that apart would changing some permutations offer protection against the Statistical Saturation Attack? And if so, would that allow for fewer rounds? $\endgroup$ Sep 22, 2017 at 3:56
-
$\begingroup$ @RedBook1 it is my personal opinion that the incorporation of programmatic entropy must improve the security of a primitive, and it would certainly appear to be beneficial in this case. However cryptographic analysis is not my forte. This might form a good new question. $\endgroup$ Sep 22, 2017 at 8:37
-
$\begingroup$ This is the new question: crypto.stackexchange.com/questions/51721/… $\endgroup$ Sep 22, 2017 at 11:28
$\begingroup$
$\endgroup$
Permutation layer diffuses the small changes globally(tries to spread over the complete block).
If permutation is not well thought out, then diffusion may be weak and changes may not spread throughout the complete block. The cipher output may be treated as concatenation of output from multiple identical ciphers with smaller block length. For Example
Consider there is no Shift-Rows operation in AES, then Change in a state will stay in a Column and will not diffuse to other columns. Thus Ciphertext can be treated as output of 4 independent 32 bit block ciphers.
In Case of PRESENT, if the permutation P was not spread over the complete block(64 bits, keeping the change within small set of bits), or there was a chunk of bits which does not get effected by change in other bits over multiple rounds, the cipher will have a major weakness.
