DEV Community: Moritz Höppner

Multiplication in Galois fields with the xtimes function

Moritz Höppner — Sun, 04 Jan 2026 17:33:31 +0000

In my previous post, I wrote about finite fields (Galois fields) of order 2ⁿ, abbreviated GF(2ⁿ). Their elements are congruence classes of polynomials over the field Z2 = { 0, 1 }. Each congruence class consists of all polynomials that leave the same remainder when divided by some fixed polynomial m.

To multiply two elements B and C from GF(2ⁿ), you choose a polynomial b from B and a polynomial c from C, and then calculate d = (b ⋅ c) mod m. The result d is a polynomial, which belongs to some congruence class D in GF(2ⁿ). D is the product of B and C.

In section 4.2 of the AES spec, you can find a different algorithm for multiplication in GF(2⁸), which is conceptually simpler than the algorithm above, because it doesn't need polynomial multiplication and modulo division, but only addition and shifting of coefficients. However, I myself needed some time to understand how exactly the algorithm works and why exactly it is correct. So I decided to write about it and share my understanding of it. That's the first section of this post.

The AES spec states this algorithm only for GF(2⁸) but it can easily be generalized to GF(2ⁿ) for arbitrary n. And in fact, it is just the algorithm presented in the GCM spec for multiplication in GF(2¹²⁸), although the spec doesn't say this. So in the second section of this post, I will explain the connection between the algorithms in both specs in more detail. So read until the end if you are - like I was - struggling to understand section 6.3 of the GCM spec on multiplication of blocks. (Why is this pseudo-code correct? What's the magic bit string R?)

In case you're curious to see the algorithm I'm talking about in code, take a look at my Ruby implementation of it.

Multiplication in GF(2⁸) following the AES spec

The goal of the algorithm in the AES spec is to calculate (b ⋅ c) mod m for polynomials b, c of degree < 8 and the fixed polynomial m = x⁸+x⁴+x³+x+1. I'll break down the algorithm into three steps:

Calculate p ⋅ x for some polynomial p of degree < 8,
calculate (p ⋅ x) mod m for some polynomial p of degree < 8 (this is called the xtimes function),
reduce the calculation of (b ⋅ c) mod m to repeated applications of the function from step 2.

Calculation of p ⋅ x

Let's give the coefficients of p names: Let p = p7x⁷ + p6x⁶ + p5x⁵ + p4x⁴ + p3x³ + p2x² + p1x + p0. Of course, p doesn't have to have degree 7; p7 can be zero, just as any other coefficient.

If you multiply p with x, you'll get p ⋅ x = p7x⁸ + p6x⁷ + p5x⁶ + p4x⁵ + p3x⁴ + p2x³ + p1x² + p0x.

If you model polynomials as finite sequences of their coefficients, p is (p7, p6, p5, p4, p3, p2, p1, p0) and p ⋅ x is (p7, p6, p5, p4, p3, p2, p1, p0, 0). So multiplication of polynomials with x is extremely simple: you just have to add a zero to the sequence of coefficients.

Calculation of (p ⋅ x) mod m

Now we're going to define the so-called xtimes function. It should satisfy the condition xtimes(p) = (p ⋅ x) mod m. But we don't want to use this equation as definition, as we are searching for something simpler.

If p ⋅ x has degree < 8 (i.e. if p7 is zero), then (p ⋅ x) mod m is just p ⋅ x. So we can define:

xtimes(p) = (p6, p5, p4, p3, p2, p1, p0, 0) if p7 = 0.

(Note that we choose to omit the leading zero coefficient p7. If you actually define polynomials as finite sequences, this omission has to be justified. After all, the sequence (0, p6, p5, p4, p3, p2, p1, p0, 0) is different from the sequence (p6, p5, p4, p3, p2, p1, p0, 0). However, the omission is certainly justified here because in the end, we are interested in finding a representative of a congruence class. And leading zero coefficients surely don't change the congruence class of the polynomial.)

If, on the other hand, p7 is not zero, we have to calculate the reduction modulo m. In the case of AES, m is fixed, but let's do the reduction for an arbitrary polynomial of degree 8, m = m8x⁸ + m7x⁷ + m6x⁶ + m5x⁵ + m4x⁴ + m3x³ + m2x² + m1x + m0. Remember that the coefficients are members of the field Z2 = { 0, 1 }. Addition and subtraction in Z2 are both the XOR operation.

Since p7 is not zero, it must be 1. And since m has degree 8, we have m8 = 1 as well. So the polynomial long division of p ⋅ x by m looks like this:

(x⁸ + p6x⁷ + ... + p0x) / (x⁸ + m7x⁷ + ... m1x + m0) = 1
- (x⁸ + m7x⁷ + ... m1x + m0)
-------------------------------
(1 - 1)x⁸ + (p6 - m7)x⁷ + ... + (p0 - m1)x + (0 - m0)

So written as a sequence, the remainder polynomial is (1 - 1, p6 - m7, ..., p0 - m1, 0 - m0) = (0, p6 - m7, ..., p0 - m1, m0).

With the same justification as above, we skip the leading zero. Since subtraction in Z2 is the XOR operation, we can calculate the remainder like this: (p6, p5, p4, p3, p2, p1, p0, 0) XOR (m7, m6, m5, m4, m3, m2, m1, m0).

Now, back to the spec. Here, m is the fixed polynomial x⁸+x⁴+x³+x+1, so the second part of the xtimes definition looks like this:

xtimes(p) = (p6, p5, p4, p3, p2, p1, p0, 0) XOR (0, 0, 0, 1, 1, 0, 1, 1) if p7 = 1.

Note that the the algorithm works just as well for other Galois fields GF(2ⁿ): For n=8, we only used the fact that m has degree 8. However, the modulus polynomial for GF(2ⁿ) has always degree n. Meaning: So far, the algorithm works for every n.

Reduction of multiplication to xtimes

We can use the xtimes function to calculate (b ⋅ c) mod m for arbitrary polynomials over Z2 of degree < 8. For example, let c be x²+x:

b ⋅ (x²+x) mod m
= (bx² + bx) mod m
= (bx² mod m) + (bx mod m)

Okay, (bx mod m) is just xtimes(b), that's good. The first summand can also be expressed in terms of xtimes:

bx² mod m
= (bx ⋅ x) mod m
= ((bx mod m) ⋅ x) mod m
= (xtimes(b) ⋅ x) mod m
= xtimes(xtimes(b))

So we have:

b ⋅ (x²+x) mod m = xtimes(xtimes(b)) + xtimes(b)

In general, the algorithm for calculating (b ⋅ c) mod m works like this: Apply the xtimes function k times to b if ck is one. Then add all the results.

All of this works just the same for other Galois fields, even of different orders. So it's no surprise that we find the same algorithm in the GCM spec, where it is used to multiply 128-bit blocks instead of bytes.

Multiplication in GF(2¹²⁸) following the GCM spec

To spare you the hassle to look it up, here is a screenshot of the multiplication algorithm in the GCM spec:

Just like above, one factor is fixed (Y) and the coefficients of the other (X) are inspected.

The blocks Vi are the results of repeated applications of xtimes to Y. The blocks Zi are the result of adding all Vis that correspond to a coefficient 1.

The Vi+1 is analogous to the xtimes definition, but there is a little gotcha: In GCM, the order of the coefficient is reversed, so the bit sequence x0x1...x127 represents the polynomial x0 + x1 ⋅ x + ... + x127 ⋅ x¹²⁷.

When I explained above how to calculate p ⋅ x, I represented polynomials by bit sequences and assumed a different ordering, so that the x0x1...x127 would represent the polynomial x0 ⋅ x¹²⁷ + ... + x126 ⋅ x + x127.

That's why multiplying a polynomial with x is not achieved by shifting the coefficients not to the left but to the right, and that's the explanation for the ">> 1" in the definition of Vi+1.

It also explains why the distinction between cases in the definition of Vi+1 works by looking at the least significant (right-most) bit, while the distinction in my xtimes definition worked by looking at the first/left-most/most significant bit.

And the unusual ordering of coefficients is the reason that the loop in step 3 ranges from 0 to 127, instead of the other way around.

Finally, the bit string R = 11100001 || 0¹²⁰ is a shifted representation of the modulus polynomial. In the case of GCM, this polynomial is m = x¹²⁸+x⁷+x²+x+1. To define xtimes, we discarded the highest order coefficient and wrote the other ones in a bit sequence. This gives us the bit sequence 0¹²⁰ || 10000111. But again, GCM reverses the coefficients, so you end up with R.

How to implement GHASH

Moritz Höppner — Tue, 30 Dec 2025 07:48:44 +0000

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 X1, ..., Xm be the blocks of X, so that we have X = X1 || X2 || ... || Xm. Now we can calculate GHASH like this:

X1 ⋅ H^m + X2 ⋅ H^m-1 + ... + Xm ⋅ H
= ∑i=1^m (Xi ⋅ 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 Z2 = { 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 Z2 = { 0, 1 }, so we add coefficients as elements of the field Z2 - 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).

(In case you're curious how this explanation of multiplication in GF(2¹²⁸) relates to the pseudo-code given in section 6.3 of the GCM spec, take a look at this post.)

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 Z2. 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 GCTRK(J0, S) = CIPHK(J0) XOR S.
J0 is the bit string IV || 0³¹ || 1, so in our case and in hexadecimal notation: 72b83e1eeee393cc7857fb4e00000001.
CIPHK(J0) is the AES encryption of J0 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 GHASHH(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 CIPHK(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 = CIPHK(J0) 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 X1 ⋅ H^m + X2 ⋅ H^m-1 + ... + Xm ⋅ H, where the Xis 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! 🎉

How to decrypt broken GCM ciphertext

Moritz Höppner — Sat, 06 Sep 2025 17:00:48 +0000

GCM-encrypted data has an authentication tag that serves as an integrity protection mechanism. It is essentially a keyed hash of the ciphertext. If the ciphertext is broken, for example because someone tampered with it or because an encrypted file is corrupted due to hardware issues, the authentication tag no longer matches the ciphertext and becomes invalid.

Some libraries will refuse to decrypt the ciphertext if the authentication tag is invalid. This is probably a good decision: The whole point of authenticated encryption is to make it impossible to tamper with encrypted data. And it probably prevents security issues and makes developers' lives a little easier, since they don't have to decide whether to authenticate ciphertext. If they use authenticated encryption, the authentication tag must be valid. Period.

However, if you still want to decrypt the ciphertext, you can choose a GCM implementation that doesn't enforce authentication. OpenSSL is such a library, as you can see from this example. But there is another option that I find interesting because it reveals something about the inner workings of GCM: You can use CTR mode for decryption. This is what I'm going to describe here.

Counter Mode

I've written about Counter Mode (CTR) in a previous post. Its specification doesn't really prescribe a way of generating counter blocks. So you start with any sequence of distinct blocks (called counter blocks). You encrypt them and then XOR the result with your plaintext (to encrypt) or your ciphertext (to decrypt). That's basically it.

(A quick side note: If you're curious why the counter blocks must be distinct, take a look at this post.)

Although the CTR spec doesn't prescribe a way of generating counter blocks, it recommends the so-called standard incrementing function in Appendix B. The idea is this: You start with any block, usually 128 bits, and you choose how many bits to use as the counter. Say, 32 bits. Now, the standard incrementing function interprets the 32 least-significant bits of the block as an integer and increments it. This can be done again and again until all 32 counter bits are 1. Then the counter "wraps", so in the next block all counter bits will be 0. For example, if the counter length is indeed 32 bits (4 bytes), then a sequence of counter blocks in hexadecimal representation might look like this (starting with a random block):

63a962e5207b6f0174bfb64ee2d1bcee
63a962e5207b6f0174bfb64ee2d1bcef
63a962e5207b6f0174bfb64ee2d1bcf0
63a962e5207b6f0174bfb64ee2d1bcf1
...
63a962e5207b6f0174bfb64efffffffe
63a962e5207b6f0174bfb64effffffff
63a962e5207b6f0174bfb64e00000000
63a962e5207b6f0174bfb64e00000001

You can use CTR in a spec-compliant way and generate your counter blocks differently. But this is the algorithm recommended in the spec.

Galois/Counter Mode

Galois/Counter Mode (GCM) doesn't just add the authentication tag to CTR. It is also more specific in three aspects—so you could say, GCM is an extension (adding the authentication tag) of a special case of CTR (being more specific about certain things).

The GCM spec is more specific than the CTR spec in the following ways:

Block size: For CTR, you can choose any block size. For GCM, the block size must be 128 bits.
The incrementing function: GCM makes the standard incrementing function mandatory. GCM also restricts the counter length: It must be 32 bits.
The initial counter block: For CTR, you can choose any initial counter block, while GCM has a built-in way of generating the first counter block. GCM needs an initialization vector (IV) as input, and the algorithm for generating the first counter block depends on the length of the IV. Usually, you have a 96-bit IV, and in this case the first counter block is IV || 00000002 (the counter part again in hexadecimal representation).

Decrypt GCM ciphertext with CTR

After this little comparison, we can easily decrypt GCM ciphertext with CTR—at least as long as our IV for GCM has a length of 96 bits; the case for other IV lengths is a bit more complicated and I will ignore it for now. For CTR decryption, we simply have to choose the standard incrementing function with a counter length of 32 bits and IV || 00000002 as the initial counter block.

We can test this idea using the Web Crypto API. It implements CTR and GCM and, luckily, uses the standard incrementing function for CTR. So we only have to choose the right counter length and initial counter block.

I have written a little web tool, which you can use to play around with this idea. Note that the Crypto API adds the GCM authentication tag to the ciphertext. By default, the authentication tag has a length of 128 bits. So when you encrypt something with GCM in the browser and decrypt the result with CTR, you'll get your original plaintext plus 128 bits of garbage, which are the result of "decrypting" the authentication tag.

How to break stream ciphers with repeating keystreams

Moritz Höppner — Sat, 15 Feb 2025 13:08:53 +0000

Stream ciphers usually generate a keystream from a secret key and other input. The encryption function XORs the plaintext with the keystream. The decryption function XORs the ciphertext with the keystream. Examples of stream ciphers that work like this are AES-CTR and ChaCha20. If the keystream ever repeats itself, the respective ciphertexts can be decrypted without knowledge of the secret key quite easily. To do this is especially easy if the attacker manages to encrypt a message of their choosing with the repeating part of the keystream. In this post, I will show how the decryption works in such a case.

Theory

The scenario is this: The attacker wants to decrypt a given ciphertext cipher_secret and knows a plaintext-ciphertext combination (say, plain_known and cipher_known), where cipher_known has been encrypted with the same keystream as cipher_secret.

So we have:

cipher_secret = plain_secret XOR keystream
cipher_known = plain_known XOR keystream

cipher_secret can now be decrypted with just two XOR operations. First, we calculate the keystream:

keystream = 0 XOR keystream
          = (plain_known XOR plain_known) XOR keystream
          = plain_known XOR (plain_known XOR keystream)
          = plain_known XOR cipher_known

Now, we decrypt cipher_secret as usual:

plain_secret = cipher_secret XOR keystream

Example

Let's try this method in a *nix shell! The vulnerable application may encrypt plaintexts with AES-CTR using hard-coded counter blocks. This can be simulated with OpenSSL by using a fixed IV:

$ function enc() {
  echo -n $1 | openssl enc -aes-256-ctr \
    -K 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f \
    -iv 00000000000000000000000000000000
}

We use this function to generate the ciphertext known by the attacker:

$ cipher_secret=$(enc "I am secret")
$ echo -n $cipher_secret | hexdump -C
00000000  bb b0 61 db 0a 3a fa b3  db 96 ee                 |..a..:.....|
0000000b

Now, the attacker lets the application encrypt a plaintext with the same length (11 bytes):

$ plain_known="01234567890"
$ cipher_known=$(enc $plain_known)

I'll use the xor shell function from my last post to do the XORing:

$ keystream=$(xor $plain_known $cipher_known)
$ xor $cipher_secret $keystream
I am secret

That worked :)

The procedure is not dependent on the cipher algorithm, as long as it works by XORing the plaintext/ciphertext with a keystream. For example, you'll get the same result (with different ciphertexts) if you use ChaCha20 instead of AES-CTR:

function enc() {
  echo -n $1 | openssl enc -chacha20 \
    -K 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f \
    -iv 00000000000000000000000000000000
}

The case without known plaintext

What if the attacker doesn't know the plaintext corresponding to one of the ciphertexts, i.e. plain_known isn't actually known? In this situation, we have:

cipher_1 = plain_1 XOR keystream
cipher_2 = plain_2 XOR keystream

And therefore:

cipher_1 XOR cipher_2 = plain_1 XOR plain_2

So the attacker can't immediately calculate the plaintexts but the result of XORing two plaintexts, which is also quite bad: If one has some knowledge about the structure of the plaintexts—such as common words or most likely bytes—it becomes surprisingly simple to brute-force one plaintext and thereby reveal the other. I have demonstrated this technique here.

The Counter Mode - manually!

Moritz Höppner — Thu, 06 Feb 2025 19:02:41 +0000

The counter mode of operation (CTR) is defined in the NIST Special Publication 800-38A, pp. 15-16. I'd summarize it like this: The CTR mode transforms any block cipher into a stream cipher. Encryption and decryption are the same function. They encrypt a sequence of counter blocks and XOR the result with the plaintext (for encryption) or the ciphertext (for decryption).

My goal here is encrypting a plaintext with AES-256-CTR. And I want to do the CTR part manually, i.e. in my shell only with the usual tools like hexdump, basenc and dd. To encrypt the counter blocks, I'll need OpenSSL - but not in CTR mode!

The shell is probably not the best tool for something like this. Especially XORing data is a little awkward. Or maybe I just think so because I'm certainly not particularly good at shell programming. However, for now I'll stay with the shell and won't switch to a language like Ruby or Go. This way, you can follow without having to install an interpreter or compiler for my preferred language.

Preparation

Let's say, we want to encrypt the plaintext Lorem ipsum dolor sit amet with AES-256-CTR. The plaintext in ASCII encoding consist of two 128-bit blocks:

$ P="Lorem ipsum dolor sit amet"
$ echo -n $P | hexdump -C
00000000  4c 6f 72 65 6d 20 69 70  73 75 6d 20 64 6f 6c 6f  |Lorem ipsum dolo|
00000010  72 20 73 69 74 20 61 6d  65 74                    |r sit amet|
0000001a

To encrypt them in CTR, we start with two counter blocks, which we save in shell variables:

$ T1=00000000000000000000000000000000
$ T2=00000000000000000000000000000001

The next step is to encrypt them with AES-256. Since both T1 and T2 are exactly one block, we can apply the AES cipher function directly. To do this with OpenSSL, we choose the ECB mode, which simply applies AES block by block. Let's save a 256-bit key in a shell variable and then encrypt the counter blocks:

$ key=000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
$ O1=$(echo -n $T1 | basenc --base16 -d | openssl enc -aes-256-ecb -K $key -nopad)
$ O2=$(echo -n $T2 | basenc --base16 -d | openssl enc -aes-256-ecb -K $key -nopad)

We need the -nopad flag here, because otherwise OpenSSL will add a complete padding block to T1 and T2, respectively.

Now, we split the plaintext in blocks:

$ P1=$(echo -n $P | dd bs=16 skip=0 count=1 status=none)
$ P2=$(echo -n $P | dd bs=16 skip=1 count=1 status=none)

Ok, so the ciphertext will be P1 XOR O1 and P2 XOR O2. To be precise, the second ciphertext block is actually not P2 XOR O2, because P2 has only 10 bytes and O2 has 16 bytes. The CTR specification states that the last ciphertext block (which may not be a complete block) Cn is calculated like this:

Cn = Pn XOR MSB_u(On)

Here, u is the length of Pn and MSB_u(On) are the u most significant bytes of On, i.e. the u left-most bytes. In our case, u is 10, so we only need the first 10 bytes of O2:

$ O2_MSB=$(echo -n $O2 | dd bs=10 count=1 status=none)

Okay. Now, we need to calculate P1 XOR O1 and P2 XOR O2_MSB. How do we do that? We could look at the hexdumps, calculate the binary representations and do the XORing by hand. But of course it'd be nice to do it programmatically. As indicated, to do that in the shell is a little awkward.

XOR as shell function

We can XOR to integers (base 10) like this:

$ echo $((6 ^ 5))
3
# That's right:
#     0110 (6)
#     0101 (5)
# --------
# XOR 0011 (3)

To use this syntax, we first convert our data to a hexadecimal representation and then interpret this representation as one number and transform it to base 10:

$ a=a
# $a now contains the string 'a', i.e. 0x61
$ a_hex=$(echo -n $a | basenc --base16)
$ echo $a_hex
61
# Great. 0x61 in base 10 is 6*16 + 1 = 97.
$ echo $((16#$a_hex))
97
# Woohoo!

This way, we can transform our data into base 10 integers and XOR them. Afterwards, we must transform the integer back to raw data. We can transform a base 10 integer into its hexadecimal representation with printf and then decode it with basenc:

$ input=97
$ input_hex=$(printf "%02x" $input)
$ echo $input_hex
61
$ input_raw=$(echo -n $input_hex | basenc --base16 -d)
$ echo $input_raw
a

A side note: We can convert an integer to its hexadecimal representation with printf "%x" $input. However, this does not necessarily output complete bytes. For example:

$ printf "%x" 3
3

But basenc expects complete bytes with two characters each, so we must pad the output with zeros:

$ printf "%02x" 3
03

Okay, with these ingredients, we can implement an XOR function:

function xor() {
  op1_hex=$(echo -n $1 | basenc --base16)
  op1_dec=$(echo $((16#$op1_hex)))

  op2_hex=$(echo -n $2 | basenc --base16)
  op2_dec=$(echo $((16#$op2_hex)))

  xor_dec=$(echo $(($op1_dec ^ $op2_dec)))
  xor_hex=$(printf "%02x" $xor_dec)

  echo -n $xor_hex | basenc --base16 -d
}

When we test this function, we may not see an output because it has no printable characters. So we must pipe it to hexdump or basenc:

$ xor e f | basenc --base16
03

The e character is encoded as 0x65, the f character is encoded as 0x66. 6 XOR 6 is 0, 5 XOR 6 is 3. It works!

Unfortunately, there is still a problem:

$ xor $P1 $O1
xor:2: number truncated after 17 digits: 4C6F72656D20697073756D20646F6C6F
xor:5: number truncated after 16 digits: F29000B62A499FD0A9F39A6ADD2E7780

Apparently, $((16#...)) cannot handle numbers of the size we need here. A simple solution that works for us is to split the arguments into bytes and XOR them separately:

function xor() {
  op_length=$(echo -n $1 | wc -c)

  for i in $(seq 1 $op_length)
  do
    op1_hex=$(echo -n $1 | dd bs=1 count=1 skip=$((i-1)) status=none | basenc --base16)
    op2_hex=$(echo -n $2 | dd bs=1 count=1 skip=$((i-1)) status=none | basenc --base16)

    op1_dec=$(echo -n $((16#$op1_hex)))
    op2_dec=$(echo -n $((16#$op2_hex)))

    xor_dec=$(echo -n $(($op1_dec ^ $op2_dec)))
    xor_hex=$(printf "%02x" $xor_dec)

    if [ $i = 1 ]; then
      result_hex=$xor_hex
    else
      result_hex="$result_hex$xor_hex"
    fi
  done

  echo -n $result_hex | basenc --base16 -d
}

Not an elegant solution, but good enough for the CTR demonstration I'm doing here.

Back to CTR

Now we can calculate the ciphertext:

$ C1=$(xor $P1 $O1)
$ C2=$(xor $P2 $O2_MSB)
$ C="$C1$C2"
$ echo -n $C | hexdump -C
00000000  be ff 72 d3 47 69 f6 a0  da 86 f7 4a b9 41 1b ef  |..r.Gi.....J.A..|
00000010  82 7d 05 c7 3e 99 fe 88  c3 82                    |.}..>.....|
0000001a

Okay good, looks like gibberish. But how do we know if $C is actually the correct AES-256-CTR ciphertext?

Well, we can calculate it with OpenSSL and compare:

$ echo -n $P | openssl enc \
    -aes-256-ctr \
    -K $key \
    -iv 00000000000000000000000000000000 \
    | hexdump -C
00000000  be ff 72 d3 47 69 f6 a0  da 86 f7 4a b9 41 1b ef  |..r.Gi.....J.A..|
00000010  82 7d 05 c7 3e 99 fe 88  c3 82                    |.}..>.....|
0000001a

Yep, we did good. :)

I said above that encryption and decryption are the same function. We can decrypt the ciphertext by XORing the encrypted counter blocks again:

$ echo $(xor $C1 $O1)$(xor $C2 $O2_MSB)
Lorem ipsum dolor sit amet

Beautiful!

But what's up with the initialization vector? Why just 16 zero bytes? And what does "initialization vector" even mean in the context of CTR? The NIST spec doesn't speak of IVs. Let's have a look at OpenSSL's implementation of CTR!

OpenSSL's implementation of CTR

The relevant function is CRYPTO_ctr128_encrypt. When we ignore the lines that are contingent on the OPENSSL_SMALL_FOOTPRINT and STRICT_ALIGNMENT flags, the function becomes pretty simple:

void CRYPTO_ctr128_encrypt(const unsigned char *in, unsigned char *out,
                           size_t len, const void *key,
                           unsigned char ivec[16],
                           unsigned char ecount_buf[16], unsigned int *num,
                           block128_f block)
{
  unsigned int n;
  size_t l = 0;

  n = *num;

  while (l < len) {
    if (n == 0) {
      (*block) (ivec, ecount_buf, key);
      ctr128_inc(ivec);
    }
    out[l] = in[l] ^ ecount_buf[n];
    ++l;
    n = (n + 1) % 16;
  }

  *num = n;
}

The comment above the function states that *num and ecount_buf must be initialized with zeros. So n starts at 0. The while loop iterates over the input bytes that belong either to the plaintext (if we are encrypting) or to the ciphertext (if we are decrypting). The first thing that happens in the loop is that the IV ivec is encrypted with the given block cipher and the result is written to ecount_buf. The IV is then incremented. A look at ctr128_inc in the same file shows that this basically means that 1 is added to the IV. Then the first byte of the input is XORed with the first byte of the encrypted IV. In the next 15 iterations, the next input bytes are XORed with the next bytes of the encrypted IV. In the 17th iteration, n is 0 again. So now the incremented IV is encrypted, and the 17th input byte is then XORed with the first input byte of the result. And so on.

So when we give OpenSSL an "initialization vector" for CTR, this is the first counter block. Given any counter block, the subsequent counter block is generated by adding 1. This is why we could reproduce our encryption result with the counter blocks T1 and T2 by passing the zero IV to OpenSSL.

How to choose counter blocks

As you might suspect, it is not a very good idea to start the counter blocks with 0 by default. Or, in other words, to set the IV to 0 by default. The NIST spec states in Appendix B (p. 18): "The specification of the CTR mode requires a unique counter block for each plaintext block that is ever encrypted under a given key, across all messages." The authors then give some hints on how this can be achieved. I won't go into these details here. For now, I just wanted to understand the CTR algorithm itself and how it can be implemented in the shell.

How to truncate CBC ciphertext

Moritz Höppner — Sat, 11 Jan 2025 10:10:44 +0000

Suppose you have a large CBC ciphertext, say AES-256-CBC encrypted, and you only need the first n bytes of the plaintext. You might know that it is a text document, and you want to display a preview. Or you might want to determine its format by some magic bytes at the beginning of the file.

You could of course decrypt the whole thing and only use the first n bytes, but obviously that'd be not very good performance-wise.

I'll show two ways of truncating CBC ciphertext so that you don't need to decrypt the whole file to get the first bytes. The idea is very simple: Remove everything from the ciphertext but the first blocks. But there is one gotcha, and that's padding. So I'll write a little about that. To reproduce the example, you need a *nix shell, the OpenSSL command line utility, hexdump, basenc (from GNU coreutils) and dd.

Let's prepare an example plaintext and ciphertext:

$ echo -n "Lorem ipsum dolor sit amet, consetetur" > lorem.txt
$ openssl enc -aes-256-cbc \
    -in lorem.txt \
    -out lorem.enc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c

Decryption is done block by block, instead of decrypting the first n bytes, we decrypt the first m blocks, where m is the smallest multiple of the block size (16 bytes in our case), so that m * { block size } <= n. In this tutorial, I'll decrypt the first block.

The naive approach

If we only want to decrypt the first block, we should be able to remove everything else from the ciphertext:

$ dd if=lorem.enc of=lorem-truncated.enc bs=16 count=1

And decrypt:

$ openssl enc -aes-256-cbc -d \
    -in lorem-truncated.enc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c
bad decrypt
408F800302000000:error:1C800064:Provider routines:ossl_cipher_unpadblock:bad decrypt:providers/implementations/ciphers/ciphercommon_block.c:107:

Okay, that didn't work. The last command should result in a "bad decrypt" error message, raised in OpenSSL's providers/implementations/ciphers/ciphercommon_block.c:107. We can see in the source code that OpenSSL looks at the last byte of the given block buf and raises an error if this byte is 0 or greater than the block size, i.e. greater than 16 or 0x10.

Let's play a little with OpenSSL to find out why this happens.

Playing with OpenSSL

To simplify the following shell commands, we can make tiny shell scripts for encryption and decryption:

# enc.sh

openssl enc -aes-256-cbc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c

# dec.sh

openssl enc -aes-256-cbc -d \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c

Okay, so the first question is: Is buf a block of the plaintext or the ciphertext? Shouldn't it be part of the ciphertext because the error occured during decryption? Let's find out.

The truncated ciphertext looks like this:

$ hexdump -C lorem-truncated.enc                                                 
00000000  81 90 91 f9 c1 33 1b fb  6d 49 3f d5 c5 04 43 89  |.....3..mI?...C.|
00000010

We can change the last byte to something between 0x00 and 0x10, say 0x0a, to see if the error message changes:

$ echo 819091f9c1331bfb6d493fd5c504430a | basenc --base16 -d | ./dec.sh

Nope, still the same.

Okay, now the same with the plaintext. Currently, we have:

$ hexdump -C lorem.txt
00000000  4c 6f 72 65 6d 20 69 70  73 75 6d 20 64 6f 6c 6f  |Lorem ipsum dolo|
00000010  72 20 73 69 74 20 61 6d  65 74 2c 20 63 6f 6e 73  |r sit amet, cons|
00000020  65 74 65 74 75 72                                 |etetur|
00000030

Since we truncate the second and third block of the ciphertext anyway, we ignore the corresponding plaintext blocks for the moment. We can reproduce the problem with only one input block:

$ echo 4c6f72656d20697073756d20646f6c6f \
    | basenc --base16 -d \
    | ./enc.sh \
    | dd bs=16 count=1 status=none \
    | ./dec.sh
bad decrypt
408F800302000000:error:1C800064:Provider routines:ossl_cipher_unpadblock:bad decrypt:providers/implementations/ciphers/ciphercommon_block.c:107:

Now our little experiment. We change the last byte to 0x0a:

$ echo 4c6f72656d20697073756d20646f6c0a \
    | basenc --base16 -d \
    | ./enc.sh \
    | dd bs=16 count=1 status=none \
    | ./dec.sh
bad decrypt
408F800302000000:error:1C800064:Provider routines:ossl_cipher_unpadblock:bad decrypt:providers/implementations/ciphers/ciphercommon_block.c:112:

Okay, we still get a "bad decrypt" error. But: It is raised now in line 112 instead of line 107! It seems that we passed the check in ciphercommon_block.c:106 and now run into a different problem. Let's play a little with this to make sure we got it right:

$ echo 4c6f72656d20697073756d20646f6c00 \
    | basenc --base16 -d \
    | ./enc.sh \
    | dd bs=16 count=1 status=none \
    | ./dec.sh
# Last byte is 0x00 -> error in line 107

$ echo 4c6f72656d20697073756d20646f6c10 \
    | basenc --base16 -d \
    | ./enc.sh \
    | dd bs=16 count=1 status=none \
    | ./dec.sh
# Last byte is 0x10 (block size) -> error in line 112

$ echo 4c6f72656d20697073756d20646f6c11 \
    | basenc --base16 -d \
    | ./enc.sh \
    | dd bs=16 count=1 status=none \
    | ./dec.sh
# Last byte is 0x11 (> block size) -> error in line 107

Great. So the decryption fails after decrypting a block, the problem is the format of the plaintext. First of all, the last byte of the plaintext has to be greater than 0 and smaller than or equal to the block size.

Now, if the last byte is correct, why is an error raised in ciphercommon_block.c:112? The for loop looks at the last pad bytes of the block, where pad is the last byte itself. If one of these bytes is not equal to pad, an error is raised. So if pad is 0x01, the for loop only looks at the last byte itself. Let's try it:

$ echo 4c6f72656d20697073756d20646f6c01 \
    | basenc --base16 -d \
    | ./enc.sh \
    | dd bs=16 count=1 status=none \
    | ./dec.sh
Lorem ipsum dol

That works! But, of course, we lost the last byte to satisfy OpenSSL. If pad is 0x02, the for loop looks at the last two bytes and requires both of them to be 0x02:

$ echo 4c6f72656d20697073756d20646f0202 \
    | basenc --base16 -d \
    | ./enc.sh \
    | dd bs=16 count=1 status=none \
    | ./dec.sh
Lorem ipsum do

Above, we tried 0x10 as last byte. Now we know that if the last byte is 0x10 (the block size), then every byte of the block has to be 0x10:

$ echo 10101010101010101010101010101010 \
    | basenc --base16 -d \
    | ./enc.sh \
    | dd bs=16 count=1 status=none \
    | ./dec.sh

As expected, no error occurs, but also no plaintext is left.

Padding

We found out that the last bytes of our plaintext block must be one of these, or else OpenSSL complains:

01
0202
030303
...
10101010101010101010101010101010

These are padding bytes. When encrypting data, OpenSSL adds them to the plaintext so that the length of the data is a multiple of 16 bytes. After all, block ciphers need blocks of a fixed length as input, 16 bytes in the case of AES. If the plaintext length is already a multiple of 16 bytes, a whole block of 0x10 padding bytes is added. So the last byte is always a padding byte. This last byte is B the last B bytes are removed from the plaintext after decryption.

This is one of many possible padding schemes, called PKCS #7. You might get a little confused when you try to find its specification. At least, I did. PKCS #7 was the name of a standard for a format to store encrypted data in. It describes something called "envelope encryption", which means data is encrypted, and then the encryption key is itself encrypted and sent together with the encrypted data. RFC 2315 describes this process and mentions in passing the above padding scheme. And even symmetric encryption doesn't necessarily have anything to do with envelope encryption, the padding scheme is now called PKCS #7. Basically the same scheme (only for smaller block sizes) is described in the PKCS #5 standard (RFC 1423), again in a very specific context, here of DES-CBC encryption. To add some more confusion, PKCS #7 is today obsoleted by something called CMS, described in RFC 5652. And this specification describes the same padding scheme.

We can see the padding bytes added by OpenSSL during encryption with the -nopad flag:

$ openssl enc -aes-256-cbc -d \
    -in lorem.enc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c \
    -nopad \
    | hexdump -C
00000000  4c 6f 72 65 6d 20 69 70  73 75 6d 20 64 6f 6c 6f  |Lorem ipsum dolo|
00000010  72 20 73 69 74 20 61 6d  65 74 2c 20 63 6f 6e 73  |r sit amet, cons|
00000020  65 74 65 74 75 72 0a 0a  0a 0a 0a 0a 0a 0a 0a 0a  |etetur..........|
00000030

Back to the truncating problem

I think the best option for truncating the ciphertext is to use the -nopad flag. Then OpenSSL treats padding bytes as plaintext, meaning it doesn't expect any padding bytes:

$ openssl enc -aes-256-cbc -d \
    -in lorem-truncated.enc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c \
    -nopad
Lorem ipsum dolo

Great, we are done. The naive approach was almost right, we simply had to add -nopad.

But just for fun, I want to show you another possibility I thought of before I knew the -nopad option existed.

We know that the last block of the ciphertext contains the encrypted padding bytes. So we can simply keep this last block. However, the last block can only be decrypted properly if the second-to-last ciphertext block is also present, as in CBC mode, any decrypted block is XORed with the ciphertext block before. So we keep the last two blocks. This means that our truncated ciphertext has at least three blocks. Our original plaintext had only three blocks to begin with, so to demonstrate the procedure, we need a slightly longer plaintext.

$ echo "Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed" > lorem.txt
$ openssl enc -aes-256-cbc \
    -in lorem.txt \
    -out lorem.enc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c
$ hexdump -C lorem.enc
00000000  81 90 91 f9 c1 33 1b fb  6d 49 3f d5 c5 04 43 89  |.....3..mI?...C.|
00000010  a2 47 23 26 af 09 04 6e  f3 f6 1a b7 16 b9 95 18  |.G#&...n........|
00000020  93 9c e7 f4 23 a2 2e c6  c5 49 e1 73 65 52 cc 92  |....#....I.seR..|
00000030  48 b3 8f c6 61 50 50 52  1d bf bf 43 b4 c8 d8 8a  |H...aPPR...C....|
00000040

Our new lorem-truncated.enc contains the first and last two blocks of lorem.enc:

$ dd if=lorem.enc of=lorem-truncated.enc bs=16 count=1
$ dd if=lorem.enc bs=16 skip=2 >> lorem-truncated.enc
$ hexdump -C lorem-truncated.enc
00000000  81 90 91 f9 c1 33 1b fb  6d 49 3f d5 c5 04 43 89  |.....3..mI?...C.|
00000010  93 9c e7 f4 23 a2 2e c6  c5 49 e1 73 65 52 cc 92  |....#....I.seR..|
00000020  48 b3 8f c6 61 50 50 52  1d bf bf 43 b4 c8 d8 8a  |H...aPPR...C....|
00000030

OpenSSL can decrypt this file without errors:

$ openssl enc -aes-256-cbc -d \
    -in lorem-truncated.enc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c \
    | hexdump -C
00000000  4c 6f 72 65 6d 20 69 70  73 75 6d 20 64 6f 6c 6f  |Lorem ipsum dolo|
00000010  46 a3 d7 ab 1b 48 3f e6  ff db 4c 12 a0 de bf ff  |F....H?...L.....|
00000020  67 20 65 6c 69 74 72 2c  20 73 65 64 0a           |g elitr, sed.|
0000002d

The second block is garbage because OpenSSL XORed the decrypted block with the first block of lorem-truncated.enc. But it should be XORed with the second block of lorem.enc, which isn't there anymore.

But we can of course simple remove the garbage block and the padding block from the plaintext:

$ openssl enc -aes-256-cbc -d \
    -in lorem-truncated.enc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c \
    | dd bs=16 count=1 status=none
Lorem ipsum dolo

Bit flipping Attack on CBC: Change of the Ciphertext

Moritz Höppner — Sun, 05 Jan 2025 17:55:31 +0000

Just like in yesterday's tutorial, I want to demonstrate a bit flipping attack on an AES-CBC encrypted ciphertext. This time, we won't change the first plaintext block by tampering with the IV but the second one by tampering with the first ciphertext block. To follow along, you'll need a shell on a *nix system, the OpenSSL command line utility, hexdump, dd and basenc (which is part of GNU corutils).

The attack doesn't depend on the block cipher (although I'll be using the fact that AES has a block size of 128 bit) but only on the mode of operation, which is CBC. For an introduction to CBC, take a look at Crypto 101, which contains a nice explanation of the kind of attack I'm about to show. My goal here is simply to show how to actually do it, how to calculate the bytes, how to read and write the encrypted files.

The original plaintext is the following HTML document (UTF-8 encoded):

<!DOCTYPE html>
<html>
  <body>
    Hello World!
  </body>
</html>

We save it as secret.html and generate the ciphertext with OpenSSL (the exact values for the IV and key don't matter, I'm using simply some MD5 hash):

$ openssl enc -aes-256-cbc \
    -in secret.html \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c \
    > secret.enc

Let's take a look at both files with hexdump:

$ hexdump -C secret.html    
00000000  3c 21 44 4f 43 54 59 50  45 20 68 74 6d 6c 3e 0a  |<!DOCTYPE html>.|
00000010  3c 68 74 6d 6c 3e 0a 20  20 3c 62 6f 64 79 3e 0a  |<html>.  <body>.|
00000020  20 20 20 20 48 65 6c 6c  6f 20 57 6f 72 6c 64 21  |    Hello World!|
00000030  0a 20 20 3c 2f 62 6f 64  79 3e 0a 3c 2f 68 74 6d  |.  </body>.</htm|
00000040  6c 3e                                             |l>|
00000042
$ hexdump -C secret.enc     
00000000  09 58 ca bb 89 66 e7 85  31 70 5a 4b 54 59 1e b0  |.X...f..1pZKTY..|
00000010  b4 1d 57 94 12 53 d0 0b  79 3f 0e b6 67 c7 a6 7e  |..W..S..y?..g..~|
00000020  42 78 e1 39 5f 3c 8a f6  9b 2a c1 0d 3e bd 97 75  |Bx.9_<...*..>..u|
00000030  c0 c9 42 08 cf d2 c5 a8  16 cd ee 73 1a af ce 7c  |..B........s...||
00000040  d8 2b bc 4a 38 04 69 80  01 91 6b d1 74 5d 52 9d  |.+.J8.i...k.t]R.|
00000050

The AES block size is 128 bit, which means 16 bytes, so exactly one row of the hexdump output. You can see that the last plaintext row is smaller than one block. In this case the missing bytes are added before the encryption. This is called padding and is the reason the ciphertext has 5 complete blocks.

In CBC mode, decryption of ciphertext blocks other than the first one works like this:

{n+1-th plaintext block} =
  AES_decrypt({n+1-th ciphertext block}, key) XOR
  {n-th ciphertext block}

So by changing the n-th ciphertext block, we can change the outcome of the decryption of the n+1-th ciphertext block.

Okay, let's change the start of the second block from <html> to :)____, where _ denotes a whitespace character. We do this by changing the first block of the ciphertext. The algorithm for this is exactly the same as in the case of the IV, with the only difference that we use the first ciphertext block instead of the IV.

As we can see in the hexdump, the hexadecimal UTF-8 representation of <html> is 3c68746d6c3e. The one of :)____ is 3a2920202020. Let C be the first six bytes of the ciphertext. We replace them by:

  C XOR ("<html>" XOR ":)    ")
= 399ef6c358ca XOR (3c68746d6c3e XOR 3a2920202020)

Let's do it!

    0011 1100 0110 1000 0111 0100 0110 1101 0110 1100 0011 1110 (3c68746d6c3e "<html>")
XOR 0011 1010 0010 1001 0010 0000 0010 0000 0010 0000 0010 0000 (3a2920202020, ":)   ")
    -----------------------------------------------------------
    0000 0110 0100 0001 0101 0100 0100 1101 0100 1100 0001 1110

    0000 1001 0101 1000 1100 1010 1011 1011 1000 1001 0110 0110 (0958cabb8966, start of first block)
XOR 0000 0110 0100 0001 0101 0100 0100 1101 0100 1100 0001 1110 (last result)
    -----------------------------------------------------------
    0000 1111 0001 1001 1001 1110 1111 0110 1100 0101 0111 1000

So we must replace the first 6 bytes of the ciphertext by 0f199ef6c578. First, we write these bytes in a file:

$ echo 0f199ef6c578 | basenc --base16 -d > secret-modified.enc

Now, we add everything from secret.enc but the first 6 bytes to the new file:

$ dd if=secret.enc bs=6 skip=1 >> secret-modified.enc

Finally, we decrypt the modified file:

$ openssl enc -aes-256-cbc -d \
    -in secret-modified.enc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c \
    > secret-modified.html

Now, the secret-modified.html file should look like this:

{ binary garbage }:)
  <body>
    Hello World!
  </body>
</html>

Great, we managed to replace <html> (the start of the second block) by :). The only problem is that we had to change the first ciphertext block for this. So the first plaintext block is of course no longer <!DOCTYPE html> but just 16 bytes of garbage.

Two thoughts on this garbage phenomenon. First, it shows how resistant the CBC mode is against data corruption. After all, we have only one block of garbage, the rest of the decrypted file seems okay. And in fact, if one block of the ciphertext is corrupted, only itself and the following block are impacted.

Second, if we are lucky, we might be able to hide the 16 bytes of garbage from our victim that decrypts and displays the file we tampered with. An HTML document will likely be displayed in a browser. So we could try to choose the changed block in a way that the garbage bytes become part of an (not exactly spec compliant) HTML tag. For example, if there was no newline after <!DOCTYPE html>, the hexdump of our original secret.html would look like this:

$ hexdump -C secret.html       
00000000  3c 21 44 4f 43 54 59 50  45 20 68 74 6d 6c 3e 3c  |<!DOCTYPE html><|
00000010  68 74 6d 6c 3e 0a 20 20  3c 62 6f 64 79 3e 0a 20  |html>.  <body>. |
00000020  20 20 20 48 65 6c 6c 6f  20 57 6f 72 6c 64 21 0a  |   Hello World!.|
00000030  20 20 3c 2f 62 6f 64 79  3e 0a 3c 2f 68 74 6d 6c  |  </body>.</html|
00000040  3e                                                |>|
00000041

In such a scenario we could tamper with the second ciphertext block and try to change the third block to something containing >:). For example, the result could be:

$ hexdump -C secret-modified.html       
00000000  3c 21 44 4f 43 54 59 50  45 20 68 74 6d 6c 3e 3c  |<!DOCTYPE html><|
00000010  xx xx xx xx xx xx xx xx  xx xx xx xx xx xx xx xx  |    garbage     |
00000020  3e 3a 29 48 65 6c 6c 6f  20 57 6f 72 6c 64 21 0a  |>:)Hello World!.|
00000030  20 20 3c 2f 62 6f 64 79  3e 0a 3c 2f 68 74 6d 6c  |  </body>.</html|
00000040  3e                                                |>|
00000041

In this case, the user will never see the suspicous 16 bytes of garbage, because the browser ignores tags it doesn't know.

Bit flipping Attack on CBC: Change of the IV

Moritz Höppner — Sat, 04 Jan 2025 07:21:33 +0000

Given an AES-CBC encrypted ciphertext, it is possible to change the outcome of the decryption in a predictable way: If you know some bytes of the first plaintext block, you can change these bytes by changing the initialization vector (IV). This is one type of a so called bit flipping attack. It doesn't matter if we use AES or some other block cipher. But I will demonstrate the attack with AES-256. To follow this tutorial, you'll only need a shell on a *nix operating system with the OpenSSL command line utility installed.

I won't explain the details of CBC; if you're not familiar with it, I recommend the relevant section of Crypto 101. There you'll find also the description of a more realistic use case for bit flipping attacks, that is: smuggling content into encrypted cookies.

Let's say, the original plaintext is Hello World!, encoded in UTF-8 or some similar encoding scheme (similar in the sense that one ASCII character is encoded by one byte and that the encoding is an extension of ASCII).

To generate the ciphertext, we need a 256-bit key and an IV with the length of one
block, i.e. 128 bit. We'll use be154e2343408caa1f11ab3445bdd34c as IV and
be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c as key (both are given here in hexadecimal representation).

We generate the ciphertext with OpenSSL:

$ echo "<p>Hello World!</p>" | openssl enc -aes-256-cbc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c \
    > ciphertext.enc

Let's assume that we want the decrypted text to be :) Hello World!. This means that the IV must be changed so that  (3c703e in hexadecimal UTF-8 representation) becomes :)_ (3a2920 in hexadecimal UTF-8 representation), where _ denotes a whitespace character.

To generate the new IV, take the first three bytes of the original IV, say abc, and calculate:

  abc XOR ("<p>" XOR ":) ")
= be154e XOR (3c703e XOR 3a2920)

I'll explain below why this does the trick. First the calculation:

    0011 1100 0111 0000 0011 1110 (3c703e, original plaintext, "<p>")
XOR 0011 1010 0010 1001 0010 0000 (3a2920, desired output, ":) ")
---------------------------------
    0000 0110 0101 1001 0001 1110

    1011 1110 0001 0101 0100 1110 (be154e, initial segment of IV)
XOR 0000 0110 0101 1001 0001 1110 (last result)
---------------------------------
    1011 1000 0100 1100 0101 0000

The result is b84c50 in hexadecimal representation. So the new IV is b84c502343408caa1f11ab3445bdd34c.

Test it by decrypting the ciphertext with it:

$ openssl enc -aes-256-cbc -d \
    -in ciphertext.enc \
    -iv b84c502343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c

Voilà, you should see :) Hello World!.

Why does this IV do what we want? Well, because of how CBC works, we know:

AES_decrypt(first_ciphertext_block, key) XOR IV = first_plaintext_block

If xyz are the first three bytes of the result of AES_decrypt, and abc are the first three bytes of the IV, we have:

xyz XOR abc = "<p>"

We changed the first three bytes of the IV by XORing the original plaintext and the desired output. So, the question is: Why does the following hold?

xyz XOR (abc XOR ("<p>" XOR ":) ")) = ":) "

Well, here is why:

  xyz XOR (abc XOR ("<p>" XOR ":) "))
= (xyz XOR abc) XOR ("<p>" XOR ":) ")  [because XOR is associative]
= "<p>" XOR ("<p>" XOR ":) ")          [as noted above]
= ("<p>" XOR "<p>") XOR ":) "          [because XOR is associative]
= ":) "                                [because x XOR x = 0 and 0 XOR x = x]