Loop unrolling posted May 2017

Reading cryptographic implementations, you can quickly spot a lot of weirdness and oddities. Unfortunately, this is because very few cryptographic implementations aim for readability (hence the existence of readable implementations). But on the other hand, there are a lot of cool techniques in there which are interesting to learn about.

Bit-slicing is one I've never really talked about, so here is a self-explanatory tweet quoting Thomas Pornin:

an example of the bitslicing technique to get constant time crypto code (from https://t.co/pz5aQs9iGR ) pic.twitter.com/UwJxEIgLlM

— David Wong (@lyon01_david) April 25, 2017

But I'm here to talk about loop unrolling. Here's what wikipedia has to say about it:

Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as the space-time tradeoff.

Want to see an example? Here's how Keccak was implemented in go

While the θ step could have easily fit in a loop:

for x := 0; x < 5; x++ {
    B[x] = a[x][0] ^ a[x][1] ^ a[x][2] ^ a[x][3] ^ a[x][4]
}

It was unrolled to allow for faster execution, getting rid of loop registers and checks for the end of the loop at every iteration:

// Round 1
bc0 = a[0] ^ a[5] ^ a[10] ^ a[15] ^ a[20]
bc1 = a[1] ^ a[6] ^ a[11] ^ a[16] ^ a[21]
bc2 = a[2] ^ a[7] ^ a[12] ^ a[17] ^ a[22]
bc3 = a[3] ^ a[8] ^ a[13] ^ a[18] ^ a[23]
bc4 = a[4] ^ a[9] ^ a[14] ^ a[19] ^ a[24]
d0 = bc4 ^ (bc1<<1 | bc1>>63)

Here is an implementation of MD5 in go. You can see that the gen.go file is generating a different md5block.go file which will be the unrolled code. Well yeah, sometimes it's just easier than doing it by hand :]

Here is an implementation of SHA-1 in assembly.

It's assembly, I'm not going to try to explain that.

Here's another example with Keccak in C. The unrolling is done in the preprocessing phase via C macros like this one:

#define REPEAT5(e) e e e e e

That's it! If you still haven't got it, you might have the qualities to run for president.

If you know more tricks let me know!