Saturday, January 29, 2011

Modes of Operation


After explaining the basis of how the AES block cipher works now we’re moving into modes of operations. Basically, a block cipher by itself allows encrypting only a data block of the cipher's block length (in AES 128 bits). Although it might happen that the plaintext to be encrypted has exactly 128 bits, this is not always the case and the plaintext normally exceeds by far 128 bits. As plaintexts can be of any length they have to be broken into blocks before the encryption process takes place.

The National Institute for Standards and Technology has defined five confidentiality modes of operation for the AES block cipher, with different characteristics. The modes of operation defined for AES are ECB (Electronic Code Book), CBC (Cipher Block Chaining), CFB (Cipher FeedBack), OFB (Output FeedBack), and CTR (Counter).

Since the idea of these posts is to demonstrate the benefits of running AES in parallel I will explain only ECB and CTR modes of operations, which are the ones that might benefit the most when running in parallel due to the lack of dependencies between the data blocks they encrypt; being like that ideal candidates to be implemented on parallel processors such as a Graphic Processing Unit or GPU (we’ll come back to that later..).

Electronic Code Book

ECB is one of the simplest modes of operations. To encrypt a plaintext the forward AES cipher function is applied. The plaintext is divided into blocks each of which is, encrypted independently using a key. In ECB decryption, the inverse cipher function is as well applied directly and independently to each block of ciphertext.


One important consideration is the fact that in ECB if a similar data pattern exists and the same key is used, then the plain text will generate the same cipher text (as would happen when enciphering a file with repeated 16 bytes blocks), which is a major leak of secret information and can be exploited by cryptanalytic attacks. In the next picture it can be seen the pattern that ECB exposes when encrypting an image, this was mainly the reason why other modes of operation were designed, among them CTR. If this property is not desired, this mode of operation should not be considered.



Counter CTR

One way to hide data patterns is to provide some randomization for each block. All the modes of operation apart from ECB require an initialization vector (IV). The IV is used to provide a unique cipher text if the same key is re-used. In CTR a set of input blocks called counters are encrypted using the key, producing output blocks called keystreams, which are used to perform an XOR operation with the plaintext blocks. The sequence of counters must have the property that each block in the sequence is different than the rest, in other words all counters must be distinct. In CTR encryption, the block cipher encryption function is called on each counter block. Afterwards, the resulting output is XORed with the respective plaintext block to generate the ciphertext. While decrypting, the block cipher encryption function is invoked on each counter block. The resulting output will be then XORed with the respective ciphertext block in order to recover the plaintext block.

Summary

In these first three posts I cover the very basis of AES and modes of operations, which for our purposes are going to be enough to start with our first coding examples. Let’s make a small review!!

A brief historical remark about the Advanced Encryption Standard, followed by an overview of its functionality was provided. It was explained how input data is mapped to an intermediate matrix called the state in where all AES operations are going to take place; as well as how the state maps to the output array. The four steps contained on the AES rounds: AddRoundKey, SubBytes, ShiftRows and MixColumns were explained. The amount of rounds strongly depends on the key length and in order to compute them it is necessary to expand the key; the process of expanding the key was exemplified as well. Moreover, modes of encryption were introduced and two parallel in nature modes of operations named ECB and CTR were covered.

The first AES examples I will be presenting soon are going to run on the CPU; we’re going to create a C program that makes usage of the OpenSSL library which is the most common used cryptographic framework. The idea is to create a (hopefully short!) tutorial of how to implement AES using OpenSSL which it is kind of painful due to the lack of documentation on the web.

Thursday, January 27, 2011

Berlin You are AWESOME!

Since a long time ago I wanted to go to Berlin, but for some reason every time I found some spare time I used to end up going to a different city. Finally a few weeks ago Amanda and I decided to go and, I have to say it did not disappoint me at all. It totally fulfilled my expectations (which in my case normally that never happens when I expect alot about something.. so extra points for that!!) the whole city gives the feeling of being walking through an open roof museum, specially about topics related to WWII. In every corner there’s something that reminds Berliners all the suffering and pain that their citizens have to go through back in the time. On the other hand it really amazed me how Germans built their country back again after being totally devastated. Another thing that took my attention was being for the first time in a big German city. In Germany, cities usually are not that big, I can think about Hamburg, Munich and Berlin itself but definitely nothing compared with other big cities around the world like New York, Mexico City or London. However, after having visited mid size German cities (which are amazing too!!) Berlin really remind me what being in a big city feels like, with a complex subway system, amazing contemporary architecture, people asking for a coin in the train after signing a tune, business men rushing on the streets, tons of nightlife, and much more..

Overall I really loved Berlin and I cannot really wait to go back again. This time I would love to go during the summer, and get to know some other side of the city I couldn’t see; like its night life and some of its urban art galleries. The monument I liked the most was the Brandenburg Gate it is really amazing all the significant events that took place there and having been there here’s a night shot of it!!!