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.
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.
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 (hence Galois). The exact form of this polynomial is not too important; it suffices to know that the tag for a ciphertext can be expressed as:
where and are some elements of generated from the key, and is the th 128-bit block of the ciphertext (interpreted as an element of ). A nice thing about this formula is that it is linear in each of the blocks . Among other things, this implies that if (and all these ciphertexts are the same length), then .
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: