|
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. |
2. I think that's right. I keep making the point about q's size because it's part of why, in the successful RSA decryption case, the SID extracted is 0: our guess for q isn't zero, of course, but a giant chunk of the bits of m are going to be padding, because q doesn't come close to filling m.
3. This gets into the details of RSA-CRT, where you take m_p (mod p) and m_q (mod q). The m_q value, by definition, doesn't wrap the modulus q; it's less than q. :) I don't have a high-level way of explaining why this cancels out the qInv part of the calculation, though you can see it pretty clearly in the paper; it just works out that way algebraically (in a "ninth grader" sense) from the RSA-CRT equation.
And yeah, it's a number, "left padded" by a whole bunch of zeroes. That's what the paper means by "m is hiding in the padding" --- our guess for q is part of the decrypted message, and it isn't zero, but it doesn't land in the part of the message the Mega client tries to scoop the SID out of. If the Mega client had checked the padding, which is something you're absolutely supposed to do (also, you're supposed to use a real padding scheme, not just zeroes), you couldn't get away with this.
4. Yep, in this first attack, the whole point of faulting qInv is to create this difference of behavior.
And yeah, you should absolutely implement a model of this attack in Python or whatever. You don't need any of the networking stuff Mega is doing, or any of the encoding. It won't be hard! This is a pretty straightforward attack. I'll probably take a whack at it this weekend.
Later
I hadn't seen 'pbsd responded to this, but, of course, "what he said".