View source for ROCA vulnerability

{{short description|Cryptographic valunerability}}
{{Infobox bug
| name = ROCA vulnerability
| image = 
| caption = 
| CVE = {{CVE|2017-15361}}
| discovered = {{Start date and age|February 2017}}
| patched =
| discoverer =  Matúš Nemec, Marek Sýs, et al. ([[Organization:Masaryk University|Masaryk University]])
| affected hardware = [[Software:Trusted Platform Module|TPM]], Yubikey, Gemalto IDPrime .NET [[Smart card|smart card]]s
| affected software = Any public-private key encryption that used RSALib including [[Software:BitLocker|BitLocker]] and [[Software:Pretty Good Privacy|PGP]]
| website =
}}

The '''ROCA vulnerability''' is a [[Cryptography|cryptographic]] weakness that allows the [[Public-key cryptography|
private key]] of a key pair to be recovered from the [[Public-key cryptography|public key]] in keys generated by devices with the vulnerability. "ROCA" is an acronym for "Return of [[Coppersmith's attack]]".<ref name=Goodin2017>{{Cite news|url=https://arstechnica.com/information-technology/2017/10/crippling-crypto-weakness-opens-millions-of-smartcards-to-cloning/|title=Crippling crypto weakness opens millions of smartcards to cloning|work=Ars Technica|access-date=2017-10-25|language=en-us|first=Dan|last=Goodin|date=2017-10-23}}</ref> The vulnerability has been given the identifier {{CVE|2017-15361}}.

The vulnerability arises from a problem with an approach to [[RSA (cryptosystem)|RSA]] [[Social:Key generation|key generation]] used in vulnerable versions of a [[Library (computing)|software library]], ''RSALib'', provided by [[Company:Infineon Technologies|Infineon Technologies]], and incorporated into many [[Smart card|smart card]]s, [[Software:Trusted Platform Module|Trusted Platform Module]] (TPM), and Hardware Security Modules (HSM) implementations, including [[Company:YubiKey|YubiKey]] 4 tokens, often used to generate [[Software:Pretty Good Privacy|PGP]] keys. Keys of lengths 512, 1024, and 2048 bits generated using these versions of the Infineon library are vulnerable to a practical ROCA attack.<ref name=nemecsys /><ref name=thehackernews>{{Cite news |url=https://thehackernews.com/2017/10/rsa-encryption-keys.html |title=Serious Crypto-Flaw Lets Hackers Recover Private RSA Keys Used in Billions of Devices |last=Khandelwal |first=Swati |work=The Hacker News |access-date=2017-10-25}}</ref> The research team that discovered the attack (all with [[Organization:Masaryk University|Masaryk University]] and led by Matúš Nemec and Marek Sýs)<ref name=nemecsys />  estimate that it affected around one-quarter of all current TPM devices globally.<ref>{{Cite news |location=United Kingdom |url=https://www.theregister.co.uk/2017/10/16/roca_crypto_vuln_infineon_chips/ |title=Never mind the WPA2 drama... Details emerge of TPM key cockup that hits tonnes of devices |publisher=The Register |access-date=2017-10-25 |first=John |last=Leyden |date=16 October 2017}}</ref> Millions of [[Smart card|smart card]]s are believed to be affected.<ref name="Goodin2017" />

The team informed Infineon of the ''RSALib'' problem in February 2017, but withheld public notice until mid-October, citing [[Responsible disclosure|responsible disclosure]]. At that time they announced the attack and provided a tool to test public keys for vulnerability. They published the details of the attack in November.<ref name=nemecsys />

==Technical details==
Generating an RSA key involves selecting two large [[Random number generation|randomly-generated]] [[Prime number|prime number]]s, 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 testing for primality numbers of the form:

:<math>k * M + (65537^a \mod{M})</math>

where <math>M</math> 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 <math>k</math> and <math>a</math>. 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|discrete logarithm]] of the public key mod <math>M</math> 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 <math>M</math> is a [[Smooth number|smooth number]]. A test site is available on the Internet.<ref name=nemecsys>{{cite conference| url=https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf|title=The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli|first1=Matus|last1=Nemec|first2=Marek|last2=Sys|first3=Petr|last3=Svenda|first4=Dusan|last4=Klinec|first5=Vashek|last5=Matyas|date=November 2017|doi=10.1145/3133956.3133969|book-title=Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security|series=CCS '17}}</ref><ref>{{Cite web |url= https://www.ncsc.gov.uk/guidance/roca-infineon-tpm-and-secure-element-rsa-vulnerability-guidance |title=ROCA: Infineon TPM and Secure Element RSA Vulnerability Guidance |website=www.ncsc.gov.uk |location=United Kingdom |access-date=2017-10-25}}</ref><ref>{{Cite web |title=ROCA: Vulnerable RSA generation (CVE-2017-15361) |publisher=Centre for Research on Cryptography and Security, Faculty of Informatics, [[Organization:Masaryk University|Masaryk University]] |location=Czech Republic |url=https://crocs.fi.muni.cz/public/papers/rsa_ccs17 |access-date=2017-10-25}}</ref><ref>{{Cite web |url=https://www.infineon.com/cms/en/product/promopages/rsa-update/ |title=Information on software update of RSA key generation function |publisher=Infineon Technologies AG |access-date=2017-10-25}}</ref>  In short, keys that fit this format have significantly low 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.<ref>{{Cite web |url=https://github.com/brunoproduit/roca |title=Implementation of the ROCA attack (CVE-2017-15361) |author=Bruno Produit |website=[[GitHub]] |date=2019-05-15 |access-date=2020-06-29}}</ref><ref>{{Cite web |url=https://github.com/FlorianPicca/ROCA |title=ROCA |author=Florian Picca |website=[[GitHub]] |date=2020-05-03 |access-date=2020-06-29}}</ref><ref>{{Cite web |url=https://github.com/elliptic-shiho/crypto_misc/blob/master/small_root/roca_attack.sage |title=ROCA |date=2020-04-13 |author=Shiho Midorikawa |website=[[GitHub]] |access-date=2020-06-29}}</ref>

==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 [[Software:OpenSSL|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.<ref name=nemecsys />{{rp|Sec 5.1}}

Infineon has released firmware updates for its [[Software:Trusted Platform Module|Trusted Platform Module]]s to manufacturers who have used its TPMs.<ref>{{Cite web | url = https://www.infineon.com/cms/en/product/promopages/tpm-update/ | title = "TPM Update - Infineon Technologies" | access-date = March 19, 2021}}</ref>

== Implications ==
The vulnerability highlighted several [[Common Criteria#Criticisms|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.{{r|parsovs_phd|p=Sec 6.7.5}}

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.<ref name=parsovs_phd>{{cite thesis|type=PhD|first=Arnis|last=Parsovs|date=March 2021|title=Estonian Electronic Identity Card and its Security Challenges|publisher=University of Tartu|url=https://dspace.ut.ee/handle/10062/71481}}</ref>{{rp|Sec 6.7}}

==See also==
* {{Section link|BitLocker|Security concerns}}
* {{Section link|Infineon Technologies|Security flaw}}
* [[Software:Trusted Platform Module|Trusted Platform Module]]

== References ==
{{reflist}}

==External links==
*[https://github.com/crocs-muni/roca ROCA detection tool (Detection source code)]
*[https://keychest.net/roca ROCA Vulnerability Test Suite (Online tool for testing keys, files, GitHub accounts, GnuPG keys, and includes an S/MIME and PGP email responder)]
*[https://monitor.certipath.com/rsatest/ TrustMonitor ROCA Vulnerability Test (Online tool for testing multiple certificates)]
*[https://github.com/iadgov/Detect-CVE-2017-15361-TPM Detect Trusted Platform Modules Vulnerable to CVE-2017-15361 (Scripts)]

{{Hacking in the 2010s}}

[[Category:Cryptographic attacks]]

{{Sourceattribution|ROCA vulnerability}}