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."
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`
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
participants (6)
-
Adam Back -
David Lucas -
Lucky Green -
Peter Trei -
Tim May -
Tom Weinstein