7
$\begingroup$

I am looking at Wikepedia Galois Counter Mode article. I see this diagram enter image description here

I am trying to figure out where the IV works its way in. Is it used to initialize the counter? If so, how does a sequence of 12 bytes (96 bits)initialize a counter on a 32 bit machine?

$\endgroup$
  • 2
    $\begingroup$ Your 2nd question seems really strange to me, so I'm assuming I'm misunderstanding. It sounds like you are saying "because my computer has a 32 bit processor, and therefore 32 bit registers, etc. I don't understand how a 96 bit IV could be loaded into memory for processing." That isn't really your doubt, is it? $\endgroup$ – mikeazo Mar 5 '18 at 19:03
  • $\begingroup$ that depends on how it is used to initialize the counter. That is my doubt. As is written in the question, if the counter is initialized to a value x: x>2^32, then yes that is a potential concern for my application. Of course that all hinges on the answer to the first question $\endgroup$ – John Frye Mar 5 '18 at 19:07
7
$\begingroup$

The diagram shows the gist of the algorithm, but not everything in it.

The bulk of the encryption in GCM uses AES in CTR mode. "CTR mode" means that "successive" values of a counter are encrypted with the block function (the AES properly said) in order to yield a key-dependent pseudorandom stream which is combined (bitwise XOR) with the data to encrypt or decrypt. Each counter value thus has the size of a full block, which is 128 bits. Note that there is no requirement for the notion of "successive values" to match any given arithmetic model, in order to achieve security; we only need that the "successive values" are distinct. Of course, for encryption and decryption to work, sender and recipient must agree on the initial value and how to "increment" it in order to obtain the successive values, and that is defined in GCM.

The specification for GCM is NIST SP800-38D. In that document, we see the following:

  • While the counter value has the size of a block (16 bytes), only the last (rightmost) 4 bytes are modified to step into the "next value". The last 4 bytes are interpreted as a 32-bit integer (with big-endian convention), which is incremented. Note that the value conceptually "wraps around" (if the last 4 bytes have value FF FF FF FF, the increment yields 00 00 00 00, and the first 12 bytes of the block are kept untouched).

  • If the IV for GCM has size exactly 12 bytes, then the value "counter 0" in the Wikipedia schema is the concatenation of the IV, and 00 00 00 01. The value "counter 1" will be identical, except that the last byte will be 02 instead of 01. Note that the AES-encrypted value "counter 0" is used as post-processing for the authentication tag; the first counter value used to encrypt actual data is "counter 1".

  • If the IV for GCM has any other size, then it is first processed with GHASH, in order to yield a full 16-byte initial value for "counter 0". Note that, in that case, the GHASH output is also used for the last 4 bytes, so the starting value for the 32-bit integer is not necessarily 1 (and the "wrapping around" behaviour may actually happen, if we start close enough to FF FF FF FF).

In GCM, the AES block function is used for exactly three things:

  • To encrypt an all-zero block, to yield the h value (used in GHASH, for the authentication tag).
  • To encrypt the value "counter 0", used to mask the authentication tag.
  • To encrypt values "counter 1", "counter 2"... to produce the pseudorandom stream that is combined (with XOR) with the plaintext or ciphertext.

The details of GCM have been made such that, if the IV has length exactly 12 bytes, then all these values are guaranteed to be distinct to each other; the security of GCM depends on it. An important consequence is that if you use the AES/GCM key for anything else, then all security guarantees evaporate like dew in the morning sun.

It shall be noted that the use of the last four bytes as wrapping counter is not a universal convention. That is, it is defined that way in GCM and all GCM implementation follow it (otherwise they would not interoperate). However, other schemes that use CTR mode may have different conventions. In EAX and CCM, the full 16-byte block is considered to be the encoding of a complete 128-bit integer.

Computers are not limited to what can fit in a register, in exactly the same way that you have only ten fingers, but can still perform operations on numbers that contain several digits. On a 32-bit computer, you would use four 32-bit registers to hold the complete 128-bit value. See for instance how it is done in BearSSL implementation; the gist of the increment operation is as follows:

            cc0 ++;
            carry = (~(cc0 | -cc0)) >> 31;
            cc1 += carry;
            carry &= (~(cc1 | -cc1)) >> 31;
            cc2 += carry;
            carry &= (~(cc2 | -cc2)) >> 31;
            cc3 += carry;

The four 32-bit words are cc0, cc1, cc2 and cc3 (of type uint32_t, i.e. exactly 32 bits each). These weird expressions compute the carry propagation with branchless, constant-time code; a simpler (but not constant-time) implementation would look like this:

            cc0 ++;
            if (cc0 == 0) {
                cc1 ++;
                if (cc1 == 0) {
                    cc2 ++;
                    if (cc2 == 0) {
                        cc3 ++;
                    }
                }
            }

To be clear, I repeat that the code snippets above handle the EAX/CCM case, where the counter is incremented as a 128-bit value, not the GCM case, where only the last 4 bytes are incremented arithmetically.

| improve this answer | |
$\endgroup$
2
$\begingroup$

So the following describes GCM, from NIST SP-800 38D:

  1. Let $H = \operatorname{CIPH}_K(0^{128})$.
  2. Define a block, $J_0$, as follows:
    • If $\operatorname{len}(IV)=96$, then let $J_0 = IV || 0^{31} ||1$.
    • If $\operatorname{len}(IV)≠96$, then let $s = 128 \lceil\operatorname{len}(IV)/128\rceil-\operatorname{len}(IV)$, and let $J_0=\operatorname{GHASH}_H(IV||0^{s+64}||[len(IV)]_{64})$ (harder to understand, but not used for the default IV of 12 bytes).
  3. Let $C=\operatorname{GCTR}_K(\operatorname{inc}_{32}(J_0), P)$.
  4. to 7. are not applicable for this question

However, usually the IV is 96 bits / 12 bytes, so in that case the initial counter value $J_0$ is simply the IV, followed by 3 bytes valued zero and a byte valued 1, but increased with 1 for the CTR mode encryption (so make that last byte a byte valued 2).

The initial counter before it is increased is used to encrypt the output of the $\operatorname{GHASH}$ value to calculate the authentication tag as you can see in the picture.

So it's kind of tricky as the initial counter value (Counter 0) in that picture is FFFFFFFFFFFFFFFFFFFFFFFF00000001 instead of all-zero if the IV is, for instance all bytes with value 0xFF. Sometimes a key check value is used for a key which consists of the encryption of an all zero block of bytes, so it is kind of beneficial to security if it is defined this way, starting at 1 instead of 0. Otherwise an IV set to all zero bytes may leak part of the $\operatorname{GHASH}$ value.


Security warning: because of above only $2^{32} - 2$ blocks should be encrypted for a given key. Furthermore it is highly recommended to use a 12 byte IV, security issues have been found if the length of the IV is anything other than 96 bits.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.