[18183] in cryptography@c2.net mail archive
Re: Number of rounds needed for perfect Feistel?
daemon@ATHENA.MIT.EDU (Greg Rose)
Sun Aug 14 21:55:06 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Fri, 12 Aug 2005 13:42:08 -0700
To: tim@dierks.org
From: Greg Rose <ggr@qualcomm.com>
Cc: cryptography@metzdowd.com
In-Reply-To: <23090.38.119.128.203.1123861646.squirrel@webmail2.pair.com
>
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@metzdowd.com
