Prev: Which Crypto League to bat in for Future.
Next: What's encoding?
From: Maaartin on 22 Jun 2010 11:36
On Jun 22, 3:51 pm, Francois Grieu <fgr...(a)gmail.com> wrote:
> 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.

IMHO, you're right. The permutation is odd, iff card({x: f(x)=1} is
odd.

> 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.

I don't know what you mean by AND(other_bits) AND hash(key). With
b1 & b2 & b3 ... & aBitDerivedFromTheKey
it could work. Anding all bits of the hash wouldn't be of much use as
it is nearly always 0. Taking an arbitrary bit would be better.

With "appropriately long Luby-Rackoff construction" do you mean 4 more
rounds? I don' think you could use less, since the above unbalanced
round adds nearly nothing to security.

What about this? Stay with balanced Feistel, denote the parts x and y,
compute hash(x) and split it into three parts h0, h1, and h2, where
length(h0)=1 and length(h1)=length(h2)=length(y). Compute

y ^= h0 || y!=0 && y!=h2 ? h1 : h2

This is the same like the standard operation (y ^= h1), except that it
with probability of 0.5 swaps 0 and h2. The probability of getting odd
permutation is slightly lower than 0.5, because of the possibility of
h2=0. However, it's more efficient than an additional round, as long
as the used hash is long enough.
From: Greg Rose on 22 Jun 2010 12:10
In article <aVYTn.25269$Xp4.22045(a)newsfe23.iad>,
Ross MacGregor <ross__macgregor(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.

Reading between the lines above, it seems to me
that what you are asking for is a PRG
(pseudo-random generator) that can take a key and
a short nonce and generate some number of
random-looking bits. Funnily enough, this is the
accepted interface for stream ciphers these days.
So you might want to look at the results of
EStream, for a bunch of efficient and tested
ciphers.

Greg.
--
From: Francois Grieu on 22 Jun 2010 12:44
On 22/06/2010 17:36, Maaartin wrote:
> On Jun 22, 3:51 pm, Francois Grieu <fgr...(a)gmail.com> wrote:
>> 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.
>
> IMHO, you're right. The permutation is odd, iff card({x: f(x)=1} is
> odd.
>
>> 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.
>
> I don't know what you mean by AND(other_bits) AND hash(key). With
> b1 & b2 & b3 ... & aBitDerivedFromTheKey
> it could work. Anding all bits of the hash wouldn't be of much use as
> it is nearly always 0. Taking an arbitrary bit would be better.

Sorry it was not clear; I'm thinking of hash(key) as a single bit
pseudo-randomly dependant on all bits of the key, your
aBitDerivedFromTheKey. This is to protect againt related-key attacks
(when using an arbitrary bit of the key, the permutation remains of
unchanged parity when other key bits change).

> With "appropriately long Luby-Rackoff construction" do you mean 4 more
> rounds? I don' think you could use less, since the above unbalanced
> round adds nearly nothing to security.

I'm thinking a bit *more* than 4 rounds when we are talking very small
blocks, because Luby-Rackoff leaves some permutations more likely than
others, I think appreciably for 4 rounds and up to 4 bits. I welcome a
quantitative evaluation of the number of rounds necessary for this
effect to fade away beyond observability.


Francois Grieu
From: Paul Rubin on 22 Jun 2010 14:29
Francois Grieu <fgrieu(a)gmail.com> writes:
> I'm thinking a bit *more* than 4 rounds when we are talking very small
> blocks, because Luby-Rackoff leaves some permutations more likely than
> others, I think appreciably for 4 rounds and up to 4 bits. I welcome a
> quantitative evaluation of the number of rounds necessary for this
> effect to fade away beyond observability.

There have been a couple threads about this in the past. I remember
doing some experiments on blocks up to 8 bits or something like that.
From: Maaartin on 22 Jun 2010 20:40
On Jun 22, 8:29 pm, Paul Rubin <no.em...(a)nospam.invalid> wrote:

> There have been a couple threads about this in the past.  I remember
> doing some experiments on blocks up to 8 bits or something like that.

How can it be done? With n bits, there are (2**n) ** (2**n)
functions, which for n=4 equals 2**64, and the number of permutation
is too high as well. I see no way how to find out if you can get them
all using e.g. 4 rounds plus a modification as I or Francois Grieu
proposed. I don't even know how to do any useful statistics. For n=3
it's easy to evaluate all possibilities, but for n=4 you need
something less trivial.

Interestingly, using Lai-Massey on 2 bits gives you only 4 functions
for any number of rounds greater than zero.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9 10 11 12
Prev: Which Crypto League to bat in for Future.
Next: What's encoding?