[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: 40-bit RC5 crack meaningless??
[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 <[email protected]>
To: "'[email protected]'" <[email protected]>
Subject: Further to Goldberg's Cracking Accomplishments
Date: Wed, 5 Feb 1997 13:58:53 -0800
Paul A. Strassmann <[email protected]> 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: [email protected]
From: "Timothy C. May" <[email protected]>
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: [email protected]
>From: Patrick Galley <[email protected]
>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" <[email protected]>
>From: "Paul A. Strassmann" <[email protected]>
>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,
[email protected] 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" <[email protected]>
To: "Betty G. O'Hearn" <[email protected]>
Subject: RSA
> Date: Thu, 30 Jan 1997 20:10:36 -0500
> To: "Wright Larry" <[email protected]>
> From: "Paul A. Strassmann" <[email protected]>
> 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: [email protected]
From: Bob Stratton <[email protected]>
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"
<[email protected]>
To: [email protected]
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.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~