Crack in 1 line of perl

This one has some relevance to cryptography in that it is a program to brute force the UNIX password mechanism, which use a variant of DES as the one way hash.
perl -nle 'setpwent;crypt($_,$c)eq$c&&print"$u $_"while($u,$c)=getpwent'

The above code was contributed by Alec Muffett <> (who is also author of Crack a complete system for this purpose. This package is intended for use by people wearing white hats to weed out users on systems they administer with poor tastes in passwords.) The commentary, and usage explanation below is mine (Adam).

There is a political aspect to this script, Alec created it as a demonstration of the simplicity of unix password attacks, for a lawyer writing a legal paper.

Unix password files

Please note that some administrators get understandably picky about non-administrators running any variants of crack. Perhaps its best if you try this on a machine where you are already (legimately!) root, so there is no confusion! Here is an entry I created for demonstration purposes on my linux box, using perl to access the crypt(3) function: % perl print crypt("fred","am"); ^D amLH9TiZZkscc That is the crypt function takes the first argument of the password to create a one way hash of, and the second argument of the salt to use (the salt is encoded as two radix 64 characters). The result ("amLH9TiZZkscc") also is encoded in radix 64, the first two characters are a copy of the salt, the remaining 11 radix 64 chars are the hash of the password and salt concatenated. The password is limited to 8 characters (8 typeable characters), and thus the keyspace is ultimately limited to around 95^8 + 95^7 + 95^6 + 95^5 + 95^4 + 95^3 + 95^2 + 95 = 6,704,780,954,517,120 based on an alphabet of these characters: abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 `-=#[];'\,./~!"$%^&*()_+{}:@|<>? 123456789012345678901234567890123 that is around 10^15 which is about 2^53 and hence around 53 bits of entropy. This might sound reasonable (DES itself only has 56 bits of keyspace), but there is another problem: humans choose poor passwords. Consider what happens if a user types all lowercase and does not use any symbols, and uses an eight character password, that leaves: 26^8 = 208,827,064,576 that is around 10^11, and 2^37, or 37 bits of entropy. (Bear in mind that a recent Net colaborative effort brute forced a 40 bit RC4 key in 31 hours, and that DES hardware could improve that by many many orders of magnitude.)

In fact the situation is much much worse than depicted by the above entropy estimates because users typically chose words in the dictionary, or worse spouses first names, their phone numbers, etc. This sorry state of education on proper choice of passwords leads to the so-called `dictionary' attack, experiments have been conducted which suggest that on most typical unix sites, a suprisingly large proportion of passwords would fall to this kind of attack.

The way that the password is checked is that the user enters their password, and this is then hashed; if the hash of the entered password matches the stored hash in the password file, access is granted. Note that it is possible for two unrelated passwords to hash to the same value. The infrequency with which these hash collisions occur means that it is exceedingly unlikely that this would ever occur by accident.

(David Wagner found a partial collision by trying 6.1 billion trial crypts. (Took him 1290 CPU hours on suns getting 1310 crypts per second). His collsion is: crypt("2NGGMda3", "Hx") = "HxyX8CL2luKyI" crypt("gnB9Gw1j", "s8") = "s8yX8CL2luKyI" however they are for different salts so it would not work in a unix password file.)

Using the example above, repeated again here:

% perl print crypt("fred","am"); ^D amLH9TiZZkscc The password is "fred", and the salt is "am", the encrypted password file entry (the salt concatenated with the encrypted password) is "amLH9TiZZkscc". To check that the password is valid the following code (pulled from the perlfunc man page) shows that the entered password is encrypted, and the same salt used, with the result compared against the stored encrypted password. $pwd = (getpwuid($<))[1]; $salt = substr($pwd, 0, 2); system "stty -echo"; print "Password: "; chop($word = <STDIN>); print "\n"; system "stty echo"; if (crypt($word, $salt) ne $pwd) { die "Sorry...\n"; } else { print "ok\n"; } That is $salt is the first two characters of the encrypted password field, and $word is the entered password. If crypt($word, $salt) is equal to the encrytped password stored in the password file access is granted.

On salts

The salt is used to increase the cost of dictionary attacks. If a salt were not used, it would be possible to precompute a tape with all the words in the dictionary encrypted (hashed), the dictionary attack would then degenerate to simply streaming the pre-encrytped fields from the tape, and comparing them to any password files being attacked.

A second reason for the use of salts, is that the way that the salt is combined in a first stage which permutes the password with the salt is designed to frustrate the use of off-the-shelf DES hardware.

The salt multiplies the storage requirements for this attack by a factor of 4096 (the number of possible salts). This is because the same password encrypted with a different salt yields a different encrypted password. For example:

crypt("fred","am") = "amLH9TiZZkscc" crypt("fred","an") = "anvepwCPZQ2Z6"

Using Alec's perl crack

Again, please note that some administrators get understandably picky about non-administrators running any variants of crack. Perhaps its best if you try this on a machine where you are already (legimately!) root, so there is no confusion!

Alec's program actually uses getpwent(3) to extract the encrytped password fields from the password file. This means that it will only (in it's current form) attack passwords stored in either a local password file (/etc/password), or an NIS password file (ypcat passwd) if the NIS system is being used.

The program takes one (or more) arguments, or standard input even, which is expected to be a dictionary of words to try, each word on a separate line.

% pwc dictionary so a password file with the entry: fred:amLH9TiZZkscc:9999:9999:Fred Bloggs:/:/dev/null and a dictionary with the word "fred" (Fred's example password encrypted as shown above). (Note use of /dev/null in the shell field to ensure that no one could log as fred, just in case!) So (as root): # echo fred:amLH9TiZZkscc:9999:9999:Fred Bloggs:/:/dev/null >> /etc/passwd or a more conventional method of creating a new user, with a shell which won't work just to make sure the account can't be used if you forget creating it. (Be extra careful to type two >s to append, deleting the file could be somewhat embarassing).

Then Alec's perl script would be used:

% echo fred > dictionary % pwc dictionary u=fred p=fred The user name and password of succesfully attacked accounts are printed on standard output, u=<username>, p=<password>.

Solutions to the unix password problem

The basic problem with unix passwords is user choices of password. There are proactive solutions to this: replacements for the passwd program that check user passwords as they are entered, and refuse to accept exceptionally dumb ones. Also password `generators' which generate a password at random. A problem with these approaches is that they result in better passwords, but this may paradoxically be worse, if the user then resorts to writing the password on a jiffy note stuck to the corner of the screen.

There are a few systems to beef up what is essentially the same system, some using larger salts, others using MD5 as a hash with no limit on password size, and encouraging use of `passphrases' rather than passwords to encourage higher entropy passphrases.

Another (separate) reason that the unix password mechanism provides poor security is that most sites have no link level encryption on their local ethernets. Ethernets being a broadcast medium are vulnerable to password `sniffing'. If you have PCs with ethernet cards, this should especially worry you, tho' it should be noted that it is relatively easy to plug a notebook equipped with PCMIA ethernet card into an exposed section of ethernet even if there are no PCs. Come to that, no connection is even necessary, there are diagnoses tools which allow ethernet traffic to be sniffed just by placing the device close to an ethernet cable.

The solution to this is to use something like Kerebos for authentication.

The S/Key one time password system provides an excellent solution for remote connections. S/key is a clever scheme which ensures that the password that is sent remotely is not re-used; this which protects against replay attacks. S/key and many other freely distributable crypto applications are available from Tatu Ylonen's international cryptography pages.

Comments, html bugs to me (Adam Back) at <>