From: Maaartin on 22 Jun 2010 08:23 On Jun 22, 1:12 pm, Francois Grieu <fgr...(a)gmail.com> wrote: > Yes, 4 rounds of Feistel cipher is fine if the number of bits is > sufficiently low that an adversary can not exhaust the plain/ciphertext > space, which is the case in practice for 108 bits. That's the > Luby-Rackoff construction. You mean "sufficiently high", right? > On the other hand, to take an extreme example, with 2 bits, knowing 2 > (plaintext,ciphertext) pairs for a Feistel cipher is enough to deduce > the other 2 pairs, when a perfect cipher would require 3 known pairs to > deduce the last one. Confirmed. It looks like 5 rounds Feistel can produce all 24 bijections. How is it for more bits?
From: Scott Fluhrer on 22 Jun 2010 08:34 "Francois Grieu" <fgrieu(a)gmail.com> wrote in message news:4c209a88$0$16872$426a74cc(a)news.free.fr... > > On the other hand, to take an extreme example, with 2 bits, knowing 2 > (plaintext,ciphertext) pairs for a Feistel cipher is enough to deduce > the other 2 pairs, when a perfect cipher would require 3 known pairs to > deduce the last one. Nit: Feistel networks always implement even permutations... except for the minimal 2 bit case, where they can implement an arbitrary permutation. This fact is somewhat obscure (who really cares about a 2 bit Feistel network), but it is still true. In particular, with a 2 bit Feistel network: - A single round with H(0)==H(1) implements an odd permutation - A single round with H(0)!=H(1) implements an even permutation -- poncho
From: Francois Grieu on 22 Jun 2010 09:09 On 22/06/2010 14:34, Scott Fluhrer wrote: > "Francois Grieu" <fgrieu(a)gmail.com> wrote in message > news:4c209a88$0$16872$426a74cc(a)news.free.fr... >> >> On the other hand, to take an extreme example, with 2 bits, knowing 2 >> (plaintext,ciphertext) pairs for a Feistel cipher is enough to deduce >> the other 2 pairs, when a perfect cipher would require 3 known pairs to >> deduce the last one. > > Nit: Feistel networks always implement even permutations... except for the > minimal 2 bit case, where they can implement an arbitrary permutation. This > fact is somewhat obscure (who really cares about a 2 bit Feistel network), > but it is still true. > > In particular, with a 2 bit Feistel network: > - A single round with H(0)==H(1) implements an odd permutation > - A single round with H(0)!=H(1) implements an even permutation I did not know this exception; I stand corrected and should have written With 4 bits, knowing 14 (plaintext,ciphertext) pairs for a Feistel cipher is enough to deduce the other 2 pairs, when a perfect cipher would require 15 known pairs to deduce the last one. [3 bits is left as an exercise to the reader / for me later] And, as noted by Maaartin 4 rounds of Feistel cipher is fine if the number of bits is sufficiently *high* that an adversary can not exhaust the plain/ciphertext space. Francois Grieu
From: biject on 22 Jun 2010 09:33 On Jun 22, 12:40 am, Ross MacGregor <ross__macgre...(a)hotmail.com> wrote: > Is there a symmetric block encryption algorithm that can > encrypt a 108 bit buffer using a key and output a 108 bit > buffer? > > I'd like to feed it a sequential range of numbers > (1001,1002,1003,1004...) and have the algorithm generate for > me a pseudo-random sequence of numbers that are guaranteed > to be unique. This is why it is important that I only encode > the 108 bits of data as this is the size of the random > number I need to generate. > > I've been searching for days for a bit level encryption > algorithm but everything seems to be based on byte sized > buffers. The OTP where you use a different key for each block would be super easy to code where you do an XOR of each bit with the key. Why make it complicated? David A. Scott -- My Crypto code http://bijective.dogma.net/crypto/scott19u.zip http://www.jim.com/jamesd/Kong/scott19u.zip old version My Compression code http://bijective.dogma.net/ **TO EMAIL ME drop the roman "five" ** Disclaimer:I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged. As a famous person once said "any cryptograhic system is only as strong as its weakest link"
From: Francois Grieu on 22 Jun 2010 09:51
I wrote > [3 bits is left as an exercise to the reader / for me later] Solved: a 3-bit (unbalanced) Feistel cipher has the potential to generate all (2^3)! permutations. More generally, unless I err, an unbalanced Feistel cipher can generate odd permutations when one of the stage is such that a single bit of the block is XOR-ed width an appropriate key-dependent one-bit function of all the other bits. That can be useful when one needs a cipher with small block size: start with b0 := b0 XOR (AND(other_bits) AND hash(key)) then proceed with an appropriately long Luby-Rackoff construction. Thanks to Scott Fluhrer for his interesting "nit"! Francois Grieu |