Active sboxes
in [Cryptography]
|
Prev: Bear Bottoms Lectures On Encryption !!!
Next: Enormous speed difference between C and ASM implementations of crypto algorithm
From: Maaartin on 7 Mar 2010 00:06 In http://groups.google.com/group/sci.crypt/browse_thread/thread/c6a1fc25594b4680 I asked questions about sboxes and got some answers... now I'd like to ask more (for whatever reason I can't continue the old thread). On Sep 24 2009, 11:55 am, Tom St Denis <t...(a)iahu.ca> wrote: > You look at a cipher like DES and off the top of your head you can't > really figure out what the branch is. IIRC from the Biham et al. > differential analysis it's 3. That means over any 2R differential > there is at least 3 sboxes active [iirc 6 for 4R and so on]. Same > thing with a lot of ciphers, like Twofish. I consider Twofish to be > very likely secure, but by that same token I have yet to see a proof > of a minimal 2R branch. In the case of AES it's very easy to prove > its 5 for 2R and 25 for 4R. For two rounds it's obvious, since MixColumns is MDS. For four rounds I would go through all possible cases, e.g., let's assume there's only 1 active sbox in the first round, this leads to 4 active sboxes in the second round which get isolated by ShiftRows, so after MixColumns the whole matrix is active (16 boxes). In the next round there may be some cancellations but in each column there remains at least one active box, so we have again 4 boxes. Together it makes 1+4+16+4 = 25. After a bit of thinking the other cases could be checked, so I'm conviced that 25 is a valid lower bound. But isn't there an easier and more systematic way?
From: J.D. on 7 Mar 2010 00:21 On Mar 7, 12:06 am, Maaartin <grajc...(a)seznam.cz> wrote: > Inhttp://groups.google.com/group/sci.crypt/browse_thread/thread/c6a1fc2.... > I asked questions about sboxes and got some answers... now I'd like to > ask more (for whatever reason I can't continue the old thread). > > On Sep 24 2009, 11:55 am, Tom St Denis <t...(a)iahu.ca> wrote: > > > You look at a cipher like DES and off the top of your head you can't > > really figure out what the branch is. IIRC from the Biham et al. > > differential analysis it's 3. That means over any 2R differential > > there is at least 3 sboxes active [iirc 6 for 4R and so on]. Same > > thing with a lot of ciphers, like Twofish. I consider Twofish to be > > very likely secure, but by that same token I have yet to see a proof > > of a minimal 2R branch. In the case of AES it's very easy to prove > > its 5 for 2R and 25 for 4R. > > For two rounds it's obvious, since MixColumns is MDS. For four rounds > I would go through all possible cases, e.g., let's assume there's only > 1 active sbox in the first round, this leads to 4 active sboxes in the > second round which get isolated by ShiftRows, so after MixColumns the > whole matrix is active (16 boxes). In the next round there may be some > cancellations but in each column there remains at least one active > box, so we have again 4 boxes. Together it makes 1+4+16+4 = 25. After > a bit of thinking the other cases could be checked, so I'm conviced > that 25 is a valid lower bound. But isn't there an easier and more > systematic way? Yes, there is a proof in the Rijndael paper that was submitted to the AES process (from page 33 to 35): http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.640
From: J.D. on 7 Mar 2010 00:32
On Mar 7, 12:06 am, Maaartin <grajc...(a)seznam.cz> wrote: > Inhttp://groups.google.com/group/sci.crypt/browse_thread/thread/c6a1fc2.... > I asked questions about sboxes and got some answers... now I'd like to > ask more (for whatever reason I can't continue the old thread). > > On Sep 24 2009, 11:55 am, Tom St Denis <t...(a)iahu.ca> wrote: > > > You look at a cipher like DES and off the top of your head you can't > > really figure out what the branch is. IIRC from the Biham et al. > > differential analysis it's 3. That means over any 2R differential > > there is at least 3 sboxes active [iirc 6 for 4R and so on]. Same > > thing with a lot of ciphers, like Twofish. I consider Twofish to be > > very likely secure, but by that same token I have yet to see a proof > > of a minimal 2R branch. In the case of AES it's very easy to prove > > its 5 for 2R and 25 for 4R. > > For two rounds it's obvious, since MixColumns is MDS. For four rounds > I would go through all possible cases, e.g., let's assume there's only > 1 active sbox in the first round, this leads to 4 active sboxes in the > second round which get isolated by ShiftRows, so after MixColumns the > whole matrix is active (16 boxes). In the next round there may be some > cancellations but in each column there remains at least one active > box, so we have again 4 boxes. Together it makes 1+4+16+4 = 25. After > a bit of thinking the other cases could be checked, so I'm conviced > that 25 is a valid lower bound. But isn't there an easier and more > systematic way? The short and sweet of it is that the number of active s-boxes over 2 rounds is lower bounded by 5C, where C is the number of active columns (columns with at least one active s-box in them). Also, the number of active columns over two rounds is at least 5. So, if you start with one active column then over the first pair of rounds you will have at minimum 5 active s-boxes, and by the end of the first two rounds you will have 5-1 = 4 active columns. Over the next pair of rounds this means 4 active columns * 5 = 20 active s-boxes. The result is 25 s- boxes at minimum over 4 rounds. |