AES Advanced Encryption Standard
AES is a symmetric block cipher for encrypting texts which can be decrypted with the original encryption key.
For many purposes, a simpler encryption algorithm such as TEA is perfectly adequate but if you suspect the worlds best cryptographic minds, and a few million dollars of computing resource, might be attempting to crack your security, then AES, based on the Rijndael algorithm, is the tightest security currently available (approved by the US government for classified information up to Secret and in in 192 or 256 key lengths, up to Top Secret). AES was adopted by NIST in 2001 as FIPS-197, and is the replacement for DES which was withdrawn in 2005.
This script also includes a wrapper function which implements AES in the Counter mode of operation (specified in NIST SP 800-38A) to encrypt arbitrary texts – many descriptions of AES limit themselves to the Cipher routine itself, and don’t consider how it can be used to encrypt texts.
Much of the Rijndael algorithm is based on arithmetic on a finite field, or Galois field (after the mathematician). Regular arithmetic works on an infinite range of numbers keep doubling a number and it will get ever bigger. Arithmetic in a finite field is limited to numbers within that field. The Rijndael algorithm works in GF(28), in which arithmetic results can always be stored within one byte – which is pretty convenient for computers. I cant begin to understand the maths (considering that addition and subtraction are the same thing – an XOR operation – and multiplication is performed ‘modulo an irreducible polynomial’: doubling 0x80 in GF(28) gives 0x1b).
The Rijndael algorithm lends itself to widely differing implementations, since the maths can be either coded directly, or pre-computed as lookup tables – directly parallel to using log tables for arithmetic. Different implementations can have varying pay-offs between speed, complexity, and storage requirements. Some may barely resemble each other. In this implementation, I have followed the standard closely; as per the standard, I have used a lookup table (‘S-box’) to implement the multiplicative inverse (i.e. 1/x) within a finite field (used for the SubBytes transformation), but other calculations are made directly rather than being pre-computed.
If you want to convince yourself that the Cipher function is working
properly internally (and you should!), NIST provide test vectors for AES (appendix C.1 of
the standard). Click
The Inverse Cipher is largely a mirror of the Cipher routine, with parallel functions for Cipher, SubBytes and ShiftRows. The MixColumns routine is slightly more complex in the inverse. I have not implemented the inverse cipher here as it is not required in counter mode.
Counter mode of operation: the AES standard concerns itself with numeric or binary data (Rijndael, along with most other encryption algorithms, works on a fixed-size block of numbers – in the case of AES, each block is 128 bits or 16 bytes).
In order to make use of it to encrypt real things (such as texts), it has to be used within a certain ‘mode of operation’. This is the interface between text or files, and the purely numerical encryption algorithm. See NIST Special Publication SP800-38A for more details and test vectors.
The simplest mode of operation (‘electronic codebook’) encrypts a text block-by-block – but since the same block of plaintext will always generate the same block of ciphertext, this can leave too many clues for attackers.
In the ‘counter mode’ used in this implementation, a counter which changes with each block is first encrypted, and the result is bitwise XOR’d with the plaintext block to get the ciphertext block (so the plaintext is not actually directly encrypted). A unique ‘nonce’ is incorporated in the counter to ensure different ciphertexts are always generated from the same plaintext every time it is encrypted; this number is stored at the head of the ciphertext to enable decryption. A combination of seconds since 1 Jan 1970 and millisecond-timestamp gives a very effective nonce. (To resist cryptographic attacks, the nonce does not need to be secret or unpredictable, but it is imperative that it is unique).
A curious quality of counter mode is that decryption also uses the cipher algorithm rather than the inverse-cipher algorithm. Though simple to implement, it has been established to be very secure.
Encrypting texts or files require not just the mode of operation. When implementing AES, you have to consider
The key is obtained by applying the Cipher routine to encrypt the first 16/24/32 characters of the password (using 128-/192-/256-bit keys) to make the key.
The test vectors have been confirmed in IE 6 & 7 (Win), FF 2 & 3 (Win), Safari 2 (Mac), Opera 9 (Linux), and Konqueror 3 (Linux) (thx Jon Passki, Vincenzo Buttazzo). If you can confirm any other versions (or find any problems), please let me know!
Speed: as mentioned, this is not an optimised implementation – on a 2GHz Intel Core 2 machine, this implementation processes around 6kB/sec using IE7, and 30kB/sec using FF3(!) (one page of text at a standard 250 words is about 1.5kB). The 128-bit version is some 25% faster than the 256-bit version.
For more information, have a look at
For some security applications, a cryptographic hash is more appropriate than encryption – if you are interested in a hash function, see my implementation of SHA-1.
Note: this script was revised on 1 August 2008 to use Base64 encoding – the previous version, which used less standard encoding, is still available if you have need to refer back to it.
If you have any queries or find any problems, please contact me.
© 2005–2008 Chris Veness