Month: November 2014

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.

Fellowships!

For the last few months, I’ve been very focused on trying to submit successful fellowship applications. My main targets are ones that are big in computer science & computer engineering: Microsoft Research, Facebook( not done yet), NSF, NDSEG (not done yet), … etc.

It has been quite exhausting, to say the least. Writing a fellowship application that mandates a personal statement is a mentally taxing experience because you are being forced to constantly sell yourself at every point along the way. I’ve always found this a little difficult because I’m the type of person who tends to avoid overestimating my ability to force myself to keep working. A bit of mental trickery, if you would; as such, I’ll often downplay praise or avoid the spotlight to avoid a growing ego. The goal of the statements isn’t to encourage that sentiment, of course, but to make you create a three-dimensional version of yourself from your written word. But that’s certainly difficult for me because I hate to sound like I’m bragging while understanding that, yes, you must sell yourself or be doomed to go home hat in hand.

The research statements are quite easy since I’ve been working at this for a while and generally have a good grasp of what it is I’m trying to accomplish, what I can do in ‘x’ amount of time, and why the problem is worth solving (hint: all research problems are worth solving with the right marketing campaign).

So far, I’ve done:

  • Microsoft Research
  • NSF GRFP
  • Qualcomm Innovation Fellowship

In that order. The MSR one was a good preparation for the GRFP since it forced me to get a research plan draft done very early that was in excess of the GRFP requirements (5 pages versus 2 pages). So most of my work went into advertising myself in the research statement :D.

Qualcomm was a little different. This fellowship is only open to certain universities that Qualcomm gets a lot of work from. WINLAB, certainly, does a lot of work with them on the Communications front; Dr. Lu in our solid state department works on hardware with them. The research proposal required a team component, so I worked with Xianyi Gao in my lab and produced a research plan on crowdsourcing that I’m hoping will appeal to the team over there given that Qualcomm had a high profile purchase of a crowdsourcing platform last year. The work is fairly novel and would answer some interesting questions so fingers crossed to at least be a finalist!

The next fellowship coming up is the Ford Foundation. This is certainly a prestigious fellowship as well, but their mission statement is about increasing diversity in higher education. From what I’ve seen of previous winners, not many were caucasians studying computer science topics like I am. 😀 I am not dissuaded, however, since my commitment to increasing diversity is what matters and I am actually proactive in this area. I have to spin a nice story with the research plan and make it more human and relatable, which is actually a great thing to be doing anyway! Really looking forward to this. 🙂