3 * Extract-and-Expand Key Derivation Function (HKDF). A cryptographicly
4 * secure key expansion function based on RFC 5869.
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.
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.
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.
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
29 * @author Chris Steipp
36 * @var BagOStuff The persistent cache
38 protected $cache = null;
41 * @var string Cache key we'll use for our salt
43 protected $cacheKey = null;
46 * @var string The hash algorithm being used
48 protected $algorithm = null;
51 * @var string binary string, the salt for the HKDF
52 * @see getSaltUsingCache
57 * @var string The pseudorandom key
62 * The secret key material. This must be kept secret to preserve
63 * the security properties of this RNG.
70 * @var string The last block (K(i)) of the most recent expanded key
75 * a "context information" string CTXinfo (which may be null)
76 * See http://eprint.iacr.org/2010/264.pdf Section 4.1
80 protected $context = [];
83 * Round count is computed based on the hash'es output length,
84 * which neither php nor openssl seem to provide easily.
88 public static $hashLength = [
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
109 public function __construct( $secretKeyMaterial, $algorithm, BagOStuff
$cache, $context ) {
110 if ( strlen( $secretKeyMaterial ) < 16 ) {
111 throw new InvalidArgumentException( "secret was too short." );
113 $this->skm
= $secretKeyMaterial;
114 $this->algorithm
= $algorithm;
115 $this->cache
= $cache;
116 $this->context
= is_array( $context ) ?
$context : [ $context ];
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 ) );
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.
129 function __destruct() {
130 if ( $this->lastK
) {
131 $this->cache
->set( $this->cacheKey
, $this->lastK
);
136 * MW specific salt, cached from last run
137 * @return string Binary string
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 );
151 // Get a binary string that is hashLen long
152 $this->salt
= hash( $this->algorithm
, $lastSalt, true );
158 * Produce $bytes of secure random data. As a side-effect,
159 * $this->lastK is set to the last hashLen block of key material.
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
165 public function generate( $bytes, $context = '' ) {
166 if ( $this->prk
=== '' ) {
167 $salt = $this->getSaltUsingCache();
168 $this->prk
= self
::HKDFExtract(
175 $CTXinfo = implode( ':', array_merge( $this->context
, [ $context ] ) );
177 return self
::HKDFExpand(
187 * RFC5869 defines HKDF in 2 steps, extraction and expansion.
188 * From http://eprint.iacr.org/2010/264.pdf:
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.
201 * XTS is the "extractor salt"
202 * SKM is the "secret keying material"
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)
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
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 );
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".
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
231 private static function HKDFExtract( $hash, $salt, $ikm ) {
232 return hash_hmac( $hash, $ikm, $salt, true );
236 * Expand the key with the given context
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
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
250 private static function HKDFExpand( $hash, $prk, $info, $bytes, &$lastK = '' ) {
251 $hashLen = self
::$hashLength[$hash];
252 $rounds = ceil( $bytes / $hashLen );
255 if ( $bytes > 255 * $hashLen ) {
256 throw new InvalidArgumentException( 'Too many bytes requested from HDKFExpand' );
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 ) {
264 $lastK . $info . chr( $counter ),
271 return substr( $output, 0, $bytes );