4 ms·

I think I understand the attack at a high level but I’m still not sure on some details. Could someone explain how the math works to provide the oracle? In part

I think I understand the attack at a high level but I’m still not sure on some details. Could someone explain how the math works to provide the oracle? In particular, the exact values the malicious server inserts as the encrypted sid and q^(-1), and why, if the guess for q is lower than the real q the plaintext sid the client sends back is 0, and why it’s not zero if the guess is higher? Am I right in thinking the attacker simply randomly flips a bit in q^(-1)? Why do they need to do this? Do they flip different bits on different guesses? And then how do they encode their guess for q in the encrypted sid? And why, exactly does this provide an oracle? How does the subsequent lattice search need only half as many guesses as binary search? Finally, does this attack require the victim to actually type their password in 512 times?

pelagicAustral 4y ago
This all is so deep, and I'm so sorry I cannot contribute to the questions you've got, but I feel like never coming back on account of "I know fuck all about this". Is this what people call 'Imposter syndrome'?
- schoen 4y ago
  Try https://www.cryptopals.com/ https://www.cryptopals.com/ or https://www.coursera.org/learn/crypto https://www.coursera.org/learn/crypto. There's a lot to know, but you can build up to it! One thing you'll learn about are oracle attacks, in which a bad protocol or implementation can leak secret data to the attacker bit-by-bit (sometimes literally bit-by-bit) in various ways. There are lots of those and they're sadly easy to create and a lot of progress in cryptographic engineering has been about finding ways to make sure oracle attacks can't occur in various real-world deployments.
tptacek 4y ago
I'll take a stab, but I'm keeping it fuzzy, not because I haven't worked the attack out at a low level but because I don't want you to know that I haven't worked the attack out at a low level. Some of this will be wrong. We're in the bizarre circumstance of being able to get our target to use a partially corrupted version of their own secret RSA key to decrypt a message of our choosing (this never happens! Only with Mega!). We're looking for q, one of two factors of our private key. We set m, the plaintext message we get to choose, to the middle of the range of possible q's. Remember, q is smaller than m; we've got a 2048 bit RSA key, and so q is 1024 bits; the client is effectively going to pad it out, and then blindly extract the 2nd though 45th bytes from it. What we're going to do resembles a fault attack (we're sort of simulating one by scrambling qInv). One of two things will happen: * If m < q, the message is going to miss our faulted qInv (it won't wrap the modulus for the q part of the CRT calculation, by definition, which cancels out the qInv part of the calculation) and thus decrypts properly. After padding and extraction, the client will pull 0's out of the decrypted message --- remember, q is much smaller than the whole message space of m, and remember, the client doesn't bother to check the padding! the number of things that went wrong here is bananas! --- and post it back. * If m >= q, our qInv fucks up the decryption; we decrypt (I assume) random gibberish, all the way through the space of m. We extract 43 bytes of the random gibberish, posting back a non-zero value. It's described in detail in III.B.2 of https://mega-awry.io/pdf/mega-malleable-encryption-goes-awry.pdf https://mega-awry.io/pdf/mega-malleable-encryption-goes-awry...
- Moodles 4y ago
  The fact that you also are a little fuzzy on the details gives me some confidence that I do in fact have some imposter syndrome ;) Thanks for your response. I understand it takes some work to parse these papers and I'm lazily just asking questions here instead of reading the paper myself, but I think I'm quite good at asking precise questions to get to the bottom of stuff, so I hope it will help others who stumble across this thread. > We're in the bizarre circumstance of being able to get our target to use a partially corrupted version of their own secret RSA key to decrypt a message of our choosing (this never happens! Only with Mega!). We overwrite the ciphertext of q^{-1} so that is fully corrupted (or at least, because it is ECB mode, a block of it is corrupted), right? By partially corrupted, do you mean "p and q are fine, but q^{-1} is not what it is supposed to be"? Does it matter how we corrupt q^{-1}? Is it just a bit flip in a single block? Do we have to corrupt it the same every time to make a new guess for q? > We set m, the plaintext message we get to choose, to the middle of the range of possible q's. Remember, q is smaller than m; I'm not quite following this part. To clarify, are you saying (roughly, I know RSA has some checks that q is not outrageously small) q lies in the interval [0, 2^1024] and we, on our first guess, set m = (2^1024 - 0)/2 = 2^1023? Then the adversary encrypts this guess m using the public key N from the client. m, when decrypted by the client at this point, could clearly be either larger or smaller than q, right? Our choice for m is literally in the middle. But the client also pads the resulting m, so it will certainly be larger than q? But to clarify, q is only (almost certainly) smaller than m because of the padding that the client adds? > * If m < q, the message is going to miss our faulted qInv I'm confused again, sorry. Is this m without the padding, right? Why, if m < q, does the RSA calculation not wrap around the modulus? I'm a bit confused how it pulls out only 0s, but this is probably related to my confusion at the last paragraph. Is it that it's that only 0s, but rather a small number followed by a ton of padding of 0s? > * If m >= q, our qInv fucks up the decryption; we decrypt (I assume) random gibberish The whole reason we fault qInv is so this case screws up while the other doesn't, right? And so it doesn't really matter how we fault qInv each time? This case faults because the calculation wraps around the modulus? It would be good to see the actual calculation and why this is which I think is my main struggle right now.
  - tptacek 4y ago
pbsd 4y ago
Look at how RSA CRT decryption works: m_1 = c^d_p mod p m_2 = c^d_q mod q h = (m_1 - m_2)*q^-1 mod p m = m_2 + h * m_1 If m < q, m_2 = m and there is nothing left to add. But if m >= q, there needs to be something to add, and this something will very likely be wrong and kind of random, because q^-1 mod p is wrong. The distinguisher between the two cases hinges on the upper bits of the decryption result being (non-)0. So for this attack to work all you have to do is change any part of q^-1; it doesn't really matter much what the change is. Now you have a binary search oracle for q, from which you can iteratively obtain the most significant bits of q, one guess at a time (e.g., try m = 2^1024 first, then (2^1024 or 0) + 2^1023, etc). Once you have half of the most significant bits of q, you can use the Coppersmith method [1] to find a small root of f(x) = msb(q) + x modulo a divisor of n and thus recover the rest of q. In reality doing exactly 512 iterations of guessing plus Coppersmith is pretty costly; if possible, guessing a few more bits will make the Coppersmith step much faster. [1] https://en.wikipedia.org/wiki/Coppersmith_method https://en.wikipedia.org/wiki/Coppersmith_method
- Moodles 4y ago
  Pretty elucidating, thanks. Could you just elaborate on the part: > If m < q, m_2 = m and there is nothing left to add. Why is this? What is d_p? d mod p?
  - pbsd 4y ago
    There is nothing left to add because m_2 is already the correct value: - If m is also < p, then (m_1 - m_2) is obviously 0, and so will be h. - If m >= p, then m must be of the form m_1 + k * p for some k. But we've already established that m = m_2, so m_1 - m_2 = (m - k * p) - m_2 = -k * p = 0 mod p. Thus h = 0. So regardless of the value of qinv, we get m verbatim if it's less than q. d_p and d_q are d mod (p-1) and d mod (q-1) respectively. Here, this Sage script is short enough that it all fits in a comment. I guess 624 bits and recover the remaining 400 with Coppersmith; this is fast enough to run in a few seconds. def oracle(c, d, p, q, qinv): m_1 = power_mod(c, d % (p-1), p) m_2 = power_mod(c, d % (q-1), q) h = (m_1 - m_2)*qinv % p m = m_2 + h * m_1 return (m >> (211*8)) != 0 # check if sid != 0 # Setup p = random_prime(2^1024, lbound=2^1023+2^1022) q = random_prime(2^1024, lbound=2^1023+2^1022) n = p*q e = 65537 d = inverse_mod(e, (p-1)*(q-1)) qinv = inverse_mod(q, p) + randint(0, 2^128) # random error block inserted in the least significant 128 bits msb_q = 0 for bit in reversed(range(400, 1024)): # if m < q, we are within range if not oracle(power_mod(msb_q + 2^bit, e, n), d, p, q, qinv): msb_q += 2^bit # Find a small root of msb_q + x modulo a divisor of n of size ~n^(1/2) P.<x> = Zmod(n)[] f = msb_q + x [lsb_q] = f.small_roots(beta=0.49, epsilon=1/32) # Check we've reached the correct solution assert(q == msb_q + lsb_q)

pelagicAustral 4y ago

This all is so deep, and I'm so sorry I cannot contribute to the questions you've got, but I feel like never coming back on account of "I know fuck all about this". Is this what people call 'Imposter syndrome'?

schoen 4y ago
Try https://www.cryptopals.com/ https://www.cryptopals.com/ or https://www.coursera.org/learn/crypto https://www.coursera.org/learn/crypto. There's a lot to know, but you can build up to it! One thing you'll learn about are oracle attacks, in which a bad protocol or implementation can leak secret data to the attacker bit-by-bit (sometimes literally bit-by-bit) in various ways. There are lots of those and they're sadly easy to create and a lot of progress in cryptographic engineering has been about finding ways to make sure oracle attacks can't occur in various real-world deployments.

tptacek 4y ago

I'll take a stab, but I'm keeping it fuzzy, not because I haven't worked the attack out at a low level but because I don't want you to know that I haven't worked the attack out at a low level. Some of this will be wrong. We're in the bizarre circumstance of being able to get our target to use a partially corrupted version of their own secret RSA key to decrypt a message of our choosing (this never happens! Only with Mega!). We're looking for q, one of two factors of our private key. We set m, the plaintext message we get to choose, to the middle of the range of possible q's. Remember, q is smaller than m; we've got a 2048 bit RSA key, and so q is 1024 bits; the client is effectively going to pad it out, and then blindly extract the 2nd though 45th bytes from it. What we're going to do resembles a fault attack (we're sort of simulating one by scrambling qInv). One of two things will happen: * If m < q, the message is going to miss our faulted qInv (it won't wrap the modulus for the q part of the CRT calculation, by definition, which cancels out the qInv part of the calculation) and thus decrypts properly. After padding and extraction, the client will pull 0's out of the decrypted message --- remember, q is much smaller than the whole message space of m, and remember, the client doesn't bother to check the padding! the number of things that went wrong here is bananas! --- and post it back. * If m >= q, our qInv fucks up the decryption; we decrypt (I assume) random gibberish, all the way through the space of m. We extract 43 bytes of the random gibberish, posting back a non-zero value. It's described in detail in III.B.2 of https://mega-awry.io/pdf/mega-malleable-encryption-goes-awry.pdf https://mega-awry.io/pdf/mega-malleable-encryption-goes-awry...

Moodles 4y ago
The fact that you also are a little fuzzy on the details gives me some confidence that I do in fact have some imposter syndrome ;) Thanks for your response. I understand it takes some work to parse these papers and I'm lazily just asking questions here instead of reading the paper myself, but I think I'm quite good at asking precise questions to get to the bottom of stuff, so I hope it will help others who stumble across this thread. > We're in the bizarre circumstance of being able to get our target to use a partially corrupted version of their own secret RSA key to decrypt a message of our choosing (this never happens! Only with Mega!). We overwrite the ciphertext of q^{-1} so that is fully corrupted (or at least, because it is ECB mode, a block of it is corrupted), right? By partially corrupted, do you mean "p and q are fine, but q^{-1} is not what it is supposed to be"? Does it matter how we corrupt q^{-1}? Is it just a bit flip in a single block? Do we have to corrupt it the same every time to make a new guess for q? > We set m, the plaintext message we get to choose, to the middle of the range of possible q's. Remember, q is smaller than m; I'm not quite following this part. To clarify, are you saying (roughly, I know RSA has some checks that q is not outrageously small) q lies in the interval [0, 2^1024] and we, on our first guess, set m = (2^1024 - 0)/2 = 2^1023? Then the adversary encrypts this guess m using the public key N from the client. m, when decrypted by the client at this point, could clearly be either larger or smaller than q, right? Our choice for m is literally in the middle. But the client also pads the resulting m, so it will certainly be larger than q? But to clarify, q is only (almost certainly) smaller than m because of the padding that the client adds? > * If m < q, the message is going to miss our faulted qInv I'm confused again, sorry. Is this m without the padding, right? Why, if m < q, does the RSA calculation not wrap around the modulus? I'm a bit confused how it pulls out only 0s, but this is probably related to my confusion at the last paragraph. Is it that it's that only 0s, but rather a small number followed by a ton of padding of 0s? > * If m >= q, our qInv fucks up the decryption; we decrypt (I assume) random gibberish The whole reason we fault qInv is so this case screws up while the other doesn't, right? And so it doesn't really matter how we fault qInv each time? This case faults because the calculation wraps around the modulus? It would be good to see the actual calculation and why this is which I think is my main struggle right now.
- tptacek 4y ago

pbsd 4y ago

Look at how RSA CRT decryption works: m_1 = c^d_p mod p m_2 = c^d_q mod q h = (m_1 - m_2)*q^-1 mod p m = m_2 + h * m_1 If m < q, m_2 = m and there is nothing left to add. But if m >= q, there needs to be something to add, and this something will very likely be wrong and kind of random, because q^-1 mod p is wrong. The distinguisher between the two cases hinges on the upper bits of the decryption result being (non-)0. So for this attack to work all you have to do is change any part of q^-1; it doesn't really matter much what the change is. Now you have a binary search oracle for q, from which you can iteratively obtain the most significant bits of q, one guess at a time (e.g., try m = 2^1024 first, then (2^1024 or 0) + 2^1023, etc). Once you have half of the most significant bits of q, you can use the Coppersmith method [1] to find a small root of f(x) = msb(q) + x modulo a divisor of n and thus recover the rest of q. In reality doing exactly 512 iterations of guessing plus Coppersmith is pretty costly; if possible, guessing a few more bits will make the Coppersmith step much faster. [1] https://en.wikipedia.org/wiki/Coppersmith_method https://en.wikipedia.org/wiki/Coppersmith_method

Moodles 4y ago
Pretty elucidating, thanks. Could you just elaborate on the part: > If m < q, m_2 = m and there is nothing left to add. Why is this? What is d_p? d mod p?
- pbsd 4y ago
  There is nothing left to add because m_2 is already the correct value: - If m is also < p, then (m_1 - m_2) is obviously 0, and so will be h. - If m >= p, then m must be of the form m_1 + k * p for some k. But we've already established that m = m_2, so m_1 - m_2 = (m - k * p) - m_2 = -k * p = 0 mod p. Thus h = 0. So regardless of the value of qinv, we get m verbatim if it's less than q. d_p and d_q are d mod (p-1) and d mod (q-1) respectively. Here, this Sage script is short enough that it all fits in a comment. I guess 624 bits and recover the remaining 400 with Coppersmith; this is fast enough to run in a few seconds. def oracle(c, d, p, q, qinv): m_1 = power_mod(c, d % (p-1), p) m_2 = power_mod(c, d % (q-1), q) h = (m_1 - m_2)*qinv % p m = m_2 + h * m_1 return (m >> (211*8)) != 0 # check if sid != 0 # Setup p = random_prime(2^1024, lbound=2^1023+2^1022) q = random_prime(2^1024, lbound=2^1023+2^1022) n = p*q e = 65537 d = inverse_mod(e, (p-1)*(q-1)) qinv = inverse_mod(q, p) + randint(0, 2^128) # random error block inserted in the least significant 128 bits msb_q = 0 for bit in reversed(range(400, 1024)): # if m < q, we are within range if not oracle(power_mod(msb_q + 2^bit, e, n), d, p, q, qinv): msb_q += 2^bit # Find a small root of msb_q + x modulo a divisor of n of size ~n^(1/2) P.<x> = Zmod(n)[] f = msb_q + x [lsb_q] = f.small_roots(beta=0.49, epsilon=1/32) # Check we've reached the correct solution assert(q == msb_q + lsb_q)