chiark / gitweb /
Initial commit.
[chopwood] / hash.py
CommitLineData
a2916c06
MW
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
26from __future__ import with_statement
27
28import crypt as CR
29import hashlib as H
30import os as OS
31
32import config as CONF
33import crypto as C
34import 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
83class 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
136class 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
145CONF.export('TrivialHash')
146
147###--------------------------------------------------------------------------
148### The Unix crypt(3) scheme.
149
150class 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
198class 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
233CONF.export('CryptHash')
234
235###--------------------------------------------------------------------------
236### Simple application of a cryptographic hash.
237
238class 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
299CONF.export('SimpleHash')
300
301### The CRAM-MD5 scheme.
302
303class 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
335CONF.export('CRAMMD5Hash')
336
337###----- That's all, folks --------------------------------------------------