Tuesday, December 13, 2005

Blogging is strange. You write down a few lines of half-coherent something under the delusion that nobody is reading the blog, and out of a sudden you show up cross-referenced in blogs that you read yourself regularly. With such a large crew blogging at Matasano (what used to be Thomas Ptacek's blog) they have a blog-update-frequency that leads to their blog being about as productivity-destructive as slashdot.

I am seriously flattered to be mentioned there (and scared that my rants are actually read).

One of today's posts there mentions DJB's crypto algorithms, specifically Salsa20. Now, I am not a cryptographer, but I do not trust Salsa, for a variety of reasons:
  • It looks too much like MD4/MD5.
  • We have very limited understanding on why a wild mixture of ADD/XOR/ROL would produce equation systems that are hard to solve. Yes, nonlinearity over GF(2)^32 and over Z/2^32Z are given by mixing boolean functions and addition, but this paper gives some pretty neat insight into how just mixing ADD/XOR (without the ROL) is trivially solvable. I don't trust a single rotation that much.
  • Avoiding integer multiplication (whose representing BDD can grow exponentially with the number of bits and is thus hard to model using the methods in the paper) is something which I would not do - I know DJB cares a lot about timing, but given the choice of potentially leaking a few cycles and making the output of an operation ridiculously complicated (while at the same time tackling the problem of weak differential propagation in the high-order bits) I chose the latter.
  • DJB might be over-emphasizes timing. His AES S-Box stamps RDTSC output into packets, which is many orders of magnitudes more precise than any measurement you will get IMHO. True, caching issues (and cache alignment issues) can easily eat up 100 cycles, but that is still a lot less than a timer tick, the measure that in the most optimistic scenarios you'd be likely to get.
All in all, I do not trust systems built on just mixing ADD/XOR/ROL. There is a reason for the name of this blog.

No comments: