If the permutation in AES (or other ciphers) were randomly generated or dependent on the key, would it not be stronger against differential attacks?
If this is so, then might we need fewer rounds for the same level of security?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ "in AES" ?? AES itself is a keyed permutation, what exactly are you attempting to describe? $\endgroup$– Richie FrameApr 12, 2016 at 9:28
-
$\begingroup$ In AES, the shift row layer is a permutation; B0,B1,B2,...B15 becomes B0, B5, B10...B11. Would AES not be stronger against differential attacks if this perm were random? $\endgroup$– Red Book 1Apr 12, 2016 at 10:57
-
1$\begingroup$ How would you decrypt it? $\endgroup$– OrangeDogApr 12, 2016 at 14:52
-
$\begingroup$ For instance, the random permutation might be key-dependent, then both sender/receiver could decrypt the message. No matter, I was more interested in the 'if the perm in AES were random' rather than 'how'. $\endgroup$– Red Book 1Apr 13, 2016 at 10:02
-
$\begingroup$ The problem with just a key dependency is that the permutation is invariant to the input, and thus still susceptible to differential cryptanalysis (same key, different inputs). And obviously you can't use the full plaintext during decryption. However, you could permute the permutation using the decrypted input so far. This is conceptually comparable to CBC mode. $\endgroup$– MSaltersApr 13, 2016 at 10:55
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
You have clarified the question as asking about whether replacing ShiftRows with a random byte permutation would strengthen AES against differential attacks. It would not.
ShiftRows and MixColumns were carefully selected to work in tandem, such that every byte affects every other byte in the state within just two rounds. MixColumns ensures that every column of four bytes has a minimum of five differentially active bytes before and after that step (i.e. if you add the differentially active bytes in the column before MixColumns to the active bytes in the column after MixColumns, the number is at least 5). ShiftRows ensures that every column after the step includes a byte from every column before the step.
Together, the two steps operate to put a high lower bound on the number of differentially active s-boxes over 4 rounds: the AES creators proved that a minimum of 25 s-boxes are active over 4 rounds, minimizing the probability of any differential characteristic/trail.
There are alternatives to ShiftRows that do the same thing (see e.g. the cipher SQUARE which swaps columns and rows). But a random byte permutation would likely not ensure such a high minimum number of active s-boxes over as few rounds as ShiftRows.
$\begingroup$
$\endgroup$
6
I assume that you mean the S-box. The answer is NO! Randomly chosen S-boxes are not good choices for differential and linear cryptanalysis. When Biham and Shamir presented differential attacks on DES, one of the things that they showed was that if you replace the S-boxes in DES with randomly chosen ones, then the differential attack becomes much more devastating. You have to plan your S-box so that it's resilient to these attacks.
answered Apr 12, 2016 at 9:40
-
2
-
1$\begingroup$ There is another problem in randomly choosing an S-box for a standardized cipher. How do you prove that it was randomly chosen? If the S-box is not fixed but somehow generated from the key, then the analysis changes. $\endgroup$– kasperdApr 12, 2016 at 15:52
-
$\begingroup$ @kasperd by using legacy hard-copy random number books, or the digits of pi, or other tracable sources of entropy. $\endgroup$– JDługoszApr 12, 2016 at 19:53
-
1$\begingroup$ Wasn't there also some discussion of that the original IBM-selected DES S-boxes were vulnerable to differential cryptanalysis, but the revised ones weren't? (If this is better asked as a separate question, ping me and I'll post it...) $\endgroup$– userApr 12, 2016 at 21:26
-
1$\begingroup$ @MichaelKjörling crypto.stackexchange.com/q/16/13713 $\endgroup$– kasperdApr 13, 2016 at 7:13
$\begingroup$
$\endgroup$
1
I made a toy cipher that functioned in this manner. It had a bytewise transposition step that was performed by an invertible randomized permutation, similar to the Fisher-Yates shuffle, but easily invertible. Key material was used to select the next "random" index to shuffle, so as to enable decryption. At first, I really liked the idea, figuring that cracking the cipher would be much more complex if the order bytes are encrypted in is secret and changes regularly.
The biggest problem with this approach, in my opinion, isn't really related to resistance against standard cryptanalysis. A far bigger, more fundamental problem is that shuffling an array based on secret data appears to be weak against timing attacks. I qualify this as a larger problem because, even if the cipher algorithm were secure, implementations of it probably won't be.
The bottom line for me was to remember that tables and secret data do not mix. While shiftRows is what it is in AES for specific reasons (synergy with mixColumns), I would not recommend randomized byte transposition be employed in any new ciphers, even those which have adequate diffusion otherwise. Primitive designers should attempt to use only components which function in constant time and expose a minimum of side channels.
$\begingroup$
$\endgroup$
One point which was not yet mentioned is the easiness of analysis. Making parts of the cipher (the S-box or the linear layer) key-dependent might increase the security -- but we do not know how to prove this. It actually makes the analysis of the design, and thus our primary resource of building trust in the design, much harder.
For the ease of analysis, a very simple, yet secure, design is much more preferable then some obscure, hard to understand, design. Thus, one primary goal of the design should be to be as simple as possible, to allow a thorough analysis and understanding the behaviour of the design as much as possible.
In this regard, the AES is actually a very good design, because we know some very nice (and quite simple) arguments, to reason about its security (e.g. properties of its S-box, the wide-trail strategy and the superbox argument to prove resistance against differential and linear cryptanalysis).
