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

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

This generator was needed so that when a client purchases your Armadillo-protected program, the merchant can automatically generate a license key for it. It was also used in Armadillo itself and, if there was an opportunity to find out a secret, then it would be possible to make keygen for her herself. What made code auditing doubly interesting.

So, here it is , an original archive obtained through titanic efforts. (source in C)

Try without clues to understand exactly what the vulnerability is hidden. Although there is a lot of code, it is well read. Did not work out? And if you look at the 528 line?

Well, firstly there are several types of keys. Old, new, etc. We are interested in the coolest ones, the so-called Short level V10 ECC signed keys for which a good half of the class with the mathematics of large numbers and the elliptic is reserved. So, we will break ECDSA!

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

But!

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

Matan

To make keygen, you need to have a pair of valid keys for the program. In principle, you can get by with one, but the first versions of the brute-force machine 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 talked with the developer, do you get the real one. But, I again stepped back from the topic, continue.

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

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

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

(EC) DSA

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

The secret key in the (EC) DSA is the random number x . Also (already only in DSA), two large primes are selected:
q , the size of which coincides with the size of the hash of the function in bits.
p such that (p-1) is divisible by q.
We also choose a number g such that its multiplicative order modulo p is q (see the wiki article). 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. Generate random k
2. compute 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 that 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 modulo)
s - s' = k ^-1 (h + x * r) - k ^-1 (h '+ x * r)

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

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

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

a as we rememberr = 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

What was done by fail0verflow in 2010, because zhoporukye encoders from Sony thought of generating k only once

With Armadillo, it was 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 enumeration a matter of several hours.

The search algorithm (all operations modulo):

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. We initialize the RNG counter
7. Generate the number k
8. Compute 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.

In the same way, it was possible to calculate any key pair in Debian, when in 2008 it turned out that due to a bug in OpenSSL, the PRNG was initialized with a number in the range 0-2 ¹⁵ . This is even easier than with armadilla. And all the DSA keys generated by Debian from 2006 to 2008 inclusive were compromised .

Well, as for the Armadilla, we have notably trolled the developers (keygen worked several versions), and then the vulnerability was fixed (updated keygen sorts are also availablecan compare). By the way, this campaign is exclusive, I did not upload this archive to public. And it was, by the way, earlier than the mentioned PSP hacks and a hole in the debian.

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

PS

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