Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22
Niels Möller (nisse@lysator.liu.se)
21 Oct 1998 01:18:36 +0200
[ Commenting an old message ]
Berke Durak <berke@gsu.linux.org.tr> writes:
> On Fri, 7 Aug 1998, Bob Baldwin wrote:
>
> > I assume that Berke's message about using RC6
> > as a strong PRNG was to take advantage of the wide
> > block size. That is, RC6 would be used as a stream
> > cipher such as counter mode with the PRNG state
> > being the secret key and counter value, and perhaps
> > the increment value is secret too.
> [...]
>
> Thanks to Bob Baldwim for his comment: after reflexion, I noticed that I
> made a dangerous mistake while using RC6 as a PRNG. I used the following
> scheme
>
> 1.key RC6 with a 128-bit (strong) seed
> 2.let B_0 be a null 128-bit RC6 data block; let i be 0 initially
> 3.B_{i+1} = E(B_i) (where E is RC6 with the mentioned key)
> 4.output B_{i+1} for the pseudorandom stream
> 5.goto 3
>
> Nothing guarantees that this algorythm will not fall in a short (i.e. with a
> period less than 2^128 iterations) cycle, since the best we know about RC6
> is that it acts as a random permutation (as every block cipher is supposed
> to be) (knowing better would prove that RC6 has some weaknesses, wouldn't it
> ?)
[ ... ]
> Does someone know
> 1.A more elegant f function (for C implementation)
> or 2.A different operation mode for using a block cipher
> as a maximum-length PRNG ?
In the eurocrypt-98 rump session, Adi Shamir proposed the following
construction:
Given some pseudorandom function F (iirc, Shamir used a hash function,
but the same should apply to a block cipher with a fixed (secret)
key), construct a sequence by iterating
x_0 = some secret seed value
x_{i+1} = F(x_i) + i (where + is addition or bitwise xor).
This simple construction guarantees that there are no short cycles,
because if i != j, then x_i = x_j implies x_{i+1} != x_{j+1}. The
sequence can't repeat until the counter wraps around.
I like this construction because of its simplicity; it seems likely
that good cryptographic properties of F carry over to the sequence
x_i.
Disclaimer: I'm not a cryptanalysist, and I can't say that the
construction is secure. If anyone has pointers to any serious analysis
of it, I'd like to know.
/Niels
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22