Ian popped the 40-bit RC5 (not RC4) challenge with 259 processors, almost all standard Unix college-lab workstations, as I understand it. (RC5 has a variable block size and a variable number of rounds; but the unknown plaintexts for this contest were enciphered using a declared 12-round RC5 with a 32-bit word size.) The message Ian revealed was something like: "That's why you need a longer key!!!!!" RSA posted rewards for anyone who can break a 56-bit DES challenge and/or any of 12 variable-length RC5 challenge messages. The 40-bit RC5 cipher was the least of these and was expected to fall quickly. The initial RSA announcement of the contest emphatically declared that even 56-bit-key crypto (DES or RC5) offers only "marginal protection" against a committed adversary -- which is not to in any way minimize Ian's accomplishment, or the efforts (some also successful!) of others who also tackled the 40-bit challenge. SDTI/RSA celebrated Ian's achievement enthusiastically at the RSA Security Conference in San Fran last week. Burt Kalisky, the Chief Scientist at RSA, preempted a main session at the Conference to do an on-stage telephone interview with Ian about his attack. SDTI (RSA) apparently hopes to use Ian's "timely" achievement to urge Congress to challenge the idiotic 40-bit EAR ceiling and the key-escrow contracts required to get a 56-bit export license. (The network Ian used to link his lab workstations, NOW at Berkeley, is definitely not standard, however. I think there is a description of it online; but briefly, NOW seems designed to very efficiently handle this sort of intensive distributed processing project. More important, perhaps, was the fact that Ian just chewed through the possible keys with a pure brute-force attack on the key space. His attack was not really optimized for RC5, or designed to attack any specific element in the RC5 crypto architecture.) Jim Bitzos of RSA also gave a thought-provoking thumbnail summary of the IBM Key Recovery Alliance (making a better case for it in 30 seconds than the long technical presentatations from IBM.) As Bitzos explained it, the variable key-size control allows a corporate user to communicate through encrypted links to a variety of international recipients -- dynamically adjusting the encryption mechanism to whatever varied restrictions are required by the French, German, US, UK, etc. , govenments. "It's an imperfect world," growled Bitzos -- but both users and vendors need workable mechanisms today to allow them to adapt to whatever contraints on strong encryption that are, or will be, required by the various national authorities. It's a mistake, he suggested, to think of the IBM Key Recovery Initiative soley in terms of US controls. Many governments are reacting with hostility to the availability of strong encryption -- and until the Market finds a voice and educates the political and spook cultures, commercial entities will inevitably have to adapt their work-a-day communications security to a wide variety of national crypto controls and key-length restrictions. (What I got about the IBM presentations was the realization that there is nothing in the key recovery mechanism, per se, that requires the recovery key to be held by a third party. That, to my mind, is the essential distinction between key escrow and key recovery. I also realized that IBM has, for years, quietly held a crucial piece of the PKC scheme in its patented "control vector" tech, which irrevocably binds a whole set of context-specific rules and constraints to a decryption key. I now realize that the control vector technology was the foundation much of the the DoD's Blacknet development. Important stuff -- check it out!) Like Big Jim said, it's an imperfect world -- and likely to become more so, from the C'punk perspective, before it becomes better. The rumor mill among the 2,500 cryptographers, mostly developers, who attended the RSA Conference was pumping overtime. One of the saddest and most persistent rumors was that the Clinton Administration would, within months, introduce a Congressional bill to make unescrowed strong encryption illegal in the US. (Personally, I'd put bitter money on that one. <sigh>) David Aaron, US Crypto Ambassador and the US permanent rep to the OECD -- in which role he has strove to convince the newly liberated nations of Eastern Europe that built-in wiretap links are essential design components for a modern democratic nation's communications infrastructure -- was charming and gracious... but it was no surprise that he didn't budge a bit from the "sovereign right to listen" policy line. You shouldn't have skipped the RSA bash, Adam, not even for your DCS gig in the sunny Caribbean. There were numerous Lion and the Lamb drinking bouts thoughout the week (some rather amazing, in terms of both the participants and the volume of "input".) You would have loved it. Passions often ran high, but usually in quiet intense coversations. I (one Lamb, white wool turning gray;-) had distinct impression that there many US government cryptographers uncomfortable with the Administration's NSA/FBI-inspired absolutist POV. Not even all senior feds feel that Constitutional Law should be (re)written by FBI case agents obsessed with making it easier to bust some two-bit crack dealer next month. (Doesn't mean much in the larger scheme of things, but the pained ambivalence vividly reminded me of Vietnam debates so many years ago.) My favorite quote, from a federal LEA lawyer deep in his cups: "If the colonial cops, rather than the philosophers, had drafted the Constitution -- would Madison and Jefferson, et al, have been willing to even put their names to it??" Suerte, _Vin -------- In Reply To:

Steve Schear wrote: | > What the US government will allow to be exported is not "strong | >encryption." It is encryption only slightly too strong to be broken | >by an amateur effort. For the right investment in custom hardware, it | >falls quickly. (500,000 $US = 3.5 hour avg break). | > | | Considering Ian's feat you certainly seem to have had your crystal | ball in hand.

Adam Shostack responded:

I wear three around my neck. Its a new age thing.

More seriously, that estimate is the cost of breaking DES on custom hardware, based on Wiener's figures. Ian got RC4-40 in 3.5 hours on I don't know how much hardware, not a lot of it custom, AFAIK.

Vin McLellan + The Privacy Guild + <vin@shore.net> 53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548