Been a while, oops.
Interestingly, there are not very many Set 5 writeups. There’s a lot of code for Set 5, but not very many explanations.
This is annoying. For some things, pure “code” is enough, e.g. “Implement Diffie-Hellman”. You can learn it by reading the code. For others, code really isn’t enough and needs a further explanation. That’s like saying “just read Spectre v1 PoC to understand how it works”.
I guess I’m just a mere mortal, but reading code is not sufficient for me for all purposes. Hopefully this is that explanation to other mortal people.
Set 5 Challenge 1 (Number 33): Implement Diffie-Hellman
Puzzle
For one of the most important algorithms in cryptography this exercise couldn’t be a whole lot easier.
Set a variable “p” to 37 and “g” to 5. This algorithm is so easy I’m not even going to explain it. Just do what I do.
Generate “a”, a random number mod 37. Now generate “A”, which is “g” raised to the “a” power mode 37 — A = (g**a) % p.
Do the same for “b” and “B”.
“A” and “B” are public keys. Generate a session key with them; set “s” to “B” raised to the “a” power mod 37 — s = (B**a) % p.
Do the same with A**b, check that you come up with the same “s”.
To turn “s” into a key, you can just hash it to create 128 bits of key material (or SHA256 it to create a key for encrypting and a key for a MAC).
Ok, that was fun, now repeat the exercise with bignums like in the real world. Here are parameters NIST likes:
p: ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024 e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd 3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec 6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f 24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361 c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552 bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff fffffffffffff g: 2
Solution
As I said in the intro, this is really just a matter of “do what you’re told”. Not much thinking to do, so not much explaining to do! Below is further discussion; move on if you’d like.
Further discussion
I’d like to comment that we use the naive method via exponentiation by squaring, partly because I’m lazy, and partly because the goal of this challenge is not to understand the “modexp” primitive, but the Diffie-Helleman primitive. Many other methods are discussed in the above link (I implemented Barrett’s, Wikipedia is a god-send.)
Being that this is a pretty core primitive, though, real applications don’t use the naive method. This is partially discussed in the Wiki link, but the main flaw is this line in the while loop, where runtime and also power consumption differ because of this if condition. Like I said here, variable time code leads to side-channels.
Set 5 Challenge 2 (Number 34): Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection
Puzzle
Use the code you just worked out to build a protocol and an “echo” bot. You don’t actually have to do the network part of this if you don’t want; just simulate that. The protocol is:
A->B
Send “p”, “g”, “A”
B->A
Send “B”
A->B
Send AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv
B->A
Send AES-CBC(SHA1(s)[0:16], iv=random(16), A’s msg) + iv
(In other words, derive an AES key from DH with SHA1, use it in both directions, and do CBC with random IVs appended or prepended to the message).
Now implement the following MITM attack:
A->M
Send “p”, “g”, “A”
M->B
Send “p”, “g”, “p”
B->M
Send “B”
M->A
Send “p”
A->M
Send AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv
M->B
Relay that to B
B->M
Send AES-CBC(SHA1(s)[0:16], iv=random(16), A’s msg) + iv
M->A
Relay that to A
M should be able to decrypt the messages. “A” and “B” in the protocol — the public keys, over the wire — have been swapped out with “p”. Do the DH math on this quickly to see what that does to the predictability of the key.
Solution
Let’s consider what Alice and Bob have as their public/private keys before encrypting their messages. Recall that, as in the previous challenge, the way Alice and Bob calculate their shared key is as such–
(p, g, a, A) (p, g, b, B)
Alice ---- p, g, A ------> Bob
Alice <--------- p, g, B ------- Bob
S == (A * B) % p S == (B * A) % p
Mallory simply changes it as such–
(p, g, a, A) (p, g, b, B)
Alice --- p, g, A ---> Mal --- p, g, p ----> Bob
Alice <-- p, g, p ---- Mal <-- p, g, B ----- Bob
S == (A * p) % p S == (B * p) % p
What happens to the shared secret S? Well, what happens to 3 * 7 % 7? 102 * 7 % 7?
<any damn value> * <second damn value> % <second damn value>? It goes to 0.
We might normally calculate S as A * B % p, but Mallory has forced us to compute A * p % p instead.
Coming back to the goal– decrypt the message– it is trivial. Because the message is in the format–
AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv
We know S == 0, and the iv is appended at the end of the ciphertext, we know all the necessary variables and we can trivially decrypt.
Set 5 Challenge 3 (Number 35): Implement DH with negotiated groups, and break with malicious “g” parameters
Puzzle
A->B
Send “p”, “g”
B->A
Send ACK
A->B
Send “A”
B->A
Send “B”
A->B
Send AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv
B->A
Send AES-CBC(SHA1(s)[0:16], iv=random(16), A’s msg) + iv
Do the MITM attack again, but play with “g”. What happens with:
g = 1 g = p g = p - 1Write attacks for each.
Solution
This is similar to the previous challenge, except whereas previously we modified the public key, in this challenge we modify the group parameter generator G. Our goal is to reverse engineer what S would be for the above 3 values of G.
Let’s do some simple math for the 3 cases. Keep our method for calculating S in mind–
S == (A * B) == (g ** a) * (g ** b)
Case 1: g = 1
S == (1 ** a) * (1 ** b)
S == 1
Boom. Broken. S is 1.
Case 2: g = P
Consider 4 mod 4.
What is 4**2 mod 4? What is 4**7 mod 4? 0.
For any a and p, it is simply that p ** a mod p == 0, since expanding the exponent (p * p * p * p ...) all ends up as 0.
Applied to our computation–
S == (P ** a) * (P ** b)
| |
| |
// This goes to 0 ... So does this!
S == 0
Boom. Broken. S is 0.
Case 3: g = P - 1
Consider instead 4 mod 5.
What would -1 mod 5 be? Equivalently, it would also be 4 mod 5, since -1 == 5(-1) + 4 (i.e. [-1] is in the same equivalence class)
Consider 5 mod 6. Or 6 mod 7. Or 12895 mod 12896. Would these all be congruent to [-1]?
Yes. For any (p-1) mod p, we can equivalently say it is the same as -1 mod p.
What about 16 mod 5? Or 64 mod 5? Or 256 mod 5?
These can all be rewritten as 4**2 mod 5, 4**3 mod 5, and 4**4 mod 5.
Or, applying our observation above, (-1)**2, (-1)**3, and (-1)**4.
In other words, for any p in (p-1)**n mod p, the statement is equivalent to -1 if n is odd, and 1 if n is even.
Applied to our computation–
S == ((P - 1)**a) * ((P - 1)**b)
S == ((P - 1)**(a + b))
S == ((-1)**(a + b))
// if (a + b) is even, S == 1
// if (a + b) is odd, S == -1
Knowing this, it is rather trivial to brute-force the 2 potential possibilities that S could be, so we can just decrypt using both values and see what we get, which is exactly what I do.
Set 5 Challenge 4 (Number 36): Implement Secure Remote Password (SRP)
Puzzle
To understand SRP, look at how you generate an AES key from DH; now, just observe you can do the “opposite” operation an generate a numeric parameter from a hash. Then:
Replace A and B with C and S (client & server)
C & S
Agree on N=[NIST Prime], g=2, k=3, I (email), P (password)
S
- Generate salt as random integer
- Generate string xH=SHA256(salt|password)
- Convert xH to integer x somehow (put 0x on hexdigest)
- Generate v=g**x % N
- Save everything but x, xH
C->S
Send I, A=g**a % N (a la Diffie Hellman)
S->C
Send salt, B=kv + g**b % N
S, C
Compute string uH = SHA256(A|B), u = integer of uH
C
- Generate string xH=SHA256(salt|password)
- Convert xH to integer x somehow (put 0x on hexdigest)
- Generate S = (B - k * g**x)**(a + u * x) % N
- Generate K = SHA256(S)
S
- Generate S = (A * v**u) ** b % N
- Generate K = SHA256(S)
C->S
Send HMAC-SHA256(K, salt)
S->C
Send “OK” if HMAC-SHA256(K, salt) validates
Solution
SRP has the super nice property of being a zero knowledge proof in that you’re proving knowledge of your password without sending it. Plus, if you squint super hard you can kinda see elements of Schnorr’s protocol in it. A great way to dip your toe in the water!
In any case, does this need a solution exactly? Kinda like the first challenge, this really is just an implementation whose algorithm they give you.
I’d say the “trickiest”" part was figuring out the libaries. I used hashlib and flask to simulate a client and server. But really, as simple as following instructions, though it definitely still took some time to work out the kinks.
Set 5 Challenge 5 (Number 37): Break SRP with a zero key
Puzzle
Get your SRP working in an actual client-server setting. “Log in” with a valid password using the protocol.
Now log in without your password by having the client send 0 as its “A” value. What does this to the “S” value that both sides compute?
Now log in without your password by having the client send N, N*2, &c.
Solution
This is where if you implemented your server properly in challenge 4, you’d have an easier time!
Let’s consider, as the challenge suggests, what happens when the server computes their shared secret S with the value A == 0.
S == (A * vᵘ)ᵇ % N
S == (0 * vᵘ)ᵇ % N
S == 0
Simple as that. S = 0. The public key the client sends is a simple multiplier on the other values!
Let’s express the equation slightly differently by just distributing the exponent and substituting for some values–
S == (A * vᵘ)ᵇ % N
S == (Aᵇ * v⁽ᵘ⁺ᵇ⁾) % N
S == (Aᵇ * C) % N // where C is just an integer, i.e. v⁽ᵘ⁺ᵇ⁾
Now let’s consider the other 2 cases– A == N, and A == 2*N. Look at what happens to our equation now–
S == (Aᵇ * C) % N
S == ((N)ᵇ * C) % N // A == N
S == ((2N)ᵇ * C) % N // A == 2N
S == ((N)ᵇ⁺¹ * C) % N // A == 2N
This is starting to look incredibly similar to case 2 from our solution above.
For any a and p, it is simply that
p ** a mod p == 0, since expanding the exponent (p * p * p * p ...) all ends up as 0.
Thus, as we learned in our previous challenge, the server’s shared secret will compute S == 0. Thus we can trivially determine HMAC-SHA256(K, salt) since K == SHA256(0) and the salt is public.
Boom. Broken!
Set 5 Challenge 5 (Number 38): Offline dictionary attack on simplified SRP
Puzzle
S
x = SHA256(salt|password) v = g**x % nC->S
I, A = g**a % nS->C
salt, B = g**b % n, u = 128 bit random numberC
x = SHA256(salt|password) S = B**(a + ux) % n K = SHA256(S)S
S = (A * v ** u)**b % n K = SHA256(S)C->S
Send HMAC-SHA256(K, salt)
S->C
Send “OK” if HMAC-SHA256(K, salt) validates
Note that in this protocol, the server’s “B” parameter doesn’t depend on the password (it’s just a Diffie Hellman public key).
Make sure the protocol works given a valid password.
Now, run the protocol as a MITM attacker: pose as the server and use arbitrary values for b, B, u, and salt.
Crack the password from A’s HMAC-SHA256(K, salt).
Solution
Since the challenge involves password cracking, I just used this password list. Being a toy example, my password is listed here.
The challenge tells us to reverse engineer the password given an HMAC. How might this be possible?
Let’s consider the math again. The key components are–
x = SHA256(salt | password)
v = g**x % n
S = (A * vᵘ)ᵇ % N
K = SHA256(S)
hmac = HMAC-SHA256(K, salt)
These steps could be able to be rewritten like a tree, where our leaf nodes terminate if they are “given” (since this is a MITM attack)–
HMAC
/ \
K salt // also given
/
S
/ | \
A vᵘ b // A, b are given since we act as the server
/ \
v u // u is given
|
x // g**x, but g is the group param
/ \
salt pass // for SHA256(salt | pass), where salt is given!
// what is pass?
Examining this tree, we can see every component that factors into the overal HMAC computation. We need A, b, u, salt, and pass.
We know b, u, and salt because we’re posing as the server (but also because we’re told that), but also A, since it is the client’s public key. How would we get pass?
Just guess and check! It’s precisely what I do. And that’s also precisely what normal cracking means, because people are uncreative. Use a password manager.
Especially if you use a bad password like I do above, it’s pretty simple. Boom, cracked.
Note: Astute readers will notice we do 2 computations of SHA256 per brute-force attempt. For a “real” person, who has knowledge of their password, they will only do this computation a handful of times. But for someone malicious and trying random inputs, it would be likely millions.
This observation that an honest party will do a computation only once is basically why password specific hashing functions exist– to make this hashing primitive take longer. Waiting 1 second instead of 0.01 seconds is tolerable for an honest party, but not for a brute-force attack. Cracking a full database already usually takes months or years as is, and increasing that factor by orders of magnitude is great for security (for the good guys!).
Set 5 Challenge 7 (Number 39): Implement RSA
Puzzle
There are two annoying things about implementing RSA. Both of them involve key generation; the actual encryption/decryption in RSA is trivial.
First, you need to generate random primes. You can’t just agree on a prime ahead of time, like you do in DH. You can write this algorithm yourself, but I just cheat and use OpenSSL’s BN library to do the work.
The second is that you need an “invmod” operation (the multiplicative inverse), which is not an operation that is wired into your language. The algorithm is just a couple lines, but I always lose an hour getting it to work.
I recommend you not bother with primegen, but do take the time to get your own EGCD and invmod algorithm working.
Now:
- Generate 2 random primes. We’ll use small numbers to start, so you can just pick them out of a prime table. Call them “p” and “q”.
- Let n be p * q. Your RSA math is modulo n.
- Let et be (p-1)*(q-1) (the “totient”). You need this value only for keygen.
- Let e be 3.
- Compute d = invmod(e, et). invmod(17, 3120) is 2753.
- Your public key is [e, n]. Your private key is [d, n].
- To encrypt: c = m ** e%n. To decrypt: m = c ** d%n
- Test this out with a number, like “42”.
- Repeat with bignum primes (keep e=3).
Finally, to encrypt a string, do something cheesy, like convert the string to hex and put “0x” on the front of it to turn it into a number. The math cares not how stupidly you feed it strings.
Solution
Not AGAIN, another implementation!
I joke. I very much believe that to be a good offensive security researcher, you must know how the defense is built, including various difficulties in building the defense. The vast majority of OpenSSL bugs are like two-thirds parsing bugs and memory errors.
I moan about implementation here because we’re straight up given the code and I don’t get to type as much :)
Still, it’s very valuable. Knowing RSA in and out will be critical next set.
One such detail for instance is that the message can’t be larger than the modulus N. This is somewhat obvious because if, say, m == N, the message “wraps around” and bits of the message are lost. That’s why often RSA is used in signatures, rather than actual message encryption (i.e. verifying authenticity, rather than confidentiality).
As the challenge suggests, I just use sympy to grab primes and a rather naive invmod implementation.
Set 5 Challenge 8 (Number 40): Implement an E=3 RSA Broadcast attack
Puzzle
Assume you’re a Javascript programmer. That is, you’re using a naive handrolled RSA to encrypt without padding.
Assume you can be coerced into encrypting the same plaintext three times, under three different public keys. You can; it’s happened.
Then an attacker can trivially decrypt your message, by:
- Capturing any 3 of the ciphertexts and their corresponding pubkeys
- Using the CRT to solve for the number represented by the three ciphertexts (which are residues mod their respective pubkeys)
- Taking the cube root of the resulting number
The CRT says you can take any number and represent it as the combination of a series of residues mod a series of moduli. In the three-residue case, you have:
result = (c_0 * m_s_0 * invmod(m_s_0, n_0)) + (c_1 * m_s_1 * invmod(m_s_1, n_1)) + (c_2 * m_s_2 * invmod(m_s_2, n_2)) mod N_012where:
c_0, c_1, c_2 are the three respective residues mod n_0, n_1, n_2 m_s_n (for n in 0, 1, 2) are the product of the moduli EXCEPT n_n --- ie, m_s_1 is n_0 * n_2 N_012 is the product of all three moduliTo decrypt RSA using a simple cube root, leave off the final modulus operation; just take the raw accumulated result and cube-root it.
Solution
If you’re like me, you might be wondering why the challenge just tells us to do these things. There’s enough name dropping for us to Google around, but still.
First– I was confused by the phrase “pubkey”. Because the pubkey is a tuple [e, n], “encrypting with three different public keys” can either a different e OR a different n. I somewhat assumed from the title “E=3” and the attack name that e was held constant. That’s something to note.
Most of this solution’s explanation is derived from here, which greatly helped me. Check it out!
First, consider what we have captured, and the Chinese Remainder Theorem (i.e. steps 1 and 2)
From step 1–
c₀ = mᵉ mod N₀
c₁ = mᵉ mod N₁
c₂ = mᵉ mod N₂
And the CRT–
Theorem. Let n0,n1,…,nr be positive integers such that gcd(ni,nj)=1 for i≠j. Then the system of linear congruences
x ≡ c₀ (mod N₀)
x ≡ c₁ (mod N₁)
x ≡ c₂ (mod N₂)
has a simultaneous solution which is unique modulo n0,n1,...nr
In other words, so long as our modulos are relatively prime, there exists some value x that satisfies our whole system of equations. To solve the CRT, we may use the following equation –
x ≡ c₀N₀d₀ + c₁N₁d₁ + ... + cᵣNᵣdᵣ (mod N)
where Nᵢ = N/nᵢ and dᵢ ≡ Nᵢ⁻¹ (mod nᵢ).
This is precisely where the computation of this result comes from. When people say “Use the CRT”, they really just mean use this above equation to solve this system of equations; thus we have–
x ≡ c₀N₀d₀ + c₁N₁d₁ + c₂N₂d₂ (mod N₀N₁N₂) ≡ c₀ (mod N₀)
≡ c₁ (mod N₁)
≡ c₂ (mod N₂)
But what precisely is x? Well– it’s just m**e or m**3, since c is equivalent in RSA to m ** 3! Just take the cube root to get the message!
… Is what many explanations say. But I want to go one step further. Why can’t we just take the cube root of c₀? After all, c₀ == (m₀ ** 3) as well, right? Why all this nonsense?
Consider 4ᵃ mod 5. If a == 3, the result would be 4 == (64) mod 5. We can’t take the cube root of that; we would just get nonsense (or I guess 1.587. But that’s not a meaningful answer).
And the reason we can’t just do that is because the result wraps around, and we don’t know how many times it wraps around.
In other words, when we look at the actual definition for “modulus”, we see the following–
In the case above–
a = n*q + r // r == a mod n
64 = 5*(12) + 4 // 4 == 64 mod 5
There is an implicit 12 here that “wraps around” such that our original value is lost. Thus, taking any root is useless. Again, obvious, but worth pointing out.
But what if it never wrapped around, i.e. if q == 0? If n were large enough that q would be 0? Say, 64 mod 128–
a = n*q + r
64 = 128*(0) + 64
Then, taking the cube root of 64, we get our original base of 4 because it never “wraps around”. Thus, we can make the following claim–
For
r = (aᵏ) mod n, a == root_k of r iff (aᵏ) < n
Again, super obvious. But worth repeating.
That’s essentially what many explanations mean in saying “m**3 < N”. They mean that the original value doesn’t wrap around, and thus, is retained. Applied to our problem–
You can see this by playing around with the message (e.g. here). Up to a certain length of message, the “trick” of taking some nth root doesn’t work.
By the way– as to my original question: “Why can’t we just take the cube root of c0”? You can, if the message is small enough. I do it here.
This, by the way, is pretty much why e == (2^16 + 1) is used instead, and also further why padding is used. Don’t use vanilla RSA!