[Summary view] [Print] [Text view]

   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       */
 107  	public function __construct( $secretKeyMaterial, $algorithm, $cache, $context ) {
 108          if ( strlen( $secretKeyMaterial ) < 16 ) {
 109              throw new MWException( "MWCryptHKDF secret was too short." );
 110          }
 111          $this->skm = $secretKeyMaterial;
 112          $this->algorithm = $algorithm;
 113          $this->cache = $cache;
 114          $this->salt = ''; // Initialize a blank salt, see getSaltUsingCache()
 115          $this->prk = '';
 116          $this->context = is_array( $context ) ? $context : array( $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 = wfMemcKey( '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  	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 MWCryptRand, 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 = MWCryptRand::generate( 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       * Return a singleton instance, based on the global configs.
 159       * @return HKDF
 160       */
 161  	protected static function singleton() {
 162          global $wgHKDFAlgorithm, $wgHKDFSecret, $wgSecretKey;
 163  
 164          $secret = $wgHKDFSecret ?: $wgSecretKey;
 165          if ( !$secret ) {
 166              throw new MWException( "Cannot use MWCryptHKDF without a secret." );
 167          }
 168  
 169          // In HKDF, the context can be known to the attacker, but this will
 170          // keep simultaneous runs from producing the same output.
 171          $context = array();
 172          $context[] = microtime();
 173          $context[] = getmypid();
 174          $context[] = gethostname();
 175  
 176          // Setup salt cache. Use APC, or fallback to the main cache if it isn't setup
 177          try {
 178              $cache = ObjectCache::newAccelerator( array() );
 179          } catch ( Exception $e ) {
 180              $cache = wfGetMainCache();
 181          }
 182  
 183          if ( is_null( self::$singleton ) ) {
 184              self::$singleton = new self( $secret, $wgHKDFAlgorithm, $cache, $context );
 185          }
 186  
 187          return self::$singleton;
 188      }
 189  
 190      /**
 191       * Produce $bytes of secure random data. As a side-effect,
 192       * $this->lastK is set to the last hashLen block of key material.
 193       * @param int $bytes Number of bytes of data
 194       * @param string $context Context to mix into CTXinfo
 195       * @return string Binary string of length $bytes
 196       */
 197  	protected function realGenerate( $bytes, $context = '' ) {
 198  
 199          if ( $this->prk === '' ) {
 200              $salt = $this->getSaltUsingCache();
 201              $this->prk = self::HKDFExtract(
 202                  $this->algorithm,
 203                  $salt,
 204                  $this->skm
 205              );
 206          }
 207  
 208          $CTXinfo = implode( ':', array_merge( $this->context, array( $context ) ) );
 209  
 210          return self::HKDFExpand(
 211              $this->algorithm,
 212              $this->prk,
 213              $CTXinfo,
 214              $bytes,
 215              $this->lastK
 216          );
 217      }
 218  
 219  
 220      /**
 221       * RFC5869 defines HKDF in 2 steps, extraction and expansion.
 222       * From http://eprint.iacr.org/2010/264.pdf:
 223       *
 224       * The scheme HKDF is specifed as:
 225       *     HKDF(XTS, SKM, CTXinfo, L) = K(1) || K(2) || ... || K(t)
 226       * where the values K(i) are defined as follows:
 227       *     PRK = HMAC(XTS, SKM)
 228       *     K(1) = HMAC(PRK, CTXinfo || 0);
 229       *     K(i+1) = HMAC(PRK, K(i) || CTXinfo || i), 1 <= i < t;
 230       * where t = [L/k] and the value K(t) is truncated to its first d = L mod k bits;
 231       * the counter i is non-wrapping and of a given fixed size, e.g., a single byte.
 232       * Note that the length of the HMAC output is the same as its key length and therefore
 233       * the scheme is well defined.
 234       *
 235       * XTS is the "extractor salt"
 236       * SKM is the "secret keying material"
 237       *
 238       * N.B. http://eprint.iacr.org/2010/264.pdf seems to differ from RFC 5869 in that the test
 239       * vectors from RFC 5869 only work if K(0) = '' and K(1) = HMAC(PRK, K(0) || CTXinfo || 1)
 240       *
 241       * @param string $hash The hashing function to use (e.g., sha256)
 242       * @param string $ikm The input keying material
 243       * @param string $salt The salt to add to the ikm, to get the prk
 244       * @param string $info Optional context (change the output without affecting
 245       *    the randomness properties of the output)
 246       * @param int $L Number of bytes to return
 247       * @return string Cryptographically secure pseudorandom binary string
 248       */
 249  	public static function HKDF( $hash, $ikm, $salt, $info, $L ) {
 250          $prk = self::HKDFExtract( $hash, $salt, $ikm );
 251          $okm = self::HKDFExpand( $hash, $prk, $info, $L );
 252          return $okm;
 253      }
 254  
 255      /**
 256       * Extract the PRK, PRK = HMAC(XTS, SKM)
 257       * Note that the hmac is keyed with XTS (the salt),
 258       * and the SKM (source key material) is the "data".
 259       *
 260       * @param string $hash The hashing function to use (e.g., sha256)
 261       * @param string $salt The salt to add to the ikm, to get the prk
 262       * @param string $ikm The input keying material
 263       * @return string Binary string (pseudorandm key) used as input to HKDFExpand
 264       */
 265  	private static function HKDFExtract( $hash, $salt, $ikm ) {
 266          return hash_hmac( $hash, $ikm, $salt, true );
 267      }
 268  
 269      /**
 270       * Expand the key with the given context
 271       *
 272       * @param string $hash Hashing Algorithm
 273       * @param string $prk A pseudorandom key of at least HashLen octets
 274       *     (usually, the output from the extract step)
 275       * @param string $info Optional context and application specific information
 276       *     (can be a zero-length string)
 277       * @param int $bytes Length of output keying material in bytes
 278       *     (<= 255*HashLen)
 279       * @param string &$lastK Set by this function to the last block of the expansion.
 280       *    In MediaWiki, this is used to seed future Extractions.
 281       * @return string Cryptographically secure random string $bytes long
 282       */
 283  	private static function HKDFExpand( $hash, $prk, $info, $bytes, &$lastK = '' ) {
 284          $hashLen = MWCryptHKDF::$hashLength[$hash];
 285          $rounds = ceil( $bytes / $hashLen );
 286          $output = '';
 287  
 288          if ( $bytes > 255 * $hashLen ) {
 289              throw new MWException( "Too many bytes requested from HDKFExpand" );
 290          }
 291  
 292          // K(1) = HMAC(PRK, CTXinfo || 1);
 293          // K(i) = HMAC(PRK, K(i-1) || CTXinfo || i); 1 < i <= t;
 294          for ( $counter = 1; $counter <= $rounds; ++$counter ) {
 295              $lastK = hash_hmac(
 296                  $hash,
 297                  $lastK . $info . chr( $counter ),
 298                  $prk,
 299                  true
 300              );
 301              $output .= $lastK;
 302          }
 303  
 304          return substr( $output, 0, $bytes );
 305      }
 306  
 307      /**
 308       * Generate cryptographically random data and return it in raw binary form.
 309       *
 310       * @param int $bytes The number of bytes of random data to generate
 311       * @param string $context String to mix into HMAC context
 312       * @return string Binary string of length $bytes
 313       */
 314  	public static function generate( $bytes, $context ) {
 315          return self::singleton()->realGenerate( $bytes, $context );
 316      }
 317  
 318      /**
 319       * Generate cryptographically random data and return it in hexadecimal string format.
 320       * See MWCryptRand::realGenerateHex for details of the char-to-byte conversion logic.
 321       *
 322       * @param int $chars The number of hex chars of random data to generate
 323       * @param string $context String to mix into HMAC context
 324       * @return string Random hex characters, $chars long
 325       */
 326  	public static function generateHex( $chars, $context = '' ) {
 327          $bytes = ceil( $chars / 2 );
 328          $hex = bin2hex( self::singleton()->realGenerate( $bytes, $context ) );
 329          return substr( $hex, 0, $chars );
 330      }
 331  
 332  }