Goals
Advance knowledge of cryptography and hashing by working through example exercises and then trying to exploit some vulnerable systems.
RSA is one of the most widely-used public-key cryptosystems in the world. It’s composed of three
algorithms: key generation (Gen), encryption (Enc), and decryption (Dec). In RSA, the public key is
a pair of integers (e, N), and the private key is an integer d.
The key pair is generated by the following steps:
- Choose two distinct big prime numbers with the same bit size, say p and q.
- Let N = p ∗ q , and φ(N) = (p − 1) ∗ (q − 1) .
- Pick up an integer e , such that 1 < e < φ(N) and gcd(e, φ(N)) = 1 .
- Get the modular inverse of e : d ≡ e −1 mod φ(N) (i.e., d ∗ e ≡ 1 mod φ(N)).
- Return (N, e) as the public key, and d as the private key. Enc - To encrypt integer m with the public key (N, e), the cipher integer c ≡ m^e mod N. Dec - To decrypt cipher integer c with private key d, the plain integer m ≡ c^d mod N.
Analysis
Can I Have Some Salt With My Password?
- Is the hash of the salted password still vulnerable? Why or why not?
Given the hash of the salted password, it is still considered vulnerable because the salt value is another random password from the same list of common passwords.
- What steps could be taken to enhance security in this situation?
In order to enhance the security in this situation, instead of using a salt value from the same list of common passwords, one can simply keep the salt value secret and make the salt value a large bit size value.
Attack A Small Key Space
- What steps did you follow to get the private key?
Given a unique RSA public key (n), with a fairly small key size of 64 bits, the first step is to find its factors (p and q). To do this task, it was needed to compute the factor of n efficiently since n is quite a large number. First, given the property of “If a number n has a prime factor larger than n, then it surely has a prime factor smaller than n” is true. Therefore, it is enough to look for the prime factors in the range of [1, n], and then compute the prime factors in the range of [n, n]. Second, given the n, all we have to do is try dividing n by odd numbers starting at floor(n) and going down until we get an integer result. Third, after finding such prime, we know that n is in reality the product of two prime factors (p and q), so we can compute q by simply dividing n and p. The second step is to get the private key from the prime factors p, q, and e, which are given in the JSON file. To do this task, it was needed to compute the totient function (n), which is (p - 1)*(q - 1). Then, compute the private key by computing the extended euclidean algorithm given the totient function and e. it should be noted that, while computing the private key, if the private key is negative, then in order to make it positive, it is needed to add the totient function value to still satisfy the function, such that ed = 1 mod n.
Where’s Waldo
- What makes the key generated in this situation vulnerable?
Given the fact that our unique RSA public keys were generated with a vulnerable RNG in the same system, according to the paper “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices”, it is possible that our public keys share non-trivial common factors due to entropy problem. In this case, to get the private key, the following steps were taken. First, since we know that the public keys were generated by a vulnerable RNG and that the public keys share nontrivial common factors, we can compute the factor by the greatest common denominator of my public key (n1) and my classmate’s public key (n2). If the greatest common denominator is not 1, we can assume that we have found the classmate that shares the same common factors, and therefore we can use the classmate’s public key to get my private key. Second, with both public keys on hand, we can compute the prime factor with both keys. Having the prime factor (q), the next steps are very non-trivial, since we know that we can calculate the other prime by dividing n1 and q.
- What steps did you follow to get the private key?
We can compute the totient function (n), which is (p - 1)*(q - 1). Then, compute the private key by computing the extended euclidean algorithm given the totient function and e, which is given in the JSON file. it should be noted that, while computing the private key, if the private key is negative, then in order to make it positive, it is needed to add the totient function to still satisfy the function, such that ed = 1 mod n.
Broadcast RSA Attack
- How does this attack work?
This attack worked because the same message is sent to several recipients using their public keys. Therefore, it does not use any randomness, which is the key to the attack. In addition, it also uses a small public exponent (e), which makes this attack work in an efficient manner.
- What steps did you follow to recover the message?
Given three different 1024 bit RSA public keys, resulting in three different encrypted messages, with the public exponent e being 3, and having the three pairs of public keys associated with the encrypted messages, we can recover the original message by following the next steps. We know that C1 = m^3 mod N1, C2 = m^3 mod N2, and C3 = m^3 mod N3. Because of this, we know that the greatest common divisor of any two different public keys is equal to 1. If some two public keys are not coprime, then we can factor each of them and decrypt the messages. To decrypt the messages, we can use the Chinese Remainder Theorem, to construct such C, which is a remainder modulo of the product of these three N1, N2, and N3, that has the same remainder modulo N1 and C1, the same remainder modulo N2 and C2, and the same remainder modulo N3 and C3. After computing such C, it turns out that it is equal to m^e mod N1N2N3. With that in mind, we can just decode the message by taking the cube root (because e is 3) of C and round up to the closest integer.