Tim_C_May@cup.portal.com (03/09/89)
There have recently been several postings claiming that the Soviets published a method for cracking DES in an hour on an IBM PC. Strangely, nobody can find this mysterious paper, nor can they explain why the Soviet government--not known for its belief in free speech and academic freedom-- would allow such a piece of dynamite to be published. Finally, none of the postings have discussed whether this purported cracking is of the full-blown DES standard, or a reduced-length key (e.g., a 32-bit key), or even some particular vendor's attempted implementation of DES (such as the version of "DES" that only allows 6-character passwords!). It might even be just another "dictionary attack" on a password file....that fits with the one hour number cited. In any case, I still maintain that the burden of proof, in the context of this discussion, is on those who claim DES can in fact be broken as described. Since this discussion in sci.crypt is based on a crossposting from comp.misc, I thought I'd repeat the original posting I made there. I'd have crossposted there myself, except I thought my discussion would be unnecessary for sci.crypt readers. Here it is: >>In a recent posting in comp.misc, friedman@porthos.rutgers.edu states: >>>> >>>>Not that I agree with Dave's intention of restricting the distribution >>>>of the Virsus TR. (I'd love to read a copy) However, DES is a bad >>>>example. Because the DES algorithm is so well known, it is no longer >>>>considered very secure. Any organization with a fast Cray can crack >>>>it in 8-10hrs. Sure, its more than you can do with your Apple II, but >>>>lots of organizations can do it. >> >>I would like to see some justification for this remark about how easy it >>is to bust DES. Diffie and Hellman looked into a "brute force" breaking >>of DES such as you describe in 1975 and concluded that a special purpose >>"DES-buster" computer could be built with tens of thousands of >>one-key-per-microsecond custom chips. They have slightly modified their >>estimates, as have others. And it may well be that NSA or others have >>built such a box, but this is unknown. >> >>Saying that a Cray can do it in tens of hours is wrong (roughly 10 to the >>17th keys need to be examined...figure it from there). There is an >>incredible financial incentive to break DES: the banking system bases >>its transfers on DES. Maybe some superhacker has indeed done it ad just >>isn't saying, but there's no evidence that a few dozen hours on a Cray >>unlocks the billions of dollars a day of these transfers. >> >>The possibility that DES has built-in weaknesses in the S-boxes, placed >>there by the NSA to deliberately weaken DES, is possible but is unsupported >>by any solid evidence. Numerous technical papers presented at the Crypto >>conferences have reported on searches for such signs of weakness (such as >>cycles) and have found none. This doesn't mean it's "strong" of course, only >>that nobody has publicly reported a cracking of it. >> >>By the way, the fact that the algorithm is publicly known is part of its >>strength and part of its design: the algorithm can be subjected to analysis >>that a "secret" algorithm cannot. Some new COMSEC algorithms being pushed >>by NIST (formerly NBS) and NSA/NCSC are secret, however. >> >>Understand that I am not claiming DES is the best, or is even particularly >>good. Personally I'm more interested in asymmetric (public key) systems, but >>their speeds just aren't up to DES-type speeds for raw data transfer. >> >>Timothy C May Tim_C_May@cup.portal.com So, before the "Soviets broke DES in an hour on a PC" statement becomes a factoid and gains even greater currency, let's see some proof. Tim May Aptos, CA Tim_C_May@cup.portal.com
foo@Portia.Stanford.EDU (castor fu) (03/10/89)
Although the Russian rumor is suspect, in a class I have been sitting in on the professor said that Adi Shamir (MIT) claims to have broken (in some sense which is not clear) a modified DES where only 8 rounds of encryption instead of the normal sixteen are used. This is very recent news, coming from SECURICOM '89, a crypto conference held just a week or so ago. He supposedly did this in 170 seconds on an IBM PC! I guess people will have to wait for the proceedings for details, although there may not be many because this work is probably proprietary, since Shamir is the "S" in RSA. I think that this may have involved particularly weak keys (in which case it is not surprising) or a weak plaintext (very interesting!). -Castor Fu foo@portia.stanford.edu
ymchee@water.waterloo.edu (Yeow Meng Chee) (03/12/89)
In article <800@Portia.Stanford.EDU>, foo@Portia.Stanford.EDU (castor fu) writes: > Although the Russian rumor is suspect, in a class I have been sitting in on > the professor said that Adi Shamir (MIT) claims to have broken (in some sense > which is not clear) a modified DES > where only 8 rounds of encryption instead of the normal sixteen are used. > ^ ^^^^^^^ > > -Castor Fu > foo@portia.stanford.edu There is a general phenomena called Combinatorial Explosion which is inherent in many combinatorial problems: for any problem, there is an integer N such that it is possible to solve the problem of size N-1 by hand, the problem of size N can be solved on a computer, and the problem of size N+1 cannot be solved on even the fastest computer around in reasonable time. So breaking DES with 8 rounds does not really imply that DES with 16 rounds can be broken in reasonable time.