# GCM - Nullcon HackIM CTF 2019

tl;dr

1. CTR Bit Flipping
2. Break GHASH to get authentication key H (unintended approach)
3. Bypass authentication

Challenge Points: 300
Challenge Solves:
Solved by: s0rc3r3r, v3ct0r and v4d3r

Non-polynomial version of GHASH; can be broken using very basic Number Theoretic concepts.

The way we solved it (unintended approach) was pretty interesting!

## Challenge Internals

We are given a service that allows us to encrypt/decrypt data using AES-CTR mode. Code for this is as follows:

As you can see, the service does not allow encrypting messages that contain “flag” as a substring. Also, when we choose to decrypt data, the service checks if the decrypted data is equal to “may i please have the flag”
and gives the flag only if it is true.

Clearly, we will have to bypass the above service:

1. Encrypt some data that does not contain “flag”, let us say “may i please have the flak”
2. Flip some bytes and get ciphertext of “may i please have the flag”
3. Send ciphertext obtained in step-(2) for decryption and get the actual flag

If what we just described in the above steps is correct, then a simple CTR Bit Flipping attack would be
sufficient to get the flag.

But things are not easy as they seem to be. Let us look at the encryption and decryption functions:

As you can see, encrypt() not only encrypts our plaintext, but also creates an authentication tag - tag that
happens to be a mitigation to CTR Bit Flipping Attack. Also, decrypt() function verifies if the authentication
tag calculated from the ciphertext and authentication tag - tag given as input, match.

An authentication tag is basically a string assigned to a plaintext/ciphertext as a unique identifier. This means that if we flip bytes, we will not have the authentication tag of the corresponding new flipped data and we
won’t be able to get the flag.

This immediately shifts our target to the function that creates an authentication tag, and search for vulnerabilities that can be exploited, so that we can bypass the authentication.

## Analysis of GHASH

Function for generating authentication tag - GHASH()

Authentication tag - tag for a k-block plaintext is generated as:
$tag = c + ((b_1 *(H^1;%;n));%;n) + ((b_2 *(H^2;%;n));%;n) + … + ((b_k *(H^k;%;n));%;n)$

For a 1-block ciphertext, we can write:
$tag = c+((b_1 + (H^1;%;n));%;n)$

Thus, if we have c for every session, we can calculate secret value H as:
$(tag-c)*(b^{-1}\mod n) \equiv H^1 \mod n$

## Retrieving c - unintended approach

We know that c is AES ECB encryption of (nonce + “\x00\x00\x00\x01”)

We observe that:
AES ECB encryption of (nonce + “\x00\x00\x00\x01”) is the same as “z”*16 (one block containing of z‘s - 16 bytes) XORed with AES CTR encryption of “z”*16 (one block of z‘s - 16 bytes).

That is:
(AES_ECB_enc(nonce + "\x00\x00\x00\x01")) == (("zzzzzzzzzzzzzzzz") xor (AES_CTR_enc("zzzzzzzzzzzzzzzz"))).

To get c, we simply send “z”*16 to the service for encryption and xor the result with “z”*16 to get c

## Getting the flag

Now that we know how to calculate c, we can get the flag with the following steps:

1. Encrypt some data that does not contain “flag”, let us say “may i please have the flak”
2. Flip some bytes and get ciphertext of “may i please have the flag”
3. Calculate H, get authentication tag for “may i please have the flag”
4. Send ciphertext obtained in (2) for decryption, along with authentication tag obtained in (3) and get the
actual flag!

Full exploit:

Running this script gave us the flag: hackim19{forb1dd3n_made_e4sy_a7gh12}