Moritz Höppner

Posted on Dec 30

How to implement GHASH

#security #cryptography #ruby #math

GHASH is the hash function that GCM uses to compute authentication tags. It is defined in NIST's GCM spec. The spec states the algorithm in a way that makes it easy to implement but hides the mathematical background to some extent. In this post, I want to describe the algorithm from a somewhat more mathematical angle and thereby touch on the topic of finite fields or, synonymously, Galois fields. I will show you how to implement GHASH in Ruby coming from this point of view.

A high-level view on GHASH

GHASH is a keyed hash function. In its NIST version (which is slightly different from its original definition), it takes a 128-bit secret key H and the data to hash X as inputs, where the bit length of X must be a multiple of 128. (Strictly speaking, the spec defines one function for every H with only X as input, but I'll ignore this technicality.) Let X₁, ..., X_m be the blocks of X, so that we have X = X₁ || X₂ || ... || X_m. Now we can calculate GHASH like this:

X₁ ⋅ H^m + X₂ ⋅ H^m-1 + ... + X_m ⋅ H
= ∑_i=1^m (X_i ⋅ H^m-i+1)

Doesn't this look surprisingly simple? It's only adding and multiplying blocks - basically evaluating a polynomial in H.

However, the catch is this: If we define GHASH as above, we can't add and multiply blocks like we do with ordinary integers. Instead, we need to use special versions of addition and multiplication, which are the operations that make the set of 128-bit blocks a field - a so called Galois field of order 2¹²⁸, which is sometimes abbreviated GF(2¹²⁸).

Galois fields

I'll make a few remarks about the theory of Galois fields but they will only touch the surface of the topic. If you want to dive deeper, I recommend having a look at Norman L. Bigg's Discrete Mathematics. It is very readable and hands-on, contrary to the treatment of the topic in certain Algebra textbooks, which in my experience tend to leave the reader alone with highly abstract definitions and statements.

Elements of Galois fields are congruence classes of polynomials. More precisely, an element of GF(2¹²⁸) is the set of all polynomials with coefficients in Z₂ = { 0, 1 } that leave the same remainder when divided by a fixed polynomial P of degree 128. Different choices of P yield different Galois fields of the same order, but not every P is suitable; it must have certain properties (which we'll skip here). For GCM/GHASH, we have P(x) = x¹²⁸+x⁷+x²+x+1.

Every element of GF(2¹²⁸) is a set of polynomials. In each of these sets, there is only one polynomial of degree < 128. (Just as in each congruence class of positive integers modulo p there is only one element < p.) We can choose this polynomial as representative of the congruence class and thus think of GF(2¹²⁸) as a set of polynomials.

Okay, so how does addition and multiplication in GF(2¹²⁸) work? We add two polynomials as we do usually. But remember that we are dealing with polynomials over Z₂ = { 0, 1 }, so we add coefficients as elements of the field Z₂ - meaning we XOR them: 0+0 = 0, 0+1 = 1+0 = 1, 1+1 = 0. Adding two polynomials of degree < 128 again gives us a polynomial of degree < 128, which consequently is the representative of some element of GF(2¹²⁸). And we multiply polynomials like we usually do. However, when multiplying two polynomials, their degree can increase, so we might end up with a polynomial of degree >= 128. To find the representative of the congruence class to which this polynomial belongs, we have to reduce it modulo P, i.e. find the remainder when dividing it by P (for example using polynomial long division).

By shifting from congruence classes to representatives of congruence classes, we can explain addition and multiplication in Galois fields in terms of addition, multiplication and modulo division of polynomials.

I have written a little Ruby gem that provides the class Z2Polynomial, which implements addition, multiplication and modulo division for polynomials over Z₂. I won't go into the details of this implementation here but use it for the GHASH implementation.

Arithmetic of blocks

How do we get from blocks of bits to polynomials to do arithmetic, and then back to interpret the result as a block of bits? Well, the idea is as simple as that: The first bit of the block is the first coefficient of the polynomial, the second bit is the second coefficient and so forth. So, for example, the byte 1101 0010 corresponds to the polynomial x⁷+x⁶+x⁴+x.

Conveniently, the Z2Polynomial class has two class methods that do the conversion from blocks to polynomials and back: from_hexstr and to_hexstr. For example, 1101 0010 in hexadecimal representation is d2. So we have:

Z2Polynomial.from_hexstr('d2').to_s
# => "x^7 + x^6 + x^4 + x"

However, this mapping from blocks of bits to polynomials is somewhat arbitrary. It is the one you find, for example, in the AES spec, but it is by no means the only possible one.

And, in fact, the GCM spec defines a different mapping from blocks to polynomials: It reverses the order of the coefficients, so that 1101 0010 corresponds to the polynomial x⁶+x³+x+1. The spec calls this convention "little endian". Both this term and the unusual mapping itself are criticized by Phillip Rogaway in his paper Evaluation of Some Blockcipher
Modes of Operation (pp. 130-131). We will come back later to this little gotcha.

Implementing GHASH

We're going to implement a class Ghash with one class method digest which takes the data and the key as inputs and returns the hash, everything as hex strings. So we want something like this:

Ghash.digest(
  input: %w(
    01020304050607080910111213141516
    01020304050607080910111213141516
    abcd
  ).join,
  key: '01020304050607080910111213141516'
)
# => 'a1a2a3a4a5a6a7a8a9b0b1b2b3b4b5b6'

Generating a test vector

How are we going to know our implementation is correct? We'll have to test the digest function with known GHASH input/output combinations. To get these, we can encrypt any data with AES-GCM, note the authentication tag and derive the GHASH value from it.

The Web Crypto API keeps the full 128-bit authentication tag and appends it to the ciphertext. Let's encrypt something with it - if you like, you can use this web tool to follow along. I'll use the following inputs:

Key (K): e9d83714dc4943a2adc515234bbb543c889a762237a4fde9cfbbc1680a934bd1
IV: 72b83e1eeee393cc7857fb4e
Plaintext: Hello world! I want something longer than 1 block.

With these inputs, the Web Crypto API implementation of AES-GCM produces the following output:

127084b89eb8e6f0a47728e519cc4e3e dc72b11f761467442ba58eda136ba1e1 3ce5546767055019928bf81afe655053 9c03966fb14e503a70622bce17fa0393 48b7

The first 50 bytes are the actual ciphertext. The remaining 16 bytes are the authentication tag T: 966fb14e503a70622bce17fa039348b7

From this, we can obtain a GHASH input/output pair when we check the construction of T in the NIST spec of GCM (keeping in mind that we have no AAD and our IV is 96 bits long):

T is GCTR_K(J₀, S) = CIPH_K(J₀) XOR S.
J₀ is the bit string IV || 0³¹ || 1, so in our case and in hexadecimal notation: 72b83e1eeee393cc7857fb4e00000001.
CIPH_K(J₀) is the AES encryption of J₀ with key K. In our case, that's 114965dde9be70892a5703ee8242b4b0, which you can verify with OpenSSL:

$ echo -n 72b83e1eeee393cc7857fb4e00000001 | \
  basenc --base16 -d | \     
  openssl enc \
    -aes-256-ecb \
    -K e9d83714dc4943a2adc515234bbb543c889a762237a4fde9cfbbc1680a934bd1 \
    -nopad | \
  basenc --base16

S is GHASH_H(input data).
The input data is constructed as follows: First, the ciphertext (without the authentication tag) is padded with zeroes so that it is a multiple of 128 bits. Let C* be this padded ciphertext. We concatenate C* with 64 zero bits. Then, we concatenate the result with the bit length of the original ciphertext as a 64-bit integer. In our case, the bit length of the original ciphertext is 50 ⋅ 8 = 400 = 0x190. So the input data is this:

127084b89eb8e6f0a47728e519cc4e3e dc72b11f761467442ba58eda136ba1e1 3ce5546767055019928bf81afe655053 9c030000000000000000000000000000 00000000000000000000000000000190

H is CIPH_K(0¹²⁸), i.e. the AES encryption of the zero block with key K. In our case, that's c51d75d9ab375617a2f68b5f905ca869, which you can again verify with OpenSSL:

$ echo -n 00000000000000000000000000000000 | \
  basenc --base16 -d | \
  openssl enc \
    -aes-256-ecb \
    -K e9d83714dc4943a2adc515234bbb543c889a762237a4fde9cfbbc1680a934bd1 \
    -nopad | \
  basenc --base16

To get our test vector from this, we calculate S = CIPH_K(J₀) XOR T:

    114965dde9be70892a5703ee8242b4b0
XOR 966fb14e503a70622bce17fa039348b7
=   8726d493b98400eb0199141481d1fc07

Okay, so we know that for key c51d75d9ab375617a2f68b5f905ca869 and input data

127084b89eb8e6f0a47728e519cc4e3e dc72b11f761467442ba58eda136ba1e1 3ce5546767055019928bf81afe655053 9c030000000000000000000000000000 00000000000000000000000000000190

our GHASH implementation should return 8726d493b98400eb0199141481d1fc07.

Let's formulate this expectation as an rspec test!

describe 'digest' do
  it 'returns the expected hash' do
    result = Ghash.digest(
      input: %w(
        127084b89eb8e6f0a47728e519cc4e3e
        dc72b11f761467442ba58eda136ba1e1
        3ce5546767055019928bf81afe655053
        9c030000000000000000000000000000
        00000000000000000000000000000190
      ).join,
      key: 'c51d75d9ab375617a2f68b5f905ca869'
    )

    expect(result).to(eq('8726d493b98400eb0199141481d1fc07'))
  end
end

Implementing the digest function

First, we fix the polynomial which is used for reduction. Remember, it is x¹²⁸+x⁷+x²+x+1 according to the GCM spec. We can build a Z2Polynomial object by passing the coefficients as an array to the constructor:

class Ghash
  # P(x) = x^128 + x^7 + x^2 + x + 1. We pass the coefficients as
  # array to the constructor of Z2Polynomial.
  P = Z2Polynomial.new([1] + [0]*120 + [1, 0, 0, 0, 0, 1, 1, 1])

  # ...
end

Now, let's get to work: Split the input string into blocks, convert them to polynomials, then build the sum X₁ ⋅ H^m + X₂ ⋅ H^m-1 + ... + X_m ⋅ H, where the X_is are polynomials that correspond to the blocks and H is a polynomial that corresponds to the key. In the end, we must convert the resulting polynomial back to a hex string:

class Ghash
  # ...

  def self.digest(input:, key:)
    # We start the sum with the zero polynomial (Y_0 in the
    # NIST spec).
    digest_pol = Z2Polynomial.new([0])

    # Convert the key to a polynomial to do GF arithmetic.
    key_pol = Z2Polynomial.from_hexstr(key)

    # Split the input string into slices of 32 characters,
    # i.e. 128 bits in hexadecimal representation.
    blocks_hex = input.chars.each_slice(32).map(&:join)

    blocks_hex.each do |block_hex|
      # Convert the block to a polynomial to do arithmetic.
      block_pol = Z2Polynomial.from_hexstr(block_hex)

      # Calculate Y_i = (Y_(i-1) + X_i) ⋅ H, where X_i is the
      # i-th block and H is the key.
      digest_pol = ((digest_pol + block_pol) * key_pol) % P
    end

    # Now, digest_pol is a polynomial that represents the
    # GHASH result. Convert it back to a hex string.
    digest_pol.to_hexstr
  end
end

Now, run the rspec test and ... it fails. The problem here is that Z2Polynomial assumes a different mapping between blocks and polynomials than the GHASH spec - remember the so-called "little endian" convention of GHASH. We can fix this easily: After converting a block to a polynomial, reverse the order of the coefficients; and do the same before converting a polynomial back to a block. All together, we have the following:

require 'z2_polynomial'

class Ghash
  # P(x) = x^128 + x^7 + x^2 + x + 1. We pass the coefficients as
  # array to the constructor of Z2Polynomial.
  P = Z2Polynomial.new([1] + [0]*120 + [1, 0, 0, 0, 0, 1, 1, 1])

  class << self
    def digest(input:, key:)
      # We start the sum with the zero polynomial (Y_0 in the
      # NIST spec).
      digest_pol = Z2Polynomial.new([0])

      # Convert the key to a polynomial to do GF arithmetic.
      key_pol = block_to_polynomial(key)

      # Split the input string into slices of 32 characters,
      # i.e. 128 bits in hexadecimal representation.
      blocks_hex = input.chars.each_slice(32).map(&:join)

      blocks_hex.each do |block_hex|
        # Convert the block to a polynomial to do arithmetic.
        block_pol = block_to_polynomial(block_hex)

        # Calculate Y_i = (Y_(i-1) + X_i) ⋅ H, where X_i is the
        # i-th block and H is the key.
        digest_pol = ((digest_pol + block_pol) * key_pol) % P
      end

      # Now, digest_pol is a polynomial that represents the
      # GHASH result. Convert it back to a hex string.
      polynomial_to_block(digest_pol)
    end

    def block_to_polynomial(block)
      reverse_coefficients(Z2Polynomial.from_hexstr(block))
    end

    def polynomial_to_block(pol)
      reverse_coefficients(pol).to_hexstr
    end

    def reverse_coefficients(pol)
      # For example, the polynomial x + 1 reversed should be
      # x^127 + x^126. To achieve this, we must pad with zeroes
      # before calling reverse.
      pol.pad_to_length(128).reverse
    end
  end
end

And now, the test passes! 🎉

DEV Community