ENCRYPTION
`
`Advanced Encryption
`Standard (AES)
`
`Simon Heron, Internet Security Analyst, Network Box
`
`Ever since humans started talking, we have been trying to work out a way
`of communicating information to one person, while keeping it secret from
`everyone else. Certainly, when you start to look at encryption methods, you are
`introduced to the ‘Caesar’ Cypher. which shows how old encryption is and how
`simple old ciphers now are for us to break.
`Explanation
`Before going in to the detail, here are
`definitions of some of the terms I will
`be using:
`
`Simon Heron
`
`Encryption Key Size: This is the
`length in bits of the key used to encrypt
`or decrypt the message. In this standard
`the cipher key can only be 128, 192 or
`256 bits long.
`There are some differences in the way
`the algorithm works for the different
`encryption key lengths, so this paper
`will primarily focus on the cipher key
`of 128 bits.
`
`Some basic principles
`
`We have seen plenty of evidence of
`this since the introduction of the Data
`Encryption Standard (DES) in the 70s,
`its various incarnations since then, and
`most recently its upgrade to Triple DES
`in 1999 (which happened as attacks on
`the original cipher became increasingly
`viable as computing resources grew).
`However, even Triple DES has had
`its day and has, since 2002, been
`superseded by the Advanced Encryption
`Standard (AES) that we should all
`be using. But keeping encryption
`technology ahead of the game is
`a continual process, and security
`professionals are already investigating
`the successor to AES.
`
`“Even Triple DES has had its
`day and has, since 2002, been
`superseded by the Advanced
`Encryption Standard (AES) that
`we should all be using”
`
`This is, inevitably, a moving target;
`it has to be to keep up with computing
`power and increasingly sophisticated
`mathematical analysis. But AES is still
`a long way from being obsolete. There
`are still many solutions that are using
`its predecessor 3DES. So in this paper,
`I will look at how AES works, without
`going into the maths.
`
`Figure 1: The State.
`
`8
`
`Network Security
`
`Plaintext: The original message and the
`one that is to be encrypted.
`
`Ciphertext: The encrypted message
`which is the output of the algorithm.
`
`There are three important issues for an
`encryption algorithm:
`
`Block Size: The number of bits that
`the cipher will operate on. This is
`128 bits in AES. Each message is split
`up into this number of bits and the
`operations described below carried
`out.
`Even Triple DES has had its day and
`has, since 2002, been superseded by
`the Advanced Encryption Standard
`(AES) that we should all be using”
`AES has a fixed block size of 128
`bits. So all data that is to be encrypted
`will be broken up into 128 bit blocks.
`Padding is added if the data is not a
`multiple of 128bits. For manipulation
`purposes, 128 bits = 16 bytes (8 * 16
`= 128) which is then treated as a 4 x 4
`byte matrix.
`This is termed the ‘state’. This is
`important as the subsequent algorithm
`will manipulate this ‘state’ to create
`the ciphertext.
`
`Only the encryption key is secret
`The algorithm can be made public but
`that does not help an attacker decipher a
`message as the encryption key is required
`to implement the algorithm. This allows
`us to define a standard which everybody
`can follow.
`
`Confusion
`This involves obscuring the relationship
`between the plaintext and the
`ciphertext. So in its simplest form, it is
`substituting one letter for a completely
`different one. The trick is to make that
`relationship impenetrable.
`
`Figure 2: The Encryption Key.
`
`December 2009
`
`PNC 1053
`
`Page 1 of 5
`
`

`

`ENCRYPTION
`
`Diffusion
`This is the mixing and reordering of the
`message. So operations here would be
`shifting data or transposing columns,
`for instance.
`
`Rijndael’s Substitution
`Box (S-Box)
`This is the most important function
`that performs substitution which
`obscures the relationship between
`the plaintext and the ciphertext. It
`introduces the second of the three
`requirements above: confusion.
`The S-Box is created by using a
`form of modulus mathematics which
`is called Rijndael’s Galois field and
`within this field, arithmetic has special
`properties which ensure values do not
`exceed 28 which keeps everything in
`a byte, which is great for computers.
`The choice of this field and other steps
`that are taken to derive the S-Box are
`carefully chosen to resist cryptanalysis
`and are definitely beyond the scope
`of this article. In practice, S-box is
`generally used in the form of a lookup
`table:
`The thing to hang onto here is
`that to process a number through the
`S-Box, each number is divided into
`its most and least significant nibble
`(4 bits). The least significant nibble
`identifies the column to use in the
`above table and the most significant
`nibble defines the row.
`
`An example
`For this, we have to move to
`hexadecimal which is frequently
`indicated by prefixing a number
`with ‘0x’ so that 16 in base 10
`(decimal) becomes 0x10 in base 16
`(hexadecimal).
`So to convert 0x53, divide into 0x50
`and 0x03 and at the intersection of row
`and column we find: 0xed. Similarly,
`0xe5 becomes 0xd9.
`
`Table 1: S-box data is generally provided as a look-up table.
`
`Table 2: The look-up table that results from the RCON function.
`
`Figure 3: Shift Function.
`
`Figure 4: S-Box step.
`
`December 2009
`
`Network Security
`
`9
`
`Page 2 of 5
`
`

`

`ENCRYPTION
`
`Figure 5: 1st Round so Rcon step, rcon(1) = 0x01.
`
`Figure 6: Creating the first column of the new key.
`
`Figure 7: Creating round key for round 1.
`
`Rcon
`This function is used to confuse the
`derivations of the encryption key that
`will be used in the standard. Very
`simplistically, this function is putting
`2 to the power of 254 to 509 but in
`the Rijndael’s Galois field which uses
`its form of mathematics to keep values
`within a byte. The result is another look
`up table.
`
`This is used to create a number of
`encryption keys (or round keys). Each
`key size (128, 192 and 256 bits) has
`a different number of ‘rounds’. Each
`round requires a different key to provide
`the required diffusion and hence a
`different number of round keys need to
`be derived from the encryption key.
`For AES128, the first ‘n’ bytes are the
`original key itself. Then the last column
`
`Figure 8: The initial round.
`
`10
`
`Network Security
`
`of the key is taken and round shifted (as
`shown in figure 3, above).
`The result is then pushed through
`the s-box to provide a completely new
`column:
`The most significant byte of the result
`is then XOR-ed with a value from the
`Rcon table above. For the first round,
`the index into the Rcon table will be 1,
`and then is incremented for each new
`round.
`To create the first column of the next
`round key, the result of this XOR is
`XOR-ed with the first column of the
`previous round key. In the case of the
`first round, this is:
`The next three columns of the new
`‘key’ are created by taking each new
`column created and XOR-ing it with
`the four byte block 16 bytes before the
`new expansion key.
`This is repeated until there are enough
`keys for each round. For AES128, there
`are 10 rounds and so 10 extra keys are
`required.
`Enough groundwork. Now lets start
`the encryption.
`
`The Advanced Encryption Standard
`There are three main stages in the
`standard:
`
`The initial round (this is really just
`initialisation).
`The intermediate rounds
`The final round
`
`(cid:115)(cid:0)(cid:0)(cid:52)(cid:72)(cid:69)(cid:0)(cid:73)(cid:78)(cid:73)(cid:84)(cid:73)(cid:65)(cid:76)(cid:0)(cid:82)(cid:79)(cid:85)(cid:78)(cid:68)
`This is straightforward: take the plain-
`text and XOR it with the encryption
`key.
`(cid:115)(cid:0)(cid:0)(cid:52)(cid:72)(cid:69)(cid:0)(cid:73)(cid:78)(cid:84)(cid:69)(cid:82)(cid:77)(cid:69)(cid:68)(cid:73)(cid:65)(cid:84)(cid:69)(cid:0)(cid:82)(cid:79)(cid:85)(cid:78)(cid:68)(cid:83)
`This stage has four steps:
`
`(cid:54)(cid:88)(cid:69)(cid:37)(cid:92)(cid:87)(cid:72)(cid:86) – use the s-box to replace
`each byte of the state with a new
`value.
`(cid:54)(cid:75)(cid:76)(cid:73)(cid:87)(cid:53)(cid:82)(cid:90)(cid:86) – Rotate the state in a
`prescribed fashion.
`(cid:48)(cid:76)(cid:91)(cid:38)(cid:82)(cid:79)(cid:88)(cid:80)(cid:81)(cid:86) – Take 4 bytes and mix
`them so that all four bytes have an
`effect on the value of each of the
`resulting four bytes.
`(cid:36)(cid:71)(cid:71)(cid:53)(cid:82)(cid:88)(cid:81)(cid:71)(cid:46)(cid:72)(cid:92) – each byte of the
`state is combined with the round key
`created by the key schedule above.
`
`December 2009
`
`Page 3 of 5
`
`

`

`ENCRYPTION
`
`x8 + x4 + x3 + x + 1 to keep it within
`the finite field. In the following, the
`(cid:83)(cid:89)(cid:77)(cid:66)(cid:79)(cid:76)(cid:0)(cid:104)(cid:115)(cid:118)(cid:0)(cid:73)(cid:83)(cid:0)(cid:85)(cid:83)(cid:69)(cid:68)(cid:0)(cid:84)(cid:79)(cid:0)(cid:68)(cid:69)(cid:78)(cid:79)(cid:84)(cid:69)(cid:0)(cid:84)(cid:72)(cid:73)(cid:83)(cid:0)(cid:84)(cid:89)(cid:80)(cid:69)(cid:0)(cid:79)(cid:70)(cid:0)
`multiplication:
`
`x0(cid:0)(cid:29)(cid:0)(cid:18)(cid:115)(cid:57)0(cid:0)(cid:62)(cid:0)(cid:19)(cid:115)(cid:57)5 ^ Y10 ^ Y15
`x4 = Y0(cid:0)(cid:62)(cid:0)(cid:18)(cid:115)(cid:57)5 (cid:62)(cid:0)(cid:19)(cid:115)(cid:57)10 ^ Y15
`x8 = Y0 ^ Y5 (cid:62)(cid:0)(cid:18)(cid:115)(cid:57)10(cid:0)(cid:62)(cid:0)(cid:19)(cid:115)(cid:57)15
`x12(cid:0)(cid:29)(cid:0)(cid:19)(cid:115)(cid:57)0 ^ Y5 ^ Y10 (cid:62)(cid:0)(cid:18)(cid:115)(cid:57)15
`
`The result, rx, satisfies the requirement to
`ensure that all four rows impact on the
`result. As this step uses XOR and is care-
`fully designed, it can be reduced to
`the lines of C outlined in listing 1:
`
`Step 4: AddRoundKey
`This is the same as the initial round above,
`but using one of the keys derived from the
`Rijndael’s key schedule. So, the result from
`Step 3, MixColumns, is XOR-ed with the
`next in the sequence of keys generated by
`the Rijndael’s Key Schedule so each round
`is XOR-ed with a different key derived
`from the original.
`
`Repeat the steps
`Repeat steps 1 to 4 until the number of
`‘rounds’ defined for the keysize by the
`standard have been carried out for this
`stage:
`
`AES128 – repeat 9 times
`AES192 – repeat 11 times
`AES256 – repeat 13 times
`
`This leaves one round for the final step.
`
`(cid:115)(cid:0)(cid:0)(cid:52)(cid:72)(cid:69)(cid:0)(cid:70)(cid:73)(cid:78)(cid:65)(cid:76)(cid:0)(cid:82)(cid:79)(cid:85)(cid:78)(cid:68)
`There are more attacks being devised
`against AES and as computing capac-
`ity improves, developments of these
`attacks may become practicable”
`
`This round carries out three steps:
`
`(cid:54)(cid:88)(cid:69)(cid:37)(cid:92)(cid:87)(cid:72)(cid:86)
`(cid:54)(cid:75)(cid:76)(cid:73)(cid:87)(cid:53)(cid:82)(cid:90)(cid:86)
`(cid:36)(cid:71)(cid:71)(cid:53)(cid:82)(cid:88)(cid:81)(cid:71)(cid:46)(cid:72)(cid:92)
`
`Step 2: ShiftRows
`The next two steps now introduce
`‘diffusion’ into the standard. For
`AES128, each row is shifted left by the
`value of the row where the top row is
`row zero. So the top row stays as it is,
`the first row is shift 1 to the left, the
`second row is shifted two to the left and
`the third row three to the left.
`
`Step 3: MixColumns
`In this step the four bytes of each
`column of the state are used as input.
`So, for example, from figure 10, the first
`four bytes to be used are:
`This step takes these four bytes and
`multiplies them in Rijndael’s Galois
`field by a fixed polynomial:
`
`c(x) = 3x3 + x2 + x + 2 modulo x4 + 1
`
`This results in the following matrix
`which may make things clearer:
`Since this is done in Rijndael’s Galois
`field, the addition is just exclusive OR
`(^) but the multiplication is followed
`by dividing by a reducing polynomial
`
`The reason why the final round does not
`have a ‘mixcolumns’ step is because that
`step is used to feed into the next round.
`Since this is the final step and there is no
`next round, the final round excludes that
`step.
`
`Network Security
`
`11
`
`Figure 9: Use the S-Box to create ‘confusion’.
`
`Figure 10: Shift Rows step.
`
`Figure 11: The resulting four input bytes
`from the row shifting step.
`
`Figure 12: Matrix produced by polynomial
`multiplation of four input bytes (as in listing 1).
`
`Let us look at each of these steps in a bit
`more detail.
`
`Step 1: SubBytes
`Take each byte and using Rijndael’s
`S-Box algorithm map that byte to the
`new value.
`
`December 2009
`
`Page 4 of 5
`
`

`

`GRIDONE
`
`void gmix_column(unsigned char *r) {
`
`unsigned char a[4];
`
`unsigned char b[4];
`
`unsigned char c;
`
`unsigned char h;
`
`/* The array ‘a’ is simply a copy of the input array ‘r’
`
`* The array ‘b’ is each element of the array ‘a’ multiplied by
`
`* in Rijndael’s Galois field
`
`* a[n] ^ b[n] is element n multiplied by 3 in Rijndael’s Galois field */
`
`for(c=0;c<4;c++) {
`
`
`a[c] = r[c];
`
`
`h = r[c] & 0x80; /* hi bit */
`
`
`b[c] = r[c] << 1;
`
`
`if(h == 0x80)
`
`
`
`b[c] ^= 0x1b; /* Rijndael’s Galois field */
`}
`r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; /* 2 * a0 + a3 + a2 + 3 * a1 */
`r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; /* 2 * a1 + a0 + a3 + 3 * a2 */
`r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; /* 2 * a2 + a1 + a0 + 3 * a3 */
`r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; /* 2 * a3 + a2 + a1 + 3 * a0 */
`
`
`
`
`
`
`}
`
`Listing 1: C code designed to mix columns in a Rijndael Galois field. (Code provided by: http://
`en.wikipedia.org/wiki/Rijndael_mix_columns).
`
`That is it, the state is encrypted.
`
`Conclusion
`There are more attacks being devised
`against AES and as computing capacity
`improves, developments of these attacks
`may become practicable. However,
`AES can always up the number of
`rounds or move to creating dynamic
`
`S-boxes to improve the resistance of the
`standard. The main attack is usually
`against implementations of the standard
`(where someone has programmed the
`standard and made a mistake that can
`be exploited). It is recommended that
`properly validated and supported code
`is used – of which there are a number of
`options – to protect against this sort of
`attack.
`
`About the author
`
`Simon Heron is an internet security analyst
`at Network Box (UK) Ltd, a managed
`security company, where he is responsible for
`developing the overall business and technology
`strategy and growth.
`Heron has more than 16 years experience
`in the IT industry, including eight years
`experience in internet security. During
`this time he has developed and designed
`technologies ranging from firewalls, anti-virus,
`LANs and WANs.
`Prior to Network Box, Heron co-founded
`and was Technical Director of Cresco
`Technologies Ltd, a network design and
`simulation solution company with customers
`in the USA, Europe and China. Before that
`he worked for Microsystems Engineering Ltd,
`as a Project Manager, where he implemented
`network security for the company.
`Heron began his career as a digital
`hardware and software engineer, developing
`pioneering speech recognition technology before
`moving on to work for the British Antarctic
`Survey (B.A.S.) as science project leader.
`While at the B.A.S. he spent two Antarctic
`winters at the research station Halley in the
`Antarctic, developing and enhancing graphical
`technologies in the harshest of conditions.
`Heron has an MSc in Microprocessor
`Technology and Applications, and a BSc in
`Naval Architecture and Shipbuilding and
`is a Certified Information Systems Security
`Professional (CISSP).
`
`A complement
`to the GridOne
`authentication
`method
`
`Seung S Yang and Hongsik Choi
`
`Authentication is the process of confirming that something claimed is true,
`and an authentication method is the way of proving the claim. As more and
`more people use networked computer systems in their everyday lives – for
`example, in online banking, email, and online shopping – the importance of
`authentication is increasing.
`
`12
`
`Network Security
`
`Seung S Yang
`
`Hongsik Choi
`
`Three types of authentication methods
`are frequently used: identification (ID)
`device-based, biometric-based and
`password-based. A password-based
`authentication method is easier to
`implement and deploy, and costs less to
`manage than the other two. The method
`relies on a possession of knowledge
`
`December 2009
`
`Page 5 of 5
`
`