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.