RSA: Attack and Defense (I)

Posted on Edited on In Views: Symbols count in article: 22k Reading time ≈ 20 mins.

RSA is a public-key cryptosystem built on top of an asymmetric encryption algorithm, which was jointly invented by three cryptographers and computer scientists at the Massachusetts Institute of Technology in 1977. The RSA public-key encryption algorithm and cryptosystem provide data confidentiality and signature verification functions widely used on the Internet. Since its birth, RSA has become a major research object of modern cryptography. Many cryptanalysts and information security experts have been studying its possible theoretical flaws and technical loopholes to ensure security and reliability in practical applications.

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?
— Sunzi Suanjing, Volume 2.26

Fortunately, after more than 40 years of extensive research and practical application tests, although many sophisticated attack methods have been discovered, RSA is generally safe. These attack methods all take advantage of the improper use of RSA or the vulnerability of software and hardware implementations, and cannot shake the security foundation of its encryption algorithm. On the other hand, the research on these attack methods shows that implementing a safe and robust RSA application is not a simple task. A consensus in cryptography and network security hardware and software engineering practice is: never roll your own cryptography!1 The appropriate solution is to use an existing, well-tested, and reliably maintained library or API to implement the RSA algorithm and protocol application.

Here is a brief survey of the common means of attacking RSA, the mathematical mechanism on which the attack is based, and the corresponding protective measures. Referring to the previous article, let’s start by reviewing the working mechanism and process of RSA:

  1. Choose two large prime numbers \(p\) and \(q\), compute \(N=pq\)
  2. Compute \(\lambda(N)\), where \(\lambda\) is Carmichael's totient function
    • When both \(p\) and \(q\) are prime, \(\lambda(pq)=\operatorname {lcm}(p − 1, q − 1)\)
    • \(\operatorname{lcm}\) is a function to find the least common multiple, which can be calculated by the Euclidean algorithm
  3. Choose a number \(e\) that is less than \(\lambda(N)\) and also coprime with it, then calculate the modular multiplicative inverse of \(e\) modulo \(\lambda(N)\). That is \(d\equiv e^{-1}\pmod {\lambda(N)}\)
    • Per the definition of modular multiplicative inverse, find \(d\) such that \((d⋅e)\bmod\lambda(N)=1\)
    • A modular multiplicative inverse can be found by using the extended Euclidean algorithm
  4. \(\pmb{(N,e)}\) is the public key，\(\pmb{(N,d)}\) is the private key
    • The public key can be known by everyone, but the private key must be kept secret
    • The records of \(p,q,\lambda(N)\) can all be discarded
  5. The sender first converts the message into a positive integer less than \(N\) according to the agreed encoding format, then uses the receiver's public key to compute the ciphertext with the formula \(\pmb{c\equiv m^e\pmod N}\)
  6. After receiving the ciphertext, the receiver uses its private key to compute the plaintext \(m\) with the formula \(\pmb{m\equiv c^d\pmod N}\), then decodes it into the original message
  7. A message encrypted with the private key can also be decrypted by the public key, i.e. if \(\pmb{s\equiv m^d\pmod N}\), \(\pmb{m\equiv s^e\pmod N}\). This is the supported digital signature feature

Note that the second and third steps in the original RSA paper use Euler's totient function \(\varphi(N)\) instead of \(\lambda(N)\). The relationship between these two functions is: \[\varphi(N)=\lambda(N)⋅\operatorname{gcd}(p-1,q-1)\] Here \(\operatorname{gcd}\) is the greatest common divisor function. Using \(\lambda(N)\) can yield the minimum workable private exponent \(d\), which is conducive to efficient decryption and signature operations. Implementations that follow the above procedure, whether using Euler's or Carmichael's functions, are often referred to as "textbook RSA ".

Textbook RSA is insecure, and there are many simple and effective means of attack. Before discussing the security holes of the textbook RSA in detail, it is necessary to review the first known attack method - integer factorization!

Integer Factorization

The theoretical cornerstone of the security of the RSA encryption algorithm is the problem of factoring large numbers. If we can separate \(p\) and \(q\) from the known \(N\), we can immediately derive the private exponent \(d\) and thus completely crack RSA. Factoring large numbers is a presumed difficult computational problem. The best-known asymptotic running time algorithm is General Number Field Sieve, and its time complexity is \({\displaystyle \exp \left(\left(c+o(1)\right)(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}\right)}\), where the constant \(c = 4/\sqrt[3]{9}\)，\(\displaystyle \exp\) and \(\displaystyle \exp\) is the exponential function of Euler's number (2.718).

For a given large number, it is difficult to accurately estimate the actual complexity of applying the GNFS algorithm. However, based on the heuristic complexity empirical estimation, we can roughly see the increasing trend of computational time complexity:

  • For a large number of 1024 bits, there are two prime factors of about 500 bits each, and the decomposition requires basic arithmetic operations of order \(2^{70}\)
  • For a large number of 2048 bits, there are two prime factors of about 1000 bits each, and the decomposition requires basic arithmetic operations of order \(2^{90}\), a million times slower than the 1024-bit number

The rapid development of computer software and hardware technology has made many tasks that seemed impossible in the past become a reality. Check the latest record released by the RSA Factoring Challenge website. In February 2020, a team led by French computational mathematician Paul Zimmermann successfully decomposed the large number RSA-250 with 250 decimal digits (829 bits):

1
2
3
4
RSA-250 = 6413528947707158027879019017057738908482501474294344720811685963202453234463
          0238623598752668347708737661925585694639798853367
        × 3337202759497815655622601060535511422794076034476755466678452098702384172921
          0037080257448673296881877565718986258036932062711

announcement

According to the announcement of the factorization released by Zimmerman, using a 2.1GHz Intel Xeon Gold 6130 processor, the total computing time to complete this task is about 2700 CPU core-years. This number may seem large, but in today's era of cluster computing, grid computing, and cloud computing for the masses, it's not a stretch to think that organizations with strong financial backing can reduce computing time to hours or even minutes. As an example, go to the online tool website of the free open-source mathematical software system SageMath and enter the following first 5 lines of Sage Python code:

1
2
3
4
5
6
7
8
p=random_prime(2**120)
q=random_prime(2**120)
n=p*q
print(n)
factor(n)
# The output
28912520751034191277571809785701738245635791077300278534278526509273423
38293227899687810929829874029597363 * 755029605411506802434801930237797621

The result was obtained within minutes, and a large number of 72 decimal digits (240 bits) was decomposed. You know, in the 1977 RSA paper, it is mentioned that it takes about 104 days to decompose a 75-digit decimal number. The technological progress of mankind is so amazing!

As the attacker's spear becomes sharper and sharper, the defender's shield must become thicker and thicker. Therefore, 1024-bit RSA is no longer secure, and applications should not use public key \(N\) values that are less than 2048 bits. And when high security is required, choose 4096-bit RSA.

Elementary Attacks

Although the decomposition of large numbers is an attack method known to everyone, the security vulnerabilities caused by some low-level errors commonly found in RSA applications make it possible to use simple attacks to succeed, and some typical ones are explained below.

  • In the early development of RSA, finding large prime numbers took quite a bit of time based on the backward computing power of the time. Therefore, some system implementations tried to share the modulus \(N\). The idea was to generate only one set \((p,q)\), and then all users would use the same \(N=pq\) values, with a central authority that everyone trusted assigning key pairs \((e_i,d_i)\) to each user \(i\), and nothing would go wrong as long as the respective private keys \(d_i\) were kept. Unfortunately, this is a catastrophic mistake! This implementation has two huge security holes：

    1. The user \(i\) can decompose \(N\) using his own key pair \((e_i,d_i)\). Whether \(d\) is generated using the Euler function \(\varphi(N)\) or the Carmichael function \(\lambda(N)\), there are algorithms that quickly derive the prime factors \(p\) and \(q\) from a given \(d\) 2. And once \(p\) and \(q\) are known, user \(i\) can compute any other user's private key \(d_j\) with one's public key \((N,e_j)\). At this point, the other users have no secrets from user \(i\).

    2. Even if all users do not have the knowledge and skill to decompose \(N\), or are "nice" enough not to know the other users' private keys, a hacker can still perform a common modulus attack to break the users' messages. If the public keys of two users, Alice and Bob, are \(e_1\) and \(e_2\), and \(e_1\) and \(e_2\) happen to be mutually prime (which is very likely), then by Bézout's identity, the eavesdropper Eve can find that \(s\) and \(t\) satisfy: \[e_{1}s+e_{2}t=gcd(e_1,e_2)=1\] At this point, if someone sends the same message \(m\) to Alice and Bob, Eve can decrypt \(m\) after recording the two ciphertexts \(c_1\) and \(c_2\) and performing the following operation: \[c_1^s⋅c_2^t\equiv(m^{e _1})^s⋅(m^{e_2})^t\equiv m^{e_{1}s+e_{2}t}\equiv m\pmod N\] The corresponding Python function code is shown below.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      def common_modulus(e1, e2, N, c1, c2):
          # Call the extended Euclidean algorithm function
          g, s, t = gymp2.gcdext(e1, e2)
          assert g == 1
          if s < 0:
              # Find c1's modular multiplicative inverse		        re = int(gmpy2.invert(c1, N))
              c1 = pow(re, s*(-1), N)
              c2 = pow(c2, t, N)
          else:
              # t is negative, find c2's modular multiplicative inverse
              re = int(gmpy2.invert(c2, N))
              c2 = pow(re, t*(-1), N)
              c1 = pow(c1, a, N)
          return (c1*c2) % N
      Two library functions of gmpy23 are called here: gcdext() to implement the extended Euclidean algorithm, and invert() to find the modular multiplicative inverse element. Note that Python's exponential function pow() supports modular exponentiation, but the exponent must not be negative. Since one of \(s\) or \(t\) must be negative, you have to first call invert() to convert \(c_1\) or \(c_2\) to the corresponding modular multiplicative inverse, then invert the negative number to calculate the modular exponent. For example, lines 7 and 8 above implement \(c_1^s=(c_1^{-1})^{-s}\bmod N\).

  • Is it possible to reuse only \(p\) or \(q\) since the shared modulus \(N\) is proven to be insecure? This seems to avoid the common-modulus attack and ensure that each user's public key \(N\) value is unique. Big mistake! This is an even worse idea! The attacker gets the public \(N\) values of all users and simply combines \((N_1,N_2)\) pairwise to solve Euclid's algorithm for the great common divisor, and a successful solution gives a prime factor \(p\), and a simple division gives the other prime factor \(q\). With \(p\) and \(q\), the attacker can immediately compute the user's private key \(d\). This is the non-coprime modulus attack.

  • When applying textbook RSA, if both the public exponent \(e\) and the plaintext \(m\) are small, such that \(c=m^e<N\), the plaintext \(m\) can be obtained by directly calculating the \(e\)th root of the ciphertext \(c\). Even if \(m^e>N\) but not large enough, then since \(m^e=c+k⋅N\), you can loop through the small \(k\) values to perform brute-force root extraction cracking. Here is the Python routine:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def crack_small(c, e, N, repeat)
        times = 0
        msg = 0
        for k in range(repeat):
            m, is_exact = gmpy2.iroot(c + times, e)
            if is_exact and pow(m, e, N) == c:
                msg = int(m)
                break
            times += N
        return msg
    Here the gmpy2 library function iroot() is called to find the \(e\)th root.

  • Textbook RSA is deterministic, meaning that the same plaintext \(m\) always generates the same ciphertext \(c\). This makes codebook attack possible: the attacker precomputes all or part of the \(m\to c\) mapping table and saves, then simply searches the intercepted ciphertext for a match. Determinism also means that textbook RSA is not semantically secure and that the ciphertext can reveal some information about the plaintext. Repeated occurrences of the ciphertext indicate that the sender is sending the same message over and over again.

  • Textbook RSA is malleable, where a particular form of algebraic operation is performed on the ciphertext and the result is reflected in the decrypted plaintext. For example, if there are two plaintexts \(m_1\) and \(m_2\), and encryption yields \(c_1=m_1^e\bmod N\) and \(c_2=m_2^e\bmod N\), what does \((c_1⋅c_2)\) decryption yield? Look at the following equation: \[(c_1⋅c_2)^d\equiv m_1^{ed}⋅m_2^{ed}\equiv m_1⋅m_2\pmod N\] So the plaintext obtained after decrypting the product of the two ciphertexts is equal to the product of the two plaintexts. This feature is detrimental to RSA encryption systems in general and provides an opportunity for chosen-ciphertext attack. The following are two examples of attack scenarios:

    1. Imagine that there is an RSA decryption machine that can decrypt messages with an internally saved private key \((N,d)\). For security reasons, the decryptor will reject repeated input of the same ciphertext. An attacker, Marvin, finds a piece of ciphertext \(c\) that is rejected by the decryptor when he enters it directly because the ciphertext \(c\) has been decrypted before. Marvin finds a way to crack it. He prepares a plaintext \(r\) himself, encrypts it with the public key \((N,e)\) to generate a new ciphertext \(c'={r^e}c\bmod N\), and then feeds the ciphertext \(c'\) to the decryptor. The decryption machine has not decrypted this new ciphertext, so it will not reject it. The result of the decryption is \[m'\equiv (c')^d\equiv r^{ed}c^d\equiv rm\pmod N\] Now that Marvin has \(m'\), he can calculate \(m\) using the formula \(m\equiv m'r^{-1}\pmod N\).

    2. Suppose Marvin wants Bob to sign a message \(m\), but Bob refuses to do so after reading the message content. Marvin can achieve his goal by using an attack called blinding4. He picks a random message \(r\), generates \(m'={r^e}m\bmod N\), and then takes \(m'\) to Bob to sign. Bob probably thinks \(m'\) is irrelevant and signs it. The result of Bob's signature is \(s'=(m')^d\bmod N\). Now Marvin has Bob's signature on the original message \(m\) using the formula \(s=s'r^{-1}\bmod N\). Why? The reason is that \[s^e\equiv (s')^er^{-e}\equiv (m')^{ed}r^{-e}\equiv m'r^{-e}\equiv m\pmod N\]

The above is by no means a complete list of elementary attack methods, but they are illustrative. In practical RSA applications, we must be very careful and should do the following:

  • generate a unique public key modulus \(N\) for each user individually to prevent common-mode attacks
  • not reuse the prime factor to generate the public key modulus \(N\), to eliminate the non-coprime modulus attack

For the textbook RSA deterministic and malleable flaws, and possible brute-force root extraction cracking vulnerabilities, the padding with random elements method can be used to protect against them, and the protection is valid due to the following:

  • Padding ensures that the number of bits in the encrypted message is close to \(N\), while not using small \(e\) values, making possible brute-force root extraction cracking ineffective
  • Random padding makes the same plaintext produce different ciphertexts, guaranteeing semantic security and making ciphertext attacks impossible
  • Strictly format-defined padding destroys malleability and reduces the possibility of ciphertext selection attacks. For example, if the first few bytes after padding must be a given value, the decrypted data will most likely not conform to the predefined format after the algebraic operation on the corresponding ciphertext, which disrupts the ciphertext selection attack.

Low Public Exponent Attacks

Using low public exponent is dangerous, and there are advanced attacks in the case of non-padding or improper padding, even if brute-force root extraction cracking does not succeed.

Broadcast Attack

Discovered by Swedish theoretical computer scientist Johan Håstad 5, hence the name Håstad's Broadcast Attack. Consider this simplified scenario, assuming that Alice needs to send the same message \(m\) to Bob, Carol, and Dave. The public keys of the three recipients are \((N_1,3)\), \((N_2,3)\), and \((N_3,3)\), i.e., the public exponent is all 3 and the public key modulus is different for each. The messages are not padded and Alice directly encrypts and sends three ciphertexts \(c_1,c_2,c_3\) using the public keys of the other three:

\[\begin{cases} c_1=m^3\bmod N_1\\ c_2=m^3\bmod N_2\\ c_3=m^3\bmod N_3 \end{cases}\]

At this point Eve secretly writes down the three ciphertexts, marking \(M=m^3\), and if she can recover \(M\), running a cube root naturally yields the plaintext \(m\). Obviously, the common modulus attack does not hold here, and we can also assume that the moduli are pairwise coprime, or else decomposing the modulus using the non-coprime modulus attack will work. So does Eve have a way to compute \(M\)? The answer is yes.

In fact, the equivalent problem for solving \(M\) here is: Is there an efficient algorithm for solving a number that has known remainders of the Euclidean division by several integers, under the condition that the divisors are pairwise coprime? This efficient algorithm is Chinese Remainder Theorem!

The Chinese remainder theorem gives the criterion that a system of one-element linear congruence equations has a solution and the method to solve it. For the following system of one-element linear congruence equations (be careful not to confuse it with the mathematical notation used to describe the attack scenario above):

\[(S) : \quad \left\{ \begin{matrix} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv a_n \pmod {m_n} \end {matrix} \right.\]

Suppose that the integers \(m_1,m_2,\ldots,m_n\) are pairwise coprime, then the system of equations \((S)\) has a solution for any integer \(a_1,a_2,\ldots,a_n\) and the general solution can be constructed in four steps as follows:

\[\begin{align} M &= m_1 \times m_2 \times \cdots \times m_n = \prod_{i=1}^n m_i \tag{1}\label{eq1}\\ M_i &= M/m_i, \; \; \forall i \in \{1, 2, \cdots , n\}\tag{2}\label{eq2}\\ t_i M_i &\equiv 1\pmod {m_i}, \; \; \forall i \in \{1, 2, \cdots , n\}\tag{3}\label{eq3}\\ x &=kM+\sum_{i=1}^n a_i t_i M_i\tag{4}\label{eq4} \end{align}\]

The last line above, Eq. (4) gives the formula of the general solution. In the sense of modulus \(M\), the unique solution is \(\sum_{i=1}^n a_i t_i M_i \bmod M\).

Try to solve the things whose number is unknown problem at the beginning of this article by using the Chinese remainder theorem

First, correspond the variable symbols to the values: \[m_1=3,a_1=2;\quad m_2=5,a_2=3;\quad m_3=7,a_3=2\] Then calculate \(M=3\times5\times7=105\), which in turn leads to the derivation of： \[\begin{align} M_1 &=M/m_1=105/3=35,\quad t_1=35^{-1}\bmod 3 = 2\\ M_2 &=M/m_2=105/5=21,\quad t_2=21^{-1}\bmod 5 = 1\\ M_3 &=M/m_3=105/7=15,\quad t_3=15^{-1}\bmod 7 = 1\\ \end{align}\] Finally, take these into the general solution formula: \[x=k⋅105+(2⋅35⋅2+3⋅21⋅1+2⋅15⋅1)=k⋅105+233\] So the smallest positive integer solution concerning modulus 105 is \(233\bmod 105=23\)。

In his mathematical text "Suanfa Tongzong", Cheng Dawei, a mathematician of the Ming Dynasty in the 16th century, compiled the solutions recorded by the mathematician Qin Jiushao of the Song Dynasty in the "Mathematical Treatise in Nine Sections" into a catchy "Sun Tzu's Song":

Three friends set out with seventy rare
Twenty-one blossoms on five trees of plums
Seven men reunited at the half-month
All be known once divided by one hundred and five

Here we must admire the wisdom of the ancient Chinese who, in the absence of a modern mathematical symbol system, were able to derive and summarize such an ingenious solution, contributing an important mathematical theorem to mankind.

So Eve just applies the solution of the Chinese Remainder Theorem, computes \(M\), and then finds its cube root to get the plaintext \(m\), and the attack succeeds. More generally, setting the number of receivers to \(k\), if all receivers use the same \(e\), then this broadcast attack is feasible as long as \(k\ge e\).

Håstad further proves that even if padding is used to prevent broadcast attacks, if the messages generated by the padding scheme are linearly related to each other, such as using the formula \(m_i=i2^b+m\) (\(b\) is the number of bits of \(m\)) to generate the message sent to the receiver \(i\), then the broadcast attack can still recover the plaintext \(m\) as long as \(k>e\). The broadcast attack in this case is still based on the Chinese remainder theorem, but the specific cracking method depends on the information of the linear relationship.

To summarize the above analysis, to prevent the broadcast attack, we must use a higher public exponent \(e\) and apply random padding at the same time. Nowadays, the common public key exponent \(e\) is 65537 (\(2^{16}+1\)), which can balance the efficiency and security of message encryption or signature verification operations.

Last, Python routines for simulating broadcast attacks are given as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def solve_crt(ai: list, mi: list):
    '''mi and ai are the list of modulus and remainders. 
       The precondition of the function is that the modulus 
       in the mi list are pairwise coprime.'''
    M = reduce(lambda x, y: x * y, mi)
    ti = [a * (M//m) * int(gmpy2.invert(M//m, m)) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ti) % M

def rsa_broadcast_attack(ctexts: list, moduli: list):
    '''RSA broadcast attack: applying CRT to crack e=3'''
    c0, c1, c2 = ctexts[0], ctexts[1], ctexts[2]
    n0, n1, n2 = moduli[0], moduli[1], moduli[2]
    m0, m1, m2 = n1 * n2, n0 * n2, n0 * n1
    t0 = (c0 * m0 * int(gmpy2.invert(m0, n0)))
    t1 = (c1 * m1 * int(gmpy2.invert(m1, n1)))
    t2 = (c2 * m2 * int(gmpy2.invert(m2, n2)))
    c = (t0 + t1 + t2) % (n0 * n1 * n2)
    return int(gmpy2.iroot(c, 3)[0])

def uint_to_bytes(x: int) -> bytes:
    '''convert unsigned integer to byte array'''
    if x == 0:
        return bytes(1)
    return x.to_bytes((x.bit_length() + 7) // 8, 'big')

quote = b'The cosmos is within us. We are made of star stuff. - Carl Sagan'
bob = RSA(1024, 3)
carol = RSA(1024, 3)
dave = RSA(1024, 3)
cipher_list = [bob.encrypt(quote), carol.encrypt(quote), dave.encrypt(quote)]
modulus_list = [bob.n, carol.n, dave.n]

cracked_cipher = solve_crt(cipher_list, modulus_list)
cracked_int = int(gmpy2.iroot(cracked_cipher, 3)[0])
assert cracked_int == rsa_broadcast_attack(cipher_list, modulus_list)

hacked_quote = uint_to_bytes(cracked_int)
assert hacked_quote == quote

This code uses two methods to simulate the broadcast attack. One calls the generic Chinese remainder theorem solver function solve_crt() and then gets the cube root of the result; the other calls the special broadcast attack function rsa_broadcast_attack() for the public key index \(e=3\), which directly outputs the cracked plaintext value. The internal implementation of these two functions is based on the generalized formula of the Chinese remainder theorem, and the output results should be identical. The cracked plaintext value is then input to the uint_to_bytes() function, which is converted into a byte array to compare with the original quote. Note that the program uses objects generated by the RSA class to simulate the receivers Bob, Carroll, and Dave, and the implementation of the RSA class is omitted here given the limitation of space.

Next article: RSA: Attack and Defense (II)

  1. American computer scientist and security expert Gary McGraw has a famous piece of advice for software developers - "never roll your own cryptography"↩︎

  2. The original RSA paper (Part IX, Section C) did mention Miller's algorithm for factoring \(N\) with a known \(d\). This algorithm also applies to \(d\) generated by the Carmichael function \(\lambda(N)\).↩︎

  3. gmpy2 is a Python extension module written in C that supports multi-precision arithmetic.↩︎

  4. On some special occasions, blinding can be used for effective privacy protection. For example, in cryptographic election systems and digital cash applications, the signer and the message author can be different.↩︎

  5. Johan Håstad, a Swedish theoretical computer scientist, a professor at the KTH Royal Institute of Technology, and a Fellow of the American Mathematical Society (AMS) and an Association for Computing Machinery (ACM) fellow.↩︎