IEEE Tweak
Synopsis: / This document specifies a tweakable block cipher to use in storage security.Author(s): Cyril Guyot
Revision Level: 1.3
Revision Date: December 3, 2003
Introduction
This document specifies an IEEE P1619 r=1 tweak algorithm, a tweakable block cipher created from a symmetric block cipher of block size 128 bits.
Tweakable block ciphers are used in cryptography for their resistance against attacks which permute blocks - cut and paste attacks[Bib] - , as well as against dictionary attacks[Bib].
Tweaks work by giving rise to apparently independent families of standard block cipher encryption operators whenever a new tweak is calculated.
Because of the possibility of cut and paste attacks with traditional storage encryption methods, this document focuses on the application of such a tweakable block cipher to storage security.
This document includes the following sections:
- Definitions, acronyms and symbols.
- Notation and conventions: ordering of bits, bytes and words
- Mathematical properties
- Specification
- Implementation issues
- Test vectors
Definitions
AES Advanced Encryption Standard
Bit A binary digit having a value of 0 or 1
Block A sequence of bits that are processed simultaneously by the symmetric cipher
Byte A group of eight bits
Cipher A series of transformation that converts plaintext to ciphertext using a cipher key
Cipher Key S secret, cryptographic key that is used by the symmetric cipher
Ciphertext The data output from the cipher
GF(2128) The finite field of characteristic 2 containing 2128 elements
FIPS Federal Information Processing Standards
Plaintext The data input to the cipher
Word A group of 32 bits
XOR Exclusive-OR operation
Å Exclusive-OR operation
Ä Multiplication of two polynomials (each of degree less than 128) modulo x128+x7+x2+x+1
Notations and Conventions
The input and output for the Tweaked cipher consist of sequences of 128 bits. These sequences will sometimes be referred to as blocks and the number of bits they contain will be referred to as their length.
Bits
Bits within such sequences are numbered starting at zero and ending at one less than the sequence length. The number i attached to a bit is known as its index and will be in the range 0<=i<128.
Bytes
The basic processing unit for a tweakable cipher is a byte; a sequence of eight bits treated as a single entity. The input, output, Cipher key and Tweak key bit sequences described are processed as arrays of bytes that are formed by dividing these sequences into groups of eight contiguous bits.
Any byte value in the tweak algorithm will be presented as the concatenation of its individual bit values between braces in the order {b7, b6, b5, b4, b3, b2, b1, b0}. These bytes are interpreted as finite field elements using a polynomial representation:
b7x7 + b6x6 + b5x5+ b4x4 + b3x3 + b2x2 + b1x + b0.
Binary representation / Hexadecimal representation{0000} / {0}
{0001} / {1}
{0010} / {2}
{0011} / {3}
{0100} / {4}
{0101} / {5}
{0110} / {6}
{0111} / {7}
{1000} / {8}
{1001} / {9}
{1010} / {a}
{1011} / {b}
{1100} / {c}
{1101} / {d}
{1110} / {e}
{1111} / {f}
Hence the element {01100011} will be represented as {63}, where the character denoting the four-bit group containing the higher numbered bits is again to the left.
Arrays of bytes
Arrays of bytes will be represented in the following form a0a1a2a3…a15
The bytes and the bit ordering within bytes are derived from the 128-bit input sequence
input0input1input2…input126input127 as follows:
a0=input0,input1,…,input7
a1=input8,input9,…,input15
…
a15=input120,input121,…,input127
Indexing
Indexing always starts at zero.
The first sector on the drive has index N=0 and the first block within any sector has index i=0
Note
The described tweakable mode was designed with the AES cipher in mind. As a consequence, all the conventions described in this document are similar to the ones described in the FIPS 197 AES standard.
Mathematical preliminaries
All bytes in the tweaked algorithm are interpreted as finite field elements using the notation introduced in the previous section. Finite field elements will be added and multiplied with the following operations:
Addition
The addition of two elements in the finite field GF(2128) is computed by XORing the two elements together.
Example: (over GF(27) for simplicity)
{0,1,0,0,1,1,1} Å {1,0,0,1,1,1,0} = {1,1,0,1,0,0,1}
Multiplication
Multiplication of two elements in the finite field GF(2128) is computed by computing the polynomial multiplication and taking the remainder of the Euclidean division by the chosen irreducible. In our case, the irreducible is x128+x7+x4+x2+x+1.
Example: (over GF(27) with irreducible x7+x+1 for simplicity)
{0,1,0,0,1,1,1} Ä {1,0,0,1,1,1,0}
= (x5+x2+x+1)*(x6+x3+x2+x) mod (x7+x+1)
= (x11+x5+x3+x) mod (x7+x+1)
= x6+x4+x3+x
= {1,0,1,1,0,1,0}
Specification
Tweakable ciphers have been described in [LRW] and two major types of tweaks have been proven to have the required properties. The tweakable block cipher this document specifies is of the Tweak-Encrypt-Tweak type and is described in Theorem 2 of the previously mentioned paper.
The first step in this algorithm is to independently choose two keys Key1 and Key2 where Key1 is the AES cipher key and Key2 is the tweak key.
Key1 needs to be chosen with the usual care associated with AES key generation. As per the FIPS 197 standard, Key1 can be any of 128, 192 or 256 bits long.
Key2 is a randomly chosen nonzero element of GF(2128) and has to be protected throughout the life of the data to be encrypted.
Once those two secrets have been agreed upon, it is possible to compute the ciphertext corresponding to a plaintext block for the corresponding disk location.
The ciphertext at a disk sector n and cipher block i within this sector is computed with the following method:
Ciphertext[n,i]
= Encrypt(Key1, Plaintext[n,i] Å Tweak[n,i,Key2]) Å Tweak[n,i,Key2]
The computation of the tweak value itself is done along the following steps:
Tweak(n,i,K) = K Ä F(n,i)
This multiplication is the previously described GF(2128) multiplication. The function F is defined as:
F:=(n,i)->(NB*(n+1)+i)
Here, NB is the size of the disk sector in cipher blocks. In usual storage applications, the sector length is 512 bits; hence this number will usually be 32.
Note that the addition and the multiplication used in the computation of F are the usual integer addition and integer multiplication.
Also, note the necessary (n+1) rather than n. This ensures that the tweak value is always different from 0.
With such conditions, it has been proven in [CW] that such a h:=K->Tweak(n,I,K) satisfies the properties required by the function h of Theorem 2.
Pseudocode for the algorithm
Parameters:
NB: Number of Cipher Blocks per sector
Input:
PT: Plaintext of length 128 bits
Key1: Cipher Key of length 128, 192 or 256 bits
Key2: Tweak Key of length 128 bits
N: Disk Sector Number
I: Cipher Block Number
Output:
CT: Ciphertext
The ciphertext shall be computed by the following or an equivalent sequence of steps:
1. Compute A=F(N,I).
2. If A>(2128-1) exit and output ERROR.
3. Compute Tweak=Key2 Ä A.
4. Compute B=Plaintext Å Tweak.
5. Encrypt B into C using the chosen symmetric cipher with the cipher key Key1.
6. Compute CT=C Å Tweak and output CT.
Implementation issues
An efficient implementation will make use of the fact that for consecutive cipher blocks, the tweak can be computed by reusing previously known information.
One can easily verify that:
Tweak(n,i+1) = Key2 Ä F(n,i+1) = (Key2 Ä F(n,i))Å (Key2 Ä X) for a certain element X of the form ({0,0,…,0,1,1,…,1})
Example: (over GF(27) for simplicity)
Key2 Ä ({1,0,1,1,0,1,1} + 1)
= Key2 Ä ({1,0,1,1,1,0,0})
= Key2 Ä ({1,0,1,1,0,1,1}Å{0,0,0,0,1,1,1})
= (Key2 Ä (1,0,1,1,0,1,1))Å(Key2 Ä (0,0,0,0,1,1,1))
As a consequence, if one precomputes Key2 Ä X for all the possible elements X of the form ({0,0,…,0,1,1,…,1}) during the block cipher key setup for example, computation of a 512 byte sector (32 cipher blocks) will only require one field multiplication, 32 field additions and a few integer increments.
Test vectors
Those test vectors apply to 512 bytes sectors.
Plaintext / 000102030405060708090a0b0c0d0e0fCipher Key / 00010001000100010001000100010001
Tweak Key / 01020102010201020102010201020102
Sector Number / 2003
Cipher Block Number / 11
Ciphertext / 6e0b458e91162e5cf23c3ca5dd3233a4
Plaintext / 000102030405060708090a0b0c0d0e0f
Cipher Key / 01020102010201020102010201020102
Tweak Key / 00010001000100010001000100010001
Sector Number / 123456789
Cipher Block Number / 0
Ciphertext / 7537c19447b16f5fba982b7015a1937e
Bibliography
[BCKM] I. F. Blake, C. Guyot, C. Kent and V. K. Murty. Encryption of Stored Data in Networks: Analysis of a Tweaked Block Cipher.
[CW] J. L. Carter and M. Wegman. Universal Classes of hash functions. Ournal of Computer and System Sciences, 18:143-154, 1979
[LRW] M. Liskov, R. Rivest and D. Wagner. Tweakable Block Ciphers. In Advances in Cryptology – CRYPTO ‘02. Lecture Notes in Computer Science. Springer-Verlag. 2002. www.cs.berkeley.edu/~daw/.