Saturday, January 19, 2013

Authenticated Encryption using AES-GCM -- a 50,000 foot view

I recently read the NIST specification for GCM and thought I'd document a very high level view of the same down here. Please note that this post will not go into the details of each step but will try to give you very high level view of how the various functions fit together in order to provide Authenticated Encryption.

As always, the referenced NIST paper is listed out in the References section. The images used are from the same paper.

GCM or the Galois Counter Mode is a mode of operation for the AES block cipher that provides Authenticated Encryption.

-===================]
Authenticated Encryption
Its a mode of a block cipher which provides not just confidentiality but integrity/authenticity too. In other words, if you encrypted blob has been tampered with(intentionally or otherwise), the algorithm provides a means for its detection.

-=============]
GMAC and AAD
There is a specialization of the GCM mode, wherein the mode is used to ensure the integrity and authenticity of the data alone -- this mode is referred to as GMAC. The data whose integrity alone needs to be maintained is referred to as Additional Authenticated Data(AAD).

-=============]
Functions of GCM
The two functions in GCM are Authenticated Encryption and Authenticated Decryption. Like in the case of the CTR mode for AES, both of these functions are parallelizable.
Its very interesting to note that it would be possible to give two kinds on input to the AE function at the same time -- the plaintext and the AAD ; in that particular case, GCM would protect the confidentiality and the integrity of plaintext and the integrity of the AAD.

To summarize, the AE function would take in the plaintext and the AAD, encrypt the plaintext and compute an "Authentication Tag" using the ciphertext and the AAD . The AD function would take in the ciphertext, the AAD, the Authentication tag, recompute the tag, verify its integrity and proceed to decrypt the ciphertext.

-====]
The IV
For the rest of this document we will use the terms IV, nonce and counter as follows :-
- The IV is the Initialization Vector which is created from the nonce and the counter value. You might be able to relate it to the IV in CTR mode where IV = nonce (concatenated with) counter. In GCM the IV creation is slightly different, but we'll look into it in more depth at a later stage.
- The Nonce is a value typically specified by the person doing the encryption. If you ever use an API to encrypt data(like BC for Java, Crypto++ for C++), chances are that you will be passing in this particular value(even though the API documentation might refer to this as "IV").
- The counter value is an internal counter that is incremented for every block. The initial state of the counter is generated by applying a function to the nonce value.

Now we will proceed to take a brief look at the different functions internal to GCM and its functionality :-

-==============]
Incrementing function
This is the function that is responsible for incrementing the counter value in GCM.

Given an input X and s, the function increments the rightmost s bits of the binary representation of X, modulo 2^s.

-============]
GHASH function

In the block diagram below, each column is a round of the GHASH function.

GHASH is a hash function which is not a cryptographically strong hash in itself but is responsible for integrity in GCM. It takes an input bit string of a length which is a multiple of 128 and outputs a GHASH block. The output of one round of the GHASH function is XOR'd with the input of the next round of GHASH and so on. The first GHASH round takes has the input XOR'd with a zero block of size 128(a bit string of 128 0's).


-===========]
GCTR function

For those of your who are familiar with the CTR mode of AES, you might find the block diagram below familiar :-



As shown in the above diagram, the Initial Counter Block(ICB) which is the IV, is passed through the Cipher function, and the result is xored against our input partitioned into 128 bit blocks. Of course the rightmost Xn block might not be a multiple of 128 bits and might be smaller than that. The output is the concatenated output ( Y1 || Y2 .... || Yn ). The values CB2, CB3... CBn are generated by applying the increment function on CB1, CB2 ... CBn-1 respectively.

-==========]
CIPH function
In this case we refer to the CIPH function as the underlying encryption algorithm. Here we are discussing AES, so CIPH refers to AES.

-======================]
Tying it all together to Encrypt
The following block diagram demonstrates how Authenticated Encryption happens :-


The following steps take place when the AE function is invoked :-

  1. You create an initial block "H"(which is then used as the hash subkey) but passing a zero-block of size 128 through CIPH
  2. Calculate a block J0 based on the IV value and size
  3. Compute a block C such that C = GCTRk(inc32(J0), P)
  4. At this point we know the ciphertext C and the AAD. We calculate values "u" and "v" based on the lengths of C and AAD which can be used for padding later on
  5. Steps from here are about computing the Authentication Tag. A block S is calculated by concatenating AAD, C, the length of C, the length of AAD and a padding with 0's. The padding length would be u + v.
  6. The S block is then encrypted using GCTR and the most significant "t" bits of the result form the Authentication Tag. i.e. T = MSBt(GCTRk(J0, S)). Please note that this is the only part of the whole process where GCTR is used to encrypt with J0.
  7. Return (C, T)
The bit length of the tag may be one of the following 5 values :- 128, 120, 112, 104 or 96. 


-=======================]
Tying it all together to Decrypt
The following block diagram shows how Authenticated Decryption works :-

The following steps take place when AD is invoked :-

  1. Check if the length of the IV, C and AAD are all supported by the implementation. Else FAIL.
  2. You create an initial block "H"(which is then used as the hash subkey) but passing a zero-block of size 128 through CIPH
  3. Calculate a block J0 based on the IV value and size
  4. Compute a block P such that P = GCTRk(inc32(J0), C)
  5. At this point we know the ciphertext C and the AAD. We calculate values "u" and "v" based on the lengths of C and AAD which can be used for padding later on
  6. Steps from here are about recomputing the Authentication Tag. A block S is calculated by concatenating AAD, C, the length of C, the length of AAD and a padding with 0's. The padding length would be u + v.
  7. The S block is then encrypted using GCTR and the most significant "t" bits of the result form the Authentication Tag. i.e. T' = MSBt(GCTRk(J0, S)). Please note that this is the only part of the whole process where GCTR is used to encrypt with J0.
  8. If T = T', return (P). Else FAIL


Reference:
1. NIST Recommendation for Block Cipher Modes Of Operation: Galois/Counter Mode(GCM) and GMAC

No comments:

Post a Comment