Ticket History #1248: SAM uses RC4 insecurely

# Fri Nov 08 00:31:06 2002 hartmans (Sam Hartman) - Ticket created

To:	krb5-bugs@mit.edu
Cc:	kenh@mit.edu
Subject:	SAM uses RC4 insecurely
Date:	Fri, 8 Nov 2002 00:31:00 -0500 (EST)
From:	hartmans@MIT.EDU (Sam Hartman)

Download (untitled) / with headers
text/plain 910B

Hi. The definition of dr in src/lib/crypto/combine_keys.c mishandles
the rc4 enctype. In particular, It will encrypt the constant using
rc4 directly in the long-term key. No cipher state is used for rc4,
so the rc4 PRNG is always positioned at the same point in the cipher
stream.

effectively for rc4 dr(k, c) is c^rc4(k). That's problematic
because:

dr(k,c1)^dr(k, c2)
= c1^rc4(k)^rc4(k)^c2
= c1^c2

So if you know c1, c2 and dr(k,c1) you can find out the first few bits
of rc4(k).

I have not yet worked through the implications of this for
combine-keys, but it becomes clear to me that:

* dr must be defined per crypto-system

* The current dr for rc4 is unacceptable even if combine-keys end up
being secure

* If SAM is going to use dr, it must be required to be defined for
each crypto system.

If these problems are not fixed by the 1.3 release, the SAM changes
must be backed out.

# Fri Nov 08 00:33:44 2002 hartmans (Sam Hartman) - Data error added

# Fri Nov 08 00:35:02 2002 hartmans (Sam Hartman) - Cc <kenh@cmf.nrl.navy.mil> added

# Fri Nov 08 00:35:03 2002 hartmans (Sam Hartman) - Target_Version 1.3 added

# Fri Nov 08 00:39:01 2002 hartmans (Sam Hartman) - Ticket 1248 RefersTo ticket 1226.

# Mon Nov 11 23:47:47 2002 <kenh@cmf.nrl.navy.mil> - Ticket #1252: - Ticket created

To:	hartmans@MIT.EDU (Sam Hartman)
Cc:	krb5-bugs@MIT.EDU
Subject:	Re: SAM uses RC4 insecurely
Date:	Mon, 11 Nov 2002 23:47:40 -0500
From:	Ken Hornstein <kenh@cmf.nrl.navy.mil>

Download (untitled) / with headers
text/plain 654B

Show quoted text

>Hi. The definition of dr in src/lib/crypto/combine_keys.c mishandles
>the rc4 enctype. In particular, It will encrypt the constant using
>rc4 directly in the long-term key. No cipher state is used for rc4,
>so the rc4 PRNG is always positioned at the same point in the cipher
>stream.
>[...]

I think maybe I'm just jet-lagged, or perhaps I'm missing something
about RC4 (I know it's a stream cipher, but not the details). But
can you elaborate on this statement?

Show quoted text

>effectively for rc4 dr(k, c) is c^rc4(k).

Hm, I guess that after reading Brezak's draft, I see that there doesn't
seem to be a Derive-Key() for RC4 (not as I understand it).

--Ken

# Tue Nov 12 13:24:57 2002 hartmans (Sam Hartman) - Ticket #1253: - Ticket created

To:	Ken Hornstein <kenh@cmf.nrl.navy.mil>
Cc:	krb5-bugs@mit.edu
Subject:	Re: SAM uses RC4 insecurely
From:	Sam Hartman <hartmans@MIT.EDU>
Date:	Tue, 12 Nov 2002 13:24:50 -0500

Download (untitled) / with headers
text/plain 629B

Well, there is a derive-key for rc4, but it only takes keyusage as
input, not a string.

Defining dk interms of dr would work for rc4 if you had a reasonable
definition of dr, but you currently do not.

This is an issue both against the code and against your draft. The
issue against your draft is best solved by including dr in the crypto
profile; the issue against the code is more complex as it requires us
to actually define dr for rc4. One simple but kind of sucky
definition of dr might be md4. A better definition would involve the
data-dependent key setup from the rest of the rc4 draft with the
confounder removed.

# Tue Nov 12 13:29:43 2002 hartmans (Sam Hartman) - Ticket #1252: - Ticket 1252 MergedInto ticket 1248.

# Tue Nov 12 15:53:23 2002 <kenh@cmf.nrl.navy.mil> - Ticket #1254: - Ticket created

To:	Sam Hartman <hartmans@mit.edu>
Cc:	krb5-bugs@mit.edu
Subject:	Re: SAM uses RC4 insecurely
Date:	Tue, 12 Nov 2002 15:53:15 -0500
From:	Ken Hornstein <kenh@cmf.nrl.navy.mil>

Download (untitled) / with headers
text/plain 862B

Show quoted text

>Well, there is a derive-key for rc4, but it only takes keyusage as
>input, not a string.

Hm, I think I'm confused. I see where the keyusage gets fed into the
algorithm in the Brezak draft, but what I don't see is anything that
looks like derive-key for rc4. Maybe we're not talking about the
same thing.

Show quoted text

>Defining dk interms of dr would work for rc4 if you had a reasonable
>definition of dr, but you currently do not.

Maybe I'm being dense again (and not knowing much about rc4, other than
glancing over the routines that implement it) but would it be
reasonable to pretend for the purposes of rc4 and dr that the blocksize
was equal to the keysize? I think that would prevent the attack you
described. Or just keep state between calls to the encryption
routine.

Like you said, dr still needs to be defined for rc4; just thinking out
loud here.

--Ken

# Tue Nov 12 16:06:22 2002 hartmans (Sam Hartman) - Ticket #1254: - Correspondence added

To:	Ken Hornstein <kenh@cmf.nrl.navy.mil>
Cc:	krb5-bugs@mit.edu
Subject:	[krbdev.mit.edu #1254]Re: SAM uses RC4 insecurely
From:	Sam Hartman <hartmans@MIT.EDU>
Date:	Tue, 12 Nov 2002 16:06:14 -0500
RT-Send-Cc:

Download (untitled) / with headers
text/plain 2.1KiB

Show quoted text

>>>>> "Ken" == Ken Hornstein <kenh@cmf.nrl.navy.mil> writes:

Let's see if we can open a few less bugs on this thread.
Copying krb5-bugs and not including a bug number in the subject opens a new bug.

Show quoted text

>> Well, there is a derive-key for rc4, but it only takes keyusage
>> as input, not a string.

Show quoted text

Ken> Hm, I think I'm confused. I see where the keyusage gets fed
Ken> into the algorithm in the Brezak draft, but what I don't see
Ken> is anything that looks like derive-key for rc4. Maybe we're
Ken> not talking about the same thing.

I'm pointing out that there is algorithm that uses the long-term key
and key usage to come up with an encryption key. It actually uses
long-term key, keyusage and data; this is against the intent of the
kcrypto draft but is allowed by the text.

Show quoted text

>> Defining dk interms of dr would work for rc4 if you had a
>> reasonable definition of dr, but you currently do not.

Show quoted text

Ken> Maybe I'm being dense again (and not knowing much about rc4,
Ken> other than glancing over the routines that implement it) but
Ken> would it be reasonable to pretend for the purposes of rc4 and
Ken> dr that the blocksize was equal to the keysize? I think that
Ken> would prevent the attack you described. Or just keep state
Ken> between calls to the encryption routine.

No, because since rc4 is a stream cipher you'll end up using the same
pseudo-random stream if I call dr with different constants. I.E. rc4
is a function that takes a key, some initial state, and a length and
returns that many bits of pseudorandom stream. I then xor that
against the data. The way the dr in the simplified profile is
definied, if I treat rc4 as a block cipher then I'll be xoring the
same output of rc4 against whatever constant I feed into dr. So the
output of two calls to dr with the same key is related in a rather
easy to detect manner.

Ideally you want dr to be a pseudo-random function.

As I mentioned, there is both md4 and the data-based-keying of rc4
without confounder as a potential candidate for dr. You could also
use the key that would be produced by the data-based keying as a
potential candidate for dr.

# Mon May 05 15:48:46 2003 tlyu (Taylor Yu) - Given to hartmans (Sam Hartman)

# Thu May 15 16:20:50 2003 hartmans (Sam Hartman) - Status changed from 'new' to 'resolved'

# Thu May 15 16:20:51 2003 hartmans (Sam Hartman) - Tags pullup added

# Thu May 15 16:20:51 2003 hartmans (Sam Hartman) - Correspondence added

From:	hartmans@mit.edu
Subject:	CVS Commit

Download (untitled) / with headers
text/plain 292B

Only allow combine_keys to work on des and 3des enctypes. It is not
supported for rc4 or AES until we implement the crypto framework PRF.

To generate a diff of this commit:

cvs diff -r5.140 -r5.141 krb5/src/lib/crypto/ChangeLog
cvs diff -r5.3 -r5.4 krb5/src/lib/crypto/combine_keys.c

# Thu May 22 22:35:47 2003 tlyu (Taylor Yu) - Version_Fixed 1.3 added

# Thu May 22 22:35:47 2003 tlyu (Taylor Yu) - Correspondence added

From:	tlyu@mit.edu
Subject:	CVS Commit

Download (untitled) / with headers
text/plain 183B

pullup from trunk

To generate a diff of this commit:

cvs diff -r5.136.2.3 -r5.136.2.4 krb5/src/lib/crypto/ChangeLog
cvs diff -r5.3 -r5.3.2.1 krb5/src/lib/crypto/combine_keys.c

# Wed Dec 16 18:02:39 2015 tlyu (Taylor Yu) - CustomField pullup deleted