Wednesday, February 13, 2008

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 = EK1(P xor (EK2(n) mul (a pow i))) xor (EK2(n) mul (a pow i))

EK1 and EK2 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 EK2 will always encrypt. EK1 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(2128). XTS mode also has another finite field operator: pow is exponentiation in GF(2128). 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, 2i for 0 ≤ i < 128 in GF(2128) is the same as 2i 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.

11 Comments:

Blogger Ditator said...

I think it would be cool if you combined this with Python-FUSE to produce a Python implementation of TrueCrypt. You could expose a single file though FUSE - "volume.image" and reading and writing to it would passthough to the volume itself. Right now TrueCrypt's support for Linux isn't very good: you cannot create new volumes as of 5.0a for example, and I have a feeling that Linux isn't one of the Truecrypt teams' priorities. Implementing Python-FUSE would be able to bypass that.

Thursday, February 14, 2008 at 6:16:00 AM GMT+1  
Blogger amr said...

Just a note of thanks for an especially lucid review, one I hope you eventually extend to keyfiles, as the TC take seems a bit ad hoc.

Sunday, February 1, 2009 at 5:55:00 PM GMT+1  
Blogger TUTU said...

結婚相談 東京
お見合いパーティー 名古屋
和光市 一戸建て
我孫子市 一戸建て
足立区 一戸建て
蕨市 一戸建て
不動産 埼玉
海水魚ショップ
目黒区 一戸建て
賃貸オフィス
エアコン 取付
エルメス バッグ
家具
離婚 相談
新興株
J-Payment
カップリングパーティー
任意整理
霊園
アメリカ旅行
オフィスチェア
介護 求人
ダイエット食品
転送電話
映像製作会社
特定調停
ストリーミング
デイトレ銘柄情報
時計修理 ロレックス
ソフトウェア
新聞折込
有料老人ホーム 横浜
恵比寿 賃貸マンション
カイロ 学校
厨房機器 買取
自転車便
川西市賃貸
相続放棄
モバイルサイト 構築
楽器 レンタル
教員
過払い請求
業務用 エアコン
債務整理 名古屋
土呂 不動産

Wednesday, November 25, 2009 at 3:24:00 PM GMT+1  
Blogger TUTU said...

業務用 エアコン
債務整理 名古屋
土呂 不動産
レディースシューズ
自家焙煎
先物 チャート
フェイシャル 麻布十番
福生市 不動産
募金
世田谷 不動産
声楽教室
RMT
分譲マンション 貸す
過払い
フランチャイズ 募集
婚活 東京
フランチャイズ 独立
大井町線 土地
刈払機
飲食業 求人
オーガニックコットン
ダイビング ライセンス
リノベーションマンション
卵巣嚢腫 漢方
グッチ バッグ
居抜き店舗
美容外科
ピーリング治療
簿記3級
朝霞 不動産
食道がん
子宮がん
賃貸事務所
ビジネス英語 メール
toeic対策

Wednesday, November 25, 2009 at 3:24:00 PM GMT+1  
Blogger mafebresv said...

A fast solution to bruteforce truecrypt is http://www.q-protex.com/software/password-recovery/truecrypt-self-bruteforce

Friday, May 7, 2010 at 7:13:00 AM GMT+2  
Blogger nhelder said...

Any plans to post another update for TrueCrypt 6?

Wednesday, June 16, 2010 at 1:44:00 PM GMT+2  
Blogger radella said...

jimmy black shoes
jimmy choo sandals
jimmy choo high
jimmy choo pumps
jimmy choo wedding shoes
buty jimmy choo
jimmy choo skor
jimmy choo booties
shopping jimmy choo
my jimmy choos
jimmy choos heels
DISCOUNT JIMMY CHOO
jimmy choo handbags
JIMMY CHOO
JIMMY CHOO shoes
jimmy choos

Wednesday, July 28, 2010 at 6:08:00 AM GMT+2  
Blogger jimmychooshoes said...

mcqueen shoes
alexander mcqueen heels
Alexander McQueen Store
Jimmy Choo sale
Replica jimmy choo shoes
manolo blahnik online store
manolo shoes
manolo blahnik sale
replica christian louboutin shoes
discount christian louboutin shoes
alexander mcqueen shoes
jimmy choo outlet
jimmy choos
jimmy shoes
Manolo Blahnik Shoes
christian shoes
Jimmy Choo Zero metallic-leather sandals
Christian Louboutin Alta

Perla Strass 100 sandals

Sunday, August 8, 2010 at 10:08:00 AM GMT+2  
Blogger vibrams said...

All the cheap christian louboutin heels for retailing inside our store can be to offer solutions of first-class quality. The christian louboutin evening complete great deal could possibly be the fine and fashionable one.They take place in fascinating design and layout and fashionable appearnce.The colourway also is quite popular. These christian louboutin pumps are luxury and noble. The christian louboutin peep toe show formal, a complete great deal extra show its gorgeous gloss and honour. hold into some mysterious alluring taste! This pairs of christian louboutin 2011 sandals attributes a quite considerable component for women's fabulous whole system figure, show their fabulous figure and fashionable gesture. Louboutin heels is a good choice for you, welcome to our Christian louboutin store!

Tuesday, May 31, 2011 at 3:08:00 PM GMT+2  
Blogger hibeyond said...

black boots

Chocolate boots

sand boots

Chestnut boots

gray boots

pink boots

grey boots

pink boots

Wednesday, August 10, 2011 at 5:48:00 AM GMT+2  
Blogger hibeyond said...

black boots

Chocolate boots

sand boots

Chestnut boots

gray boots

pink boots

grey boots

pink boots

Wednesday, August 10, 2011 at 5:48:00 AM GMT+2  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home