[Dovecot] CRAM-MD5 Password Generation Algorithm

[Bill Cole]

At 2:07 PM +0100 4/12/08, Douglas Willcocks  imposed structure on a 
stream of electrons, yielding:
>On Sat, 12 Apr 2008 07:52:01 +0200, Patrick Ben Koetter
><p at state-of-mind.de> wrote:
[...]
>>  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.

It's not technically a plaintext format or an obvious encoding, but 
if I'm reading the Dovecot code correctly, it is some form of the 
intermediate "contexts" derived from the password as part of the 
HMAC-MD5 algorithm.

It is not clear to me whether one could actually reverse that 
derivation. It seems to me that it should be simple, but no one seems 
to say that explicitly about the practice of storing the 
pre-calculated contexts rather than the actual password, so maybe I'm 
missing something. It may be that actual implementations always use 
the MD5 of the actual password as the key the context calculation, 
rather than using the password itself. That would make the contexts 
16 bytes each plus padding, which would explain the Dovecot 
'CRAM-MD5' storage format.

What IS clear is that with the HMAC-MD5 contexts one can authenticate 
as the user using CRAM-MD5, and that CRAM-MD5 requires the server to 
store either a recoverable plaintext password or the HMAC-MD5 
contexts derived from it.

[...]

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

I'm pretty sure that it is a pair of 16-byte values derived from the 
password, represented in hexadecimal and concatenated.

>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."

It may be illuminating to look at 
http://tools.ietf.org/html/draft-ietf-sasl-crammd5-09 and pay 
particular attention to Section 5.

>>>  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.

What exactly is wrong with using dovecotpw?

Are you unaware of the existence of system() and backtick operators 
in your preferred languages, or of the ability to write a CGI in 
shell?

Most generic 'best practice' advice for writing web-based tools tries 
to discourage any mechanism that feeds commands to a shell, but it is 
important to understand why that is and when the generic advice 
should be set aside. No Bourne/POSIX or csh-based shell is 
particularly fast, and system() or `` calls launching a shell to run 
a command line from another language has a fork cost, so using either 
approach for performance-sensitive apps is a bad idea on that basis 
alone. In regards to security, there has been a long ugly history of 
sloppy coders being exposed by their failure to diligently validate 
user input before feeding it to a shell. That problem has been 
addressed to some degree by delusional misfeatures like PHP's 'safe' 
mode, which encourages the coder and the admin to collaborate in 
insecurity under the misimpression of being safe. If you are 
disciplined about how you use what the user tells you, there's 
nothing inherently unsafe in passing it through a shell or even 
writing a simple web app entirely in shell.




-- 
Bill Cole
bill at scconsult.com