MEGA Attack Explainer
I think I understand the attack at a high level but I’m still not sure on some details.<p>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?<p>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?