Attacks on Asymmetric Systems

In 2010, researchers discovered that millions of RSA keys generated by embedded devices (smart cards, routers, HSMs) shared prime factors. The attack: GCD of pairs of public moduli. If n1 = p*q and n2 = p*r (same p!), then GCD(n1, n2) = p instantly factors both. This is not a theoretical attack - it required only a database of public keys and modular GCD computation. Understanding RSA factoring makes attacks like these obvious.

• **Shared RSA primes (2012)**: 0.2% of 7 million RSA public keys had shared prime factors due to low-entropy random number generators in embedded devices. All such keys were instantly factored via GCD.
• **ROCA vulnerability (2017)**: Infineon TPMs generated RSA keys with special structure exploitable by Coppersmith. Estonian national ID cards, Microsoft Surface Pro, Lenovo ThinkPads all affected.
• **RSA Factoring Challenge**: RSA-768 factored 2009 using 2000 AMD core-years. RSA-1024 remains the next target, estimated at ~2^86 operations.
• **SageMath Coppersmith**: sage's `small_roots()` function implements Coppersmith. Used in CTF competitions to solve RSA challenges with small e and predictable padding in seconds.

Attacks on RSA

RSA security depends on the hardness of factoring n=p*q. Modern factoring uses the Number Field Sieve (NFS). A 768-bit RSA key was factored in 2009 (2^67 operations); 1024-bit is feasible for nation-state adversaries. Current recommendation: 2048+ bits.

Factoring is the central problem in RSA. Pollard's p-1 method works if p-1 has only small prime divisors: if every prime divisor of p-1 is at most B, factoring takes O(B log B) steps. Fermat's attack is effective when p and q are close: n = a^2 - b^2 = (a+b)(a-b). When p-q < n^{0.25}, factoring is straightforward.

ROBOT (Return Of Bleichenbacher's Oracle Threat) 2017: a rediscovery of the original attack. Researchers found the vulnerability in 7 key products including F5, Citrix, and Cisco. Facebook used a vulnerable certificate - an attacker could sign data on behalf of facebook.com. The only defense is OAEP instead of PKCS#1 v1.5, plus constant-time comparisons.

Pohlig-Hellman Algorithm

The Pohlig-Hellman algorithm (1978) solves DLP efficiently when the group order n is smooth (has only small prime factors). If n = p1^e1 * p2^e2 * ..., each component DLP is solved separately and combined via CRT. Complexity: O(sum sqrt(pi)) not O(sqrt(n)).

This is why Diffie-Hellman requires a prime-order subgroup. Parameters generated by OpenSSL, RFC 3526, and RFC 7919 use safe primes where (p-1)/2 is also prime, making the prime-order subgroup immune to Pohlig-Hellman.

Index Calculus Method

The index calculus method (subexponential DLP in Z_p) uses a factor base of small primes to build a discrete logarithm database, then expresses the target in terms of this base. It does not generalize to elliptic curves, which is why ECDLP has no subexponential attack.

The absence of index calculus for ECDLP is the mathematical reason why elliptic curves provide the same security as much larger RSA/DH parameters. A 256-bit ECC key is as hard to break as a 3072-bit RSA key.

Coppersmith Method and Lattice Attacks

Coppersmith's theorem (1996) finds small roots of polynomials mod n using the LLL lattice reduction algorithm. This enables RSA attacks when partial information about p, q, d, or the message M is available - even if the full value is unknown.

RSA challenges from Capture-the-Flag competitions often involve Coppersmith-style attacks: small e with insufficient padding, RSA with related messages, or partial key exposure from side-channel leakage. SageMath provides a direct Coppersmith implementation.

Key Ideas

• **NFS factoring**: subexponential complexity breaks RSA-768 (2009), threatens RSA-1024. Current minimum: RSA-2048 for 112-bit security.
• **Pohlig-Hellman**: DLP in smooth-order groups decomposed via CRT. Defense: prime-order subgroups (safe primes). Essential for DH security.
• **Index calculus**: subexponential DLP in Z_p. Does not generalize to ECC - this is why ECDLP has no subexponential attack.
• **Coppersmith/LLL**: finds small polynomial roots mod n. Breaks RSA with partial key exposure (>n^0.5 bits of p), small e with short padding, small d (Boneh-Durfee).

Related Topics

Asymmetric attacks connect number theory to practical cryptanalysis:

• RSA Mathematics — Key generation must avoid small prime factors, close primes, and small d to prevent these attacks.
• RSA in Practice — Wiener attack, small-e attacks, and OAEP padding requirements all connect to practical RSA deployment.
• Post-Quantum Cryptography — Shor algorithm provides quantum polynomial-time factoring and DLP, making all current asymmetric systems vulnerable.

Вопросы для размышления

• The ROCA vulnerability (2017) affected Infineon TPM-generated RSA keys. What specific mathematical property did these keys have that made them Coppersmith-vulnerable?
• If an attacker can collect all public RSA keys from a Certificate Transparency log, what computation would detect any with shared prime factors?
• Pohlig-Hellman reduces DLP complexity when n is smooth. For DH with a safe prime p=2q+1, what is the effective security against Pohlig-Hellman?

Связанные уроки

• nt-04
• nt-07