1<?php
2
3/*
4	The MIT License (MIT)
5
6	Copyright (c) 2015 Bruno Bierbaumer
7
8	Permission is hereby granted, free of charge, to any person obtaining a copy
9	of this software and associated documentation files (the "Software"), to deal
10	in the Software without restriction, including without limitation the rights
11	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12	copies of the Software, and to permit persons to whom the Software is
13	furnished to do so, subject to the following conditions:
14
15	The above copyright notice and this permission notice shall be included in all
16	copies or substantial portions of the Software.
17
18	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24	SOFTWARE.
25*/
26
27final class Sha3
28{
29    const KECCAK_ROUNDS = 24;
30    private static $keccakf_rotc = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2, 14, 27, 41, 56, 8, 25, 43, 62, 18, 39, 61, 20, 44];
31    private static $keccakf_piln = [10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24, 4, 15, 23, 19, 13, 12,2, 20, 14, 22, 9, 6, 1];
32
33    private static function keccakf64(&$st, $rounds)
34    {
35        $keccakf_rndc = [
36            [0x00000000, 0x00000001], [0x00000000, 0x00008082], [0x80000000, 0x0000808a], [0x80000000, 0x80008000],
37            [0x00000000, 0x0000808b], [0x00000000, 0x80000001], [0x80000000, 0x80008081], [0x80000000, 0x00008009],
38            [0x00000000, 0x0000008a], [0x00000000, 0x00000088], [0x00000000, 0x80008009], [0x00000000, 0x8000000a],
39            [0x00000000, 0x8000808b], [0x80000000, 0x0000008b], [0x80000000, 0x00008089], [0x80000000, 0x00008003],
40            [0x80000000, 0x00008002], [0x80000000, 0x00000080], [0x00000000, 0x0000800a], [0x80000000, 0x8000000a],
41            [0x80000000, 0x80008081], [0x80000000, 0x00008080], [0x00000000, 0x80000001], [0x80000000, 0x80008008]
42        ];
43
44        $bc = [];
45        for ($round = 0; $round < $rounds; $round++) {
46
47            // Theta
48            for ($i = 0; $i < 5; $i++) {
49                $bc[$i] = [
50                    $st[$i][0] ^ $st[$i + 5][0] ^ $st[$i + 10][0] ^ $st[$i + 15][0] ^ $st[$i + 20][0],
51                    $st[$i][1] ^ $st[$i + 5][1] ^ $st[$i + 10][1] ^ $st[$i + 15][1] ^ $st[$i + 20][1]
52                ];
53            }
54
55            for ($i = 0; $i < 5; $i++) {
56                $t = [
57                    $bc[($i + 4) % 5][0] ^ (($bc[($i + 1) % 5][0] << 1) | ($bc[($i + 1) % 5][1] >> 31)) & (0xFFFFFFFF),
58                    $bc[($i + 4) % 5][1] ^ (($bc[($i + 1) % 5][1] << 1) | ($bc[($i + 1) % 5][0] >> 31)) & (0xFFFFFFFF)
59                ];
60
61                for ($j = 0; $j < 25; $j += 5) {
62                    $st[$j + $i] = [
63                        $st[$j + $i][0] ^ $t[0],
64                        $st[$j + $i][1] ^ $t[1]
65                    ];
66                }
67            }
68
69            // Rho Pi
70            $t = $st[1];
71            for ($i = 0; $i < 24; $i++) {
72                $j = self::$keccakf_piln[$i];
73
74                $bc[0] = $st[$j];
75
76                $n = self::$keccakf_rotc[$i];
77                $hi = $t[0];
78                $lo = $t[1];
79                if ($n >= 32) {
80                    $n -= 32;
81                    $hi = $t[1];
82                    $lo = $t[0];
83                }
84
85                $st[$j] =[
86                    (($hi << $n) | ($lo >> (32 - $n))) & (0xFFFFFFFF),
87                    (($lo << $n) | ($hi >> (32 - $n))) & (0xFFFFFFFF)
88                ];
89
90                $t = $bc[0];
91            }
92
93            //  Chi
94            for ($j = 0; $j < 25; $j += 5) {
95                for ($i = 0; $i < 5; $i++) {
96                    $bc[$i] = $st[$j + $i];
97                }
98                for ($i = 0; $i < 5; $i++) {
99                    $st[$j + $i] = [
100                        $st[$j + $i][0] ^ ~$bc[($i + 1) % 5][0] & $bc[($i + 2) % 5][0],
101                        $st[$j + $i][1] ^ ~$bc[($i + 1) % 5][1] & $bc[($i + 2) % 5][1]
102                    ];
103                }
104            }
105
106            // Iota
107            $st[0] = [
108                $st[0][0] ^ $keccakf_rndc[$round][0],
109                $st[0][1] ^ $keccakf_rndc[$round][1]
110            ];
111        }
112    }
113
114    private static function keccak64($in_raw, $capacity, $outputlength, $suffix, $raw_output)
115    {
116        $capacity /= 8;
117
118        $inlen = self::ourStrlen($in_raw);
119
120        $rsiz = 200 - 2 * $capacity;
121        $rsizw = $rsiz / 8;
122
123        $st = [];
124        for ($i = 0; $i < 25; $i++) {
125            $st[] = [0, 0];
126        }
127
128        for ($in_t = 0; $inlen >= $rsiz; $inlen -= $rsiz, $in_t += $rsiz) {
129            for ($i = 0; $i < $rsizw; $i++) {
130                $t = unpack('V*', self::ourSubstr($in_raw, $i * 8 + $in_t, 8));
131
132                $st[$i] = [
133                    $st[$i][0] ^ $t[2],
134                    $st[$i][1] ^ $t[1]
135                ];
136            }
137
138            self::keccakf64($st, self::KECCAK_ROUNDS);
139        }
140
141        $temp = self::ourSubstr($in_raw, $in_t, $inlen);
142        $temp = str_pad($temp, $rsiz, "\x0", STR_PAD_RIGHT);
143
144        $temp[$inlen] = chr($suffix);
145        $temp[$rsiz - 1] = chr(ord($temp[$rsiz - 1]) | 0x80);
146
147        for ($i = 0; $i < $rsizw; $i++) {
148            $t = unpack('V*', self::ourSubstr($temp, $i * 8, 8));
149
150            $st[$i] = [
151                $st[$i][0] ^ $t[2],
152                $st[$i][1] ^ $t[1]
153            ];
154        }
155
156        self::keccakf64($st, self::KECCAK_ROUNDS);
157
158        $out = '';
159        for ($i = 0; $i < 25; $i++) {
160            $out .= $t = pack('V*', $st[$i][1], $st[$i][0]);
161        }
162        $r = self::ourSubstr($out, 0, $outputlength / 8);
163
164        return $raw_output ? $r : bin2hex($r);
165    }
166
167    private static function keccakf32(&$st, $rounds)
168    {
169        $keccakf_rndc = [
170            [0x0000, 0x0000, 0x0000, 0x0001], [0x0000, 0x0000, 0x0000, 0x8082], [0x8000, 0x0000, 0x0000, 0x0808a], [0x8000, 0x0000, 0x8000, 0x8000],
171            [0x0000, 0x0000, 0x0000, 0x808b], [0x0000, 0x0000, 0x8000, 0x0001], [0x8000, 0x0000, 0x8000, 0x08081], [0x8000, 0x0000, 0x0000, 0x8009],
172            [0x0000, 0x0000, 0x0000, 0x008a], [0x0000, 0x0000, 0x0000, 0x0088], [0x0000, 0x0000, 0x8000, 0x08009], [0x0000, 0x0000, 0x8000, 0x000a],
173            [0x0000, 0x0000, 0x8000, 0x808b], [0x8000, 0x0000, 0x0000, 0x008b], [0x8000, 0x0000, 0x0000, 0x08089], [0x8000, 0x0000, 0x0000, 0x8003],
174            [0x8000, 0x0000, 0x0000, 0x8002], [0x8000, 0x0000, 0x0000, 0x0080], [0x0000, 0x0000, 0x0000, 0x0800a], [0x8000, 0x0000, 0x8000, 0x000a],
175            [0x8000, 0x0000, 0x8000, 0x8081], [0x8000, 0x0000, 0x0000, 0x8080], [0x0000, 0x0000, 0x8000, 0x00001], [0x8000, 0x0000, 0x8000, 0x8008]
176        ];
177
178        $bc = [];
179        for ($round = 0; $round < $rounds; $round++) {
180
181            // Theta
182            for ($i = 0; $i < 5; $i++) {
183                $bc[$i] = [
184                    $st[$i][0] ^ $st[$i + 5][0] ^ $st[$i + 10][0] ^ $st[$i + 15][0] ^ $st[$i + 20][0],
185                    $st[$i][1] ^ $st[$i + 5][1] ^ $st[$i + 10][1] ^ $st[$i + 15][1] ^ $st[$i + 20][1],
186                    $st[$i][2] ^ $st[$i + 5][2] ^ $st[$i + 10][2] ^ $st[$i + 15][2] ^ $st[$i + 20][2],
187                    $st[$i][3] ^ $st[$i + 5][3] ^ $st[$i + 10][3] ^ $st[$i + 15][3] ^ $st[$i + 20][3]
188                ];
189            }
190
191            for ($i = 0; $i < 5; $i++) {
192                $t = [
193                    $bc[($i + 4) % 5][0] ^ ((($bc[($i + 1) % 5][0] << 1) | ($bc[($i + 1) % 5][1] >> 15)) & (0xFFFF)),
194                    $bc[($i + 4) % 5][1] ^ ((($bc[($i + 1) % 5][1] << 1) | ($bc[($i + 1) % 5][2] >> 15)) & (0xFFFF)),
195                    $bc[($i + 4) % 5][2] ^ ((($bc[($i + 1) % 5][2] << 1) | ($bc[($i + 1) % 5][3] >> 15)) & (0xFFFF)),
196                    $bc[($i + 4) % 5][3] ^ ((($bc[($i + 1) % 5][3] << 1) | ($bc[($i + 1) % 5][0] >> 15)) & (0xFFFF))
197                ];
198
199                for ($j = 0; $j < 25; $j += 5) {
200                    $st[$j + $i] = [
201                        $st[$j + $i][0] ^ $t[0],
202                        $st[$j + $i][1] ^ $t[1],
203                        $st[$j + $i][2] ^ $t[2],
204                        $st[$j + $i][3] ^ $t[3]
205                    ];
206                }
207            }
208
209            // Rho Pi
210            $t = $st[1];
211            for ($i = 0; $i < 24; $i++) {
212                $j = self::$keccakf_piln[$i];
213                $bc[0] = $st[$j];
214
215
216                $n = self::$keccakf_rotc[$i] >> 4;
217                $m = self::$keccakf_rotc[$i] % 16;
218
219                $st[$j] =  [
220                    ((($t[(0+$n) %4] << $m) | ($t[(1+$n) %4] >> (16-$m))) & (0xFFFF)),
221                    ((($t[(1+$n) %4] << $m) | ($t[(2+$n) %4] >> (16-$m))) & (0xFFFF)),
222                    ((($t[(2+$n) %4] << $m) | ($t[(3+$n) %4] >> (16-$m))) & (0xFFFF)),
223                    ((($t[(3+$n) %4] << $m) | ($t[(0+$n) %4] >> (16-$m))) & (0xFFFF))
224                ];
225
226                $t = $bc[0];
227            }
228
229            //  Chi
230            for ($j = 0; $j < 25; $j += 5) {
231                for ($i = 0; $i < 5; $i++) {
232                    $bc[$i] = $st[$j + $i];
233                }
234                for ($i = 0; $i < 5; $i++) {
235                    $st[$j + $i] = [
236                        $st[$j + $i][0] ^ ~$bc[($i + 1) % 5][0] & $bc[($i + 2) % 5][0],
237                        $st[$j + $i][1] ^ ~$bc[($i + 1) % 5][1] & $bc[($i + 2) % 5][1],
238                        $st[$j + $i][2] ^ ~$bc[($i + 1) % 5][2] & $bc[($i + 2) % 5][2],
239                        $st[$j + $i][3] ^ ~$bc[($i + 1) % 5][3] & $bc[($i + 2) % 5][3]
240                    ];
241                }
242            }
243
244            // Iota
245            $st[0] = [
246                $st[0][0] ^ $keccakf_rndc[$round][0],
247                $st[0][1] ^ $keccakf_rndc[$round][1],
248                $st[0][2] ^ $keccakf_rndc[$round][2],
249                $st[0][3] ^ $keccakf_rndc[$round][3]
250            ];
251        }
252    }
253
254    private static function keccak32($in_raw, $capacity, $outputlength, $suffix, $raw_output)
255    {
256        $capacity /= 8;
257
258        $inlen = self::ourStrlen($in_raw);
259
260        $rsiz = 200 - 2 * $capacity;
261        $rsizw = $rsiz / 8;
262
263        $st = [];
264        for ($i = 0; $i < 25; $i++) {
265            $st[] = [0, 0, 0, 0];
266        }
267
268        for ($in_t = 0; $inlen >= $rsiz; $inlen -= $rsiz, $in_t += $rsiz) {
269            for ($i = 0; $i < $rsizw; $i++) {
270                $t = unpack('v*', self::ourSubstr($in_raw, $i * 8 + $in_t, 8));
271
272                $st[$i] = [
273                    $st[$i][0] ^ $t[4],
274                    $st[$i][1] ^ $t[3],
275                    $st[$i][2] ^ $t[2],
276                    $st[$i][3] ^ $t[1]
277                ];
278            }
279
280            self::keccakf32($st, self::KECCAK_ROUNDS);
281        }
282
283        $temp = self::ourSubstr($in_raw, $in_t, $inlen);
284        $temp = str_pad($temp, $rsiz, "\x0", STR_PAD_RIGHT);
285
286        $temp[$inlen] = chr($suffix);
287        $temp[$rsiz - 1] = chr($temp[$rsiz - 1] | 0x80);
288
289        for ($i = 0; $i < $rsizw; $i++) {
290            $t = unpack('v*', self::ourSubstr($temp, $i * 8, 8));
291
292            $st[$i] = [
293                $st[$i][0] ^ $t[4],
294                $st[$i][1] ^ $t[3],
295                $st[$i][2] ^ $t[2],
296                $st[$i][3] ^ $t[1]
297            ];
298        }
299
300        self::keccakf32($st, self::KECCAK_ROUNDS);
301
302        $out = '';
303        for ($i = 0; $i < 25; $i++) {
304            $out .= $t = pack('v*', $st[$i][3],$st[$i][2], $st[$i][1], $st[$i][0]);
305        }
306        $r = self::ourSubstr($out, 0, $outputlength / 8);
307
308        return $raw_output ? $r: bin2hex($r);
309    }
310
311    // 0 = not run, 1 = 64 bit passed, 2 = 32 bit passed, 3 = failed
312    private static $test_state = 0;
313    private static function selfTest()
314    {
315        if(self::$test_state === 1 || self::$test_state === 2){
316            return;
317        }
318
319        if(self::$test_state === 3){
320            throw new \Exception('Sha3 previous self test failed!');
321        }
322
323        $in = '';
324        $md = '6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7';
325        if(self::keccak64($in, 224, 224, 0x06, false) === $md){
326            self::$test_state = 1;
327            return;
328        }
329
330        if(self::keccak32($in, 224, 224, 0x06, false) === $md){
331            self::$test_state = 2;
332            return;
333        }
334
335        self::$test_state = 3;
336        throw new \Exception('Sha3 self test failed!');
337    }
338
339    private static function keccak($in_raw, $capacity, $outputlength, $suffix, $raw_output)
340    {
341        self::selfTest();
342
343        if(self::$test_state === 1) {
344            return self::keccak64($in_raw, $capacity, $outputlength, $suffix, $raw_output);
345        }
346
347        return self::keccak32($in_raw, $capacity, $outputlength, $suffix, $raw_output);
348    }
349
350    public static function hash($in, $mdlen, $raw_output = false)
351    {
352        if( ! in_array($mdlen, [224, 256, 384, 512], true)) {
353            throw new \Exception('Unsupported Sha3 Hash output size.');
354        }
355
356        return self::keccak($in, $mdlen, $mdlen, 0x06, $raw_output);
357    }
358
359    public static function shake($in, $security_level, $outlen, $raw_output = false)
360    {
361        if( ! in_array($security_level, [128, 256], true)) {
362            throw new \Exception('Unsupported Sha3 Shake security level.');
363        }
364
365        return self::keccak($in, $security_level, $outlen, 0x1f, $raw_output);
366    }
367
368    /**
369     *  Multi-byte-safe string functions borrowed from https://github.com/sarciszewski/php-future
370     */
371
372    /**
373     * Multi-byte-safe string length calculation
374     *
375     * @param string $str
376     * @return int
377     */
378    private static function ourStrlen($str)
379    {
380        // Premature optimization: cache the function_exists() result
381        static $exists = null;
382        if ($exists === null) {
383            $exists = \function_exists('\\mb_strlen');
384        }
385        // If it exists, we need to make sure we're using 8bit mode
386        if ($exists) {
387            $length =  \mb_strlen($str, '8bit');
388            if ($length === false) {
389                throw new \Exception('mb_strlen() failed.');
390            }
391            return $length;
392        }
393
394        return \strlen($str);
395    }
396
397    /**
398     * Multi-byte-safe substring calculation
399     *
400     * @param string $str
401     * @param int $start
402     * @param int $length (optional)
403     * @return string
404     */
405    private static function ourSubstr($str, $start = 0, $length = null)
406    {
407        // Premature optimization: cache the function_exists() result
408        static $exists = null;
409        if ($exists === null) {
410            $exists = \function_exists('\\mb_substr');
411        }
412        // If it exists, we need to make sure we're using 8bit mode
413        if ($exists) {
414            return \mb_substr($str, $start, $length, '8bit');
415        } elseif ($length !== null) {
416            return \substr($str, $start, $length);
417        }
418        return \substr($str, $start);
419    }
420}
421