[1096] in Kerberos_V5_Development
Re: Common random routines: for review
daemon@ATHENA.MIT.EDU (Bill Sommerfeld)
Fri May 3 10:34:07 1996
To: "Richard Basch" <basch@lehman.com>
Cc: krbdev@MIT.EDU
In-Reply-To: Your message of "Fri, 3 May 1996 00:25:10 -0400 ."
<199605030425.AAA19055@badger.lehman.com>
Date: Fri, 03 May 1996 10:16:07 -0400
From: Bill Sommerfeld <sommerfeld@orchard.medford.ma.us>
-----BEGIN PGP SIGNED MESSAGE-----
> I actually thought of the fact that the last two des blocks are
> plaintext zeros, as you said, giving an attacker more plaintext-cipher
> pairs. However, as I recall, the theoretical attacks on 1-des require
> 2^40 such pairs, and 3-des requires about 2^105 of such sequences.
Give me 2^64 distinct cipher-plain pairs on a 64-bit block cipher like
3DES, and you don't need to give me the key, because you've just given
me a copy of the codebook.
This generator is still not stronger than 2**64; I think it's actually
more like (2**64/3) if you know the sequence number and (2**64)/2 if
you don't; it also allows occasional "flashes of insight" to an
attacker..
If *any* generated value from the sequence is of the form:
wwxxyyzz00000000 XXXXXXXXXXXXXXXX YYYYYYYYYYYYYYYY
then, an attacker will know for a fact that key zzyyxxww in the
sequence will start with:
XXXXXXXXXXXXXXXX YYYYYYYYYYYYYYYY
which reduces the search space for the rest of the key into tractable
territory. (to 2**56).
If we assume 3DES is a random function, any given output value has 1
chance in in 2**32 of looking like this.. each individual key we
generate has one chance in 2**32 of revealing all but 56 bits of
someone else's 3DES key.
If we assume that an attacker can consume 95% of the output of the RNG
(assume an on-line attack on the KDC, having it generate lots and lots
of 3des keys, in a lightly-loaded realm..) and is interested in the
other 5%, this becomes worrysome.
I haven't completely considered parity bits. I think they only make
the attack less probable by a factor of 2**12 -- but that doesn't give
me a whole lot of comfort.
> Theoretically if a service is up long enough to produce enough keys, the
> random number generator should probably be re-initialized periodically
> (hopefully with a true source of randomness). Also, even if the random
> sequence encryption key is broken, the seed key is not exposed.
Right, but with the current KDC technology, you've just leaked N weeks
worth of session keys, allowing the attacker to break past traffic..
> I could do the same thing I did with the string2key function, which is
> to do wrap-around cbc chaining, using the last cblock as the ivec for
> another cbc-encryption of the entire message... This change would
> increase the lifetime of a given random sequence by a little.
That might help a little; I think, however, that it would make more
sense to use 3 different 3DES keys (one for each block of output), and
start the sequence with a "random" value unknown to the attacker
instead of always starting with all zeros..
- Bill
-----BEGIN PGP SIGNATURE-----
Version: 2.6.1
iQCVAwUBMYoVJLT+rHlVUGpxAQHQsQP/Wa+zz01uBdb/QQzmpIPrMHIlO3eFgo8a
xWzjfgfHzOkr4JLMhE07BFHwdOpL4Zg0QaiXKuFUFx0capVfFL6TMx6k5P0nwP1w
nioktbFdsntJQkZRpb5BMTAIS6No0LEySBidvNN8XE7kyEbfMA3dAyMhqz3ZuAYm
lBD0c3Js128=
=aw9s
-----END PGP SIGNATURE-----
