Symmetric Encryption

The attributes of symmetric encryption

What makes encryption symmetric? You know what symmetry is right? So you can hazard a guess… Symmetric encryption algorithms use the same key for both encryption and decryption. They are typically used for blocks of data such as files or on streams of data such as a network data flow. Table 1, shown below, defines six of the main attributes of symmetric encryption.

Table 1: The main attributes of symmetric encryption

AttributeProperty
KeyOne key is shared between two or more entities.
Key exchangeOut of band (communication outside of the main system: for example, sending a text message with the key, password or login code to access your email or banking website) or by using asymmetric encryption.
SpeedFast with minimal complexity.
Key lengthFixed key length: 128-bit, 192-bit or 256-bit, for example.
ApplicationsBulk data encryption: files, databases, logical partitions and physical drives. Protecting data-in-transit: Internet Protocol Security (IPSec), Secure Shell (SSH) and Transport Layer Security (TLS)/Secure Sockets Layer (SSL).
Security propertiesConfidentiality.

Symmetric encryption algorithms

Some of the best known encryption algorithms in use across modern technology are symmetric algorithms. The list includes DES (Data Encryption Standard), 3DES (Triple DES), Twofish, Blowfish, RC4, Serpent and AES(Rijndael).

Data Encryption Standard (DES)

The original DES was published on 15 January 1977 by the National Institute of Standards and Technology (NIST). It is a symmetric block cipher with a 64 bit block size. The block size of a cipher is the fixed number of bits that the cipher operates on during any encryption/decryption operation. It turns out that with a 64 bit block size, you dont have to encrypt a block or stream of data that is too large before you run into problems of block repetition. Still between 1977 and the retirement of DES, the amount of data seemed like a large amount (less so nowadays).

DES uses a 64 bit key however 8 bits are sacrificed as overhead due to error protection/detection meaning the effective key length is 56 bits. With a key length of 56 bits, 72 thousand trillion keys are therefore possible. Thats a lot of possibilities. DES, as well as many other well known symmetric ciphers (3DES, Twofish, Blowfish and RC5) are based on an earlier cipher known as a Feistel cipher. Feistel ciphers have two main advantages. First, they provide structural reusability (the same structure can be used for encryption and decryption); therefore, the decryption logic does not need to be implemented in reverse order. The second advantage is one-way functions. Ill write a post down the line about Feistel ciphers and if Ive done it yet then you can click HERE to go read it. Ok you’re still here so I obviously haven’t written it yet. Get on twitter and give me a nudge. Ok lets look in a little bit more detail about how these encryption algorithms work.

Substitution box (S box) & Permutation box (P box)

Symmetric block ciphers typically use structures called S boxes and P boxes to work with their keys to transform input to output. S boxes along with P boxes work together to obscure the relationship between the key and the ciphertext. This conforms to the Shannon principle of confusion.S boxes are used in many symmetric block ciphers including DES, 3DES, Blowfish, Twofish and the daddy of them all, AES. An S box takes a fixed number of bits on the input and maps it to a fixed number of bits at the output according to an agreed lookup table. The output and input need not be the same bit length. S boxes are designed with diffusion in mind such that changing a single input bit should result in the change of two or more output bits and should also, on average, keep a reasonable balance between 0s and 1s.

Permutation boxes typically come after S boxes and effectively jumble the block in a predetermined way. Again this is done to obfuscate the relationship between the key and the ciphertext. When taken together the S box and the P box make up whats called an SP network and encryption algorithms use a number of these SP networks in succession (known as rounds, as in boxing rounds) to transform the input plaintext block into the output ciphertext block.

Advanced Encryption Standard (AES)

When DES was overtaken by data demands and Moores law and placed into an early grave by being demonstrably brute forced, the world needed to find a successor. That successor needed to be robust enough to last for the foreseeable future so a global competition invited all comers to compete to have their algorithm take the crown and be named as the new Advanced Encryption Standard. In the meantime DES needed to be temporarily shored up and thus was born 3DES which fudged a bit more security but not in a sustainable way.

The competition whittled the entrants down to the final 5 and these 5 went into the final stages where they were tested and challenged to destruction. These finalists were, MARS, RC6, Rijndael, Serpent, and Twofish. Each algorithm had done great to make it this far but there could be only one winner and so two Belgian cryptographers, Vincent Rijmen and Joan Daemen won the contest from 15 shortlisted proposals and Rijndael was announced as the lucky algorithm that would lose its name and forever be known as AES.

Rijndael Encryption Algorithm

Let’s take a look at the winner of the competition, the Rijndael algorithm. Rijndael is a 128 block size algorithm and uses three key lengths, namely 128, 192 and 256 bit keys. Like Feistel it uses rounds of increasing encryption where repetition further obfuscates the plaintext and, like all encryption algorithms which use rounds, there is a tradeoff between rounds and computational overhead. So 128 bit key AES (Rijndael) uses 10 rounds, 192 bit uses 12 and 256 uses 14. Each round (apart from the last) breaks a round into 4 parts, namely, SubBytes, ShiftRows, MixColumns and AddRoundKey. Lets look at each of these in turn.

SubBytes

The SubBytes stage of a Rijndael round is simply the use of an S-Box and the Rijndael S-Box is shown below. This step adds confusion as per the Shannon model.

000102030405060708090a0b0c0d0e0f
00637c777bf26b6fc53001672bfed7ab76
10ca82c97dfa5947f0add4a2af9ca472c0
20b7fd9326363ff7cc34a5e5f171d83115
3004c723c31896059a071280e2eb27b275
4009832c1a1b6e5aa0523bd6b329e32f84
5053d100ed20fcb15b6acbbe394a4c58cf
60d0efaafb434d338545f9027f503c9fa8
7051a3408f929d38f5bcb6da2110fff3d2
80cd0c13ec5f974417c4a77e3d645d1973
9060814fdc222a908846eeb814de5e0bdb
a0e0323a0a4906245cc2d3ac629195e479
b0e7c8376d8dd54ea96c56f4ea657aae08
c0ba78252e1ca6b4c6e8dd741f4bbd8b8a
d0703eb5664803f60e613557b986c11d9e
e0e1f8981169d98e949b1e87e9ce5528df
f08ca1890dbfe6426841992d0fb054bb16
Rijndael SubBytes S-Box

Thus, the 4×4 block (known as a state) is systematically substituted for its replacement byte from the table above and that concludes part 1.

ShiftRows

The shift rows step is similarly straightforward. The 4×4 state which is produced is now passed to this stage which does the following to it.

  • Row 0 (top row) remains unchanged
  • Row 1 (next row down) is shifted to the left by one block
  • Row 2 (next row down) is shifted to the left by two blocks
  • Row 3 (next row down) is shifted to the left by three blocks

Therefore, at the conclusion of this stage, the state is now further obfuscated from the original.

MixColumns

The state produced after the ShiftRows stage is thus passed to the MixColumns stage. In this step, each column is matrix multiplied with a 4×4 circulant (a special type of square matrix in which all row vectors are composed of the same elements and each row vector is rotated one element to the right relative to the preceding row vector) matrix. I don’t propose to go too far into the linear algebra of this step but let’s just suffice it to say that the translation taking place at this stage is limited to remain within a Galois field.

So, the preceding two steps afford the translation with its diffusion as per the Shannon model. Also note that this step is not competed during the final round as it would not add value to the encrypted output at that stage.

AddRoundKey

The final stage is the AddRoundKey stage. In this stage the state is effectively XORed with the round key which is a derived sub key which is generated using a separate algorithm applied to the initial main key.

AES Rijndael (Overview)

So to conclude, examining the entire process in its entirety we have the following:

  1. Initial plaintext block input
  2. Block is XORed with the initial main key
  3. Round 1 begins
    1. R1 SubBytes
    2. R1 ShiftRows
    3. R1 MixColumns
    4. R1 Round key XORed
    5. Round 2 begins
  4. (Rounds repeat until penultimate round concludes)
  5. Final Round SubBytes
  6. Final Round ShiftRows
  7. Final Round key XORed
  8. Ciphertext block complete

Conclusion

To conclude we can summarise that symmetric key algorithms are some of the most robust, secure and widely used algorithms in the cryptography toolbox. Their strengths include convenience and speed and they are used primarily for block encryption of data at rest such as files, directories, volumes and even full disk drives as well as for data in motion such as flow data in transit as streams on browsers for example. The original DES algorithm, although eventually overtaken by technological progress gave rise to a number of extremely secure algorithms one of which is now known as the Advanced Encryption Standard AES.

Comments

Leave a Reply

You must be logged in to post a comment.