1<?php
2/**
3 * Extract-and-Expand Key Derivation Function (HKDF). A cryptographicly
4 * secure key expansion function based on RFC 5869.
5 *
6 * This relies on the secrecy of $wgSecretKey (by default), or $wgHKDFSecret.
7 * By default, sha256 is used as the underlying hashing algorithm, but any other
8 * algorithm can be used. Finding the secret key from the output would require
9 * an attacker to discover the input key (the PRK) to the hmac that generated
10 * the output, and discover the particular data, hmac'ed with an evolving key
11 * (salt), to produce the PRK. Even with md5, no publicly known attacks make
12 * this currently feasible.
13 *
14 * This program is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (at your option) any later version.
18 *
19 * This program is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License along
25 * with this program; if not, write to the Free Software Foundation, Inc.,
26 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
27 * http://www.gnu.org/copyleft/gpl.html
28 *
29 * @author Chris Steipp
30 * @file
31 */
32
33class CryptHKDF {
34
35	/**
36	 * @var BagOStuff The persistent cache
37	 */
38	protected $cache = null;
39
40	/**
41	 * @var string Cache key we'll use for our salt
42	 */
43	protected $cacheKey = null;
44
45	/**
46	 * @var string The hash algorithm being used
47	 */
48	protected $algorithm = null;
49
50	/**
51	 * @var string binary string, the salt for the HKDF
52	 * @see getSaltUsingCache
53	 */
54	protected $salt = '';
55
56	/**
57	 * @var string The pseudorandom key
58	 */
59	private $prk = '';
60
61	/**
62	 * The secret key material. This must be kept secret to preserve
63	 * the security properties of this RNG.
64	 *
65	 * @var string
66	 */
67	private $skm;
68
69	/**
70	 * @var string The last block (K(i)) of the most recent expanded key
71	 */
72	protected $lastK;
73
74	/**
75	 * a "context information" string CTXinfo (which may be null)
76	 * See http://eprint.iacr.org/2010/264.pdf Section 4.1
77	 *
78	 * @var array
79	 */
80	protected $context = [];
81
82	/**
83	 * Round count is computed based on the hash'es output length,
84	 * which neither php nor openssl seem to provide easily.
85	 *
86	 * @var int[]
87	 */
88	public static $hashLength = [
89		'md5' => 16,
90		'sha1' => 20,
91		'sha224' => 28,
92		'sha256' => 32,
93		'sha384' => 48,
94		'sha512' => 64,
95		'ripemd128' => 16,
96		'ripemd160' => 20,
97		'ripemd256' => 32,
98		'ripemd320' => 40,
99		'whirlpool' => 64,
100	];
101
102	/**
103	 * @param string $secretKeyMaterial
104	 * @param string $algorithm Name of hashing algorithm
105	 * @param BagOStuff $cache
106	 * @param string|array $context Context to mix into HKDF context
107	 * @throws InvalidArgumentException if secret key material is too short
108	 */
109	public function __construct( $secretKeyMaterial, $algorithm, BagOStuff $cache, $context ) {
110		if ( strlen( $secretKeyMaterial ) < 16 ) {
111			throw new InvalidArgumentException( "secret was too short." );
112		}
113		$this->skm = $secretKeyMaterial;
114		$this->algorithm = $algorithm;
115		$this->cache = $cache;
116		$this->context = is_array( $context ) ? $context : [ $context ];
117
118		// To prevent every call from hitting the same memcache server, pick
119		// from a set of keys to use. mt_rand is only use to pick a random
120		// server, and does not affect the security of the process.
121		$this->cacheKey = $cache->makeKey( 'HKDF', mt_rand( 0, 16 ) );
122	}
123
124	/**
125	 * Save the last block generated, so the next user will compute a different PRK
126	 * from the same SKM. This should keep things unpredictable even if an attacker
127	 * is able to influence CTXinfo.
128	 */
129	public function __destruct() {
130		if ( $this->lastK ) {
131			$this->cache->set( $this->cacheKey, $this->lastK );
132		}
133	}
134
135	/**
136	 * MW specific salt, cached from last run
137	 * @return string Binary string
138	 */
139	protected function getSaltUsingCache() {
140		if ( $this->salt == '' ) {
141			$lastSalt = $this->cache->get( $this->cacheKey );
142			if ( $lastSalt === false ) {
143				// If we don't have a previous value to use as our salt, we use
144				// 16 bytes from random_bytes(), which will use a small amount of
145				// entropy from our pool. Note, "XTR may be deterministic or keyed
146				// via an optional “salt value”  (i.e., a non-secret random
147				// value)..." - http://eprint.iacr.org/2010/264.pdf. However, we
148				// use a strongly random value since we can.
149				$lastSalt = random_bytes( 16 );
150			}
151			// Get a binary string that is hashLen long
152			$this->salt = hash( $this->algorithm, $lastSalt, true );
153		}
154		return $this->salt;
155	}
156
157	/**
158	 * Produce $bytes of secure random data. As a side-effect,
159	 * $this->lastK is set to the last hashLen block of key material.
160	 *
161	 * @param int $bytes Number of bytes of data
162	 * @param string $context Context to mix into CTXinfo
163	 * @return string Binary string of length $bytes
164	 */
165	public function generate( $bytes, $context = '' ) {
166		if ( $this->prk === '' ) {
167			$salt = $this->getSaltUsingCache();
168			$this->prk = self::HKDFExtract(
169				$this->algorithm,
170				$salt,
171				$this->skm
172			);
173		}
174
175		$CTXinfo = implode( ':', array_merge( $this->context, [ $context ] ) );
176
177		return self::HKDFExpand(
178			$this->algorithm,
179			$this->prk,
180			$CTXinfo,
181			$bytes,
182			$this->lastK
183		);
184	}
185
186	/**
187	 * RFC5869 defines HKDF in 2 steps, extraction and expansion.
188	 * From http://eprint.iacr.org/2010/264.pdf:
189	 *
190	 * The scheme HKDF is specifed as:
191	 *   HKDF(XTS, SKM, CTXinfo, L) = K(1) || K(2) || ... || K(t)
192	 * where the values K(i) are defined as follows:
193	 *   PRK = HMAC(XTS, SKM)
194	 *   K(1) = HMAC(PRK, CTXinfo || 0);
195	 *   K(i+1) = HMAC(PRK, K(i) || CTXinfo || i), 1 <= i < t;
196	 * where t = [L/k] and the value K(t) is truncated to its first d = L mod k bits;
197	 * the counter i is non-wrapping and of a given fixed size, e.g., a single byte.
198	 * Note that the length of the HMAC output is the same as its key length and therefore
199	 * the scheme is well defined.
200	 *
201	 * XTS is the "extractor salt"
202	 * SKM is the "secret keying material"
203	 *
204	 * N.B. http://eprint.iacr.org/2010/264.pdf seems to differ from RFC 5869 in that the test
205	 * vectors from RFC 5869 only work if K(0) = '' and K(1) = HMAC(PRK, K(0) || CTXinfo || 1)
206	 *
207	 * @param string $hash The hashing function to use (e.g., sha256)
208	 * @param string $ikm The input keying material
209	 * @param string $salt The salt to add to the ikm, to get the prk
210	 * @param string $info Optional context (change the output without affecting
211	 * 	the randomness properties of the output)
212	 * @param int $L Number of bytes to return
213	 * @return string Cryptographically secure pseudorandom binary string
214	 */
215	public static function HKDF( $hash, $ikm, $salt, $info, $L ) {
216		$prk = self::HKDFExtract( $hash, $salt, $ikm );
217		$okm = self::HKDFExpand( $hash, $prk, $info, $L );
218		return $okm;
219	}
220
221	/**
222	 * Extract the PRK, PRK = HMAC(XTS, SKM)
223	 * Note that the hmac is keyed with XTS (the salt),
224	 * and the SKM (source key material) is the "data".
225	 *
226	 * @param string $hash The hashing function to use (e.g., sha256)
227	 * @param string $salt The salt to add to the ikm, to get the prk
228	 * @param string $ikm The input keying material
229	 * @return string Binary string (pseudorandm key) used as input to HKDFExpand
230	 */
231	private static function HKDFExtract( $hash, $salt, $ikm ) {
232		return hash_hmac( $hash, $ikm, $salt, true );
233	}
234
235	/**
236	 * Expand the key with the given context
237	 *
238	 * @param string $hash Hashing Algorithm
239	 * @param string $prk A pseudorandom key of at least HashLen octets
240	 *    (usually, the output from the extract step)
241	 * @param string $info Optional context and application specific information
242	 *    (can be a zero-length string)
243	 * @param int $bytes Length of output keying material in bytes
244	 *    (<= 255*HashLen)
245	 * @param string &$lastK Set by this function to the last block of the expansion.
246	 *    In MediaWiki, this is used to seed future Extractions.
247	 * @return string Cryptographically secure random string $bytes long
248	 * @throws InvalidArgumentException
249	 */
250	private static function HKDFExpand( $hash, $prk, $info, $bytes, &$lastK = '' ) {
251		$hashLen = self::$hashLength[$hash];
252		$rounds = ceil( $bytes / $hashLen );
253		$output = '';
254
255		if ( $bytes > 255 * $hashLen ) {
256			throw new InvalidArgumentException( 'Too many bytes requested from HDKFExpand' );
257		}
258
259		// K(1) = HMAC(PRK, CTXinfo || 1);
260		// K(i) = HMAC(PRK, K(i-1) || CTXinfo || i); 1 < i <= t;
261		for ( $counter = 1; $counter <= $rounds; ++$counter ) {
262			$lastK = hash_hmac(
263				$hash,
264				$lastK . $info . chr( $counter ),
265				$prk,
266				true
267			);
268			$output .= $lastK;
269		}
270
271		return substr( $output, 0, $bytes );
272	}
273}
274