20-08-2014, 04:40 PM
Implementation and Analysis of the Advanced Encryption Standard (AES) Algorithm in Different Memory Configurations Project Report
Implementation and Analysis.pdf (Size: 439.5 KB / Downloads: 490)
ABSTRACT
In 1997 the US National Institute for Standards and Technology unveiled Rijndael
as the new Advanced Encryption Standard (AES) to be used throughout the US
government to encrypt sensitive (but not classified) data. The specification for the
algorithm has left enough room to implement the various data transformations
using a broad range of techniques.
These techniques are carefully researched and a combination of suitable ones are
used to create two separate AES implementations, one optimised to use as little
memory space as possible and the other optimised to increase execution speed.
The implementations are extensively tested against precompiled test values and
analysis of the execution times is carried out. This analysis is then used to identify
the different advantages amongst the two implementations and therefore suggest
the circumstances where each would be best suited.
The dissertation then concludes by discussing the possible extensions to the work
carried out in this project including the ways in which the implementations can be
combined to create hybrid solutions for specific tasks.
Introduction
Encryption is always going to be necessary for maintaining privacy in our
personal communications. In fact it was created for that exact reason. However
people are always finding new ways of “breaking” encryption and therefore
leaving these communications open to being read or possibly tampered with by a
third party.
In 1997 The Unites States National Institute of Standards and Technology (NIST)
asked the public, including academics and professionals, to submit new
cryptography algorithms as possible candidates to become the new Advanced
Encryption Standard (AES). The previous standard called the Data Encryption
Standard (DES) was in need of replacement by a new algorithm which was to be
used throughout the US government to encrypt sensitive (but not classified)
information.
There were 3 main candidates for the new standard namely, Rijndael, Serpent,
2fish, RC6 and MARS. In November 2001 Rijndael was chosen as the new AES
algorithm. Rijndael can encrypt using 128, 192 and 256 bit cipher keys which are
applied, using the algorithm, to data blocks of 128bits to perform the required
transformation.
The aim of this dissertation is to produce two implementations of the AES
encryption algorithm for use in two very different circumstances. The first of
these implementations is designed for use in a conventional home computer
system. The main requirement for this version is to maximise the speed at which
the encryption can be achieved at the cost of memory usage. The second
implementation has the reverse requirements of the first. The solution aims to
minimise usage of memory space at the cost of speed of execution. This solution
would be useful in small devices such as mobile phones, personal digital
assistants (PDA’s) and possibly smart chips used in credit and debit cards
Literature Review
Firstly, a look at the history and background of encryption should produce a
clearer understanding for the need of security and how implementations such
as the one being produced can help with this need.
The next part of this review will look at the more specific encryption technique
known as the Advanced Encryption Standard (AES) and explain why it is used,
how it works and how it can be implemented. Following this, the investigation
must be expanded to search for solutions for the problem at hand. This
involves looking for possible optimisation techniques and how they can be
incorporated into the solution as well as highlighting the differences needed
between the two implementations.
In addition, this review will be considering other factors which will contribute
to the overall performance of the final implementations. These factors are
likely to include the choice of programming language since this can have a
large effect of the overall efficiency of algorithms.
Finally, due to the rapid advances in the technology of encryption and
cryptanalysis it is necessary to examine the likelihood of the dissertation
findings being obsolete shortly after they are produced. This has been known to
happen in the past where weaknesses are found in other encryption systems. If
this was the case then it may be necessary to use another encryption standard
Breakdown of the Algorithm
The overall structure of the Rijndael algorithm is very straight forward and has
often be praised for its simplicity. It is constructed from a repeated number of
grouped operations called rounds (the number depends on the block length).
The algorithm takes an encryption key of 128, 192 or 256 bit length as an input
and a data block length of 128bits (The size of the blocks when the message
has been split up).
The algorithm treats the input data as a matrix of bytes. A 4x4 matrix holds the
input message in its individual bytes and the transformations in the algorithm
are then acted upon this matrix. The “current state” is the 4x4 matrix after it
has gone through a number of these transformations.
Current research in cryptanalysis shows that the resistance of the Rijndael
algorithm to cryptanalytic attacks increases with the number of rounds there
are (Daemen and Rijmen 2002). The choice for the number of rounds was
decided by taking the number of rounds required to make short-cut attacks
ineffective and then adding a number of rounds as a safety margin. The chosen
number of rounds is different depending on the key length chosen:
The Future of AES
It is very important to look at the future of the Rijndael algorithm since there is
no point implementing an encryption algorithm with known floors. The
eventual downfall of the DES was the key length as the exhaustive list of
possible keys was not big enough and so as technology advanced it became
easier to test all the keys quickly.
The main change from DES to AES is well motivated from a security point of
view (url: crypto). Ferguson et al. (2002) has done lots of cryptanalysis on the
algorithm and found techniques to attempt to break up to 6 rounds of the 128-
bit version however that still leaves a security margin of 4 rounds which are
untouched. Another possibility that remains is that of “brute force”. This
requires testing every possible key to find a match. This is a completely
unusable tactic when using 128 bit keys since this equates to 3.40282367 ×
1038 possible keys. This is an immense amount of keys and there is not a
computer in the foreseeable future which could ever process that number of
keys.
In addition to this, the specification for Rijndael means that the number of
rounds is a parameter which can be increased further without any need for
additional specifications. This means that if a security need was extremely
great then an increase in rounds is very easy to implement. (Daemen & Rijmen
2000). Also if a successful attack on the algorithm was published then the
number of rounds could be increased to counteract it.
Choice of Programming Language
The final consideration to make before any implementation details can be
considered is the choice of programming language. This can have a large
effect over the performance of the algorithm which is of high importance to
this dissertation.
Since the coding of the solution may be quite complex it will be an advantage
to use a language which I am already competent in. These include C, Matlab
and Java. The advantage of using Matlab would be that the algorithm can
work directly on matrices which Matlab can maintain and therefore allow for a
more natural, and easier to understand solution. However, the downside to
Matlab is the performance as it cannot produce computational speeds close to
C. Since this is one of the main objectives for one of the solutions, Matlab will
not be used.
If Java was to be used then the application would be able to run on multiple
operating systems and processors. As advantageous as this is, it does result in
loss of performance again compared to C. Also there is little or no scope for
using the object-orientated advantage of Java for the problem at hand. For
these reasons I have chosen C as the programming language for the
implementations
Mathematical Background
As explained earlier, the Rijndael algorithm acts upon a 4x4 matrix with each
matrix entry holding one byte of data. Initially the input string to be encrypted
is split into separate bytes and then placed into the matrix in a specified order.
Once in the form of a matrix, the algorithm applies several different
mathematical operations to the bytes with the outputs of these operations also
being bytes. Since a single byte of data can only represent a finite number of
elements (e.g. 1 byte can represent 256 different decimal numbers) it means
that these operations are acting on a finite field. These types of fields are
known as the Galois Fields. This particular one is denoted GF (28
) as there are
2
8
different elements.
In order to use this field it is necessary to fully define some simple arithmetic
operations. In order to define them a method of representing a byte
mathematically must be chosen. There are a number of different ways to
represent the field GF (28
) however; all of them are in fact isomorphic. In a
mathematical sense this means they are all essentially equivalent.
Multiplication
Multiplication using the new polynomials works in the same way as with the
previous polynomial representation except for the fact that the coefficients are
now elements of GF (28
) and not GF (2). This means that any arithmetic
operations carried out between the coefficients must be done using the rules set
out above for elements in GF (28
).
Once again a complication appears with the order of the resulting polynomial
being too large to be represented as a 4-byte vector. Therefore the result must
be reduced by calculating the result modulo m(x), where m(x) is the irreducible
polynomial
Application Objectives
Obviously the first main objective for both implementations is the successful
use of the algorithm on the plaintext entered by the user. To check that this
goal has been achieved it is necessary to acquire some precompiled test data
where the algorithm has already been correctly applied to a given input.
Both implementations will need to be able to handle the three different key
lengths (128, 192, 256 bits) and adapt the algorithm accordingly as set out in
the official AES specification.
The user must be able to enter (as arguments to the program) the key size, a
128 bit plaintext and the key. The application must use these arguments to
calculate the correct ciphertext and display it back to the user.
This dissertation is not concerned with the possible applications that may use
the encryption technique, only the functionality of the actual encryption itself.
Therefore there is no requirement to have an extensive user interface on either
implementation. Instead the program only is only required to accept arguments
through the command line to test the working of the algorithm against test data.
The Algorithm
This chapter explains the different parts of the AES algorithm and how they
link together to create the cipher. The user will initiate the procedure by
entering a 128 bit plaintext (32 hexadecimal characters) and a 128, 192, or 256
bit key.
For this chapter a number of symbols are used to shorten the notation:
Nb – Refers to the number of words in the input plaintext
(i.e. number of bits in the plaintext / 32)
Nk – Number of words in the input key
(i.e. number of bits in the key / 32)
Nr – The number of rounds in the encryption algorithm.
Note that in the specification for Rijndael encryption, it allows for plaintext
block sizes of 128, 192, 256 bits. However, in the AES specification this was
altered to only allow 128 bit block sizes. This means that Nb (The number of
words in the input plaintext) is always 128 bit / 32 = 4
Function Walkthroughs (Low-Level)
This chapter aims to provide the reader with an understanding of exactly how
the encryption algorithm is implemented. The first section provides a
walkthrough of the functions which are common to both implementations. The
next two sections refer to functions which are specifically written for just one
Implementation
The program names for the two implementations are as follows:
AES - Low Memory AES Implementation
QAES - For the Quick AES Implementation
These applications have been written in the C programming language and the
source code for these two applications (AES.c and QAES.c) is available in the
appendix.
The syntax to run the application is as follows:
(Q)AES [number of bits in key] [plaintext input] [key input]
The application will then return the ciphertext to the screen. For example
Software Testing
This chapter deals with two types of testing of the written applications. The
first section tests the accuracy of the encryption algorithm against precompiled
test data to check that the correct output ciphertexts are being produced. The
second section deals with the functionality of the program under incorrect
inputs from the user.
Speed Analysis
One of the main objectives for this dissertation is to conduct analysis of the
speed at which the encryption can take place using the different
implementations. This analysis can be used to help build an understanding of
which hardware conditions suit different implementations.
As mentioned earlier we generally expect to achieve faster results from the
high speed implementation due to the use of a number of lookup tables.
However, the initialisation of these tables may produce the reverse effects
when encrypting small amounts of data
Conclusion
From the very start of this project it was expected that the task of implementing
an encryption algorithm would be complex and this assumption was proved
correct. The levels of mathematical complexity in the algorithm meant that a
large amount of time was required to fully understand the structure of the
cipher and the individual transformations involved in it before any form of
implementation could be considered.
Fortunately there has been a reasonable amount of material available, each with
a different person’s perspective, concerned with the AES algorithm. These
different points of view help to build a good overall understanding and have
been essential in achieving the desired goals.
The original objectives for this dissertation were to produce two fully working
implementations of the AES encryption both with their own specific
optimisations. It is evident from the test data that both implementations are
encrypting correctly with respect to the official specification and therefore the
first main objective has been met. However during the software testing a small
number of problems arose where the program accepted non-hexadecimal
characters as inputs when it should not. If the implementations are to be used
in the future then a safety check must be placed at the start of the program to
fix this problem.
In addition to this primary goal, there has been an extremely effective use of
previous work to produce the optimisations that were required for each
implementation to achieve its own individual objectives. The use of lookup
tables in the high speed implementation has dramatically affected the time it
takes to encrypt large amounts of data whilst still keeping the overheads of the
initialisation process to a reasonable level. Furthermore, the on-the-fly
techniques incorporated into the low memory solution has resulted in an
implementation that can encrypt small amounts of data at competitive speeds,
without the need for the additional memory space.