[tptacek]

1. Yes: the RSA key (as encoded by Mega) is the tuple (p, q, d, qInv), and the only thing we corrupt is qInv. It doesn't matter (in this first attack) how we corrupt qInv! We flip any bit in an AES block that corresponds to where qInv would be in the encrypted key, so that when it's decrypted, the 16 bytes of that block are completely randomized. It doesn't matter what value qInv takes, and the value doesn't have to be consistent.

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".

[Moodles]

Thanks for the responses. I hope it was useful to go through. Yeah, I think the salient points are that the sid is not all 0 but mostly 0 in one case and Fermat's Little Theorem basically make the math work out. I suspect the authors thought of this clever attack because they were already thinking about fault attacks on RSA where perhaps similar concepts come up.

I predict with some confidence this will be made into a CTF soon if it hasn't already so we may as well work on the code now ;-)