 Coppersmith's Attack

Coppersmith's attack describes a class of attacks on the publickey cryptosystem RSA based on Coppersmith's theorem (see below). The public key in the RSA system is a tuple of integers (N,e), where N is the product of two primes p and q. The secret key is given by an integer d satisfying ; equivalently, the secret key may be given by and if the Chinese remainder theorem is used to improve the speed of decryption, see CRTRSA. Encryption of a message M produces the ciphertext which can be decrypted using d by computing .
Coppersmith's theorem has many applications in attacking RSA specifically if the public exponent e is small or if partial knowledge of the secret key is available.
Contents
Low Public Exponent Attack
In order to reduce encryption or signatureverification time, it is useful to use a small public exponent (e). In practice, common choices for e are 3, 17 and 65537 (2^{16} + 1).^{[1]} These values for e are Fermat primes, sometimes referred to as F_{0},F_{2} and F_{4} respectively . They are chosen because they make the modular exponentiation operation faster. Also, having chosen such e, it is simpler to test whether gcd(e,p − 1) = 1 and gcd(e,q − 1) = 1 while generating and testing the primes in step 1 of the key generation. Values of p or q that fail this test can be rejected there and then. (Even better: if e is prime and greater than 2 then the test can replace the more expensive test gcd(p − 1,e) = 1.
If the public exponent is small and the plaintext m is very short, then the RSA function may be easy to invert which makes certain attacks possible. Padding schemes ensure that messages have full lengths but additionally choosing public exponent e = 2^{16} + 1 is recommended. When this value is used, signatureverification requires 17 multiplications, as opposed to roughly 1000 when a random e of the same size is used. Unlike low private exponent (see Wiener's Attack), attacks that apply when a small e is used are far from a total break which would recover the secret key d. The most powerful attacks on low public exponent RSA are based on the following theorem which is due to Don Coppersmith.Theorem 1 (Coppersmith)^{[2]}
 Let N be an integer and be a monic polynomial of degree d over the integers. Set for . Then, given attacker, Eve, can efficiently find all integers x_{0} < X satisfying . The running time is dominated by the time it takes to run the LLL algorithm on a lattice of dimension O(w) with .
This theorem states the existence of an algorithm which can efficiently find all roots of f modulo N that are smaller than . As X gets smaller, the algorithm's runtime will decrease. This theorem's strength is the ability to find all small roots of polynomials modulo a composite N.
Håstad's Broadcast Attack
The simplest form of Håstad's attack is presented to ease understanding. The general case uses Coppersmith's theorem.
How does it work?^{[3]}
Suppose one sender sends the same message M in encrypted form to a number of people , each using the same small public exponent e, say e = 3, and different moduli . A simple argument shows that as soon as ciphertexts are known, the message M is no longer secure: Suppose Eve intercepts C_{1},C_{2}, and C_{3}, where . We may assume gcd(N_{i},N_{j}) = 1 for all i,j (otherwise, it is possible to compute a factor of one of the N_{i}’s by computing gcd(N_{i},N_{j}).) By the Chinese Remainder Theorem, she may compute such that . Then ; however, since M < N_{i} for all i', we have M^{3} < N_{1}N_{2}N_{3}. Thus C = M^{3} holds over the integers, and Eve can compute the cube root of C to obtain M.
For larger values of e more ciphertexts are needed, particularly, e ciphertexts are sufficient.
Generalizations
Håstad also showed that applying a linearpadding to M prior to encryption does not protect against this attack. Assume the attacker learns that C_{i} = f_{i}(M)^{e} for and some linear function f_{i}, i.e., Bob applies a pad to the message M prior to encrypting it so that the recipients receive slightly different messages. For instance, if M is m bits long, Bob might encrypt M_{i} = i2^{m} + M and send this to the ith recipient.
If a large enough group of people is involved, the attacker can recover the plaintext M_{i} from all the ciphertext with similar methods. In more generality, Håstad proved that a system of univariate equations modulo relatively prime composites, such as applying any fixed polynomial g_{1}(M) = 0 mod N_{i}, could be solved if sufficiently many equations are provided. This attack suggests that randomized padding should be used in RSA encryption.
Theorem 2 (Håstad)
 Suppose are relatively prime integers and set N_{min} = min_{i}{N_{i}}. Let be k polynomials of maximum degree q. Suppose there exists a unique M < N_{min} satisfying g_{i}(M) = 0(mod N_{i}) for all . Furthermore suppose k > q. There is an efficient algorithm which, given for all i, computes M.
Proof:
Since the N_{i} are relatively prime the Chinese Remainder Theorem might be used to compute coefficients T_{i} satisfying and for all . Setting we know that . Since the T_{i} are nonzero we have that is also nonzero. The degree of is at most q. By Coppersmith’s Theorem, we may compute all integer roots x_{0} satisfying and . However, we know that , so M is among the roots found by Coppersmith's theorem.This theorem can be applied to the problem of broadcast RSA in the following manner: Suppose the ith plaintext is padded with a polynomial , so that . Then the polynomials satisfy that relation. The attack succceeds once . The original result used the Håstad method instead of the full Coppersmith method. Its result was required k = O(q^{2}) messages, where q = max_{i}(e_{i}.deg f_{i}).^{[3]}
FranklinReiter Related Message Attack
FranklinReiter identified a new attack against RSA with public exponent e = 3. If two messages differ only by a known fixed difference between the two messages and are RSA encrypted under the same RSA modulus N, then it is possible to recover both of them.
How does it work?
Let be Alice's public key. Suppose are two distinct messages satisfying for some publicly known polynomial . To send M_{1} and M_{2} to Alice, Bob may naively encrypt the messages and transmit the resulting ciphertexts C_{1};C_{2}. Eve can easily recover M_{1};M_{2} given C_{1};C_{2}, by using the following theorem:
Theorem 3 (FranklinReiter)
 Set e = 3 and let be an RSA public key. Let satisfy for some linear polynomial with . Then, given , attacker, Eve, can recover M_{1},M_{2} in time quadratic in log _{2}N.
For an arbitrary e (rather than restricting to e = 3) the time required is quadratic in e and log _{2}N).
Proof:
Since , we know that M_{2} is a root of the polynomial . Similarly, M_{2} is a root of . The linear factor x − M_{2} divides both polynomials. Therefore, Eve calculates the greatest common divisor (gcd) of g_{1} and g_{2}, if the gcd turns out to be linear, M_{2} is found. The gcd can be computed in quadratic time in e and log _{2}N using the Euclidean algorithm.Coppersmith’s Short Pad Attack
Like Håstad’s and FranklinReiter’s attack, this attack exploits a weakness of RSA with public exponent e = 3. Coppersmith showed that if randomized padding suggested by Håstad is used improperly then RSA encryption is not secure.
How does it work?
Suppose Bob sends a message M to Alice using a small random padding before encrypting it. An attacker, Eve, intercepts the ciphertext and prevents it from reaching its destination. Bob decides to resend M to Alice because Alice did not respond to his message. He randomly pads M again and transmits the resulting ciphertext. Eve now has two ciphertexts corresponding to two encryptions of the same message using two different random pads.
Even though Eve does not know the random pad being used, she still can recover the message M by using the following theorem, if the random padding is too short.
Theorem 4 (Coppersmith)
 Let be a public RSA key where N is nbits long. Set . Let be a message of length at most n − m bits. Define M_{1} = 2^{m}M + r_{1} and M_{2} = 2^{m}M + r_{2}, where r_{1} and r_{2} are distinct integers with . If Marvin is given and the encryptions C_{1},C_{2} of M_{1},M_{2} (but is not given r_{1} or r_{2}, he can efficiently recover M.
Proof^{[2]}
Define g_{1}(x,y) = x^{e} − C_{1} and g_{2}(x,y) = x^{e} − C_{2}. We know that when y = r_{2} − r_{1}, these polynomials have x = M_{1} as a common root. In other words, is a root of the resultant . Furthermore, . Hence, is a small root of h modulo N, and Marvin can efficiently find it using Theorem 1 (Coppersmith). Once is known, the FranklinReiter attack can be used to recover M_{2} and consequently M.References
Categories:
Wikimedia Foundation. 2010.