Draft Proposal for lrw-aes mode for Tweakable Tweakable Narrow-block Encryption




Yüklə 101.92 Kb.
tarix20.04.2016
ölçüsü101.92 Kb.


IEEE P1619 D1

June 17, 2005



Draft Proposal for LRW-AES Mode for Tweakable Tweakable Tweakable Tweakable Narrow-block 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 10016-5997, 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 08855-1331, 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 LRW-AES tweakable block cipher and its use of for encryption of storage. LRW-AES 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, LRW-AES encrypts and decrypts blocks of 16 bytes, under the control of a secret AES key, a secret 16 byte secondary key, and a 16-byte tweak generated from the secondary key and the logical position of the block. LRW-AES 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 LRW-AES is encryption of storage at the sector level. This cipher addresses threats such as copy-and-paste 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 LRW-AES 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 LRW-AES Encryption Procedure 10

4.2.1 AES Encryption 10

4.2.2 LRW-AES Encryption 10

4.2.3 Optimizing Calculation of T 11

4.3 The LRW-AES Decryption Procedure 12

4.3.1 AES Decryption 12

4.3.2 LRW-AES Decryption 12

5. Using LRW-AES 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 Narrow-block Encryption

1. Overview

1.1 Scope and Purpose


The purpose of this document is to specify the LRW-AES transform and its use for encryption of data at rest. The LRW-AES 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 LRW-AES states that it should look like a block cipher. Moreover, using the same keyset at different positions should look like using completely independent keysets.

LRW-AES 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 LRW-AES is encryption of storage at the sector level. This cipher addresses threats such as copy-and-paste attacks and dictionary attacks, while allowing parallelization of cipher implementations. In contrast to other ciphers proposed to IEEE P1619, such as EME-32-AES (see [EME]), LRW-AES does not provide “wide” block pseudo-integrity of entire sectors. However, LRW-AES requires approximately one half the AES encrypt or decrypt operations that EME-32-AES requires.

The LRW-AES mode of operation uses a block cipher with 16-byte 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 high-level concepts like files and directories. The disk is often partitioned into fixed-length 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 LRW-AES 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 16-byte narrow blocks beginning at a defined location.


1.2 Related work


The formal definition of the security goal of a tweakable block-cipher is due to Liskov, Rivest, and Wagner [LRW02], where they also show how (narrow-block) tweakable ciphers can be built from standard block ciphers. An earlier work by Schroeppel suggested the idea of a tweakable block-cipher, 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 9899-1990, Programming Language—C.1,2

NIST FIPS-197, 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 non-negative 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.

3.3 Abbreviations and acronyms


AES Advanced Encryption Standard (see NIST FIPS-197).

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 (0-9,A-F) digits followed by the subscript 16, except in C-code contexts, where they are written as 0x123EF2 etc. Thus the decimal number “26” may also be represented also as “1A16”.


3.5 Letter symbols


The following symbols are used in equations and figures:

 Bit-wise exclusive-OR operation

 Multiplication of two polynomials (each of degree less than 128) modulo x128+x7+x2+x+1

← Assignment of a value to a variable


4. The LRW-AES transform


In this section the LRW-AES 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(2128)


We now describe a procedure for multiplying a 16-byte block a by another 16-byte block b in the finite field GF(2128). Both the inputs and the output of this procedure are 16-byte blocks. When these blocks are interpreted as binary polynomials of degree 127, the procedure computes z = a b modulo P128, where P128 is the polynomial P128(x) = x128 + x7 + x2 + x + 1. 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 P128(x) = x128+x7+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)

= x4+x3+x

= {0,0,1,1,0,1,0}

Efficient multiplication in GF(2128) 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(2128).

4.1.1 Multiplication Algorithm 1


Algorithm 1 represents a simple non-optimized method.

Z ← 0, VC

for i = 0 to 127 do

if Yi = 1 then

ZZV

end if

if V127 = 0 then

V ← rightshift(V )

else

V ← rightshift(V )  P128

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 ith step of Algorithm 1 V = C · xi , where xi represents the 16 byte member of GF(2128) with only the ith bit set. A 2,048 byte table of Vi (i = 0 to 127) may be stored on the first use of Algorithm 1 and reused thereafter.
Z ← 0,

table of Vi (i = 0 to 127) has been precomputed


for i = 0 to 127 do

if Yi = 1 then

ZZVi

end if

end for

return Z

4.2 The LRW-AES 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 = AES-enc(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)

4.2.2 LRW-AES Encryption


The LRW-AES encryption procedure is modeled with this equation:

C = LRW-AES(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)

Key1 and Key2 should be chosen according to the methods described in [R2] and Key1 should be independent of Key2.

Figure 1. LRW-AES Encryption

The ciphertext shall be computed by the following or an equivalent sequence of steps:



  1. If I > 2128-1 or I not positive, exit and output ERROR

  2. T Key2 I

  3. PP PT

  4. CC ← AES-enc(Key1 ,PP)

  5. C CCT

  6. 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 Key2 X between LRW-AES calls.

One can easily verify that:



Ti+1 = Key2  (i+1) = (Key2  i) (Key2  X) = Ti  (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 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 The LRW-AES Decryption Procedure

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 = AES-dec(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 LRW-AES Decryption


The LRW-AES decryption procedure is modeled with this equation:

P = LRW-AES(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. LRW-AES Decryption


The plaintext shall be computed by the following or an equivalent sequence of steps:

  1. If I> 2128-1 or I not positive, exit and output ERROR

  2. TKey2 I

  3. CCCT

  4. PP←AES-dec(Key1 ,CC)

  5. PPPT

  6. return P


5. Using LRW-AES for Encryption of Storage


The scope of this document is limited to direct application of the LRW-AES 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 16-byte, 24-byte or 32-byte AES primary key and a 16-byte 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 LRW-AES, 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 LRW-AES 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 16-byte 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 2-byte Application Tag and a 4-byte 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 20-byte value H is computed as the SHA-1 digest of the sector data being written.

  • When the 2-byte 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 4-byte 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 ‘block-replay’ attacks, providing additional assurance of block-level 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 2128) is encoded as a 16-byte block T using big-endian notation. That is, the integer J is represented in base-256 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]25615 + T[1]25614 + T[2]25613 + T[3]25612 + T[4]25611 + T[5]25610 + T[6]2569


+ T[7]2568 + T[8]2567 + T[9]2566 + T[10]2565 + T[11]2564 + T[12]2563 + T[13]2562
+ T[14]256 + T[15]

Annex A: Bibliography (informative)


[BACKUP] Dalit Naor. Key Backup Format for Wide-block Encryption. April 14 2004

[CW79] J. L. Carter and M. Wegman. Universal Classes of hash functions. Journal of Computer and System Sciences, 18:143-154, 1979



[EME] Shai Halevi, Draft Proposal for Tweakable Wide-Block 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 31-46. Springer-Verlag, 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



1 Replaces ANSI X3.159-1989.

2 ISO documents are available from ISO Central Secretariat, 1 rue de Varembé, Case Postale 56, CH-1211, Genève 20, Switzer-land/Suisse; and from the Sales Department, American National Standards Institute, 11 West 42nd Street, 13th Floor, New York, NY 10036-8002, USA

3 FIPS publications are available from the National Technical Information Service (NTIS), 5285 Port Royal Road, Springfield, VA, USA. FIPS-197 is also available on-line from http://csrc.nist.gov/CryptoToolkit/aes/



Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə