Recreating binary counter for arbitrary length arrays

Question

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.

Answer 1

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);
}