AES 128-BIT ENCRYPTION.pdf PDF

Preview

Summary

Chapter 1 INTRODUCTION GCM-AES (Galois Counter Mode Advanced Encryption Standard) is an authenticated encryption mode designed by David McGrew and John Viega. The details of this mode of operation can be found in [2]. This document aims to explore hardware implementation of GCM-AES mode of operation...

Description

Chapter 1 INTRODUCTION GCM-AES (Galois Counter Mode – Advanced Encryption Standard) is an authenticated encryption mode designed by David McGrew and John Viega. The details of this mode of operation can be found in [2]. This document aims to explore hardware implementation of GCM-AES mode of operation specifically targeting FPGA [1] (Field Programmable Gate Arrays). The aim of such an implementation is to benchmark GCM-AES on FPGA in terms of area, power and speed. 1.1 Definitions : 1.1.1 AES In today’s digital world, encryption is emerging as a disintegrable part of all communication networks and information processing systems, for protecting both stored and in transit data. Encryption is the transformation of plain data (known as plaintext) into unintelligible data (known as ciphertext) through an algorithm referred to as cipher. There are numerous encryption algorithms that are now commonly used in computation, but the U.S. government has adopted the Advanced Encryption Standard (AES) to be used by Federal departments and agencies for protecting sensitive information. The National Institute of Standards and Technology (NIST) has published the specifications of this encryption standard in the Federal Information Processing Standards (FIPS) Publication 197. [1] Any conventional symmetric cipher, such as AES, requires a single key for both encryption and decryption, which is independent of the plaintext and the cipher itself. It should be impractical to retrieve the plaintext solely based on the ciphertext and the encryption algorithm, without knowing the encryption key. Thus, the secrecy of the encryption key is of high importance in symmetric ciphers such as AES. Software implementation of encryption algorithms does not provide ultimate secrecy of the key since the operating system, on which the encryption software runs, is always vulnerable to attacks. There are other important drawbacks in software implementation of any encryption algorithm, including lack of CPU instructions operating on very large operands, word size 1

mismatch on different operating systems and less parallelism in software. In addition, software implementation does not fulfill the required speed for time critical encryption applications. Thus, hardware implementation of encryption algorithms is an important alternative, since it provides ultimate secrecy of the encryption key, faster speed and more efficiency through higher levels of parallelism. Different versions of AES algorithm exist today (AES128, AES196, and AES256) depending on the size of the encryption key. In this project, a hardware model for implementing the AES128 algorithm was developed using the Verilog hardware description language. A unique feature of the design proposed in this project is that the round keys, which are consumed during different iterations of encryption, are generated in parallel with the encryption process. The hardware model was then completely verified using a testbench, which took advantage of the Verilog’s object oriented programming (OOP) feature, by constructing random test objects and providing them to the model. The validation process continued until the model was verified for a certain Functional Coverage. Then, the verified model was synthesized using the Synopsis Design-Compiler tool to get an estimate of the number of gates, area and timing of the hardware model. 1.1.2 GCM Galois/Counter Mode (GCM) for authenticated encryption with associated data. GCM is constructed from an approved symmetric key block cipher with a block size of 128 bits, such as the Advanced Encryption Standard (AES) algorithm that is specified in Federal Information Processing Standard (FIPS) Pub. 197 [2]. Thus, GCM is a mode of operation of the AES algorithm. GCM provides assurance of the confidentiality of data using a variation of the Counter mode of operation for encryption. GCM provides assurance of the authenticity of the confidential data (up to about 64 gigabytes per invocation) using a universal hash function that is defined over a NIST Special Publication 800-38D binary Galois (i.e., finite) field. GCM can also provide authentication assurance for additional data (of practically unlimited length per invocation) that is not encrypted. If the GCM input is restricted to data that is not to be encrypted, the resulting specialization of GCM, called GMAC, is simply an authentication mode on the input data. In the rest of this document, statements about GCM also apply to GMAC. GCM provides stronger authentication assurance than a (non-cryptographic) checksum or error detecting code; in particular, GCM can detect both

2

1) accidental modifications of the data and 2) intentional, unauthorized modifications. The two functions of GCM are called authenticated encryption and authenticated decryption. Each of these functions is relatively efficient and parallelizable; consequently, highthroughput implementations are possible in both hardware and software. GCM has several other useful characteristics, including the following: • The GCM functions are “online” in the sense that the lengths of the confidential data and the additional, non-confidential data are not required in advance; instead, the lengths can be calculated as the data arrives and is processed. • The GCM functions require only the forward direction of the underlying block cipher (i.e., the inverse direction is not required). • The authenticity of the protected data can be verified independently from the recovery of the confidential data from its encrypted form. • If the unique initialization string is predictable, and the length of the confidential data is known, then the block cipher invocations within the GCM encryption mechanism can be pre-computed. • If some or all of the additional, non-confidential data is fixed, then the corresponding elements of the GCM authentication mechanism can be pre-computed. 1.2 Purpose In today's world most of the communication is done using electronic media. Data Security play a vital role in such communication. hence, there is a need to protect data from malicious attacks. This can be achieved by Cryptography.The ideal encryption algorithm would provide unbreakable security with no significant impact on the normal flow of data. The earlier encryption algorithm is Data Encryption (DES) which has several loopholes such as small key size and sensible to brute force attack etc. For twenty years the Data Encryption Standard (DES) was the state of the art, but it became unsafe once it was determined how to identify its secret key and decipher the encrypted data. These loopholes overcome by a new algorithm called as Advanced Encryption Standard Algorithm. In September 1997, the National Institute of Standards and Technology (NIST) issued a request for a new Advanced Encryption Standard (AES) to replace DES. Several algorithms were proposed and considered, and in October 2000 the Rijndael block cipher algorithm was chosen as the new AES.

3

1.3 Motivation : The Advanced Encrption Standard, in the following referenced as AES, is the winner of the contest, held in 1997 by the US Government, after the Data Encryption Standard (DES) was found too weak. Fifteen candidates were accepted in 1998 and based on public comments the pool was reduced to five finalistsin 1999. In October 2000, one of these five algorithns was selected as the forthcoming standard: a slighthly modified version of the Rijindael. The Rijndael, whose name is based on the names of its two Belgian inventors, Joan Diemen and Vincent Rijmenm, is a Block cipher, whcih means that it works on fixed-length group of bits, which are called Blocks. It takes an input block of a certain size, usually 128, and produces a corresponding output block of the same size. The transformation requires a second input, which is the secret key. It is important to know that the secret key can be of any size (depending on the cipher used) and the AES uses three different key sizes: 128, 192 and 256 bits. 1.4 Organization of report : Chapter 2 covers an overview of the AES encryption algorithm and different version of it. In this chapter, different types of transformations and steps that are involved in the AES encryption process are introduced. Chapter 3 discusses the design and modeling of the implementation of the AES128 encryption algorithm by explaining the modules used in the design hierarchy, their interconnections and state diagrams. Chapter 4 discusses the elements of GCM and associated notation and requirements. Chapter 5

This section presents the mathematical components that appear in the

specifications of the authenticated encryption and authenticated decryption functions.

4

Chapter 2 ADVANCED ENCRYPTION STANDARD (AES) 2.1 Overview This chapter is a summary of the Federal Information Processing Standards (FIPS) Pub-

lication 197 [1], issued by the National Institute of Standards and Technology (NIST) which specifies the Advanced Encryption Standard. Throughout the remainder of this chapter, the mathematical properties of the Advanced Encryption Standard (AES) are introduced using the information obtained from the AES specification. The AES is a subset of a much larger encryption algorithm known as Rijndael, which was one of many proposals to the NIST competing for becoming a standard encryption algorithm. On October of 2000, the NIST announced the

Rijndael algorithm as the winner due to the best overall score in security, performance, efficiency, implementation capability and simplicity. [2] The AES algorithm is a symmetric cipher. In symmetric ciphers, a single secret key is used for both the encryption and decryption, whereas in asymmetric ciphers, there are two sets of keys known as private and public keys. The plaintext is encrypted using the public key and can only be decrypted using the private key. In addition, the AES algorithm is a block cipher as it operates on fixed-length roups of bits (blocks), whereas in stream ciphers, the plaintext bits are encrypted one at a time, and the set of transformations applied to successive bits may vary during the encryption process. The AES algorithm operates on blocks of 128 bits, by using cipher keys with lengths of 128, 192 or 256 bits for the encryption process. Although the original Rijndael encryption algorithm was capable of processing different blocks sizes as well as using several other cipher key lengths, but the NIST did not adopt these additional features in the AES. [1]

2.2 Inputs, Outputs and the State The plaintext input and ciphertext output for the AES algorithms are blocks of 128 bits. The cipher key input is a sequence of 128, 192 or 256 bits. In other words the length of the cipher key, Nk, is either 4, 6 or 8 words which represent the number of columns in the cipher key. The AES algorithm is categorized into three versions based on the cipher key length. The number of rounds of encryption for each AES version depends on the cipher key size.

5

In the AES algorithm, the number of rounds is represented by Nr, where Nr = 10 when

Nk = 4, Nr = 12 when Nk = 6, and Nr = 14 when Nk = 8. The following table illustrated the variations of the AES algorithm. For the AES algorithm the block size (Nb), which represents the number of columns comprising the State is Nb = 4.

AES Version

Key Length

Block Size

Number

(Nk words)

(Nb words)

Rounds

of

(Nr rounds) AES128

4

4

AES192

6

4

12

AES256

8

4

14

10

Table 1 – AES Variations The basic processing unit for the AES algorithm is a byte. As a result, the plaintext, ciphertext and the cipher key are arranged and processed as arrays of bytes. For an input, an output or a cipher key denoted by a, the bytes in the resulting array are referenced as an , where n is in one of the following ranges: Block length = 128 bits, 0 > 1 = 0011011.

27

Given a positive integer s and a non-negative integer x that is less than 2s, the integer-to-string function, denoted [x]s, is the binary representation of x as a string of bit length s with the least significant bit on the right. For example, for the (base 10) integer 39, the binary representation (base 2) is 100111, so [39] 8 = 00100111. Given a (non-empty) bit string X, the string-to-integer function, denoted int(X), is the integer x such that [x]len(X) = X. In other words, int(X) is the non-negative integer less than 2len(X) hose binary representation is X. For example, int(00011010) = 26.

5.2 Multiplication Operation on Blocks Let R be the bit string 11100001 || 0120. Given two blocks X and Y, Algorithm 1 below computes a “product” block, denoted X •Y: Algorithm 1: X •Y

Input: blocks X, Y.

Output: block X •Y.

Steps: 1. Let x0x1...x127 denote the sequence of bits in X. 2. Let Z0 = 0128 and V0 = Y. 3. For i = 0 to 127, calculate blocks Zi+1 and Vi+1 as follows:

4. Return Z128. The • operation on (pairs of) the 2128 possible blocks corresponds to the multiplication operation for the binary Galois (finite) field of 2128 elements. The fixed block, R, determines a representation of this field as the modular multiplication of binary polynomials of degree less than 128. The convention for interpreting strings as polynomials is “little endian”: i.e., if u is the variable of the polynomial, then the block x0x1...x127 corresponds to the polynomial x0 + x1 u +

x2 u2 + ... + x127 u127. The XOR operation is used to add coefficients of “like” terms during the 28

multiplication. The reduction modulus is the polynomial of degree 128 that corresponds to R || 1. Ref. [6] discusses this field in detail. For a positive integer i, the ith power of a block X with this multiplication operation is denotedXi. For example, H2=H•H, H3=H•H•H, etc.

5.3 GHASH Function Algorithm 2: GHASHH (X)

Prerequisites: block H, the hash subkey.

Input: bit string X such that len(X) = 128m for some positive integer m.

Output: block GHASHH (X).

Steps: 1. Let X1, X 2, ... , X m-1, X m denote the unique sequence of blocks such that X = X 1 || X 2 || ... || X m-1 || X m. 2. Let Y0 be the “zero block,” 0128. 3. For i = 1, ..., m, let Yi = (Yi-1 ⊕ Xi) • H. 4. Return Ym. In effect, the GHASH function calculates X1•Hm ⊕ X2•Hm-1 ⊕ ... ⊕ Xm-1•H2 ⊕ Xm•H. Ref. [6] describes methods for optimizing implementations of GHASH in both hardware and software. The GHASH function is illustrated in Figure 1 below, without the zero block, Y0, whose exclusive-OR with X1 does not change X1.

29

Figure 5.1: GHASHH (X1 || X2 || ... || Xm) = Ym.

5.4 GCTR Function Algorithm 3 below specifies the GCTR function. The suggested notation does not indicate the choice of the underlying block cipher. Algorithm 3: GCTRK (ICB, X)

Prerequisites: approved block cipher CIPH with a 128-bit block size; key K.

Input: initial counter block ICB; bit string X, of arbitrary length.

Output: bit string Y of bit length len(X).

30

STEPS

In Steps 1 and 2, the input string of arbitrary length is partitioned into a sequence of blocks to the greatest extent possible, so that only the rightmost string in the sequence may be a “partial” block. In Steps 3 and 4, the 32-bit incrementing function is iterated on the initial counter block input to generate a sequence of counter blocks; the input block is the first block of the sequence In Steps 5 and 6, the block cipher is applied to the counter blocks and the results are XORed with the corresponding blocks (or partial block) of the partition of the input string. In Step 7, the sequence of results is concatenated to form the output. Figure 2 below illustrates the GCTR function.

Figure 5.2 GCTRk (ICB,X1llx2ll…………llX*n) = Y1llY2ll………………llY*n

31

Chapter 6 GCM Specification Algorithms 4 and 5 for the authenticated encryption and authenticated decryption functions of GCM are specified in Secs. 6.1 and 6.2 below. The specifications include the inputs, the outputs, the steps of the algorithm, diagrams, and summaries. The suggested notation does not indicate the choice of the underlying block cipher. The inputs that are typically fixed across many invocations of the function are called the prerequisites; however, some of the prerequisites may also be regarded as (varying) input. The prerequisites and the other inputs shall meet the requirements in Sec. 4. For both algorithms, equivalent sets of steps that produce the correct output are permitted. For example, in Algorithm 5, the verification of the tag may precede the computation of the plaintext.

6.1 Algorithm for the Authenticated Encryption Function Algorithm 4 below specifies the authenticated encryption function: Algorithm 4: GCM-AEK (IV, P, A)

Prerequisites: approved block cipher CIPH with a 128-bit block size;key K; definitions of supported inputoutput lengths; supported tag length t associated with the key.

Input: initialization vector IV (whose length is supported); plaintext P (whose length is supported); additional authenticated data A (whose length is supported).

Output: ciphertext C; authentication tag T.

32

In Step 1, the hash subkey for the GHASH function is generated by applying the block cipher to the “zero” block. In Step 2, the pre-counter block (J0) is generated from the IV. In particular, en the length of the IV is 96 bits, then the padding string 031||1 is appended to the IV to form the pre-counter block. Otherwise, the IV is padded with the minimum number of ‘0’ bits, possibly one, so that the length of the resulting string is a multiple of 128 bits (the block size); this string in turn is appended with 64 additional ‘0’ bits, followed by the 64-bit representation of the length of the IV, and the GHASH function is applied to the resulting string to form the precounter block. In Step 3, the 32-bit incrementing function is applied to the pre-counter block to produce the initial counter block for an invocation of the GCTR function on the plaintext. The output of this invocation of the GCTR function is the ciphertext. In Steps 4 and 5, the AAD and the ciphertext are each appended with the minimum number of ‘0’ bits, possibly none, so that the bit lengths of the resulting strings are multiples of the block size. The concatenation of these strings is appended with the 64-bit representations of the lengths of the AAD and the ciphertext, and the GHASH function is applied to the result to produce a single output block. In Step 6, this output block is encrypted using the GCTR function with the pre-counter block that was generated in Step 2, and the result is truncated to the specified tag length to form the authentication tag. The ciphertext and the tag are returned as the output in Step 7.

33

Figure 6.1: GCM-AEK (IV, P, A) = (C, T). The authenticated encryption function is illustrated in Figure 3 above. The determination of J0 from IV (Step 2) is not depicted.

6.2 Algorithm for the Authenticated Decryption Function Algorithm 5 below specifies the authenticated decryption function: Algorithm 5: GCM-ADK (IV, C, A, T)

Prerequisites: approved block cipher CIPH with a 128-bit block size; key K; definitions of supported inputoutput lengths; supported tag length t associated with the key.

Input: initialization vector IV; ciphertext C; additional authenticated data A; authentication tag T.

34

Output: plaintext P or indication of inauthenticity FAIL.

In Step 1, the implementation’s support for the lengths of the IV, the ciphertext, the AAD, and the authentication tag is verified. In Step 2, the hash subkey for the GHASH function is generated by applying the block cipher to the “zero” block. In Step 3, the pre-counter...