Security代写:CS588 Attacking RSA

不正确的使用RSA算法会导致脆弱性,这个lab作业模拟脆弱的RSA加密过程,并完成对应的攻击代码。

Introduction

In this lab, you will investigate vulnerabilities in RSA, when it is used incorrectly.

Objectives

  • Understand how to apply RSA encryption and digital signatures.
  • Investigate how using RSA incorrectly can compromise confidentiality and integrity.

Getting Familiar with RSA

Textbook RSA

Here, we summarize a naive version of the RSA (“textbook RSA”) encryption and digital signatures schemes. This version of RSA should not be used; you will show in this lab several ways in which it can be vulnerable. Consult https://en.wikipedia.org/wiki/RSA_(cryptosystem) for more detail.

Encryption

Below we describe the key generation (KeyGen), encryption (Enc), and decryption (Dec) algorithms of RSA.

  1. KeyGen:
    • (a) Choose two random primes p and q.
    • (b) Let n = pq be the modulus.
    • (c) Select a random encryption exponent e such that the greatest common denominator of e and (p - 1)(q - 1) is 1 (that is, e and (p - 1)(q - 1) are relatively prime).
    • (d) Let the decryption exponent d be e^-1 mod (p - 1)(q - 1).
    • (e) Return the public key pk = (n, e) and the secret key sk = d.
  2. Enc(pk = (n, e), m), where m is a message to be encrypted:
    • (a) Return the ciphertext c = m^e mod n.
  3. Dec(sk = d, c), where c is a ciphertext to be decrypted:
    • (a) Return the recovered message m = c^d mod n.

As an example, say that during KeyGen, I choose p = 5 and q = 11. Therefore, I have n = 55. If I choose e = 3, I need to find a d such that 3d mod (5 - 1)(11 - 1) = 3d mod 40 = 1. I can try a few numbers, and see that 3 27 mod 40 = 81 mod 40 = 1, so I set d = 27.

Now, say that you know only n = 55 and e = 3. Encryption is just raising the message m to the power of e; you can encrypt m = 51 as c = 51^3 mod 55 = 132651 mod 55 = 46.

Decryption is the inverse of encryption; it takes the e-th root of the ciphertext. e and d are chosen in such a way that raising to the power of d is the same as taking the eth root. Therefore, I, who also know d = 27, can decrypt c = 46 by taking m = 46^27 mod 55 = 51.

Taking the eth root of a value modulo an n whose factorization you don’t know is considered to be unrealistic for large numbers. However, in our example, someone else, who doesn’t know d = 27, can also figure out what m is, just by trying each number modulo 55 and raising it to e = 3. (If they get 46, they know they’ve found the right m!) This is only possible because we chose small p and q. If p and q are over 1000 bits long, instead of just 5 bits long, decryption without knowledge of d (or the factorization of n) becomes unrealistic.

Digital Signatures

In “textbook RSA” digital signatures, key generation (KeyGen) is exactly the same as it is in the encryption scheme described above. Signing (Sig) is reminiscent of decryption, and verification (Ver) is reminiscent of encryption.

  1. Sig(sk = d, m), where m is a message to be signed:
    • (a) Return the signature σ = m^d mod n.
  2. Ver(m, σ, pk = (n, e)), where m is a message and is a signature to be verified:
    • (a) Verify that σ^e mod n = m mod n.

Using RSA Securely

In order to avoid vulnerabilities such as the ones explored in this lab, instead of “textbook RSA”, RSA PKCS #1 (ftp://ftp.rsasecurity.com/pub/pkcs/ascii/pkcs-1.asc) is used.

Encryption

To encrypt a message m using RSA PKCS #1 version 1.5, the message is padded as follows.

The result is encrypted using the “textbook RSA” encryption function.

Digital Signatures

To sign a message m using RSA PKCS #1 version 1.5, the message is padded as follows:

The result is signed using the “textbook RSA” signing function. The algorithms that check the digital signatures need to be implemented very carefully. In Part 5, you will show that if the implementation of the verification algorithm is slightly off, PKCS1.5 signatures can be forged.

NOTE: The implementation vulnerabilities that are explored in this lab have occurred often enough in the wild that many cryptographers and practitioners have concluded that using RSA PKCS v1.5 is not a good idea. RSA-OAEP is the suggested choice for RSA encryption. See https://tools.ietf.org/html/rfc3560.)

Avoiding the attacks discussed in this lab has also been cited as motivation for using elliptic curve cryptographic signatures (e.g., ECDSA) instead of RSA.
Nevertheless, RSA is still widely used in practice.

Textbook RSA in Python

You can experiment with RSA yourself, using Python. In tools.py, we provide several functions you can use in this exploration. For instance, we provide text to integer (and integer to text) conversion, because the RSA algorithms assume that the message m is an integer modulo n.

  • text_to_int: takes in a string and returns an integer which can be used in RSA.
  • int_to_text: takes in an integer and returns the corresponding string.

We also provide a few other functions:

  • find_root: takes in integers x and r, and returns the integer component of the rth root of x. (Python’s built in pow function can be used to do this, but it doesn’t work for very large ‘long’-type values.)
  • combine_moduli: takes in two integer moduli n1 and n2 and two integers x1 and x2 , and returns an integer x mod n1 n2 such that x mod n1 = x1 and x mod n2 = x2 . For instance, combine_moduli(n1 = 5, n2 = 7, x1 = 2, x2 = 3) = 17, since 17 mod 5 = 2, and 17 mod 7 = 3.

The following shows how to use Python to do some basic RSA operations:

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
from Crypto.PublicKey import RSA
from Crypto.Hash import SHA256
import tools
# set the security parameter:
secparam = 2048
# generate an RSA key:
key = RSA.generate(secparam)
public_key = key.publickey()
# save the public and private keys to files and read them back:
open('key.pub', 'w').write(public_key.exportKey())
open('key.priv', 'w').write(key.exportKey())
# read the public key in:
recovered_public_key = RSA.importKey(open('key.pub', 'r').read())
assert recovered_public_key == public_key
# read the private key in:
recovered_key = RSA.importKey(open('key.priv', 'r').read())
assert recovered_key == key
# use the PUBLIC KEY to encrypt a message:
message = "I ATE SOME PIE"
message_int = tools.text_to_int(message)
ciphertext = public_key.encrypt(message_int, None)
# save the ciphertext to a file and read it back:
open('ciphertext', 'w').write(str(ciphertext))
recovered_ciphertext = eval(open('ciphertext', 'r').read())
assert recovered_ciphertext == ciphertext
# use the PRIVATE KEY to decrypt the message:
recovered_message_int = int(key.decrypt(ciphertext))
assert recovered_message_int == message_int
# use the PRIVATE KEY to sign a hash of the message:
hash = SHA256.new(message).digest()
signature = key.sign(hash, None)
# save the signature to a file and read it back:
open('signature', 'w').write(str(signature))
recovered_signature = eval(open('signature', 'r').read())
assert recovered_signature == signature
# use the PUBLIC KEY to verify the signature:
hash = SHA256.new(message).digest()
assert public_key.verify(hash, signature)

We can also use math operations in Python to explore RSA ciphertexts and signatures manually.
For instance, you can manually verify the signature. The modulus can be accessed as public_key.n, and the public exponent can be accessed as public_key.e.

1
2
3
print "%0128x" % pow(signature[0], public_key.e, public_key.n)
# The suffix of the signature^e mod n should be:
print SHA256.new(message).hexdigest()

Small Message Space Attack

Imagine that you are a government agent trying to determine when your neighboring country,
Malland, will attack. Open part2_ctext to find a “textbook RSA” ciphertext sent by Malland to its ally, Horridland. You know that the Mallanders are likely to be saying one of three things:

  1. “attack tomorrow at dawn”,
  2. “attack just before dusk”, or
  3. “attack early next week”.

The file part2_key.pub contains Horridland’s public key. Use this knowledge to figure out what the message is.
What would you do to prevent Malland from executing the same attack on ciphertexts you send?

What to submit

  1. A Python 2.x script named part2.py that:
    • (a) Takes in three parameters:
      • i. The path to a file with a public key,
      • ii. The path to a file with a ciphertext, and
      • iii. The path to a file enumerating the possible messages, each on a new line.
    • (b) Prints the identified message.
  2. A file named part2.txt with your suggestion for how to prevent the attack you executed in part2.py.

Small Plaintext and Encryption Exponent Attack

Open part3_ctext to find another “textbook RSA” ciphertext, sent by Malland to Horridland.
However, this time, you don’t really know what Malland might be saying. You do, however, know that the encryption exponent is e = 3, and that Mallanders tend to be very brief and to the point, so you think the message in question is probably very short. Use this knowledge to figure out what the message is.

Defense: Padding

A technique that prevents this attack is padding, which is used in PKCS #1. Padding artificially increases the size of the message so that it is almost as big as the modulus n by adding extra characters or bits to the message. Why would padding help prevent this attack?

What to submit

  1. A Python 2.x script named part3.py that:
    • (a) Takes in one parameter: the path to a file with a ciphertext.
    • (b) Prints the identified message.
  2. A file named part3.txt that explains why padding prevents the attack you executed in part3.py.

Broadcast Attack

Since you thwarted Malland’s plots with Horridland, Malland enlisted the help of two more allies Awfuland and Badland. Horridland, Awfuland and and Badland made the mistake of all having the same low encryption exponent, e = 3. Their public keys are in part4_key1.pub, part4_key2.pub, and part4_key3.pub, repectively. Malland sends Horridland, Awfuland and Badland a plan of attack, still using “textbook RSA” encryption. You get your hands on all three ciphertexts:

  1. In part4_ctext1, find the ciphertext Malland sent Awfuland, encrypted as cA = m^3 mod nA (using Awfuland’s modulus nA).
  2. In part4_ctext2, find the ciphertext Malland sent Badland, encrypted as cB = m^3 mod nB (using Badland’s modulus nB).
  3. In part4_ctext3, find the ciphertext Malland sent Horridland, encrypted as cH = m^3 mod nH (using Horridland’s modulus nH ).

Use the fact that all three ciphertexts use the same low encryption exponent to figure out what their plan of attack is.
Hint: Use the provided function combine_moduli in tools.py.

If Malland padded the message by adding enough ‘1’ characters to the end to make it almost as long as the modulus, would that prevent you from recovering their message? If not, how could
Malland go about thwarting you?

What to submit

  1. A Python 2.x script named part4.py that:
    • (a) Takes in six parameters:
      • i. three paths to files with public keys (all of whose public exponents are e = 3), and
      • ii. three paths to files with ciphertexts.
    • (b) Prints the identified message.
  2. A file named part4.txt that explains whether padding the message with ‘1’ characters prevents the attack you executed in part4.py, and if not, how that attack could be prevented.

Breaking PKCS #1 v1.5

Up until now, we have been talking about encryption. Now, we’ll take a brief detour and talk about
RSA signatures. Signatures are frequently generated on hashes of messages, instead of on messages themselves. PKSC #1 v1.5 is a signing standard widely used on the internet. It involves adding padding to a message hash before signing it using RSA, as described in Part 1.2.2. When PKSC #1 v1.5 is used, an RSA signature on the following padded message hash is generated.

When PKCS padding is used, it is important for implementations to verify that every bit of the padded, signed message is exactly as it should be. It is tempting for an implementor to validate the signature by first stripping off the 00 01 bytes, then some number of padding FF bytes, then 00, and then parse the ASN.1 and verify the hash. If the implementation does not check the length of the FF bytes and that the hash is in the least significant bits of the message, then it the public verification exponent e is low, is possible for an attacker to forge values that pass this validation check.

Say that e = 3, as in Parts 3 and 4. If the length of the required padding, ASN.1 bytes, and hash value is significantly less than n1/3 then an attacker can construct a cube root over the integers whose most significant bits will validate as a correct signature, ignoring the actual key. To construct a forged signature that will validate against such implementations, an attacker simply needs to construct an integer whose most significant bytes have the correct format, including the hashed message, pad the remainder of this value with zeros or other garbage that will be ignored by the vulnerable implementation, and then take a cube root over the integers, rounding as appropriate.

Historical fact: This attack was discovered by Daniel Bleichenbacher, who presented it in a lightning talk at the rump session at the Crypto 2006 conference. At the time, many important implementations of RSA signatures were discovered to be vulnerable to this attack, including
OpenSSL. In 2014, the Mozilla library NSS was found to be vulnerable to this type of attack: https://www.mozilla.org/security/advisories/mfsa2014-73/.
Horridland is still using a broken implementation of signature verification; in fact, below is the code they are using.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ASN1_MAGIC = "003021300906052b0e03021a05000414"
def verify_rsa(sig_hex, message, public_key):
"""
Verifies an RSA signature.
inputs:
sig_hex: a digital signature, in hexadecimal
message: the message string to which sig_hex corresponds
public_key: the public verification key
(a Crypto.PublicKey.RSA._RSAobj value)
output: true or false
"""

sig_int = int(sig_hex , 16)
m_int = pow(sig_int, public_key.e, public_key.n)
m_hex = "%0512x" % m_int
h = SHA.new(message).hexdigest()
return re.match('0001f*' + ASN1_MAGIC + h, m_hex) is not None

Open part5_key.pub to find Malland’s public verification key. You want to tell Horridland to retreat, and make them believe that it’s a message from their ally Malland. Using the signature forgery technique described above, produce an RSA signature on “retreat immediately” that Horridland would accept.

Since 2010, NIST has specified that RSA public exponents must be at least 216 + 1. Briefly explain why Bleichenbacher’s attack would not work for these keys.

What to submit

  1. A Python 2.x script named part5.py that:
    • (a) Takes in two parameters:
      • i. the path to a file with a public key, and
      • ii. a message string.
    • (b) Prints a valid signature on the message under the given public key.
  2. A file named part5.txt containing your answer to the question above (why Bleichenbacher’s attack wouldn’t work with a high public verification exponent).

RSA in the Wild

Find one network protocol that uses RSA on the internet. Make sure to cite your source, and to specify the version of the protocol that you are talking about!

  1. A file named part6.txt containing the name and version of the network protocol that uses RSA on the internet, and a citation to your source.