home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7074 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  2.9 KB
  1. Path: sparky!uunet!nntp1.radiomail.net!csl.sri.com!boucher
  2. From: boucher@csl.sri.com (Peter K. Boucher)
  3. Newsgroups: sci.crypt
  4. Subject: Re: DES (Was: Re: 800MHz
  5. Date: 21 Jan 1993 23:03:08 GMT
  6. Organization: Computer Science Lab, SRI International
  7. Lines: 63
  8. Distribution: world
  9. Message-ID: <1jna3cINNeed@roche.csl.sri.com>
  10. References: <1444.204.uupcb@ssr.com> <1993Jan9.163011.23230@csi.uottawa.ca> <1993Jan10.050811.3740@ils.nwu.edu> <1993Jan10.060013.4644@csi.uottawa.ca>
  11. NNTP-Posting-Host: affirmed.csl.sri.com
  12.  
  13. cbbrowne@csi.uottawa.ca (Christopher Browne) writes:
  14.  
  15. >If it "only" costs $56, then they must have some CHEAP ways to break
  16. >DES, unless they're COMPLETELY ignoring the cost of computer
  17. >resources.  In short, for $56 a pop, they can't be using brute force.
  18. >Maybe they can use differential analysis.  Maybe they can use
  19. >something analogous to D.A.  But for $56 per pop, they're either
  20. >lying, or they have SOME "silver bullet."
  21.  
  22. Of course, the risk of a trap door has never been completely 
  23. negated.  However, notable experts disagree with you about the
  24. cost of a brute-force attack.  Dr. Hellman (see my previous post)
  25. maintains that it costs between $10 and $100 to break a DES key
  26. by brute force (if you can afford the $1M to $10M startup costs,
  27. and if you keep the DES-breaking machine continuously busy).  
  28.  
  29. Dr. Ron Rivest (the "R" in RSA) also gave a talk where he showed
  30. the following:
  31.  
  32.           DATE 
  33. BUDGET       | 1993   2003   2013
  34.       -------|------|------|------
  35.       $25K   | 47   | 52   | 57
  36.       -------|------|------|-----
  37.       $25M   | 60   | 65   | 70
  38.       -------|------|------|-----
  39.       $25G   | 73   | 78   | 83
  40.  
  41. The cells represent the bit-size of the largest key that an
  42. organization with a certain-size budget could afford to break
  43. by brute force.  It was assumed that decryption times would be
  44. about the same as for DES.  Thus, a small country, a drug cartel,
  45. or anyone else with $25M to spend could afford to brute-force
  46. attack DES (which has 56 bits - less than 60).
  47.  
  48. Interestingly enough, exportable crypto implementations (40 key-
  49. bits or less) can be broken by the local cops, a group of grad
  50. students, or anyone else with $25K to spend.
  51.  
  52. The French equivalent of NSA has made it public that they consider
  53. it their duty to spy on American firms and give the data to French
  54. firms.  They could afford the $25G.
  55.  
  56. He made a similar table for RSA keys:
  57.  
  58.           DATE 
  59. BUDGET       | 1993   2003   2013
  60.       -------|------|------|------
  61.       $25K   | 400  | 450  | 550
  62.       -------|------|------|-----
  63.       $25M   | 600  | 700  | 850
  64.       -------|------|------|-----
  65.       $25G   | 900  | 1050 | 1200
  66.  
  67. So, 512-bit RSA keys aren't looking so great anymore.  1024-bit
  68. keys seem barely adequate in this light.  2K- to 3K-bit RSA keys
  69. seem prudent to protect any data that you are seriously 
  70. concerned might be attacked by a big-budget ($25G) enemy.
  71.  
  72. -- 
  73. Peter K. Boucher
  74. --
  75. RIPEM public key available upon request.
  76.