# Recreating binary counter for arbitrary length arrays

After weeks of slaving over FIPS-197, I finally have my own working C/C# implementation of AES-128 which I'm quite happy about.

The next thing I'm looking to do is implement a nonce counter block of configurable length (either 8 or 16 bytes) to convert this block cipher into a stream cipher (CTR mode), according to NIST 800-38a recommendation.

So to do this, the idea I had was to create from scratch a sort of BigNumber implementation that basically reflects how we increment the bits in a byte, starting with the least significant bit:

0000
0001
0010
0011
0100
0101
0110
0111
1000
...


The concept is come up with the same counting system, incrementing each element in the array (starting with the last element), resetting the LSE ("least significant element") when it's at max and incrementing the previous element.

Here's what I came up with:

// Re-invent the byte using arbitrary length array (i.e. BigNumber)
// to increment 16-byte nonce

// Benchmark: 273,839 inc/s { 00, 04, 2D, AF } on ATmega328
void incBytes(byte *state, int i)
{
if (state[i] < 0xff)
{
state[i]++;
return;
}

state[i] = 0x00;

if (i == 0)
return;

i--;
incBytes(state, i);
}

void printBytes(byte *state, int len)
{
int i;
for (i = 0; i < len; i++)
{
printf("%02X ", state[i]);
}

printf("\n");
}

void test()
{
long t, count;
byte nonce[16];

fillBytes(nonce, 0, sizeof(nonce));
count = 0;
t = millis();
while (millis() - t < 1000)
{
// cipher(plaintext, expandedKey);
// cipherCtr(plaintext, expandedKey, nonce);
incBytes(nonce, sizeof(nonce) - 1);
count++;
}

Serial.print(count);
Serial.println(" inc/s (incBytes)");
dumpBytes(nonce, sizeof(nonce));
}


And here is a link to it in action at Ideone.

So I'd just like to get some feedback, not so much on the purpose of all of this or other alternatives out there, but if there are ways to improve it or if this is pretty much it :)

It will then provide me with a way to ensure that the Nonce block for AES-128 in CTR mode gets incremented properly (hence unique) using any arbitrary length byte array.

Note: This is for an Atmega328 so I would like to avoid using long long (64-bit integers) altogether.

• If it's 8 or 16 bytes, you shouldn't be stringing together bytes - string together uint64s. The overflow logic will operate much more quickly. – Reinderien May 18 '15 at 22:50
• Ah, I guess I should've this pointed out: This is for an Atmega328 (i.e. Arduino Uno) and I'm told that merely adding 1 to a uint64 can be a bit costly: forum.arduino.cc/index.php?topic=58697.msg422187#msg422187 – Matt Borja May 18 '15 at 22:54
• If you care about cost and you're on a microcontroller, your overflow logic should be implemented in assembly and check the carry flag. – Reinderien May 18 '15 at 22:55
• Ah, but I'm not quite ready for assembly just yet :) Will add a note to myself to look into it though... – Matt Borja May 18 '15 at 22:56
• Depending on your dev env, you might be able to access the carry flag from C directly. – Reinderien May 18 '15 at 22:57

## No check for end of array

incByte() doesn't check if i >= 0. So if all bytes are 0xff, it will happily start reading/writing to state[-1].

## Simplification

Actually, I would remove the recursion. If byte is of size 1 byte, you could also simplify the check for overflow past 0xff:

void incByte(byte *state, int i)
{
do {
if (++state[i] != 0)
return;
i--;
} while (i >= 0);
}

• Yeah, the no check for end of array I simply didn't include in my code but did add it later. However, regarding simplification, I just did a quick 1s benchmark test between my function (recursive) and yours and got the following results: recursive: 273452 inc/s (incBytes), last count: 04 2C 2C  vs. non-recursive: 244377 inc/s (incBytes2), last count: 03 BA 99. Does that sound right? – Matt Borja May 19 '15 at 5:45
• @MattBorja I modified the code, can you retest? I changed the loop to a do loop to move the end check to the bottom. – JS1 May 19 '15 at 6:22
• 269,366 inc/s, last count: 04 1C 36 - note I'm actually running this before any other tests now, which is seeing a slight improvement so your benchmark has been updated. Running the same test with the recursive version yields 274,006 inc/s, last count: 04 2E 56 with the highest recorded in the original post. – Matt Borja May 19 '15 at 6:38
• @MattBorja Don't know what to say. On my x86 desktop it is faster than the recursive version (but I'm not sure what optimizations GCC is doing). I have no idea what compiler you are using for your Atmega328 or what code it is generating. – JS1 May 19 '15 at 6:40
• Yeah, it's in the ballpark at this point, definitely appreciable improvement. I'm just using github.com/Robot-Will/Stino for adding Arduino compiler to SublimeText as far as that goes. – Matt Borja May 19 '15 at 6:43