3 ### Password hashing schemes
5 ### (c) 2013 Mark Wooding
8 ###----- Licensing notice ---------------------------------------------------
10 ### This file is part of Chopwood: a password-changing service.
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.
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.
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/>.
26 from __future__ import with_statement
36 ###--------------------------------------------------------------------------
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
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.
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.
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
67 ### The external password hashing protocol consists of the following pieces.
70 ### Method: return a freshly salted hash for the password PASSWD, using
71 ### information from the database record REC.
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.
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.
83 class BasicHash (object):
85 Convenient base class for password hashing schemes.
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.
92 There is a trivial implementation of `_check' included which is suitable
93 for unsalted hashing schemes.
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.
103 def __init__(me, encoding = None, prefix = '', suffix = ''):
105 Initialize a password hashing scheme object.
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.
113 me._enc = U.ENCODINGS[encoding]
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
119 def check(me, rec, hash, passwd):
121 Uncook the HASH and present the raw version to `_check' for checking.
123 if not hash.startswith(me._prefix) or \
124 not hash.endswith(me._suffix):
126 raw = me._enc.decode(hash[len(me._prefix):len(hash) - len(me._suffix)])
127 return me._check(rec, raw, passwd)
129 def _check(me, rec, hash, passwd):
130 """Trivial password checking: assumes that hashing is deterministic."""
131 return me._hash(rec, passwd) == hash
133 ###--------------------------------------------------------------------------
134 ### The trivial scheme.
136 class TrivialHash (BasicHash):
138 The trivial hashing scheme doesn't apply any hashing.
140 This is sometimes called `plain' format.
143 def _hash(me, rec, passwd): return passwd
145 CONF.export('TrivialHash')
147 ###--------------------------------------------------------------------------
148 ### The Unix crypt(3) scheme.
150 class CryptScheme (object):
152 Represents a particular version of the Unix crypt(3) hashing scheme.
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.
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.
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 `='
165 CHARS = '0123456789ABCDEFHIJKLMNOPQRSTUVWXYZabcdefghiklmnopqrstuvwxyz./'
167 def __init__(me, prefix, saltlen, suffix):
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.
173 me._saltlen = saltlen
178 Return a fresh salt, according to the format appropriate for this
181 nbytes = (me._saltlen*3 + 3)//4
182 bytes = OS.urandom(nbytes)
187 for i in xrange(me._saltlen):
193 salt.append(me.CHARS[abits & 0x3f])
196 return me._prefix + ''.join(salt) + me._suffix
198 class CryptHash (BasicHash):
200 Represents a hashing scheme based on the Unix crypt(3) function.
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
207 The encoding ability inherited from `BasicHash' is not used here, since
208 crypt(3) already encodes hashes in its own strange way.
211 ## A table of built-in schemes.
213 'des': CryptScheme('', 2, ''),
214 'md5': CryptScheme('$1$', 8, '$'),
215 'sha256': CryptScheme('$5$', 16, '$'),
216 'sha512': CryptScheme('$6$', 16, '$')
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
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
229 def _hash(me, rec, passwd):
230 """Hash a password using fresh salt."""
231 return CR.crypt(passwd, me._salt())
233 CONF.export('CryptHash')
235 ###--------------------------------------------------------------------------
236 ### Simple application of a cryptographic hash.
238 class SimpleHash (BasicHash):
240 Represents a password hashing scheme which uses a cryptographic hash
241 function simplistically, though possibly with salt.
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.
248 See the `hash_preimage', `hash_format' and `hash_parse' methods for details
249 of the formatting protocol.
252 def __init__(me, hash, saltlen = 0, encoding = 'base64', *args, **kw):
254 Initialize a simple hashing scheme.
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.
260 super(SimpleHash, me).__init__(encoding = encoding, *args, **kw)
262 me.hashlen = H.new(me._hashfn).digest_size
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)
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)
280 def hash_preimage(me, hc, rec, passwd, salt):
282 Feed whatever material is appropriate into the hash context HC.
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.
291 def hash_format(me, rec, hash, salt):
292 """Format a HASH and SALT for storage. See also `hash_parse'."""
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:]
299 CONF.export('SimpleHash')
301 ### The CRAM-MD5 scheme.
303 class CRAMMD5Hash (BasicHash):
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
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
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)
320 def _hash(me, rec, passwd):
321 """Hash a password, following the HMAC rules."""
323 ## If the key is longer than the hash function's block size, we're
324 ## required to hash it first.
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])
335 CONF.export('CRAMMD5Hash')
337 ###----- That's all, folks --------------------------------------------------