ROCA vulnerability

Generating an RSA key involves selecting two large randomly-generated prime numbers, a process that can be time-consuming, particularly on small devices, such as smart cards. In addition to being primes, the numbers should have certain other properties for best security. The vulnerable RSALib selection process quickly creates primes of the desired type by only considering numbers of the form k \times M + (65537^a \bmod M), where M is the product of the first n successive primes (2, 3, 5, 7, 11, 13, ...), and n is a constant that only depends on the desired key size. The security is based on the secret constants k and a. The ROCA attack exploits this particular format for primes using a variation of the Coppersmith method. In addition, public keys generated this way have a distinctive fingerprint that can be quickly recognized by attempting to compute the discrete logarithm of the public key mod M to base 65537. Computing discrete logarithms in a large group is usually extremely difficult, but in this case it can be done efficiently using the Pohlig–Hellman algorithm because M is a smooth number. A test site is available on the Internet. In short, keys that fit this format have significantly lower entropy and can be attacked relatively efficiently (weeks to months), and the format can be confirmed ("fingerprinted") by the attacker very quickly (microseconds). Multiple implementations of the attack are publicly available. ==Mitigation==

The ROCA authors consider public keys of length 512, 1024 and 2048-bits generated by RSALib to be vulnerable. Because the details of key generation differ for different key lengths, shorter keys are not necessarily more vulnerable than longer keys. For example, a 1952-bit RSAlib key is stronger than a 2048-bit key and a 4096-bit key is weaker than a 3072-bit key. The best mitigation, according to the authors, is to generate RSA keys using a stronger method, such as by OpenSSL. If that is not possible, the ROCA authors suggest using key lengths that are less susceptible to ROCA such as 3936-bit, 3072-bit or, if there is a 2048-bit key size maximum, 1952-bits. == Implications ==

The vulnerability highlighted several shortcomings of the Common Criteria certification scheme as the vulnerability was present in a list of Common Criteria certified smart card products. Namely, the approval of homegrown cryptographic algorithms; the lack of transparency in certification reports, inability to revoke Common Criteria certificates for known vulnerable products and distribute this information to the users of the certified products. In Estonia, the discovery of the vulnerability resulted in a state-level cyber crisis as the vulnerable smart card chip was deployed on more than 750,000 Estonian identity cards that are used daily by Estonian residents and e-residents to securely authenticate online and create digital signatures. ==See also==