[1097] in Kerberos_V5_Development
Re: Common random routines: for review
daemon@ATHENA.MIT.EDU (Richard Basch)
Fri May 3 11:25:57 1996
Date: Fri, 3 May 1996 11:22:19 -0400
To: Bill Sommerfeld <sommerfeld@orchard.medford.ma.us>
Cc: "Richard Basch" <basch@lehman.com>, krbdev@MIT.EDU
In-Reply-To: <199605031416.OAA00653@orchard.medford.ma.us>
From: "Richard Basch" <basch@lehman.com>
On Fri, 3-May-1996, "Bill Sommerfeld" wrote to "Richard Basch, krbdev@mit.edu" saying:
> -----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.
You are correct... An active attack of the KDC would then give you
random keys, which you can build a codebook from by simply knowing the
first cblock is the plaintext for the second cblock.
A wrapped cbc chaining, as I previously suggested would eliminate this
attack. The des case would also be slightly improved by this, but not
as dramatically as the 3des case.
> 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..
I am not sure how you got those values. However, if you know the
sequence numbers, it is probably reduced by 2**8 (or thereabouts).
I think the strength of the 3des codebook was actually more like 2**53,
not 2**105 (somehow I managed to double the exponent; I was tired when I
wrote the message and didn't think about it too much).
> 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
I am not sure I understood your reasoning here... I think the only thing
you managed to get from the sequencing as it was is a codebook with
mapping the "cleartext" first cblock into the "ciphertext" second
cblock, and again between the cleartext second cblock to the ciphertext
third cblock. It was certainly a rapid codebook generator in the
previous proposal. However, I don't think it revealed anything about
the actual key.
> 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.
If you can elaborate on this, I would be interested.
For now, I have applied the quick double cbc encrypt fix in my tree.
. . .
> 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..
The problem that you are describing about building up multiple sets of
3des keys is probably better accomplished by building up a random PAD
that is XORed with the entire message before the CBC encryption. I
don't think much is gained by using additional keys if there is no
mapping between plaintext and ciphertext. Also, I don't know think the
PAD is actually necessary with the double cbc fix. The problem now
becomes developing another set of functions to develop the PAD or extra
keys, or whatever, that is mathematically unrelated to the generation of
the encryption key. If there is some mathematical relationship that we
overlook, we may be weakening the entire mechanism.
--
Richard Basch
Sr. Developer/Analyst URL: http://web.mit.edu/basch/www/home.html
Lehman Brothers, Inc. Email: basch@lehman.com, basch@mit.edu
101 Hudson St., 33rd Floor Fax: +1-201-524-5828
Jersey City, NJ 07302-3988 Voice: +1-201-524-5049
