interface/modules/zend_modules/library/Zend/Crypt/Key/Derivation/Scrypt.php

   1 <?php
   2 /**
   3  * Zend Framework (http://framework.zend.com/)
   4  *
   5  * @link      http://github.com/zendframework/zf2 for the canonical source repository
   6  * @copyright Copyright (c) 2005-2013 Zend Technologies USA Inc. (http://www.zend.com)
   7  * @license   http://framework.zend.com/license/new-bsd New BSD License
   8  */
   9
  10 namespace Zend\Crypt\Key\Derivation;
  11
  12 use Zend\Crypt\Key\Derivation\Pbkdf2;
  13
  14 /**
  15  * Scrypt key derivation function
  16  *
  17  * @see      http://www.tarsnap.com/scrypt.html
  18  * @see      https://tools.ietf.org/html/draft-josefsson-scrypt-kdf-01
  19  */
  20 abstract class Scrypt
  21 {
  22     /**
  23      * Execute the scrypt algorithm
  24      *
  25      * @param  string $password
  26      * @param  string $salt
  27      * @param  int $n CPU cost
  28      * @param  int $r Memory cost
  29      * @param  int $p parallelization cost
  30      * @param  int $length size of the output key
  31      * @return string
  32      */
  33     public static function calc($password, $salt, $n, $r, $p, $length)
  34     {
  35         if ($n == 0 || ($n & ($n - 1)) != 0) {
  36             throw new Exception\InvalidArgumentException("N must be > 0 and a power of 2");
  37         }
  38         if ($n > PHP_INT_MAX / 128 / $r) {
  39             throw new Exception\InvalidArgumentException("Parameter n is too large");
  40         }
  41         if ($r > PHP_INT_MAX / 128 / $p) {
  42             throw new Exception\InvalidArgumentException("Parameter r is too large");
  43         }
  44
  45         if (extension_loaded('Scrypt')) {
  46             if ($length < 16) {
  47                 throw new Exception\InvalidArgumentException("Key length is too low, must be greater or equal to 16");
  48             }
  49             return self::hex2bin(scrypt($password, $salt, $n, $r, $p, $length));
  50         }
  51
  52         $b = Pbkdf2::calc('sha256', $password, $salt, 1, $p * 128 * $r);
  53
  54         $s = '';
  55         for ($i = 0; $i < $p; $i++) {
  56             $s .= self::scryptROMix(substr($b, $i * 128 * $r, 128 * $r), $n, $r);
  57         }
  58
  59         return Pbkdf2::calc('sha256', $password, $s, 1, $length);
  60     }
  61
  62    /**
  63     * scryptROMix
  64     *
  65     * @param  string $b
  66     * @param  int $n
  67     * @param  int $r
  68     * @return string
  69     * @see    https://tools.ietf.org/html/draft-josefsson-scrypt-kdf-01#section-4
  70     */
  71     protected static function scryptROMix($b, $n, $r)
  72     {
  73         $x = $b;
  74         $v = array();
  75         for ($i = 0; $i < $n; $i++) {
  76             $v[$i] = $x;
  77             $x = self::scryptBlockMix($x, $r);
  78         }
  79         for ($i = 0; $i < $n; $i++) {
  80             $j = self::integerify($x) % $n;
  81             $t = $x ^  $v[$j];
  82             $x = self::scryptBlockMix($t, $r);
  83         }
  84         return $x;
  85     }
  86
  87     /**
  88      * scryptBlockMix
  89      *
  90      * @param  string $b
  91      * @param  int $r
  92      * @return string
  93      * @see    https://tools.ietf.org/html/draft-josefsson-scrypt-kdf-01#section-3
  94      */
  95     protected static function scryptBlockMix($b, $r)
  96     {
  97         $x    = substr($b, -64);
  98         $even = '';
  99         $odd  = '';
 100         $len  = 2 * $r;
 101
 102         for ($i = 0; $i < $len; $i++) {
 103             if (PHP_INT_SIZE === 4) {
 104                 $x = self::salsa208Core32($x ^ substr($b, 64 * $i, 64));
 105             } else {
 106                 $x = self::salsa208Core64($x ^ substr($b, 64 * $i, 64));
 107             }
 108             if ($i % 2 == 0) {
 109                 $even .= $x;
 110             } else {
 111                 $odd .= $x;
 112             }
 113         }
 114         return $even . $odd;
 115     }
 116
 117     /**
 118      * Salsa 20/8 core (32 bit version)
 119      *
 120      * @param  string $b
 121      * @return string
 122      * @see    https://tools.ietf.org/html/draft-josefsson-scrypt-kdf-01#section-2
 123      * @see    http://cr.yp.to/salsa20.html
 124      */
 125     protected static function salsa208Core32($b)
 126     {
 127         $b32 = array();
 128         for ($i = 0; $i < 16; $i++) {
 129            list(, $b32[$i]) = unpack("V", substr($b, $i * 4, 4));
 130         }
 131
 132         $x = $b32;
 133         for ($i = 0; $i < 8; $i += 2) {
 134             $a      = ($x[ 0] + $x[12]);
 135             $x[ 4] ^= ($a << 7) | ($a >> 25) & 0x7f;
 136             $a      = ($x[ 4] + $x[ 0]);
 137             $x[ 8] ^= ($a << 9) | ($a >> 23) & 0x1ff;
 138             $a      = ($x[ 8] + $x[ 4]);
 139             $x[12] ^= ($a << 13) | ($a >> 19) & 0x1fff;
 140             $a      = ($x[12] + $x[ 8]);
 141             $x[ 0] ^= ($a << 18) | ($a >> 14) & 0x3ffff;
 142             $a      = ($x[ 5] + $x[ 1]);
 143             $x[ 9] ^= ($a << 7) | ($a >> 25) & 0x7f;
 144             $a      = ($x[ 9] + $x[ 5]);
 145             $x[13] ^= ($a << 9) | ($a >> 23) & 0x1ff;
 146             $a      = ($x[13] + $x[ 9]);
 147             $x[ 1] ^= ($a << 13) | ($a >> 19) & 0x1fff;
 148             $a      = ($x[ 1] + $x[13]);
 149             $x[ 5] ^= ($a << 18) | ($a >> 14) & 0x3ffff;
 150             $a      = ($x[10] + $x[ 6]);
 151             $x[14] ^= ($a << 7) | ($a >> 25) & 0x7f;
 152             $a      = ($x[14] + $x[10]);
 153             $x[ 2] ^= ($a << 9) | ($a >> 23) & 0x1ff;
 154             $a      = ($x[ 2] + $x[14]);
 155             $x[ 6] ^= ($a << 13) | ($a >> 19) & 0x1fff;
 156             $a      = ($x[ 6] + $x[ 2]);
 157             $x[10] ^= ($a << 18) | ($a >> 14) & 0x3ffff;
 158             $a      = ($x[15] + $x[11]);
 159             $x[ 3] ^= ($a << 7) | ($a >> 25) & 0x7f;
 160             $a      = ($x[ 3] + $x[15]);
 161             $x[ 7] ^= ($a << 9) | ($a >> 23) & 0x1ff;
 162             $a      = ($x[ 7] + $x[ 3]);
 163             $x[11] ^= ($a << 13) | ($a >> 19) & 0x1fff;
 164             $a      = ($x[11] + $x[ 7]);
 165             $x[15] ^= ($a << 18) | ($a >> 14) & 0x3ffff;
 166             $a      = ($x[ 0] + $x[ 3]);
 167             $x[ 1] ^= ($a << 7) | ($a >> 25) & 0x7f;
 168             $a      = ($x[ 1] + $x[ 0]);
 169             $x[ 2] ^= ($a << 9) | ($a >> 23) & 0x1ff;
 170             $a      = ($x[ 2] + $x[ 1]);
 171             $x[ 3] ^= ($a << 13) | ($a >> 19) & 0x1fff;
 172             $a      = ($x[ 3] + $x[ 2]);
 173             $x[ 0] ^= ($a << 18) | ($a >> 14) & 0x3ffff;
 174             $a      = ($x[ 5] + $x[ 4]);
 175             $x[ 6] ^= ($a << 7) | ($a >> 25) & 0x7f;
 176             $a      = ($x[ 6] + $x[ 5]);
 177             $x[ 7] ^= ($a << 9) | ($a >> 23) & 0x1ff;
 178             $a      = ($x[ 7] + $x[ 6]);
 179             $x[ 4] ^= ($a << 13) | ($a >> 19) & 0x1fff;
 180             $a      = ($x[ 4] + $x[ 7]);
 181             $x[ 5] ^= ($a << 18) | ($a >> 14) & 0x3ffff;
 182             $a      = ($x[10] + $x[ 9]);
 183             $x[11] ^= ($a << 7) | ($a >> 25) & 0x7f;
 184             $a      = ($x[11] + $x[10]);
 185             $x[ 8] ^= ($a << 9) | ($a >> 23) & 0x1ff;
 186             $a      = ($x[ 8] + $x[11]);
 187             $x[ 9] ^= ($a << 13) | ($a >> 19) & 0x1fff;
 188             $a      = ($x[ 9] + $x[ 8]);
 189             $x[10] ^= ($a << 18) | ($a >> 14) & 0x3ffff;
 190             $a      = ($x[15] + $x[14]);
 191             $x[12] ^= ($a << 7) | ($a >> 25) & 0x7f;
 192             $a      = ($x[12] + $x[15]);
 193             $x[13] ^= ($a << 9) | ($a >> 23) & 0x1ff;
 194             $a      = ($x[13] + $x[12]);
 195             $x[14] ^= ($a << 13) | ($a >> 19) & 0x1fff;
 196             $a      = ($x[14] + $x[13]);
 197             $x[15] ^= ($a << 18) | ($a >> 14) & 0x3ffff;
 198         }
 199         for ($i = 0; $i < 16; $i++) {
 200             $b32[$i] = $b32[$i] + $x[$i];
 201         }
 202         $result = '';
 203         for ($i = 0; $i < 16; $i++) {
 204             $result .= pack("V", $b32[$i]);
 205         }
 206
 207         return $result;
 208     }
 209
 210     /**
 211      * Salsa 20/8 core (64 bit version)
 212      *
 213      * @param  string $b
 214      * @return string
 215      * @see    https://tools.ietf.org/html/draft-josefsson-scrypt-kdf-01#section-2
 216      * @see    http://cr.yp.to/salsa20.html
 217      */
 218     protected static function salsa208Core64($b)
 219     {
 220         $b32 = array();
 221         for ($i = 0; $i < 16; $i++) {
 222             list(, $b32[$i]) = unpack("V", substr($b, $i * 4, 4));
 223         }
 224
 225         $x = $b32;
 226         for ($i = 0; $i < 8; $i += 2) {
 227             $a      = ($x[ 0] + $x[12]) & 0xffffffff;
 228             $x[ 4] ^= ($a << 7) | ($a >> 25);
 229             $a      = ($x[ 4] + $x[ 0]) & 0xffffffff;
 230             $x[ 8] ^= ($a << 9) | ($a >> 23);
 231             $a      = ($x[ 8] + $x[ 4]) & 0xffffffff;
 232             $x[12] ^= ($a << 13) | ($a >> 19);
 233             $a      = ($x[12] + $x[ 8]) & 0xffffffff;
 234             $x[ 0] ^= ($a << 18) | ($a >> 14);
 235             $a      = ($x[ 5] + $x[ 1]) & 0xffffffff;
 236             $x[ 9] ^= ($a << 7) | ($a >> 25);
 237             $a      = ($x[ 9] + $x[ 5]) & 0xffffffff;
 238             $x[13] ^= ($a << 9) | ($a >> 23);
 239             $a      = ($x[13] + $x[ 9]) & 0xffffffff;
 240             $x[ 1] ^= ($a << 13) | ($a >> 19);
 241             $a      = ($x[ 1] + $x[13]) & 0xffffffff;
 242             $x[ 5] ^= ($a << 18) | ($a >> 14);
 243             $a      = ($x[10] + $x[ 6]) & 0xffffffff;
 244             $x[14] ^= ($a << 7) | ($a >> 25);
 245             $a      = ($x[14] + $x[10]) & 0xffffffff;
 246             $x[ 2] ^= ($a << 9) | ($a >> 23);
 247             $a      = ($x[ 2] + $x[14]) & 0xffffffff;
 248             $x[ 6] ^= ($a << 13) | ($a >> 19);
 249             $a      = ($x[ 6] + $x[ 2]) & 0xffffffff;
 250             $x[10] ^= ($a << 18) | ($a >> 14);
 251             $a      = ($x[15] + $x[11]) & 0xffffffff;
 252             $x[ 3] ^= ($a << 7) | ($a >> 25);
 253             $a      = ($x[ 3] + $x[15]) & 0xffffffff;
 254             $x[ 7] ^= ($a << 9) | ($a >> 23);
 255             $a      = ($x[ 7] + $x[ 3]) & 0xffffffff;
 256             $x[11] ^= ($a << 13) | ($a >> 19);
 257             $a      = ($x[11] + $x[ 7]) & 0xffffffff;
 258             $x[15] ^= ($a << 18) | ($a >> 14);
 259             $a      = ($x[ 0] + $x[ 3]) & 0xffffffff;
 260             $x[ 1] ^= ($a << 7) | ($a >> 25);
 261             $a      = ($x[ 1] + $x[ 0]) & 0xffffffff;
 262             $x[ 2] ^= ($a << 9) | ($a >> 23);
 263             $a      = ($x[ 2] + $x[ 1]) & 0xffffffff;
 264             $x[ 3] ^= ($a << 13) | ($a >> 19);
 265             $a      = ($x[ 3] + $x[ 2]) & 0xffffffff;
 266             $x[ 0] ^= ($a << 18) | ($a >> 14);
 267             $a      = ($x[ 5] + $x[ 4]) & 0xffffffff;
 268             $x[ 6] ^= ($a << 7) | ($a >> 25);
 269             $a      = ($x[ 6] + $x[ 5]) & 0xffffffff;
 270             $x[ 7] ^= ($a << 9) | ($a >> 23);
 271             $a      = ($x[ 7] + $x[ 6]) & 0xffffffff;
 272             $x[ 4] ^= ($a << 13) | ($a >> 19);
 273             $a      = ($x[ 4] + $x[ 7]) & 0xffffffff;
 274             $x[ 5] ^= ($a << 18) | ($a >> 14);
 275             $a      = ($x[10] + $x[ 9]) & 0xffffffff;
 276             $x[11] ^= ($a << 7) | ($a >> 25);
 277             $a      = ($x[11] + $x[10]) & 0xffffffff;
 278             $x[ 8] ^= ($a << 9) | ($a >> 23);
 279             $a      = ($x[ 8] + $x[11]) & 0xffffffff;
 280             $x[ 9] ^= ($a << 13) | ($a >> 19);
 281             $a      = ($x[ 9] + $x[ 8]) & 0xffffffff;
 282             $x[10] ^= ($a << 18) | ($a >> 14);
 283             $a      = ($x[15] + $x[14]) & 0xffffffff;
 284             $x[12] ^= ($a << 7) | ($a >> 25);
 285             $a      = ($x[12] + $x[15]) & 0xffffffff;
 286             $x[13] ^= ($a << 9) | ($a >> 23);
 287             $a      = ($x[13] + $x[12]) & 0xffffffff;
 288             $x[14] ^= ($a << 13) | ($a >> 19);
 289             $a      = ($x[14] + $x[13]) & 0xffffffff;
 290             $x[15] ^= ($a << 18) | ($a >> 14);
 291         }
 292         for ($i = 0; $i < 16; $i++) {
 293             $b32[$i] = ($b32[$i] + $x[$i]) & 0xffffffff;
 294         }
 295         $result = '';
 296         for ($i = 0; $i < 16; $i++) {
 297             $result .= pack("V", $b32[$i]);
 298         }
 299
 300         return $result;
 301     }
 302
 303     /**
 304      * Integerify
 305      *
 306      * Integerify (B[0] ... B[2 * r - 1]) is defined as the result
 307      * of interpreting B[2 * r - 1] as a little-endian integer.
 308      * Each block B is a string of 64 bytes.
 309      *
 310      * @param  string $b
 311      * @return int
 312      * @see    https://tools.ietf.org/html/draft-josefsson-scrypt-kdf-01#section-4
 313      */
 314     protected static function integerify($b)
 315     {
 316         $v = 'v';
 317         if (PHP_INT_SIZE === 8) {
 318             $v = 'V';
 319         }
 320         list(,$n) = unpack($v, substr($b, -64));
 321         return $n;
 322     }
 323
 324     /**
 325      * Convert hex string in a binary string
 326      *
 327      * @param  string $hex
 328      * @return string
 329      */
 330     protected static function hex2bin($hex)
 331     {
 332         if (version_compare(PHP_VERSION, '5.4') >= 0) {
 333             return hex2bin($hex);
 334         }
 335         $len    = strlen($hex);
 336         $result = '';
 337         for ($i = 0; $i < $len; $i+=2) {
 338             $result .= chr(hexdec($hex[$i] . $hex[$i+1]));
 339         }
 340         return $result;
 341     }
 342 }