Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57
John Kelsey (kelsey@plnet.net)
Mon, 10 Aug 1998 02:06:11 -0500
-----BEGIN PGP SIGNED MESSAGE-----
[ To: CodherPlunks ## Date: 08/09/98 ##
Subject: Re: Strong PRNG with AES or 3-DES ]
>Date: Sat, 8 Aug 1998 12:01:55 +0300 (EEST)
>From: Berke Durak <berke@gsu.linux.org.tr>
>To: CodherPlunks@toad.com
>Subject: Re: Strong PRNG with AES or 3-DES
>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 ?)
This is just running your block cipher in full-block
OFB-mode. You don't get a guarantee of cycle length, but
assuming the block cipher acts like a random permutation,
your expected cycle length is 2^{127} blocks. (If it acted
like a random function, you'd expect a cycle length of
about 2^{64}).
To see why this is so, consider running your block cipher in
OFB-mode from an all-zero starting block. In general, you
have X_{i+1} = E_K(X_i). Now, for each X_{i+1}, there is
exactly one X_i. That is, there can be only one plaintext
block that encrypts to any given ciphertext block. Now,
think about a sequence of outputs
X_0, X_1, X_2, ..., X_{n-1}, X_n.
What's the probability that the next value, E_K(X_n} = X_2?
The probability is zero; it can't possibly happen, because
only X_1 encrypts to X_2. The only value in the sequence
that can possibly occur by encrypting X_n is X_0. If we
started from an all-zero block, then the only way we get a
short cycle is to have a block encrypt to the all-zero
block. The probability of this happening for each X_i is
2^{-128}. We expect to hit this after about 2^{127} blocks.
What's the probability that you will have cycled by your Nth
block? It's about N * 2^{-128}. For any cycle length you
care about in this application, OFB-mode is just fine.
Note that if you didn't feed back the full block, or if you
used a random function instead of a random permutation, then
you would get an expected cycle length of about 2^{64}
blocks. That's true because in that case, X_{n+1} can
legitimately be X_0,X_1,...,X_n. Saying there is a cycle
somewhere in the first N blocks of output is the same thing
as saying there is a collision in the first N blocks of
output, so you're susceptible to the birthday paradox.
I should comment that three or four years ago, someone on
sci.crypt explained this to me. So I guess I am passing it
on, hopefully without adding my own errors.
>Anyway, I'm considering using the following scheme:
>
> 1.key RC6 with a 128-bit strong seed
> 2.let A,B,C,D be the 32-bit blocks, with (A,B,C,D)
> forming the 128-bit RC6 block.
> set A,B,C,D initially to zero.
> 3.output E(A,B,C,D) for the pseudorandom stream
> 4.(A,B,C,D) <- f(A,B,C,D)
> where f is a function such that
> for all (A,B,C,D),
> card { f^i(A,B,C,D) | i in |N } = 2^128.
> 5.goto step 3
>
>The simplest f function that comes to mind is
>incrementation.
This will work just fine if the block cipher is any good.
Note that there is another theoretical flaw in this
generator, as well as your previously-proposed one. As the
number of outputs gets much larger than 2^{64}, it becomes
easier and easier to distinguish your PRNG's outputs from a
real random output sequence, since you never get 128-bit
collisions. This is of no importance whatever for a
real-world PRNG application, but it does exist.
You can simplify your carry-bit processing by doing
something like
D++;
if(D==0){
C++;
if(C==0){
B++;
if(B==0)
A++;
}
}
This really should be quite strong, as long as the key is
randomly selected and the block cipher is strong. After
all, we would expect a strong block cipher to be able to
allow huge numbers of chosen plaintexts without being
broken.
>Berke Durak - berke@gsu.linux.org.tr -
http://gsu.linux.org.tr/kripto-tr/
>PGP bits/keyID: 2047/F203A409 fingerprint:
44780515D0DC5FF1:BBE6C2EE0D1F56A1
- --John Kelsey, kelsey@counterpane.com / kelsey@plnet.net
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBNc6cyCZv+/Ry/LrBAQElfgQAsZ2nuC0yHdPcKttBxBAxOLZr1eftVdji
GXCRHmR2jjsE/LJErmsbBgQ6LTVkkEvbwLXQdNXvt3MEEyV0/wJQwwD9t3Ck7bj6
FQ0qOLXoQt0qsixXrl6W3vEvmUucnS14SLFEnALwJGUUpr0S5ymywoR7+kgtSQj2
c+A+wjLrYOE=
=S7VP
-----END PGP SIGNATURE-----
--John Kelsey, kelsey@counterpane.com / kelsey@plnet.net
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57