Commit | Line | Data |
---|---|---|
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 | ||
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 -------------------------------------------------- |