December 2, 2017 11:49 am
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
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.
It caused an identity card related re-keying in Estonia which relied on Gemalto/Infineon. The re-keying used ECC.
Unrelated to this but a wifi attack appeared around the same time.
Posted by Ruchir Tewari
Categories: crypto, primes, tpm, vulnerability
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.