AES CBC Mode Encryption

If you've used javax.crypto to do encryption, then you're familiar with the code below that obtains an instance of a Cipher (note that the code below is written in Scala).

val encryptCipher = Cipher.getInstance("AES/CBC/PKCS5Padding", BouncyCastleProvider.PROVIDER_NAME)

The first parameter to getInstance is where you specify the type of encryption you want to use. In the example above, I'm using AES encryption in CBC mode This tutorial explains what CBC mode really means and what's happening under the hood.

AES encryption starts by dividing the plaintext message into 128-bit blocks. The result looks something like this:

Once the message has been divided into 128-bit blocks, the message is encrypted using CBC mode. CBC mode stands for "Cipher Block Chaining" mode. In pseudo-code, the steps of the CBC algorithm are as follows:

1. A random initialization vector (IV) is generated and then XORed with Message[0].
2. The result of the XOR operation is fed into the encryption function E(k, m) where k is the encryption key and m is result of the XOR operation.
3. The result of the encryption function becomes the first 128-bit block of the ciphertext (ciphertext[0]).
4. ciphertext[0] is then XORed with Message[1].
5. The result of the XOR operation is fed into the encryption function E(k, m) where k is the encryption key and m is the result of the XOR operation.
6. This continues until the entire message has been encrypted.

Here's what CBC mode AES encryption looks like with a picture:

You can see why it's called cipher block "chaining", as the result of each encryption function is chained to the XOR of the next plaintext message block. Note that if the message can't be divided evenly into 128-bit blocks, the last plaintext block is padded to make it 128-bits. If, however, the message divides evenly into 128-bits, the plaintext message is appended with a dummy block of 128-bits before encryption.

In a future blog post, I'll describe how AES encryption with CTR mode works, and how it differs from CBC mode.

AES Encryption Bouncy Castle Example

Here's a little example, showing how to perform AES encryption in CTR mode using Bouncy Castle. My example is in Scala, but the idea is the same for Java. I've placed all of the code on Git: https://github.com/travisdazell/AES-CTR-BOUNCYCASTLE

To start with, here's an "encrypt" method that takes a key, IV (initialization vector), and message and returns the encryption of the message under the specified key and IV. All of the method parameters are expected to be hex-encoded. Note that I'm using a utility method I created to convert the hex strings to byte arrays, which is what the crypto library expects as input. This utility method is included in the code on Git.

def encrypt(hexEncodedIv : String, hexEncodedKey : String, hexEncodedMessage : String) = {
    // we're using Bouncy Castle
    Security.addProvider(new org.bouncycastle.jce.provider.BouncyCastleProvider())

    // create our key specification
    val secretKeySpec = new SecretKeySpec(hexStringToByteArray(hexEncodedKey), "AES")
     
    // create an AES engine in CTR mode (no padding)
    val aes = Cipher.getInstance("AES/CTR/NoPadding", BouncyCastleProvider.PROVIDER_NAME)
     
    // initialize the AES engine in encrypt mode with the key and IV
    aes.init(Cipher.ENCRYPT_MODE, secretKeySpec, new IvParameterSpec(hexStringToByteArray(hexEncodedIv)))
     
    // encrypt the message and return the encrypted byte array
    aes.doFinal(hexStringToByteArray(hexEncodedMessage))
}

Our "decrypt" method will be the same as the "encrypt" method; however, instead of Cipher.ENCRYPT_MODE, we'll use Cipher.DECRYPT_MODE. Of course, we'll be passing the ciphertext to the method instead of the plaintext message.

def decrypt(hexEncodedIv : String, hexEncodedKey : String, hexEncodedCipherText : String) = {
    // we're using Bouncy Castle
    Security.addProvider(new org.bouncycastle.jce.provider.BouncyCastleProvider())

    // create our key specification
    val secretKeySpec = new SecretKeySpec(hexStringToByteArray(hexEncodedKey), "AES")
     
    // create an AES engine in CTR mode (no padding)
    val aes = Cipher.getInstance("AES/CTR/NoPadding", BouncyCastleProvider.PROVIDER_NAME)
     
    // initialize the AES engine in decrypt mode with the key and IV
    aes.init(Cipher.DECRYPT_MODE, secretKeySpec, new IvParameterSpec(hexStringToByteArray(hexEncodedIv)))
     
    // decrypt the ciphertext and return the plaintext as a byte array
    aes.doFinal(hexStringToByteArray(hexEncodedCipherText))
}

Converting a Hex String to a Byte Array in Scala

Here's a Scala method that converts a hex string to an array of bytes. This is useful when needing to encrypt a hex string, because most of the crypto libraries operate on byte arrays.

def hexStringToByteArray(s : String) = {
    val len = s.length();
    var data = new Array[Byte](len / 2)
    var i = 0

    while (i < len) {
        val b = (Character.digit(s.charAt(i), 16) << 4) +
                (Character.digit(s.charAt(i+1), 16))

        data(i / 2) = b.asInstanceOf[Byte]

        i+=2
    }

    data
}

Many Time Pad Attack - Crib Drag

The one time pad (OTP) is a type of stream cipher that is a perfectly secure method of encryption. It's very simple to implement and is perfectly secure as long as the length of the key is greater than or equal to the length of the message. That's it's major downfall. However, it also requires that the key never be used more than once. This tutorial shows what happens when you re-use a key to encrypt more than one message. I also show how to uncover the plain-text of two messages that have been encrypted with the same key, without even knowing the key. I use a method called crib dragging.

Let's begin with a brief description of OTP and how it works. Let's take the following message and key:

message = "Hello World"
key = "supersecret"

If we convert both the message and key to hex strings, we get the following:

message = "48656c6c6f20576f726c64"
key = "7375706572736563726574"

If we do a simple XOR of the two hex strings we get the following cipher-text:

cipher-text = "3b101c091d53320c000910"


If we XOR the cipher-text with the key, we can recover the plain-text. That's how OTP works. Without the key, you have no way of uncovering the plain-text.

Let's consider what happens when you have two messages encrypted with the same key. Take the following two messages and key:

message1 = "Hello World"
message2 = "the program"
key = "supersecret"

If we convert each message and the key to hex strings, and then encrypt each message using a simple XOR with the key, we'll get the following cipher-texts:

cipher-text1: "3b101c091d53320c000910"
cipher-text2: "071d154502010a04000419"


Let's say that all we have is the two cipher-texts and the knowledge that they were encrypted with a supposed OTP; however, they were both encrypted with the same key. To attack this encryption and uncover the plain-text, follow the steps below.

1. Guess a word that might appear in one of the messages
2. Encode the word from step 1 to a hex string
3. XOR the two cipher-text messages
4. XOR the hex string from step 2 at each position of the XOR of the two cipher-texts (from step 3)
5. When the result from step 4 is readable text, we guess the English word and expand our crib search.
1. If the result is not readable text, we try an XOR of the crib word at the next position.

Step 1 seems difficult (guessing a word that might appear in one of the messages), but when you think about it, the word "the" is the most commonly used English word. So, we'll start with assuming "the" is in one of the messages. After encoding "the" as a hex string, we'll get "746865". That takes care of steps 1 and 2. If we XOR the two cipher-texts, we'll get the following result:

cipher-text1 XOR cipher-text2 = "3c0d094c1f523808000d09"

The next step is to XOR our crib word "746865" at each position of the XOR of the cipher-texts. What we'll do is slide "746865" along each position of "3c0d094c1f523808000d09" and analyze the result. After the first XOR, we get the following result:

         3c0d094c1f523808000d09
XOR  746865
----------------------------------
          48656c

When we convert the hex string "48656c" to ASCII, we get the following text, "Hel". This takes us to step 5 from above. Because this looks like readable text, we can assume that the word "the" is in the first position of one message. If we didn't get readable text, we would slide "746865 (the)" one position to the right and try again (and keep repeating until the end of 3c0d094c1f523808000d09).

Note that we don't know which message contains the word "the". It could be in either message1 or message2. Next, we need to guess what the word "Hel" is when fully expanded. It could be "Help", "Hello", etc. If we guess "Hello", we can convert "Hello" to a hex string, we get "". We then XOR it with the XOR of the two cipher-texts (just like we did with "the"). Here's the result:

         3c0d094c1f523808000d09
XOR  48656c6c6f
----------------------------------
          7468652070

"7468652070"  when converted to ASCII, is "the p". We then repeat the process, guessing what "the p" might be when expanded and then XOR that result with the XOR of the cipher-texts. Granted, guessing what "the p" might expand to is not super easy, but you get the idea. If we were to guess "the program", convert it to a hex string, and XOR it with the XOR of the cipher-texts, we'll get "Hello World".

This is called crib dragging. My suggestion is to first try " the " (note the spaces before and after). Most cipher-texts that you'll try cracking will contain that word somewhere in the text. If the result of your crib drag yields gibberish, then you can be sure " the " isn't in either of the plain-text messages. So, try another commonly used English word or phrase and keep trying until the result yields something that looks like readable text. Then you can just expand your guess and keep XORing until you uncover the plain-text messages.

In a future blog post, I'll demonstrate an implementation of a crib drag in Scala.

XOR Hex-Encoded Strings in Scala

It's been said that all cryptographers do is XOR things together. Although that's not entirely true, we do find ourselves XORing things quite a bit... maybe there is some truth to that after all. Anyway, the other day, while I was writing a two-time pad attack on stream ciphers, I needed a few utility methods to make the string operations a bit easier. One of the methods was performing XOR operations on two hex-encoded strings. Here's the utility method in Scala. I posted it here in case anybody else might find it useful.

def xorHexStrings(hexString1 : String, hexString2 : String) = {
    val iterator1 = hexString1.sliding(2, 2)
    val iterator2 = hexString2.sliding(2, 2)
    val result =  new StringBuilder
        
    if (hexString2.length > hexString1.length) {
        while (iterator1.hasNext) {
            val i = Integer.toString(Integer.parseInt(iterator1.next, 16) ^
                    Integer.parseInt(iterator2.next, 16), 16)

            if (i.length == 1) result.append("0")
            result.append(i)

        }
            
        while (iterator2.hasNext) result.append(iterator2.next)
    }
    else {
        while (iterator2.hasNext) {
            val i = Integer.toString(Integer.parseInt(iterator1.next, 16) ^
                    Integer.parseInt(iterator2.next, 16), 16)

            if (i.length == 1) result.append("0")
            result.append(i)

        }
          
        while (iterator1.hasNext) result.append(iterator1.next)
    }
        
    result.toString()
}

If we call this method within our main function, we can see the results.

def main(args : Array[String]) {
    val hexString1 = "1274560603"
    val hexString2 = "876429"

    //prints 95107f0603
    println(xorHexStrings(hexString1, hexString2))
}