How does libgcrypt increment the counter for CTR mode?

Question

I have a file encrypted with AES-256 using libgcrypt's CTR mode implementation. I want to be able to decrypt the file in parts (e.g. decrypting blocks 5-10 out of 20 blocks without decrypting the whole file).

I know that by using CTR mode, I should be able to do it. All I need is to know the correct counter. The problem lies in the fact that all I have is the initial counter for block 0. If I want to decrypt block 5 for example, I need another counter, one that is achieved by doing some action on the initial counter for each block from 0 to 5.

I can't seem to find an API that libgcrypt exposes in order to calculate counter for later blocks given the initial counter.

How can I calculate the counter of later blocks (e.g. block #5) given the counter of block #0?

Socorrosocotra

Answer 1

When in doubt, go to the source. Here's the code in gcrypt's generic CTR mode implementation (_gcry_cipher_ctr_encrypt() in cipher-ctr.c) that increments the counter:

for (i = blocksize; i > 0; i--)
  {
    c->u_ctr.ctr[i-1]++;
    if (c->u_ctr.ctr[i-1] != 0)
      break;
  }

There are other, more optimized implementations of counter incrementing found in other places in the libgcrypt source, e.g. in the various cipher-specific fast bulk CTR encryption implementations, but this generic one happens to be nice and readable. (Of course, all those alternative implementations need to produce the same sequence of counter values anyway, so that gcrypt stays compatible with itself.)

OK, so what does it actually do?

Well, looking at the context (or, more specifically, cipher-internal.h), it's clear that c->u_ctr.ctr is an array of blocksize unsigned bytes (where blocksize equals 16 bytes for AES). The code above increments its last byte by one, and checks if the result wrapped around to zero. If it didn't, it stops; if it did wrap, the code then moves to the second-to-last byte, increments it, checks to see if it wrapped, and keeps looping until it either finds a byte that doesn't wrap around when incremented, or it has incremented all of the blocksize bytes.

So, for example, if your original counter value was {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, then after incrementing it would become {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}. If incremented again, it would become {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2}, then {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3}, and so on up to {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,255}, after which the next counter value would be {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0} (and after that {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3}, etc.).

Of course, what this is really doing is just arithmetically incrementing a single (blocksize × 8)-bit integer, stored in memory in big-endian byte order.

Emera

Hi Ilmari Karonen. Thank you very much for your very detailed answer. It helped me a lot, and I've achieved exactly what I was trying to do! BTW, I can't vote yet but I did press the vote up button :) – Socorrosocotra

@Socorrosocotra As you can see I've asked for migration to SO (I'm a new mod at SO, still learning the ropes). As you now have > 15 points here you should be able to vote. But other than voting, if an answer solved your question then you should accept it by hitting the V button on the left of the message. – Maxama

@Maarten, Thank you for the information. I've checked Ilmari answer as the one that solved my problem. Thank you guys – Socorrosocotra