| 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 -------------------------------------------------- |