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
Marcus Watts (mdw@umich.edu)
Wed, 21 Oct 1998 15:05:52 -0400
Writes nisse@lysator.liu.se (Niels =?ISO-8859-1?Q?M=F6ller?=):
> 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
>
>
If F(x) is a block cipher instead of a one-way hash, then it's
no longer truely a one-way function. That means it's vulnerable
to a state compromise attack. If the attacker can gain access to
the internal state he can walk backwards through the function to
find previous numbers.
(where E(x,y) means to encrypt y using the key x,
D(x,y) means to decrypt y using the key x, and
^ means xor.)
if x_{i+1} = E(k,x_{i}) ^ i
then x_{i-1} = D(k,x_{i}^(i-1))
Granted, it may be hard for mallet to steal k, but if he can,
the gig is up. Ways mallet might use include finding a core
fump made by an errant application in some publically accessible place,
or walking in with machine guns and seizing the machine.
I believe a better (but much slower) way to do this would be to use
x_0, n_0 = secrets.
x_{i+1} = E(x_{i},n_{i}); n_{i+1} = n_{i}+1
Just for fun, here's a timing comparison of RC6, rijndael, and (not
AES) rc4. With these algorithms, at least, setkey is at least somewhat
slower, but not horribly so (I believe with some of the other AES
submissions this is not so.)
128 bit key and block; all timings in microseconds per operation;
sk=set key (for encryption); sk-1=set key (for decryption).
rs/6k = IBM RS/6000 530H, AIX 3.2.5, xlc 1.3.0.41
ultra-5 = Sun Ultra-5, Solaris 2.6, gcc 2.7.2
486 = Dell 450M (50Mhz???), openbsd 2.3, gcc 2.8.1
rs/6k ultra-5 486
rijndael,C encrypt,block 25 3.8 33
rijndael,C decrypt,block 24 3.6 32
rijndael,C sk 46 5.7 73
rijndael,C sk-1 70 9.2 108
[ with rijndael, using a key for decryption
requires an additional 24 microseconds of work. ]
[ assembler "should" be much faster. ]
rc6,C encrypt,block 24.6 4.66 65.2
rc6,C decrypt,block 25.3 4.96 67.8
rc6,C sk 89.4 12.2 193
rc6,as encrypt,block 18.5 - 48.5
rc6,as decrypt,block 20.2 - 48.2
rc6,as sk 73.1 - 101
C = version based on Salvo Salasio's versoin.
as = hand optimized assembler version
rs/6k ultra-5 486
rc4,as encrypt,block 8.2 .977 10.4
rc4,as sk 96 12.5 123
rc4,C encrypt,block 9.8 1.63 17.3
rc4,C sk 97 9.85 212
as=hand optimized assembler
C=EAY's version.
(again, block = 16 bytes, using 128 byte key.)
-Marcus Watts
UM ITD PD&D Umich Systems Group
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22