RSA Attacks

Introduction

Invented

by Ron Rivest, Adi Shamir, and Len Adleman, the RSA cryptosystem was first revealed

in the August 1977 issue of Scientific American. The RSA is most commonly used

for providing privacy and ensuring authenticity of digital data. RSA is used by

many commercial systems. It is used to secure web traffic, to ensure privacy and

authenticity of Email, to secure remote login sessions, and it is at the heart

of electronic credit-card payment systems.

Since

its initial release, the RSA has been analyzed for vulnerabilities. Twenty

years of research have led to a number of intriguing attacks, none of them is

devastating. They mostly show the danger of wrong use of RSA. RSA encryption in

its simple form is explained as follow.

Let,

N = p*q be the product of two large primes of the same size (n/2 bits

each). A typical size for N is n=1024

bits, i.e.309 decimal digits.

Let

e, d be two integers satisfying

e*d

= 1 mod ? (N)

Where,

? (N) = (p-1) (q-1).

N = RSA modulus,

e = encryption exponent, and

d = called the decryption exponent.

The

pair (N, e) is the public key. The pair (N, d) is called the secret key and

only the recipient of an encrypted message knows it.

A

message M is encrypted by computing,

C =

Memod N.

To

decrypt the ciphertext C, the authentic receiver computes

Cdmod N.Cd = Med = M

(mod N)

The

last equality is based on Euler’s theorem.

Factoring Large Integers

This

is known as the first attack on RSA public key (N, e). After getting the

factorization of N, an attacker can easily construct ? (N), from which the

decryption exponent d = e-1mod? (N) can be found. Factoring the modulus is

referred to as brute-force attack. Although factorizing the modulus has been

improving, the current state of the art of this attack is unable to post a

threat to the security of RSA when RSA is used properly.

At

the moment RSA seems to be extremely secure. It has survived over 20 years of

scrutiny and is in widespread use throughout the world. The attack that is most

often considered for RSA is the factoring of the public key. If this can be

achieved, all messages written with the public key can be decrypted. The point

is that with very large numbers, factoring takes an unreasonable amount of time.

It has not been proven that breaking the RSA algorithm is equivalent to

factoring large numbers (there may be another, easier method), but neither has

it been proven that factoring is not equivalent.

Searching

the Message Space

One

of the seeming weaknesses of public key cryptography is that one has to give

away to everybody the algorithm that encrypts the data. If the message space is

small, then one could simply try to encrypt every possible message block, until

a match is found with one of the ciphertext blocks. In practice this would be

an insurmountable task because the block sizes are quite large.

Guessing d

Another

possible attack is a known ciphertext attack. This time the attacker knows both

the plaintext and ciphertext (they simply has to encrypt something). They then

try to crack the key to discover the private exponent, d. This might

involve trying every possible key in the system on the ciphertext until it returns

to the original plaintext. Once d has been discovered it is easy to find

the factors of n. Then the system has been broken completely and all

further ciphertexts can be decrypted.

The

problem with this attack is that it is slow. There are an enormous number of

possible ds to try. This method is a factorizing algorithm as it allows

us to factor n. Since factorizing is an intractable problem we know this

is very difficult. This method is not the fastest way to factorize n.

Therefore one is suggested to focus effort into using a more efficient

algorithm specifically designed to factor n.

Cycle Attack

This

attack is very similar to the last. The idea is to encrypt the ciphertext

repeatedly, counting the iterations, until the original text appears. This

number of re-cycles will decrypt any ciphertext. Again this method is very slow

and for a large key it is not a practical attack. A generalization of the

attack allows the modulus to be factored and it works faster the majority of

the time. But even this will still have difficulty when a large key is used.

Improvement

in algorithm is to use the public exponent of the public key to re-encrypt the

text. However any exponent should work so long as it is coprime to (p-1).(q-1)

(where p, q are factors of the modulus). So using an exponent such as 216

+ 1. This number has only two 1s in its binary representation. Using binary

fast exponentiation, we use only 16 modular squarings and 1 modular

multiplication. This is likely to be faster than the actual public exponent.

The trouble is that we cannot be sure that it is coprime to (p-1).(q-1).

In practice, many RSA systems use 216 + 1 as the encrypting exponent

for its speed.

In

the cycle attack, the encrypting exponent could be chosen to make

the system more efficient. Many RSA systems use e=3 to make encrypting

faster. However, there is a vulnerability with this attack. If the same message

is encrypted 3 times with different keys (that is same exponent, different

moduli) then we can retrieve the message. The attack is based on the Chinese

Remainder Theorem.

Common Modulus

The

assumption that generating the same modulus N = p*q for all users of a system,

and user is provided with a unique pair (ei, di) from which user I forms a

public key (N, ei) and a secret key (N, di) may seem to work providing that a

trusted central authority provides the unique pairs.

One

of the early weaknesses found was in a system of RSA where the users within an

organization would share the public modulus. That is to say, the administration

would choose the public modulus securely and generate pairs of encryption and

decryption exponents (public and private keys) and distribute them all the

employees/users. The reason for doing this is to make it convenient to manage

and to write software for. But, the resulting system is insecure since Bob who

is unable to decipher Alice’s cipher due to not having Alice private key d Alice

he however, can factor N using his own exponents.

With

blinding eavesdrop obtain a valid

signature on a message of his choice by asking user to sign a random

“blinded message”. In that case, user 1 does not know what message is

actually signing and most signature schemes apply a “one-way hash” to

the message prior to signing, thus the attack is not a serious concern. Let (N,

d) be user 1’s private key and (N, e) be

public key. Assume that an adversary wants user 1’s signature on a message M ? Z*N. Being a smart move,

user 2 should refuse to sign M. Otherwise eavesdrop can compute S = S’ / ? mod

N and obtains user 1’s signature S on the original M.

Thus,

Se =

(S’)e/ ?e= (M’)ed / ?e ? M’ / ?e= M (mod N)

Faulty Encryption

Consider

the situation where an attacker, Malory, has access to the communication

channel used by Alice and Bob. In other words, Malory can listen to anything

that is transmitted, and can also change what is transmitted. Alice wishes to

talk privately to Bob, but does not know his public key. She requests by

sending an email, to which Bob replies. But during transmission, Malory is able

to see the public key and decides to flip a single bit in the public exponent

of Bob, changing (e,n) to (e’,n). When Alice receives the faulty key, she encrypts

the prepared message and sends it to Bob (Malory also gets it). But of course,

Bob cannot decrypt it because the wrong key was used. So he lets Alice know and

they agree to try again, starting with Bob re-sending his public key. This time

Malory does not interfere. Alice sends the message again, this time encrypted

with the correct public key.

Malory

now has two ciphertexts, one encrypted with the faulty exponent and one with

the correct one. She also knows both these exponents and the public modulus.

Therefore she can now apply the common modulus attack to retrieve Alice’s

message, assuming that Alice was foolish enough to encrypt exactly the same

message the second time.

4.1Coppersmith

theorem

The

most powerful attacks on low public exponent RSA are based on a Copper-smith

theorem.

The

theorem provides an algorithm for efficiently finding all roots of f modulo N that are less than X = N1/d.

The algorithm’s running time decreases as X gets smaller. The strength of this theorem

is its ability to find small roots of polynomials modulo a composite N.

Application

of Coppersmith’s Theorem:

·

Attack

stereotyped messages in RSA (sending messages whose difference is less than N1/e

can compromise RSA)

·

Security

proof of RSA-OAEP (constructive security proof).

·

Affine

Padding

·

Polynomially

related RSA messages (sending the same message to multiple recipients)

·

Factoring

N = p*q if the high bits of pare known.

·

An

algorithm that can get the private key for RSA in deterministic polynomial time

can be used to factor N in deterministic polynomial time.

·

Finding

integers with a large smooth factoring a proscribed interval.·Finding roots of modular multivariate polynomials.

4.2

Hastad’s broadcast attack

The

first application of Coppersmith’s theorem and the improvement to an old attack

is Hastad’s Broadcast Attack.

Suppose,

Bob wishes to send an encrypted message M to a number of parties P1, P2,……Pk.

Each party has its own RSA key (Ni, ei). We assume M is less than all the Ni’s.

Idealistically, to send M, Bob encrypts it using each of the public keys and

sends out of the ith ciphertext to pi. An attacker Eve can

eavesdrop on the connection out of Bob’s sight and collect the k transmitted ciphertexts.

For

simplicity, suppose all public exponents ei, are equal to 3. A

simple arguments shows that Eve can recover M if k ? 3. Indeed, Bob obtains C1,

C2, C3,

Where, C1= M3mod

N1, C2= M3mod N2, C3= M3mod

N3.

Assume

that gcd(Ni, Nj) = 1 for all i ? j since otherwise Eve

can factor some of the Ni’s. Hence, applying the Chinese Remainder Theorem (CRT)

to C1, C2, C3 gives a C’ ?ZN1N2N3

satisfying C’ = M3mod N1N2N3. Since M is less than all the Ni’s, we

have M3< N1N2N3. Then C' = M3
holds over the integers. Thus, Eve may recover M by computing the real cube
root of C'. More generally, if all public exponents are equal to e, Eve can
recover M as soon as k > e. The attack is feasible only when a small e is

used. To stimulate Hastad’s result, if M is m bits long, Bob could send Mi=

i2m+ M to party Pi. Since Eve obtains encryptions of

different messages, he can’t mount the attack.

Unfortunately,

Hastad showed that this linear padding is insecure. In fact, he proved that

applying any fixed polynomial to the message prior to encryption does not

prevent the attack. Suppose that for each of the participants P1…

Pk, Bob has a fixed public polynomial fi ? ZNi x.

To broadcast a message M, Bob sends the encryption of fi (M) to party

Pi. By eavesdropping, Eve learns Ci= fi (M) ei

mod Ni for i =1… k. Hastad showed that if enough parties are

involved, Eve can recover the plaintext M from all the ciphertexts. In more

generality, Hastad proved that a system of univariate equations modulo

relatively prime composites, such as applying any fixed polynomial g1 (M)

= 0 mod Ni, could be solved if sufficiently many equations are provided. This

attack suggests that randomized padding should be used in RSA encryption.

4.4

Coppersmith’s short pad attack

Generally,

The Franklin-Reiter attack is considered to be an artificial attack because why

should Bob send Alice the encryption of related messages? Coppersmith

strengthened the attack and proved an important result on padding. Coppersmith

showed that if randomized padding suggested by Hastad is used improperly then RSA

encryption is not secure. A naive random padding algorithm might pad a plaintext

M by appending a few random bits to one of the ends. The following attack

points out the danger of such simplistic padding. Suppose Bob sends a

properly-padded encryption of M to Alice. An attacker, Eve, intercepts the ciphertext

and prevents it from reading its destination. Bob notice that Alice did not

respond to his message and decides to resend M to Alice. He randomly pads M and

transmits the resulting ciphertext. Eve now has two ciphertexts corresponding

to two encryptions of the same message using two different random pads.

Implementation

Attacks

5.1

Timing attacks

Let

us consider a smartcard that stores a private RSA key. An attacker may not be

able to see its content and expose the key. However, the precise time of

decryption the card takes can help an attacker find or discover the private

decryption exponent d. Repeated squaring algorithm can be used for this attack

which is explained as follow:

• Let d = dn, dn-1… d0

(binary of d)

• Set z = M and C = 1. For i=0 … n do:

• (1)

if di= 1 set C = C. z mod N

• (2)

z = z * z mod N

• C at the end has the value Mdmod

N

5.2

Random Faults

To

speed up the computation of Md mod N, Implementations of RSA

decryption and signatures frequently use the Chinese Remainder Theorem. Instead

of working modulo N, the signer Bob first computes the signatures modulo p and q

and then combines the result using the Chinese Remainder Theorem.

More

accurately,

Bob

first computes,

Cp= Mdpmod p and Cq=

Mdqmod q

Where dp= d mod (p -1) and dq=

d mod(q-1).

then C = T1Cp+ T2Cq(mod

N)

whereT1= { 1 mod p and T2=

{0 mod p 0 mod q } 1 mod q}

The

running time of the last CRT step is negligible compared to the two

exponentiations. p and q are half the length of N. Since simple implementations of

multiplication take quadratic time, multiplication modulo p is four times

faster than modulo N. Furthermore, dp is half the length of d and consequently

computing Mdp mod p is eight times faster than computing Mdp

mod N. Overall signature time is thus reduced by a factor of four. Many RSA

implementations use this method to improve performance.

6 Conclusion

Twenty

years of research aimed to break the RSA produced some insightful attacks, but

no serious attack has been found yet. Currently, it appears that proper RSA

implementation can provide the required security in the digital world. Four

main classes of RSA attacks were found: (1) elementary attacks that show the

misuse of the system, (2) low private exponent to show how serious it gets when

a low private is used, (3) low public exponent attacks, and (4) attacks on the

RSA implementation.

Proper

use of RSA and properly padding a message before encryption can defeat the

explained attacks.

Reference:

https://www.utc.edu/center-information-security-assurance/pdfs/course-paper-5600-rsa.pdf

https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

http://www.ijcsit.com/docs/Volume%202/vol2issue5/ijcsit2011020578.pdf