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.
<![CDATA[
perl -nle 'setpwent;crypt($_,$c)eq$c&&print"$u $_"while($u,$c)=getpwent'
]]>
The above code was contributed by Alec Muffett
<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:
<![CDATA[
% 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
<![CDATA[
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:
<![CDATA[
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:
<![CDATA[
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:
<![CDATA[
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:
<![CDATA[
% 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.
<![CDATA[
$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:
<![CDATA[
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.
<![CDATA[
% pwc dictionary
]]>
so a password file with the entry:
<![CDATA[
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):
<![CDATA[
# 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:
<![CDATA[
% 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
<aba@dcs.ex.ac.uk>