Tuesday, October 2, 2012

DerbyCon, CTF, Crypto Attacks, 42...

First post! Been putting this off for a while. Basically this is just a place for me to collect all my random research and experiences in one place. As of now they are scattered all over Google docs, Reddit, my hard disk, my brain (very volatile storage) and various other places. The writing may be terrible, but hopefully the content makes up for it. So here we go...

Just had an amazing first experience at a conference, DerbyCon! Even if I only made two talks. The CTF was a blast, myself and the rest of team JollyAndFriends owned it. Although it was really tight, right down to the last 15m and we only won by 10pts. It was amazing to meet and work with the whole team and guys like mubix who hung around and grinded away at a couple of the challenges with us for a while. Props to the organizers and attendees of the con.

This was actually my second CTF and I think I may be addicted. The Stripe web CTF was also amazingly well done, although I participated in that one solo. At some point in the near future I'll probably give it its own dedicated blog post describing my approach to some of the more interesting challenges.

Pretty happy I actually got to put some of my research into practice in the form of a really basic crypto attack for the Derby CTF. I plan on posting my crypto notes/research/attack code some time later, but the simple attack used in the CTF was the following:

We were provided with 3 files, "plain1_encrypted", "plain2_encrypted", "plain2"; they represent exactly what their names imply, some encrypted and plain text files. We were also provided with the binaries used for the encryption and decryption routines, but that is actually irrelevant, they didn't contain keys and you don't really need them.

The unencrypted plain text file "plain2" had the following contents:


0x80085:fu2 breens$ xxd plain2
0000000: 4b43 3537 4b43 3537 4b43 3537 4b43 3537  KC57KC57KC57KC57
0000010: 4b43 3537 4b43 3537 4b43 3537 4b43 3537  KC57KC57KC57KC57
0000020: 4b43 3537 4b43 3537 4b43 3537 4b43 3537  KC57KC57KC57KC57
0000030: 4b43 3537 4b43 3537 4b43 3537 4b43 3537  KC57KC57KC57KC57
0000040: 4b43 3537 4b43 3537 4b43 3537 4b43 3537  KC57KC57KC57KC57
0000050: 4b43 3537 4b43 3537 4b43 3537 4b43 3537  KC57KC57KC57KC57
0000060: 4b43 3537 4b43 3537 4b43 3537 4b43 3537  KC57KC57KC57KC57


The hex dumps of the two encrypted files were as follows:
0x80085:fu2 breens$ xxd plain2_encrypted

0000000: 0bb7 b2ef ebc7 6a8e 5ac6 51d6 507d 82af  ......j.Z.Q.P}..
0000010: 0980 0e1c 201a af1c a2e2 7959 558a 89d7  .... .....yYU...
0000020: 8c1a eefc 98c7 2079 6169 3101 cdbe 9961  ...... yai1....a
0000030: 03eb 8910 face 6796 6092 d3d7 d1a6 e155  ......g.`......U
0000040: 41d7 353c 8dc5 ad42 4f65 bfff 7fdd 9135  A.5<...BOe.....5
0000050: 9556 d0f9 effa f1bc 6742 da69 9282 2ec4  .V......gB.i....
0000060: ba36 ca12 2c90 60bb a0ad dfbc 60f5 dad2  .6..,.`.....`...
0000070: 9b2e 0d94 1292 5c43 f8de 8e4f a494 644d  ......\C...O..dM

0x80085:fu2 breens$ xxd plain1_encrypted

0000000: 0bb7 b2ef a583 5abe 5ac6 51d6 1e39 b29f  ......Z.Z.Q..9..
0000010: 0980 0e1c 6e5e 9f2c a2e2 7959 1bce b9e7  ....n^.,..yY....
0000020: 8115 9a8c eec0 702d 5853 7442 d295 c910  ......p-XStB....
0000030: 24c9 db73 deca 37d5 7fb9 83ab ff9c 980d  $..s..7.........
0000040: 6694 000b c686 9875 0426 8ac8 349e a402  f......u.&..4...
0000050: 9556 d0f9 a1be c18c 6742 da69 dcc6 1ef4  .V......gB.i....
0000060: ba36 ca12 62d4 508b a0ad dfbc 2eb1 eae2  .6..b.P.........
0000070: 9b2e 0d94 1292 5c43 f8de 8e4f a494 644d  ......\C...O..dM


Notice all of the highlighted values are repeated bytes that occur in both encrypted files. The last 16 bytes (1 block) are all consecutive and all the same, this was probably some sort of IV. The repeated bytes that occur within the cipher text are more interesting...

Since the repeated bytes are separated by non repeated sections, this suggests that it could not be AES in CBC mode. Since the repetition occurs at the byte level rather than in full blocks at a time, that rules out ECB mode. We will make an educated guess at this point that the encryption algorithm in use is probably AES in CTR or OFB mode, with a static IV (bad!).

The way that AES in a steam cipher mode like OFB or CTR works is that the AES algorithm is used to encrypt the IV concatenated with some other data to generate a "keystream". In CTR mode, the "other data" is a simple counter like 1,2,3,4... In OFB mode, there is feedback from previously encrypted data. I'll post far more detail in my crypto notes. This keystream is then XOR'd with the plaintext to produce the ciphertext. The danger with this approach is that if the keystream EVER repeats, this can be detected because repeated sequences of bytes will be observed in the ciphertext when the plain text contains repetition (just like we saw in the CTF).

 Due to the following relationship (easy to deduce by taking a quick look at the truth table for the XOR operation) it is trivial to decrypt text given some known plain text when the keystream is repeated:

keystream XOR plaintext = ciphertext -- therefore
ciphertext XOR plaintext = keystream

And once you have keystream, to recover the plaintext from unknown ciphertext that uses the same keystream is easy!

ciphertext XOR keystream = plaintext

So let's see that in action! I used the python interpreter to do the XOR operation:

**First we do plain2 XOR plain2_encrypted to get keystream***
>>> hex(0x4b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b4335374b433537 ^ 0x0bb7b2efebc76a8e5ac651d6507d82af09800e1c201aaf1ca2e27959558a89d78c1aeefc98c7207961693101cdbe996103eb8910face67966092d3d7d1a6e15541d7353c8dc5ad424f65bfff7fdd91359556d0f9effaf1bc6742da6992822ec4ba36ca122c9060bba0addfbc60f5dad29b2e0d9412925c43f8de8e4fa494644d)

'0xbb7b2efebc76a8e5ac651d6507d82af42c33b2b6b599a2be9a14c6e1ec9bce0c759dbcbd384154e2a2a043686fdac5648a8bc27b18d52a12bd1e6e09ae5d4620a94000bc686987504268ac8349ea402de15e5cea4b9c48b2c01ef5ed9c11bf3f175ff2567d3558cebeeea8b2bb6efe5d06d38a359d16974b39dbb78efd7517aL' **THIS IS KEYSTREAM**

**Now we do keystream XOR plain1_encrypted to get plain1***
>>> hex(0xbb7b2efebc76a8e5ac651d6507d82af42c33b2b6b599a2be9a14c6e1ec9bce0c759dbcbd384154e2a2a043686fdac5648a8bc27b18d52a12bd1e6e09ae5d4620a94000bc686987504268ac8349ea402de15e5cea4b9c48b2c01ef5ed9c11bf3f175ff2567d3558cebeeea8b2bb6efe5d06d38a359d16974b39dbb78efd7517aL ^ 0x0bb7b2efa5835abe5ac651d61e39b29f09800e1c6e5e9f2ca2e279591bceb9e781159a8ceec0702d58537442d295c91024c9db73deca37d57fb983abff9c980d6694000bc686987504268ac8349ea4029556d0f9a1bec18c6742da69dcc61ef4ba36ca1262d4508ba0addfbc2eb1eae29b2e0d9412925c43f8de8e4fa494644d)

'0x4e443030000000004e4430304b433537050705074b43353705070507464c41473d44656372797074546865466c6167546f4765745468654b65794c6f6c0000000000000000000000000000004b433537050705074b433537050705074b433537050705074b433537050705074b4335374b4335374b4335374b433537L'

If we hex decode the green highlighted hex which SHOULD be plain text, we get this:
ND00ND00KC57 KC57 FLAG=DecryptTheFlagToGetTheKeyLolKC57 KC57 KC57 KC57 KC57KC57KC57KC57

Success! So it was as easy as XORing the bytes of plain2_encrypted with the bytes of plain2 to recover keystream, then XORing those bytes with plain1_encrypted to yield the plaintext!

Moral of the story - don't use a static IV!


3 comments:

  1. This is an excellent write up. Thank you as we pulled down fu2.zip, extracted, but that was the extent of our work on this. Congrats again!

    ReplyDelete
  2. Thanks, glad you found it useful!

    ReplyDelete
  3. Very well written. Even I understood the majority of the information. I'm glad, although not surprised, that you were successful.

    Alyssa Shepard
    -The Only Juggernaut

    ReplyDelete