dnelson@ddsw1.UUCP (Douglas Nelson) (02/03/88)
I heard something about the regular old crypt() on most versions of Unix has been cracked by a program??? Being a security adviser for our system, I would like to see how this was done, and what could be done to prevent it. ------------------ Douglas Nelson dnelson@ddsw1.UUCP ------------------
jbs@eddie.MIT.EDU (Jeff Siegal) (02/04/88)
In article <538@ddsw1.UUCP> dnelson@ddsw1.UUCP (Douglas Nelson) writes: >I heard something about the regular old crypt() on most versions of Unix has >been cracked by a program??? Not crypt() the library routine--crypt the program. If you have files encrypted using the crypt program, they can be attacked easily (i.e. by someone without any knowledge of codebreaking) using Bob Baldwin's "Crypt Breaker's Workbench" (cbw). Bob's fdes package speeds up the crypt() routine by a factor of 20-100, so brute force attacks become more attractive (e.g. throwing /usr/dict/words at the password file) but, in general, crypt() is not know to have been broken. Jeff Siegal
relkins@vax1.acs.udel.EDU (Rob Elkins) (02/04/88)
In article <538@ddsw1.UUCP> dnelson@ddsw1.UUCP (Douglas Nelson) writes: > >I heard something about the regular old crypt() on most versions of Unix has >been cracked by a program??? Being a security adviser for our system, I would >like to see how this was done, and what could be done to prevent it. Yes, this is true. The program is called cbw or crypt-breakers-workbench and it is available from unix-archives (Vol 10). It uses techniques described in a paper by Reeds & Weinberger (ATT Bell Tech Journal 10/84). The author of cbw, Robert Baldwin wrote the program to show the inherient problems with crypt. Using cbw and a little patience, a crypted file can be turned into plaintext. Baldwin does describe some possible ways to better secure files if you are forced to use crypt. cbw uses a plaintext attack approach on the file, thus a binary file can not be decrypted using cbw. Baldwin suggests using the unix compress program before crypting a file. Rob Elkins -- ARPA: relkins@vax1.acs.udel.edu BITNET: FFO04688 AT ACSVM Live Long and Prosper!
dnelson@ddsw1.UUCP (Douglas Nelson) (02/05/88)
While looking at the source for crypt.c, I noticed that it seemed that some of the complitations seemed irrelivant to the actual end product, thus the multiple forulating seemed only to waste time, perhaps making "brute force" hacking much more inefficient, at best, if I understand correctly. I have seen a program that is only a few lines long, but takes a work from the dictionary file (usually at /usr/dict/words) and then crypts the plain- text word (using crypt() ) and then uses strcmp() to compare the encrypted result to that of the the one in the /etc/passwd file. While this seems to work, it would only seemingly work if your password is ideally a normal english word. I suppose the solution would be to require users to have at least one number in their password, thus rendering a system like that useless for all intents and purposes. Would someone be able to get a copy of Bob Baldwin's "Crypt breaker's work- shop?" I would very much like to take a look at that. I will gladly send anyone the C source for that dictionary brute-force code that I have if anyone has any vague interest in seeing it. It is quite logical at how one would go at it though... Thanks for all your comments, any questions/comments/answers/threats can be sent to me at: ------------------ Douglas Nelson dnelson@ddsw1.UUCP ------------------
dkovar@lf-server-2.BBN.COM (David Kovar) (02/08/88)
All replies should go to DKovar@BBN.COM and not whatever the mailer generates for a reply. In article <637@ddsw1.UUCP> dnelson@ddsw1.UUCP (Douglas Nelson) writes: > >While looking at the source for crypt.c, I noticed that it seemed that some >of the complitations seemed irrelivant to the actual end product, thus the >multiple forulating seemed only to waste time, perhaps making "brute force" >hacking much more inefficient, at best, if I understand correctly. > >I have seen a program that is only a few lines long, but takes a work from >the dictionary file (usually at /usr/dict/words) and then crypts the plain- >text word (using crypt() ) and then uses strcmp() to compare the encrypted >result to that of the the one in the /etc/passwd file. > >While this seems to work, it would only seemingly work if your password is >ideally a normal english word. I suppose the solution would be to require >users to have at least one number in their password, thus rendering a system >like that useless for all intents and purposes. > It is a very inefficient hack, but it does work. Take one Sun workstation, one program, one /usr/dict/words file, one password file, and a week of vacation and viola! Basically, it proved that about 10% of the average users pick a password that exists in /usr/dict/words. I then hacked a version of login and passwd that made sure the password was *not* in user dict words. (The former reported to the user that his password was not very secure and the latter refused to accept one that were in the dictionary.) I also put together a list of about 50 "common" passwords. Using that as the dictionary file I was able to find at least one or two passwords out of 200 on a system. All of this was basically done for my own enlightenment and to try to point out to a few people that the systems were not overly secure. Not that anyone really listened much. The program should be obvious to anyone and takes about half an hour to code in an elegant fashion. The only things that would improve it are a) a more complete set of "common" passwords and b) a faster crypt routine. -David Kovar DKovar@BBN.COM
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/09/88)
In article <538@ddsw1.UUCP> dnelson@ddsw1.UUCP (Douglas Nelson) writes: >I heard something about the regular old crypt() on most versions of Unix has >been cracked by a program??? Not too long ago, the Crypt Breaker's Workbench was posted to one of the net newsgroups (I forget which, probably comp.sources.unix). It doesn't exactly automatically crack the encryption, but it does provide the interactive tools to help you do it, along with some clever guessing algorithms. I tried it out on a random collection of "crypt"ed files, and it did indeed help me crack them in short order. Very nice work. By the way, this was the "crypt" UTILITY, not the crypt() library function. The former is basically a trivialized Hagelin machine and the latter is a salted version of the DES. >Being a security adviser for our system, I would >like to see how this was done, and what could be done to prevent it. Easy: Don't use "crypt" to protect anything against more than the casual browser, if that. By the way, you should move all those crypt()ed passwords OUT of /etc/passwd and into a file that is not publicly readable! There are programs that simply crypt() a modest dictionary of probable passwords (using the appropriate salts) and try to match the results against the entries in /etc/passwd. A lot of matches turn up, on most systems. By hiding the encrypted passwords, you prevent such programs from working. Then the only avenue of attack on the passwords (assuming the system is otherwise properly administered) is to check passwords by using the system utilities such as "su" and "login" that validate passwords, but these are slow and may log the break-in attempts so that the effort is spotted long before it succeeds.
ln63wgq@sdcc13.ucsd.EDU (Keith Messer) (02/09/88)
About breaking crypt() ... I've worked out a technique and some of the tables for a simplified DES even now. I am convinced that the algorithm is vulnerable to a known-plaintext attack, and have good feelings about breaking it even in the other modes that are currently thought to be secure. Think of the DES purely as a boolean function, and its insecurity becomes obvious. UNIX*, for instance, uses a variation of the DES with a known 64 bit plaintext and a secret 56 bit key to produce 64 bits of cyphertext output. So, if you want to hack these 56 bit passwords, all you need to do is express each cyphertext bit in terms of every bit of the key. That makes 64 very nasty boolean expressions for the encryption---but they can be simplified! And once each cyphertext bit is expressed in the simplest possible way in terms of the key bits, you can begin to solve for bits of the key. This may sound like a bit of work, but it only has to be done once. The result is a machine which makes breaking UNIX* passwords a trivial exercise and a technique that can be extended to help break DES in its really nasty modes like CBC, used to make milnet passwords. It's very clear, then, that all that'll be required to do the work is a boolean expression simplifier. Although I'm no expert at that sort of thing, I'm convinced I can write one if I have to. It would be better if someone out there has written one already or has one and can send it to me, though. Anyone who knows about this--either how to code a boolean simplifier or where to find one--I'd be very happy to hear from you! If you're interested and want a bibliography papers on the subject, send me mail. Unfortunately, though, most of the current literature puts so much emphasis on higher level mathematical structures that it loses track of solving the problem. Anyway, send me mail anyway. I'm curious about what kind of people read this group! Keith Messer ln63wgq@sdcc13.ucsd.edu ------------------------------------------------------------------------------- "The National Bureau of Standards comittee that told IBM to make the DES use 56-bit instead of 128-bit keys should be set on fire." --Me "The impatient explorer... invents a box in which all journeys may be kept." --Kenneth Patchen -------------------------------------------------------------------------------
wallace@degas.Berkeley.EDU (David E. Wallace) (02/10/88)
In article <980@sdcc13.ucsd.EDU> ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer) writes: > >About breaking crypt() ... (and suggests a technique for breaking DES based on finding boolean expressions for the output bits in terms of the key, and then simplifying them)... This approach is a nice try - the problem is it's extremely unlikely to be at all practical. It's fairly easy to see that boolean expression simplification (all the way to simplest form) is NP-hard: if there was a polynomial algorithm to do it, then we could solve SAT (given a boolean expression, find out if there is some setting of the input variables that makes the expression true) in polynomial time: just run the input expression through the simplifier, and see if the result is 0. If so, there is no solution, otherwise there is. SAT is known to be NP-complete. So if you have an algorithm to do simplification in polynomial time, you have just shown that P=NP, and all the theoreticians that have been working on that problem over the years can go on to something else. This is extremely unlikely, to say the least. Hence any simplification algorithm you are likely to come up with either won't be able to simplify all expressions all the way, or will take an exponential amount of time (exponential in the size of the input expression), or both. Also, those "very nasty boolean expressions" may very well themselves involve an exponential number of terms (something close to 2^56, say). So first you formulate the boolean expression (with a possibly exponential number of terms), and then you simplify it (taking time that's probably exponential in the size of that expression) - and you still haven't solved the whole problem, you've just got a simpler boolean expression that you hope will lead you to a solution. It sounds like it would be far faster to just try all 2^56 keys and see which one works. Of course, you might get really lucky, and find that the expressions don't have an unreasonable number of terms, and find a simplification heuristic that happens to work quickly in this particular case. But it's a real long, long shot. Nice try - but no cigar. Dave Wallace > I've worked out a technique and some of the tables for a simplified > DES even now. I am convinced that the algorithm is vulnerable to > a known-plaintext attack, and have good feelings about breaking it > even in the other modes that are currently thought to be secure. > > Think of the DES purely as a boolean function, and its insecurity > becomes obvious. UNIX*, for instance, uses a variation of the DES > with a known 64 bit plaintext and a secret 56 bit key to produce > 64 bits of cyphertext output. So, if you want to hack these 56 > bit passwords, all you need to do is express each cyphertext bit in > terms of every bit of the key. That makes 64 very nasty boolean > expressions for the encryption---but they can be simplified! And > once each cyphertext bit is expressed in the simplest possible way > in terms of the key bits, you can begin to solve for bits of the > key. This may sound like a bit of work, but it only has to be done > once. The result is a machine which makes breaking UNIX* passwords > a trivial exercise and a technique that can be extended to help > break DES in its really nasty modes like CBC, used to make milnet > passwords. > > It's very clear, then, that all that'll be required to do the work > is a boolean expression simplifier. Although I'm no expert at that > sort of thing, I'm convinced I can write one if I have to. It would > be better if someone out there has written one already or has one and > can send it to me, though. Anyone who knows about this--either how > to code a boolean simplifier or where to find one--I'd be very happy > to hear from you! > > > Keith Messer > ln63wgq@sdcc13.ucsd.edu Dave Wallace UUCP: ...!ucbvax!wallace ARPA: wallace@degas.Berkeley.EDU
adamj@web5h.berkeley.edu (Adam J. Richter) (02/10/88)
Once upon a time I had some ideas similar to Keith Messer's for trying to derive a direct formula for the 56 key bits of DES given the 64 input bits and 64 output bits. I wrote some C code to manipulate big boolean expressions efficiently, and patched the source to crypt(3) to deal with these expressions instead of ints. The stuff lives in the directory weaver.berkeley.edu:/usr/weaver/adamj/C/crypto, which has anonymous ftp that connects to the top of the file system. I heard given an explanation similar Dave Wallace's, and gave up. Adam J. Richter adamj@widow.berkeley.edu ....!ucbvax!widow!adamj Home: (415)549-6377 Work: (415)523-9000 Sun room: (415)642-7762
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/11/88)
In article <22925@ucbvax.BERKELEY.EDU> wallace@degas.Berkeley.EDU.UUCP (David E. Wallace) writes: >Hence any simplification algorithm you are likely to come up with either >won't be able to simplify all expressions all the way, or will take an >exponential amount of time (exponential in the size of the input expression), >or both. This is a good example of the difference between the outlook of a real cryptanalyst and one of the academic theoreticians that publish most of the "open" literature on the subject. (This has been noted elsewhere, for example in an excellent book by Deavours and Kruh on cipher machines, published by Artech.) It should be obvious that there is NO NEED to EXACTLY solve the simplification problem. A heuristic method that is "good enough" would suffice, and such a method need not at all be NP-complete. (There are good examples of this in the literature; I seem to recall such an algorithm for the TSP problem by folks at Bell Labs, for example.) I sent Keith a fair amount of information about how a practical Boolean simplification algorithm could be designed. I don't particularly want to post it more generally, because if he gets his technique to work, he deserves the undoubtedly large proceeds from his invention. (Just imagine how much you could ask for an effective automated DES-cracking box!) There are indeed some problems to be solved in the course of making the proposed attack work, but there is no real evidence that the problems are inherently unsolvable by practical means. "Complexity" arguments are bogus in cyptography; they have been made many, many times for systems that in fact were busted wide open in a few hours by competent cryptanalysts. Information-theoretic arguments are much more valuable, but I'm not aware of one that shows the DES to be unduly "hard".
youngb@pur-ee.UUCP (02/11/88)
In article <7242@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >In article <22925@ucbvax.BERKELEY.EDU> wallace@degas.Berkeley.EDU.UUCP (David E. Wallace) writes: >>Hence any simplification algorithm you are likely to come up with either >>won't be able to simplify all expressions all the way, or will take an >>exponential amount of time (exponential in the size of the input expression), >>or both. > >... > >I sent Keith a fair amount of information about how a >practical Boolean simplification algorithm could be designed. I don't >particularly want to post it more generally, because if he gets his >technique to work, he deserves the undoubtedly large proceeds from his >invention. (Just imagine how much you could ask for an effective >automated DES-cracking box!) > >... It should be pointed out that this idea for attacking DES is not entirely new. Others in the past have used methods very similar to this to attack ciphers. I am presently trying to apply these methods with possible variations to attacking DES. I don't think I should say any more than this (my prof. may be listening). Good luck though. Bret usenet: ihnp4!pur-ee!youngb ARPA: youngb@eg.ecn.purdue.edu UUCP: youngb@pur-ee.UUCP
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/12/88)
In article <7527@pur-ee.UUCP> youngb@pur-ee.UUCP (H. Bret Young) writes: >... I am presently trying to apply these >methods with possible variations to attacking DES. Sounds like we should form a "DES Breaker's Club". In case it isn't obvious, I should point out that before trying to solve the system of Boolean equations, it is advisable to boil down the scope of the problem by finding and exploiting structure in the encryption system. There are some good opportunities to apply a bit of (abstract) algebra to this problem. (The simpler the eventual system of equations that needs to be solved computationally, the better off you are.)
mitch@Stride.COM (Thomas Mitchell) (02/16/88)
In article <22925@ucbvax.BERKELEY.EDU> wallace@degas.Berkeley.EDU.UUCP (David E. Wallace) writes: >In article <980@sdcc13.ucsd.EDU> ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer) writes: >> >>About breaking crypt() ... >(and suggests a technique for breaking DES based on finding boolean >expressions for the output bits in terms of the key, and then simplifying >them)... > >This approach is a nice try - the problem is it's extremely unlikely to >be at all practical. >> DES even now. I am convinced that the algorithm is vulnerable to >> a known-plaintext attack,.. >> Think of the DES purely as a boolean function, and its insecurity >> becomes obvious. ^^^^^^^^ Solution left for the student? Some people believe that the analysis of DES by NSA and others found just such a flaw and that they hold it out as a way that they can break most any given input. It might be of interest to see if he can reduce the DES alg. to a simpler procedure. As I see it the DES is a series of reversible transformations which preserve the data content of the message. These paths or transformations may have a short cut which may present itself when the boolean reduction is finished or partly finished. I guess what I am saying is that if David can reduce DES sufficiently he may be able to generate exhaustive searches fast enough or given the plain text be able to extract the key all with a facility which would make the US and world banking industry cry. Just remember how big a discovery a^2 + b^2 = c^2 was in the correct context, E=mc^2.
wallace@degas.Berkeley.EDU (David E. Wallace) (02/18/88)
In article <716@stride.Stride.COM> mitch@stride.stride.com.UUCP (Thomas Mitchell) writes: >In article <22925@ucbvax.BERKELEY.EDU> wallace@degas.Berkeley.EDU.UUCP (David E. Wallace) writes: >>In article <980@sdcc13.ucsd.EDU> ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer) writes: >>> ... >I guess what I am saying is that if David can reduce DES ^^^^^ Not me - Keith is the one who is trying to crack DES. Misplaced attribution here. - DEW. Dave Wallace UUCP: ...!ucbvax!wallace ARPA: wallace@degas.Berkeley.EDU
jboede@auscso.UUCP (Jon Boede) (03/18/88)
I posted a question on this a while back and it was summarily ignored, perhaps
because it's such an easy question... anyhow, I'm still trying to get it to
work.
What I'm looking for is a function that will encrypt or decrypt a string
passed to it using the DES functions in the standard library. I have a v7
manual that documents this and it seems fairly simple yet I continue to have
no luck.
Assuming that I could attack a while string in 8 character (64 bit) chunks,
I've written the following which fails nicely because I immediately encrypt
then decrypt the bit array (block of chars) and I don't get back what I put
in!
Thanks,
Jon
main()
{
char blk2[64], text[32], block[64], key[9];
register bit, loop;
strcpy(key,"xyzzy678");
/* load and set the key block */
for (loop=0; loop < 8; loop++) {
for (bit=0; bit < 8; bit++)
block[loop*8+bit] = ((int)key[loop] & (1<<bit)) ?
'\1' : '\0';
}
setkey(block);
strcpy(text,"thisisometext"); /* going to do just first 8 chars */
for (loop=0; loop < 8; loop++)
for (bit=0; bit < 8; bit++)
block[loop*8+bit] = ((int)*(text+loop) & (1<<bit)) ?
'\1' : '\0';
for (loop=0; loop < 64; loop++)
blk2[loop] = block[loop];
encrypt(block,0); /* encrypt it */
encrypt(block,1); /* decrypt it */
for (loop=0; loop < 64; loop++)
if (blk2[loop] != block[loop]) {
puts("different");
exit(0);
}
puts("same");
exit(0);
}
--
Jon Boede jboede@auscso.UUCP, jon%bodedo@im4u.cs.utexas.edu
1301 Trace Dr. #204, Austin, TX 78741-1735 (512) 462-3287
"People who are incapable of making decisions are
the ones that hit those barrels at freeway exits."amh@newcastle.ac.uk (Andrew Hilborne) (03/23/88)
I have also written (an even shorter) program which appears to show that the setkey(3)/encrypt(3) library routines are broken, this time on BSD4.2. I don't have it here, but the basics are that the program fragment: setkey(key); encrypt(block, 0); encrypt(block, 1); Should be a no-op on "block", but is not. Could someone confirm that this is true? Or explain where the documentation fails? -- ------------------------------------------------------------------------ SENDER : "Andrew Hilborne" PHONE : +44 91 2722522 POST : MARI Ltd, Newcastle upon Tyne, NE4 8RY, UK UUCP : <UK>!ukc!mari!amh
jboede@auscso.UUCP (Jon Boede) (03/25/88)
In article <2830@cheviot.newcastle.ac.uk> amh@mari (Andrew Hilborne) writes: > I have also written (an even shorter) program which appears to show that > the setkey(3)/encrypt(3) library routines are broken, this time on > BSD4.2. I don't have it here, but the basics are that the program > fragment: > > setkey(key); > encrypt(block, 0); > encrypt(block, 1); > > Should be a no-op on "block", but is not. [ The orignal posting said that it looked broken under SysV and SCO XENIX ] I was contacted after my posting to this newsgroup by someone who works at SCO (great company, BTW, second time someone from there has called to help and both times they've been great help, but anyway...) he said that 1) the code I posted *should* have worked and 2) he looked at the source for encrypt(3) and it is, in fact, broken. In his opinion, encrypt(3) has been broken for at least 6 years. The plot thickens. My 7th edition manual talks about DES-this and DES-that in crypt(3). It describes encrypt(3) such: encrypt(block,ed_flag); unsigned char *block; int ed_flag; If ed_flag was 0 it encrypted, else decrypted. BUT! When I actually went to the SysV manuals, crypt(3) no longer mentioned DES, calling it the "hashing function". The reeeealy interesting part is that encrypt is now... void encrypt(block,ignored); unsigned char *block; It said that the second variable is ignored but must be given. This, of course, makes encrypt(3) a one way function. Did AT&T break crypt on purpose? To satisfy export regulations? Surely they didn't know it was broken and then didn't feel like fixing it! Seems a little fishy to me... enquiring minds wanna know! Jon -- Jon Boede jboede@auscso.UUCP, jon%bodedo@im4u.cs.utexas.edu 1301 Trace Dr. #204, Austin, TX 78741-1735 (512) 462-3287 "People who are incapable of making decisions are the ones that hit those barrels at freeway exits."