Why is my python aes-ctr-128 micro benchmark with block by block encryption slow?

Question

I designed an puzzle algorithm to take the value of each encrypted block which point to the next block to be encrypted. I have to use aes-ctr-128 for that with some particular reason.

I run a dummy test to see how fast or slow it could be.

Here is what I did. I tested both pycrypto and cryptography.

I first create a 16MB file with random bytes.

I tried in two ways:

Method 1. Load the file into a block list with block size 128bits.

Method 2. Simply load the file into a string.

Now I tested the total time to encrypt each 128-bit block. And I tested the total time to encrypt the whole file.

Here’s the result:

pycrypto:

1. to encrypt 128-bit block one by one: 61,824 aes-ctr-128 per sec

2. to encrypt the entire file: 8,843,713 aes-ctr-128 per sec

cryptography

1. to encrypt 128-bit block one by one: 384,959 aes-ctr-128 per sec

2. to encrypt the entire file: 113,417,922 aes-ctr-128 per sec

I'm wondering why method 1 and 2 gave me the result with so much difference? Are these two methods suppose to give the same speed?

Here's my test code:

import os
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.backends import default_backend
backend = default_backend()

from Crypto.Cipher import AES
from Crypto.Util import Counter
import random
import time

BLOCK_SIZE = 16

def read_block(fname):
    block_list = []
    blobfo = open(fname)
    atEOF = False
    while not atEOF:
        blobdata = blobfo.read(BLOCK_SIZE)
        block_list.append(blobdata)
        if len(blobdata) < BLOCK_SIZE:
        # we should stop after this...
        atEOF = True
    return block_list


print 'loading data'
block_list = read_block('mediumdata')

print 'loading finish'
print len(block_list), 'blocks'

print 'start encryption'
NUM_COUNTER_BITS = 128
# Here I just use a random key
key = os.urandom(16)
t1 = time.time()
for block in block_list:
    ctr = Counter.new(NUM_COUNTER_BITS)
    cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
    cipher.encrypt(block)
t2 = time.time()
print 'finish encryption'

print 'total time:', t2 - t1
print 'time for each aes:', (t2 - t1) / len(block_list)

print 'num of aes per sec:', len(block_list) / (t2 - t1)

print 'now try to encrypt whole file'
block = open('mediumdata').read()
print type(block)
print 'start encryption'
NUM_COUNTER_BITS = 128
key = os.urandom(16)
t1 = time.time()
ctr = Counter.new(NUM_COUNTER_BITS)
cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
cipher.encrypt(block)
t2 = time.time()
print 'finish encryption'

print 'total time:', t2 - t1
print 'time for each aes:', (t2 - t1) / len(block_list)

print 'num of aes per sec:', len(block_list) / (t2 - t1)


print 'now try cryptography'

print 'start encryption'
t1 = time.time()
num = random.randint(1, 65530)
nonce = "".join(chr((num >> (i * 8)) & 0xFF) for i in range(16))
backend = default_backend()
cipher = Cipher(algorithms.AES(key), modes.CTR(nonce), backend=backend)
encryptor = cipher.encryptor()
for block in block_list:
    ciphertext = encryptor.update(block)
encryptor.finalize()
t2 = time.time()
print 'finish encryption'

print 'total time:', t2 - t1
print 'time for each aes:', (t2 - t1) / len(block_list)

print 'num of aes per sec:', len(block_list) / (t2 - t1)

print 'try a whole file'

block = open('mediumdata').read()

print 'start encryption'
t1 = time.time()
num = random.randint(1, 65530)
nonce = "".join(chr((num >> (i * 8)) & 0xFF) for i in range(16))
backend = default_backend()
cipher = Cipher(algorithms.AES(key), modes.CTR(nonce), backend=backend)
encryptor = cipher.encryptor()
ciphertext = encryptor.update(block)# + encryptor.finalize()
encryptor.finalize()
t2 = time.time()
print 'finish encryption'


print 'total time:', t2 - t1
print 'time for each aes:', (t2 - t1) / len(block_list)

print 'num of aes per sec:', len(block_list) / (t2 - t1)

Did I miss anything here?

Is there a way that I can make method 1 faster?

Answer 1

AES is a block cipher with multiple permutation rounds. Each round has it's own round key, which needs to be derived from "master" key (key in your code). Calling AES.new(key, mode, ...) will automatically derive the round keys, but this key schedule process is quite heavy. Doing the key schedule for every block will slow down the processing considerably considerably compared to the one-call approach, especially if the actual encryption code uses the AES-NI instruction set.

Additionally, as kennytm points out in the comments, Python is an interpreted language, so iterating over the blocks in Python instead of the underlying native crypto code (e.g. pyCrypto uses the C library tomcrypt) will necessarily incur an additional performance penalty.

---

The code for Method 1 is broken, because you're creating a new Counter object for each block, which is always initialized to 1. Thus, you're XORing every block with the same key stream, which creates a many-time pad and likely enables an attacker to deduce the plaintext.

We can fix this by only having a single Counter object. Having also a single key schedule considerably increases the performance.

Improved Method 1 code:

ctr = Counter.new(NUM_COUNTER_BITS)
cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
for block in block_list:
    cipher.encrypt(block)

Results for pyCrypto:

1049887 blocks

Method 1
total time: 17.31999993324279785156
time for each aes: 1.64970134245e-05
num of aes per sec: 60617.0325662

Improved Method 1
total time: 0.78299999237060546875
time for each aes: 7.45794540146e-07
num of aes per sec: 1340851.86492

Method 2
total time: 0.147000074387
time for each aes: 1.4001513914e-07
num of aes per sec: 7142084.82126

Full code