Re: 40-bit RC5 crack meaningless?

[Peter Trei <trei@ziplink.net>]

Subject: Re: 40-bit RC5 crack meaningless??
From: Peter Trei <ptrei@acm.org>

> Subject:       40-bit RC5 crack meaningless??

Mr. Strassman allegedly sent the quoted letter to Winn Schwartaus'
"infowar" mailing list, and it was then posted by persons unknown to
the sci.crypt usenet group. Identity on the internet being the fluid
thing it is, I apologize in advance if he never sent this letter, or
if it has been modified before it reached me.

The quoted letter attempts to minimize the importance of Ian
Goldberg's recent bruteforce decryption of export-strength RC5
encryption.

In my opinon, as described below, Mr. Strassman's arguments are
without merit when applied to the situation the RSA challenges are
intended to model - the security of encrypted Internet protocols. As
such, I feel that his letter may lull some people into an unjustified
and dangerous sense of security.

> >Date: Thu, 30 Jan 1997 20:10:36 -0500
> >From: "Paul A. Strassmann" <paul@strassmann.com>
> >Subject: Further to Goldberg's Cracking Accomplishments
> >Gentlemen:
> >
> >As I suspected (see earlier private comment), the
> >highly promoted RSA cracking contest offered
> >a number of clues that ordinarly would not be
> >volunteered by  info-terrorists or info-criminals to
> >IW Defense teams.

> >These clues made the cracking significantly easier,
> >because it made it possible to eliminate an enormous
> >range of possible searches.

What's the target, and who is doing the encrypting?  These "clues"
_are_ available to adversaries engaged in industrial and economic
espionage; a important part of a covert infowar.

It's certainly true that "info-terrorists or info-criminals" will not
be so easy to tap, but the absence of these 'clues' is a red
herring. They will be secure because they will use good encryption,
which is not what US firms can export today.

The challenges are realistic models of encrypted Internet protocols,
for example IPSEC with ESP data encryption. As such, they accurately
display the vulnerability of data on the Internet to espionage.

> >The following was extracted verbatim from the
> ><The RSA Data Security Secret-Key Challenge>
> >posted on <http://www.rsa.com/rsalabs/97challenge/>:
> >
> >Clue #1:
> >
> >  " ...all the RC5 contests posted as part of the RSA Secret-Key Challenge
> >will use 12-round RC5 with a 32-bit word size. "
> >
> >Clue #2:
> >
> >  " ...The first RC5 contest will consist of some unknown plaintext
> >encrypted using a 40-bit key;."

Clues #1 and #2 are absolutely reasonable - in an open standard, it is
absolutely normal to know the cipher being used, it's mode, and the
length of the key. See the SSL specification, or IPSEC's RFCs.

> >Clue #3: (a  giveway!)
> >
> > " ... For each contest, the unknown plaintext message is preceded by three
> >   known blocks of text that contain the 24-character phrase "The
> >   unknown message is:  .....".

To those who are unfamiliar with Internet protocols, this would appear
to give the cryptanalyst an unrealistic head-start. This is not the
case.  Most Internet protocols have highly stereotyped packet headers;
for example, _every_ normal return packet from a web server starts out
with the string "HTTP/1.0" (servers using something other than version
1.0 are rare as hen's teeth at the moment).  When you consider that
such a packet may contain a firm's confidential earnings predictions
or trade secrets (hopefully encrypted), the economic importance of
such data is clear.

Similar stereotyped headers exist for many other protocols, such as
NNTP and SMTP. As such, a known-plaintext attack, as modeled by
RSADSI's symmetric key challange, is quite realistic.

Even if a full known plaintext for the first block is unavailable, a
knowlegable cryptanalyst can usually make some very reasonable
assumptions which will greatly speed his or her task. (I'm assuming
DES here - which has a 64 bit block, but the argument extends easily
to other block sizes). For example, if we know that the data contains
only printable ASCII characters (true for the headers of most Internet
protocols), then for a 64 bit block, there are 8 bits which we _know_
will be zero in the decrypted block. This lets us dispose of 255 out
of every 256 incorrect trial decryptions immediately, and we will have
to perform more extensive tests on less then 0.4% of candidate keys.

Similar intelligent guesses can be made about the headers of other
protocols, for example IPSEC-secured IPv6 packet headers in tunneling
mode.

Some people have noted that the challenges include the IV, or
'initialization vector' used in CBC (cipher-block-chaining) modes of
encryption, and argue that this would not be available to an
adversary. Once again, this assertion falls when examined in the light
of actual usage.

The purpose of an IV is to make dictionary and replay attacks more
difficult. It is not intended to prevent brute force attacks, and so
is _normally_ included in the clear in communications protocols (for
example, see RFC 1827 for it's clear transmission in IPSEC). If it
is not included, it is effectively part of the keying material, and
thus adds it's bits to the strength of the key. As such, its value
would have to be transmitted and protected as carefully as the rest of
the key.  

> >In summary: The claim of exportable cryptography being totally 
> >insecure, because it can be cracked in 3.5 hours is not 
> >realistic. The three clues announced in the contest 
> >would not apply under infowar conditions.

As I have shown above, Mr. Strassman's optimism is misplaced in the
case of actual, fielded use of encryption on the Internet. It may
apply to some classified systems, but they don't use exportable
cryptography anyway. A covert inforwar against commercial and private
targets is _quite_ plausible.

> >What other clues may have been provided to Goldberg
> >to  support private agendas and gain shrill headlines
> >is also a matter of speculation, but I rest my case.

What exactly is he hinting at here?

> >I certainly cannot assert that a 40 bit key cannot be decyphered.

Of course he can't. 40 bits of RC4 encryption (as used in the
exportable version of Netscape) was brute-forced not once, but three
separate times in the fall of 1995, the fastest effort taking about 28
hours. Today it could be done much more quickly, as Ian demonstrated
with RC5 (an algorithm of similar complexity).

> >However, I do not think that the RSA unqualified claims
> >offer full and appropriate disclosure.

I disagree. The RSA challenges accurately model the use of encryption
on the unclassified Internet. Ian's decryption of 40-bit RC5 is of
considerable importance in demonstrating the insecurity of American
citizens caused by Administration efforts to compromise exportable
encryption.

In my opinon, Mr. Strassman's assertions as to the strength of
exportable encryption are too dangerous to be left unchallenged.

> >Paul A. Strassmann
> >55 Talmadge Hill Road, New Canaan, CT. 06840
> >Telephone: 203-966-5505; Fax: 203-966-5506
> >INTERNET:                  paul@strassmann.com
> >WorldwideWeb:           http://www.strassmann.com

Peter Trei
ptrei@acm.org

Disclaimer: I am speaking as a knowlegable private citizen, not as
a representative of my employer. This posting represents my opinon
only.