[Dovecot] CRAM-MD5 Password Generation Algorithm

[Bill Cole]

At 9:32 PM +0100 4/12/08, Douglas Willcocks wrote:
>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.

I'm now convinced that the contexts are NOT reversible 
programmatically to the key, because I now have a correct 
understanding of what they actually are...

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

No, it looks like your greater motivation and focus led you to a more 
careful reading of the source and a clearer description of what the 
HMAC-MD5 contexts actually are than I managed. For some reason I was 
thinking that the contexts were what that page calls Ki and Ko, but 
rather are MD5(Ko) and MD5(Ki) and are inserted in place of the 
normal initialization vector when completing the HMAC calculation. 
This means that they cannot be reversed to the actual password, but 
it is probably not terribly daunting to crack out the password, given 
the pair of hashes with a known derivation, restrictions on 'legal' 
passwords,  and the huge pile of work that has been done on MD5 
cracking. The pair of contexts in principle provides twice as much 
information about the original password as would a single hash, so it 
should be easier to crack than a straight MD5 hash.

In any case, the contexts could be used by someone who does not have 
the password to do a CRAM-MD5 authentication, so the direct risk of 
storing them is not a great deal different from storing the plaintext 
password. The difference is that they only provide access to a 
service that uses CRAM-MD5.

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

And indeed, when I look at the code and at what happens when I try to 
do the same thing in Perl with the Digest::MD5 module, I can't get 
the same output.

Puzzling. I'm probably missing something.

[...]

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

Well, if you are building a tool to manage passwords for Dovecot, 
that doesn't seem like a horrendous dependency.

But it is extremely annoying that reproducing what dovecotpw is doing 
is not easier.


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

You may find what you need in Digest::Perl::MD5, which is an all-Perl 
MD5 implementation of MD5. It is rarely installed because Digest::MD5 
(which uses a compiled backend) is significantly faster.



-- 
Bill Cole
bill at scconsult.com