Security代写：CS588AttackingRSA

不正确的使用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:
  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.
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.
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.