Subject: draft-harris-ssh-arcfour-fixes-02: informational or proposed?

From: Sam Hartman <[email-masked]>
Date: Wed, 01 Jun 2005 14:35:07 -0400

Hi, folks.  The IESG has received a last call comment recommending
that the new rc4 cipher for ssh be published as informational rather
than as a proposed standard because of weaknesses in rc4.  It would be
inappropriate to make a decision based on one comment so I am
soliciting comments on this point.

The argument in favor of publishing this document at proposed is that
the existing arcfour cipher is part of a standard and that many other
IETF protocols use rc4 in standards track documents.

Please submit comments to [email-masked] or [email-masked] on this issue
by 2005-06-28.

Included below is a partial bibliography of RC4 attacks provided to
the IESG by the person making the original comment.

S. Fluhrer, I. Mantin, & A. Shamir, "Weaknesses in the Key Scheduling
Algorithm of RC4", Proceedings of 8th Annual International Workshop
on Selected areas in Cryptography (SAC 2001), Toronto, ON, CA,
August 2001.

J. D. Golic, "Linear Statistical Weakness of RC4 Key Generator",
Procedings of EuroCrypt 1997, Konstanz, DE, May 1997.

S. Fluhrer & D. McGrew, "Statistical Analysis of the RC4 Key
Generator", Proceedings of 7th International Workshop on Fast
Software Encryption (FSE 2000), New York, NY, US, April 2000.

S. Mister & S.E. Tavares, "Cryptanalysis of RC4-like Ciphers",
Proceedings of 5th Annual International Workshop on Selected
Areas in Cryptography (SAC 1998), Kingston, ON, CA, August 1998.

L. Knudsen, W. Meier, B. Preneel, V. Rijmen, & S. Verdoolaege,
"Analysis Method for RC4", Proceedings of AsiaCrypt 1998.

R. Wash, "Lecture Notes on Stream Ciphers and RC4", unpublished,
Case Western Reserve University, OH, US
http://acm.cwru.edu/files/2002%20Spring/talks/latex_samp2_4_09_02.pdf

S. Paul & B. Preneel, "Analysis of Non-fortuitous Predictive States
of the RC4 Key Generator", Proceedings of 4th International Conference
on Cryptology in India (IndoCrypt 2003), New Delhi, IN, December 2003.

_______________________________________________
Ietf mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ietf

---

From: Keith Moore <[email-masked]>
Date: Wed, 1 Jun 2005 14:43:34 -0400

> IETF protocols use rc4 in standards track documents.

previous mistakes are not valid justifications for new mistakes.
previous accidents are not valid justifications for deliberately weakening
new products.

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 01 Jun 2005 20:58:35 +0200

> IETF protocols use rc4 in standards track documents.

A similar argument could be made for MD5.  I don't think it is a
strong argument.

If there is a known public weakness today, publishing it as a standard
seem like a poor idea to me.

FWIW, my general comment is that the IETF should not promote RC4.
Technically better alternatives exists; and the cryptographic/IPR
history of RC4 doesn't improve the case for it.  I have similar
thoughts on the use of RC4 in SASL DIGEST-MD5.

Cheers,
Simon

---

From: Sam Hartman <[email-masked]>
Date: Wed, 01 Jun 2005 15:09:04 -0400

>>>>> "Keith" == Keith Moore <[email-masked]> writes:

    >> The argument in favor of publishing this document at proposed
    >> is that the existing arcfour cipher is part of a standard and
    >> that many other IETF protocols use rc4 in standards track
    >> documents.

    Keith> previous mistakes are not valid justifications for new
    Keith> mistakes.  previous accidents are not valid justifications
    Keith> for deliberately weakening new products.
So, that's certainly true.  but I can see two points.

1) There is an existing somewhat broken rc4 cipher in the ssh
   standards-track document.  This spec proposes to replace that
   cipher with one that is much less broken.  Why should that be at a lower level of standardization than the existing cipher?

2) The fact that we have rc4 in a lot of standards may suggest that we
    consider the attacks against it not sufficient to actually count
    as broken.  To some extent this second consideration is targeted
    at the security community.

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 01 Jun 2005 15:22:38 -0400

>IETF protocols use rc4 in standards track documents.

Correct me if I'm wrong, but the serious problems with RC4 that I know 
of are related-key attacks.  Those don't occur in, say, secsh or TLS.
This draft improves the situation somewhat, and is thus good.  That 
said, I see no problem with strengthening the security considerations 
section to cite some of these other references.  (Arguably, though, 
those citations belong in a different document on RC4.)

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

---

From: Keith Moore <[email-masked]>
Date: Wed, 1 Jun 2005 15:34:19 -0400

>    cipher with one that is much less broken.  Why should that be 
>    a lower level of standardization than the existing cipher?

It shouldn't.   But there's no reason that the existing specification
cannot be reclassified as Historic at the same time as the new
specification is approved for whatever classification seems reasonable.
There's also no reason that an applicability statement cannot be
written (preferably as a separate document) that explains the reasons
for the status of each dialect of rc4, and the risks vs. benefits of
using each dialect of rc4.  (other than, perhaps, it's awkward for IESG
to originate such statements, and even more difficult to get consensus
on such statements than for ordinary specifications)

Note that I'm not specifically recommending that the new rc4 document
not be standards-track, nor am I specifically recommending that the
existing documents should be reclassified as non-standards-track.  I am
saying that the fact that the "existing arcfour cipher is part of a
standard and that many other IETF protocols use rc4 in standards track
documents" is not a justification for making the new document a
standard if it doesn't meet our technical criteria.  Nor is it a
justification for keeping the old documents at standards-track if they
no longer meet our technical criteria.

Keith

p.s. Part of the problem, I suspect, is that the standards-track vs.
non-standards-track bit is overloaded (in practice) to be both a
"recommendation" bit and a "this meets our technical criteria" bit.
There are times that we'd like to recommend protocols and practice that
don't meet our normal criteria for standards-track. There are also
times that we want to make standards for protocols even we don't
specifically recommend their use.    But we have a difficult time doing
that because we know that in practice anything we label as "standard"
will be taken as if it is recommended.

---

From: Sam Hartman <[email-masked]>
Date: Wed, 01 Jun 2005 15:48:20 -0400

>>>>> "Steven" == Steven M Bellovin <[email-masked]> writes:

    Steven> ------- Forwarded Message

    Steven> In message <[email-masked]>, Sam Hartman
    Steven> writes:
    >> 
    >> 
    >> Hi, folks.  The IESG has received a last call comment
    >> recommending that the new rc4 cipher for ssh be published as
    >> informational rather than as a proposed standard because of
    >> weaknesses in rc4.  It would be inappropriate to make a
    >> decision based on one comment so I am soliciting comments on
    >> this point.
    >> 

    Steven> Correct me if I'm wrong, but the serious problems with RC4
    Steven> that I know of are related-key attacks.  

That's what I thought too.  However that seems to be false.  The one
reference currently in the security considerations section is for an
attack to distinguish an RC4 stream from a random stream.  That's much
more serious for ssh and tls than the related key attacks.

--Sam

---

From: "william(at)elan.net" <[email-masked]>
Date: Wed, 1 Jun 2005 15:48:44 -0700 (PDT)

>> IETF protocols use rc4 in standards track documents.

SSH needs stronger stream cipher, but all implementations use RC4 and quick
way out is to increase key size (to 128 or 256 bit as in the draft),
I think its better then no increase in ssh security at all, so I don't see 
why you want to continue to have less secure protocol solution as proposed
standard and block its update to something better.

For the long term, IESG really needs to make it clear to SSH that they
MUST develop/introduce completely different stream cipher, perhaps SEAL, 
maybe something else. It might even be good to mention in current draft 
that this is considered a temporary solution and that SSH will be moving 
to different cipher in the future to replace RC4.

> This draft improves the situation somewhat, and is thus good.

Yes, but large stream of RC4 data makes statistical attack possible.
And there are people who use SSH for more then just telnet session, 
biggest of SSH use by amount of data is probably X11 forwarding and
tunnels and that is where RC4 is a weak link. At least the draft
mentions it which is good!

-- 
William Leibzon
Elan Networks
[email-masked]

---

From: "william(at)elan.net" <[email-masked]>
Date: Thu, 2 Jun 2005 02:31:23 -0700 (PDT)

> previous accidents are not valid justifications for deliberately weakening

Keith,

I think you're right in general. But in this specific case its not a
"new product". SSH already uses RC4, the change is increasing size
of key that maybe used. Admittedly it does not fix problems with SSH
using RC4 in general, but the update provide for better security
then current system and is definitely not weakening it.

-- 
William Leibzon
Elan Networks
[email-masked]

---

From: Bill Sommerfeld <[email-masked]>
Date: Thu, 02 Jun 2005 10:36:52 -0400

On Wed, 2005-06-01 at 15:48, Sam Hartman wrote:

> attack to distinguish an RC4 stream from a random stream. 

A critical parameter to such attacks is the amount of keystream required
under a single key before the attack becomes feasible.  

Assuming I've read it correctly, the most recent paper I've found on the
topic mentions a threshold of 2^24 bytes if you don't discard the start
of the keystream, and 2^32 if you discard the first 256 bytes. 

As the sshv2 protocol allows for either party to trigger a rekey of both
directions of the communication, it certainly seems like a cautionary
note to set rekey thresholds appropriately would be in order.  given the
extremely lightweight nature of the algorithm you may still come out
ahead from a cpu time/power/battery-life perspective even with frequent
rekey...

						- Bill

---

From: Ben Harris <[email-masked]>
Date: Fri, 03 Jun 2005 10:53:20 +0100

>soliciting comments on this point.

I think it may be worth my explaining a little of the background here, and
what I'm trying to achieve.  I don't know that a Standards Track RFC is the
correct approach, but it seemed the most appropriate to me.

SSH finally got approved for publication as a Proposed Standard earlier this
year.  It supports many symmetric ciphers, one of which is "arcfour".  This
is RC4 with a 128-bit key, using the keystream from the beginning. 
"arcfour" is notable for being, in software implementations, both the
fastest and the simplest of the symmetric ciphers specified for SSH in any
Standards Track document (except for "none", of course).  This makes its use
tempting in circumstances where code size or CPU usage are important.

RC4 has several weaknesses, some of which can be eliminated by discarding
the start of the keystream, which is a trivial operation.  Increasing its
key size is also trivial.  Some of RC4's other weaknesses are inherent in
its keystream generator.

My aim in writing draft-harris-ssh-arcfour-fixes was to ensure that the
fastest and simplest standard SSH cipher (a) wasn't unnecessarily weak and
(b) had its necessary weaknesses documented.  Other ways to accomplish the
same thing would be to somehow deprecate "arcfour" and force people to use
"blowfish-ctr" instead, or to standardise a new cipher that's faster,
simpler, and more secure than "arcfour".

It occurs to me that if someone could come up with a procedure for doing so,
my ideal here would be to cause "arcfour" to become NOT RECOMMENDED, and to
introduce "arcfour-128" and "arcfour-256" with the same status.

People wishing to read the papers referenced might find these URLs useful. 

>on Selected areas in Cryptography (SAC 2001), Toronto, ON, CA,
<http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps>

>Procedings of EuroCrypt 1997, Konstanz, DE, May 1997.
<http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Golic.PDF>

>Software Encryption (FSE 2000), New York, NY, US, April 2000.
<http://www.mindspring.com/~dmcgrew/rc4-03.pdf>

>"Analysis Method for RC4", Proceedings of AsiaCrypt 1998.
<http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Knudsen.ps>

>on Cryptology in India (IndoCrypt 2003), New Delhi, IN, December 2003.
<http://www.cosic.esat.kuleuven.be/publications/article-86.pdf>

-- 
Ben Harris

---

From: Ben Harris <[email-masked]>
Date: Fri, 03 Jun 2005 10:06:13 +0100

In article <[email-masked]> you write:
>note to set rekey thresholds appropriately would be in order.

I don't believe that rekeying is sufficient, which is why the draft doesn't
recommend it.  The distinguisher relies on the non-uniform distribution of
digraphs in all RC4 keystreams, so if it needs to it can work on two bytes
from each of 2^32 separate keystreams.  I think (and I'd be happy for a
crytographer to contradict me here) this means that if you encrypt the same
thing (e.g. an SSH password packet) 2^32 times under different RC4 keys, an
attacker can deduce one bit of information about it, or more accurately one
bit of information per digraph.

-- 
Ben Harris

---

From: Ben Harris <[email-masked]>
Date: Fri, 03 Jun 2005 10:15:36 +0100

In article <[email-masked]> you write:
>of key that maybe used.

That's not the only change.  The important aspect of my draft is that it
requires discarding the first 1536 bytes of RC4 keystream.  Apparently RSA
Security have always recommended discarding the start of the keystream, but
SSH (and TLS, for that matter) has ignored this recommendation.  The
addition of support for 256-bit keys was just my taking an opportunity to
bring RC4 into line with the rest of SSH, and to give us a little more
security headroom against any remaining attacks on the key schedule.

-- 
Ben Harris