Years ago when I set out to learn cryptography for my work as a software developer, I found it interesting that unlike many other aspects of software engineering the “Don’ts” vastly exceed the “Do’s”. To make things worse, the Don’ts of cryptography tend to lead to security vulnerabilities in our software which are in a category of their own when it comes to software bugs. When I learned cryptography for application purposes, I would note the Don’ts and briefly overview the type of attack it would open the software up to if I did not adhere. Recently, I sat down and did a deeper dive through one of those Don’ts:
Cryptographic Wisdom: Don’t use a predictable Initialization Vector (IV) for AES in CBC Mode.
Cryptographers say when operating AES in CBC Mode that we should use an IV that has been generated by a cryptographically secure pseudorandom number generator. I say OK, then we will do that. But what if we didn’t? Oh the hubris…
Question: What is an Initialization Vector (IV) and why do I care?
Cipher Block Chaining (CBC) Mode Encryption looks like this:
The Initialization Vector plays the crucial role that the same plaintext will not equal the same ciphertext when the same Encryption Key is used as long as a unique value is used for the IV. Therefore, encrypting the message “HELLO WORLD” with the same key, but a different IV will result in a different result (ciphertext). By doing Plaintext-Block-1 XOR IV we change the value fed into the encryption algorithm and therefore alter the result of Ciphertext-Block-1 which is then in turn XORed with Plaintext-Block-2 before it is fed into the encryption algorithm and this consequently has cascading effects down the chain.
Question: Aren’t IVs public knowledge? Why is predictability a problem?
The IV for a given ciphertext is typically public knowledge and usually prepended to the ciphertext; however, the IV for a yet to be encrypted plaintext is not public knowledge and if it is or can be predicted then it opens up the implementation to Chosen Plaintext Attacks. You might wonder as to why and it comes down to how CBC mode encryption works.
For example, Alice’s Ciphertext-Block-1 (aC1) is the result of Alice’s Plaintext-Block-1 (aP1) being XORed with the IV generated for the encryption of Alice’s message (aIV).
aC1 = E(aP1 XOR aIV)
If the eavesdropper (Eve) can predict the IV to be used for her encryption (eIV) then she can choose a Plaintext such that Eve’s Plaintext-Block-1 (eP1):
eP1 = aIV XOR eIV XOR PG1
Where PG1 is Plaintext-Guess-Block-1 which is what Eve is guessing for the value of aP1. This allows a dirty trick to be played in the calculation of Eve’s Ciphertext-Block-1 (eC1):
eC1 = E(eP1 XOR eIV) eC1 = E(aIV XOR eIV XOR PG1 XOR eIV) eC1 = E(aIV XOR PG1)
Therefore, if Eve’s Plaintext-Guess-Block-1 (PG1) is a match for the Alice’s Plaintext-Block-1 (aP1) of Alice’s message then eC1 = aC1 and that signals to Eve that she has successfully recovered the contents of aP1. As Eve is able to nullify the effects of the IV generated by the encryption oracle and swap in the IV of her choosing then she can use this method to go block-by-block to figure out the plaintext content of Alice’s messages.
Now you might be thinking that for AES which has a 128-bit block size that Eve will still have her work cut out for herself as there is a huge range of possibilities for plaintext values. You would be right as a guess has a 1 in 2^128 (3.40282366921e38) chance of being right; however, that can be wittled down further as language is not random, not all bytes map to printable characters, context matters, and the protocol might have additional features that can be leveraged.
Theoretical Toy Scenario
I am a big believer in learn-by-example, so let’s go through an example to see how devastating such a choice can be on the security of a system.
- We have a communication protocol that formats authenticated request messages like this:
MSG=[Message Content],TOKEN=[Secret Token]
- Request messages are UTF-8 encoded.
- Authenticated requests are AES-128 encrypted to protect the authentication token as well as the user message.
- The IV is predictable as it is incremented by 1 with each encryption operation.
The attacker (Eve) knows the following:
- There exists a Message Header “MSG=” and Eve either figured this out through an unencrypted channel, experimentation (possible due to IV generation flaw), or via available documentation.
- Eve has figured out the IV generation pattern.
- Eve has deduced the character encoding used is UTF-8 and that a block cipher is being used that has a block size of 128-bit (16 bytes).
Eve does not know the following:
- The encryption key or even the key size (128-bit, 192-bit, 256-bit, etc.).
- What follows the normal message structure of
MSG=[Message Content]
- The encryption algorithm being used although Eve should have a strong suspicion it is AES.
Yet Eve will be able to recover the content beyond the message and unveil the authentication token because the implementer committed the cryptographic sin of using an IV that the attacker could see a pattern in and successfully predict. This toy scenario is inspired by the real life BEAST Attack that security researchers Thai Duong and Juliano Rizzo found back in 2011 against SSL/TLS 1.0.
To optimize the attack, we will leverage the protocol against itself. If we send a message “xxxxxxxxxxx” through the messenger then the resulting message will be:
|MSG=xxxxxxxxxxx,|TOKEN=...
Where the | characters represent the boundary of individual blocks. By choosing a plaintext wherein we know all except 1 character, it makes it trivial to bruteforce that unknown character as we can just loop through printable characters until the Ciphertext Blocks we care about match.
We then repeat this process once we find ‘,’ to be a match and next choose “xxxxxxxxxx” so the resulting message will be:
|MSG=xxxxxxxxxx,T|OKEN=...
Then we loop again until we have a match on ‘T’ and so on.
As our Secret Token is “XYZABC1234567890@#&%” we have to make use of multiple blocks, but the principle is the same. Say we are at the point where we have recovered “,TOKEN=XYZABC1234567890” then the next choice of plaintext to feed into the messenger is “xxxx” so the resulting message will be:
|MSG=xxxx,TOKEN=X|YZABC1234567890@|
Again we will loop through printable characters until we find ‘@’ to be a match and then continue on until the entire plaintext is recovered and the authentication token is revealed.
Coding Time
Our Encryption Oracle is implemented like so:
/// <summary>
/// An encryption oracle the encrypts the provided data using AES-128 in CBC mode
/// with the fatal security flaw that it uses a predictable IV value.
/// </summary>
public static class EncryptionOracle
{
private static ulong Counter { get; set; }
private static byte[] SECRET_KEY = new byte[] {
0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f };
static EncryptionOracle()
{
Counter = 0;
}
public static byte[] AesCbcEncryptPredictableIv(byte[] dataBytes)
{
using (var aes = new AesManaged())
{
aes.IV = WeakGenerateIV();
aes.Key = SECRET_KEY;
using (ICryptoTransform encryptor = aes.CreateEncryptor())
{
using (var outStream = new MemoryStream())
{
using (var cryptoStream = new CryptoStream(outStream, encryptor,
CryptoStreamMode.Write))
{
using (var inStream = new MemoryStream(dataBytes))
{
inStream.CopyTo(cryptoStream);
}
}
// Return IV + Cipher Text
return aes.IV.Concat(outStream.ToArray()).ToArray();
}
}
}
}
private static byte[] WeakGenerateIV()
{
return new byte[] { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }
.Concat(BitConverter.GetBytes(Counter++).Reverse()).ToArray();
}
}
As you can see it uses an internal counter to generate the next IV which is the fatal flaw as it can be predicted. The dummy key {0x00, 0x01, … 0x0e, 0x0f} is just an example of a encryption key and it is obviously not secure, but it is not the focus of this article so just ignore that aspect.
Our Messenger (that Eve is eavesdropping on) is implemented like so:
public static class Messenger
{
// Feel free to tinker with this value and watch how the attack
// will discover it via the ciphertext alone
private const string SecretToken = "XYZABC1234567890@#&%";
public static byte[] MakeEncryptedMessage(string message)
{
string formattedMessage = $"MSG={message},TOKEN={SecretToken}";
byte[] encodedData = Encoding.UTF8.GetBytes(formattedMessage);
return EncryptionOracle.AesCbcEncryptPredictableIv(encodedData);
}
}
The Messenger class is pretty simple and just formats the message, includes the Secret Token, encodes the resulting string, and then passes the encoded data into the Encryption Oracle. I encourage anyone playing with the example code to pick different values for the Secret Token to see them eventually unveiled.
Eve’s Chosen Plaintext Attack Code is:
class MainClass
{
public static void Main(string[] args)
{
int blockSize = 16;
int encryptionIteration = 0;
string recoveredString = string.Empty;
while (true)
{
// Pick message to observe
string message = PickMsgToSend(recoveredString, blockSize);
byte[] encryptedMessageData = Messenger.MakeEncryptedMessage(message);
byte[] initVector = encryptedMessageData.Take(blockSize).ToArray();
byte[] encryptedData = encryptedMessageData.Skip(blockSize).ToArray();
encryptionIteration++;
// Now find out next character
char foundChar = char.MinValue;
bool success = false;
Console.WriteLine($"Bruteforcing next character...");
foreach (char tryChar in GetPrintableCharacterCollection())
{
string msgGuess = PickMsgToGuess(recoveredString, tryChar, blockSize);
byte[] predictedIV = PredictIV(encryptionIteration);
byte[] guessMsgData = GenerateGuessMessageData(msgGuess, initVector,
predictedIV, blockSize);
byte[] encryptedGuessData = EncryptionOracle.AesEncrypt(guessMsgData)
.Skip(blockSize).ToArray();
encryptionIteration++;
// Check to see if the encrypted data for the blocks we are concerned
// with match up - If they do then we have a match and have unveiled
// the next plaintext character - Otherwise we continue through the
// printable characters.
if (encryptedData.Take(msgGuess.Length)
.SequenceEqual(encryptedGuessData.Take(msgGuess.Length)))
{
foundChar = tryChar;
success = true;
break;
}
}
// If we found another character, then append it - otherwise we are done.
if (success)
{
recoveredString += foundChar;
Console.WriteLine($"Recovered String Update: {recoveredString}");
}
else
{
break;
}
}
Console.WriteLine($"Recovered String Result: {recoveredString}");
}
private static byte[] GenerateGuessMessageData(string messageGuess,
byte[] messageIV, byte[] nextIV, int blockSize)
{
byte[] messageGuessData = Encoding.UTF8.GetBytes(messageGuess);
// We need our first plaintext block to be
// IV_known XOR IV_predicted XOR Message_Block_1
byte[] xorData1 = XorArray(messageIV, nextIV);
byte[] msgBlock1 = messageGuessData.Take(blockSize).ToArray();
byte[] firstBlockData = XorArray(xorData1, msgBlock1);
// swap the first plaintext block with the modified one above
return firstBlockData.Concat(messageGuessData.Skip(blockSize)).ToArray();
}
private static string PickMsgToSend(string recoveredString, int blockSize)
{
const string header = "MSG=";
int knownCharCount = header.Length + recoveredString.Length;
int blocksFilled = knownCharCount / blockSize;
// We need to pad the plaintext such that
// [MSG=][x-pad] + [Recovered Text][Unknown Character]
// will place the Unknown Character at the edge of a ciphertext block
int xpadLen = blocksFilled * blockSize + blockSize - header.Length
- recoveredString.Length - 1;
return new string('x', xpadLen);
}
private static string PickMsgToGuess(string recoveredString, char guessChar,
int blockSize)
{
const string header = "MSG=";
int knownCharCount = header.Length + recoveredString.Length;
int blocksFilled = knownCharCount / blockSize;
// We need to make the plaintext guess such that
// [MSG=][x-pad][Recovered Text][Bruteforce Character]
// where Bruteforce Character happens at the edge of a block
// and this allows us to test the guess one at a time
int xPadLen = blocksFilled * blockSize + blockSize - header.Length
- recoveredString.Length - 1;
return header + new string('x', xPadLen) + recoveredString + guessChar;
}
// The flaw here is that the attacker can predict the next IV to be
// used by the encryption oracle
private static byte[] PredictIV(long iteration)
{
return new byte[] { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }
.Concat(BitConverter.GetBytes(iteration).Reverse()).ToArray();
}
private static byte[] XorArray(byte[] array1, byte[] array2)
{
if (array1.Length == array2.Length)
{
byte[] xorArray = new byte[array1.Length];
for (int i = 0; i < array1.Length; i++)
{
xorArray[i] = (byte)(array1[i] ^ array2[i]);
}
return xorArray;
}
throw new ArgumentException();
}
private static char[] GetPrintableCharacterCollection()
{
return Enumerable.Range(0, char.MaxValue + 1)
.Select(i => (char)i)
.Where(c => !char.IsControl(c))
.ToArray();
}
}
This will allow Eve to send messages and capture their encrypted output. She can then methodically figure out the next plaintext character in the captured encrypted data by passing her plaintext guesses into the Encryption Oracle to see if she has a match. Once she has a match then she can move on to figuring out the next character.
The output of the attacking code looks like this:
The key takeaway here is that your Initialization Vector should be randomly generated via a cryptographically secure random number generator. If it is predictable or, worse yet, static, then you possibly open up the system to Chosen Plaintext Attacks as in that case you are misapplying cryptography. Thanks for reading as always.