Breaking Counter Mode Encryption
The subject of today’s post is breaking counter mode encryption, which directly concerns three cryptopals challenges: challenge 19, challenge 20, and challenge 25. (And maybe more … I’m only as far as challenge 25 at this point.)
What is counter mode encryption? Counter mode encryption is a method of encryption in which the content of a message itself is subjected to an XOR binary mathematical operation against an encrypted stream of bytes. It’s called counter mode because the non-encrypted stream of bytes is simply a unique nonce paired up with a counter that is incremented, encrypted, and chained over and over again. Wikipedia has a great summary of what it is.
Look at the image at the top of this post. That’s the algorithm. Can you spot any weaknesses?
In the three previously mentioned challenges, the task is to decrypt a ciphertext without knowing the key. If you look carefully at that image, it should be relatively obvious that there are two weaknesses.
- The block cipher is deterministic. If you can figure out what the nonce and counter is, you can produce the same keystream. That’s usually pretty hard if it’s done right, but it’s still a weakness.
- If you can figure out what the keystream is (regardless of the nonce, counter and key), then you can figure out the plaintext. After all, the plaintext is just an XOR of the ciphertext and the keystream.
In challenges 19 and 20, multiple messages are built using the exact same keystream. This is a no-no. If you encrypt several messages with the same keystream, it becomes relatively simple to figure out the keystream. After all, for a single character in a message, there are only 256 possible bytes against which the message can be XOR’d to produce the cipher text. When you know that the same character different characters (say the first one) in several different messages were built via XOR against the same byte of keystream, then you can find the keystream by trying all 256 bytes and taking what you consider the “best one.”
How to find the best one? In challenge 19, they ask you to primarily use trial and error. Cycle through all 256 a few times for the first few columns, review the results, try some more bytes, and make more substitutions.
In challenge 20, they tell you to do this programmatically. Remember ETAOIN SHRDLU? Frequency analysis on each individual first, second, third, nth character in each of these messages is how I determined which was the best.
public abstract class AbstractFrequencyAnalyzingCTRKeyDeterminer {
//without knowing the key, can we derive the keystream?
// ciphertext block XOR keystream block = plaintext block
// since we have the cipher text block, we just have to figure out what to xor against these texts to make them
// legible
final Chi chi = new Chi();
final XOR xor = new XOR();
public abstract void additionalManualTweaks(final byte[][] ciphertexts, final byte[] keyStream);
public byte[] findTheKeyStream(final byte[][] ciphertexts) {
//inefficient, but find the longest cipher length
int maxLen = Arrays.stream(ciphertexts)
.map(b -> b.length)
.max(Integer::compareTo)
.orElseThrow();
byte[] keyStream = new byte[maxLen];
//get a column of letters in cipher text
// gracefully pass by ciphertexts without letters in the column under examination
for (int l = 0; l < keyStream.length; l++) {
final byte[] temp = new byte[ciphertexts.length];
int count = 0;
for (byte[] ciphertext : ciphertexts) {
if (l < ciphertext.length) {
temp[count] = ciphertext[l];
count++;
}
}
final byte[] byteColumn = new byte[count];
System.arraycopy(temp, 0, byteColumn, 0, count);
keyStream[l] = determineKeyByte(byteColumn);
}
//this function will manually place characters to resolve the full keystream
additionalManualTweaks(ciphertexts, keyStream);
return keyStream;
}
/**
* use chi-squared scores to find the "best" byte for the key
*/
private byte determineKeyByte(final byte[] byteColumn) {
//get the most likely first byte, but print them all
double lowestChiScore = Double.MAX_VALUE;
Integer winner = null;
for (int i = Byte.MIN_VALUE; i <= Byte.MAX_VALUE; i++) {
char[] xordFirstLetters = xor.singleKeyXOR(byteColumn, i);
double localChi = chi.score(xordFirstLetters);
if (localChi < lowestChiScore) {
lowestChiScore = localChi;
winner = i;
}
}
assert winner != null;
return (byte) winner.intValue();
}
}In challenge 25, they give you a new tool. They say, “Hey! You can now edit the original message via an edit function!” They tell you to build the keystream, encrypt the new text against the appropriate keystream bytes, and overwrite the original message. Then, if you decrypt the message, you’ll find your text beginning at the appropriate offset.
public void edit(final byte[] cipherText, final int offset, final String newText) {
// get keystream of length offset plus newText.length rounded up to block size
final LittleEndianNonce nonce = new LittleEndianNonce();
final int blockLength = nonce.get().length;
final int newLength = ((newText.length() + offset) / blockLength) * blockLength + blockLength;
final int numOfBlocks = newLength / blockLength;
final byte[] keystream = new byte[newLength];
for (int block = 0; block < numOfBlocks; block++) {
var encryptedNonce = ecb.AES(nonce.get(), CipherMode.ENCRYPT);
System.arraycopy(encryptedNonce, 0, keystream, block * encryptedNonce.length, encryptedNonce.length);
nonce.increment();
}
//get the portion of the keystream we actually care about
final byte[] ktext = new byte[newText.length()];
System.arraycopy(keystream, offset, ktext, 0, newText.length());
// overwrite the ciphertext
var newTextBytes = newText.getBytes();
var sub = xor.multiByteXOR(newTextBytes, ktext);
System.arraycopy(sub, 0, cipherText, offset, sub.length);
}
But this is a fatal flaw. XOR has a property that dooms whoever thinks this might have been a good idea: XOR-ing a text against all zeros (and I mean binary zero –> [00000000], not character zero, which is actually 48 in binary –> [00110000]) leaves the original text. So, if you edit a ciphertext such that the entire ciphertext is overwritten with zeros, you’ll get the unaltered keystream.
/**
* plaintext can be anything. Find an ascii art and use that if you want.
*/
@Test
void recoverThePlainText() {
final String plaintext = getPlainTextFromFile();
final byte[] cipherText = ctr.encrypt(plaintext);
/*------------------------------------------*/
//we can get the keystream out of the edit function by
// passing in all 0s
final String breakerString = new String(new byte[cipherText.length]);
//copy the cipherText so we retain original
final byte[] keystream = ArrayUtils.clone(cipherText);
//edit the copy with the breaker string to get the keystream
ctr.edit(keystream, 0, breakerString);
//once we have the keystream, we can simply xor it against the cipherText to recover the plaintext
final String broken = new String(xor.multiByteXOR(cipherText, keystream));
assertEquals(plaintext, broken);
}Game over.
Of these three challenges, I probably enjoyed challenge 20 the most. It took me a bit to figure out that I could treat the set of messages they provided as a matrix, where every column in the matrix was XOR’d against the same character. Once I figured that out, it just became a single character XOR and frequency analysis. Challenge 25 was way too obvious, and I didn’t have the patience to sit there poking and plugging at challenge 19. I solved challenge 20 first, and then applied my solution to challenge 19.
Thanks for reading! -LH