Re: Comparing Cryptographic Key Sizes

Adam Back <aba@dcs.ex.ac.uk> writes.

> Below is a explanation of the meaning of cryptographic key sizes which
> started as an explanation I wrote for a journalist friend of mine, on
> being asked about how relatively secure a system using DES and RSA
> (SET) was as compared to netscapes export version of SSL.
 
> It could use some criticism.  If you are not that crypto aware, does
> it make sense to you?  If you are crypto aware, what do you think of
> my off the cuff estimates of hardness?
> 
> 
> 56 bit DES is probably roughly similar to 512 bit RSA in hardness to
> break.

This is way off. We used ~457,000 MIPS years to search half of the 
DES keyspace. Factoring a 512 bit modulus using the General Number
Field Sieve (GNFS) would take about 28,000 MIPS years (see Schneier
for the exact number - I don't have AC2 at hand)

Lenstra has estimated that with 500,000 MIPS years, you should be
able to factor a 600 bit modulus using GNFS, if your workstations 
had enough memory.

[...]

> About 10 years ago now Michael Wiener made a design for such a DES
> breaking machine.  He estimated it would cost $10,000,000 to build a
> machine which would break a 56 bit DES encrypted message a few hours.
> His machine was scalable, pay more money, break the key faster, pay
> less take longer.  The estimate was that could build one with enough
> DES key searching units to break it in a day for $1,000,000.  That was
> 10 years ago.  10 years is a long time in the computer industry.
> Nowadays you build the machine more cheaply as chip technology has
> progressed, and computers are much faster per $.  Estimates are around
> $100,000 to build the machine (neglecting hardware engineers
> consultancy fees).

Go back and check the numbers - if you don't the journalists will. 
(I don't have this paper to hand either :-( ) The Wiener paper is 
much more recent (93?) , and the cost much lower (I think it was 
about $1M for HW and $500K for development costs, for a 3.5 hour 
machine).

Peter Trei
trei@process.com

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

At 09:52 24/06/97 -6, Peter Trei <trei@process.com> wrote:
>Adam Back <aba@dcs.ex.ac.uk> writes.

<...>

>> About 10 years ago now Michael Wiener made a design for such a DES
>> breaking machine.  He estimated it would cost $10,000,000 to build 
a
>> machine which would break a 56 bit DES encrypted message a few 
hours.
>> His machine was scalable, pay more money, break the key faster, 
pay
>> less take longer.  The estimate was that could build one with 
enough
>> DES key searching units to break it in a day for $1,000,000.  That 
was
>> 10 years ago.  10 years is a long time in the computer industry.
>> Nowadays you build the machine more cheaply as chip technology has
>> progressed, and computers are much faster per $.  Estimates are 
around
>> $100,000 to build the machine (neglecting hardware engineers
>> consultancy fees).
>
>Go back and check the numbers - if you don't the journalists will. 
>(I don't have this paper to hand either :-( ) The Wiener paper is 
>much more recent (93?) , and the cost much lower (I think it was 
>about $1M for HW and $500K for development costs, for a 3.5 hour 
>machine).

Relevant section of AC2 is Table 7.1 (page 153)

The numbers referred to above are slightly out:

In 1995, $1M would give you a machine that would break 56-bit DES in 
an average of 3.5 hours

A $10M machine would break 56-bit DES in an average of 21 minutes

[Double the times for an exhaustive keysearch]

<...>
-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.0
Charset: noconv

iQA/AwUBM6/l3+Kk4yfQWUNhEQKW2ACgtC4Jpwy7TCPdXdvUkGuXrwiPDUMAoKD6
1XnG5v2Z9gJzQyrwQ8G4mJ1z
=zOLc
-----END PGP SIGNATURE-----

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
               David Lucas - Test Engineer @ SCO Cambridge.
                          E-mail: davidlu@sco.com

 Opinions expressed within this message are my own and do not necessarily
            represent those of my employer * I am not a lawyer
--------------------------------------------------------------------------
        The light at the end of the tunnel is an oncoming train...
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Re comments that I should re-read the paper, here is what Wiener's
paper says about estimated costs of a specialized DES key breaker:

 $100,000 for a machine to break DES in an average of  35 hrs
 $1 mil   for a machine to break DES in an average of 3.5 hrs
 $10 mil  for a machine to break DES in an average of  21 mins

It was as Peter says published in 1993.

Wiener also budgets for $500,000 in design costs (wages, parts, fab
etc).

Another interesting part of the design is that it is based on a
pipelined chip, clocked at 50Mhz which can try 50 Million keys/sec.

35 hours sounds a reasonable amount of time to break a Swift banking
transfer key protecting trillions of dollars of funds.

Perhaps $10,000 isn't too far off the current day costs of breaking
DES after all.  (500Mhz chips?  You can get dec alphas at that speed,
and thats a general purpose CPU)

(If anybody is short of a copy, I've put the one up I've got (no idea
where I got it from) here:

	http://www.dcs.ex.ac.uk/~aba/crypto-papers/des_key_search.ps
)

Adam
-- 
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`

Adam Back wrote:
> 
> Re comments that I should re-read the paper, here is what Wiener's
> paper says about estimated costs of a specialized DES key breaker:
> 
>  $100,000 for a machine to break DES in an average of  35 hrs
>  $1 mil   for a machine to break DES in an average of 3.5 hrs
>  $10 mil  for a machine to break DES in an average of  21 mins
> 
> It was as Peter says published in 1993.
> 
> Wiener also budgets for $500,000 in design costs (wages, parts, fab
> etc).
> 
> Another interesting part of the design is that it is based on a
> pipelined chip, clocked at 50Mhz which can try 50 Million keys/sec.
> 
> 35 hours sounds a reasonable amount of time to break a Swift banking
> transfer key protecting trillions of dollars of funds.

One thing that I haven't heard anybody mention yet is that if time is
important, you can break keys in an arbitrarily short period of time,
if there's a continuous sequence of transactions.  Assume it takes 35
hrs to crack a key (with 50% probability), This means that you have a
1.4% chance to crack it in one hour.  If you give up after an hour and
pick a new transaction to crack, you have a 50% chance of cracking at
least one transaction after 48 hours, and they will all have been
cracked in less than an hour.

-- 
What is appropriate for the master is not appropriate| Tom Weinstein
for the novice.  You must understand Tao before      | tomw@netscape.com
transcending structure.  -- The Tao of Programming   |

At 10:54 AM -0700 6/24/97, Adam Back wrote:
>Re comments that I should re-read the paper, here is what Wiener's
>paper says about estimated costs of a specialized DES key breaker:
>
> $100,000 for a machine to break DES in an average of  35 hrs
> $1 mil   for a machine to break DES in an average of 3.5 hrs
> $10 mil  for a machine to break DES in an average of  21 mins
...
>35 hours sounds a reasonable amount of time to break a Swift banking
>transfer key protecting trillions of dollars of funds.
>

Show me the money! A DES break that resulted in a loss of several tens of
millions of dollars, suitably publicized, would be both educational and
rewarding.

We often talk about the "threat model." But what's the _profit model_ for
breaking DES?

Can money be made by breaking a SWIFT transfer in approx. 35 hours?

(Personally, I doubt it. Between increasing use of 3DES and "time windows"
which are probably much shorter than tens of hours, I doubt a Wiener
machine would be of much use to a hacker.)

Of course, the payoffs could be huge. If the banking system is really
vulnerable to this sort of attack, then why has some private group not
financed the building of a Wiener machine? (I know many people who could
pay for such a machine out of "spare cash," if the profits/risks were
there; I'm not saying *I* would, of course, only that the amounts are not
so high. The cheapest of the listed machines above is comparable in price
to a Jaguar XK8.)

Is anyone publishing on this? Are the details of the SWIFT and similar
interbank transfer systems available anywhere?

(What kind of out-of-band checksums may exist? What kind of callback
systems? What window of opportunity exists if a single DES key is found? Is
it useful?)

--Tim May




There's something wrong when I'm a felon under an increasing number of laws.
Only one response to the key grabbers is warranted: "Death to Tyrants!"
---------:---------:---------:---------:---------:---------:---------:----
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."

On Tue, 24 Jun 1997, Tim May wrote:
> Is anyone publishing on this? Are the details of the SWIFT and similar
> interbank transfer systems available anywhere?
> 
> (What kind of out-of-band checksums may exist? What kind of callback
> systems? What window of opportunity exists if a single DES key is found? Is
> it useful?)

All this interesting stuff is specified in exhaustive detail in ANSI X9 A10.
http://www.x9.org/

--Lucky

Tim May <tcmay@got.net> writes:
> At 10:54 AM -0700 6/24/97, Adam Back wrote:
> >
> > $100,000 for a machine to break DES in an average of  35 hrs
> ...
> >35 hours sounds a reasonable amount of time to break a Swift banking
> >transfer key protecting trillions of dollars of funds.
> >
> 
> Show me the money! A DES break that resulted in a loss of several tens of
> millions of dollars, suitably publicized, would be both educational and
> rewarding.
> 
> We often talk about the "threat model." But what's the _profit model_ for
> breaking DES?

Who says it hasn't been done?  It's not as if the banks would be keen
to advertise this.

You remember a while back some Russians (including one "mathematician"
according to news reports) had succeeded in fleecing a US bank of
several mil and routing the money to various banks around the world.
Until they got caught.  The news reports said the US bank(s) wanted to
talk to him to find out how he did it.  I was always curious as to
what that Russian did to crack bank security.  I conjecture that it is
possible that he built a wiener machine, and that the bank hushed up
the story.  (And switched to 3DES post haste:-)


Also re. $100k = price of a ferrari and there are plenty of mobsters
around with that kind of money, that price was 1993 price.  Maybe at
1997 prices $100k would get you down to a few hours again.  How small
are the moving windows?

Re. the "profit model" there were several possibilities discussed
around the time the DES crack was starting, before Peter Trei
persuaded RSA to make a challenge.  One was a european ATM card which
had a master DES key, and this was part of some standardisation thing
(each bank had it's own DES key, plus all participating banks allowed
this master key).  But it's not much fun making profit off ATM
machines -- they have cameras in them, and the cash you can draw on
one card in a 24hr period isn't that much.  You'd have to produce
hundreds of faked cards, and have a whole host of accomplices running
around emptying cash machines.  Tricky logistics, many participants ->
increased chance of getting caught.  Not that easy to cash in on.

One factor that hasn't really been discussed much is the possibility
of amortizing cost.  You build the DES breaking machine, and if you
use it to break 1000 DES keys, that's $1k per key.  Starting to open
up even lower end applications with good organisation.

I'm sure there were a couple of things discussed where there were some
interbank transfers which relied on DES.  Moving window means you've
got to break the keys fast, as you say.  Also I wonder how easy it is
to siphon the money and make it disappear with all the auditing.  (aka
may be you could invest 1 mil and build a fast key breaker, transfer
lots of money, but so what if the audit trail points fairly and
squarely at you?  Cash the money quick and buy unconditional
immunity in Belzize?)


btw I now have a text only version of the wiener paper up on:

	http://www.dcs.ex.ac.uk/~aba/crypto-papers/

sans diagrams.  (ps2ascii is your friend).  As well as the postscript.
Some people can't handle postscript.

Adam
-- 
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`