**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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import java.math.BigInteger; import java.security.SecureRandom; public class SPECK { public int n; // Word size public int m; // # of key words public int T; // Number of rounds public BigInteger l[]; // Used in the key generation public BigInteger k[]; // Stores subkeys public BigInteger xm; // Encrypted x public BigInteger ym; // Encrypted y public int alpha, beta; // Number of shifts, function of n public static SecureRandom random = new SecureRandom(); // These are standard sizes for each of the values //n = {16,24,32,48,64}; //m = {4,3/4,3/4,2/3,2/3/4}; //T = {22,22/23,26/27,28/29,32/33/34} |

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*.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Constructor SPECK(int n, int m, int T){ this.n = n; this.m = m; this.T = T; // The size of k is actually specified k = new BigInteger[T]; /* * Two ways to approach 'l': * 1) Just store its value in an array large enough to holld it * 2) Use a circular index to wrap around since you only need a certain amount -- * its not being reused. Its only for key expansion. */ l = new BigInteger[2*T]; k[0] = new BigInteger(2*n,random); l[m-4] = new BigInteger(2*n,random); l[m-3] = new BigInteger(2*n,random); l[m-2] = new BigInteger(2*n,random); if (n == 16){ alpha = 7; beta = 2; } else{ alpha = 8; beta = 3; } } |

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! 😀

1 2 3 4 5 6 7 8 9 |
public void keyExpand(){ for(int i =0; i <= T-2; i++){ l[i+m-1] = unsign((k[i].add(unsign(cyclicRightShift(l[i],n,alpha)))).xor(new BigInteger("" + i))); k[i+1] = unsign(unsign(cyclicLeftShift(k[i],n,beta)).xor(l[i+m-1])); } } } |

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.

1 2 3 4 5 6 7 8 9 10 11 |
public void encrypt(BigInteger x, BigInteger y){ for(int i = 0; i <= T-1; i++){ x = unsign((cyclicRightShift(x,n,alpha).add(y)).xor(k[i])); y = unsign(cyclicLeftShift(y,n,beta).xor(x)); } xm = x; ym = y; System.out.println("Encrypt: " + x + " " + y); } |

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

1 2 3 4 5 6 7 8 9 |
public void decrypt(BigInteger x, BigInteger y){ for(int i =T-1; i >=0; i--){ y = unsign(cyclicRightShift(y.xor(x),n,beta)); x = unsign(cyclicLeftShift(unsign((x.xor(k[i]).subtract(y))),n,alpha)); } System.out.println("Decrypt: " + x + " " + y); } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Use this after subtractions or rotations to prevent getting negatives // This algorithm uses unsigned numbers, after all :D // Note: you need to work with the LARGEST number you can represent // in your space. This means 0xffff for ints. protected BigInteger unsign(BigInteger num) { return num.andNot(BigInteger.valueOf(-1).shiftLeft(n)); } // Returns all 1111... up to the size of L, the total number of bits. private BigInteger allOnes(int L) { return BigInteger.ZERO .setBit(L) .subtract(BigInteger.ONE); } // Left circular shift. Note that we have to use this instead of something // like Integer.rotateLeft() because we typically will store something smaller // than 'n' in a data type that can support it but we need to shift ONLY over // the size of 'n'. Example: int stores 32 bits, n is 16 bits. Wrap over the // 16 bits. private BigInteger cyclicLeftShift(BigInteger n, int L, int k) { return n.shiftLeft(k) .or(n.shiftRight(L - k)) .and(allOnes(L)); } private BigInteger cyclicRightShift(BigInteger n, int L, int k){ return (n.shiftRight(k).or(n.shiftLeft(L-k))).and(allOnes(L)); } |

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.