[Excerpts from Winn Schwartau's 2/9 "InfoWar Digest," with responses to Paul Strassmann's diatribe on the RSADS Secret-Key Challenge. Burt Kaliski, Tim May, Padgett Peterson -- among others -- toss in their two bits. Longish. [FYI: RSADS still has 12 open Challenges pending, offering cash rewards for anyone who can decrypt 56-bit DES -- or any of eleven _other_ RC5 cyphertext samples, encrypted with keys of varied lengths, ranging from 48-bit through 128-bits. Details somewhere on the RSA site: <http://www.rsa.com> ] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From: Burt Kaliski <burt@RSA.COM> To: "'infowar@infowar.com'" <infowar@infowar.com> Subject: Further to Goldberg's Cracking Accomplishments Date: Wed, 5 Feb 1997 13:58:53 -0800 Paul A. Strassmann <paul@strassmann.com> quoted a UC Berkeley press release on Ian Goldberg's successful effort to discover the unknown 40-bit key to an RC5 ciphertext offered in the RSA Data Security Secret-Key Challenge, and raised a number of justifiable concerns about whether a contest like the Challenge is an appropriate measure of the security of a 40-bit encryption algorithm in an InfoWar environment.
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.
Mr. Strassmann is a well known scholar of the InfoWar threat environment. I am not, so I cannot address those specific concerns directly -- but I would like to offer some rationale as to why the Challenge was structured as it was. The RSA Data Security Secret-Key Challenge <http://www.rsa.com/rsalabs/97challenge/>, started last week, is an open contest sponsored by RSA Laboratories that offers cash prizes for the successful recovery of encryption keys for the DES and RC5 block ciphers. Following the model of the RSA Factoring Challenge which for several years has provided an assessment of the security of the RSA public-key algorithm at various key sizes, the Secret-Key Challenge is intended to measure of the security of secret-key algorithms at various key sizes. As was the case with the Factoring Challenge, full details of the algorithms and key sizes are provided. In addition, three plaintext-ciphertext pairs (the ciphertext encrypted with the key of interest) are provided for each key to be recovered. Last week, the first of the keys in the Challenge, a 40-bit RC5 key, was recovered by Ian Goldberg, a U.C. Berkeley graduate student. His effort involved about 250 workstations and took 3.5 hours. When I called Mr. Goldberg to congratulate him in a teleconference during the RSA Data Security Conference last week, he explained that he had discovered the valid key with a search of about 350 billion keys, using a university computer network to search at a rate of 100 billion keys/hour. There are about 1 trillion 40-bit keys, for any algorithm. Mr. Goldberg's search method involved simple brute-force; that is, the known plaintext was encrypted with each key, and then compared to the available ciphertext, looking for a match. The overall effort was essentially what was expected for the 40-bit key size, and as one would expect, the recovery of a key for the other RC5 key sizes (from 48 bits to 128 bit), or for DES (56 bits), will involve much more work. With the same "brute force" method employed by Mr. Goldberg last week, one would expect a 256-fold increase in effort for each eight-bit increase in key size. Special-purpose hardware may reduce the actual time, of course, but the total number of possible keys to be tested will grow at that rate. Mr. Strassman expressed concern as to whether the successful recovery of a 40-bit key in 3.5 hours is a realistic measure of the strength of 40-bit keys in an InfoWar environment, where full details of the algorithm and plaintext blocks are not necessarily known. Again, not being acquainted with the threat environment, I cannot address his concerns directly. Nevertheless, RSA Laboratories does consider this type of contest to be appropriate as a general measure of cryptographic strength -- for RSA's products and those of any other vendor in the international crytographic community. The information provided to RSA Secret-Key Challenge contestants is no more than is common and conventional for any open contest to test the strength of a cryptographic algorithm. These conventions have evolved within the international community of cryptographers seeking, on the basis of several acknowledged principles, to develop common criteria for measuring the relative strength or security of any particular cryptographic algorithm with a given key size. Our rationale for the structure of the Challenge is reflected in the following observations: * Knowledge of the algorithm and key size (as per Kerchoffs' principle), as well as the availability of known plaintext, are standard assumptions in modern cryptanalysis. Since an opponent may obtain this information eventually, it is preferable not to rely on its secrecy when assessing cryptographic strength. * The implementation of large-scale key-search engines is simplified under the standard assumptions. This makes the contest accessible to a wider variety of contributors, than if we required contributors to know, for instance, a particular language, or language statistics, or other characteristics of the plaintext. (Perhaps another challenge where we didn't provide plaintext samples would be a worthwhile follow-up.) * In practice -- even if the plaintext is not known -- significant information about it is likely to be, such as character distributions (ASCII, English), header values (e.g., BER tag and length), or padding. The cost (in time, effort, and computing resources) of a key search with even a small amount of information of this kind is not significantly more than the cost with known plaintext. For instance, if it is known that the characters are represented in ASCII, for instance, then one can decrypt available ciphertext with each key and check that the recovered plaintext follows ASCII conventions (most significant bit of each byte 0). The chance that an incorrect key produces plaintext that passes the test is 1/2^k where k is the number of plaintext bytes recovered. This means, for example, that of 2^40 keys tried, we expect only 2^32 to pass the check for a single eight-byte block. The 2^32 keys must then be tested further against other ciphertext blocks. So instead of 2^40 encryptions -- as in the case when the plaintext is known -- a cryptanalyst would need to search within 2^40+2^32+2^24+2^16+2^8+1 (roughly) keys, to find the correct key. But this represents an increase in effort of less than 0.5 percent. RSA Laboratories appreciates the InfoWar Community's interest in the RSA Data Security Secret-Key Challenge, and Mr. Strassmann's comments in particular. We look forward to further suggestions and critiques of our efforts. -- Burt Kaliski
Chief Scientist RSA Laboratories
Date: Mon, 3 Feb 1997 21:42:24 -0800
To: infowar@infowar.com
From: "Timothy C. May" <tcmay@got.net>
Subject: Re: Infowar Digest Volume 02: Number 04 - Crypto and Goldberg
I seldom read your newsletter carefully. I did tonight, and discovered two
of the items you included contain serious errors.
(Of course, as a strong advocate of "infowar" I suppose I'm pleased to see
your subscribers in the government misled by these errors...it makes our
job a little easier in the long run.)
>To: infowar@infowar.com
>From: Patrick Galley <Patrick.Galley@studi.epfl.ch
>Subject: New crypto attack
>Date: Mon, 27 Jan 1997 07:56:39 +0000
>
>Hello
>
>A friend of mine told me to look at the WWW site "John Douglass'
>CryptoMaverick Page").
>
>There I've found a paper from John Douglass which says that if RSA
>products are sold worldwide it because there is a backdoor inside. He
>said the same thing for DES and PGP.
.....
>If this guy is right. It would be better for is security that everybody
>knows the truth.
>
>I think it would be nice if you could look at this doc and talk about it
>in infowar.com.
I looked at the site and it's a mixture of conspiracy theory rantings and
misinformation.
As to the security of various RSA algorithms (and PGP, for example), the
security of many of these algorithms lies in the publishing of the source
code, with digital signatures on the released binaries to allow independent
verification.
If a real security hole is found in, say, PGP or Netscape, expect it to be
publicized loudly and quickly. (Indeed, certain flaws have been found, and
quickly publicized. The same Ian Goldberg involved in later message was one
of those who isolated a flaw in the random number generator used in an
earlier version of Netscape.)
The web site mentioned here doesn't cut it, and this message here is just
more "disinformation" (itself a part of infowar, so I guess the author is
practicing his skills).
>Date: Thu, 30 Jan 1997 20:10:36 -0500
>To: "Wright Larry" <Wright_Larry@bah.com>
>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.
Paul Strassmann is simply missing the central point of cracking the 40-bit
export-allowed version. It is not based on a known plaintext attack, but on
exhaustive search of the 40-bit keyspace. What Goldberg and his colleagues
who contributed CPU time on the "NOW" (Network of Workstations) did was to
search approximately 100 billion keys per hour. As there are about a
trillion keys in the 40-bit keyspace, it was a foregone conclusion they
would find the key within 10 hours (modulo any screwups at their end), with
about half the time being the most likely time. As it was, they found the
key a tad bit early, by the luck of the draw (so to speak).
RSA certainly knows how long it takes to brute force the keyspace. They
just didn't know who would find the key first. (And at least one other
group reported a solution within minutes of Goldberg's report.)
So, Paul is simply throwing disinformation--or lack of understanding--into
the air by claiming that this crack does not mean a 40-bit key is "weak."
Simply put, it is. Anyone who looks at the math understands this. The
keyspace is simply too small for real security.
(Does the NSA use 40-bit keys? Of course not. Hmmmhhh.)
As the select panel of cryptographers empaneled to study key lengths
concluded, 56 bits is already too weak, 80 bits is better and should be
adopted forthwith for export, and >96 bits is preferable.
As an "infowarrior" of sorts myself, I can assure you that we don't give a
hoot in hell what the regs say is "allowed." When any tourist on his way to
Europe can carry as many CD-ROMSs and DAT tapes in his luggage as he
wishes, with absolutely no "exit checks," who really cares what the "export
laws" allow?
(I carried 5 gigabytes of data, some of it crypto-related, to a meeting
with cryptographers and crypto anarchists in Monte Carlo a while back.
Obviously I was not searched or even glanced at on my way out, nor on my
arrival at Charles de Gaulle airport, etc. Only upon my return to San
Francisco was I asked what my business had been. The Customs Officer gave
me a blank look when I told him I was meeting with cryptographers in Monte
Carlo (I told him the truth, knowing I was breaking no laws whatsoever). He
had no idea what I was talking about, and was bored. He then asked me if I
was bringing back any stuff I bought in shops over there. "No," I told him.
He just waved me through.)
Not to mention the ease with which stuff is shipped out over the Internet.
(I made a bet a couple of years ago that each major new cipher would arrive
at offshore non-U.S. sites within 3 hours of release in the U.S. Remailers
make it so easy to bounce stuff around.)
And of course I was the one in 1988 who first proposed the now-popular
method of using the least significant bits (LSBs) of CDs and DATs filled
with music, and LSBs of GIF images, to transparently export megabytes of
data undetectably. (To any sniffers, the LSBs are formally and
statistically identical to the ordinary noise of microphones and recording
electronics.) A normal 2-hour DAT tape of a recording I made off the radio
or off of one of my CDs can carry 160 megabytes of "data" riding in just
the LSBs alone. That's equivalent to 16 copies of the Bible, or a
significant chunk of the B-2 Stealth bomber CAD database.
I'd like to see your list get involved in more accurate and less
scare-mongering discussions.
--Tim May
Just say "No" to "Big Brother Inside"
We got computers, we're tapping phone lines, I know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May | Crypto Anarchy: encryption, digital money,
tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets,
Higher Power: 2^1398269 | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."
Date: Tue, 4 Feb 1997 00:52:28 -0500 (EST) From: "Craig H. Rowland" <crowland@psionic.com> To: "Betty G. O'Hearn" <betty@infowar.com> Subject: RSA
Date: Thu, 30 Jan 1997 20:10:36 -0500 To: "Wright Larry" <Wright_Larry@bah.com> 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.
You are talking about implementing security through obscurity. You can never assume that an enemy does not know what security precautions are in place to protect information, or in this case, what cipher you have chosen to protect your data. The security of your in-place mechanisms should be able to stand on their own merits under a worst case scenario of full public disclosure.
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;."
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: .....".
Let me address 1, 2, and 3 all together as they all suffer from the same flaw in logic as discussed above. First, the ciphers in this contest includes more than RC5, the main point of the contest is not to illustrate the security of a particular cipher from cryptanalytic attack, but rather to show that key lengths that are too short are insecure against a brute force attack. The fact that the cipher is known does not affect the overall purpose of the contest. Second, you are again assuming the cipher is unknown by your enemy. Suppose you are a financial institution, I can be almost 100% assured that your communications are protected with DES as the cipher. If I can discover what equipment you are using and what modes the cipher runs in (CBC, ECB, etc) I can then attempt a similiar brute-force attack using the widely available DES specifications. Commercial organizations using exportable software systems suffer the same fate. You are also assuming that a mathmatical analysis of the encrypted data stream will not reveal what cipher is being used. Various statistical attacks could reveal key pieces of information that could quickly unveil what cipher you are using and what mode it is being run in. Third, just because part of a message is known does not mean the contest is invalid. Many network communication protocols use a fixed set of characters to establish and end communication sessions. An attacker, aware of how the protocols work, can often discern what a message may contain when it is initiated. An example of this could include SMTP traffic which includes a standard set of protocol keywords, or an electronic funds transfer which includes unique bank identification numbers or other similar data. This is called a known plaintext attack and is very common.
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.
Again, this is not correct. You are assuming total ignorance by the enemy which is rarely the case.
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.
Why does one even need a "clue" about this key size? It should be obvious to anyone remotely educated/interested in the field of cryptography that the reason the NSA limits exportable key length to 40 bits or less to begin with is so they can do the same thing at Ft. Meade on their internal computers that was done here publically. The whole debate over exportable encryption rarely rests on the cipher, but rather on the *length* of the keys used. This *alone* should be enough to convince the reader that key length is in fact a very vital issue for both the NSA and the Internet community.
I certainly cannot assert that a 40 bit key cannot be decyphered. However, I do not think that the RSA unqualified claims offer full and appropriate disclosure.
Nonsense..RSA sells cipher technology that uses both 40 bit encryption and higher, they make their money either way...their only bias in this area is that they have their exportable software crippled in such a way as to make it useless to foreign buyers. Luckily companies in Finland, Switzerland, and Germany are starting to take up the slack and provide strong cryptographic products of their own. -- Craig ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Date: Tue, 4 Feb 1997 12:49:25 -0500 (EST) To: infowar@infowar.com From: Bob Stratton <strat@wheelgroup.com> Subject: RSA's Challenge Claims and the Real World In Infowar Digest Volume 02, Number 04, Paul Strassman writes:
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.
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.
I certainly cannot assert that a 40 bit key cannot be decyphered. However, I do not think that the RSA unqualified claims offer full and appropriate disclosure.
I feel compelled to respectfully submit what may be considered a rebuttal. In general, I tend to dismiss claims of anything being "totally" anything, but in this particular instance, I think further discussion may be warranted. I admit to being a little surprised by this tack on the part of RSA. RSA Labs (the research side of that house) has earned my respect over time by doing serious cryptological work and publishing it in a thoughtful, academic manner worthy of note. The histrionics of press releases notwithstanding, I think these comments merit further examination: I may concede that the "three clues...would not apply under infowar conditions". In doing so, I must also ask for further clarification as to exactly which infowar Mr.Strassman is referring. Given this forum's consideration of the national security implications of attack on the financial infrastructure, it seems a fair question. In any event, I question whether this is relevant within the context of the challenge, and the purposes behind it. RSA's purpose in posting this challenge was presumably to enlighten the public and others as to the _relative_ strength of currently exportable cryptosystems. I have no doubt that the agenda behind this is to encourage resistance to current U.S. policies on cryptographic export, a stance designed to maximize share value in what is admittedly a commercial venture. I'm also willing to note that I have a general distaste for INFOSEC "challenges" of any sort. I would, however, like to explore the assertion that the clues posted in the challenge were not offered in the spirit of full and fair disclosure. I will concede in any case that this was not an exhaustive, controlled study. "Challenges" such as these have a place. Within the INFOSEC environment, cryptanalytic attack appears to be one of the more reasonable areas for them. Compared to "challenges" against network "firewalls", for example, cryptanalysis is an area where there is the opportunity to adequately define the goal and to measure the result. In this case, RSA was not attempting to prove a negative, as have so many (too many) other firms offering so-called "challenges". If we restrict our focus for purposes of argument to commercially available cryptographic software, the clues become significantly less onerous and mysterious. Clue #1, the disclosure of 12-round RC5 with a 32-bit word size, is certainly the most arcane of the lot. Speaking as a former commercial software developer, I would be quite surprised if vendors would not routinely disclose information of this sort. Certainly vendors using standard algorithms would tend to be more willing to do so than those using proprietary ones, which only bolsters my later arguments, as you will see below. If we may depart for just a moment to other algorithms, almost any _standard_ implementation of an algorithm which is interoperable with other implementations would, by definition, disclose or facilitate disclosure of this sort of information, by its very nature. Again, in a commercial environment, interoperability is key (no pun intended), so it's likely that implementation details are either available, or readily deducible. Clue 2, the disclosure of key size, again meets the standards just discussed. In the case of products recently exportable from the U.S., one of two things is generally true. Either the key size is actually 40 bits, or the key size is larger than 40 bits, but steps are taken to make all key information beyond 40 bits accessible to observers of the tool. Again, in a commercial environment, this is no secret. Clue 3 is perhaps where I'm most inclined to agree with Mr. Strassman. Disclosure of known plaintext, in this case the phrase "The unknown message is:" is certainly quite serious in that it may significantly aid cryptanalytic attack. My only comment here is that in the commercial arena, interoperability demands standards, and standards define consistent protocols. Those protocols will almost always result in some manner of reproducible content, most readily exemplified by message headers in electronic mail systems. While mechanisms exist for enhanced cryptographic protection of said content, in general the commercial environment has lagged behind the military, and perhaps rightly so. In none of the aforementioned cases, however, do I see information that fundamentally invalidates the significance of RSA's Challenge TO THE CIVILIAN COMMERCIAL INFOSEC COMMUNITY. That community has serious, current INFOSEC needs, and one must question (as I know many of us do every day) to what degree we're willing to lay our economic fabric open to subversion in order to lessen the cost of intelligence collection. --Bob Stratton ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Date: Tue, 4 Feb 1997 9:25:21 -0500 (EST) From: "A. Padgett Peterson P.E. Information Security" <PADGETT@hobbes.orl.mmc.com> To: infowar@infowar.com Subject: RSA challenge Paul rote:
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. ... 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: .....".
Those who follow my hobby may have noticed that about two years ago I began using the "3.5 hour" figure to assign a maximun value of $250 to any information sent via a 40 bit code. The advent of multiple parallel machines (via networks) capable of operating entirely out of L1 cache just made the technology available. However, such attacks do rely on known plain text for speed (final test is a simple XOR/alarm if zero. The same technology was used in Colossis back in 1944. It was just a touch slower. The simle answer is message compression prior to encryption which would make deciding when the message was broken much more difficult. Naysayers claim "there is always KPT" but this does not need to be true. - whole months of Enigma traffic went undecoded because there was no crib available but eventually human error gave the BP team a clue. Today, electronic systems can remove such errors from human hands. Personally believe that 56 bits is "good enough" today though it makes little sense from a programming standpoint not to use 64 *so long as a different key is used for every message and every message, no matter how trivial, is encrypted*. Or you could use a "shared secret" book code: a simple XOR with a digital satellite data stream transmitting compressed video should do nicely. All that is needed is to know which stream and when to start. I call that an "unwitting key provider". So as Paul says, the contest proves little except to confirm my 3.5 hour estimate (remember the gentleman in France who broke the 40 bit NS code last year and what his time was...) - but that was for equipment available several years ago. Today I use the figure of one gig kps (keys per second) for 1997 equipment per seive. A single one would break 40 bits in an average of under 10 min. DES would fall in a day to 400 in parallel. But the question remains: without KPT, how can you tell when the break occured ? Is a world of difference between an XOR and decompression. And if every message uses a differnt key... Warmly, Padgett ps WORD virus anti-virus macro is avaliable: http://www.netmind.com/~padgett/ under "Anti-Virus hobby". FreeWare. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~