--- key: "icdp-case-roca-2017" title: "ROCA: structured RSA key generation" url: "https://softwaresecurity.com/domains/identity-crypto/key-management-pki/roca-infineon-weak-keys/" api: "https://softwaresecurity.com/api/v1/articles/icdp-case-roca-2017.json" domain: "identity-crypto" topic: "Identity \u0026 cryptography" type: "Case study" identifiers: ["CWE-1240","CWE-326","A04:2025","V11.6.1"] tags: ["Key management","PKI and certificates","Firmware and hardware security"] stages: ["operate"] roles: ["developer"] license: "CC-BY-4.0" license_url: "https://creativecommons.org/licenses/by/4.0/" code_license: "MIT" --- # ROCA: structured RSA key generation Understand why mathematically structured RSA primes were factorable despite normal key lengths, then plan replacement around generation provenance. Canonical URL: https://softwaresecurity.com/domains/identity-crypto/key-management-pki/roca-infineon-weak-keys/ ## In short ROCA (CVE-2017-15361) made RSA keys generated by an Infineon library in TPMs, smart cards and security tokens factorable from the public key alone. Check every RSA public key you rely on with the researchers’ `roca-detect` tool, update the firmware, then generate and enroll new keys: a firmware update fixes future keys, not existing ones. Record where and how each hardware key was generated. - The weakness is in how primes were generated, so it is visible in the public key. - Hardware protection against key extraction does not help when the key can be computed. - A positive detector result means the known structure is present; a negative result covers only that structure. - Firmware updates fix future generation; existing keys must be regenerated and re-enrolled. - Separate signing, authentication and decryption uses before retiring an affected key. ## Incident at a glance - Date: 2017-10-16 - Category: Cryptographic weakness - Organizations: Infineon Technologies; Microsoft; Google; HP; Lenovo; Fujitsu - CVE: [CVE-2017-15361](https://nvd.nist.gov/vuln/detail/cve-2017-15361) - Impact: RSA keys generated by Infineon’s library on TPMs, smart cards and tokens made since at least 2012 could be factored from the public key: at worst about 97 CPU-days for 1024-bit and 141 CPU-years for 2048-bit keys. The researchers found about 760,000 vulnerable keys. - How it was found: Researchers at Masaryk University’s CRoCS lab, Enigma Bridge and Ca’ Foscari University noticed the structure while analyzing large numbers of RSA keys generated on smart cards. ### Timeline 1. 2012: Chips with the affected key-generation library are in use from at least this year. 2. 2017-02-01: The researchers disclose the vulnerability to Infineon, agreeing an eight-month embargo. 3. 2017-10-10: Microsoft, Google and other vendors publish TPM security advisories and updates. 4. 2017-10-16: ROCA is publicly disclosed with offline and online key detectors. 5. 2017-10-30: The full paper is made public. 6. 2017-11-02: ROCA is presented at ACM CCS 2017. ## Verify it 1. Run `roca-detect` on every RSA public key in scope and keep the tool version and result per fingerprint. 2. Confirm each replacement key has a new public-key fingerprint and passes the detector. 3. Confirm the old key is rejected for authentication after the cutoff. 4. Restore a representative archive with the new key path before destroying the old decryption key. ## What you will learn - Explain structured generation as distinct from short keys or shared primes. - Use public-key detection evidence within its scope. - Sequence credential and encrypted-data migration. Audience: Engineers who use TPMs, smart cards or security keys to generate RSA keys, and responders who replace affected keys. Before you start: - Distinguish key length from the entropy and structure of generated primes. Time: About 17 minutes: 4 to read and 13 for the exercise ## An optimization restricted the primes a generator could produce ROCA, publicly disclosed in October 2017, affected RSA key generation in an Infineon cryptographic library used by multiple hardware products. The affected generator produced primes with a special mathematical structure. Researchers used that structure to make factorization feasible for affected key sizes, including some 2048-bit keys under the published cost analysis. Conceptually, the primes were drawn from a restricted family involving powers of a fixed generator modulo a product of small primes. Their residues left a recognizable structure in the public modulus. That structure narrowed the search in a way generic RSA factorization does not assume. The complete attack used lattice-based techniques related to Coppersmith’s method; a simple divisibility test is not the factorization algorithm. A public-key fingerprinting test can detect characteristic residues without access to the private key. This is why inventory and triage could operate on public certificates or keys. A positive detector result is evidence of the generator’s known structure; it is not a transcript proving that an attacker already recovered a particular private key. ## Key generation is the affected operation The relevant question is where and how a key was generated. Importing a properly generated external RSA key into an affected device is a different case from generating the key using the vulnerable library. Conversely, exporting a certificate to another host does not remove the weakness from a key originally generated by the affected process. ROCA differs from two moduli accidentally sharing a prime because of poor randomness. A shared-prime gcd scan, like the fleet check in the weak RSA key guide at /domains/identity-crypto/key-management-pki/weak-rsa-key-generation/, can find one family of failures while missing ROCA’s restricted prime structure. A ROCA detector likewise does not certify all aspects of RSA quality. Hardware protection from key extraction does not solve a mathematical weakness visible from the public modulus. The researchers’ disclosure and factorization-cost estimates are historical evidence scoped to tested key structures and sizes. Do not translate one reported cost into a universal price for every RSA key. Product names alone are also weaker evidence than key provenance plus the detector output. ## Patch first, generate again, then replace trust A firmware or library update can fix future generation, but an already generated vulnerable key remains mathematically vulnerable. Generate replacement keys with a corrected or independent trusted process, issue replacement certificates or credentials, deploy them, and retire the old trust bindings. Renewing a certificate while retaining the same modulus preserves the weakness. Replacement has a dependency graph: identity systems may bind devices to public keys, disk or document encryption may depend on decryption keys, and signed artifacts may need historical validation. Decide which old keys must remain available solely for controlled data recovery and which credentials must stop authenticating immediately. A successful rollout requires both continuity and rejection. If the new certificate works but every verifier continues trusting the old credential, impersonation risk persists. If the old decryption key is destroyed before data migration, the response can cause data loss. Separate signing, authentication, and decryption uses before setting retirement dates. ## What should you do today? - Run `roca-detect` (installed with `pip install roca-detect`) over the certificates, SSH public keys and PGP keys you trust; it reads public keys only. - For any positive result, update the device firmware, generate a new key on the patched device or elsewhere, re-enroll it, and revoke the old one. - Decrypt and re-encrypt data protected by an affected decryption key before retiring it. - For new hardware-backed keys, record the device model, firmware version and generation date in your cryptographic inventory (/domains/identity-crypto/key-management-pki/crypto-inventory-pqc/), and prefer elliptic-curve keys where supported. ## A detector is a scoped test, not a warranty Record the public-key fingerprint, generation source, detector version, and result for each candidate. Verify new fingerprints differ, new credentials work, and retired credentials fail where policy requires. For data migration, restore a representative old backup using the documented recovery path before deleting keys. The exercise uses supplied detector results rather than a counterfeit miniature ROCA test. The learner practices scope and lifecycle reasoning; a few small residues cannot reproduce the published factorization research. ## Guided practice Three credentials are found during a ROCA response. Use provenance and detector results to decide what changes. ### Supplied material ```text A: generated by affected firmware; detector positive; certificate serial 10; public-key fingerprint K1. B: independently generated then imported; detector negative; fingerprint K2. C: replacement certificate serial 11; fingerprint K1. Firmware is now patched. A also decrypts an archived payroll export. ``` ### 1. Scope the mathematical weakness Decide whether patching firmware repairs A and whether C is a new key. Worked answer: Patching changes future generation; A’s modulus is unchanged. C is a new certificate around the same K1 key, so it preserves the weakness. ### 2. Respect detector limits State the conclusion justified for B. Worked answer: The supplied detector did not find its targeted structure, and provenance differs. This does not prove B lacks every possible generation or implementation weakness. ### 3. Sequence retirement Place new generation, reissuance, consumer rollout, archive migration, and key retirement in a safe order. Worked answer: Generate K3 with a corrected process, verify it, issue and deploy credentials, update consumers, migrate or recover archives, then retire K1 according to its separate authentication and decryption uses. New authentication succeeds and K1 authentication fails after cutoff. Deliverable: A credential disposition table and a sequence that prevents both continued impersonation and accidental data loss. Scope: The detector results are supplied. No ROCA detector, factorization, private-key extraction, or live hardware operation is performed. Articles and teaching material: CC BY 4.0. Original executable code: MIT. Attribution: Software Security. ## Sources - [Masaryk University CRoCS: ROCA research disclosure](https://crocs.fi.muni.cz/public/papers/rsa_ccs17). 16 October 2017. - [CERT/CC VU#307015: Infineon RSA key generation vulnerability](https://kb.cert.org/vuls/id/307015) - [NVD: CVE-2017-15361](https://nvd.nist.gov/vuln/detail/cve-2017-15361) - [CRoCS: ROCA detection tool (roca-detect)](https://github.com/crocs-muni/roca)