Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!snorkelwacker.mit.edu!apple!olivea!decwrl!mcnc!ncsuvx!news From: setzer@matagh.ncsu.edu (William Setzer) Newsgroups: comp.org.eff.talk Subject: Re: Encrypting your data to keep it private Message-ID: Date: 7 Jan 91 03:27:00 GMT References: <6748@crash.cts.com> <61912@bbn.BBN.COM> Sender: news@ncsuvx.ncsu.edu (USENET News System) Followup-To: comp.org.eff.talk Organization: NCSU Math Dept. Lines: 95 In-reply-to: lear@turbo.bio.net's message of 6 Jan 91 23:20:48 GMT lear@turbo.bio.net (Eliot) writes: :In comp.org.eff.talk there has been some question as to whether DES :has been tampered with. I would appreciate someone from sci.crypt :explaining in laymen's terms the various issues involved. I will assume that everyone knows how DES works, ie. you have some text and a key, and you encrypt the text with the key via DES. Ok, you send it to a "friendly", and he wants to know if you actually sent it. Well, the easiest way is for the friendly to decode the message with the key. If he gets gibberish (which he is almost certain to get if the key is wrong), then the message is bogus. But what if he gets an understandable message? Someone _might_ have discovered the key, and sent a bogus message. Or even worse, the "friendly" may have decided to fake a message from you, and since he knows the key, it's trivial. How do we protect you _and_ the friendly from forgery or denial? What needs to be done is "authentification". There are many ways to do this. Here is one described in Konheim, _Cryptography, A Primer_ (not really a primer, BTW): In some secure way, person A and person B exchange a long list of "signatures". Think of them as functions, so A gets a big list of functions f(b_i, C), and B gets a big list of functions g(a_j, C), where C is some message that both A and B know. Given the a_j's and b_i's, both A and B know how to calculate f and g, but only A knows the a_j's and only B knows the b_i's. (And, in practice, it's hard to find the a_j's and b_i's, even if you know C, f, and g.) In front of some trusted third party, they sign that the lists each receives is identical (ie. A acknowledges that the g(a_i, C)'s are correct in front of B and a witness, and vice versa.) Let's call this the contract. Now, suppose A wants to send message M to B. When A sends M to B, A calculates 21 signatures, say g(a_k1, M), ..., g(a_k21, M) and appends them to the message. B then asks A for 10 of the a_j's, in the range of a_k1, ..., a_k21, *B's choice,* say a_m0,...,a_m9. B calculates g(a_m0, C), ...,g(a_m9, C) and checks to see that they are in the contract. He also calculates g(a_m0, M),...,g(a_m9, M) and checks them against A's signature in the message. If everything matches, then B says "OK, I believe you". Now let's see what happens if either A or B cheat. Suppose A tries to deny sending the message. Then B gives the message M, his list of g(a_j, C)'s, and the 10 revealed keys a_m0, ..., a_m9 to that trusted third party. The third party requires A to give him the 21 keys, a_k1, ..., a_k21. Then the third party calculates g(a_k1, C), ..., g(a_k21, C) and checks them against the contract. If they don't match, then A has obviously cheated by not coughing up the right keys. Well, suppose they did match. Then the third party uses a_k1,...,a_k21 to calculate g(a_k1, M), ...,g(a_k21, M). If they match, A has to fess up, since A was the only one who knew the 21 keys, so is the ony one who could have calculated the 21 signatures at the end of M. (Since B has a_m0,...,a_m9, and they match g(a_m0, C), ...,g(a_m9, C), and only A knows the a_j's, only A could have given B the a_m0,...,a_m9. Thus A can't deny that a message was sent.) Now suppose B forged a message, and tried to forge the 21 signatures. A just gives his 21 keys a_k1,...,a_k21 to the trusted third party. The third party gets B's a_m0,...,a_m9 and calculates g(a_m0, C), ...,g(a_m9, C) to see if they match. If not, then B gets caught since he doesn't have 10 of A's keys. Suppose they match. Then the third party will verify that A's keys are correct by calculating g(a_k1,C), ...,g(a_k21, C). He then calculates g(a_k1, M),..., g(a_21, M) and compares them to the signatures on M. Since B didn't know but 10 of the 21 keys, there is a very high probability (over 999999 in 10^6 for the curious) that 11 of the signatures won't match. B gets caught. Whew! Maybe I said way too much. Anyway, this is a typical method of authenticating DES transmissions. Of course, the hard part is exchanging the f's and g's, because you can't reuse them safely. (And the game is over if an "unfriendly" obtained either the list of a_j's or b_i's). But, it protects both A and B from tampering, since there is a way to verify the participation of both A and B. In a fairly unrelated statement, Eliot mentions: :Although the people in sci.crypt probably have a better handle on it :than he did, Bamford claims that the NSA convinced IBM to shorten the :key from 128 bits to 56. A cryptosystem is at most as strong as its keys. You can break DES in 2^56 tries, by trying all the keys. Recently, two people (Shamir and Binam?) developed a method of cryptanalyzing "standard" DES that took at most 2^56 tries. So it turns out that a larger key does you no good, since there is a better method available than trying all the keys. These two people also discovered that any tampering with the S-boxes actually helps the method break DES faster. (This indicates to some people, including myself, that the NSA knew about this method, and adjusted DES accordingly. They strengthened the S-boxes against it, and shortened the key to 56 bits, since they knew more did no good. Of course, all this in parentheses is all IMHO.) I'm afraid I don't read comp.org.eff.talk, so I won't be around to answer any followups. However, I would be glad to answer any questions you may have via e-mail. William Setzer setzer@matagh.ncsu.edu