Number of rounds needed for perfect Feistel?

[Hal Finney]

Tim Dierks writes:
> 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.

Tim - Sounds like you probably want the Luby-Rackoff construction.
I couldn't find the paper online but here is an article about it,
http://everything2.com/index.pl?node_id=1499050.  Basically the answer
is that it takes four rounds for maximum security.

You might also want to look at Naor-Reingold,
http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/lr_abs.html, which replaces
two of the rounds with permutations that have weaker requirements.  There
has been quite a bit of other work that aims to speed up or simplify LR.

As far as the security of using 34 bit blocks, I think as long as you
use a decent cipher mode and stay well below the birthday bound of 2^17
blocks encrypted per key, you can be OK with it.

One thing about using AES, it is probably overkill as the round function;
for one thing, reversibility is not needed there.  If speed is not
much of an issue and you've got AES lying around, go ahead and use it,
otherwise you might look for an older 64-bit cipher or a fast hash
function, maybe even MD5.  AES is reasonably fast though.

Hal Finney

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