We are given an encrypted file (agent_log.enc), it’s corresponding plaintext (agent_log.txt), and the encryption tool source code (crypt.c). We have to find the key.

encrypt and decrypt functions:

int decrypt(const unsigned char *key, const char *infile, const char *outfile) { unsigned char buf[16]; int result = 0, read_count = 0; FILE *fi = NULL, *fo = NULL; fail_null(fi, fopen, infile, "rb"); fail_null(fo, fopen, outfile, "wb"); while ((read_count = fread(buf, 16, 1, fi)) == 1) { permute(buf, iP2); substitute(buf, iS2); xor(buf, key); permute(buf, iP1); substitute(buf, iS1); if (fwrite(buf, 16, 1, fo) != 1) fail_not_zero(ferror, fo); } fail_not_zero(ferror, fi); done: if (fi) { fclose(fi); fi = NULL; } if (fo) { fclose(fo); fo = NULL; } return result; } int encrypt(const unsigned char *key, const char *infile, const char *outfile) { unsigned char buf[16]; int result = 0, read_count = 0; FILE *fi = NULL, *fo = NULL; fail_null(fi, fopen, infile, "rb"); fail_null(fo, fopen, outfile, "wb"); while ((read_count = fread(buf, 16, 1, fi)) == 1) { substitute(buf, S1); permute(buf, P1); xor(buf, key); substitute(buf, S2); permute(buf, P2); if (fwrite(buf, 16, 1, fo) != 1) fail_not_zero(ferror, fo); } fail_not_zero(ferror, fi); done: if (fi) { fclose(fi); fi = NULL; } if (fo) { fclose(fo); fo = NULL; } return result; }

The encrypt and decrypt functions process the data in 16 byte blocks. There are 2 permutation functions, 2 substitution functions and an inverse for each function. We introduce some new notation below:

denotes permute(x, P1);

denotes permute(x, iP1);

denotes permute(x, P2);

denotes permute(x, iP2);

denotes substitute(x, S1);

denotes substitute(x, iS1);

denotes substitute(x, S2);

denotes substitute(x, iS2);

denotes the key

denotes encryption of a single block (16 bytes)

denotes decryption of a single block (16 bytes)

denotes the XOR operation

With our new notation we then have:

Where the inverse functions work as follows:

If we start decrypting ‘agent_log.enc’ we get:

Simplifying we get:

We just applied two inverse functions to the ciphertext! In other words we undid the last 2 operations of the encryption.

If we start encrypting ‘agent_log.txt’ we get:

**The most important observation here is that none of the steps in the intermediate_encrypt and intermediate_decrypt require knowledge of the key.**

If we XOR intermediate_encrypt and intermediate_decrypt we get:

The first and last term cancel out, thus leaving us with the key.

We can actually do it in practice with very slight modifications to crypt.c, as below:

$ diff --unified crypt_old.c crypt.c --- crypt_old.c 2014-06-17 04:41:36.000000000 +0000 +++ crypt.c 2014-06-17 04:44:58.000000000 +0000 @@ -69,6 +69,8 @@ while ((read_count = fread(buf, 16, 1, fi)) == 1) { permute(buf, iP2); substitute(buf, iS2); + /* dump intermediate_decrypt bytes for first block */ + fwrite(buf, 16, 1, stdout); exit(1); xor(buf, key); permute(buf, iP1); substitute(buf, iS1); @@ -103,6 +105,8 @@ while ((read_count = fread(buf, 16, 1, fi)) == 1) { substitute(buf, S1); permute(buf, P1); + /* dump intermediate_encrypt bytes for first block */ + fwrite(buf, 16, 1, stdout); exit(1); xor(buf, key); substitute(buf, S2); permute(buf, P2);

Then we run it:

$ gcc crypt.c -w -o crypt $ ./crypt -e dummykey agent_log.txt /dev/null > intermediate_encrypt $ ./crypt -d dummykey agent_log.enc /dev/null > intermediate_decrypt $ python Python 2.7.3 (default, Sep 26 2013, 20:08:41) [GCC 4.6.3] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> xor = lambda a, b: ''.join(chr(ord(x) ^ ord(y)) for x, y in zip(a, b)) >>> xor(open('intermediate_encrypt').read(), open('intermediate_decrypt').read()) 'ShallWePlayAGame'

Shoutouts to Lopi, PenguinsHateFlags.

~ X-N2O