Detailed Algorithm Specification

Executive Summary

Signidice algorithm has been analyzed with regard to the following parameters:

Security. The algorithm applies the digital RSA signature; an instance was submitted to a range of test attacks.
Number generation quality. The algorithm is intended for fair random number generation (FRNG) within games. Therefore, we performed a range of tests to identify the quality of randomization.

All in all, the results are quite positive for both parameters. No attacks able of damaging the algorithm within a specific time-frame seem to exist. Likewise, sequences obtained via the suggested algorithm can be considered close to truly random.

Algorithm security

We emulated a range of popular attacks against RSA algorithms to test our solution, namely:

RSA homomorphic attack
Аlternative keys
Low private exponent attack
Low public exponent attack
Common modulus
Davida's attack
Blind signature attack
Random faults

The results proved that the solution resists attacks well; moreover, no other fraud sequences applicable to our protocol have been detected so far.

Randomization Quality

We researched statistics of sequences generated via Signidice. Two stages of tests were performed, namely, graphic statistical tests and NIST test suites.

In the framework of graphic tests two sequences were used: one obtained with RSA signature and the other generated by Random.org for reference. The test set based on 'Methods and Tools for Pseudo-Random Number Generators Quality Evaluation’ book by M. Ivanov and I. Chugunkov’ included the following tests:

Data distribution in histogram
Lag-plot
Bit series distribution
Monotonicity evaluation
Autocorrelation plot (correlograms)

All tests proved that the generated sequence is close to being truly random. Given minor discrepancy between the tested and the reference sequences, we can claim that the suggested algorithm delivers high quality random number generation.

NIST statistical tests are only applicable to RSA sequences and using a reference sequence is not feasible. The following tests were performed:

Frequency (monobit) test
Frequency test within a block
Cumulative sums (Cusums) test
Runs test
Longest Run-of-ones in a block test
Binary matrix rank test
Discrete Fourier transform (spectral) test
Non-Overlapping (Aperiodic) Template Matching Test
Approximate entropy test
Serial test

These test also yielded positive results and backed conclusions of the above test set with regard to randomization quality.

Algorithm

Algorithm Specification

The specification below provides an abridged description of our version of Signidice. While applied issues are omitted, the document focuses on cryptographic transformations.

Let's assume that the game involves three participants: Casino (B), player (P), smart contract (C).

B Generates RSA parameters.

Then, under the suggested algorithm, for the specified public exponent e and a key length of B=2048 bit p and q are generated as follows:

q length is defined:

As the result of enumeration we get a p number with a length of B-qs, so that bits for the number come from an RC4-based generator.

p is a prime number, probability is:

(use the Miller-Rabin primality test to check it).

The q number of qs length is generated the same way. The next step is to check the following condition:
If it cannot be met, p and q are regenerated.
Once the condition is met, the modulus is calculated:

Then, the private key is calculated in the following way.

$d= e^{-1}mod \varphi (N)$

where

$\varphi(N) = (p - 1)(q - 1)$

Then generation is complete.

B: Writes N and e to Smart Contract (C).
P: Generates a random number R (R < N) and transmits it to B and C
C: Checks whether R has been used before.
B, C: Calculate V:

Where meta stands for metadata related to the game channel (game ID, round number etc.)

B: Calculates S:

$S= RSA_{Sign}(V)= V^{^{d}}mod N$

Then, checks whether the signature has been generated correctly and sends it to P and C.

P and C: Check the signature with the use of an open key e:

$S^{e} mod N==V ?$

The final signature generates game results and distributes rewards.

Adversary's Goals

For the player (P):

To predict the signature result and make the right bid.
Get the necessary result during the signature process.

For the casino (B):

To forge the signature result to change the game result in the favor of casino.

Overview of Known RSA Attacks

Attacks were selected on the basis of 2006 article “Mathematical Attacks on RSA Cryptosystem”, by Imad Khaled Salah, Abdullah Darwish and Saleh Oqeili. Apart from attacks mentioned there, we included the alternative key generation threat.
Note that we expect the audience of this chapter to be familiar with the basics of modular arithmetic.

RSA Homomorphic Encryption

With regard to multiplication, an unpadded RSA is a partially homomorphic encryption algorithm. In math terms in means:

Let’s assume that a player P sends two numbers (m1 and m2) for signing and receives the following signatures:

$s_{1}=m_{1}^{в} mod N$

$s_{2}=m_{2}^{в} mod N$

Then P sends m3=m1*m2 for signing, and the following is true:

$s_{3}=m_{3}^{d} mod N= (m_{1}*m_{2})^{d} mod N=(m_{1}^{d}*m_{2}^{d}) mod N= m_{1}^{d} mod N* m_{2}^{d}mod N=s_{1}*s_{2} mod N$

In this case a player is well aware of the signature result in advance, in the given example the result every time is calculated as follows:

$s_{1}=V_{1}^{d} mod N$

$s_{2}=V_{2}^{d} mod N$

Then, to perform an attack a player has to pick an R to satisfy the following condition:

$V_{3}=V_{1}*V_{2} mod N$

But V₃ is a SHA hashing result from R and a metadata set that cannot be tampered by any of the players. Thus, SHA cryptologic resistance prevents obtaining the right R within the given time frame.

Alternative Key Generation

The alternative key generation concept implies that the same message encrypted with multiple private keys remains valid. Note that the whole strategy is based on the fact that a signature (i.e. an encrypted message) appears both valid and unchanged regardless of which alternative key is applied. To demonstrate it, let's consider the widely used formula for alternative key generation and see how a message signed with an alternative key appears to be identical to the original one.
The following parameters set the RSA system:

N – system modulus
e – public key
d – private key

Let's define a message m; the message is a number < N. The element order a modulo m is the smallest positive integer lsatisfying the following:

$a^{l}\equiv 1 mod m$

The order of the message modulo N is:

Then:

$m^{r}\equiv 1 mod N$

Given that d is a private key, all alternative encryption keys

$d_{a}$

for a message m have the following format:

$d_{a}\equiv d mod r$

If r values are comparable,

$d_{a}$

can be expressed in the following way:

$d_{a}=d+i*r$

, for some i ϵ Z

Valid key message signature can be then expressed as follows:

$s=m^{d} mod N$

And, alternative key message signature has the following format:

$s'= m^{d_{a}} mod N$

Given that

$d_{a}=d+ir$

we have

$m^{d_{a}} mod N=m^{d+ir} mod N$

Let's apply the degree properties :

$m^{d+i*r} mod N= m^{d}*m^{i*r} mod N= m^{d}*(m^{r})^{i} mod N$

As we mentioned previously:

$m^{r}\equiv1 mod N$

therefore, the following is true:

$m^{d}*(m^{r})^{i} mod N \equiv m^{d}*(1)^{i} mod N= m^{d} mod N$

The obtained equation represents the valid key signature:

$m^{d} mod N=s$

The above steps allow concluding that both valid and alternative key signatures do look identical:

$s'= m^{d_{a}} mod N\equiv m^{d+i*r} mod N\equiv m^{d}*m^{i*r} mod N\equivm^{d}*(m^{r})^{i} mod N\equiv m^{d}*(1)^{i} mod N\equiv m^{d} mod N=s$

Low Private Exponent Attack (Wiener's Attack)

When a private key d is small enough, an attacker can expose it. Let's consider the theorem below (without proof):

Let

, where

. Let's also assume that

$1/3 * N^{0.25}$

.
Suppose that an attacker has a public key (e, N); then he can effectively determine d.

Considering the attack itself is out of the scope of the present explanation, the given theorem suffices to illustrate vulnerability. Note that in its current realization the public exponent e is fixed and equals 65537 d is generated randomly so that:

$d\equiv e^{-1} mod \varphi (N)$

Both parts are then multiplied by e:

$de\equiv 1 mod \varphi (N)$

The modular equation definition yields:

$de = 1 +k*\varphi (N)$

d is expressed as follows:

$d=\frac{1+k\varphi (N)e}{e}$

It appears that (N)'s value is comparable to that of N itself,

$e\approx 2^{16}$

minimal k = 1. Then, d can be expressed as:

$d\approx \frac{N}{2^{16}}$

Let's compare the obtained number to the one from the theorem. Let’s visualize them as N functions.

The green line on the graph indicates the function

$1/3 * N^{0.25}$

, whereas

$\frac{N}{2^{16}}$

is indicated by a red line. It appears that even with low values (graphs were constructed for N value from 0 to 2^20) the encrypting exponents of the regarded algorithm realization do exceed the required threshold.
With N values going up the gap also is also increasing (till N = 2^100):

RSA required much larger numbers, with a higher private key security threshold.

Low Public Exponent Attacks

Most part of detected LPE attacks only expose signed messages. Given that in Signidice signed messages are public, this attack type is useless save for one exception. The private key d is exposed if its minor

$\frac{n}{4}$

(where n stands for an RSA modulus) is obtained by an attacker. Yet, a casino's private key stored locally is not supposed to be transmitted, rendering the attack highly unlikely.

Common Modulus and Davida's Attacks

Both of these attacks can be used only for reading the signed message.

Blind Signature Attack

Let’s assume that an adversary wants Bob to sign the message M without knowing it. For that purpose, the adversary has to take the following steps:

Chooses a random r number.
Computes $M^{'} = r^{e}*M$ , where e is a public exponent.
Sends M' for signing.

Now the adversary can compute the signature as follows:

$S =S^{'}/r =(M^{'d} mod N) / r =( (r^{e}*M)^{d} mod N) / r = (r*M^{d} mod N) / r=M^{d} mod N$

Similar to the above RSA homomorphic attack, this one is not applicable to the suggested algorithm, as there is a hash function applied to data sent to a casino for signing. Given the security level, we are certain that a player will not be able to calculate the value satisfying the following expression:

$SHA256(M) = r^{e}*SHA256(M^{'})$

Random Fault Attack with the Use of CRT

factorization and CRT based algorithm can be utilized to accelerate the raising to power with a modular exponentiation. In case of any fault a adversary will be able to expose p and q. However, this fault can only eventually lead to an invalid signature. Our algorithm has its signature validity checked every time before publishing, which means a adversary is unable to obtain it in case of an unexpected fault.

Statistical tests

Overview

A part of Signidice is considered as a pseudorandom number generator (further on referred to as the Generator) that operates in the following way:

Generates a certain value V on the basis of a player random number and metadata; this value is signed by a bankroller.
Then the modular remainder of 128 is taken from the obtained signature. The resulting number (0 to 127 included) represents the generator output.

Tests were performed in two stages: graphic statistical tests and NIST test suites. Unlike real-life algorithm, no random numbers were input to the generator; arithmetic sequences like x, x+1, x+2, x+3.... where x is a random seed, were applied instead. The purpose is to ensure more control over dependencies and potential non-randomness and to demonstrate that even in the given environment output is quite close to being truly random (further the input method is referred to as a counter mode). Also, normal distribution number selection tests were performed. Results matched those obtained with the counter mode applied, therefore these tests are not covered here.

Graphical tests

In the course of testing two sequences were used: one obtained from the generator operation in counter mode and the other generated at Random.org for reference.

The test set included the following (based on 'Methods and Tools for Pseudo-Random Number Generators Quality Evaluation’ by M. Ivanov and I. Chugunkov):

Data distribution in a histogram
Lag-plot
Bit series distribution
Evaluating monotonicity Autocorrelation plot (correlograms)

Sequences of different N length were used in the testing, which is explained by test requirements, some of which need a bigger amount of input data, while others might only need sequences of 10000 elements.

Data Distribution in a Histogram

This test is aimed at identifying quality of distribution of elements in a sample (N). The histogram is based on element occurrence frequency.

Smaller difference between bars of juxtaposed charts indicates a higher generation quality.

N = 100 000.

Test results (comparison charts)

Test results prove low difference in bar heights of both samples; similarly, the frequency of elements is acceptable.

Lag-plot

This test is intended for identifying the dependence between the sequence elements. Sequence

$e_{1},e_{2},...,e_{N}$

is demonstrated on the chart as coordinate points

$(e_{i},e_{i+1})$

Sequence

$e_{1},e_{2},...,e_{N}$

coordinates points

$(e_{i},e_{i+1})$

are added to the plot.

The charts below clearly illustrate chaotic positioning of dots and the absence of visible pattern which prove that a sequence is random. If the tested sequence N is incremented, the field is going to be eventually fully covered with dots.

N = 10 000

Test Result Charts

Bit Series Distribution

Tests for *n = 1, 2, 3 were performed. The results allow identifying the n-gram bit distribution equality represented as sequence bits. Random sequences have equal distribution; in other words, each n-gram has the same occurrence number.

N = 100 000

Test Result Charts

For n = 1 (the 1 to 0 correlation in the sample sequence):

For n = 2:
For n = 3:

The results satisfy the sequence requirements (properties are close to truly random), the amount of n-grams is almost the same.

Evaluating Monotonicity

For a sequence with statistical qualities close to truly random, possibility of non-increasing (or non-decreasing) sectors depends on its length: the longer the sequence, the smaller the probability. Random sequences cannot face long non-increasing (or non-decreasing) sectors.

N = 20 000

Test Result Charts

The bars of the charts below show the size of monotonous subsequences within the tested sequence. It is clearly visible that most part of monotonous subsequences contain 2 elements or less. The longest contains 7 elements. These results allow concluding that generated numbers are close to being truly random.

Autocorrelation Plot (Correlograms)

The test is designed to check correlation of shifts within the sequence. The tested sequence has to be normalized in order to construct autocorrelation. Let

$a_{R-1}a_{R-2}...a_{0}$

be a binary representation of an i element of the sequence.

Therefore, its normalized value is:

$b_{i}=\sum_{j=0}^{R-1}(-1)^{a_{j}}*2^{j}$

The next step is to compute the correlation lags between the shifted sequence copies. The following formula applies:

$c_{j}=\frac{\sum_{j=0}^{n-1}b_{i}*b_{i+j}mod\, n}{\sum_{j=0}^{n-1}b^{2}_{i}}$

For a sequence close to truly random the correlation lags value is supposed to be close to zero at all shifting points.

N = 10 000

Test Result Charts

At all shifting points correlation lag values are close to zero showing that each tested sequence is close to truly random.

NIST Statistical tests

NIST Statistical Test Suite is a suite of 15 tests intended for defining the closeness of a binary sequence to truly random. These tests are based on various statistic properties on characteristic of truly random sequences. We've generated a test sequence of 100,000 elements in counter mode (we chose this mode for the same reason we had for graphic tests). The sample size predetermined the use of the following tests:

Frequency (Monobit) Test
Frequency Test within a Block
Cumulative Sums (Cusums) Test
Runs Test
Tests for the Longest-Run-of-Ones in a Block
Binary Matrix Rank Test
Discrete Fourier Transform (spectral) Test
Non-overlapping Template Matching Test
Approximate Entropy Test
Serial Test

The idea of these tests is likely to coincide with some of the graphical tests above. Yet, these provide a particular ranking, that does not necessarily depend on checker’s opinion, therefore rechecking is reasonable.

For test results download the tests_result.txt. A test is considered successful, if P-value > 0.01 and PROPORTION > 0.800.

For detailed coverage of each test, additional documentation and testing software guidelines, follow the links:

Is this article helpful for you?

Customer support service by UserEcho