PoliCTF 2015 - 3DOGES2

Introduction

3DOGES2 is a service from the cryptography section of the PoliCTF 2015 worth 400 points. It is written in Go and does some crypto involving 3DES in CBC mode. The source code was given and can be found in the appendix. A typical communication with the service looks like the following:

< Welcome! Wanna talk with John? Follow the instructions to get a Secure™ Channel.
< dd94f8bb1f51a3d7637489cc712a3725dff8e69f7aa68789ec43903a7d45d03ede21bbdda8c34ce3f1dd7008c5a1ca2ec1a86d695d493dcb38d4c80142ddf64007c08c2bcc57fe9be01435f379f139ef6d5f8944fc0cdd15ef5c027aab9c5d43
<
< You surely know what to do with this:
< 0edef9812a0b7bd409cefd4b0732aa3df368cffa92d32b3c75f0640962a7a931
<
< Insert key:
> Cyclopropenylidene
< JOHN IS ANGRY.

("< " denotes data sent from the server to the client and "> " from the client to the server)

General overview of the service

Let's take a look at what the service actually does. In the main function we see some cryptographic key ede2Key, which is at least 16 bytes long. This key is processed by some obfuscation function named muchSecurity and used as a key for 3DES in CBC mode afterwards. See function NewTripleDOGESCipher which makes a new des.TripleDESCipher and encrypt which uses cipher.NewCBCEncrypter after padding the input with padSlice to 64 bit blocks.

The IV for CBC mode is randomly generated and prepended to the ciphertext. There are two hex strings in the example communication above. Both are encryptions of some strings. The first one is the encryption of the string "nWelcome! Wanna talk with John? [...]", the second one contains the encrypted challenge key we have to enter after "Insert Key:".

Our goal is to somehow decrypt the second string. For this we need the plaintext/ciphertext pair in the first string.

Analyzing `muchSecurity`

For reference, here is the mentioned obfuscation function:

func muchSecurity(key []byte) []byte {
    var tripleDOGESKey []byte

    secondKey := make([]byte, 16)
    copy(secondKey, key)
    for i := 8; i < 16; i++ {
        // Let's be sure it is enough complex. Complex is good, a friend told us so.
        key[i] = (secondKey[i] & 0x3c) | (suchSubstitution[(secondKey[i] >> 2) & 0x0f] << 6)
        key[i] |= (key[i] >> 3) & 0x03
        key[i] |= ((key[i] >> 4) ^ key[i]) << 7
    }

    // EDE2 is required.
    tripleDOGESKey = append(tripleDOGESKey, key[:8]...)
    return append(tripleDOGESKey, key[:16]...)
}

Lets look at the modifications of key first. The for loop will only change bytes 8 to 16. There are no interdependencies between the bytes of the key, because it only accesses key[i] or secondKey[i] (which is just a needlessly preserved copy). Rather than analysing shifts, ands, xors we can build a lookup table for each input byte. This is possible because of the missing interdependencies. Actually we don't need a lookup table in our attack, but only a set of the possible values. The 16 values are: {0x44, 0xc9, 0x8d, 0xd2, 0x96, 0x1b, 0x5f, 0x20, 0x64, 0xa9, 0xad, 0xf2, 0xf6, 0x7f}. See getK3Alphabet in our attack implementation for how to obtain them in detail.

For the final result it initializes an empty key tripleDOGESKey which will be returned. It consists of the first 8 bytes of key, followed by the first 16 bytes of key. As a result our tripleDOGESKey, which will be used for 3DES, will have 24 bytes. Sadly this is way too much to do an exhaustive search on the key space.

The 24 byte key in 3DES is split into 3 three keys of 8 bytes each. We will call them K1, K2 and K3 respectively. Each key will be used for one DES operation.

As you might already noticed, K1 and K2 are the same (we append the first 8 bytes followed by the first 16 bytes of key). This reduces the key space, but even an 8 byte key space would still be too much for our available computational resources. Additionally K3 depends on K1/K2, but we can ignore this dependency in our attack (see explanation below).

The attack

Our attack simply does exhaustive search on K3, which is the only thing we have to obtain. To see why, we have to take a look at how 3DES works. 3DES encrypts by using three DES operations in the following way:

ciphertext = E(K3, D(K2, E(K1, plaintext)))

E stands for encryption, D for decryption. Since K1 equals K2, we can simplify this to:

ciphertext = E(K3, plaintext)

Yay! K1 and K2 are gone, we don't have to take care of them. 3DES with equal K1 and K2 is basically DES with K3.

As explained in the previous section, we have only 16 values for each byte of K3. If we want to do exhaustive search, we just have to try 16^8 = (2^4)^8 = 2^32 keys. This is still computational expensive, but feasible.

Lets remember how CBC works:

                +-----+         +-----+
                | m0  |         | m1  |           [...]
                +--+--+         +--+--+
                   |               |
                   |               |
                  \|/             \|/
           +---->(XOR)     +---->(XOR)     +---->
           |       |       |       |       |
           |       |       |       |       |
           |      \|/      |      \|/      |
           |  +----+----+  |  +----+----+  |
           |  | E(K, *) |  |  | E(K, *) |  |
           |  +----+----+  |  +----+----+  |
           |       |       |       |       |
           |       |       |       |       |
           |      \|/      |      \|/      |
+-----+    |    +--+--+    |    +--+--+    |
| IV  +----+    | c0  +----+    | c1  +----+      [...]
+-----+         +-----+         +-----+

m0, m1, ... are the message blocks, c0, c1, ... the corresponding cipher blocks. IV is the initialization vector, which is prepended to the ciphertext. E(K, *) encrypts * (which is some message block XORed with the previous ciphertext block or IV) with key K, in this case using DES.

To do exhaustive search on K3 we simply try all possibilities by encrypting (m0 XOR IV) with DES and check for equality with c0. If it is equal we have found the key K3 with very high probability (there might be a negligible chance of finding another key with this property, but we can safely ignore that). In our case m0 is "nWelcome", IV is "xddx94xf8xbbx1fx51xa3xd7" and c0 is "x63x74x89xccx71x2ax37x25".

Another way would be to encrypt the whole string with DES in CBC mode, but that would require 11 DES operations per key instead of 1, thus being much slower.

We ran our implementation in the cloud on a machine with 16 cores. It took about 1 hour to find the key. To solve the challenge we have to decrypt the challenge key, which needs to be entered after "Insert Key:". This can be done easily by using DES in CBC mode with our obtained key K3. After entering the result of the decryption we obtain the flag:

< Insert key:
> Root superpassword
> Amazing! Flag: flag{!wow-such-flag-much-crypto-amazing}

See the appendix for the implementation of this attack.

Appendix

Our implementation of the attack:

package main

import (
   "bytes"
   "crypto/cipher"
   "crypto/des"
   "encoding/hex"
   "fmt"
   "log"
   "os"
   "runtime"
)

// Change these values to what you get from the communication with the service
const PLAINTEXT = "\nWelcome! Wanna talk with John? Follow the instructions to get a Secure™ Channel.\n"
const CIPHERTEXT = "dd0d5bd3b14540169c513b276e97948b0d34f390114ebd8aea6f85610beed8d0d8120b891504b52b70a172a72438be1554b59c6ef0fdfbcaabb663e8a6481122934edfd951acbfbe44c5c51f259d0f91669701f051be53858b462cbc27d13ba1"
const CHALLENGE = "0b3dfc6a7a4945a6fea0d63cb9c7e267823c0240a5c7db8730eec4ae7cd672e6"

var suchSubstitution = [32]byte{
   0, 1, 1, 0, 1, 0, 0, 1,
   0, 1, 0, 0, 1, 1, 0, 1,
   0, 0, 1, 1, 1, 0, 1, 0,
   0, 1, 1, 0, 1, 1, 0, 0,
}

func main() {
   runtime.GOMAXPROCS(20)
   exhaustiveSearchK3()
}

func exhaustiveSearchK3() {
   plaintext := []byte(PLAINTEXT)
   ciphertext, err := hex.DecodeString(CIPHERTEXT)
   if err != nil {
      log.Fatal("Could not decode hex string for plaintext/ciphertext pair")
   }
   if len(plaintext) < des.BlockSize || len(ciphertext) < des.BlockSize {
      log.Fatal("Plaintext/ciphertext pair must at least one DES block long")
   }

   progressChan := make(chan uint64)
   resultChan := make(chan []byte)
   alphabet := getK3Alphabet()
   for i := 0; i < len(alphabet); i++ {
      go exhaustiveSearchK3Worker(plaintext, ciphertext, alphabet, i, progressChan, resultChan)
   }

   cnt := uint64(0)
   maxCnt := uint64(1 << 32)
   for {
      select {
      case threadCnt := <-progressChan:
         cnt += threadCnt
         fmt.Printf("\rExhausted %f%% of the key space", float64(cnt)/float64(maxCnt)*100.0)
      case key := <-resultChan:
         fmt.Println("\nFound K3:", key)
         fmt.Println("Challenge key:", decryptChallengeKey(key))
         os.Exit(0)
      }
   }
}

func exhaustiveSearchK3Worker(plaintext []byte, ciphertext []byte, alphabet []byte, threadNo int, progressChan chan uint64, resultChan chan []byte) {
   // IV, c0 and (m0 XOR IV)
   iv := ciphertext[:des.BlockSize]
   c0 := ciphertext[des.BlockSize : 2*des.BlockSize]
   m0XorIV := make([]byte, des.BlockSize)
   for i := 0; i < des.BlockSize; i++ {
      m0XorIV[i] = plaintext[i] ^ iv[i]
   }

   cnt := uint64(0)
   key := make([]byte, 8)
   out := make([]byte, des.BlockSize)

   // Parallization is done by assigning the first key byte a certain value
   // based on the thread number.
   key[0] = alphabet[threadNo]

   // Nested loop to build all key permutations. It might be somewhat ugly,
   // but is very fast/easy to implement and efficient. You know, at CTFs
   // time counts.
   for _, i1 := range alphabet {
      key[1] = i1
      for _, i2 := range alphabet {
         key[2] = i2
         for _, i3 := range alphabet {
            // For performance reasons we don't sent our count after every
            // DES operation. This position is a good tradeoff between
            // seeing progress and not degrading performance
            progressChan <- cnt
            cnt = 0
            key[3] = i3
            for _, i4 := range alphabet {
               key[4] = i4
               for _, i5 := range alphabet {
                  key[5] = i5
                  for _, i6 := range alphabet {
                     key[6] = i6
                     for _, i7 := range alphabet {
                        key[7] = i7

                        // Finally encrypt (m0 XOR IV)
                        cipher, err := des.NewCipher(key)
                        if err != nil {
                           log.Fatal("Could not initialize cipher")
                        }
                        cipher.Encrypt(out, m0XorIV)

                        // And compare it with c0.
                        // If it matches we (probably) have found the key.
                        if bytes.Equal(out, c0) {
                           resultChan <- key
                           return
                        }
                        cnt++
                     }
                  }
               }
            }
         }
      }
   }
}

func getK3Alphabet() []byte {
   alphabet := make([]byte, 0)
   duplicates := make(map[byte]bool)
   for i := 0; i < 256; i++ {
      character := muchSecuritySimple(byte(i))
      if duplicates[character] {
         continue
      }
      alphabet = append(alphabet, character)
      duplicates[character] = true
   }
   return alphabet
}

func muchSecuritySimple(k byte) byte {
   k = (k & 0x3c) | (suchSubstitution[(k>>2)&0x0f] << 6)
   k |= (k >> 3) & 0x03
   k |= ((k >> 4) ^ k) << 7
   return k
}

func decryptChallengeKey(key []byte) string {
   ciphertext, err := hex.DecodeString(CHALLENGE)
   if err != nil {
      log.Fatal("Can't decode ciphertext hex string to get challenge key")
   }
   if len(ciphertext)%des.BlockSize != 0 {
      log.Fatal("Encrypted challenge key must be a multiple of DES block size")
   }

   desCipher, err := des.NewCipher(key)
   if err != nil {
      log.Fatal("Can not initialize DES cipher")
   }
   iv := ciphertext[:des.BlockSize]
   ciphertext = ciphertext[des.BlockSize:]
   plaintext := make([]byte, len(ciphertext))
   mode := cipher.NewCBCDecrypter(desCipher, iv)
   mode.CryptBlocks(plaintext, ciphertext)

   return string(plaintext)
}

The given source code of 3DOGES2:

package main

import (
    "crypto/des"
    "crypto/cipher"
    "crypto/rand"
    "errors"
    "io"
    "fmt"
    "log"
    "net"
    "os"
    "bytes"
    "encoding/hex"
)

const (
    CONN_HOST = "0.0.0.0"
    CONN_PORT = "8000"
    CONN_TYPE = "tcp"
)

var suchSubstitution = [32]byte{
    0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 0, 0, 1, 1, 0, 1,
    0, 0, 1, 1, 1, 0, 1, 0,
    0, 1, 1, 0, 1, 1, 0, 0,
}

func main() {
    ede2Key := []byte("<-- Some supersecret encryption key goes here -->")

    // Create a new instance of our magic cipher. Wow.
    tripleDOGESKey := muchSecurity(ede2Key)
    muchCipher, err := NewTripleDOGESCipher(tripleDOGESKey)
    if err != nil {
        log.Fatal(err)
    }

    // Listen for incoming connections.
    l, err := net.Listen(CONN_TYPE, CONN_HOST+":"+CONN_PORT)
    if err != nil {
        fmt.Println("Error listening:", err.Error())
        os.Exit(1)
    }
    // Close the listener when the application closes.
    defer l.Close()
    fmt.Println("Listening on " + CONN_HOST + ":" + CONN_PORT)
    for {
        // Listen for an incoming connection.
        conn, err := l.Accept()
        if err != nil {
            fmt.Println("Error accepting: ", err.Error())
            os.Exit(1)
        }
        // Handle connections in a new goroutine.
        go handleRequest(conn, muchCipher)
    }
}

// Handles incoming requests.
func handleRequest(conn net.Conn, muchCipher cipher.Block) {
    // Whoops.
    superkey := []byte("<-- Some amazing program key goes here -->")
    success := []byte("Amazing! Flag: <-- Some incredible flag goes here -->\n")
    failure := []byte("JOHN IS ANGRY.\n")

    // Print things.
    plain := []byte("\nWelcome! Wanna talk with John? Follow the instructions to get a Secure™ Channel.\n")
    cipherthings := make([]byte, 1024)
    ciphertext := encrypt(plain, muchCipher)
    hex.Encode(cipherthings, ciphertext)
    plain = append(plain, cipherthings...)
    conn.Write(plain)

    plain = []byte("\n\nYou surely know what to do with this:\n")
    cipherthings = make([]byte, 1024)
    ciphertext = encrypt(superkey, muchCipher)
    hex.Encode(cipherthings, ciphertext)
    plain = append(plain, cipherthings...)
    conn.Write(plain)

    request := []byte("\n\nInsert key:\n")
    conn.Write(request)

    // Make a buffer to hold incoming data.
    buf := make([]byte, 1024)
    // Read the incoming connection into the buffer.
    reqLen, err := conn.Read(buf)
    if err != nil {
        fmt.Println("Error reading:", err.Error())
    }

    // Send a response back to our friends.
    if bytes.Contains(buf[:reqLen], superkey) {
        conn.Write(success)
    } else {
        conn.Write(failure)
    }

    // Close the connection when you're done with it.
    conn.Close()
}

func NewTripleDOGESCipher(tripleDOGESKey []byte) (cipher.Block, error) {
    // I can't break it, so it is unbreakable. A friend told us so.
    muchCipher, err := des.NewTripleDESCipher(tripleDOGESKey)
    if err != nil {
        return nil, err
    }
    return muchCipher, nil
}

func encrypt(text []byte, block cipher.Block) []byte {
    if len(text)%des.BlockSize != 0 {
        text = padSlice(text)
    }

    ciphertext := make([]byte, des.BlockSize+len(text))
    iv := ciphertext[:des.BlockSize]
    if _, err := io.ReadFull(rand.Reader, iv); err != nil {
        log.Fatal(err)
    }

    mode := cipher.NewCBCEncrypter(block, iv)
    mode.CryptBlocks(ciphertext[des.BlockSize:], text)

    return ciphertext
}

func decrypt(text []byte, block cipher.Block) []byte {
    if len(text) < des.BlockSize {
        log.Fatal(errors.New("ciphertext too short"))
    }
    iv := text[:des.BlockSize]
    text = text[des.BlockSize:]

    // CBC mode always works in whole blocks.
    if len(text)%des.BlockSize != 0 {
        text = padSlice(text)
    }

    mode := cipher.NewCBCDecrypter(block, iv)
    dst := make([]byte, len(text))
    mode.CryptBlocks(dst, text)

    return dst
}

func muchSecurity(key []byte) []byte {
    var tripleDOGESKey []byte

    secondKey := make([]byte, 16)
    copy(secondKey, key)
    for i := 8; i < 16; i++ {
        // Let's be sure it is enough complex. Complex is good, a friend told us so.
        key[i] = (secondKey[i] & 0x3c) | (suchSubstitution[(secondKey[i] >> 2) & 0x0f] << 6)
        key[i] |= (key[i] >> 3) & 0x03
        key[i] |= ((key[i] >> 4) ^ key[i]) << 7
    }

    // EDE2 is required.
    tripleDOGESKey = append(tripleDOGESKey, key[:8]...)
    return append(tripleDOGESKey, key[:16]...)
}

func padSlice(src []byte) []byte {
    // src must be a multiple of block size.
    bs := des.BlockSize
    mult := int((len(src) / bs) + 1)
    leng := bs * mult

    src_padded := make([]byte, leng)
    copy(src_padded, src)
    return src_padded
}