Category: primes

ROCA, TPM chips and Fast Primes

· Leave a comment ·

This issue affects IoT devices relying on TPMs for security. Especially those that are remote and hard to update using a firmware update.

ROCA: Return Of the Coppersmith Attack.

A ‘Fast Primes’ algo is used to generate primes, but since they are not uniformly distributed, one can use knowledge of the public keys to guess the private keys. Primality testing was discussed in this blog here.

From the full paper here:  Practical Factorization of Widely Used RSA Moduli

  • All RSA primes (as well as the moduli) generated by the RSALib have the following form: p=k∗M+(65537^a modM). Because of this the public key, p*q is of the form 65537^c mod M.
  • The integers k, a are unknown, and RSA primes differ only in their values of a and k for keys of the same size. The integer M is known and equal to some primorial M = Pn# (the product of the n successive primes) and is related to the size of the required key. The attack replaces this with a smaller M’ which still satisfies the above prime generation equation, enabling guessing of a.

  • Coppersmith algorithm based RSA attacks are typically used in scenarios where we know partial information about the private key (or message) and we want to compute the rest. The given problem is solved in the three steps:

    problem → f(x)≡0modp → g(x)=0 → x0

    p is an unknown prime and x0 is a small root of the equation. Code based on SageMath (python) – https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage

  • The LLL is a fascinating algorithm which ‘reduces’ a lattice basis b0, · · · ,bn−1. The algorithm computes an alternative basis b0 ′ , · · · , bn-1′ of the lattice which is smaller than the original basis. Coppersmith’s algorithm utilizes the LLL algorithm.

 

Discussion of Coppersmith attack in “Twenty Years of Attacks on the RSA Cryptosystem”.

A statement by Infineon is here. A discussion on this appeared on crypto.stackexchange.com at https://crypto.stackexchange.com/questions/52292/what-is-fast-prime .

The vulnerability affects HP, Lenovo and Fujitsu which OEM Infineon TPMs. It also affected Gemalto IDPrime smartcards which used the Infineon library.

Unrelated to this but a wifi attack appeared around the same time.