Not so scary, XTS-AES

Greetings,% username%!

Today's article is inspired by the thoughts of writing a free analogue of the program for encrypting files in DropBox, namely, an aspect of the file encryption mode sector-by-sector (for the ability to read / write from / to any place)
We will talk about the XTS-AES encryption mode used in all popular disk encryptors (TrueCrypt, DiskCryptor).
It is described in IEEE P1619 ™ / D16 (Standard for Cryptographic Protection of Data on Block-Oriented Storage Devices) and is considered the safest way to store data sector-by-sector.


First of all, we will determine the input data for work:

1. 256/512 key bits (maybe SHA-256/512 (salt + password) or something like KDF )
2. Sector address (number)
3. Own data block of length multiple of 128 bits (block size AES)

Simplified, the algorithm is as follows:

1. Breakdown of a key into two. The first part becomes the data encryption key ( k1 ), the second - the key for generating tweak value ( k2 )
   Thus, if we use a 512-bit key, we saw it on 2x256 and use it in AES-256
2. We convert the sector number into a byte array and encrypt it with the k2 key . This is our tweak value
3. We go through the data array in blocks of 16 bytes in size and for each block:
4. 1.Ksorim it with tweak value
5. 2. We encrypt / decrypt it with the key k1
6. 3. Again Xorim already (races) an encrypted data block with tweak value . We save it, this will be the encrypted block of the sector we need (for / ras)
7. 4. Multiply the tweak value by the polynomial α = x ¹²⁸ + x ⁷ + x ² + x + 1

The most incomprehensible here (for me, in particular) is polynomial multiplication. Algorithmically, this is simply a shift of the entire array by 1 bit + xor in the last step.

1.  
2. private const int GF_128_FDBK = 0x87;
3. private const int AES_BLK_BYTES = 16;
4. ...
5.  
6. // multiply T (weak value) by α
7. Cin = 0; // carry bit
8. for (j = 0; j <AES_BLK_BYTES; j ++)
9. {
10.     Cout = (T [j] >> 7) & 1;
11.     T [j] = (byte) (((T [j] << 1) + Cin) & 0xFF);
12.     Cin = cout;
13. }
14. if (Cout! = 0)
15. {
16.     T [0] ^ = GF_128_FDBK;
17. }
18.  

In principle, no crime. This is done so that the tweak value is different for each data block within the sector.
Question to a mathematically savvy audience : Why was it chosen the multiplication by polynomial in GF (2) modulo x ¹²⁸ + x ⁷ + x ² + x + 1? My (non) knowledge is enough only to assume that cyclic groups are involved here, and all this is a kind of analogue of a cyclic shift.

C # working code that even passes standard tests:

1.  
2. class XTS
3. {
4.     private const int GF_128_FDBK = 0x87;
5.     private const int AES_BLK_BYTES = 16;
6.  
7.     public static byte [] encryptSector (byte [] inData, byte [] dataEncryptionKey, byte [] tweakEncryptionKey, UInt64 sectorNumber, bool encrypt)
8.     {
9.         byte [] outData = new byte [inData.Length]; // there will be a result. The inData size must be a multiple of 32!
10.  
11.         uint i, j; // local counters
12.         var T = new byte [AES_BLK_BYTES]; // tweak value
13.         var x = new byte [AES_BLK_BYTES]; // buffer for (over / dec) the encrypted data block
14.  
15.         // convert sector number to byte array
16.         Array.Copy (BitConverter.GetBytes (sectorNumber), T, 8);
17.  
18.         // after encryption in T, we have tweak value. true means encrypt
19.         processAES (tweakEncryptionKey, T, true);
20.        
21.         // Process AES_BLK_BYTES bytes at a time
22.         for (i = 0; i <inData.Length; i + = AES_BLK_BYTES)
23.         {
24.             // Xorim tweak value with a piece of data
25.             for (j = 0; j <AES_BLK_BYTES; j ++)
26.             {
27.                 x [j] = (byte) (inData [i + j] ^ T [j]);
28.             }
29.  
30.             // encrypt / decrypt the block
31.             processAES (dataEncryptionKey, x, encrypt);
32.  
33.              // Xorim tweak value with the processed data block
34.             for (j = 0; j <AES_BLK_BYTES; j ++)
35.             {
36.                 outData [i + j] = (byte) (x [j] ^ T [j]);
37.             }
38.  
39.             // Multiply tweak value by α
40.             j = AES_BLK_BYTES;
41.             int t = T [AES_BLK_BYTES - 1];
42.             while (--j! = 0)
43.                 T [j] = (byte) ((T [j] << 1) | ((T [j - 1] & 0x80)! = 0? 1: 0));
44.             T [0] = (byte) ((T [0] << 1) ^ ((t & 0x80)! = 0? 0x87: 0x00));
45.         }
46.         return outData;
47.     }
48.  
49.     private static void processAES (byte [] k, byte [] T, bool encrypt)
50.     {
51.         / * AesFastEngine taken from BouncyCastle. You can replace the standard
52.         * implementation, or even use a different algorithm, just consider
53.         * encryption block size.
54.         * /
55.         var engine = new AesFastEngine ();
56.         engine.Init (encrypt, new KeyParameter (k));
57.         engine.ProcessBlock (T, 0, T, 0);
58.     }
59. }
60.  

______________________
Using AES, as you can see, is not necessary. True, nothing is said about this in the standard.

The homework will be to implement sector processing for sizes not multiple of 32.
And I will continue to write the encryption for DropBox)