🚀 go-pugleaf

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

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!

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
------------------

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

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.

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
-------------------------------------------------------------------------------

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

	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

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".

In article <980@sdcc13.ucsd.EDU> ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer) writes:
>
>About breaking crypt() ...
>
>	I've worked out a technique and some of the tables for a simplified
>       DES even now...
>
>	Think of the DES purely as a boolean function, and its insecurity
>       becomes obvious. ...
>       ... 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!
>       ... you can begin to solve for bits of the key
>
>	It's very clear, then, that all that'll be required to do the work
>       is a boolean expression simplifier...

I've been working on this approach from time to time without much success.
Yes, you can define DES as boolean functions, and yes, you could theoretically
solve for each of the 56 bits of key given the known input and output.
However, your "very nasty" modifier is rather optimistic in my view.
It doesn't take many rounds before your intermediate results get
humungous.  Yes, there are simplifications, but there is a limit to the
amount of simplifying that can be done at each step.  Konheim gives some
information about the complexity limit for the S-boxes, for example, and
points out that they can't be reduced beyond a certain point.

My hope was that if there is actually a back door in there someplace it
would be discoverable by running this thing through -- at some point there
would be a dramatic collapse, instead of the expected geometric increase
in complexity.  I haven't demonstrated either the existence or
nonexistence of that trap door.

-- 
	Jim Gillogly
	{hplabs, ihnp4}!sdcrdcf!randvax!jim
	jim@rand-unix.arpa    [HASA: U (Spam) division]

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

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.)

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.

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