IEEE P1619 D1
June 17, 2005
Draft Proposal for LRWAES Mode for Tweakable Tweakable Tweakable Tweakable Narrowblock Encryption
Sponsored by the
Security in Storage Committee
of the
IEEE Computer Society
Copyright © 2005 by the Institute of Electrical and Electronics Engineers, Inc.
Three Park Avenue
New York, New York 100165997, USA
All rights reserved.
This document is an unapproved draft of a proposed IEEE Standard. As such, this document is subject to change. USE AT YOUR OWN RISK! Because this is an unapproved draft, this document must not be utilized for any conformance/compliance purposes. Permission is hereby granted for IEEE Standards Committee participants to reproduce this document for purposes of IEEE standardization activities only. Prior to submitting this document to another standards development organization for standardization activities, permission must first be obtained from the Manager, Standards Licensing and Contracts, IEEE Standards Activities Department. Other entities seeking permission to reproduce this document, in whole or in part, must obtain permission from the Manager, Standards Licensing and Contracts, IEEE Standards Activities Department.
IEEE Standards Activities Department
Standards Licensing and Contracts
445 Hoes Lane, P.O. Box 1331
Piscataway, NJ 088551331, USA
Introduction
The IEEE P1619 family of standards specify an architecture for protection of user data in storage devices. The purpose of P1619 related documents is to describe cryptographic algorithms and methods for encrypting data before it is sent to storage (disk or tape). It also includes modes and formats to be used in data protection to create interoperable solutions.
This standard defines the LRWAES tweakable block cipher and its use of for encryption of storage. LRWAES is a tweakable block cipher that acts on “narrow” blocks of 16 bytes, and it uses as subroutine the AES block cipher (that acts on blocks of 16 bytes). Specifically, LRWAES encrypts and decrypts blocks of 16 bytes, under the control of a secret AES key, a secret 16 byte secondary key, and a 16byte tweak generated from the secondary key and the logical position of the block. LRWAES is a concrete instantiation of the class of tweakable block ciphers described in theorem 2 of reference [LRW02]. When used to encrypt storage data, the tweak value is computed from the logical position of the current narrow block within the scope of the current key.
The motivating application for LRWAES is encryption of storage at the sector level. This cipher addresses threats such as copyandpaste attacks and dictionary attacks, while allowing parallelization of cipher implementations.
At the time this standard was completed, the working group had the following membership:
James P. Hughes, Chair
Member 1
Member 2
…
Member 21
Member 22
…
Member 41
Member 42
…
The following members of the balloting committee voted on this standard. Balloters may have voted for approval, disapproval, or abstention. (To be provided by IEEE editor at time of publication.)
Contents
Introduction ii
1. Overview 5
1.1 Scope and Purpose 5
1.2 Related work 5
2. References 6
3. Definitions 7
3.1 Conformance levels 7
3.2 Glossary of terms 7
3.3 Abbreviations and acronyms 7
3.4 Numerical values 7
3.5 Letter symbols 7
4. The LRWAES transform 9
4.1 Multiplication in the finite field GF(2128) 9
4.1.1 Multiplication Algorithm 1 9
4.1.2 Multiplication Algorithm 2 9
4.2 The LRWAES Encryption Procedure 10
4.2.1 AES Encryption 10
4.2.2 LRWAES Encryption 10
4.2.3 Optimizing Calculation of T 11
4.3 The LRWAES Decryption Procedure 12
4.3.1 AES Decryption 12
4.3.2 LRWAES Decryption 12
5. Using LRWAES for Encryption of Storage 14
5.1 Tweak Position Value 14
5.2 Encoding the tweak values 15
Annex A: Bibliography (informative) 16
Annex B: Test Vectors 17
Tweakable Narrowblock Encryption
1. Overview 1.1 Scope and Purpose
The purpose of this document is to specify the LRWAES transform and its use for encryption of data at rest. The LRWAES transform acts on “narrow” blocks of 16 bytes, under the control of two secret keys (the “keyset”), and the logical position of the data being encrypted within the scope of the keys (the range of data locations being encrypted). It is implemented as a mode of operation for the AES block cipher (that has blocks of size 16 bytes). The security goal of LRWAES states that it should look like a block cipher. Moreover, using the same keyset at different positions should look like using completely independent keysets.
LRWAES is a concrete instantiation of the class of tweakable block ciphers described in theorem 2 of reference [LRW02]. When used to encrypt storage data, the tweak value is computed from the logical position of the current narrow block within the scope of the current key.
The motivating application for LRWAES is encryption of storage at the sector level. This cipher addresses threats such as copyandpaste attacks and dictionary attacks, while allowing parallelization of cipher implementations. In contrast to other ciphers proposed to IEEE P1619, such as EME32AES (see [EME]), LRWAES does not provide “wide” block pseudointegrity of entire sectors. However, LRWAES requires approximately one half the AES encrypt or decrypt operations that EME32AES requires.
The LRWAES mode of operation uses a block cipher with 16byte blocks, and turns it into a tweakable cipher with 16 byte blocks. It is proven in [LRW02] that this mode indeed achieves the stated security goal, assuming that the underlying AES block cipher is secure.
An example application for this transform is encryption of storage at the sector level, where the encrypting device is not aware of highlevel concepts like files and directories. The disk is often partitioned into fixedlength sectors (typically 512 bytes), and the encrypting device is given one sector at a time, in arbitrary order, to encrypt or decrypt. The device needs to operate on sectors as they arrive, independently of the rest. Moreover, the ciphertext must have the same length as its plaintext. On the other hand, it is possible to vary the encryption/decryption process, based on the location on the disk where the ciphertext is stored. The dependency on the location allows that identical plaintext sectors stored at different places on the disk will have unrelated ciphertexts.
This document includes the description of the LRWAES transform itself (in both encryption and decryption modes), as well as how it should be used for encryption of data at rest. The scope is limited to encryption of storage data consisting of an integral number of 16byte narrow blocks beginning at a defined location.
The formal definition of the security goal of a tweakable blockcipher is due to Liskov, Rivest, and Wagner [LRW02], where they also show how (narrowblock) tweakable ciphers can be built from standard block ciphers. An earlier work by Schroeppel suggested the idea of a tweakable blockcipher, by designing a cipher that natively incorporates a tweak [S98].
2. References
The following referenced documents are indispensable for the application of this document. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendments or corrigenda) applies.
ANSI/ISO 98991990, Programming Language—C.^{1}^{,}^{2}
NIST FIPS197, Federal Information Processing Standard (FIPS) for the Advanced Encryption Standard.^{3}
3. Definitions 3.1 Conformance levels
3.1.1 may: A key word indicating flexibility of choice with no implied preference.
3.1.2 shall: A key word indicating a mandatory requirement. Designers are required to implement all such mandatory requirements.
3.1.3 should: A key word indicating flexibility of choice with a strongly preferred alternative. Equivalent to the phrase is recommended.
3.2 Glossary of terms
3.2.1 byte: Eight bits of data, used as a synonym for octet.
3.2.2 block: Sixteen bytes of data.
3.2.3 wide block: 512 bytes of data.
3.2.4 key scope: Two nonnegative integers representing the start and extent of the region to be encrypted by a particular keyset
3.2.5 key set: A pair of secret values, the first of which is a 16, 24, or 32 byte primary key, and the second of which is a 16 byte secondary key.
AES Advanced Encryption Standard (see NIST FIPS197).
IEEE The Institute of Electrical and Electronics Engineers, Inc.
3.4 Numerical values
Decimal and hexadecimal numbers are used within this document. For clarity, decimal numbers are generally used to represent counts and hexadecimal numbers are used to describe bit patterns.
Decimal numbers are represented in their usual 0, 1, 2, ... format. Hexadecimal numbers are represented by a string of one or more hexadecimal (09,AF) digits followed by the subscript 16, except in Ccode contexts, where they are written as 0x123EF2 etc. Thus the decimal number “26” may also be represented also as “1A_{16}”.
3.5 Letter symbols
The following symbols are used in equations and figures:
Bitwise exclusiveOR operation
Multiplication of two polynomials (each of degree less than 128) modulo x^{128}+x^{7}+x^{2}+x+1
← Assignment of a value to a variable
In this section the LRWAES transform is described. That is, the procedures to be followed when encrypting or decrypting a block, given the secret keyset, and the logical position of the data.
4.1 Multiplication in the finite field GF(2^{128})
We now describe a procedure for multiplying a 16byte block a by another 16byte block b in the finite field GF(2^{128}). Both the inputs and the output of this procedure are 16byte blocks. When these blocks are interpreted as binary polynomials of degree 127, the procedure computes z = a b modulo P_{128}, where P_{128} is the polynomial P_{128}(x) = x^{128} + x^{7} + x^{2} + x + 1. Multiplication of two elements in the finite field GF(2^{128}) 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 P_{128}(x) = x^{128}+x^{7}+x^{2}+x+1.
Example: (over GF(2^{7}) with irreducible x^{7}+x+1 for simplicity)
{0,1,0,0,1,1,1} {1,0,0,1,1,1,0}
= (x^{5}+x^{2}+x+1)(x^{6}+x^{3}+x^{2}+x) mod (x^{7}+x+1)
= (x^{11}+x^{5}+x^{3}+x) mod (x^{7}+x+1)
= x^{4}+x^{3}+x
= {0,0,1,1,0,1,0}
Efficient multiplication in GF(2^{128}) may be implemented in numerous ways, depending on whether the multiplier is hardware or software based and which special optimizations may apply.
The following algorithms compute the value of Z = C · Y , where C, Y and Z ε GF(2^{128}).
4.1.1 Multiplication Algorithm 1
Algorithm 1 represents a simple nonoptimized method.
Z ← 0, V ← C
for i = 0 to 127 do
if Y_{i} = 1 then
Z ← Z V
end if
if V_{127} = 0 then
V ← rightshift(V )
else
V ← rightshift(V ) P_{128}
end if
end for
return Z
4.1.2 Multiplication Algorithm 2
A simple optimization of the Algorithm 1 improves performance when multiple inputs Y are multiplied by the same constant C. Note that in the i^{th} step of Algorithm 1 V = C · x^{i} , where x^{i} represents the 16 byte member of GF(2^{128}) with only the i^{th} bit set. A 2,048 byte table of V_{i} (i = 0 to 127) may be stored on the first use of Algorithm 1 and reused thereafter.
Z ← 0,
table of V_{i} (i = 0 to 127) has been precomputed
for i = 0 to 127 do
if Y_{i} = 1 then
Z ← Z V_{i}
end if
end for
return Z
4.2 The LRWAES Encryption Procedure 4.2.1 AES Encryption
Subject to the procedures described in publication (AES), we denote the operation of applying the encryption procedure from by:
C = AESenc(K, P)
where:
C is the block of 16 bytes resulting from the encryption operation (i.e., the ciphertext)
K is an array of 16, 24 or 32 bytes that is used as the encryption key
P is a block of 16 bytes (i.e., the plaintext)
The LRWAES encryption procedure is modeled with this equation:
C = LRWAES(Key1, Key2, P, I)
where:
Key1 is the 16, 24, or 32 byte primary key (i.e., the cipher key)
Key2 is the 16 byte secondary key (i.e., the tweak key)
P is a block of 16 bytes (i.e., the plaintext)
I is a 16 byte position value (see section 5)
C is the block of 16 bytes resulting from the operation (i.e. the ciphertext)
Key_{1} and Key_{2} should be chosen according to the methods described in [R2] and Key_{1} should be independent of Key_{2}.
Figure 1. LRWAES Encryption
The ciphertext shall be computed by the following or an equivalent sequence of steps:

If I > 2^{128}1 or I not positive, exit and output ERROR

T ← Key_{2 } I

PP ← P T

CC ← AESenc(Key_{1} ,PP)

C ← CC T

return C
4.2.3 Optimizing Calculation of T
An efficient implementation may make use of the fact that for consecutive cipher blocks, the value T can be computed by reusing previously known information as indicated below. An implementation may store a precomputed table of values Key_{2} X between LRWAES calls.
One can easily verify that:
T_{i+1} = Key_{2} (i+1) = (Key_{2} i) (Key_{2} X) = T_{i} (Key_{2} X)
for a certain element X of the form ({0,0,…,0,1,1,…,1})
Example: (over GF(2^{7}) for simplicity)
Key_{2} ({1,0,1,1,0,1,1} + 1)
= Key_{2} ({1,0,1,1,1,0,0})
= Key_{2} ({1,0,1,1,0,1,1}{0,0,0,0,1,1,1})
= (Key_{2} (1,0,1,1,0,1,1))(Key_{2} (0,0,0,0,1,1,1))
As a consequence, if one precomputes Key_{2} 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 32 consecutive cipher blocks will only require one field multiplication, 32 field additions and a few integer increments. Thus the incremental cost of generating T over many consecutive cipherblocks is asymptotically the cost of a table lookup and field addition (XOR).
4.3.1 AES Decryption
Subject to the procedures described in publication (AES), we denote the operation of applying the decryption procedure from by:
P = AESdec(K,C)
where:
C is a block of 16 bytes (i.e., the ciphertext)
K is an array of 16, 24 or 32 bytes that is used as the decryption key
P is the block of 16 bytes resulting from the decryption procedure (i.e., the plaintext)
4.3.2 LRWAES Decryption
The LRWAES decryption procedure is modeled with this equation:
P = LRWAES(Key1, Key2, C, I)
where:
Key1 is the 16, 24, or 32 byte primary key (i.e., the cipher key)
Key2 is the 16 byte secondary key (i.e., the tweak key)
P is a block of 16 bytes (i.e., the plaintext)
I is a 16 byte position value (see section 5)
C is the block of 16 bytes resulting from the operation (i.e. the ciphertext)
Figure 2. LRWAES Decryption
The plaintext shall be computed by the following or an equivalent sequence of steps:

If I> 2^{128}1 or I not positive, exit and output ERROR

T←Key_{2 } I

CC←C T

PP←AESdec(Key_{1} ,CC)

P←PP T

return P
5. Using LRWAES for Encryption of Storage
The scope of this document is limited to direct application of the LRWAES transform to encrypt or decrypt data at rest, when this data consists of an integral number of logically contiguous cipher blocks . To use this standard, a key set consisting of a 16byte, 24byte or 32byte AES primary key and a 16byte secondary key shall be associated with an ordered sequence of blocks, numbered consecutively 1 through N, where 1 is the index of the first cipher block for this key set, and N is the index of the last one. The sequence of blocks that are associated with the key set is related to the SCOPE of that key. In order to encrypt or decrypt a block using a key set, the index of the block within the scope of the key must be known.
Key Scope is defined in [BACKUP] as being represented by two integers which represent the “LBA” or Logical Byte Address of the start of the storage to be encrypted in bytes and the number of bytes to be encrypted. To be valid for use with LRWAES, the number of bytes to be encrypted in the key scope must be a multiple of 16, the cipher block size.
In a typical application for storage encryption, the the scope of a key typically includes a range of logically consecutive sectors on the disk, and the Start location of the key scope would be the location of the beginning of the first sector in the range. The alignment of key scopes with integral numbers of consecutive storage sectors is recommended, but not mandated.
An LRWAES secret key pair shall not be associated with more than one scope. The reason is that encrypting more than one block with the same key pair and the same index introduces security vulnerabilities that can potentially be used in an attack on the system.
5.1 Tweak Position Value
The position value I used to compute the tweak value for a given block is constructed to be unique across the key scope.
Each block of 16 bytes is associated with a logical index i which may be viewed as the number of 16 byte blocks from the beginning of the key scope, with the first block being numbered 1.
The integer index i is converted to a 16byte value I according to the encoding described in section 5.2.
In some storage encryption scenarios, SCSI protection information is available for each sector being encrypted. Protection information includes a 2byte Application Tag and a 4byte Reference Tag, one or both of which may be available for use during encryption.
In situations where SCSI protection information is available during the encryption and decryption processes, it may be incorporated into the position value in the following way:

A 20byte value H is computed as the SHA1 digest of the sector data being written.

When the 2byte Application Tag is available, the bytes H[0] and H[1] may be placed in the Application Tag field and in I[0] and I[1] respectively.

When the 4byte Reference Tag is available, the bytes H[2]..H[5] may be placed in the Reference Tag field and in I[2]..I[5].
During the decryption process, an additional verification step may be added in which H is regenerated from the recovered plaintext and compared against the values in the protection information. If the protection information does not match, it indicates the protection information or the ciphertext data has been modified since the encryption operation that generated them.
It is recommended that SCSI protection information be used when available. Use of this information mitigates the risk of ‘blockreplay’ attacks, providing additional assurance of blocklevel integrity.
The value I containing the encoded index i and optionally the Application Tag and Reference Tag values becomes the input to the tweak as described in sections 4.2 and 4.3.
5.2 Encoding the tweak values
A positive integer J (smaller than 2^{128}) is encoded as a 16byte block T using bigendian notation. That is, the integer J is represented in base256 notation, where the most significant byte is stored as the first byte in the block T and the least significant byte is stored as the last byte. Using C notations, we view T as an array of sixteen unsigned char, indexed from 0 (first) to 15 (last), with each byte representing a number between 0 and 255, then the integer J is
J = T[0]256^{15} + T[1]256^{14} + T[2]256^{13} + T[3]256^{12} + T[4]256^{11} + T[5]256^{10} + T[6]256^{9}
+ T[7]256^{8} + T[8]256^{7} + T[9]256^{6} + T[10]256^{5} + T[11]256^{4} + T[12]256^{3} + T[13]256^{2}
+ T[14]256 + T[15]
Annex A: Bibliography (informative)
[BACKUP] Dalit Naor. Key Backup Format for Wideblock Encryption. April 14 2004
[CW79] J. L. Carter and M. Wegman. Universal Classes of hash functions. Journal of Computer and System Sciences, 18:143154, 1979
[EME] Shai Halevi, Draft Proposal for Tweakable WideBlock Encryption, April 2004.
[LRW02] M. Liskov, R. Rivest, and D. Wagner. “Tweakable block ciphers.” In Advances in Cryptology – CRYPTO '02, volume 2442 of Lecture Notes in Computer Science, pages 3146. SpringerVerlag, 2002.
[S98] R. Schroeppel. “The Hasty Pudding cipher.” The first AES conference, NIST, 1998.
Annex B: Test Vectors
Key 1

4562ac25f828176d4c268414b5680185

Key 2

258e2a05e73e9d03ee5a830ccc094c87

I

00000000000000000000000000000001

P

30313233343536373839414243444546

T

258e2a05e73e9d03ee5a830ccc094c87

PP

15bf1836d30bab34d663c24e8f4d09c1

CC

d43c59c8829d425c0707cb9e986a023f

C

f1b273cd65a3df5fe95d489254634eb8

Key 1

59704714f557478cd779e80f54887944

Key 2

0d48f0b7b15a53ea1caa6b29c2cafbaf

I

00000000000000000000000000000002

P

30313233343536373839414243444546

T

1a91e16f62b4a7d43954d6538595f75e

PP

2aa0d35c568191e3016d9711c6d1b218

CC

1a59cac1f70f6a311e1bd13a37f51668

C

00c82bae95bbcde5274f0769b260e136

Key 1

d82a9134b26a565030fe69e2377f9847

Key 2

cdf90b160c648fb6b00d0d1bae85871f

I

00000000000000000000000200000000

P

30313233343536373839414243444546

T

18c91f6d601a1a375d0b0ef73ad574c4

PP

28f82d5e542f2c0065324fb579913182

CC

6efb3eee8d95ebb5a4526cf453db2ac5

C

76322183ed8ff182f9596203690e5e01

Key 1

0f6aeff8d3d2bb152583f73c1f012874cac6bc354d4a6554

Key 2

90ae61cf7baebdccade494c54a29ae70

I

00000000000000000000000000000001

P

30313233343536373839414243444546

T

90ae61cf7baebdccade494c54a29ae70

PP

a09f53fc4f9b8bfb95ddd587096deb36

CC

0ca174e02e0c653c7b9f1b5b620b1231

C

9c0f152f55a2d8f0d67b8f9e2822bc41

Key 1

8ad4ee102fbd81fff886ceac93c5adc6a01907c09df7bbdd

Key 2

5213b2b7f0ff11d8d608d0cd2eb1176f

I

00000000000000000000000200000000

P

30313233343536373839414243444546

T

e1fe23b1ac11a19a5d622e8f6f468d8d

PP

d1cf1182982497ad655b6fcd2c02c8cb

CC

35d949ceb8809cff9502668de8a5b98b

C

d4276a7f14913d65c860480287e33406

Key 1

f8d476ffd646ee6c2384cb1c77d6195dfef1a9f37bbc8d21a79c21f8cb900289

Key 2

a845348ec8c5b5f126f50e76fefd1b1e

I

00000000000000000000000000000001

P

30313233343536373839414243444546

T

a845348ec8c5b5f126f50e76fefd1b1e

PP

987406bdfcf083c61ecc4f34bdb95e58

CC

15438c6f135d3c6fe26deae731e16b35

C

bd06b8e1db98899ec498e491cf1c702b

Key 1

fb7615b23d80891dd470980bc79584c8b2fb64ce6097878d17fce45a49e830b7

Key 2

6e7817e72d5e12d46064047af12f9e0c

I

00000000000000000000000200000000

P

30313233343536373839414243444546

T

5abc25a8c0c808f5e25f3c746ec7286a

PP

6a8d179bf4fd3ec2da667d362d836d2c

CC

012cab696b156faadf36b6e13d0fb48f

C

5b908ec1abdd675f3d698a9553c89ce5

