NSA’s SPECK Block Cipher in Java

Edit: Updated to work with BigIntegers of arbitrary bit size.

I was going about, trying to run my own timing analysis of NSA’s new block ciphers — SIMON and SPECK — and I couldn’t find any easy Java implementations for them. I had thought that by this time that Bouncycastle would have added it to their library but alas they did not. I went ahead to implement myself and was quickly reminded of how different things are when you work at the bit level!

My main trouble here was: 1) properly handling the bit operations, 2) my Java 7’s lack of unsigned integers!!! (fixed in Java 8, oh how far we have come~).

First, the implementation is based off of: https://eprint.iacr.org/2013/404.pdf , the original paper.

Start with the definitions:

So that’s the standard stuff.
Move to a constructor. Note that there are standard sizes seen above as comments; the checking for this hasn’t been programmed but it seems like a couple of switch statements. I left it up to the user to decide because lazy.

Constructor! Pretty straightfoward. Note that there are only two pairs of values for the shifting constants, alpha and beta.
I lazily constructed a large array for l, but if there are memory concerns I wrote a second way to do it. The values aren’t reused; you could just store as little as 3 values and get away with it! 😀

Key expansion! This is shown in two ways in the paper: inside and outside the algorithm. I opted for outside. The round function uses circular shift functions. We’ll get into what unsign and the cyclic shifting functions are further down.

The encryption function. Implemented exactly as seen in the paper.

Decryption! In the paper, they do x first and y second when describing the inverse. I find it’s easier to do something like this instead:
1. Do the reassignment for y first.
2. Follow through with x.

So reversing the encryption gives:

x = (rightShift(x,alpha) + y) ^ k[i];
x ^ k[i] = rightShift(x,alpha) + y
(x ^ k[i]) – y = rightShift(x,alpha)
leftShift((x ^ k[i]) – y,alpha) = x

which is what we see up there.

OK, unsign, leftCyclicalShift, and rightCyclicalShift. This is explained in the comments but I’ll reiterate here:
unsign: This is needed because Java doesn’t have unsigned integers. Doing a logical AND with 11111…., the highest representation of the BigInteger, will reverse the value back from negative to positive. This needs to be done after rotations and subtractions.

leftShift & rightShift — I got into a lot of trouble using Integer.rotateLeft and Integer.rotateRight from the JDK prior to switching off to BigInteger. The problem is the number of bits in the specified word is not the same as an integer — you have to rotate on the number of bits you’re USING in your word size, not the number of bits in the integer. This problem exists doubly in BigInteger; the data size is infinite so doing rotations is tricky. You need to eliminate anything larger than your thing and move it over.

So that’s it.
I’ll probably do a simple SIMON implementation in Java as well in the coming days.