Not so scary, XTS-AES

Greetings,% username%!

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


First of all, we define the input data for the work:

1. 256/512 key bits (maybe SHA-256/512 (salt + password) or something like KDF )
2. Address (number) of the sector
3. Sobsno data block length of 128 bits (block size AES)

Simplified, the algorithm is as follows:

1. Breaking down the 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 key of 512 bits, then we saw it into 2x256 and use it in AES-256
2. Convert the sector number into an array of bytes and encrypt it with the key k2 . 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. We like it with tweak value
5. 2.We encrypt / decrypt it with the key k1
6. 3. Again, we already have (races) an encrypted data block with tweak value . We save it, this will be the encrypted block of the sector that we need (for / for).
7. 4. Multiply tweak value by the polynomial α = x ¹²⁸ + x ⁷ + x ² + x + 1

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

2. private const int GF_128_FDBK = 0x87 ;
3. private const int AES_BLK_BYTES = 16 ;
4. ...
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. }

In principle, no crime. This is done in order to tweak value was different for each data block within the sector.
Question to a mathematically savvy audience : Why was it chosen to multiply by a 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 certain analogue of the cyclic shift.

C # working code that even passes standard tests:

2. class XTS
3. {
4. private const int GF_128_FDBK = 0x87 ;
5. private const int AES_BLK_BYTES = 16 ;
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!
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 (for / ra) encrypted data block
15. // convert sector number to byte array
16. Array. Copy ( BitConverter. GetBytes ( sectorNumber ) , T, 8 ) ;
18. // after encryption in T we have tweak value. true means encrypt
19. processAES ( tweakEncryptionKey, T, true ) ;
21. // Process by 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. }
30. // encrypt / decrypt block
31. processAES ( dataEncryptionKey, x, encrypt ) ;
33. // xorim tweak value with processed data block
34. for ( j = 0 ; j < AES_BLK_BYTES ; j ++ )
35. {
36. outData [ i + j ] = ( byte ) ( x [ j ] ^ T [ j ] ) ;
37. }
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. }
49. private static void processAES ( byte [ ] k, byte [ ] T, bool encrypt )
50. {
51. / * AesFastEngine is taken from BouncyCastle. You can replace with standard
52. * implementation, or even use a different algorithm, just consider
53. * block size encryption.
54. * /
55. var engine = new AesFastEngine ( ) ;
56. engine. Init ( encrypt, new KeyParameter ( k ) ) ;
57. engine. ProcessBlock ( T, 0 , T, 0 ) ;
58. }
59. }

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

Homework will implement the processing sector for sizes not multiples of 32.
And I will continue to write encryption for DropBox)