Shamir::constantTimeSelect() - Code Metrics - unitpay/shamir - Measure and Improve Code Quality continuously with Scrutinizer

Shamir::constantTimeSelect() A
last analyzed 2021-10-26 13:47 UTC

↳ Parent: Shamir

Complexity

Conditions	3
Paths	2

Size

Total Lines	6
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	4
CRAP Score	3

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
eloc	3
c	1
b	0
f	0
dl	0
loc	6
ccs	4
cts	4
cp	1
rs	10
cc	3
nc	2
nop	3
crap	3

<?php

declare(strict_types=1);

namespace Unitpay\Shamir;

use DivisionByZeroError;
use InvalidArgumentException;
use RuntimeException;
use SplFixedArray;
use Throwable;

use function count;
use function pack;
use function random_int;
use function sprintf;
use function strlen;
use function unpack;

final class Shamir
{
    /**
     * @param string $secret Secret string to be split
     * @param int $parts Number of shares to be generated, must be at least 2, and less than 256
     * @param int $threshold Number of shares needed to reconstruct secret, must be at least 2, and less than 256
     *
     * @throws Throwable
     *
     * @return string[] Shares, each one byte longer than the secret with a tag used to reconstruct the secret
     */
    public static function split(string $secret, int $parts, int $threshold): array
    {
        // sanity check the input
        if ($parts < $threshold) {
            throw new InvalidArgumentException('Parts cannot be less than threshold.');
        }
        if ($parts > 255) {
            throw new InvalidArgumentException('Parts cannot exceed 255.');
        }
        if ($threshold < 2) {
            throw new InvalidArgumentException('Threshold must be at least 2.');
        }
        if ($threshold > 255) {
            throw new InvalidArgumentException('Threshold cannot exceed 255.');
        }

        $secret_len = strlen($secret);

        if ($secret_len === 0) {
            throw new InvalidArgumentException('Cannot split an empty secret.');
        }

        $secret_arr = SplFixedArray::fromArray(unpack('C*', $secret), false);

        // generate random list of x coordinates
        $xCoordinates = self::perm(255);

        // allocate the output array, initialize the final byte of the output with
        // the offset. The representation of each output is {y1, y2, .., yN, x}
        $out = new SplFixedArray($parts);
        for ($idx = 0; $idx < $parts; $idx++) {
            $out[$idx] = new SplFixedArray($secret_len + 1);
            $out[$idx][$secret_len] = $xCoordinates[$idx] + 1; // @review: is there possible overflow
        }

        // construct a random polynomial for each byte of the secret
        // because we are using a field of size 256, we can only represent a single byte as the intercept
        // of the polynomial, so we must use a new polynomial for each byte
        foreach ($secret_arr as $idx => $val) {
            try {
                $p = self::makePolynomial($val, $threshold - 1);
            } catch (Throwable $e) {
                throw new RuntimeException(sprintf('Failed to generate polynomial: %s.', $e->getMessage()));
            }

            // generate a `parts` number of (x,y) pairs
            // we cheat by encoding the x value once as the final index, so that it only needs to be stored once.
            for ($i = 0; $i < $parts; $i++) {
                $x = $xCoordinates[$i] + 1;
                $out[$i][$idx] = self::evaluatePolynomial($p, $x); // y
            }
        }

        // convert to strings
        $result = [];
        foreach ($out as $item) {
            $result[] = pack('C*', ...$item);
        }
        return $result;
    }

    /**
     * @param string[] $parts Shares strings
     *
     * @return string Reconstructed secret
     */
    public static function reconstruct(array $parts): string
    {
        $partsCount = count($parts);
        if ($partsCount < 2) {
            throw new InvalidArgumentException('Less than two parts cannot be used to reconstruct the secret.');
        }

        // verify the parts are all the same length
        $firstPartLen = strlen($parts[0]);
        if ($firstPartLen < 2) {
            throw new InvalidArgumentException('Parts must be at least two bytes.');
        }

        $parts_arr = new SplFixedArray($partsCount);

        $idx = 0;
        foreach ($parts as $_part) {
            $part = SplFixedArray::fromArray(unpack('C*', $_part), false);
            if ($part->getSize() !== $firstPartLen) {
                throw new InvalidArgumentException('All parts must be the same length.');
            }
            $parts_arr[$idx++] = $part;
        }

        // create a buffer to store the reconstructed secret
        $secret = new SplFixedArray($firstPartLen - 1);

        // buffer to store the samples
        $x_samples = new SplFixedArray($partsCount);
        $y_samples = new SplFixedArray($partsCount);

        // set the x value for each sample and ensure no x_sample values are the same,
        // otherwise div() can be unhappy
        $checkMap = [];
        foreach ($parts_arr as $i => $part) {
            $samp = $part[$firstPartLen-1];
            if (isset($checkMap[$samp])) {
                throw new RuntimeException('Duplicate part detected.');
            }
            $checkMap[$samp] = true;
            $x_samples[$i] = $samp;
        }

        // reconstruct each byte
        foreach ($secret as $idx => $_) {
            // set the y value for each sample
            foreach ($parts_arr as $i => $part) {
                $y_samples[$i] = $part[$idx];
            }

            // interpolate the polynomial and compute the value at 0
            // evaluate the 0th value to get the intercept
            $secret[$idx] = self::interpolatePolynomial($x_samples, $y_samples, 0);
        }

        return pack('C*', ...$secret);
    }

    private static function div(int $a, int $b): int
    {
        if ($b === 0) {
            // leaks some timing information, but we don't care anyways as this (should never happen)
            throw new DivisionByZeroError('Divide by zero.');
        }

        $diff = ((Tables::logTable[$a] - Tables::logTable[$b]) + 255) % 255;
        /** @psalm-suppress PossiblyInvalidArrayOffset */
        $ret = Tables::expTable[$diff];

        // ensure we return zero if $a is zero but aren't subject to timing attacks
        return self::constantTimeSelect(self::constantTimeByteEq($a, 0), 0, $ret);
    }

    /**
     * Multiplies two numbers in GF(2^8)
     */
    private static function mult(int $a, int $b): int
    {
        $sum = (Tables::logTable[$a] + Tables::logTable[$b]) % 255;
        $ret = Tables::expTable[$sum];

        // ensure we return zero if either a or b are zero but aren't subject to timing attacks
        $ret = self::constantTimeSelect(self::constantTimeByteEq($a, 0), 0, $ret);
        return self::constantTimeSelect(self::constantTimeByteEq($b, 0), 0, $ret);
    }

    /**
     * Combines two numbers in GF(2^8), this can also be used for subtraction since it is symmetric
     */
    private static function add(int $a, int $b): int
    {
        return $a ^ $b;
    }

    /**
     * Constructs a random polynomial of the given degree but with the provided intercept value
     *
     * @throws Throwable
     */
    private static function makePolynomial(int $intercept, int $degree): SplFixedArray
    {
        $size = $degree + 1;
        // create a wrapper
        $coefficients = new SplFixedArray($size);
        // ensure the intercept is set
        $coefficients[0] = $intercept;
        for ($i = 1; $i < $size; $i++) {
            $coefficients[$i] = random_int(0, 255);
        }

        return $coefficients;
    }

    private static function evaluatePolynomial(SplFixedArray $coefficients, int $x): int
    {
        // special case the origin
        if ($x === 0) {
            return $coefficients[0];
        }
        // compute the polynomial value using Horner`s method.
        $degree = $coefficients->getSize() - 1;
        $out = $coefficients[$degree];
        for ($i = $degree - 1; $i >= 0; $i--) {
            $coeff = $coefficients[$i];
            $out = self::add(self::mult($out, $x), $coeff);
        }
        return $out;
    }

    /**
     * Takes N sample points and returns the value at a given $x using a lagrange interpolation
     */
    private static function interpolatePolynomial(SplFixedArray $x_samples, SplFixedArray $y_samples, int $x): int
    {
        $limit = $x_samples->getSize();
        $result = 0;
        for ($i = 0; $i < $limit; $i++) {
            $basis = 1;
            for ($j = 0; $j < $limit; $j++) {
                if ($i === $j) {
                    continue;
                }
                $num = self::add($x, $x_samples[$j]);
                $denom = self::add($x_samples[$i], $x_samples[$j]);
                $term = self::div($num, $denom);
                $basis = self::mult($basis, $term);
            }
            $group = self::mult($y_samples[$i], $basis);
            $result = self::add($result, $group);
        }
        return $result;
    }

    /**
     * Returns, as a slice of $n ints, a pseudo-random permutation of the integers  in the half-open interval [0,n)
     *
     * @throws Throwable
     */
    private static function perm(int $n): SplFixedArray
    {
        $m = new SplFixedArray($n);
        for ($i = 0; $i < $n; $i++) {
            $j = random_int(0, $i);
            $m[$i] = $m[$j];
            $m[$j] = $i;
        }
        return $m;
    }

    /**
     * Returns $x if $v === 1 and $y if $v === 0, its behavior is undefined if $v takes any other value
     */
    private static function constantTimeSelect(int $v, int $x, int $y): int
    {
        if ($v !== 0 && $v !== 1) {
            throw new RuntimeException('Undefined behavior.');
        }
        return ~($v-1) & $x | ($v-1) & $y;
    }

    /**
     * Returns 1 if $x === $y and 0 otherwise
     */
    private static function constantTimeByteEq(int $x, int $y): int
    {
        if ((((~0xFF) & $x) | ((~0xFF) & $y)) !== 0) { // check is both uint8
            throw new InvalidArgumentException('Not uint8 values passed.');
        }
        return ($x ^ $y) === 0 ? 1 : 0;
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		namespace Unitpay\Shamir;
6
7		use DivisionByZeroError;
8		use InvalidArgumentException;
9		use RuntimeException;
10		use SplFixedArray;
11		use Throwable;
12
13		use function count;
14		use function pack;
15		use function random_int;
16		use function sprintf;
17		use function strlen;
18		use function unpack;
19
20		final class Shamir
21		{
22		/**
23		* @param string $secret Secret string to be split
24		* @param int $parts Number of shares to be generated, must be at least 2, and less than 256
25		* @param int $threshold Number of shares needed to reconstruct secret, must be at least 2, and less than 256
26		*
27		* @throws Throwable
28		*
29		* @return string[] Shares, each one byte longer than the secret with a tag used to reconstruct the secret
30		*/
31	8	public static function split(string $secret, int $parts, int $threshold): array
32		{
33		// sanity check the input
34	8	if ($parts < $threshold) {
35	1	throw new InvalidArgumentException('Parts cannot be less than threshold.');
36		}
37	7	if ($parts > 255) {
38	1	throw new InvalidArgumentException('Parts cannot exceed 255.');
39		}
40	6	if ($threshold < 2) {
41	2	throw new InvalidArgumentException('Threshold must be at least 2.');
42		}
43	4	if ($threshold > 255) {
44		throw new InvalidArgumentException('Threshold cannot exceed 255.');
45		}
46
47	4	$secret_len = strlen($secret);
48
49	4	if ($secret_len === 0) {
50	1	throw new InvalidArgumentException('Cannot split an empty secret.');
51		}
52
53	3	$secret_arr = SplFixedArray::fromArray(unpack('C*', $secret), false);
54
55		// generate random list of x coordinates
56	3	$xCoordinates = self::perm(255);
57
58		// allocate the output array, initialize the final byte of the output with
59		// the offset. The representation of each output is {y1, y2, .., yN, x}
60	3	$out = new SplFixedArray($parts);
61	3	for ($idx = 0; $idx < $parts; $idx++) {
62	3	$out[$idx] = new SplFixedArray($secret_len + 1);
63	3	$out[$idx][$secret_len] = $xCoordinates[$idx] + 1; // @review: is there possible overflow
64		}
65
66		// construct a random polynomial for each byte of the secret
67		// because we are using a field of size 256, we can only represent a single byte as the intercept
68		// of the polynomial, so we must use a new polynomial for each byte
69	3	foreach ($secret_arr as $idx => $val) {
70		try {
71	3	$p = self::makePolynomial($val, $threshold - 1);
72		} catch (Throwable $e) {
73		throw new RuntimeException(sprintf('Failed to generate polynomial: %s.', $e->getMessage()));
74		}
75
76		// generate a `parts` number of (x,y) pairs
77		// we cheat by encoding the x value once as the final index, so that it only needs to be stored once.
78	3	for ($i = 0; $i < $parts; $i++) {
79	3	$x = $xCoordinates[$i] + 1;
80	3	$out[$i][$idx] = self::evaluatePolynomial($p, $x); // y
81		}
82		}
83
84		// convert to strings
85	3	$result = [];
86	3	foreach ($out as $item) {
87	3	$result[] = pack('C*', ...$item);
88		}
89	3	return $result;
90		}
91
92		/**
93		* @param string[] $parts Shares strings
94		*
95		* @return string Reconstructed secret
96		*/
97	6	public static function reconstruct(array $parts): string
98		{
99	6	$partsCount = count($parts);
100	6	if ($partsCount < 2) {
101	1	throw new InvalidArgumentException('Less than two parts cannot be used to reconstruct the secret.');
102		}
103
104		// verify the parts are all the same length
105	5	$firstPartLen = strlen($parts[0]);
106	5	if ($firstPartLen < 2) {
107	1	throw new InvalidArgumentException('Parts must be at least two bytes.');
108		}
109
110	4	$parts_arr = new SplFixedArray($partsCount);
111
112	4	$idx = 0;
113	4	foreach ($parts as $_part) {
114	4	$part = SplFixedArray::fromArray(unpack('C*', $_part), false);
115	4	if ($part->getSize() !== $firstPartLen) {
116	1	throw new InvalidArgumentException('All parts must be the same length.');
117		}
118	4	$parts_arr[$idx++] = $part;
119		}
120
121		// create a buffer to store the reconstructed secret
122	3	$secret = new SplFixedArray($firstPartLen - 1);
123
124		// buffer to store the samples
125	3	$x_samples = new SplFixedArray($partsCount);
126	3	$y_samples = new SplFixedArray($partsCount);
127
128		// set the x value for each sample and ensure no x_sample values are the same,
129		// otherwise div() can be unhappy
130	3	$checkMap = [];
131	3	foreach ($parts_arr as $i => $part) {
132	3	$samp = $part[$firstPartLen-1];
133	3	if (isset($checkMap[$samp])) {
134	1	throw new RuntimeException('Duplicate part detected.');
135		}
136	3	$checkMap[$samp] = true;
137	3	$x_samples[$i] = $samp;
138		}
139
140		// reconstruct each byte
141	2	foreach ($secret as $idx => $_) {
142		// set the y value for each sample
143	2	foreach ($parts_arr as $i => $part) {
144	2	$y_samples[$i] = $part[$idx];
145		}
146
147		// interpolate the polynomial and compute the value at 0
148		// evaluate the 0th value to get the intercept
149	2	$secret[$idx] = self::interpolatePolynomial($x_samples, $y_samples, 0);
150		}
151
152	2	return pack('C*', ...$secret);
153		}
154
155	5	private static function div(int $a, int $b): int
156		{
157	5	if ($b === 0) {
158		// leaks some timing information, but we don't care anyways as this (should never happen)
159	1	throw new DivisionByZeroError('Divide by zero.');
160		}
161
162	4	$diff = ((Tables::logTable[$a] - Tables::logTable[$b]) + 255) % 255;
163		/** @psalm-suppress PossiblyInvalidArrayOffset */
164	4	$ret = Tables::expTable[$diff];
165
166		// ensure we return zero if $a is zero but aren't subject to timing attacks
167	4	return self::constantTimeSelect(self::constantTimeByteEq($a, 0), 0, $ret);
168		}
169
170		/**
171		* Multiplies two numbers in GF(2^8)
172		*/
173	6	private static function mult(int $a, int $b): int
174		{
175	6	$sum = (Tables::logTable[$a] + Tables::logTable[$b]) % 255;
176	6	$ret = Tables::expTable[$sum];
177
178		// ensure we return zero if either a or b are zero but aren't subject to timing attacks
179	6	$ret = self::constantTimeSelect(self::constantTimeByteEq($a, 0), 0, $ret);
180	6	return self::constantTimeSelect(self::constantTimeByteEq($b, 0), 0, $ret);
181		}
182
183		/**
184		* Combines two numbers in GF(2^8), this can also be used for subtraction since it is symmetric
185		*/
186	6	private static function add(int $a, int $b): int
187		{
188	6	return $a ^ $b;
189		}
190
191		/**
192		* Constructs a random polynomial of the given degree but with the provided intercept value
193		*
194		* @throws Throwable
195		*/
196	6	private static function makePolynomial(int $intercept, int $degree): SplFixedArray
197		{
198	6	$size = $degree + 1;
199		// create a wrapper
200	6	$coefficients = new SplFixedArray($size);
201		// ensure the intercept is set
202	6	$coefficients[0] = $intercept;
203	6	for ($i = 1; $i < $size; $i++) {
204	6	$coefficients[$i] = random_int(0, 255);
205		}
206
207	6	return $coefficients;
208		}
209
210	5	private static function evaluatePolynomial(SplFixedArray $coefficients, int $x): int
211		{
212		// special case the origin
213	5	if ($x === 0) {
214	1	return $coefficients[0];
215		}
216		// compute the polynomial value using Horner`s method.
217	5	$degree = $coefficients->getSize() - 1;
218	5	$out = $coefficients[$degree];
219	5	for ($i = $degree - 1; $i >= 0; $i--) {
220	5	$coeff = $coefficients[$i];
221	5	$out = self::add(self::mult($out, $x), $coeff);
222		}
223	5	return $out;
224		}
225
226		/**
227		* Takes N sample points and returns the value at a given $x using a lagrange interpolation
228		*/
229	3	private static function interpolatePolynomial(SplFixedArray $x_samples, SplFixedArray $y_samples, int $x): int
230		{
231	3	$limit = $x_samples->getSize();
232	3	$result = 0;
233	3	for ($i = 0; $i < $limit; $i++) {
234	3	$basis = 1;
235	3	for ($j = 0; $j < $limit; $j++) {
236	3	if ($i === $j) {
237	3	continue;
238		}
239	3	$num = self::add($x, $x_samples[$j]);
240	3	$denom = self::add($x_samples[$i], $x_samples[$j]);
241	3	$term = self::div($num, $denom);
242	3	$basis = self::mult($basis, $term);
243		}
244	3	$group = self::mult($y_samples[$i], $basis);
245	3	$result = self::add($result, $group);
246		}
247	3	return $result;
248		}
249
250		/**
251		* Returns, as a slice of $n ints, a pseudo-random permutation of the integers in the half-open interval [0,n)
252		*
253		* @throws Throwable
254		*/
255	3	private static function perm(int $n): SplFixedArray
256		{
257	3	$m = new SplFixedArray($n);
258	3	for ($i = 0; $i < $n; $i++) {
259	3	$j = random_int(0, $i);
260	3	$m[$i] = $m[$j];
261	3	$m[$j] = $i;
262		}
263	3	return $m;
264		}
265
266		/**
267		* Returns $x if $v === 1 and $y if $v === 0, its behavior is undefined if $v takes any other value
268		*/
269	9	private static function constantTimeSelect(int $v, int $x, int $y): int
270		{
271	9	if ($v !== 0 && $v !== 1) {
272	1	throw new RuntimeException('Undefined behavior.');
273		}
274	8	return ~($v-1) & $x \| ($v-1) & $y;
275		}
276
277		/**
278		* Returns 1 if $x === $y and 0 otherwise
279		*/
280	10	private static function constantTimeByteEq(int $x, int $y): int
281		{
282	10	if ((((~0xFF) & $x) \| ((~0xFF) & $y)) !== 0) { // check is both uint8
283	2	throw new InvalidArgumentException('Not uint8 values passed.');
284		}
285	8	return ($x ^ $y) === 0 ? 1 : 0;
286		}
287		}
288

unitpay / shamir

Shamir::constantTimeSelect() A last analyzed 2021-10-26 13:47 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

Shamir::constantTimeSelect() A
last analyzed 2021-10-26 13:47 UTC