In the States, GOSTs are also so-so. YubiKey FIPS fatal vulnerability that could have been avoided

Hi% username%!

On June 13, 2019, Yubico, a manufacturer of two-factor authentication devices, issued a security notice stating 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 GOSTs, called FIPS - Federal Information Processing Standard. Hardware and software with which the state. structures required to comply with FIPS.

According to the colleagues we met at EuroCrypt 2019, FIPS certification is a hell of a thing, to the point that FIPS experts come to you, launch your software in debug mode, change the values ​​in memory and check if it falls where it is intended.

Despite this, getting certified and becoming FIPS compliant is real. Therefore, the products and companies that provide services to the state, there are many times more than ours.

ECDSA

Inside the usb token of Yubico there is a storage for keys and an engine that implements including ECDSA. During registration, the public key from the token is transferred to the server and stored.

And at login, the server sends a random string to the client, which it signs along with the meta-information, such as, for example, a domain.

In a nutshell about how ECDSA or the digital signature on elliptic curves works. Some details are omitted for ease of presentation:

1. We consider the hash from the message and translate it into a number. $$.
2. We generate a cryptographically strong random number k.
3. Calculate point $$ where G is the base point of the curve called the generator (constant)
4. We calculate $$where n is the order of the base point (constant)
5. We calculate $$where d is the private key
6. The digital signature consists of a pair of numbers r, s

It is critical 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 were received for different messages m and m1, but using the same secret k. Let's calculate the private key.

• The attacker calculates e and e1.
• Because the $$then we can find out k. $$
• Because the $$, then we can calculate d. $$
• d - private key

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

Yubico

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

What could be done?

Generally speaking, the problem has long been resolved. Since 2013, there is RFC 6979 , which describes a deterministic ECDSA obtained from the usual one through several simple modifications. Moreover, in 2014, when developing the U2F standard, it was precisely because of potential problems with the RPS that FIPS openly proposed switching to Deterministic ECDSA, but the offer was rejected. This is one of the reasons FIPS stands for F * cked-up, Insecure, Persnickety Standards.

Yubico could formally meet the FIPS requirements for the randomness of the number k, but use workaround, generating k deterministically, and then XOR it with the fact that it issued an RNG (or by running everything through KDF). However, this has not been done.

What about us?

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

If there are representatives of Russian developers, it would be interesting to listen to their opinion on this matter. Or at least to keep that in mind.

Thanks for attention.