As Armadillo was fixed, the PSP was hacked and all DSA keys in Debian were compromised. Or again about weak PRNG and (EC) DSA

About seven years ago, an archive with a seed of a key generator for a protector called Armadillo fell into the hands of crackers. Just some of the grateful users of the product wanted to test it for strength. And where else can you get a free audit of such an interesting code, if not on a cracker forum.

This generator was needed so that when a client buys your program protected by Armadillo, the merchant can automatically generate a license key for it. Also, it was used in Armadillo itself, and if there was an opportunity to find out the secret, then you could make a keygen for her. What made the code audit twice as interesting.

So, here it is , the original, obtained through the titanic efforts, archive. (source on C)
')
Try to understand without prompting what exactly the vulnerability is. Although there is a lot of code, but it is well read. Did not work out? And if you look at the 528 line?

Well, first there are several types of keys. The old, new, and so on. We are interested in the coolest, so-called Short level V10 ECC signed keys for which a good half of the sample is allocated with the mathematics of large numbers and elliptic. So, we will break ECDSA!

A 112 bit curve is used, the secret key ( x ) is also 112 bits. This is a bit too much for brute force.

But!

The secret values ​​are taken from the PRNG, which is initialized ... tada! 32 bit number !

Matan

To make keygen, you need to have a couple of valid keys for the program. In principle, one can do without one, but the first versions of the brutal force needed two keys to verify the correctness of the theory. Below it will be shown why.
Oh, and it was not easy to get them! After all, when you buy Armadillo, a temporary key is generated. And only then, having personally communicated with the developer, you get the real one. But, I again departed from the topic, we will continue.

In the key are the parameters of the ECDSA parameters h, r, s . h - message hash, r, s - signature parameters.

How to get them from there you can look in the samples, the only thing that r and s are called c and d in them.

So, we have two triples (r, s) h and (r ', s') h'

(EC) DSA

I will show the formulas using the DSA as the essence of the vulnerability is the same and the essence of the formulas is the same, they are just much more readable.

The secret key in DSA (EC) is a randomly chosen number x . Also (already only in DSA), two large prime numbers are selected:
q whose size is the same as the size of the hash function in bits.
p , such that (p-1) is divisible by q.
Another number g is chosen such that its multiplicative order modulo p is equal to q (see the article on the wiki). But we are not interested, just this number will be found in the formulas.

To generate a digital signature, we perform the following actions:

1. We generate random k
2. calculate r = g ^k mod p mod q
3. calculate s = k ^-1 (H ( m ) + x * r) mod q

Where H ( m ) is the hash of the message we are signing.

Vulnerability

Suppose we met two signatures with two identical r . s they are considered as follows:
s = k ^-1 (H (m) + x * r) mod q
s '= k ^-1 (H (m') + x * r) mod q

Subtract one from the other (all operations are carried out by module)
s - s '= k ^-1 (h + x * r) - k ^-1 (h' + x * r)

Now, k can be bracketed, since it is the same
s– s' = k ^-1 (h + x * r - h'– x * r)

x * r shrink
s– s '= k ^-1 (h– h')

Move k to the left
k = (h– h ') / (s - s')

and, as we remember, r = g ^k mod p mod q .
The whole problem here is in k . If it is known, then you can calculate the secret key x by the formula
x = ((s * k) - h) * r ^-1 mod q

This was done by the fail0verflow group in 2010, since Zoporuki coders from Sony guessed to generate k only once

With Armadillo, things were not so simple. r were always different, but due to the fact that the generator was initialized with a 32-bit number, the total number of options was 2 ³² , which made the search work for several hours.

Brute force algorithm (all modulo operations):

1. h '= -h
2. r '= r ^-1
3. s '= s * r'
4. h '= h' * r '
5. We start the cycle from 0 to 2 ³² -1 and in it:
6. Initialize the RNG counter
7. Generate the number k
8. We calculate x = ((s * k) - h) * r ^-1 mod q
9. Save this x

And so for both keys. It turns out for two somewhere 2.6 gigabytes of data. Then you just need to find the same x in them, it will be the secret key.

Similarly, it was possible to calculate any key pair in Debian, when in 2008 it turned out that PRNG initialized the number in the range 0-2 ¹⁵ because of a bug in OpenSSL. It is even easier than with armadillo. And all DSA keys generated in Debian from 2006 to 2008 inclusive were compromised .

Well, as for the armadillos, we notably patrolled the developers (keygen worked several versions), and then the vulnerability was fixed (updated keygen samples are also available , you can compare). By the way, the campaign is an exclusive, I did not post this archive to the public. And it was, by the way, earlier than the mentioned PSP hacks and the hole in the debian.

I hope it was interesting. Take care of your PRNG.

PS

Here is the archive with the same armadillo and two valid keys in my name. You can try to generate a key for yourself as a home task.
For 80 lvl: manage with one key. And what, quite an olympiad problem