chiark - git - mdw - chopwood/blob - hash.py

   1 ### -*-python-*-
   2 ###
   3 ### Password hashing schemes
   4 ###
   5 ### (c) 2013 Mark Wooding
   6 ###
   7
   8 ###----- Licensing notice ---------------------------------------------------
   9 ###
  10 ### This file is part of Chopwood: a password-changing service.
  11 ###
  12 ### Chopwood is free software; you can redistribute it and/or modify
  13 ### it under the terms of the GNU Affero General Public License as
  14 ### published by the Free Software Foundation; either version 3 of the
  15 ### License, or (at your option) any later version.
  16 ###
  17 ### Chopwood is distributed in the hope that it will be useful,
  18 ### but WITHOUT ANY WARRANTY; without even the implied warranty of
  19 ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20 ### GNU Affero General Public License for more details.
  21 ###
  22 ### You should have received a copy of the GNU Affero General Public
  23 ### License along with Chopwood; if not, see
  24 ### <http://www.gnu.org/licenses/>.
  25
  26 from __future__ import with_statement
  27
  28 import crypt as CR
  29 import hashlib as H
  30 import os as OS
  31
  32 import config as CONF
  33 import crypto as C
  34 import util as U
  35
  36 ###--------------------------------------------------------------------------
  37 ### Protocol.
  38 ###
  39 ### A password hashing scheme knows about how to convert a plaintext password
  40 ### into whatever it is that gets stored in the database.  The important
  41 ### consideration is that this conversion is potentially randomized, using a
  42 ### `salt'.
  43 ###
  44 ### There are two contexts in which we want to do the conversion.  The first
  45 ### case is that we've somehow come up with a new password, and wish to write
  46 ### it to the database; we therefore need to come up with fresh random salt.
  47 ### The second case is that we're verifying a password against the database;
  48 ### here, we must extract and reuse the salt used when the database record
  49 ### was written.  This latter case is only used for verifying passwords in
  50 ### the CGI interface, so it might be acceptable to fail to implement it in
  51 ### some cases, but we don't need this freedom.
  52 ###
  53 ### It turns out that there's a useful division of labour we can make,
  54 ### because hashing is a two-stage process.  The first stage takes a salt and
  55 ### a password, and processes them somehow to form a hash.  The second stage
  56 ### takes this hash, and encodes and decorates it to form something which can
  57 ### usefully be stored in a database.  Most of the latter processing is
  58 ### handled in the `BasicHash' class.
  59 ###
  60 ### Hashing is not done in isolation: rather, it's done within the context of
  61 ### a database record, so that additional material (e.g., the user name, or
  62 ### some `realm' indicator) can be fed into the hashing process.  None of the
  63 ### hashing schemes here do this, but user configuration can easily subclass,
  64 ### say, `SimpleHash' to implement something like Dovecot's DIGEST-MD5
  65 ### scheme.
  66 ###
  67 ### The external password hashing protocol consists of the following pieces.
  68 ###
  69 ### hash(REC, PASSWD)
  70 ###     Method: return a freshly salted hash for the password PASSWD, using
  71 ###     information from the database record REC.
  72 ###
  73 ### check(REC, HASH, PASSWD)
  74 ###     Method: if the password PASSWD (and other information in the database
  75 ###     record REC) matches the HASH, return true; otherwise return false.
  76 ###
  77 ### NULL
  78 ###     Attribute: a string which can (probably) be stored safely in the
  79 ###     password database, but which doesn't equal any valid password hash.
  80 ###     This is used for clearing passwords.  If None, there is no such
  81 ###     value, and passwords cannot be cleared using this hashing scheme.
  82
  83 class BasicHash (object):
  84   """
  85   Convenient base class for password hashing schemes.
  86
  87   This class implements the `check' and `hash' methods in terms of `_check'
  88   and `_hash' methods, applying an optional encoding and attaching prefix and
  89   suffix strings.  The underscore methods have the same interface, but work
  90   in terms of raw binary password hashes.
  91
  92   There is a trivial implementation of `_check' included which is suitable
  93   for unsalted hashing schemes.
  94
  95   The `NULL' attribute is defined as `*', which commonly works for nontrivial
  96   password hashes, since it falls outside of the alphabet used in many
  97   encodings, and is anyway too short to match most fixed-length hash
  98   functions.  Subclasses should override this if it isn't suitable.
  99   """
 100
 101   NULL = '*'
 102
 103   def __init__(me, encoding = None, prefix = '', suffix = ''):
 104     """
 105     Initialize a password hashing scheme object.
 106
 107     A raw password hash is cooked by (a) applying an ENCODING (e.g.,
 108     `base64') and then (b) attaching a PREFIX and SUFFIX to the encoded
 109     hash.  This cooked hash is presented for storage in the database.
 110     """
 111     me._prefix = prefix
 112     me._suffix = suffix
 113     me._enc = U.ENCODINGS[encoding]
 114
 115   def hash(me, rec, passwd):
 116     """Hash the PASSWD using `_hash', and cook the resulting hash."""
 117     return me._prefix + me._enc.encode(me._hash(rec, passwd)) + me._suffix
 118
 119   def check(me, rec, hash, passwd):
 120     """
 121     Uncook the HASH and present the raw version to `_check' for checking.
 122     """
 123     if not hash.startswith(me._prefix) or \
 124        not hash.endswith(me._suffix):
 125       return False
 126     raw = me._enc.decode(hash[len(me._prefix):len(hash) - len(me._suffix)])
 127     return me._check(rec, raw, passwd)
 128
 129   def _check(me, rec, hash, passwd):
 130     """Trivial password checking: assumes that hashing is deterministic."""
 131     return me._hash(rec, passwd) == hash
 132
 133 ###--------------------------------------------------------------------------
 134 ### The trivial scheme.
 135
 136 class TrivialHash (BasicHash):
 137   """
 138   The trivial hashing scheme doesn't apply any hashing.
 139
 140   This is sometimes called `plain' format.
 141   """
 142   NULL = None
 143   def _hash(me, rec, passwd): return passwd
 144
 145 CONF.export('TrivialHash')
 146
 147 ###--------------------------------------------------------------------------
 148 ### The Unix crypt(3) scheme.
 149
 150 class CryptScheme (object):
 151   """
 152   Represents a particular version of the Unix crypt(3) hashing scheme.
 153
 154   The Unix crypt(3) function has grown over the ages, and now implements many
 155   different hashing schemes, with their own idiosyncratic salt conventions.
 156   Fortunately, most of them fit into a common framework, implemented here.
 157
 158   We assume that a valid salt consists of: a constant prefix, a fixed number
 159   of symbols chosen from a standard alphabet of 64, and a constant suffix.
 160   """
 161
 162   ## The salt alphabet.  This is not quite the standard Base64 alphabet, for
 163   ## some reason, but at least it doesn't have the pointless trailing `='
 164   ## signs.
 165   CHARS = '0123456789ABCDEFHIJKLMNOPQRSTUVWXYZabcdefghiklmnopqrstuvwxyz./'
 166
 167   def __init__(me, prefix, saltlen, suffix):
 168     """
 169     Initialize a crypt(3) scheme object.  A salt will consist of the PREFIX,
 170     followed by SALTLEN characters from `CHARS', followed by the SUFFIX.
 171     """
 172     me._prefix = prefix
 173     me._saltlen = saltlen
 174     me._suffix = suffix
 175
 176   def salt(me):
 177     """
 178     Return a fresh salt, according to the format appropriate for this
 179     crypt(3) scheme.
 180     """
 181     nbytes = (me._saltlen*3 + 3)//4
 182     bytes = OS.urandom(nbytes)
 183     salt = []
 184     a = 0
 185     abits = 0
 186     j = 0
 187     for i in xrange(me._saltlen):
 188       if abits < 6:
 189         next = ord(bytes[j])
 190         j += 1
 191         a |= next << abits
 192         abits += 8
 193       salt.append(me.CHARS[abits & 0x3f])
 194       a >>= 6
 195       abits -= 6
 196     return me._prefix + ''.join(salt) + me._suffix
 197
 198 class CryptHash (BasicHash):
 199   """
 200   Represents a hashing scheme based on the Unix crypt(3) function.
 201
 202   The parameters are a PREFIX and SUFFIX to be applied to the output hash,
 203   and a SCHEME, which may be any function which produces an appropriate salt
 204   string, or the name of the one of the built-in schemes listed in the
 205   `SCHEME' dictionary.
 206
 207   The encoding ability inherited from `BasicHash' is not used here, since
 208   crypt(3) already encodes hashes in its own strange way.
 209   """
 210
 211   ## A table of built-in schemes.
 212   SCHEME = {
 213     'des': CryptScheme('', 2, ''),
 214     'md5': CryptScheme('$1$', 8, '$'),
 215     'sha256': CryptScheme('$5$', 16, '$'),
 216     'sha512': CryptScheme('$6$', 16, '$')
 217   }
 218
 219   def __init__(me, scheme, *args, **kw):
 220     """Initialize a crypt(3) hashing scheme."""
 221     super(CryptHash, me).__init__(encoding = None, *args, **kw)
 222     try: me._salt = me.SCHEME[scheme].salt
 223     except KeyError: me._salt = scheme
 224
 225   def _check(me, rec, hash, passwd):
 226     """Check a password, by asking crypt(3) to do it."""
 227     return CR.crypt(passwd, hash) == hash
 228
 229   def _hash(me, rec, passwd):
 230     """Hash a password using fresh salt."""
 231     return CR.crypt(passwd, me._salt())
 232
 233 CONF.export('CryptHash')
 234
 235 ###--------------------------------------------------------------------------
 236 ### Simple application of a cryptographic hash.
 237
 238 class SimpleHash (BasicHash):
 239   """
 240   Represents a password hashing scheme which uses a cryptographic hash
 241   function simplistically, though possibly with salt.
 242
 243   There are many formatting choices available here, so we've picked one
 244   (which happens to match Dovecot's conventions) and hidden it behind a
 245   simple bit of protocol so that users can define their own variants.  A
 246   subclass could easily implement, say, the DIGEST-MD5 convention.
 247
 248   See the `hash_preimage', `hash_format' and `hash_parse' methods for details
 249   of the formatting protocol.
 250   """
 251
 252   def __init__(me, hash, saltlen = 0, encoding = 'base64', *args, **kw):
 253     """
 254     Initialize a simple hashing scheme.
 255
 256     The ENCODING, PREFIX, and SUFFIX arguments are standard.  The (required)
 257     HASH argument selects a hash function known to Python's `hashlib'
 258     module.  The SALTLEN is the length of salt to generate, in octets.
 259     """
 260     super(SimpleHash, me).__init__(encoding = encoding, *args, **kw)
 261     me._hashfn = hash
 262     me.hashlen = H.new(me._hashfn).digest_size
 263     me.saltlen = saltlen
 264
 265   def _hash(me, rec, passwd):
 266     """Generate a fresh salted hash."""
 267     hc = H.new(me._hashfn)
 268     salt = OS.urandom(me._saltlen)
 269     me.hash_preimage(rec, hc, passwd, salt)
 270     return me.hash_format(rec, hc.digest(), salt)
 271
 272   def _check(me, rec, hash, passwd):
 273     """Check a password against an existing hash."""
 274     hash, salt = me.hash_parse(rec, hash)
 275     hc = H.new(me._hashfn)
 276     me.hash_preimage(rec, hc, passwd, salt)
 277     h = hc.digest()
 278     return h == hash
 279
 280   def hash_preimage(me, hc, rec, passwd, salt):
 281     """
 282     Feed whatever material is appropriate into the hash context HC.
 283
 284     The REC, PASSWD and SALT arguments are the database record (which may
 285     carry interesting information in additional fields), the user's password,
 286     and the salt, respectively.
 287     """
 288     hc.update(passwd)
 289     hc.update(salt)
 290
 291   def hash_format(me, rec, hash, salt):
 292     """Format a HASH and SALT for storage.  See also `hash_parse'."""
 293     return hash + salt
 294
 295   def hash_parse(me, rec, raw):
 296     """Parse the result of `hash_format' into a (HASH, SALT) pair."""
 297     return raw[:me.hashlen], raw[me.hashlen:]
 298
 299 CONF.export('SimpleHash')
 300
 301 ### The CRAM-MD5 scheme.
 302
 303 class CRAMMD5Hash (BasicHash):
 304   """
 305   Dovecot can use partially hashed passwords with the CRAM-MD5 authentication
 306   scheme, if they're formatted just right.  This hashing scheme does the
 307   right thing.
 308
 309   CRAM-MD5 works by applying HMAC-MD5 to a challenge string, using the user's
 310   password as an HMAC key.  HMAC(k, m) = H(o || H(i || m)), where o and i are
 311   whole blocks of stuff derived from the key k in a simple way.  Rather than
 312   storing k, then, we can store the results of applying the MD5 compression
 313   function to o and i.
 314   """
 315
 316   def __init__(me, encoding = 'hex', *args, **kw):
 317     """Initialize the CRAM-MD5 scheme.  We change the default encoding."""
 318     super(CRAMMD5Hash, me).__init__(encoding = encoding, *args, **kw)
 319
 320   def _hash(me, rec, passwd):
 321     """Hash a password, following the HMAC rules."""
 322
 323     ## If the key is longer than the hash function's block size, we're
 324     ## required to hash it first.
 325     if len(passwd) > 64:
 326       h = H.new('md5')
 327       h.update(passwd)
 328       passwd = h.digest()
 329
 330     ## Compute the key schedule.
 331     return ''.join(C.compress_md5(''.join(chr(ord(c) ^ pad)
 332                                           for c in passwd.ljust(64, '\0')))
 333                    for pad in [0x5c, 0x36])
 334
 335 CONF.export('CRAMMD5Hash')
 336
 337 ###----- That's all, folks --------------------------------------------------