IV in Galois Counter Mode I am looking at Wikepedia Galois Counter Mode article. I see this diagram


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?
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)) &gt;&gt; 31;
            cc1 += carry;
            carry &amp;= (~(cc1 | -cc1)) &gt;&gt; 31;
            cc2 += carry;
            carry &amp;= (~(cc2 | -cc2)) &gt;&gt; 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.