service.py: Fix the RemoteService `_mkcmd' protocol.

[chopwood] / hash.py

### -*-python-*-
###
### Password hashing schemes
###
### (c) 2013 Mark Wooding
###

###----- Licensing notice ---------------------------------------------------
###
### This file is part of Chopwood: a password-changing service.
###
### Chopwood is free software; you can redistribute it and/or modify
### it under the terms of the GNU Affero General Public License as
### published by the Free Software Foundation; either version 3 of the
### License, or (at your option) any later version.
###
### Chopwood is distributed in the hope that it will be useful,
### but WITHOUT ANY WARRANTY; without even the implied warranty of
### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
### GNU Affero General Public License for more details.
###
### You should have received a copy of the GNU Affero General Public
### License along with Chopwood; if not, see
### <http://www.gnu.org/licenses/>.

from __future__ import with_statement

import crypt as CR
import hashlib as H
import os as OS

import config as CONF
import crypto as C
import util as U

###--------------------------------------------------------------------------
### Protocol.
###
### A password hashing scheme knows about how to convert a plaintext password
### into whatever it is that gets stored in the database.  The important
### consideration is that this conversion is potentially randomized, using a
### `salt'.
###
### There are two contexts in which we want to do the conversion.  The first
### case is that we've somehow come up with a new password, and wish to write
### it to the database; we therefore need to come up with fresh random salt.
### The second case is that we're verifying a password against the database;
### here, we must extract and reuse the salt used when the database record
### was written.  This latter case is only used for verifying passwords in
### the CGI interface, so it might be acceptable to fail to implement it in
### some cases, but we don't need this freedom.
###
### It turns out that there's a useful division of labour we can make,
### because hashing is a two-stage process.  The first stage takes a salt and
### a password, and processes them somehow to form a hash.  The second stage
### takes this hash, and encodes and decorates it to form something which can
### usefully be stored in a database.  Most of the latter processing is
### handled in the `BasicHash' class.
###
### Hashing is not done in isolation: rather, it's done within the context of
### a database record, so that additional material (e.g., the user name, or
### some `realm' indicator) can be fed into the hashing process.  None of the
### hashing schemes here do this, but user configuration can easily subclass,
### say, `SimpleHash' to implement something like Dovecot's DIGEST-MD5
### scheme.
###
### The external password hashing protocol consists of the following pieces.
###
### hash(REC, PASSWD)
###     Method: return a freshly salted hash for the password PASSWD, using
###     information from the database record REC.
###
### check(REC, HASH, PASSWD)
###     Method: if the password PASSWD (and other information in the database
###     record REC) matches the HASH, return true; otherwise return false.
###
### NULL
###     Attribute: a string which can (probably) be stored safely in the
###     password database, but which doesn't equal any valid password hash.
###     This is used for clearing passwords.  If None, there is no such
###     value, and passwords cannot be cleared using this hashing scheme.

class BasicHash (object):
  """
  Convenient base class for password hashing schemes.

  This class implements the `check' and `hash' methods in terms of `_check'
  and `_hash' methods, applying an optional encoding and attaching prefix and
  suffix strings.  The underscore methods have the same interface, but work
  in terms of raw binary password hashes.

  There is a trivial implementation of `_check' included which is suitable
  for unsalted hashing schemes.

  The `NULL' attribute is defined as `*', which commonly works for nontrivial
  password hashes, since it falls outside of the alphabet used in many
  encodings, and is anyway too short to match most fixed-length hash
  functions.  Subclasses should override this if it isn't suitable.
  """

  NULL = '*'

  def __init__(me, encoding = None, prefix = '', suffix = ''):
    """
    Initialize a password hashing scheme object.

    A raw password hash is cooked by (a) applying an ENCODING (e.g.,
    `base64') and then (b) attaching a PREFIX and SUFFIX to the encoded
    hash.  This cooked hash is presented for storage in the database.
    """
    me._prefix = prefix
    me._suffix = suffix
    me._enc = U.ENCODINGS[encoding]

  def hash(me, rec, passwd):
    """Hash the PASSWD using `_hash', and cook the resulting hash."""
    return me._prefix + me._enc.encode(me._hash(rec, passwd)) + me._suffix

  def check(me, rec, hash, passwd):
    """
    Uncook the HASH and present the raw version to `_check' for checking.
    """
    if not hash.startswith(me._prefix) or \
       not hash.endswith(me._suffix):
      return False
    raw = me._enc.decode(hash[len(me._prefix):len(hash) - len(me._suffix)])
    return me._check(rec, raw, passwd)

  def _check(me, rec, hash, passwd):
    """Trivial password checking: assumes that hashing is deterministic."""
    return me._hash(rec, passwd) == hash

###--------------------------------------------------------------------------
### The trivial scheme.

class TrivialHash (BasicHash):
  """
  The trivial hashing scheme doesn't apply any hashing.

  This is sometimes called `plain' format.
  """
  NULL = None
  def _hash(me, rec, passwd): return passwd

CONF.export('TrivialHash')

###--------------------------------------------------------------------------
### The Unix crypt(3) scheme.

class CryptScheme (object):
  """
  Represents a particular version of the Unix crypt(3) hashing scheme.

  The Unix crypt(3) function has grown over the ages, and now implements many
  different hashing schemes, with their own idiosyncratic salt conventions.
  Fortunately, most of them fit into a common framework, implemented here.

  We assume that a valid salt consists of: a constant prefix, a fixed number
  of symbols chosen from a standard alphabet of 64, and a constant suffix.
  """

  ## The salt alphabet.  This is not quite the standard Base64 alphabet, for
  ## some reason, but at least it doesn't have the pointless trailing `='
  ## signs.
  CHARS = '0123456789ABCDEFHIJKLMNOPQRSTUVWXYZabcdefghiklmnopqrstuvwxyz./'

  def __init__(me, prefix, saltlen, suffix):
    """
    Initialize a crypt(3) scheme object.  A salt will consist of the PREFIX,
    followed by SALTLEN characters from `CHARS', followed by the SUFFIX.
    """
    me._prefix = prefix
    me._saltlen = saltlen
    me._suffix = suffix

  def salt(me):
    """
    Return a fresh salt, according to the format appropriate for this
    crypt(3) scheme.
    """
    nbytes = (me._saltlen*3 + 3)//4
    bytes = OS.urandom(nbytes)
    salt = []
    a = 0
    abits = 0
    j = 0
    for i in xrange(me._saltlen):
      if abits < 6:
        next = ord(bytes[j])
        j += 1
        a |= next << abits
        abits += 8
      salt.append(me.CHARS[abits & 0x3f])
      a >>= 6
      abits -= 6
    return me._prefix + ''.join(salt) + me._suffix

class CryptHash (BasicHash):
  """
  Represents a hashing scheme based on the Unix crypt(3) function.

  The parameters are a PREFIX and SUFFIX to be applied to the output hash,
  and a SCHEME, which may be any function which produces an appropriate salt
  string, or the name of the one of the built-in schemes listed in the
  `SCHEME' dictionary.

  The encoding ability inherited from `BasicHash' is not used here, since
  crypt(3) already encodes hashes in its own strange way.
  """

  ## A table of built-in schemes.
  SCHEME = {
    'des': CryptScheme('', 2, ''),
    'md5': CryptScheme('$1$', 8, '$'),
    'sha256': CryptScheme('$5$', 16, '$'),
    'sha512': CryptScheme('$6$', 16, '$')
  }

  def __init__(me, scheme, *args, **kw):
    """Initialize a crypt(3) hashing scheme."""
    super(CryptHash, me).__init__(encoding = None, *args, **kw)
    try: me._salt = me.SCHEME[scheme].salt
    except KeyError: me._salt = scheme

  def _check(me, rec, hash, passwd):
    """Check a password, by asking crypt(3) to do it."""
    return CR.crypt(passwd, hash) == hash

  def _hash(me, rec, passwd):
    """Hash a password using fresh salt."""
    return CR.crypt(passwd, me._salt())

CONF.export('CryptHash')

###--------------------------------------------------------------------------
### Simple application of a cryptographic hash.

class SimpleHash (BasicHash):
  """
  Represents a password hashing scheme which uses a cryptographic hash
  function simplistically, though possibly with salt.

  There are many formatting choices available here, so we've picked one
  (which happens to match Dovecot's conventions) and hidden it behind a
  simple bit of protocol so that users can define their own variants.  A
  subclass could easily implement, say, the DIGEST-MD5 convention.

  See the `hash_preimage', `hash_format' and `hash_parse' methods for details
  of the formatting protocol.
  """

  def __init__(me, hash, saltlen = 0, encoding = 'base64', *args, **kw):
    """
    Initialize a simple hashing scheme.

    The ENCODING, PREFIX, and SUFFIX arguments are standard.  The (required)
    HASH argument selects a hash function known to Python's `hashlib'
    module.  The SALTLEN is the length of salt to generate, in octets.
    """
    super(SimpleHash, me).__init__(encoding = encoding, *args, **kw)
    me._hashfn = hash
    me.hashlen = H.new(me._hashfn).digest_size
    me.saltlen = saltlen

  def _hash(me, rec, passwd):
    """Generate a fresh salted hash."""
    hc = H.new(me._hashfn)
    salt = OS.urandom(me._saltlen)
    me.hash_preimage(rec, hc, passwd, salt)
    return me.hash_format(rec, hc.digest(), salt)

  def _check(me, rec, hash, passwd):
    """Check a password against an existing hash."""
    hash, salt = me.hash_parse(rec, hash)
    hc = H.new(me._hashfn)
    me.hash_preimage(rec, hc, passwd, salt)
    h = hc.digest()
    return h == hash

  def hash_preimage(me, hc, rec, passwd, salt):
    """
    Feed whatever material is appropriate into the hash context HC.

    The REC, PASSWD and SALT arguments are the database record (which may
    carry interesting information in additional fields), the user's password,
    and the salt, respectively.
    """
    hc.update(passwd)
    hc.update(salt)

  def hash_format(me, rec, hash, salt):
    """Format a HASH and SALT for storage.  See also `hash_parse'."""
    return hash + salt

  def hash_parse(me, rec, raw):
    """Parse the result of `hash_format' into a (HASH, SALT) pair."""
    return raw[:me.hashlen], raw[me.hashlen:]

CONF.export('SimpleHash')

### The CRAM-MD5 scheme.

class CRAMMD5Hash (BasicHash):
  """
  Dovecot can use partially hashed passwords with the CRAM-MD5 authentication
  scheme, if they're formatted just right.  This hashing scheme does the
  right thing.

  CRAM-MD5 works by applying HMAC-MD5 to a challenge string, using the user's
  password as an HMAC key.  HMAC(k, m) = H(o || H(i || m)), where o and i are
  whole blocks of stuff derived from the key k in a simple way.  Rather than
  storing k, then, we can store the results of applying the MD5 compression
  function to o and i.
  """

  def __init__(me, encoding = 'hex', *args, **kw):
    """Initialize the CRAM-MD5 scheme.  We change the default encoding."""
    super(CRAMMD5Hash, me).__init__(encoding = encoding, *args, **kw)

  def _hash(me, rec, passwd):
    """Hash a password, following the HMAC rules."""

    ## If the key is longer than the hash function's block size, we're
    ## required to hash it first.
    if len(passwd) > 64:
      h = H.new('md5')
      h.update(passwd)
      passwd = h.digest()

    ## Compute the key schedule.
    return ''.join(C.compress_md5(''.join(chr(ord(c) ^ pad)
                                          for c in passwd.ljust(64, '\0')))
                   for pad in [0x5c, 0x36])

CONF.export('CRAMMD5Hash')

###----- That's all, folks --------------------------------------------------