Thursday, March 11, 2010

Threefish encryption

For one of my classes, I'm trying to figure out how to make hardware acceleration for the Threefish cipher. As step one of this, I had to actually figure out how to calculate it. That was surprisingly hard. Threefish may be state-of-the-art, really hot stuff, but there are no clearly written programs that show how you calculate it. There are some programs written for greasy-fast speed, and some programs written for smallness, but none that are actually clear about what it is they're doing.

So I had to write my own, obviously. I went to the submission to NIST, which explains Threefish clearly, but puts everything in a very mathematical notation that is quite unlike most programming languages. So I took the description in the NIST document and translated that as closely as possible into Haskell code, which resulted in a small, elegant, correct program that would have taken days to actually finish a single calculation.

The problem is that the mathematical description has about the same performance characteristics as the naive Fibonacci function, i.e. it explodes exponentially. This was fixed through a really dirty trick: I added some list indirection to get Haskell to memoize values. I would tell more about it, but I'm still not entirely sure what I did myself.

Anyway, triumph! Hurrah! The code is here. Be warned, it's pretty rough.