Number of rounds needed for perfect Feistel?

Greg Rose ggr at qualcomm.com
Fri Aug 12 16:42:08 EDT 2005


At 11:47 2005-08-12 -0400, Tim Dierks wrote:
>I'm attempting to design a block cipher with an "odd" block size (34
>bits). I'm planning to use a balanced Feistel structure with AES as the
>function f(), padding the 17-bit input blocks to 128 bits with a pad
>dependent on the round number, encrypting with a key, and extracting the
>low 17 bits as the output of f().
>
>If I use this structure, how many rounds do I need to use to be secure (or
>can this structure be secure at all, aside from the obvious insecurity
>issues of the small block size itself)? I've been told that a small number
>of rounds is insecure (despite the fact that f() can be regarded as
>"perfect") due to collisions in the output of f(). However, I don't
>understand this attack precisely, so a reference would be appreciated.

Here's my understanding, but it's from my memory, so don't take it 
too seriously.

First, Luby-Rackov gives you a lower bound of four rounds. Note, 
though, that the random functions you need must be independent of 
each other, so you'll need to put something into AES that is 
dependent on the round number to ensure this (and it avoids slide 
atttacks too). Secondly, the security bound is only 2^(N/4), because 
you're fighting the birthday paradox on collisions in half-blocks.

Then a couple of years ago, at crypto, there was a paper that showed 
that 6 rounds was as secure as it gets in the non-chosen-text model, 
and 7 rounds is secure enough even with adaptive chosen-text attacks: 
see Luby-Rackoff: 7 Rounds are Enough for 2^n(1-epsilon) Security
Jacques Patarin , crypto 2003. You still need the round functions to 
be different.

Hope that helps.
Greg. 


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list