summaryrefslogtreecommitdiff
path: root/includes/utils/MWCryptHKDF.php
blob: 740df922414388a1fd1ad0195c2f9f97bef95d87 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
<?php
/**
 * Extract-and-Expand Key Derivation Function (HKDF). A cryptographicly
 * secure key expansion function based on RFC 5869.
 *
 * This relies on the secrecy of $wgSecretKey (by default), or $wgHKDFSecret.
 * By default, sha256 is used as the underlying hashing algorithm, but any other
 * algorithm can be used. Finding the secret key from the output would require
 * an attacker to discover the input key (the PRK) to the hmac that generated
 * the output, and discover the particular data, hmac'ed with an evolving key
 * (salt), to produce the PRK. Even with md5, no publicly known attacks make
 * this currently feasible.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 * http://www.gnu.org/copyleft/gpl.html
 *
 * @author Chris Steipp
 * @file
 */

class MWCryptHKDF {

	/**
	 * Singleton instance for public use
	 */
	protected static $singleton = null;

	/**
	 * The persistant cache
	 */
	protected $cache = null;

	/**
	 * Cache key we'll use for our salt
	 */
	protected $cacheKey = null;

	/**
	 * The hash algorithm being used
	 */
	protected $algorithm = null;

	/**
	 * binary string, the salt for the HKDF
	 */
	protected $salt;

	/**
	 * The pseudorandom key
	 */
	private $prk;

	/**
	 * The secret key material. This must be kept secret to preserve
	 * the security properties of this RNG.
	 */
	private $skm;

	/**
	 * The last block (K(i)) of the most recent expanded key
	 */
	protected $lastK;

	/**
	 * a "context information" string CTXinfo (which may be null)
	 * See http://eprint.iacr.org/2010/264.pdf Section 4.1
	 */
	protected $context = array();

	/**
	 * Round count is computed based on the hash'es output length,
	 * which neither php nor openssl seem to provide easily.
	 */
	public static $hashLength = array(
		'md5' => 16,
		'sha1' => 20,
		'sha224' => 28,
		'sha256' => 32,
		'sha384' => 48,
		'sha512' => 64,
		'ripemd128' => 16,
		'ripemd160' => 20,
		'ripemd256' => 32,
		'ripemd320' => 40,
		'whirlpool' => 64,
	);


	/**
	 * @param string $secretKeyMaterial
	 * @param string $algorithm Name of hashing algorithm
	 * @param BagOStuff $cache
	 * @param string|array $context Context to mix into HKDF context
	 * @throws MWException
	 */
	public function __construct( $secretKeyMaterial, $algorithm, $cache, $context ) {
		if ( strlen( $secretKeyMaterial ) < 16 ) {
			throw new MWException( "MWCryptHKDF secret was too short." );
		}
		$this->skm = $secretKeyMaterial;
		$this->algorithm = $algorithm;
		$this->cache = $cache;
		$this->salt = ''; // Initialize a blank salt, see getSaltUsingCache()
		$this->prk = '';
		$this->context = is_array( $context ) ? $context : array( $context );

		// To prevent every call from hitting the same memcache server, pick
		// from a set of keys to use. mt_rand is only use to pick a random
		// server, and does not affect the security of the process.
		$this->cacheKey = wfMemcKey( 'HKDF', mt_rand( 0, 16 ) );
	}

	/**
	 * Save the last block generated, so the next user will compute a different PRK
	 * from the same SKM. This should keep things unpredictable even if an attacker
	 * is able to influence CTXinfo.
	 */
	function __destruct() {
		if ( $this->lastK ) {
			$this->cache->set( $this->cacheKey, $this->lastK );
		}
	}

	/**
	 * MW specific salt, cached from last run
	 * @return string Binary string
	 */
	protected function getSaltUsingCache() {
		if ( $this->salt == '' ) {
			$lastSalt = $this->cache->get( $this->cacheKey );
			if ( $lastSalt === false ) {
				// If we don't have a previous value to use as our salt, we use
				// 16 bytes from MWCryptRand, which will use a small amount of
				// entropy from our pool. Note, "XTR may be deterministic or keyed
				// via an optional “salt value”  (i.e., a non-secret random
				// value)..." - http://eprint.iacr.org/2010/264.pdf. However, we
				// use a strongly random value since we can.
				$lastSalt = MWCryptRand::generate( 16 );
			}
			// Get a binary string that is hashLen long
			$this->salt = hash( $this->algorithm, $lastSalt, true );
		}
		return $this->salt;
	}

	/**
	 * Return a singleton instance, based on the global configs.
	 * @return HKDF
	 * @throws MWException
	 */
	protected static function singleton() {
		global $wgHKDFAlgorithm, $wgHKDFSecret, $wgSecretKey, $wgMainCacheType;

		$secret = $wgHKDFSecret ?: $wgSecretKey;
		if ( !$secret ) {
			throw new MWException( "Cannot use MWCryptHKDF without a secret." );
		}

		// In HKDF, the context can be known to the attacker, but this will
		// keep simultaneous runs from producing the same output.
		$context = array();
		$context[] = microtime();
		$context[] = getmypid();
		$context[] = gethostname();

		// Setup salt cache. Use APC, or fallback to the main cache if it isn't setup
		$cache = ObjectCache::newAccelerator( $wgMainCacheType );

		if ( is_null( self::$singleton ) ) {
			self::$singleton = new self( $secret, $wgHKDFAlgorithm, $cache, $context );
		}

		return self::$singleton;
	}

	/**
	 * Produce $bytes of secure random data. As a side-effect,
	 * $this->lastK is set to the last hashLen block of key material.
	 * @param int $bytes Number of bytes of data
	 * @param string $context Context to mix into CTXinfo
	 * @return string Binary string of length $bytes
	 */
	protected function realGenerate( $bytes, $context = '' ) {

		if ( $this->prk === '' ) {
			$salt = $this->getSaltUsingCache();
			$this->prk = self::HKDFExtract(
				$this->algorithm,
				$salt,
				$this->skm
			);
		}

		$CTXinfo = implode( ':', array_merge( $this->context, array( $context ) ) );

		return self::HKDFExpand(
			$this->algorithm,
			$this->prk,
			$CTXinfo,
			$bytes,
			$this->lastK
		);
	}


	/**
	 * RFC5869 defines HKDF in 2 steps, extraction and expansion.
	 * From http://eprint.iacr.org/2010/264.pdf:
	 *
	 * The scheme HKDF is specifed as:
	 * 	HKDF(XTS, SKM, CTXinfo, L) = K(1) || K(2) || ... || K(t)
	 * where the values K(i) are defined as follows:
	 * 	PRK = HMAC(XTS, SKM)
	 * 	K(1) = HMAC(PRK, CTXinfo || 0);
	 * 	K(i+1) = HMAC(PRK, K(i) || CTXinfo || i), 1 <= i < t;
	 * where t = [L/k] and the value K(t) is truncated to its first d = L mod k bits;
	 * the counter i is non-wrapping and of a given fixed size, e.g., a single byte.
	 * Note that the length of the HMAC output is the same as its key length and therefore
	 * the scheme is well defined.
	 *
	 * XTS is the "extractor salt"
	 * SKM is the "secret keying material"
	 *
	 * N.B. http://eprint.iacr.org/2010/264.pdf seems to differ from RFC 5869 in that the test
	 * vectors from RFC 5869 only work if K(0) = '' and K(1) = HMAC(PRK, K(0) || CTXinfo || 1)
	 *
	 * @param string $hash The hashing function to use (e.g., sha256)
	 * @param string $ikm The input keying material
	 * @param string $salt The salt to add to the ikm, to get the prk
	 * @param string $info Optional context (change the output without affecting
	 *	the randomness properties of the output)
	 * @param int $L Number of bytes to return
	 * @return string Cryptographically secure pseudorandom binary string
	 */
	public static function HKDF( $hash, $ikm, $salt, $info, $L ) {
		$prk = self::HKDFExtract( $hash, $salt, $ikm );
		$okm = self::HKDFExpand( $hash, $prk, $info, $L );
		return $okm;
	}

	/**
	 * Extract the PRK, PRK = HMAC(XTS, SKM)
	 * Note that the hmac is keyed with XTS (the salt),
	 * and the SKM (source key material) is the "data".
	 *
	 * @param string $hash The hashing function to use (e.g., sha256)
	 * @param string $salt The salt to add to the ikm, to get the prk
	 * @param string $ikm The input keying material
	 * @return string Binary string (pseudorandm key) used as input to HKDFExpand
	 */
	private static function HKDFExtract( $hash, $salt, $ikm ) {
		return hash_hmac( $hash, $ikm, $salt, true );
	}

	/**
	 * Expand the key with the given context
	 *
	 * @param string $hash Hashing Algorithm
	 * @param string $prk A pseudorandom key of at least HashLen octets
	 *    (usually, the output from the extract step)
	 * @param string $info Optional context and application specific information
	 *    (can be a zero-length string)
	 * @param int $bytes Length of output keying material in bytes
	 *    (<= 255*HashLen)
	 * @param string &$lastK Set by this function to the last block of the expansion.
	 *    In MediaWiki, this is used to seed future Extractions.
	 * @return string Cryptographically secure random string $bytes long
	 * @throws MWException
	 */
	private static function HKDFExpand( $hash, $prk, $info, $bytes, &$lastK = '' ) {
		$hashLen = MWCryptHKDF::$hashLength[$hash];
		$rounds = ceil( $bytes / $hashLen );
		$output = '';

		if ( $bytes > 255 * $hashLen ) {
			throw new MWException( "Too many bytes requested from HDKFExpand" );
		}

		// K(1) = HMAC(PRK, CTXinfo || 1);
		// K(i) = HMAC(PRK, K(i-1) || CTXinfo || i); 1 < i <= t;
		for ( $counter = 1; $counter <= $rounds; ++$counter ) {
			$lastK = hash_hmac(
				$hash,
				$lastK . $info . chr( $counter ),
				$prk,
				true
			);
			$output .= $lastK;
		}

		return substr( $output, 0, $bytes );
	}

	/**
	 * Generate cryptographically random data and return it in raw binary form.
	 *
	 * @param int $bytes The number of bytes of random data to generate
	 * @param string $context String to mix into HMAC context
	 * @return string Binary string of length $bytes
	 */
	public static function generate( $bytes, $context ) {
		return self::singleton()->realGenerate( $bytes, $context );
	}

	/**
	 * Generate cryptographically random data and return it in hexadecimal string format.
	 * See MWCryptRand::realGenerateHex for details of the char-to-byte conversion logic.
	 *
	 * @param int $chars The number of hex chars of random data to generate
	 * @param string $context String to mix into HMAC context
	 * @return string Random hex characters, $chars long
	 */
	public static function generateHex( $chars, $context = '' ) {
		$bytes = ceil( $chars / 2 );
		$hex = bin2hex( self::singleton()->realGenerate( $bytes, $context ) );
		return substr( $hex, 0, $chars );
	}

}