Hacker News new | past | comments | ask | show | jobs | submit login

If you want to learn the math, check out http://www.amazon.com/Introduction-Mathematical-Cryptography....



I like this book a lot, but you won't need any of this math until set 8. I spent a lot of term learning things like lattice basis reduction algorithms (I used Strang's linear algebra book and MIT lectures) only to discover that there really isn't a whole lot that requires you to break out linear algebra in day-to-day cryptography.

In particular: virtually all of block cipher crypto and message authentication relies on straightforward math. (It would be different if our challenges covered poly MACs, but we don't have good examples of common flaws in poly MAC implementations).


Nonce reuse? It usually gets you at least forgeries, and in GCM's case it even gets you key recovery.

I agree that the published sets of challenges don't really need much theory.


Are you referring to Joux here? Is the math for that really complicated? (I haven't tried to implement it.)

Later: I just read Ferguson, with the linear algebra.


Yeah. Joux's attack is conceptually simple. You have 2 tags T_0, T_1, obtained with distinct messages and the same IV. This means T_0 = S_0 ^ X and T_1 = S_1 ^ X, where X is the same value for both. So you have T_0 ^ T_1 = S_0 ^ S_1. S_0 and S_1 are the polynomial evaluation of the ciphertext at H, the authentication key (which is also the same).

Now, via a simple polynomial evaluation property, you have f(x) + g(x) = (f + g)(x). We know f and g --- those are the two ciphertexts being authenticated here, interpreted as polynomials --- and we know that the polynomial f + g - S_0 - S_1 must be 0 at H. From there it's a matter of finding the roots of this polynomial, one of which is H, and this is the mathematically complicated part of the attack. Though you can treat root-finding as a black-box, the keywords here are Berlekamp or Cantor-Zassenhaus.

(Hopefully I didn't get this too wrong, I'm handwaving here)


Can you imagine how much more insufferable I'm going to be once I have worked examples of these attacks? ;)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: