pssht  latest
SSH server library written in PHP
Base.php
1 <?php
2 
3 /*
4 * This file is part of pssht.
5 *
6 * (c) François Poirotte <clicky@erebot.net>
7 *
8 * For the full copyright and license information, please view the LICENSE
9 * file that was distributed with this source code.
10 */
11 
13 
17 abstract class Base
18 {
20  const PRIME_36 = '0x0000000FFFFFFFFB';
21 
23  const PRIME_64 = '0xFFFFFFFFFFFFFFC5';
24 
26  const PRIME_128 = '0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61';
27 
29  protected $cipher;
30 
32  protected $blocklen;
33 
35  protected $taglen;
36 
38  static protected $twop32;
39 
41  static protected $twop64;
42 
43  protected function __construct($cipher, $taglen)
44  {
45  if (!in_array($taglen, array(4, 8, 12, 16))) {
46  throw new \InvalidArgumentException('Invalid tag length');
47  }
48 
49  $this->cipher = $cipher;
50  $this->blocklen = mcrypt_get_block_size($cipher, 'ecb');
51  $this->taglen = $taglen;
52 
53  self::$twop32 = gmp_pow(2, 32);
54  self::$twop64 = gmp_pow(2, 64);
55  }
56 
57  protected function KDF($k, $index, $numbytes)
58  {
59  // Calculate number of block cipher iterations
60  $n = (int) ceil($numbytes / $this->blocklen);
61  $y = '';
62  $bhex = (($this->blocklen - 8) << 1);
63  $pad = "%0${bhex}X%016X";
64 
65  // Build Y using block cipher in a counter mode
66  $cipher = mcrypt_module_open($this->cipher, null, 'ecb', null);
67  $iv = mcrypt_create_iv(mcrypt_get_iv_size($this->cipher, 'ecb'), MCRYPT_RAND);
68  mcrypt_generic_init($cipher, $k, $iv);
69  for ($i = 1; $i <= $n; $i++) {
70  $t = pack('H*', sprintf($pad, $index, $i));
71  $t = mcrypt_generic($cipher, $t);
72  $y .= $t;
73  }
74  mcrypt_generic_deinit($cipher);
75  return substr($y, 0, $numbytes);
76  }
77 
78  protected function PDF($k, $nonce)
79  {
80  $nlen = strlen($nonce);
81  $nonce = gmp_init(bin2hex($nonce), 16);
82 
83  // Extract and zero low bit(s) of Nonce if needed
84  if ($this->taglen <= 8) {
85  $index = gmp_intval(gmp_mod($nonce, gmp_init($this->blocklen / $this->taglen)));
86  $nonce = gmp_xor($nonce, $index);
87  }
88 
89  $nonce = gmp_strval($nonce, 16);
90  $nonce = pack('H*', str_pad($nonce, $nlen << 1, '0', STR_PAD_LEFT));
91 
92  // Make Nonce BLOCKLEN bytes by appending zeroes if needed
93  $nonce = str_pad($nonce, $this->blocklen, "\x00");
94 
95  $kprime = $this->KDF($k, 0, strlen($k));
96  $t = mcrypt_encrypt($this->cipher, $kprime, $nonce, 'ecb');
97 
98  if ($this->taglen <= 8) {
99  return substr($t, $index * $this->taglen, $this->taglen);
100  } else {
101  return substr($t, 0, $this->taglen);
102  }
103  }
104 
105  public function UMAC($k, $m, $nonce)
106  {
107  $hashed = $this->UHASH($k, $m);
108  $pad = $this->PDF($k, $nonce);
109  $tag = gmp_xor(gmp_init(bin2hex($pad), 16), gmp_init(bin2hex($hashed), 16));
110  $tag = gmp_strval($tag, 16);
111  $tag = pack('H*', str_pad($tag, $this->taglen << 1, '0', STR_PAD_LEFT));
112  return $tag;
113  }
114 
115  protected function UHASH($k, $m)
116  {
117  $iters = $this->taglen >> 2;
118  $l1key = $this->KDF($k, 1, 1024 + ($iters - 1) << 4);
119  $l2key = $this->KDF($k, 2, $iters * 24);
120  $l3key1 = $this->KDF($k, 3, $iters * 64);
121  $l3key2 = $this->KDF($k, 4, $iters * 4);
122 
123  $y = '';
124  for ($i = 0; $i < $iters; $i++) {
125  $l1key_i = substr($l1key, $i << 4, 1024);
126  $l2key_i = substr($l2key, $i * 24, 24);
127  $l3key1_i = substr($l3key1, $i << 6, 64);
128  $l3key2_i = substr($l3key2, $i << 2, 4);
129 
130  $a = $this->l1Hash($l1key_i, $m);
131  if (strlen($m) <= 1024) {
132  $b = "\x00\x00\x00\x00\x00\x00\x00\x00" . $a;
133  } else {
134  $b = $this->l2Hash($l2key_i, $a);
135  }
136  $c = $this->l3Hash($l3key1_i, $l3key2_i, $b);
137  $y .= $c;
138  }
139  return $y;
140  }
141 
142  protected function l1Hash($k, $m)
143  {
144  // Break M into 1024 byte chunks (final chunk may be shorter)
145  $ms = str_split($m, 1024);
146 
147  // For each chunk, except the last: endian-adjust, NH hash
148  // and add bit-length. Use results to build Y.
149  $len = gmp_init("0x2000", 16);
150  $y = '';
151  $last = array_pop($ms);
152  $k_i = str_split(substr($k, 0, 1024), 4);
153  foreach ($ms as $mp) {
154  $v = unpack('V*', $mp);
155  array_unshift($v, 'N*');
156  $m_i = call_user_func_array('pack', $v);
157  $nh = gmp_strval($this->NH($k_i, $m_i, $len), 16);
158  $y .= pack('H*', str_pad($nh, 16, '0', STR_PAD_LEFT));
159  }
160 
161  // For the last chunk: pad to 32-byte boundary, endian-adjust,
162  // NH hash and add bit-length. Concatenate the result to Y.
163  $len = gmp_init(strlen($last) * 8);
164  $last = str_pad($last, max(32, ((strlen($last) + 31) >> 5) << 5), "\x00");
165  $v = unpack('V*', $last);
166  array_unshift($v, 'N*');
167  $m_t = call_user_func_array('pack', $v);
168  $k_i = str_split(substr($k, 0, strlen($m_t)), 4);
169  $nh = gmp_strval($this->NH($k_i, $m_t, $len), 16);
170  $y .= pack('H*', str_pad($nh, 16, '0', STR_PAD_LEFT));
171  return $y;
172  }
173 
174  protected function NH($k_i, $m, $len)
175  {
176  // Break M and K into 4-byte chunks
177  $m_i = str_split($m, 4);
178 
179  // Perform NH hash on the chunks, pairing words for multiplication
180  // which are 4 apart to accommodate vector-parallelism.
181  $y = gmp_init(0);
182  for ($i = 0, $t = count($m_i) >> 3; $i < $t; $i++) {
183  for ($j = 0; $j < 4; $j++) {
184  $y = gmp_add(
185  $y,
186  gmp_mul(
187  gmp_mod(
188  gmp_add(
189  gmp_init(bin2hex($m_i[8 * $i + $j]), 16),
190  gmp_init(bin2hex($k_i[8 * $i + $j]), 16)
191  ),
192  self::$twop32
193  ),
194  gmp_mod(
195  gmp_add(
196  gmp_init(bin2hex($m_i[8 * $i + $j + 4]), 16),
197  gmp_init(bin2hex($k_i[8 * $i + $j + 4]), 16)
198  ),
199  self::$twop32
200  )
201  )
202  );
203  }
204  }
205  $y = gmp_mod(gmp_add($y, $len), self::$twop64);
206  return $y;
207  }
208 
209  protected function l2Hash($k, $m)
210  {
211  // Extract keys and restrict to special key-sets
212  $mask64 = gmp_init('0x01ffffff01ffffff', 16);
213  $mask128 = gmp_init('0x01ffffff01ffffff01ffffff01ffffff', 16);
214  $k64 = gmp_and(gmp_init(bin2hex(substr($k, 0, 8)), 16), $mask64);
215  $k128 = gmp_and(gmp_init(bin2hex(substr($k, 8, 16)), 16), $mask128);
216 
217  // If M is no more than 2^17 bytes, hash under 64-bit prime,
218  // otherwise, hash first 2^17 bytes under 64-bit prime and
219  // remainder under 128-bit prime.
220  if (strlen($m) <= (1 << 17)) {
221  // View M as an array of 64-bit words, and use POLY modulo
222  // prime(64) (and with bound 2^64 - 2^32) to hash it.
223  $y = $this->POLY(
224  64,
225  gmp_sub(
226  gmp_init('0x10000000000000000', 16),
227  gmp_init('0x100000000', 16)
228  ),
229  $k64,
230  $m
231  );
232  } else {
233  $m_1 = substr($m, 0, 1 << 17);
234  $m_2 = substr($m, 1 << 17) . "\x80";
235  $m_2 = str_pad($m_2, max(16, ((strlen($m_2) + 15) >> 4) << 4), "\x00");
236 
237  $y = $this->POLY(
238  64,
239  gmp_sub(gmp_pow(2, 64), gmp_pow(2, 32)),
240  $k64,
241  $m_1
242  );
243  $y = $this->POLY(
244  128,
245  gmp_sub(gmp_pow(2, 128), gmp_pow(2, 96)),
246  $k128,
247  pack('H*', substr(str_repeat('00', 16) . gmp_strval($y, 16), -32)) . $m_2
248  );
249  }
250 
251  $res = substr(str_repeat('00', 16) . gmp_strval($y, 16), -32);
252  return pack('H*', $res);
253  }
254 
255  protected function POLY($wordbits, $maxwordrange, $k, $m)
256  {
257  $wordbytes = $wordbits >> 3;
258  $p = gmp_init(constant(__CLASS__ . '::PRIME_' . $wordbits), 16);
259  $offset = gmp_sub(gmp_pow(2, $wordbits), $p);
260  $marker = gmp_sub($p, 1);
261 
262  // Break M into chunks of length wordbytes bytes
263  $m_i = str_split($m, $wordbytes);
264 
265  // Each input word m is compared with maxwordrange. If not smaller
266  // then 'marker' and (m - offset), both in range, are hashed.
267  $y = gmp_init(1);
268  for ($i = 0, $n = count($m_i); $i < $n; $i++) {
269  $m = gmp_init(bin2hex($m_i[$i]), 16);
270  if (gmp_cmp($m, $maxwordrange) >= 0) {
271  $y = gmp_mod(gmp_add(gmp_mul($k, $y), $marker), $p);
272  $y = gmp_mod(gmp_add(gmp_mul($k, $y), gmp_sub($m, $offset)), $p);
273  } else {
274  $y = gmp_mod(gmp_add(gmp_mul($k, $y), $m), $p);
275  }
276  }
277 
278  return $y;
279  }
280 
281  protected function l3Hash($k1, $k2, $m)
282  {
283  $y = gmp_init(0);
284  $prime36 = gmp_init(self::PRIME_36, 16);
285  for ($i = 0; $i < 8; $i++) {
286  $m_i = gmp_init(bin2hex(substr($m, $i << 1, 2)), 16);
287  $k_i = gmp_mod(gmp_init(bin2hex(substr($k1, $i << 3, 8)), 16), $prime36);
288  $y = gmp_add($y, gmp_mul($m_i, $k_i));
289  }
290  $y = gmp_and(gmp_mod($y, $prime36), '0xFFFFFFFF');
291  $y = gmp_xor($y, gmp_init(bin2hex($k2), 16));
292  $y = pack('H*', str_pad(gmp_strval($y, 16), 8, '0', STR_PAD_LEFT));
293  return $y;
294  }
295 }
const PRIME_128
128-bits prime number, in hexadecimal notation.
Definition: Base.php:26
$cipher
Cipher algorithm used to encrypt data.
Definition: Base.php:29
$taglen
Length of tags generated by this instance.
Definition: Base.php:35
$blocklen
Block length for the cipher.
Definition: Base.php:32
const PRIME_64
64-bits prime number, in hexadecimal notation.
Definition: Base.php:23
const PRIME_36
36-bits prime number, in hexadecimal notation.
Definition: Base.php:20