August 13, 2019

Cryptopals Challenge #11 - ECB/CBC Detection

In this post we dive into detecting AES-ECB and some statistics behind the detection.

Cryptopals Challenge #11 - ECB/CBC Detection

In this challenge we are asked to write code to encrypt a message using a random key and using AES-ECB half of the time and AES-CBC the other half of the time.  The challenge then asks us to write code to detect which procedure was used to encrypt the data.  To get started, we first write a python script for RNG.

Writing the RNG

First, generating the key with 16 random bytes:

def Generate_Key():
    key = b""

    for i in range(16):
        key += bytes(chr(random.randint(64,126)), 'utf-8')

    return key

Next we write a function which returns a cipher and a boolean.  If the cipher is AES-ECB I chose to return True and if it were CBC I chose to return False.  This is used to generate the cipher and check the answer of the detection oracle.

def Choose_AES(key):
    choice = random.randint(0,1)
    if(choice == 0):
        return, AES.MODE_ECB), True
    if(choice == 1):
        return, AES.MODE_CBC), False

Third, we write a method which pads with 5-10 random bytes before and after the plaintext:

def Append_Bytes(plaintext):
    #Generate how many bytes are going to be appended before/after
    before = random.randint(5,10)
    after = random.randint(5,10)
    #Add the before bytes
    new_bytes = b""
    for i in range(before):
        new_bytes += bytes(chr(random.randint(0,127)), 'utf-8')

    #Add the plaintext
    new_bytes += plaintext

    #Add the after bytes
    for i in range(after):
        new_bytes += bytes(chr(random.randint(0,127)), 'utf-8')

    return new_bytes

Finally, we put this all together and write a function which generates a key and a cipher, encrypts the data, and returns the ciphertext and type of encryption.

Writing the Detection

Storing this in a file called Random_AES allows us to make the code more modular.  Now we have to use the code!

The general skeleton for how we will test them is by running this function:

def Attempt_Detection(trials):
    plaintext = b""
    count = [0,0,0]

    for i in range(int(trials)):
        count[Detect_AES(plaintext)] += 1

    print("SUCCESS: {} \nDETECTED-WRONG: {}\nNOT-DETECTED:{}".format(count[0], count[1], count[2]))
    print("TOTAL FAILURES: {} \nTRIALS:{} \nPERCENT:{}%".format(trials-count[0], trials, count[0]/trials*100))

This function will take an input of trials, run that many detections and keep track of how many were wrong.  If the trial is detected correctly we increment count[0]. Since this function is mainly built to detect ECB, all counts are with reference to correct/incorrect/false-positive detection of ECB.   If the trial detected ECB but the encryption was CBC (false positive), we increment count[1].  Finally, if it incorrectly detects CBC over ECB (not-detected) we increment count[2].

To do all this detection, we simply have to use the code from Challenge #8!

def Detect_AES(plaintext):
    ciphertext, type = Random_Encrypt(plaintext)
    ECB, _ = Is_ECB(ciphertext)

    #If both true or both false
    if((ECB and type) or (not ECB and not type)):
        return 0

    #If ECB is true but type is CBC (false)
    if(ECB and not type):
        return 1

    #If ECB is false but type is true
    if(not ECB and type):
        return 2

Remember, type returns True if Random_Encrypt() uses ECB.  Therefore, if both Is_ECB and Random_Encrypt() are True (Both ECB)  or both are False (Both not ECB), the oracle detected correctly.  If the oracle returns True when Random_Encrypt() returns false, this means the oracle returns a false positive.  Finally, if the oracle returns False when Random_Encrypt() is true, this means it was ECB and the oracle missed it.

Now we can do some testing.  We know that the ECB detection oracle will work if two or more blocks are identically encrypted.  This means that, in order to get 100% correct, we need a plaintext which guarantees two blocks are identical.  

The max padding which can occur is 10 bytes at the beginning of the plaintext.  The min padding is 5 bytes.  Since the blocksize is 16, this means we could feed a plaintext of 6-11 bytes to create a block which includes the padding.

So, we have to add just enough characters that the initial padding will always be placed in a block, then the two following blocks will always be 32 bytes of identical text. I did this by feeding the oracle a string solely comprised of As.  To accomplish the goal I fed 43 As to the oracle.  To understand this, consider the minimum padding of 5.  When the oracle uses a padding of 5, it requires 11 bytes from the plaintext.  As the padding increases, the bytes consumed from the plaintext decreases:

Random Bytes Plaintext Bytes Used Plaintext Bytes Remaining
5 11 32
6 10 33
7 9 34
8 8 35
9 7 36
10 6 37

Thus, we only have to account for the minimum padding since every higher padding will just shift the blocks over.  If the problem had padding which exceeded 16, we would need only to account for a padding of 1.  This is because the padding would create full blocks and it would essentially pad with a range of 1-15.

Predicting Accuracy

Even if you hate statistics and probabilities, I would encourage you to read this section!

By feeding a string of 43 the oracle returns 100% accuracy.  For each character removed from the 43, there is one more padding possibility which will cause faulty detection.  For example, reducing to 41 will make padding of 5 and 6 cause faulty detection.  This means 2 of 6 possibilities will result in non-detection.

Knowing that each decrease from 42 creates one more possibility, we can test how this will affect the probability.  Given that each padding outcome is equally likely, we can expect the effectiveness to decrease by around the same amount.  If each padding were equally represented and the random bytes never collide to make two identical blocks we would expect around a 16.67% failure rate since 1/6 possibilities result in failure.  What is interesting is this does not occur.  Running the detection 1000 times each with 100 trials to find the average failure rate gives the following data:

String Length Failure Rate Gain from Previous
42 8.12% 8.12%
41 16.63% 8.51%
40 24.98% 8.35%
39 33.22% 8.24%
38 41.57% 8.35%
37 50.061% 8.491%

On average we can expect around a 8.34% dip in success for each character removed from the 43 character payload.  Once the payload reaches 37 characters or below, it maintains around a 50% failure rate.  This is because the ECB detection will almost always return false.  Since half of the ciphers are CBC, the detection will trigger 50% of the time as it only checks for not ECB.

This insight of the ECB function being true 50% of the time explains why we do not see a 16.67% (1/6) decrease in probability!  The statement about 1/6 of the chances returning false is actually inaccurate.  Because in each of these cases, there is a 1/2 chance that the cipher encrypts using CBC.  Thus, the probability that the oracle is incorrect only occurs when we hit an unaccounted padding AND the cipher encrypts using ECB.

The probability multiplication rule states that P(A and B) = P(A) P(B | A).  This means the total probability is the probability that A occurs multiplied by the probability that B occurs given A occurs.  In this case, we take A as the occurrence of padding outside the accounted range.  B is the cipher encrypting using ECB.  Since these events are independent, neither choice affects the other, we can simplify the expression.  The probability of B occurring has no connection to the probability of A.  Therefore, P(B|A) is simply equal to P(B).  Thus we find that P(A and B) is equal to P(A)P(B), or 1/6 multiplied by  1/2 which equals 1/12.

Converting 1/12 to a percent returns 8.3%, which is very close to the empirical value!  Thus, we have deduced why and by how much decreasing the string length will affect correctness.

I hope you found this article interesting!  This was the first cryptopals challenge were we took a look at some of the math behind the crypto. By delving into the math we get a better understanding of the behavior of the system.   Next time we will move on to a more simple problem involving decrypting ECB.