TrueCrypt explained (TrueCrypt 5 update)

TrueCrypt 5 was released a few days ago. Having nothing better to write about, I might as well update the TrueCrypt code to handle TrueCrypt 5 volumes. This is fortunately quite easy to do. We must implement a new cryptographic mode, XTS, and add a new hash algorithm, SHA-512. There are also some minor changes in the code that must be made. Both the LRW mode of operation and the SHA1 hash algorithm are both considered deprecated in TrueCrypt 5, so the code in this post will only handle the new volumes. For information how to read TrueCrypt 4 volumes please read the old post: TrueCrypt Explained. Actually, you should probably read the old post anyway, otherwise this post will be very difficult to understand.

Key strengthening

First of all, let’s add SHA-512. This is already supported out of the box in Python 2.5 thanks to hashlib. If you have Python 2.4 installed, you can use a backported version of the module courtesy of krypto.org. SHA-512 is a stronger hash than SHA1 and more computationally intensive so the PBKDF2 iteration count is 1000 for SHA-512, exactly like Whirlpool. The iteration count for RIPEMD-160 is 2000 as before.

Code: keystrengthening5.py. Requires hashlib, ripemd, whirlpool.

XTS mode

A long-awaited feature of TrueCrypt 5 is system encryption. Encrypting the operating system partition adds an extra layer of security because it gets rid of the problem with traces of secret being data written to the swap file, the registry, temporary files and so on. Writing code to do this doesn’t really have anything to do with cryptography per se, rather it’s a problem of boot loaders, system drivers and so on. But as we all know, cryptography is hard, and there are all sorts of non-obvious problems to think about. One of these problems is related to the LRW-mode of operation, used in TrueCrypt 4.3, combined with system encryption.

There exist a weakness in the LRW mode that makes it unsuitable for system encryption. In this case, “weakness” and “unsuitable” are relative terms. The problem is this: if the LRW key itself is written to the volume, it can be derived. And this can happen if the cryptographic software swaps the key to disk, and the software then encrypts the swap file. This is quite frankly not a problem in practice for TrueCrypt, because even if the LRW key is known, it only makes chosen plaintext attacks easier, and these attacks are very difficult to execute. TrueCrypt also prevents keys from being written to disk: once a cipher is initialized with the key it’s overwritten in memory. For more details, see this post at IEEE.

In either case, TrueCrypt now supports the XTS mode of operation and LRW is deprecated. All new volumes created with TrueCrypt 5 will use the XTS mode. This mode has no known weaknesses that I’m aware of. The XTS mode is very similar to LRW, and is quite easy to implement. Before I describe this mode using common cryptographic notation, I will describe how to use this mode. We will write this function:

def XTSDecrypt(cipher1, cipher2, i, n, block):
    pass

As can be seen, the XTS mode uses two ciphers initialized with different keys. These two ciphers use the same algorithm. Note that unlike TrueCrypt 4.3, the cipher parameters to the mode function are primitive cipher algorithms, not chains/cascades. cipher1 and cipher2 can thus only be one of AES, Twofish or Serpent. How cascades are handled will be described later.

This function takes five arguments. cipher1 is the first cipher initialized with it’s key, cipher2 is the second cipher initialized with another key, block is a 16 byte string of ciphertext, and n and i are two integers which will be described soon. Here’s an example how the code is used:

>>> cipher1 = Rijndael("passwordpassword")
>>> cipher2 = Rijndael("wordpasswordpass")
>>> XTSDecrypt(cipher1, cipher2, 0, 0, "\x00"*16)
'\x0e\xc2\xf1\xb2\x1ce5=\xfd\xe1\xe1jA\xdbb\xc7'

n and i are intimately related. The integer n is the dataunit index. A dataunit is a large block of text, cipher text in this case. The integer i is the index of the block within the dataunit. Let’s say we have 2048 bytes of data to decrypt, and the dataunit size is 512. To decrypt the first 16 bytes in the first dataunit, n is 0 and i is 0. If we want to decrypt the 16 bytes from byte 1024 to 1040, n is 2 and i is 0. To decrypt a complete dataunit with index n, we simply iterate over i, and advance the dataunit 16 bytes each time.

In TrueCrypt 5.0, the dataunit size is always 512. Knowing this, we can write a helper function XTSDecryptMany that takes as argument a dataunit block of 512 bytes and the dataunit index, and decrypts the whole block.

def XTSDecryptMany(cipher1, cipher2, n, blocks):
    length = len(blocks)
    assert length % 16 == 0
    data = ''
    for i in xrange(length / 16):
        data += XTSDecrypt(cipher1, cipher2, i, n, blocks[0:16])
        blocks = blocks[16:]
    return data

That said, we can now describe the XTS mode using common cryptographic notation:

C = E_K1(P xor (E_K2(n) mul (a pow i))) xor (E_K2(n) mul (a pow i))

E_K1 and E_K2 are cipher1 and cipher2 respectively, and P is plaintext block and C is ciphertext block. n is the dataunit index and i is the block index within the dataunit. Note that E_K2 will always encrypt. E_K1 will decrypt for XTSDecrypt, but encrypt for XTSEncrypt (we won’t write this function, but it’s trivial to change the code).

And now for the math part. As with LRW mode, mul is multiplication in GF(2¹²⁸). XTS mode also has another finite field operator: pow is exponentiation in GF(2¹²⁸). This is not really an operator, just repeated multiplication. Finally a is simply the polynomial x, that is the number 0x2 because we represent our polynomials as bits. If this doesn’t make any sense, see the TrueCrypt Explained post.

If you remember the previous discussion, the dataunit size is 512. With a block size of 16, i will never be larger than 31. And fortunately for us, 2ⁱ for 0 ≤ i < 128 in GF(2¹²⁸) is the same as 2ⁱ for 0 ≤ i < 128 in Z. So in Python we can write (a pow i) simply as 2**i or 1<<i.

Having said that, the function XTSDecrypt can be implemented almost exactly as the function LRW. There is however a small difference implementation wise: In TrueCrypts implementation of LRW the integers, when converted to strings, are represented as big endian. TrueCrypts implementation of XTS however, represents integers as little endian. This doesn’t matter at all for security, but can be confusing if you try to reuse code.

Code: xts.py. Requires gf2n.

Putting it all together

With the XTS code working, we must now update the code that decrypts the header and decrypts the rest of the volume. Adding the SHA-512 hash is very easy, we just have to remove the SHA-1 function from the list of HMACs and add SHA-512 instead, and also make sure the iteration count is 1000 instead of 2000 for this hash.

Replacing the LRW mode support with XTS mode support is not very difficult, but there are more changes needed. The most important change is related to cascaded ciphers, such as AES-Twofish. In TrueCrypt 4.3 a cipher cascade was treated as a primitive cipher and the LRW function was therefore only used once per encrypt/decrypt. We can write this as AES-Twofish-LRW.

In TrueCrypt 5.0 however, the ciphers in a chain are treated individually. First the block is encrypted/decrypted with AES-XTS, then with Twofish-XTS, for example. This means we must add some extra code to handle all decryptions. Given a list of 2-tuples (cipher1, cipher2) we can simply do:

def Decrypt(ciphers, i, n, ciphertext):
    assert len(ciphertext) == 16
    for cipher1, cipher2 in reversed(ciphers):
        ciphertext = XTSDecrypt(cipher1, cipher2, i, n, ciphertext)
    return ciphertext

We will also modify XTSDecryptMany so it will call Decrypt instead of XTSDecrypt:

def DecryptMany(ciphers, n, blocks):
    length = len(blocks)
    assert length % 16 == 0
    data = ''
    for i in xrange(length / 16):
        data += Decrypt(ciphers, i, n, blocks[0:16])
        blocks = blocks[16:]
    return data

DecryptMany is the highest-level decryption routine we will use. For TrueCrypt volumes that use cascaded algorithms, the parameter ciphers is a list of length 2 or length 3. For volumes that use a single algorithm, ciphers is a list of length 1.

Now we can modify the class TrueCryptVolume and decrypt TrueCrypt 5 volume headers. For each hash algorithm we generate a 192 byte long key using PBKDF2. In TrueCrypt 4.3 we only had to generate a 128 byte key, but now when we use the XTS mode instead of LRW a longer key is required to handle the (at most) six keys needed, of 32 bytes each.

This 192 byte key is split into six 32 byte keys. That means two keys for every algorithm. For a three-cipher cascade, all six keys will be used. A simple volume that only uses AES, only two keys will be used.

We will now try to decrypt the volume header for each cascade in the list of possible cascades supported. These are as before:

Cascades = [
    [Rijndael],
    [Serpent],
    [Twofish],
    [Twofish, Rijndael],
    [Serpent, Twofish, Rijndael],
    [Rijndael, Serpent],
    [Rijndael, Twofish, Serpent],
    [Serpent, Twofish]
]

Let’s say the correct algorithm is Rijndael. We will create two Rijndael instances cipher1 and cipher2 (remember two instances are needed for XTS) and initialize each of them with the first and the second key from the PBKDF2 output. We can then decrypt the volume header with DecryptMany, like this:

DecryptMany([(cipher1, cipher2)], 0, header)

Should the correct cascade be [Twofish, Rijndael], the volume will be decrypted with:

DecryptMany([(ciphertwo1, ciphertwo2), (cipherrij1, cipherrij2)], 0, header)

Where ciphertwo1, ciphertwo2, cipherrij1 and cipherrij2 are initialized with their corresponding keys from the 192 long key previously generated.

Once the header has been decrypted correctly, all ciphers will be reinitialized with the new keys from the decrypted volume header. We can then use DecryptMany to decrypt the rest of the volume, via TCReadSector. We must modify the TCReadSector function slightly so the dataunit index is correct for hidden volumes. This is documented in the code.

Code: truecrypt5.py. Requires rijndael, serpent, twofish, keystrengthening5, xts.

Conclusion

TrueCrypt 5 is a very well documented project, both the documentation on the website and the source code. The TrueCrypt team deserves credit for that. If you are interested in every detail of TrueCrypt you should read the source code, it’s quite easy to understand. That said, hopefully this minimalist Python implementation and the longer article about TrueCrypt 4.3 will help you better understand the core functionality of the project. If you like TrueCrypt, please donate to the TrueCrypt project, they deserve it.

Finally the obligatory disclaimer: The author of this blog is not affiliated with the TrueCrypt project in any way. The code in this post is MIT License, so you can do pretty much anything you want with it.