In the States, GOSTs are also so-so. Fatal vulnerability in YubiKey FIPS

Hi% username%!

On June 13, 2019, Yubico, a manufacturer of devices for two-factor authentication, issued a security notice , which addresses the critical vulnerability of some Yubikey FIPS devices. Let's see what this vulnerability is and how it could be prevented.

Foreword

The States also have their own GOST standards, called FIPS - Federal Information Processing Standard. Hardware and software with which the state. structures must comply with FIPS.
')
According to colleagues we met at EuroCrypt 2019, FIPS certification is hell, to the point that FIPS experts come to you, launch your software in debug mode, change values ​​in memory and check if it falls down where it is intended.

Despite this, it is possible to get certified and become FIPS compliant. Therefore, there are many times more products and companies supplying services to the state than we do.

Ecdsa

Inside the usb token Yubico there is a storage for keys and an engine that implements, including ECDSA. Upon registration, the public key from the token is transmitted and saved to the server.

And when logging in, the server sends the client a random string, which he signs along with the meta information, such as, for example, a domain.

In a nutshell, how ECDSA or digital signature on elliptic curves works. Some details are omitted for simplicity:

1. We consider the hash of the message and translate it into a number. $$$e = HASH (m)$.
2. We generate a cryptographically stable random number k.
3. Calculate point $$$(x, y) = k * G$where G is the base point of the curve, called the generator (constant)
4. Calculate $$$r = x ~ mod ~ n$where n is the base point order (constant)
5. Calculate $$$s = k ^ {- 1} (e + r * d) \, \ bmod \, n$where d is the private key
6. A digital signature consists of a pair of numbers r, s

It is crucial that the number k is not only secret, but always different. Otherwise, it becomes possible to calculate the private key.

For example, we have two signatures (r, s) and (r1, s1), which are obtained for different messages m and m1, but using the same secret k. Let's calculate the private key.

• The attacker computes e and e1.
• Insofar as $$$s - s1 = k ^ {- 1} (e - e1)$, then you can learn k. $$$k = \ frac {e - e1} {s - s1}$
• Insofar as $$$s = k ^ {- 1} (e + r * d)$then one can calculate d. $$$d = \ frac {s * k - e} {r}$
• d - private key

If the numbers k are different, but not quite , then you can also calculate the private key, you just need to sort out a little. By the way, in 2013 I already wrote how the sloppy implemented (EC) DSA broke in PlayStation and other products, I highly recommend reading.

Yubico

So, in a number of Yubico FIPS products there was a bug in which the numbers k immediately after the token was turned on were not entirely random generated. And there was a real opportunity to calculate the private key sewn inside. Therefore, they withdrew the vulnerable devices and issued a notification.

What could be done?

Generally speaking, the problem has long been solved. Since 2013, there has been RFC 6979 , which describes deterministic ECDSA, derived from the usual way through several simple modifications. Moreover, in 2014, when developing the U2F standard, it was precisely because of the potential problems with the RNG that FIPS openly suggested switching to Deterministic ECDSA, but the proposal was rejected. This is one of the reasons why FIPS is decoded as F * cked-up, Insecure, Persnickety Standards.

Yubico could formally comply with the FIPS requirements for the randomness of the number k, but using workaround, generating k is deterministic, and then XOR-I with the fact that issued the RNG (or drove everything through KDF). However, this was not done.

And what about us?

And we have all the same. GOST R 34.10-2012 - essentially the same ECDSA, just with other curves. The requirements for generating the number k remain the same as in the traditional ECDSA. Does any of the manufacturers of our tokens make the above described workaround? Does it use a deterministic version of ECDSA? I doubt it.

If there are representatives of Russian developers, it would be interesting to hear their opinion on this. Or at least so they have it in mind.

Thanks for attention.