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 mailto:Alec.Muffett@com.sun.uk (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 = );
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 mailto:aba@dcs.ex.ac.uk