[Dovecot] CRAM-MD5 Password Generation Algorithm

[Douglas Willcocks]

On Sat, 12 Apr 2008 07:52:01 +0200, Patrick Ben Koetter
<p at state-of-mind.de> wrote:
> * Douglas Willcocks <dovecot at dovecot.org>:
>> Hi,
>>
>> I'm just in the middle of setting up dovecot to serve IMAPS -- Actually
>> I've finished apart from one thing: CRAM-MD5 passwords.
>
> CRAM-MD5 is a shared secret mechanism to prove authenticity without
> transmitting the password in plaintext. Both parties - server and client
-
> proove that they share a secret.
>
> CRAM-MD5 passwords are passwords saved in plaintext format on the client
> and
> (!) on the server. Here's why:
>

That's what I first thought.

> 1. The server sends a challenge (a random string)
> 2. The client uses the challenge to encrpyt the user password and creates
> a
>    encrypted string
> 3. The client uses the username and the encrypted string, base64 encodes
> both
>    to one string (response) and sends that to the server
> 4. The server base64 decodes the response to get the username
> 5. The server uses to username to lookup the corresponding password.
> 6. The server uses the password to decrypt the encrypted client string.
> 7. The server compares the decryption result with the challenge it sent.
> If
>    they match, server and client share the same secret - the password.
>

Thank you for your explanation, I understand how the CRAM-MD5 communication
algorithm works, it's more the CRAM-MD5 scheme hashing that is giving me
trouble. From experience I know that CRAM-MD5 needs plaintext passwords,
but according to the dovecot wiki pages (which I've referenced below) you
_can_ have them stored in some sort of hashed form, and I'm trying to
understand both how to generate that hashed for and (out of curiosity) how
dovecot can manage to use hashed passwords for CRAM-MD5.

> As you can see, the password must be available in plaintext to decrypt
the
> encrypted client string. Databases like /etc/shadow that store passwords
> encrypted cannot do this. All they can do is answer questions like this:
> "I do
> have password 'foo'. If you encrypt that, will it match the value you
have
> stored as password in the database?" Shared secret mechanisms, such as
> CRAM-MD5, DIGEST-MD5 and NTLM, cannot do with that. They need the
password
> string in unencrypted plaintext.
>
>> I'm using SQL as a backend for the password storage, and I don't want to
>> store the passwords in plaintext. I've also configured dovecot to be
> rather
>> restrictive when it comes to authentication methods (only CRAM-MD5 is
>> allowed).
>
> Then you have to store passwords in plaintext.
>

On the following page : http://wiki.dovecot.org/HowTo/CRAM-MD5

They use dovecotpw to generate a seemingly hashed version of the password
and then store it in the password database

 username:{CRAM-MD5}26b633ec8bf9dd526293c5897400bddeef9299fad

Perhaps this not an irreversible hash, but more something like (althought
it's not) base64? The thing is, it _looks_ like a hash.

For example, using dovecotpw I can generate the hashed (??) version of
'password', which is

{CRAM-MD5}9186d855e11eba527a7a52ca82b313e180d62234f0acc9051b527243d41e2740

I can then place that in the database and the authentication is successful.

What's more, according to
http://wiki.dovecot.org/Authentication/PasswordSchemes

You only need to store the password in plaintext if you are using _both_
CRAM-MD5 and DIGEST-MD5.

To quote:

"The problem with non-plaintext auth mechanisms is that the password must
be stored either in plaintext, or using a mechanism-specific scheme that's
incompatible with all other non-plaintext mechanisms. For example if you're
going to use CRAM-MD5 authentication, the password needs to be stored in
either PLAIN or CRAM-MD5 scheme. If you want to allow both CRAM-MD5 and
DIGEST-MD5, the password must be stored in plaintext."



>
>> To generate the passwords to go into the database I can use the
> dovecotpw
>> utility, but I'm wanting to stick some sort of minimal admin interface
> on
>> the server to be able to manage the users etc without having to use the
>> CLI.
>
> Use pwgen.
>

The problem (as stated above) is not how to generate passwords, there are
thousands of libraries that can do that relatively well.

>
>> I've looked at the theoretical explanation of the hashing algorithm, and
>> I've read through the source code that dovecotpw uses to generate the
>> passwords with the intent of creating a higher level language library
>> (Perl, Ruby, PHP ... whatever)) to generate passwords, but I don't seem
> to
>> be able to replicate the functionality, and there don't seem to be any
>> existing libraries that generate consistent results (that I've found).
>>
>> I don't have that much experience with C, and so I'm sure that I must
> have
>> misunderstood how dovecotpw does its stuff. Perhaps someone could
> explain
>> how the algorithm works? Or point me in the right direction?
>
> HTH,
>
> p at rick
>
> --
> state of mind
> Agentur für Kommunikation, Design und Softwareentwicklung
>
> Patrick Koetter            Tel: 089 45227227
> Echinger Strasse 3         Fax: 089 45227226
> 85386 Eching               Web: http://www.state-of-mind.de
>
> Amtsgericht München        Partnerschaftsregister PR 563

Thanks for your reply,

Douglas Willcocks

--