Monday 20 August 2012

Secrets of Reverse Engineering: Flaws in Cryptex

The book Reversing: Secrets of Reverse Engineering has an interesting exercise. In the chapter on Deciphering File Formats the author created a command-line file encryption tool. It's called Cryptex and allows you to encrypt one or more files. Although it's a relatively simple tool it was claimed that:
"If you use long and unpredictable passwords such as j8&1`#:#mAkQ)d* and keep those passwords safe, Cryptex would actually provide a fairly high level of security." --  page 200
It's unsure what the author meant with "fairly high level of security". But when ignoring brute force attacks it's either secure or it's not. And in this case Cryptex is not secure. To be fair it wasn't the point of the author to make a truly secure implementation. The point was to have an interesting file format to analyze. But funny enough Cryptex does precisely what the author warned about:
"Perhaps (and this is more common than you would think) the program you are auditing incorrectly uses a strong industry-standard encryption algorithm in a way that compromises the security of the encrypted files." -- page 202
Indeed more common than you would think.

Let's first give a simplified overview on how Cryptex stores the encrypted files. All files are combined and saved in a single .crx file. The content of the file always starts with "CrYpTeX9" which acts as a signature to verify it's a file created by Cryptex. The remaining content of the .crx archive is divided into sectors. Each sector is 4096 bytes long. The first sector following the "CrYpTeX9" signature contains a list of all the encrypted files in the archive and their location in the .crx file. Finally the .crx archive contains all the encrypted files. Each file starts in a new sector and large files are spread out over multiple sectors.

The problem lies in how Cryptex encrypts its archive. It first derives a key from the password using a SHA1 hash and passes it to the Triple DES block cipher. So far so good. But then each sector is encrypted independently with the same key. Cryptex does this by resetting the state of the Triple DES cipher after encrypting a sector. Among other things this means that if certain sectors repeat we will also notice this repetition in the encrypted archive.

Also troublesome is when a small modification is made to a file which is then encrypted to a new Cryptex archive. To see this I created a file called short1.txt with as content only asterisks:

**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************

And another file called short2.txt with only one modification:

**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
*******0******************************************
**************************************************

Encrypting short1.txt to short1.ctx and short2.txt to short2.txt gives the following:


We can see that both encrypted archives contain identical parts! The identical parts start at the beginning of the sector where files are saved. This allows someone to see where a file has been modified without knowing the password of the archive. Clearly the encrypted archive leaks information.

In the screenshot above we can see that the first 23 * 16 = 368 bytes are identical and the first difference is at 369 bytes from the start of the sector. For our text files each line is saved in 52 bytes (50 characters plus two bytes for the newline and carriage return). This means that the first different character is actually at position 7 * 52 + 7 = 371. Why don't these two positions match? The answer isn't too difficult: it's because 3DES is a block cipher and always encrypts blocks of 8 bytes at once. And the block containing the modified character starts at byte 369.

You might still wonder why the remaining blocks are also different. After all, both files have a sequence of asterisks at the end of the file. The reason is because 3DES is used in Cipher-Block Chaining (CBC) mode [2]. Essentially this means that previous processed blocks influence how the current block is encrypted. So once there is a difference between both files, it will influence all the blocks after it.

To conclude you should never reuse a key. Unfortunately that's exactly what Cryptex is doing: it incorrectly uses a strong industry-standard encryption algorithm in a way that compromises the security of the encrypted files.