SharifCTF 7 – GCM Magic

In this Crypto challenge, we are given access to a webserver which implements GCM encryption and decryption on user provided strings. There is also a “forbidden” plaintext which the server will refuse to encrypt. At first it’s a little unclear where the flag is, but given that there’s a forbidden plaintext, it makes sense to find a ciphertext/tag/nonce combination that decrypts to that plaintext. Indeed, successfully doing this results in the server returning the flag.

screen-shot-2016-12-20-at-3-24-34-pm

We didn’t know anything about GCM before doing this problem, so we spent a lot of time reading up on the implementation of GCM, in particular this NIST paper. It turns out however, that there is a solution to this challenge which doesn’t really rely on any of the technical details of GCM. We’ll try to summarize the important aspects of GCM below; this summary took a while for us to figure out from the above paper, so hopefully it will prove useful to other people reading this.

GCM stands for Galois/Counter Mode encryption. At its core, GCM is a stream cipher constructed from a block cipher using what is called Counter Mode operation. You might be familiar with other techniques (‘modes’) for converting block ciphers (i.e. functions which encrypt fixed-bit size inputs) to stream ciphers (i.e. functions which encrypt arbitrary size inputs). The simplest such method (although incredibly insecure) is what’s called Electronic Codebook (ECB); basically, divide your stream into blocks of the appropriate size, and apply the block cipher to each block. The Counter Mode is only slightly more complicated; instead of encrypting each block, instead encrypt a counter (a nonce followed by the index of the block) and XOR this with the block.

ctr_encryption

This solves some of the worst problems with schemes like ECB, but is open to other vulnerabilities. One such vulnerability is that, even if an adversary cannot decrypt arbitrary messages, if he knows the ciphertext for any one plaintext, he can generate the ciphertext for any other plaintext by simply XORing the difference in plaintexts with the ciphertext. This allows for the possibility of e.g. performing man-in-the-middle attacks. We can easily get the correct ciphertext this way (note: for all encryptions/decryptions, we’re using the example nonce value).

forbidden plaintext = 506c656173652067697665206d652074686520666c616721

P = 506c656173652067697665206d652074686520666c616720 # differs from forbidden plaintext in last bit
E(P) = 7396aeed0929e00c260d013749dce7a0bce963b6f4c4b351
--> E(forbidden plaintext) = 7396aeed0929e00c260d013749dce7a0bce963b6f4c4b350

Unfortunately we can’t just plug this in and get the flag, because we also need to provide a “tag.” This is where the Galois part of GCM comes in: one solution to the aforementioned vulnerability is an authentication component to the encryption (the “tag”) that can be used to verify that someone with access to the key encrypted the message. This “tag” is essentially a hash computed by some polynomial over \mathbb{F}_{2^{128}} (hence Galois). The exact form of this polynomial is not too important; it suffices to know that the tag for a ciphertext C can be expressed as:

TAG(C) = b_0 + (\mathrm{len}(C))H + (C_1H^2 + C_2H^3 + \dots + C_kH^{k})

where b_0 and H are some elements of \mathbb{F}_{2^{128}} generated from the key, and C_i is the ith 128-bit block of the ciphertext (interpreted as an element of F_{128}). A nice thing about this formula is that it is linear in each of the blocks C_i. Among other things, this implies that if C^{(a)} + C^{(b)} = C^{(c)} + C^{(d)} (and all these ciphertexts are the same length), then TAG(C^{(a)}) + TAG(C^{(b)}) = TAG(C^{(c)}) + TAG(C^{(d)}).

This immediately suggests a way to compute the tag of the forbidden plaintext: we simply take two plaintexts that differ in some bit, compute their tag, and then compute the tag of the plaintext that differs from the forbidden plaintext in the same bit. XORing all of the results, we can get the tag of the forbidden plaintext (and hence solve the challenge).

forbidden plaintext = 506c656173652067697665206d652074686520666c616721

Pa = 000000000000000000000000000000000000000000000000
Ca = 23facb8c7a4cc06b4f7b641724b9c7d4d48c43d098a5d471
Ta = b4c9629a2ab7c4bd55285d3109391fc

Pb = 000000000000000000000000000000000000000000000001
Cb = 23facb8c7a4cc06b4f7b641724b9c7d4d48c43d098a5d470
Tb = 6e01d1dc33cb46e8d7585605a959c030

Pc = 506c656173652067697665206d652074686520666c616720 # differs from forbidden plaintext in the last bit
Cc = 7396aeed0929e00c260d013749dce7a0bce963b6f4c4b351
Tc = b8df54702989242e9838f2726ecafac7

C = 7396aeed0929e00c260d013749dce7a0bce963b6f4c4b350
T = dd921385b8e91e8d9a3221a4d700ab0b # Ta ^ Tb ^ Tc

Plugging C, T, and the nonce into the decryption oracle gives the flag:

screen-shot-2016-12-20-at-3-37-36-pm

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s