Attack on RSA

 The Security of RSA

Four possible approaches to attacking the RSA algorithm are

• Brute force: This involves trying all possible private keys.

• Mathematical attacks: There are several approaches, all equivalent in effort to factoring the product of two primes.

• Timing attacks: These depend on the running time of the decryption algorithm.

• Chosen ciphertext attacks: This type of attack exploits properties of the RSA algorithm.

The defense against the brute-force approach is the same for RSA as for other crypto systems, namely, to use a large key space. Thus, the larger the number of bits in $d$, the better. However, because the calculations involved, both in key generation and in encryption/decryption, are complex, the larger the size of the key, the slower the system will run.

THE FACTORING PROBLEM We can identify three approaches to attacking RSA mathematically.
1. Factor $n$ into its two prime factors.This enables calculation of $\phi(n) = (p - 1) ×(q - 1)$, which in turn enables determination of $d \equiv e^{-1} \pmod {\phi(n)}$.
2. Determine $\phi(n)$ directly, without first determining $p$ and $q$. Again, this enables determination of $d \equiv e^{-1} \pmod {\phi(n)}$.
3. Determine $d$ directly, without first determining $\phi(n)$.

Most discussions of the cryptanalysis of RSA have focused on the task of factoring $n$ into its two prime factors. Determining $\phi(n)$ given $n$ is equivalent to factoring $n$ .With presently known algorithms, determining $d$ given $e$ and $n$ appears to be at least as time-consuming as the factoring problem. Hence, we can use factoring performance as a benchmark against which to evaluate the security of RSA.

For a large $n$ with large prime factors, factoring is a hard problem, but it is not as hard as it used to be. RSA Laboratories had issued challenges for the RSA cipher with key sizes of 100, 110, 120, and so on, digits.The latest challenge to be met is  the RSA-200 challenge with a key length of 200 decimal digits, or about 663 bits.The threat to larger key sizes is twofold: the continuing increase in computing power and the continuing refinement of factoring algorithms.We have seen that the move to a different algorithm resulted in a tremendous speedup.We can expect further refinements in the GNFS, and the use of an even better algorithm is also a possibility.In fact, a related algorithm, the special number field sieve (SNFS), can factor numbers with a specialized form considerably faster than the generalized number field sieve.Thus, we need to be careful in choosing a keysize for RSA. For the near future, a key size in the range of 1024 to 2048 bits seems reasonable.

In addition to specifying the size of $n$, a number of other constraints have been suggested by researchers.To avoid values of $n$ that may be factored more easily, the algorithm’s inventors suggest the following constraints on $p$ and $q$.

1. $p$ and $q$ should differ in length by only a few digits.Thus, for a 1024-bit key (309 decimal digits), both $p$ and $q$ should be on the order of magnitude of $10^{75}$ to $10^{100}$.

2. Both $(p - 1)$ and $(q - 1)$ should contain a large prime factor.

3. $gcd(p - 1, q - 1)$ should be small.

In addition, it has been demonstrated that if $e < n$ and $d < n^{1/4}$, then $d$ can be easily determined.

TIMING ATTACKS: If one needed yet another lesson about how difficult it is to assess the security of a cryptographic algorithm, the appearance of timing attacks provides a stunning one.Paul Kocher, a cryptographic consultant, demonstrated that a snooper can determine a private key by keeping track of how long a computer takes to decipher messages .Timing attacks are applicable not just to RSA, but to other public-key cryptography systems. This attack is alarming for two reasons: It comes from a completely unexpected direction, and it is a ciphertext-only attack.

A timing attack is somewhat analogous to a burglar guessing the combination of a safe by observing how long it takes for someone to turn the dial from number to number.We can explain the attack using the modular exponentiation algorithm , but the attack can be adapted to work with any implementation that does not run in fixed time. In this algorithm, modular exponentiation is accomplished bit by bit, with one modular multiplication performed at each iteration and an additional modular multiplication performed for each 1 bit.

As Kocher points out in his paper, the attack is simplest to understand in an extreme case. Suppose the target system uses a modular multiplication function that is very fast in almost all cases but in a few cases takes much more time than an entire average modular exponentiation. The attack proceeds bit-by-bit.For a given ciphertext, the attacker can complete the first $j$ iterations of the for loop.The operation of the subsequent step depends on the unknown exponent bit. If the bit is set,$d =(d × a) \pmod n$ will be executed. For a few values of $a$ and $d$, the modular multiplication will be extremely slow, and the attacker knows which these are.Therefore, if the observed time to execute the decryption algorithm is always slow when this particular iteration is slow with a 1 bit, then this bit is assumed to be 1. If a number of observed execution times for the entire algorithm are fast, then this bit is assumed to be 0.

Although the timing attack is a serious threat, there are simple countermeasures that can be used, including the following.

• Constant exponentiation time: Ensure that all exponentiations take the same amount of time before returning a result.This is a simple fix but does degrade

performance.

• Random delay: Better performance could be achieved by adding a random delay to the exponentiation algorithm to confuse the timing attack. Kocher points out that if defenders don’t add enough noise, attackers could still succeed by collecting additional measurements to compensate for the random delays.

• Blinding: Multiply the ciphertext by a random number before performing exponentiation.This process prevents the attacker from knowing what ciphertext bits are being processed inside the computer and therefore prevents the bit-by-bit analysis essential to the timing attack.RSA Data Security reports a 2 to 10% performance penalty for blinding

CHOSEN CIPHERTEXT ATTACK AND OPTIMAL ASYMMETRIC ENCRYPTION PADDING 

The basic RSA algorithm is vulnerable to a chosen ciphertext attack (CCA). CCA is defined as an attack in which the adversary chooses a number of ciphertexts and is then given the corresponding plaintexts, decrypted with the target’s private key.Thus, the adversary could select a plaintext, encrypt it with the target’s public key, and then decrypted with the private key. Clearly, this provides the adversary with no new information. Instead, the adversary exploits properties of RSA and selects blocks of data that, when processed using the target’s private key, yield information needed for cryptanalysis.

A simple example of a CCA against RSA takes advantage of the following property of RSA:

$$E(PU,M1) × E(PU,M2) = E(PU, [M1 × M2]) $$

We can decrypt $C = M^e \pmod n$ using a CCA as follows.

1. Compute $X = (C × 2^e) \pmod n$.

2. Submit $X$ as a chosen ciphertext and receive back $Y = X^d \pmod n$.

But now note that

$$X = (C \pmod n) * (2^e \pmod n)$$

$$X= (M^e mod n) * (2^e mod n)$$

$$X= (2M)^e \pmod n$$

Therefore $Y=2M \pmod n$

From this, we can deduce M. To overcome this simple attack, practical RSA-based cryptosystems randomly pad the plaintext prior to encryption.However, more sophisticated CCAs are possible, and a simple padding with a random value has been shown to be insufficient to provide the desired security. To counter such attacks, RSA Security Inc., a leading RSA vendor and former holder of the RSA patent, recommends modifying the plaintext using a procedure known as optimal asymmetric encryption padding (OAEP).

Figure below depicts OAEP encryption. As a first step, the message M to be encrypted is padded.A set of optional parameters,$P$, is passed through a hash function, H. The output is then padded with zeros to get the desired length in the overall data  block (DB). Next, a random seed is generated and passed through another hash function, called the mask generating function (MGF).The resulting hash value is bit-by-bit XORed with DB to produce a masked DB. The masked DB is in turn passed through the MGF to form a hash that is XORed with the seed to produce the masked seed.The concatenation of the masked seed and the masked DB forms the encoded message EM.Note that the EM includes the padded message, masked by the seed, and the seed, masked by the maskedDB.The EM is then encrypted using RSA.