[Dovecot] CRAM-MD5 Password Generation Algorithm

[Douglas Willcocks]

On Sat, 12 Apr 2008 14:23:58 -0400, Bill Cole
<dovecot-20061108 at billmail.scconsult.com> wrote:
> 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.
> 
> [...]
> 

I'm not convinced that the context is reversible.

In the source of version 1.0.13:

The function 'hmac_md5_init' is called (from password-scheme-cram-md5.c:13)
to generate the scheme. Looking at the definition of 'hmac_md5_init' and
the explanation of the algorithm given on
http://www.cryptostuff.com/crypto/index.php?title=hmac, it's quite easy to
see the resemblance (with the exception of the lack of 'message' in
'hmac_md5_init'.

That implies the (multiple) usage of the MD5 hashing algorithm on the
password, making it more or less irreversible.

I may of course have misunderstood the sequence of functions that dovecotpw
actually calls of course...


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

That's the representation I'm trying to replicate.

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

I've read through the document, and I now understand where exactly the
precomputed context sits in the whole picture, but I'm still unsure how to
reproduce it without dovecotpw.

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

I _am_ aware of such functionality in the various languages I previously
mentioned, but I don't want to simply wrap the executable, I would like to
reproduce the algorithm. I have nothing against using dovecotpw, but would
I rather not depend on it for portability reasons.

I may want to run the library on various different machines, architectures
or os' and I don't want to have to compile dovecot for each situation if I
only need a small part of one of the encryption libraries.

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

I am well aware of the security implications of using the best practices
for web-based system <-> Shell interaction, but that isn't the problem
here. It's not a question of security, it's a question of portability.

> 
> --
> Bill Cole
> bill at scconsult.com

--

Douglas Willcocks