CryptAda - (nuclear) crypto on embedded device

The project sources

As junior DevOps/SRE, we're quite interested in cryptography and its usage. Therefore, when we were asked to participate to this contest for a uni project, we decided to go for some cryptography-related subject.

For the quite small knowledge we had on the subject, we thought that having a software on the embedded device that could generate RSA keys would be a good start.

The first steps - Bignums

In order to generate RSA private keys, we need a way to obtain big, very big prime numbers. Those numbers we need are way too big for classical number representation in ADA. We need a way to manipulate Bignums, aka number that can have hundreds of number of digits. Typical RSA keys as in 2020 contains 2048 or 4096 bits, so if we want to create such keys, we need bignums that can handle at least 4096 digits.

For the project, we first looked at a library to handle without dependencies bignum, but this library was too limited and too slow. Therefore, we created a bignum library, fitting our needs (allocation on the stack, fast operations, base 256 for better performances, handling negative numbers, ...). We spent quite some time optimizing it, since numbers computations will be most of the CPU time used to generate a key.

Pseudo-prime numbers

The algorithm to find a prime number is quite easy to understand, and leave very few place for optimization. To assert that n is prime, we look at (x * x) mod n, with x going from 2 to sqrt(n).
This operation is slow, and not suitable for 2048 bits numbers. To have an efficient way to assert that a number is prime, we switch to checking it to be pseudo-prime, with a sufficient probability.
A pseudo-prime number means that this number has a probability n of being prime, and functions generating pseudo-prime number must allow us to choose this n value.

We tweaked a bit, and found the best way to generate prime number with a probability > 99.999 % in a reasonable time. The algorithm is the following:
- Check for it being prime with all the prime numbers < 100 using a ~sieve of Eratosthenes
- Check for it being pseudo-prime using Fermat's primality test with {2, 3, 5, 7}
- Run a Miller-Rabin test with 4 iterations using randomly generated witnesses
- Run a Miller-Rabin test with a number of iterations depending on the number being checked with randomly generated witnesses
When a number passes all of this tests, it is safe (up to a defined probability) to consider it being prime.

Random number generator

Random numbers are required to run such algorithms. But random must respect some conditions. We're not only looking for a Pseudo Random Number Generator (PRNG), but for a PRNG that either mix entropy or is Cryptographically Secure (CSPRNG). As we're on an embedded device, we have GPIO pins and sensors, so we chose the first option as entropy could be generated easily.

We implemented a PRNG fed with entropy, inspired by the Linux PRNG (/dev/random). We have an entropy pool of 2048 bits, that is constantly fed by the noise generated by the 3-axis accelerometer using a mixing function. We also have an extraction function, that consume some of the entropy available in the pool (accounted by a estimation function that maintains a gauge every time an operation is performed on the entropy pool) to give a random number.

In our application, entropy is collected periodically in the background, since we created an ADA Task to perform this operation.

The implementation uses chacha20 as a hash function for the extraction process, which can be resumed as:
- Hash the whole entropy pool
- Fold the hash in a 16 bytes hash
- Mix the hash back in the pool to mix-it and re-credit some entropy
- Re-extract 16 bytes of entropy from the pool
- Xor and fold the initial hash and the entropy newly extracted to create a 64 bits output value

The entropy pool can also be fed by any source of entropy, and we also looked on nuclear decay. Unfortunately, our Geiger-Müller counter was shipped with a lot of delay, and we lack the time to interface it.

RSA

With prime numbers and a random number generator, it is finally possible to create RSA keys. The project offers a graphical interface on the touch screen of the board to choose the RSA key size between 256, 512 and 768, which are the biggest key that can be generated in a reasonable time on such low-specs board. The touch screen also permits the user to generate a key, and to print it on the USART connection. The project aims to be a good start for either an embedded crypto library, or for a device like a smartcard (Yubikey).

A RSA key is dumped on the USART using the ASN.1 format, but as a conf file. Here's an example of a very small RSA key generated by the board:

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:187031899687190461
pubExp=INTEGER:65537
privExp=INTEGER:113679732755818241
p=INTEGER:191569309
q=INTEGER:976314529
e1=INTEGER:45208217
e2=INTEGER:554591105
coeff=INTEGER:98718018

With openssl, the configuration above can easily be converted to the DER/PEM format, making the key suitable for most applications.