includes/utils/MWCryptHKDF.php

   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
  33 class MWCryptHKDF {
  34
  35         /**
  36          * Singleton instance for public use
  37          */
  38         protected static $singleton = null;
  39
  40         /**
  41          * The persistant cache
  42          */
  43         protected $cache = null;
  44
  45         /**
  46          * Cache key we'll use for our salt
  47          */
  48         protected $cacheKey = null;
  49
  50         /**
  51          * The hash algorithm being used
  52          */
  53         protected $algorithm = null;
  54
  55         /**
  56          * binary string, the salt for the HKDF
  57          */
  58         protected $salt;
  59
  60         /**
  61          * The pseudorandom key
  62          */
  63         private $prk;
  64
  65         /**
  66          * The secret key material. This must be kept secret to preserve
  67          * the security properties of this RNG.
  68          */
  69         private $skm;
  70
  71         /**
  72          * The last block (K(i)) of the most recent expanded key
  73          */
  74         protected $lastK;
  75
  76         /**
  77          * a "context information" string CTXinfo (which may be null)
  78          * See http://eprint.iacr.org/2010/264.pdf Section 4.1
  79          */
  80         protected $context = array();
  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         public static $hashLength = array(
  87                 'md5' => 16,
  88                 'sha1' => 20,
  89                 'sha224' => 28,
  90                 'sha256' => 32,
  91                 'sha384' => 48,
  92                 'sha512' => 64,
  93                 'ripemd128' => 16,
  94                 'ripemd160' => 20,
  95                 'ripemd256' => 32,
  96                 'ripemd320' => 40,
  97                 'whirlpool' => 64,
  98         );
  99
 100
 101         /**
 102          * @param string $secretKeyMaterial
 103          * @param string $algorithm Name of hashing algorithm
 104          * @param BagOStuff $cache
 105          * @param string|array $context Context to mix into HKDF context
 106          * @throws MWException
 107          */
 108         public function __construct( $secretKeyMaterial, $algorithm, $cache, $context ) {
 109                 if ( strlen( $secretKeyMaterial ) < 16 ) {
 110                         throw new MWException( "MWCryptHKDF secret was too short." );
 111                 }
 112                 $this->skm = $secretKeyMaterial;
 113                 $this->algorithm = $algorithm;
 114                 $this->cache = $cache;
 115                 $this->salt = ''; // Initialize a blank salt, see getSaltUsingCache()
 116                 $this->prk = '';
 117                 $this->context = is_array( $context ) ? $context : array( $context );
 118
 119                 // To prevent every call from hitting the same memcache server, pick
 120                 // from a set of keys to use. mt_rand is only use to pick a random
 121                 // server, and does not affect the security of the process.
 122                 $this->cacheKey = wfMemcKey( 'HKDF', mt_rand( 0, 16 ) );
 123         }
 124
 125         /**
 126          * Save the last block generated, so the next user will compute a different PRK
 127          * from the same SKM. This should keep things unpredictable even if an attacker
 128          * is able to influence CTXinfo.
 129          */
 130         function __destruct() {
 131                 if ( $this->lastK ) {
 132                         $this->cache->set( $this->cacheKey, $this->lastK );
 133                 }
 134         }
 135
 136         /**
 137          * MW specific salt, cached from last run
 138          * @return string Binary string
 139          */
 140         protected function getSaltUsingCache() {
 141                 if ( $this->salt == '' ) {
 142                         $lastSalt = $this->cache->get( $this->cacheKey );
 143                         if ( $lastSalt === false ) {
 144                                 // If we don't have a previous value to use as our salt, we use
 145                                 // 16 bytes from MWCryptRand, which will use a small amount of
 146                                 // entropy from our pool. Note, "XTR may be deterministic or keyed
 147                                 // via an optional “salt value”  (i.e., a non-secret random
 148                                 // value)..." - http://eprint.iacr.org/2010/264.pdf. However, we
 149                                 // use a strongly random value since we can.
 150                                 $lastSalt = MWCryptRand::generate( 16 );
 151                         }
 152                         // Get a binary string that is hashLen long
 153                         $this->salt = hash( $this->algorithm, $lastSalt, true );
 154                 }
 155                 return $this->salt;
 156         }
 157
 158         /**
 159          * Return a singleton instance, based on the global configs.
 160          * @return HKDF
 161          * @throws MWException
 162          */
 163         protected static function singleton() {
 164                 global $wgHKDFAlgorithm, $wgHKDFSecret, $wgSecretKey;
 165
 166                 $secret = $wgHKDFSecret ?: $wgSecretKey;
 167                 if ( !$secret ) {
 168                         throw new MWException( "Cannot use MWCryptHKDF without a secret." );
 169                 }
 170
 171                 // In HKDF, the context can be known to the attacker, but this will
 172                 // keep simultaneous runs from producing the same output.
 173                 $context = array();
 174                 $context[] = microtime();
 175                 $context[] = getmypid();
 176                 $context[] = gethostname();
 177
 178                 // Setup salt cache. Use APC, or fallback to the main cache if it isn't setup
 179                 try {
 180                         $cache = ObjectCache::newAccelerator( array() );
 181                 } catch ( Exception $e ) {
 182                         $cache = wfGetMainCache();
 183                 }
 184
 185                 if ( is_null( self::$singleton ) ) {
 186                         self::$singleton = new self( $secret, $wgHKDFAlgorithm, $cache, $context );
 187                 }
 188
 189                 return self::$singleton;
 190         }
 191
 192         /**
 193          * Produce $bytes of secure random data. As a side-effect,
 194          * $this->lastK is set to the last hashLen block of key material.
 195          * @param int $bytes Number of bytes of data
 196          * @param string $context Context to mix into CTXinfo
 197          * @return string Binary string of length $bytes
 198          */
 199         protected function realGenerate( $bytes, $context = '' ) {
 200
 201                 if ( $this->prk === '' ) {
 202                         $salt = $this->getSaltUsingCache();
 203                         $this->prk = self::HKDFExtract(
 204                                 $this->algorithm,
 205                                 $salt,
 206                                 $this->skm
 207                         );
 208                 }
 209
 210                 $CTXinfo = implode( ':', array_merge( $this->context, array( $context ) ) );
 211
 212                 return self::HKDFExpand(
 213                         $this->algorithm,
 214                         $this->prk,
 215                         $CTXinfo,
 216                         $bytes,
 217                         $this->lastK
 218                 );
 219         }
 220
 221
 222         /**
 223          * RFC5869 defines HKDF in 2 steps, extraction and expansion.
 224          * From http://eprint.iacr.org/2010/264.pdf:
 225          *
 226          * The scheme HKDF is specifed as:
 227          *      HKDF(XTS, SKM, CTXinfo, L) = K(1) || K(2) || ... || K(t)
 228          * where the values K(i) are defined as follows:
 229          *      PRK = HMAC(XTS, SKM)
 230          *      K(1) = HMAC(PRK, CTXinfo || 0);
 231          *      K(i+1) = HMAC(PRK, K(i) || CTXinfo || i), 1 <= i < t;
 232          * where t = [L/k] and the value K(t) is truncated to its first d = L mod k bits;
 233          * the counter i is non-wrapping and of a given fixed size, e.g., a single byte.
 234          * Note that the length of the HMAC output is the same as its key length and therefore
 235          * the scheme is well defined.
 236          *
 237          * XTS is the "extractor salt"
 238          * SKM is the "secret keying material"
 239          *
 240          * N.B. http://eprint.iacr.org/2010/264.pdf seems to differ from RFC 5869 in that the test
 241          * vectors from RFC 5869 only work if K(0) = '' and K(1) = HMAC(PRK, K(0) || CTXinfo || 1)
 242          *
 243          * @param string $hash The hashing function to use (e.g., sha256)
 244          * @param string $ikm The input keying material
 245          * @param string $salt The salt to add to the ikm, to get the prk
 246          * @param string $info Optional context (change the output without affecting
 247          *      the randomness properties of the output)
 248          * @param int $L Number of bytes to return
 249          * @return string Cryptographically secure pseudorandom binary string
 250          */
 251         public static function HKDF( $hash, $ikm, $salt, $info, $L ) {
 252                 $prk = self::HKDFExtract( $hash, $salt, $ikm );
 253                 $okm = self::HKDFExpand( $hash, $prk, $info, $L );
 254                 return $okm;
 255         }
 256
 257         /**
 258          * Extract the PRK, PRK = HMAC(XTS, SKM)
 259          * Note that the hmac is keyed with XTS (the salt),
 260          * and the SKM (source key material) is the "data".
 261          *
 262          * @param string $hash The hashing function to use (e.g., sha256)
 263          * @param string $salt The salt to add to the ikm, to get the prk
 264          * @param string $ikm The input keying material
 265          * @return string Binary string (pseudorandm key) used as input to HKDFExpand
 266          */
 267         private static function HKDFExtract( $hash, $salt, $ikm ) {
 268                 return hash_hmac( $hash, $ikm, $salt, true );
 269         }
 270
 271         /**
 272          * Expand the key with the given context
 273          *
 274          * @param string $hash Hashing Algorithm
 275          * @param string $prk A pseudorandom key of at least HashLen octets
 276          *    (usually, the output from the extract step)
 277          * @param string $info Optional context and application specific information
 278          *    (can be a zero-length string)
 279          * @param int $bytes Length of output keying material in bytes
 280          *    (<= 255*HashLen)
 281          * @param string &$lastK Set by this function to the last block of the expansion.
 282          *    In MediaWiki, this is used to seed future Extractions.
 283          * @return string Cryptographically secure random string $bytes long
 284          * @throws MWException
 285          */
 286         private static function HKDFExpand( $hash, $prk, $info, $bytes, &$lastK = '' ) {
 287                 $hashLen = MWCryptHKDF::$hashLength[$hash];
 288                 $rounds = ceil( $bytes / $hashLen );
 289                 $output = '';
 290
 291                 if ( $bytes > 255 * $hashLen ) {
 292                         throw new MWException( "Too many bytes requested from HDKFExpand" );
 293                 }
 294
 295                 // K(1) = HMAC(PRK, CTXinfo || 1);
 296                 // K(i) = HMAC(PRK, K(i-1) || CTXinfo || i); 1 < i <= t;
 297                 for ( $counter = 1; $counter <= $rounds; ++$counter ) {
 298                         $lastK = hash_hmac(
 299                                 $hash,
 300                                 $lastK . $info . chr( $counter ),
 301                                 $prk,
 302                                 true
 303                         );
 304                         $output .= $lastK;
 305                 }
 306
 307                 return substr( $output, 0, $bytes );
 308         }
 309
 310         /**
 311          * Generate cryptographically random data and return it in raw binary form.
 312          *
 313          * @param int $bytes The number of bytes of random data to generate
 314          * @param string $context String to mix into HMAC context
 315          * @return string Binary string of length $bytes
 316          */
 317         public static function generate( $bytes, $context ) {
 318                 return self::singleton()->realGenerate( $bytes, $context );
 319         }
 320
 321         /**
 322          * Generate cryptographically random data and return it in hexadecimal string format.
 323          * See MWCryptRand::realGenerateHex for details of the char-to-byte conversion logic.
 324          *
 325          * @param int $chars The number of hex chars of random data to generate
 326          * @param string $context String to mix into HMAC context
 327          * @return string Random hex characters, $chars long
 328          */
 329         public static function generateHex( $chars, $context = '' ) {
 330                 $bytes = ceil( $chars / 2 );
 331                 $hex = bin2hex( self::singleton()->realGenerate( $bytes, $context ) );
 332                 return substr( $hex, 0, $chars );
 333         }
 334
 335 }