[pmwiki-users] action=crypt gives different results

[Patrick R. Michaud]

On Sat, Mar 04, 2006 at 12:26:37PM +0100, Sebastian Siedentopf wrote:
> 
> Am 03.03.2006 um 18:17 schrieb Patrick R. Michaud:
> 
> >Yes -- any string it comes up with is a valid encryption for
> >the input string you provide.  (I'll be happy to provide the
> >details of how it works if anyone is interested.)
> 
> Always willing to learn something I'm playing the "let Pm write  
> emails instead of working on pmwiki" card. :)

(Providing detail comes from having been a professor in my previous job. :-)

Okay, here's a quick overview of how password authentication and 
encryption works for many systems, including PmWiki (which just borrows
from the way they do it).

Essentially, we want to have some way to store passwords such that
someone who happens to see the stored (encrypted) form cannot
easily determine the original password.  We also want to have
a way to easily verify that the password someone enters matches the
one we have stored in encrypted form.

In Unix, encryption of passwords has traditionally been performed 
by the crypt(3) function, which PHP also supports.  The crypt 
function takes a password string (the "cleartext"), and returns 
an encrypted form of the string called the "password hash".  For example,
the password hash for the password "secret" might be
"$1$aP2iRNwR$Vn3hrxPqflGQaqM5qHnyu."

One notable feature of the algorithms used to compute password hashes
is that they are "one way" conversions -- i.e., it's easy to compute
a password hash from a cleartext password, but there's not an easy
(or known) mechanism to go from the password hash back to the original
password.  Because of this, it's relatively safe to let others view
the password hash strings, because one cannot use it to directly 
find the original password. 

At this point most people ask, "If it's not possible to get the
original password from the password hash, how does the computer
check for a matching password?"  The answer is that in order to verify
a password, the computer simply runs the password through the
conversion algorithm again, and sees if the resulting password hash 
matches the one we have stored.  

Given the speed of today's computers, however, the conversion function
(technically called a "cryptographic hash function") has to be resistant
to "dictionary attacks".  For example, the password "secret" above
created a password hash of "$1$aP2iRNwR$Vn3hrxPqflGQaqM5qHnyu."   
If a given password *always* results in the same password hash, then
a malicious person can simply compile a list of common passwords and
their hashes (a "dictionary"), and then do a simple lookup of the hash 
to determine the original password that created it.  So, we need to make 
it hard for someone to build such a dictionary.

The normal way to do this is to use a concept called "salt", which
is a random string of characters that are combined with the password 
prior to computing the password hash.  So, when generating a password
hash to be used to store a password, the system first generates a
random string of characters and combines it with the cleartext password
before it computes the password hash.  This is why ?action=crypt
returns different values for the same password -- each password
hash is being created using a different salt value.  

Salting the password in this manner makes dictionary attacks much more 
difficult for an attacker, because each cleartext password can now 
be represented by billions of different password hashes.  It's 
not practical to build a table to store all combinations of passwords
and their possible hashes.

But then how does the computer verify a password containing random
salt?  Well, the salt is stored as part of the password hash.
In my system's version of crypt, the components of the password
hash are separated by dollar signs:

    $1$pTdh3961$dhMGxKexV/pyRMU.AgTTB.

The "$1$" at the beginning identifies the algorithm that was used
to produce the hash.  The "pTdh3961" between the next pair of dollar
signs is the random salt string that the system used in order to 
compute the rest of the hash, and the "dhMGxKexV/pyRMU.AgTTB." is 
the result of running the conversion algorithm on the 
password ("secret") combined with its salt string ("pTdh3961").

A different salt produces an entirely different hash for the same
password, as in "$1$dMGn7AOb$26zXR2rCaMNm6PAeRt1Rd.", where the salt 
is "dmGn7AOb". 

So, to verify a password against a stored hash of the original, the
algorithm simply uses the same salt string (present in the hash) that
was used to generate the hash from the original password, instead
of using a randomly generated salt.  If the resulting hash is the
same as what is stored, then the password submitted for verification
matches the original.

(Yes, it is the case that there can be multiple passwords that result
in the same password hash.  But for most practical purposes the
number of such collisions is completely dwarfed by the sheer number
of potential passwords that don't collide.)

That's basically how it works.  :-)

Pm