pkenny1@ub.D.UMN.EDU (Pat "Hack #2" Kenny) (05/06/87)
I have written a DES program in pascal for a term project and I have to do a talk about it soon and I would like to ask some questions for anybody to respond to, thanks in advance. 1. How much is DES used and who uses it? 2. Does anybody really know what the numbers in the S-Boxes are and where they got them. 3. Where is the DES implemented? I heard about it being put into those instant cash machines, is that true? 4. Does anybody know about the DES and unix, I know they use it there, but how much did they change it? 5. What does the NSA know about the DES that we don't? Do they have a machine to crack it? 6. Are there any DES jokes or other names for DES? Thanks, any help would be helpful. -------------------------------------------------------------------------- Pat Kenny on the edge of infinity (DULUTH MN). Come and see what it looks like. ---------------------------------------------------------------------------
simsong@mit-amt.MEDIA.MIT.EDU (Simson L. Garfinkel) (05/07/87)
In article <599@umnd-cs.D.UMN.EDU> pkenny1@ub.UUCP (Pat "Hack #2" Kenny) writes: >2. Does anybody really know what the numbers in the S-Boxes are and where > they got them. This is classified. >4. Does anybody know about the DES and unix, I know they use it there, but > how much did they change it? A varient of DES is used in cypt(3) call (used for password encrypting). It uses different s-boxes so that you can't use a DES chip to break unix passwords. (Instead, you have to use Bob Baldwin's program.) >5. What does the NSA know about the DES that we don't? Do they have a machine > to crack it? This is also classified.
rotondo@ernie.Berkeley.EDU (Scott Rotondo) (05/07/87)
In article <599@umnd-cs.D.UMN.EDU> pkenny1@ub.UUCP (Pat "Hack #2" Kenny) writes: > 1. How much is DES used and who uses it? DES is widely used for commercial and government (non-military) encryption. It is due to be recertified in a year or two, and chances are it will not be considered to be secure enough. The new scheme the NSA is pushing puts them in the role of key distributor, and it keeps the algorithm secret. Not the way to do a realistic encryption system. At any rate, assuming it is not recertified, current levels of usage should decline (except electronic banking, see below). > 2. Does anybody really know what the numbers in the S-Boxes are and where > they got them. Everyone knows what the numbers in the S-boxes are (you had to know to write your program), but how they arrived at those numbers is still classified. > 3. Where is the DES implemented? I heard about it being put into those > instant cash machines, is that true? DES is the standard system used in electronic funds transfers, including automated tellers. This is the one area where the NSA proposes that the government continue to use DES, as the Treasury Dept. does a lot of funds transfers. > 4. Does anybody know about the DES and unix, I know they use it there, but > how much did they change it? DES is used in the Unix crypt(3) function (NOT crypt(1)) to encode passwords. The algorithm is DES except that the initial permutation is altered to one of 4096 possibilities by the first two characters in the passwd file entry, known as "salt" bits. This makes it impossible to encrypt common words and then check them against all the passwd entries looking for a match. > 5. What does the NSA know about the DES that we don't? Do they have a machine > to crack it? The main thing that NSA knows is the way in which the S-box numbers were derived. There has been speculation without proof that there is a trap door here to allow the NSA to crack it. There has also been speculation that the NSA cannot crack DES, and that is why they are pushing for a new standard where they control the keys and the algorithm. > 6. Are there any DES jokes or other names for DES? The only other name I can think of is Digital Encryption Standard, which some people think DES stands for instead of Data Encryption Standard. Hope this is helpful. -- Scott
gwyn@brl-smoke.ARPA (Doug Gwyn ) (05/07/87)
In article <18742@ucbvax.BERKELEY.EDU> rotondo@ernie.Berkeley.EDU.UUCP (Scott Rotondo) writes: >The main thing that NSA knows is the way in which the S-box numbers were >derived. There has been speculation without proof that there is a trap >door here to allow the NSA to crack it. There has also been speculation >that the NSA cannot crack DES, and that is why they are pushing for a new >standard where they control the keys and the algorithm. Although I haven't studied DES very hard and don't have any inside (i.e. classified) information about DES, from a previous life as a part-time cryppy I don't see how DES could be considered unbreakable, in the absence of sufficiently frequent key changes. This follows from very general information-theoretical considerations. Because of the complexity of the encryption algorithm, the unicity distance is probably rather large, but it wouldn't be infinite. On the other hand, it is probable that it would take knowledge that only NSA and similar organizations tend to have to routinely break DES using economically feasible expenditure of resources. Since I have to be careful not to discuss anything about this subject for which I can't point to publicly-available descriptions, suffice it to say that the articles I've seen on cryptography in the open literature don't hold a candle to the ones I used to read in the NSA Technical Journal. I would bet that NSA can break DES any time they so choose, if they have a large enough contiguous sample of the cipher stream; "trap doors" shouldn't be necessary. The newer proposal for general government encryption amounts to a reversion to the military way of doing business; they have always classified both the keys and encryption system details (algorithms). Even though it's taken for granted in the cryppy business that the "opposition" sooner or later determines the details of the encryption system, it still makes sense to try to delay their doing so. The keys of course must be protected. (So-called "public key" systems attempt to make the latter unnecessary, but I wouldn't place reliance on the opposition's lack of sufficient cleverness or dumb luck to protect anything of very great value.) Consider this: If NSA can really design a truly secure system for government use, then they sure as hell wouldn't want everyone whose traffic they read to learn how to do the same. It is perfectly natural that no details of how critical aspects of a secure cryptosystem are determined are made public. (Personally I would love for there to be a universally-used secure system, since I value privacy. But virtually no government operates on such abstract considerations; rather they attempt to attain short-range advantage over other governments as expeditiously as possible. I wish ours were different, and think it once was.) In summary, I don't think there is a conspiracy on NSA's part, and I estimate NSA's capabilities to be higher than other people seem to think. (I suspect NSA is happy to be underestimated.)
rotondo@ernie.Berkeley.EDU.UUCP (05/07/87)
In article <5841@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn) writes: > Although I haven't studied DES very hard and don't have any inside > (i.e. classified) information about DES, from a previous life as a > part-time cryppy I don't see how DES could be considered unbreakable, > in the absence of sufficiently frequent key changes. This follows > from very general information-theoretical considerations. Because of > the complexity of the encryption algorithm, the unicity distance is > probably rather large, but it wouldn't be infinite. [ ... ] > I would bet that NSA can break DES any time they so choose, if they > have a large enough contiguous sample of the cipher stream; "trap > doors" shouldn't be necessary. Let me start with the disclaimer that I have access only to the open literature on the subject, so your information may be more reliable than mine. My understanding of the information theoretic argument is that the unicity distance indicates the approximate amount of ciphertext needed to break the cipher using infinite computational resources. As is the case with all systems except one-time pads, the unicity distance for DES is quite finite (about 18 chars). However, actually doing the computation seems to require an exhaustive search of 2^55 keys (not 2^56 because of a known symmetry in the S-boxes). The only apparent way to reduce this search is to know about a trap door in the S-boxes (or elsewhere, but I don't see where). I probably should have pointed out in my previous posting that a perfectly valid reason for the NSA to be pushing for a new standard is that the old one just isn't secure enough. A search of 2^55 keys isn't as prohibitive as it once was [see several papers by Martin Hellman]. Still, if I had to choose, I'd prefer that we use DES with longer keys or multiple encryption rather than trusting the NSA to hold the keys. This is probably their main reason for wanting the new system, but being able to read everyone's mail is a nice fringe benefit. > (So-called "public key" systems attempt to make [protecting keys] > unnecessary, but I wouldn't place reliance on the opposition's > lack of sufficient cleverness or dumb luck to protect anything of > very great value.) Does "sufficient cleverness or dumb luck" mean finding a way to factor large numbers or something else? My main objection to public key systems is that they are just too slow. -- Scott
baldwin@eddie.MIT.EDU (Robert W. Baldwin) (05/08/87)
> From: pkenny1@ub.D.UMN.EDU (Pat "Hack #2" Kenny) >1. How much is DES used and who uses it? >3. Where is the DES implemented? I heard about it being put into those > instant cash machines, is that true? ATM machines use DES to validate the users Personal Identification Number (password). Your card has a number on it which is the result of applying a DES based function to your PIN and your account number. When you type in your PIN, the ATM performs this function and lets you continue if the result matches the number on the card. The DES function uses a secret key that is coded in the ATM's DES circuits. If you know this master key you can manufacture fake ATM cards. If you find/make an ATM that cannot speak to the bank to verify account numbers, then you can withdraw money using the fake card. The situation is more complicated for inter-bank transactions that require remote verification of the PIN. The link between the bank and the ATM is not encrypted. The machines could be designed in such a way that this is not a security hole, but I have heard that this is not the case. In order to make it easier for the banks to change the behavior of ATMs, they included features that make it possible to spoof the machine into despensing money provided the ATM has been given a valid card and somehow ended up in an error state (e.g., cash was not removed from the cash drawer). >2. Does anybody really know what the numbers in the S-Boxes are and where > they got them. Adi Shamir noticed an interesting pattern in the s-boxes, but he has not come up with a way to exploit the pattern. In fact, the pattern may be a strength. Basically, the parity of the output of each s-box (the xor of all four bits) is almost completely controlled by one of the input bits. That is, if you tell me the value of just one of the input bits, I can predict the parity of the output bits, and I will almost always be right. There are values for the other 5 input bits that will make me wrong, but I will be right for most of the 32 possible values of the 5 other input bits. >4. Does anybody know about the DES and unix, I know they use it there, but > how much did they change it? The Unix file encryption program uses a weak variant of the Enigma cipher system which the Germans used during WWII. The October 1984 issue (v63 n8) of the ATT Bell Labs Technical Journal (pg 1673-1683) has an article by Jim Reeds and Peter Weinberger on breaking this cipher system. I wrote an interactive workbench, CBW, for break the cipher and it is about to be distributed on mod.sources. If you must use the Unix file encryptor, run your file through compress or compact first. The Unix password hashing function is based on DES. Basically, your password is used as the key to encrypt the constant zero 25 times. The result is compared against a number in /etc/passwd, and if they match, you are let in. More precisely, there are 4096 variants of DES and the specific one that is used is specified by two 'salting' characters that are in your line of the password file. Thus, the login program asks for your username, looks you up in the password file to find out which variant to use, and then ask for your password. The password and the two salting characters are passed to a function called crypt (not to be confused with the file encryption program with the same name) that performs the 25 iterations of the salted DES and returns a result that can be compared with the 'encrypted' ('hashed' would be a better term) password in your line of /etc/passwd. The salting effects the expansion function, E, not the S-Boxes, as simson@amt said, nor the initial permutation, IP, as rotondo@ernie said. The strength of DES depends on the details of the S-boxes so fooling with those is a bad idea. Changing the IP would still allow an attacker to use DES chips to crack password files. A high speed implementation of the salted des transform is available on eddie.mit.edu (ihnp4!mit-eddie) in /usr/spool/uucppublic/fdes.tar. This includes documentation that explains the tricks used to get the factor of 40 increase in speed. Most of the tricks have been published by Marc Davio, Yvo Desmedt, et al. in the proceedings of EuroCrypt 1983. The new trick is a five instruction implementation of the salting. >6. Are there any DES jokes or other names for DES? Does Everyone Spy? Do Encryption Spell (stuff) (shit) (slowly) Decryption Extra Simple (slow) (speedy) --Bob Baldwin baldwin@xx.lcs.mit.edu ihnp4!mit-eddie!baldwin.UUCP
matt@oddjob.UChicago.EDU (D 1 4 U 2 C) (05/08/87)
In a very informative article Robert W. Baldwin writes one thing I just can't believe: ) ) Your card has a number on it which ) is the result of applying a DES based function to your PIN and your ) account number. When you type in your PIN, the ATM performs this ) function and lets you continue if the result matches the number on the ) card. But two of my cards (AmEx and Discover) came with forms for changing my PIN. All I had to do was send in the form and wait two weeks before using the new PIN. This argues for remote verification. Matt Crawford
ken@rochester.ARPA (Ken Yap) (05/08/87)
This is only vaguely related to DES so maybe I should have changed the subject line. A friend of mine discovered something interesting about the way some (all?) ATM's work. He put in a non-participating bank's card and the machine cycled him through the whole validation sequence before spitting out the card with the message "invalid card" or something like that. So it looks like the ATM makes up a whole package of info before firing it off to the mainframe. I can just imagine the Cobol code, yuk! Ken
gwyn@brl-smoke.UUCP (05/08/87)
In article <18771@ucbvax.BERKELEY.EDU> rotondo@ernie.Berkeley.EDU.UUCP (Scott Rotondo) writes: >... However, actually >doing the computation seems to require an exhaustive search of 2^55 >keys (not 2^56 because of a known symmetry in the S-boxes). Let me assure you that cryptanalysts virtually never search a space anywhere near that large. Rather, they exploit algebraic structure of the encipherment system, using a variety of techniques. One rather puny, although publicly-known, example goes by the name "indirect symmetry of position"; it's described in Kahn (unabridged). I once implemented this on a computer and watched messages "unravel". For more modern systems including DES, one would use much more sophisticated algebraic methods than that, but until I find public references I can't disclose even the limited amount I know about this. I don't want to give the impression that cryptanalysis involves merely solving exact equations, however. A barrage of statistical tests are in general performed to steer the analysis into the most productive directions; you can think of this as favoring certain branches of the search tree of possibilities. One of the best public introductions to this area that I know of is the quite old technical paper (more like a book) by Solomon Kullback entitled "Statistical Methods in Cryptanalysis". It was published by the War Department in 1938 (revised edition) and was originally Confidential, later Restricted, now declassified via automatic downgrading rules. I don't know a source for this, but Aegean Press might be one. (I'm getting their book list soon; they have at least some older editions of Mil Cryp for sale.) Certainly there has been a lot of progress in this area since then.. >Does "sufficient cleverness or dumb luck" mean finding a way to factor >large numbers or something else? "Sufficient cleverness" was mostly an oblique reference to the widely- held idea that one would have to factor the product of two large primes to crack a public-key system. Some people have maintained that any algorithm for cracking such a system amounts to an algorithm for the factorization, but I haven't been convinced that this conclusion is warranted. "Dumb luck" means any of a variety of ways a system could be cracked besides exploiting a clever analytic algorithm. Practical cryptanalysis of difficult systems often involves looking for easy wedges into the messages; examples from older systems include finding isomorphs (same message encrypted twice under different keys, sometimes different systems), crib dragging (guessing at the presence of probably plaintext phrases and trying to lever open the key under the assumption that the phrase occurs at a particular location), looking for hardware malfunctions (stuck shift registers, for example), and so forth. These methods, while tedious (unless computers are used), are far, far less work than any brute force approach such as trying all possible keys. Sometimes they pay off and sometimes they don't; when luck is with the analyst, nominally-secure traffic can be read. As you can undoubtedly tell, I find the amount of ingenuity that can be applied to cryptanalysis quite fascinating. I think this would be a wondeful subject for a college curriculum, although the number of potential employers for cryppies isn't very large yet. (It's growing as attention focuses on commercial data transmission.)
simsong@mit-amt.MEDIA.MIT.EDU (Simson L. Garfinkel) (05/08/87)
I believe that there are currently several distinct systems used for verification of PINs. Some of them involve remote verification. Some of them involve storing encrypted PINs on the cards. Some of them involve storing non-encrypted PINs on the cards (indeed, most of the early systems come under this last catagory.) For obvious reasons, companies who issue these things are very reluctant to dispence corect information. I've asked people at my bank on several occasions and received several different answers.
eppstein@tom.columbia.edu (David Eppstein) (05/08/87)
In <5845@brl-smoke.ARPA>, gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: > "Sufficient cleverness" was mostly an oblique reference to the widely- > held idea that one would have to factor the product of two large > primes to crack a public-key system. Some people have maintained that > any algorithm for cracking such a system amounts to an algorithm for > the factorization, but I haven't been convinced that this conclusion > is warranted. For RSA I agree with you, but there is for instance a cryptosystem such that ability to break it is provably equivalent to testing for quadratic residuosity modulo a certain number (the public key). Galil, Haber, and Yung, FOCS 1985. This is not quite the same as factoring, but actually taking square roots rather than merely knowing whether one exists is in fact random time equivalent to factoring, so this is evidence that residuosity is hard. Of course this depends on interaction rather than the more common method of one party encrypting, sending the whole thing at once, and then the other party decrypting. And it's not very practical. But it is provable. So in this case "sufficient cleverness" would have to involve some breakthroughs in number theory, not just in cryptology. Disclaimer: Galil is my advisor, and I also work with Haber and Yung. There may be other systems provably equivalent to simple number theoretic functions, but this is the one I'm most familiar with. Note to people who think they know a little number theory: residuosity is only the same as the Jacobi symbol when n is prime. The Jacobi symbol is easy to compute, but residuosity modulo composites is (apparently) not. -- David Eppstein, eppstein@cs.columbia.edu, Columbia U. Computer Science Dept.
robert@jimi.cs.unlv.edu (Robert Cray) (05/09/87)
In article <18742@ucbvax.BERKELEY.EDU> rotondo@ernie.Berkeley.EDU.UUCP (Scott Rotondo) writes: >DES is used in the Unix crypt(3) function (NOT crypt(1)) to encode passwords. >The algorithm is DES except that the initial permutation is altered to one >of 4096 possibilities by the first two characters in the passwd file entry, >known as "salt" bits. This makes it impossible to encrypt common words >and then check them against all the passwd entries looking for a match. > You are correct, however I would add that there exist implimentations of crypt(3) that are fairly fast (Bob Baldwin's fdes) -- when I tried it, it could run through about 50,000 calls to fcrypt(3) (on an 11/780) in about 45 minutes. Given a few days, someone with bad intentions could easily check a list of "common" words against every user (each word would have to be re-encrypted for every user). The same is true for the password-encryption on VMS, except that the VMS routines (that were posted to the net) go through about 50k words in ~11 minutes. --robert
jbs@eddie.MIT.EDU (Jeff Siegal) (05/10/87)
In article <566@jimi.cs.unlv.edu> robert@jimi.UUCP (Robert Cray) writes: >In article <18742@ucbvax.BERKELEY.EDU> rotondo@ernie.Berkeley.EDU.UUCP (Scott Rotondo) writes: >>[...] "salt" bits. This makes it impossible to encrypt common words >>and then check them against all the passwd entries looking for a match. >[...] (Bob Baldwin's fdes) -- when I tried it, it >could run through about 50,000 calls to fcrypt(3) (on an 11/780) in >about 45 minutes. [...] check a list of "common" words against >every user (each word would have to be re-encrypted for every user) Actually, if you make a hobby of cracking password files, you can collect a library of encrypted dictionaries (i.e. each time you encrypt the dictionary for a user using that pair of salt characters, you keep it around on disk). As your library grows, a substantial portion of the users in a password file you are attempting to crack involve a simple lookup (i.e. much < 1 sec) >The same is true for the >password-encryption on VMS, except that the VMS routines (that were posted >to the net) go through about 50k words in ~11 minutes. Except that the encrypted passwords are not available to any user on a VMS system--you need privs to access them. Jeff
mkaplan@aecom.YU.EDU (Marc Kaplan) (05/10/87)
In article <27595@rochester.ARPA>, ken@rochester.ARPA (Ken Yap) writes: > This is only vaguely related to DES so maybe I should have changed the > subject line. > > A friend of mine discovered something interesting about the way some > (all?) ATM's work. He put in a non-participating bank's card and the > machine cycled him through the whole validation sequence before > spitting out the card with the message "invalid card" or something like > that. So it looks like the ATM makes up a whole package of info before > firing it off to the mainframe. I can just imagine the Cobol code, > yuk! > > Ken Well, I noticed the same situation when using my card with an invalid PIN. However, I reached a very different conclusion. This is (I assume) a security feature designed to make it harder for a "bad guy" to guess someone's PIN. Since it's only four digits, an average of 5000 attempts should give him the valid PIN. If the machine tells him immediately if his PIN is valid or invalid, it makes it *much* easier to sit there and try numbers. If he has to go through an entire transaction first, it will take four or five times as long to try each number. Unix uses a similar strategy to discourage password guessing. The password checking program is slowed down by a large factor (25?) so the bad guy won't know the results too quickly. Unfortunately, the strategy works badly for passwords, since too many users use first names, two character passwords, etc. BTW, I assume that the ATMs will temporarily invalidate a card if a few hundred bad attempts are made to remove money. At least, thats how I would do it. Eric Safern ...aecom!mkaplan
calvin@tcom.stc.co.uk (Calvin Sambrook) (05/11/87)
In article <1072@mit-amt.MEDIA.MIT.EDU> simsong@media-lab.MEDIA.MIT.EDU (Simson L. Garfinkel) writes: >I believe that there are currently several distinct systems used for >verification of PINs. Some of them involve remote verification. Some of them >involve storing encrypted PINs on the cards. Some of them involve storing >non-encrypted PINs on the cards (indeed, most of the early systems come >under this last catagory.) > >For obvious reasons, companies who issue these things are very reluctant to >dispence corect information. I've asked people at my bank on several occasions >and received several different answers. In 1984 some friends of mine built a card reader as part of thier lab work for thier BSc in computer systems. They used only commercially available components and freely available information. Imagine my horror (along with others in our lab group) when they demonstrated thier ability to read our account and PIN numbers directly off our cards ! The reader (which they disassembled after their work had been assessed) cost them just under 150 pounds (sterling) to build and was powered from 12V d.c. I would imagine that any enterprising card thief could make a device like this pay for itself in just a few hours. I certainly learned a lesson from this and as well as keeping my plastic very safe now I also check my bank statements *very* carefully ! It makes me wonder just how much money the banks lose each day... -- calvin -- -- | Wie Tabaluga sagt: (Tabaluga und das leuchtende Schweigen - Peter Maffay) | Sag mal, kannst du deine Flammen nicht auspusten? | Mein Vater sagt auch immer: 'Bein reden spuckt man kein Feuer'
akt@cos.UUCP (05/11/87)
In article <1072@mit-amt.MEDIA.MIT.EDU>, simsong@mit-amt.MEDIA.MIT.EDU (Simson L. Garfinkel) writes: > [.....] > For obvious reasons, companies who issue these things are very reluctant to > dispence corect information. I've asked people at my bank on several occasions > and received several different answers. even if the banks don't tell you, ANSI will. i have forgotten the relevant standard numbers, but ANSI has a whole slew of them for EFT. they use DES extensively. key-management is by RSA, i think.