This is the third blog post in the Cyber Security Challenge Belgium 2015 (CSCBE) solutions series. This time, we’re taking on a very technical challenge: One Way.
Data Extraction
The challenge
The following challenge description was given to the students:
“We want our employees to be able to send us confidential information which only we can decrypt. Since we don’t believe in PKI (we have our reasons!), we made our own crypto system (homemade is always better, right!). To prevent tampering, we took some precautions: A salt is added to each request and the IV is chosen at random for every connection. Take a look at the given clientFramework.py file for more info on how to use our crypto system.“
The accompanying clientFramework.py file contains some helper methods so that the students could focus on the actually encryption logic instead of fighting with python to be able to correctly communicate with the server.
The details
The python file contains some information about the server, from which the following information can be deduced:
- The Initiation Vector (IV) is chosen at random for every session
- The IV is updated after every encryption request according to a known algorithm
- The server encrypts the given plain text as follows: encryption = encrypt(plain text + FLAG, IV)
- The encryption protocol is AES in CBC mode with blocks of 16 characters
- The FLAG consists of 8 lowercase ASCII characters
- The used IV is returned together with the encrypted string
The IV is randomly chosen at the start of the session, but the client can request multiple encryption operations during each session. After each encryption, the IV is updated according to a known function. That means that we can calculate the IV that will be used for the next iteration. This will prove to be very important in what follows.
Encryption 101
Let’s take a look at how the Cipher Block Chaining (CBC) algorithm works, which is what the challenge is using.
The following image shows the working of CBC:
 |
| Image taken from Wikipedia |
The plaintext is split up into blocks of 16 bytes each and each block is encrypted separately. In order to counter certain attacks which are possible against the Electronic CodeBook algorithm (ECB), each plaintext is first XOR’ed with the ciphertext of the previous block. Because the first block doesn’t have a previous block which it can use to XOR with, an IV is used. The IV should always be random and unpredictable.
After the plaintext has been encrypted, the IV has served its purpose and it no longer has to be secret. In this challenge, the IV is returned to the client together with the encrypted text.
Finding the flaw
You may have already noticed a small but very important mismatch between how CBC should be implemented, and how the challenge server implements CBC: the IV should always be random and unpredictable. The server’s IV is completely random and unpredictable, but only for the first encryption request. For every subsequent request, the IV can be calculated from the original IV, which creates a serious security flaw.
Take another look at the CBC diagram. By knowing which IV will be used to XOR with the plaintext, we can prevent the IV from having effect. If we XOR the plaintext with the predicted IV before sending it to the server, the server will apply the XOR again which undoes our original XOR:
plaintext 
IV IV = plaintext (IV IV) = plaintext 0 = plaintext.
IV IV = plaintext (IV IV) = plaintext 0 = plaintext.The second flaw is that the flag is appended to the given plaintext. Since we have full control over the plaintext, we can decide at which position in the plaintext the flag will be, and hence we can control where it will end up in the encrypted string.
Exploiting the flaw
If we have complete control over which plaintext is entered into the first encrypted block, we can get the encrypted value of any given plaintext. This means we can create a rainbow table for every possible plaintext consisting of 16 bytes:
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaab
aaaaaaaaaaaaaaac
//…
zzzzzzzzzzzzzzzx
zzzzzzzzzzzzzzzy
zzzzzzzzzzzzzzzz
Remember that we have to XOR the plaintext string with the predicted IV before sending it to the server.
Before encrypting the plaintext, the server appends the flag to our input. If we only send 15 characters to the server, the server will encrypt aaaaaaaaaaaaaaaX where X is the first character of the flag.
We can now look up the encrypted value of aaaaaaaaaaaaaaaX in our rainbow table. This will match to
aaaaaaaaaaaaaaas and we now know that the first character of the flag is an ‘s’.
To get the second character, we need to create a rainbow table based on the aaaaaaaaaaaaaas prefix (which has 14 a’s). When the table is complete, we can ask the server to encrypt “aaaaaaaaaaaaaas”. The encrypted string will contain the second character of the flag in the last position and we can look it up in our rainbow table. The encrypted string will match to aaaaaaaaaaaaaasa, so ‘a’ is the next character of the flag. We can keep doing this for every character:
aaaaaaaaaaaaaaas
aaaaaaaaaaaaaasa
aaaaaaaaaaaaasal
aaaaaaaaaaaasalt
aaaaaaaaaaasaltm
aaaaaaaaaasaltmi
aaaaaaaaasaltmin
aaaaaaaasaltmine
aaaaaaasaltmine0
aaaaaasaltmine00
aaaaasaltmine000
aaaasaltmine0000
aaasaltmine00000
aasaltmine000000
asaltmine0000000
saltmine00000000
After a few iterations, the padding zeros start showing up in the solution. These extra zeros after the flag are just padding that was added by the server in order to have a complete block to encrypt. When we’ve removed all the prefixed a’s, we end up with the flag, which is saltmine.
Padding attack
The attack we used above is a form of padding oracle attack. This attack is possible because of two distinct vulnerabilities in the server algorithm: We can predict the IV, and we can modify the padding in front of the flag. By combining these two flaws, we are able to get the flag, which would have been impossible without either of them.
In November 2014, the POODLE attack was discovered, which uses a padding oracle attack against SSL3.0.
Statistics
Nine of the participating teams were able to solve this challenge. Eight of these teams were able to secure a place in the CSCBE finals. There were a lot of random guesses for the solution of this challenge. Some even came close (“saltflag” or “salted00”) but luckily, only the teams who actually solved the challenge were able to get the points.
Final thoughts
A strong cryptographic algorithm is only effective when it is used correctly. The challenge demonstrated that small flaws can a have disastrous effects. Although cryptography can be very daunting at first, it certainly pays off to invest some time in to understanding how different algorithms work and how they should be used. Even if you don’t fully understand the internal workings of the AES encryption method, you may still be able to find flaws in the way it is used and thereby be able to break the encryption.