EVERHART%ARISIA@rca.COM ("GLENN EVERHART, 609 486 6328") (06/18/87)
Over the last two or so years, I've heard from a variety of places that the Data Encryption Standard, which NSA is decertifying, produces ciphers which can be broken in about 1.5 hours on an IBM PC (presumably much faster on VAXen... :-) ). These have been from sufficiently reliable sources that I've been inclined to believe the stories, though I have no clearances in crypto compartments, etc... Recently I was speaking with a DECUS buddy about the famous VMS security hole and our conversation wandered into this area. He remembered seeing an article 7 or 8 years ago (1979 or 1980 more or less) in the Proceedings of the Soviet Academy of Science which discussed pruning decision trees in DES ciphers in its' first part. Apparently the article, which he described as heavily mathematical, gives the basis for finding LARGE equivalence classes of keys so that DES can be broken by testing far fewer than 2**56 possible keys. Enough fewer that 1-2 hours on a PC sounded about right. (The second part of the article gives conditions necessary for public key ciphers not to be trivial to break.) The article was in English translation, by the way, so the original may have been a bit earlier. I don't live near any library big enough to have that journal and am wondering if anyone out there in netland who's interested in these matters would be good enough to hunt the reference up and post it? Maybe that way the community can avoid some dangerously weak ciphers where they need to be strong... (I've also heard that repeated applications of the unix or Software Tools "Crypt" tool, with relatively prime key lengths, can be VERY VERY much stronger than one would expect...) Glenn Everhart Everhart%Arisia@rca.com