AES encryption takes more time to decrypt than encrypt

Question

I am trying to find how much time an AES encryption and decryption takes for a given amount of data and key. In all the cases encryption takes way lesser processing time than decryption. I tried to get this answer somewhere else but can't find. May I know why does decryption takes a lot more time than encryption for AES 128/256 bit?

I am trying to implement a simple AES encryption in Arduino UNO. I use micros() to measure the time it takes to encrypt or decrypt.

Here is what I did for encryption:

Serial.print("Encrypted: ");
unsigned long start1 = micros();
String enc = aes_encrypt("this is data source","this is key");
Serial.println(enc);
unsigned long start2 = micros();
unsigned long diff1 = start2 - start1;
Serial.print("Time to encrypt the data: ");
Serial.print(diff1);
Serial.println(" microseconds");

Answer 1

As the commenters have said, it is impossible to answer without many more details about your particular implementation, but here is some background on Rijndael (pronounced 'rain-doll') that might help. Rijndael is the family of ciphers on which AES is based. AES is defined as Rijndael[1] with a block size of 128 bits and key lengths of 128, 192 and 256 bits.

Back in 1999, when the winner of the AES had not been chosen yet, Bruce Schneier published a paper[2] on performance of the proposed ciphers. The Pentium Pro CPU was a high end processor back then. On page seven of his report he states:

Rijndael is another variant of Square: a fast cipher that works very well across all platforms. It boasts a clean mathematical structure involving only table lookup and XOR operations. Although the encryption and decryption algorithms are not exactly identical, their general structure and performance are virtually indistinguishable.

Rijndael’s assembly language on both the Pentium and Pentium Pro processors is about 300 clocks per block. Unlike RC6 and Mars, there are no known CPU platforms (8-bit or 32-bit) on which Rijndael’s relative performance would be unduly negatively affected or on which timing attacks would be possible.

According to this, one of the algorithm's advantages is its resistance to timing attacks. This would definitely have been a factor in the decision to select Rijndael as the current AES.

Later, though, discussing performance on 8-bit smart cards, which I read as computing platforms with very restricted resources, he says about Rijndael:

Perhaps the only negative comment about Rijndael on smart cards is that the performance numbers in the paper do not include a decryption function. Including decryption would increase the code size somewhat (probably between 512 and 1024 bytes), and decryption speed would be slower (possibly twice as slow) than encryption speed due to the coefficients of the inverse MDS matrix.

Again, without details about your implementation, it is impossible to know what the cause of the discrepancy is. There is strong evidence pointing to the fact that encryption and decryption for a given key should take about the same time, but the Arduino UNO has an 8-bit RISC processor and even though it has 2K of memory, it can only consume it 8 bits at a time. You could be experiencing the same theoretical problem Schneier described.

[1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard - Check the section called Description of the cipher.

[2] https://www.schneier.com/paper-aes-performance.pdf

Answer 2

AES is asymmetrical in this regard. It is down to the key schedule, which generates a sequence of round keys from an initial key. In a modern desktop environment, the round key sequence is simply generated before encryption/decryption starts, so the difference in speed is minimal.

In a memory-constrained environment like a smartcard, this may not be possible, and the round keys have to be generated on the fly. But for decryption, the final round key is the first to be used, and generating this final round key requires generating all the intermediate round keys (which are not used). Then the round keys have to be generated again in reverse order, as the algorithm progresses.

This was a deliberate design decision - MACs only need the encryption primitive, and even some encryption/decryption algorithms (CTR, EAX) only use the encryption primitive of the underlying block cipher. So the Rijndael algorithm was optimised for encryption speed over decryption speed.

Answer 3

I just noticed that you take the time for encryption and sending the result over a serial line. Serial line transmission is - I guess - significantly slower than AES operations on the Arduino.

Your calls to micros() should be as close to aes_encrypt() as possible, otherwise the measurement is falsified.

If the size of the data sent over the serial line is different for encryption or decryption, this would explain your measurements.