# 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. Commented May 18, 2015 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 Commented May 18, 2015 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. Commented May 18, 2015 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... Commented May 18, 2015 at 22:56
• Depending on your dev env, you might be able to access the carry flag from C directly. Commented May 18, 2015 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? Commented May 19, 2015 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
Commented May 19, 2015 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. Commented May 19, 2015 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
Commented May 19, 2015 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. Commented May 19, 2015 at 6:43