mlm@NL.CS.CMU.EDU (Michael Mauldin) (02/29/88)
In article <4051@megaron.arizona.edu>, mike@arizona.edu (Mike Coffin) writes: > From article <996@sdcc13.ucsd.EDU>, by ln63wgq@sdcc13.ucsd.EDU (Keith Messer): > > I don't expect I'm even close to the smartest person who's worked on the > > problem, but if my approach isn't going to work, I'd like to hear why. > > Perhaps you have a really nifty job and are a bright guy, but you're acting > > like a geek. > > I guess this is directed at me, despite the subject line. Well, I > don't have a nifty job --- I'm just another lowly grad student --- but > I don't see how I was acting like a geek. I didn't even say your > approach wouldn't work. Ingrid Schaumuller-Bichl of Austria had a paper in Eurocrypt 82 (actually Lectures Notes in Computer Science #149, Cryptography, by Springer-Verlag, 1983) about finding the complexity of DES (DEA in Europe) by representing each output bit as an XOR-sum-of-products (an idea originally due to M.E. Hellman of Stanford in 1976). He was able to make significant progress on S-P systems using linear S-boxes, and also gives the XOR-sop exprfessions for each of the 8 S-boxes. His conclusion was that the computers fast enough and large enough to simplify the polynomials that arise would probably be able to "brute-force" search the DES key. He also suggested a meet-in-the- middle attack where the intermediate variables after the 8th round of substitution/permutation are expressed in terms of both the inputs and the outputs, giving a far simpler system of 64 equations in 56 unknowns. So Keith, keep plugging on that simplifier, because that's a good idea. And Mike, lighten up. If he doesn't know how hard a problem he's working on, he might just solve it. And let's not call each other geeks, okay? Michael L. Mauldin (Fuzzy) Department of Computer Science ARPA: Michael.Mauldin@NL.CS.CMU.EDU Carnegie Mellon University Phone: (412) 268-3065 Pittsburgh, PA 15213-3890