[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Deafening Silence
Shawn,
Your note is very timely. We've been working for the past few days to
clean up the isakmp-oakley draft and bring it more in line with the
main ISAKMP doc. Of course, code modifications will follow.
> >>I also think that the drafts are not concrete enough so that 2
> >>implementer would come up with interoperable implementations.
> >
> > You make a strong bold claim. However, there is an existence proof to
> >the contrary since interoperability of independently-written implementations
> >has ALREADY been shown. For example, the DRA/Malvern implementation written
> >against isakmp-04 talked fine with the cisco UNIX implementation written
> >against isakmp-04. There can be no doubt that the ISAKMP and ISAKMP-Oakley
> >specifications are sufficiently concrete to implement. All the details are
> >there, including all of the magic numbers, in a clean easily-read format.
>
> I don't doubt that this is true. However, I can't find a copy of the
> isakmp-04 draft anywhere. The current draft is isakmp-05. And, if I
> look at that draft, and then look at the isakmp-oakley-00 draft and
> the freely-distributable cisco UNIX implementation, I see a number of
> very crucial differences which are causing a lot of confusion for me
> as an implementor. Just one example (but perhaps the most crucial one):
The interop tests we had with DRA/Malvern were at a time when 04 was the
latest-and-greatest. When 05 came out we developed the reference implelentation.
The code that interoperated with DRA was not the free code.
> The cisco UNIX implementation, which looks to be based largely on
> isakmp-oakley-00, only implements Oakley Main Mode and Oakley Quick Mode.
> Since Oakley Aggressive Mode is cited in the draft as a SHOULD but not
> a MUST, it looks like it complies with the requirements of isakmp-oakley-00.
> But, since it does not implement Base, Identity Protection, or
> Authentication Only exchanges, it cannot be considered compliant with
> the isakmp-05 draft, since those exchange types are MUSTs. Furthermore,
> the XCHG field values used in the implementation *directly conflict*
> with those in isakmp-05! (Oakley Main Mode is 1, Oakley Aggressive Mode
> is 2, and the unused-except-for-debugging-output Oakley New Group Mode
> is 3 - see the ikmpd/isakmp.h source file.)
Correct on both. The free code can not yet be declared as being truely
ISAKMP compliant; and, the XCHG values were not defined in our draft.
You'll also note in ikmpd/isakmp.h that the exchanges as well as other
defines like protocol numbers are accompanied by a remark like "NOT YET
ASSIGNED IN ISAKMP DRAFT". We've known this was a problem; it and several
other inconsistencies are being dealt with presently.
> Clearly, this conflict MUST be resolved one way or another before we
> can ensure that implementations based on the current drafts are
> interoperable. From my (perhaps naive) analysis, Identity Protection
> and Oakley Main Mode look enough like one another that a merger of
> the two should be possible. The Base exchange and Oakley Aggressive
> Mode seem to be relatively close, in terms of the desired functionality,
> but I can't say for certain. Oakley Quick Mode, if it is needed (and
> currently no other exchange type in either draft provides for the
> exchange of IDui and IDur, so I believe it is) will almost certainly
> need a separate exchange type.
A far from naive analysis: this is exactly what has been discussed.
I propose this thread be moved to the isakmp-oakley mailing list
(isakmp-oakley@cisco.com, majordomo@cisco.com for administrivia). If you--
or anyone else-- find any more problems, or inconsistencies that need to
be resolved, please let us know while the ink is not yet dry.
Dan.
Message-Id: <199610111726.NAA18539@jekyll.piermont.com>
To: rgm3@chrysler.com
cc: Stephen Kent <kent@bbn.com>, John Gilmore <gnu@toad.com>, ipsec@TIS.COM
Subject: Re: Short keys * Options, combinations, and negotiations => simplicity
Reply-To: perry@piermont.com
X-Reposting-Policy: redistribute only with permission
Date: Fri, 11 Oct 1996 13:26:21 -0400
From: "Perry E. Metzger" <perry@piermont.com>
Sender: ipsec-approval@neptune.tis.com
Precedence: bulk
Robert Moskowitz writes:
> At 08:05 PM 10/8/96 -0500, Stephen Kent wrote:
> >Moreover, in selecting any safeguard, one
> >must balance percieved threats against costs. While you clearly precieve
> >NSA as a threat, I don't find that most of my commercial clients share that
> >view. They are more concerned about hackers, criminals, and other
> >adversaries for whom DES is a reasonable countermeasure.
>
> Our industry has already faced government backed industrial espionage. Not
> NSA backed, but their competitors....
I must also state that corporate threats are not out of the question,
either. Dr. Kent's statement that his commercial clients may not be
worried could very well be correct (my clients are worried but his may
not be). That is, however, unimportant. Most corporate executives do
not understand cryptography and thus do not know what is necessary.
Luckily, we don't have to rely on opinion, we can rely on solid
engineering and math for this judgement.
All cryptography is economics. The point at which you have enough
security in a commercial environment is easy to define -- breaking
your codes must cost more than the information protected is worth.
According to the paper "Minimal Key Lengths for Symmetric Ciphers to
Provide Adequate Commercial Security"*, by Blaze, Diffie, Rivest,
Schneier, Shimomura, Thompson, and Wiener, for an initial investment
of $10Million, a device may be made which will successfully break DES
keys in six minutes each, at an amortized price of $38. For an
investment of $300k, one can break the keys in three hours for the
same amortized price.
It is clear that for any corporate secret worth more than $38, DES is
inadequate.
If you think an investment of $10 Million, or even $300k, is
improbable, think again.
In my particular industry group (the financial industry), an
expenditure of a few million dollars to break someone's traffic might
be a a very lucrative (if highly illegal) investment, and if the
amortized cost of a single break was only $38, the expense would be
considered inconsequential by many unscrupulous people. Indeed, with
that low an amortized cost, one could afford strategies that would
prevent being caught. If the amortized cost was high, you would need
to make a big killing which might lead to your discovery, but with an
amortized cost of $38, you could afford to make just a few hundred
here and a few thousand there, indefinitely. You could, for example,
front run trades for MONTHS, and have your pattern of activity look
nearly innocent.
Even outside my industry, it is not unreasonable to expect such
investments to be made. These investments are not, in the greater
scheme of things, large, and as I have noted, the amortized cost of
any individual crack is smaller than a businessman's lunch.
In other words, any thought that DES is adequate is simply wrong (no
disrespect intended to Dr. Kent, who I admire). If your information is
worth more than $38, its worth more than DES. (By the way, the same
paper places the cost per crack of a 40 bit key at around eight CENTS,
with an investment of $400 -- "exportable" crypto isn't worthwhile if
you expect *any* serious attempt at all).
I think the conclusion statement from the paper is worth
quoting. "Bearing in mind that the additional computational costs of
stronger encryption are modest, we strongly recommend a minimum
key-length of 90 bits for symmetric cryptosystems."
*The paper by Blaze et all is available from
ftp://ftp.research.att.com/dist/mab/keylength.ps
ftp://ftp.research.att.com/dist/mab/keylength.txt
Perry
PS It has been contended by the NSA in a document circulated in
Washington that the paper by Blaze et al is wrong. I will quote their
response to this contention here in order to cut off any argument in
advance. This document is also available as
ftp://ftp.research.att.com/dist/mab/keylength.nsa
----------------------------------------------------------------------
July 18, 1996
There is currently being circulated, to members of Congress and
possibly elsewhere, a four page document entitled ``Brute-Force
Cryptanalytic Attacks'' that calls into question some of the
conclusions of the ``Minimum Key Lengths for Symmetric Ciphers'' white
paper [1]. The document bears no author or organization attribution,
but we are told that it originated from NSA.
The NSA document argues that ``physical realities'' make parallel key
search much more expensive and time consuming than our white paper
estimated. However, the NSA document appears to have been written
from the perspective of general parallel processing or cryptanalysis
rather than exhaustive key search per se. It ignores several
elementary principles of parallel processing that apply specifically
to exhaustive key search machines of the type that our white paper
considered.
In particular, NSA argues that interconnections, heat dissipation,
input/output bandwidth, and interprocessor communication make it
difficult to ``scale up'' a key search machine by dividing the task
among a large number of small components. While these factors do
limit the scalability of more general purpose multiprocessor computers
(such as those made by Cray), they do not apply at all to specialized
exhaustive key search machines. The NSA argument ignores the most
fundamental feature of brute-force key search: the processors
performing the search have no need to communicate with other
components of the system while they perform their share of the search,
and therefore the system has no need for any of the global
interconnections that limit scaling. Indeed, there is no reason that
all the components of a parallel search machine must be located even
within the same city, let alone the same computer housing. We note
that one of our co-authors (Eric Thompson, of Access Data, Inc.)
designs and builds medium-scale FPGA-based key search machines with
exactly this loosely-coupled structure, and regularly uses them to
recover keys for clients that include the FBI.
The NSA document also calls into question our cost estimates for ASIC
components, suggesting that ASIC chips of this type cost NSA
approximately $1000.00 each. However, our $10.00 per chip estimate is
based on an actual price quote from a commercial chip fabrication
vendor for a moderate-size order for an exhaustive search ASIC
designed in 1993 by Michael Wiener [2]. Perhaps NSA could reduce its
own costs by changing vendors.
Finally, the NSA report offers estimates of the time required to
perform exhaustive search using a Cray model T3D supercomputer. This
is a curious choice, for as our report notes, general-purpose
supercomputers of this type make poor (and uneconomical) key search
engines. However, even the artificially low performance results for
this machine should give little comfort to the users of 56 bit keys.
According to NSA, 56 bit keys can be searched on such a machine in
less than 453 days. ``Moore's law'' predicts that it will not be long
before relatively inexpensive general-purpose computers offer similar
computational capability.
/s/ Matt Blaze
Whitfield Diffie
References:
[1] Blaze, M., Diffie, W., Rivest, R., Schneier, B., Shimomura, T.,
Thompson, E., and Wiener, M. ``Minimum Key Lengths for Symmetric
Key Ciphers for Commercial Security.'' January 1996. Available
from ftp://ftp.research.att.com/dist/mab/keylength.txt
[2] Wiener, M. ``Exhaustive DES Key Search.'' Presented at
Crypto-93, Santa Barbara, CA. August 1993.
=========================================================================
[Transcription of document circulated to various members of congress
and others in June, 1996, apparently by NSA]
BRUTE-FORCE CRYPTANALYTIC ATTACKS
Two published theoretical estimates of cost versus time to perform
brute-force hardware attacks on selected cryptography key lengths
differ between themselves and differ significantly from what we find
when we buy or build computers to carry out such attacks.
The differences lie in assumptions made in the theoretical estimates,
which are not fully spelled out by the authors, and in scaling up
hypothesized small machines to ever larger ones without accounting for
physical realities.
The factors not accounted for are:
o R&D costs for the first machine, typically on the order of $10
million.
o As more and more chips are added to a machine, two effects occur:
o Interconnections increase and increase running time;
o Heat from the chips eventually limit [sic] the size of a
machine.
o Memory costs are not included.
o When get [sic] to the very fast processing speed estimates,
machines can become Input/Output bound; so [sic] it cannot achieve
the estimated speed.
o Assuming every algorithm can be tested in same amount of time and
key length is the only difference.
Table 1 are [sic] the average time estimates made for a given cost
done by Michael Wiener of Bell Norther Research in 1995. These are
published in Bruce Schneier's Applied Cryptography book.
Note that these are average times, one-half of the total exhaust time.
Table 2 are [sic] the estimates for total exhaust times using Field
Programmmable Gate Arrays (FPGA) and Application Specific ICs (ASICs)
done for the Business Software Alliance by Blaze, Diffie, Rivest,
Schneier, Shimomura, Thompson, and Wiener in 1996. In addition to the
above factors not accounted for they have assumed ASICs cost as low as
$10. We find ASICs more typically cost $1000 and their capabilities
can vary considerably depending upon the specific task.
Table 3 are out estimates based on our experience with a Cray T3D
supercomputer with 1024 nodes. This machine costs $30 million.
[Tables 1, 2, and 3 not transcribed here.]
----------------------------------------------------------------------