PyCrypto problem using AES+CTR

Question

I'm writing a piece of code to encrypt a text using symmetric encryption. But it's not coming back with the right result...

from Crypto.Cipher import AES
import os

crypto = AES.new(os.urandom(32), AES.MODE_CTR, counter = lambda : os.urandom(16))
encrypted = crypto.encrypt("aaaaaaaaaaaaaaaa")
print crypto.decrypt(encrypted)

Here, the decrypted text is different from the original.

I don't really understand much about cryptography so please bear with me. I understand the CTR mode requires a "counter" function to supply a random counter each time, but why does it need it to be 16 bytes when my key is 32 bytes and it insists that my message is in multiples of 16 bytes too? Is this normal?

I'm guessing that it doesn't get back to the original message because the counter changed between encrypt and decrypt. But then, how is it supposed to work theoretically anyway? What am I doing wrong? Anyway, I'm forced to resort back to ECB until I figure this out :(

Solution 1

The counter must return the same on decryption as it did on encryption, as you intuit, so, one (NOT SECURE AT ALL) way to do it is:

>>> secret = os.urandom(16)
>>> crypto = AES.new(os.urandom(32), AES.MODE_CTR, counter=lambda: secret)
>>> encrypted = crypto.encrypt("aaaaaaaaaaaaaaaa")
>>> print crypto.decrypt(encrypted)
aaaaaaaaaaaaaaaa

CTR is a block cipher, so the "16-at-a-time" constraint that seems to surprise you is a pretty natural one.

Of course, a so-called "counter" returning the same value at each call is grossly insecure. Doesn't take much to do better, e.g....:

import array

class Secret(object):
  def __init__(self, secret=None):
    if secret is None: secret = os.urandom(16)
    self.secret = secret
    self.reset()
  def counter(self):
    for i, c in enumerate(self.current):
      self.current[i] = c + 1
      if self.current: break
    return self.current.tostring()
  def reset(self):
    self.current = array.array('B', self.secret)

secret = Secret()
crypto = AES.new(os.urandom(32), AES.MODE_CTR, counter=secret.counter)
encrypted = crypto.encrypt(16*'a' + 16*'b' + 16*'c')
secret.reset()
print crypto.decrypt(encrypted)

Solution 2

AES is a block cipher: it's an algorithm (more precisely, a pair of algorithms) that takes a key and a message block and either encrypts or decrypts the block. The size of a block is always 16 bytes, regardless of the key size.

CTR is a mode of operation. It's a pair of algorithms that builds on a block cipher to produce a stream cipher, which can encrypt and decrypt messages of arbitrary lengths.

CTR works by combining successive message blocks with the encryption of successive values of a counter. The size of the counter needs to be one block so that it's valid input for the block cipher.

• Functionally, it doesn't matter what the successive values of the counter are, as long as the encryption and decryption side use the same sequence. Usually the counter is treated as a 256-bit number and incremented for each successive block, with an initial value chosen at random. Thus, usually, the incrementation method is baked into the code, but the decryption side needs to know what the initial value is, so encryption side sends or stores the initial counter value at the beginning of the encrypted message.
• For security, it is vital to never repeat the same counter value with a given key. So for a single-use key, it's ok to start with '\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'. But if the key is used multiple times then the second message is not allowed to reuse any of the counter values used by the first message, and the easiest way to ensure that is to generate the initial counter value at random (with a 2^128 space, the chances of a collision are acceptably negligible).

By letting the caller pick a counter function, the PyCrypto library gives you plenty of rope to hang yourself. You should use Crypto.Util.Counter, not just “for better performance” as the documentation puts it, but because it's easier to build something secure than what you're likely to come up with on your own. And even so, take care to use a random initial value, which is not the default.

import binascii
import os
from Crypto.Cipher import AES
from Crypto.Util import Counter
def int_of_string(s):
    return int(binascii.hexlify(s), 16)
def encrypt_message(key, plaintext):
    iv = os.urandom(16)
    ctr = Counter.new(128, initial_value=int_of_string(iv))
    aes = AES.new(key, AES.MODE_CTR, counter=ctr)
    return iv + aes.encrypt(plaintext)
def decrypt_message(key, ciphertext):
    iv = ciphertext[:16]
    ctr = Counter.new(128, initial_value=int_of_string(iv))
    aes = AES.new(key, AES.MODE_CTR, counter=ctr)
    return aes.decrypt(ciphertext[16:])

Solution 3

why does it need it to be 16 bytes when my key is 32 bytes

It has to be the same length as the cipher's block size. CTR mode just encrypts the counter and XORs the plaintext with the encrypted counter block.

Notes:

1. the counter value MUST be unique -- if you EVER use the same counter value to encrypt two different plaintexts under the same key, you just gave away your key.
2. like an IV, the counter is NOT secret -- just send it along with the ciphertext. If you make the code more complicated by trying to keep it secret, you will probably shoot yourself in the foot.
3. the counter value need not be unpredictable -- starting with zero and adding one for each block is perfectly fine. But note that if you encrypt multiple messages, you need to keep track of the counter values that have already been consumed, i.e. you need to keep track of how many blocks have already been encrypted with that key (and you can't use the same key in different instances of your program or on different machines).
4. the plain text can be any length -- CTR mode turns a block cipher into a stream cipher.

Standard disclaimer: Crypto is hard. If you don't understand what you are doing, you will get it wrong.

I just want to store some passwords across sessions.

Use scrypt. scrypt includes encrypt and decrypt which use AES-CTR with a password-derived key.

$ pip install scrypt

$ python
>>> import scrypt
>>> import getpass
>>> pw = getpass.getpass("enter password:")
enter password:
>>> encrypted = scrypt.encrypt("Guido is a space alien.",pw)
>>> out = scrypt.decrypt(encrypted,pw)
>>> out
'Guido is a space alien.'

Solution 4

I may be definitely late and I may have overlooked the previous answers, but I didn't find a clear statement of how this should (at least IMHO) be done according with the PyCrypto packages.

The Crypto.Util.Counter package provides callable stateful counters, which are very useful, but it was easy at least for me to use them improperly.

You have to create a counter, with e.g. ctr = Counter.new('parameters here'). Every time your counter is called by your counter mode cipher object to encrypt the message, it is incremented. This is needed for good cryptography practices, otherwise information about equal blocks may leak from the ciphertext.

Now you cannot call the decryption function on the same cipher object, because it would call again the same counter which in the meanwhile has been incremented, possibly several times. What you need to do is to create a new cipher object with a different counter initialized with the same parameters. In this way the decryption works properly, starting the counter from the same point as the encryption was done.

Working example below:

# Import modules
from Crypto.Cipher import AES
from Crypto import Random
from Crypto.Util import Counter


# Pad for short keys
pad = '# constant pad for short keys ##'

# Generate a random initialization vector, to be used by both encryptor and decryptor
# This may be sent in clear in a real communication

random_generator = Random.new()
IV = random_generator.read(8)


# Encryption steps

# Ask user for input and pad or truncate to a 32 bytes (256 bits) key
prompt = 'Input your key. It will padded or truncated at 32 bytes (256 bits).\n-: '
user_keye = raw_input(prompt)
keye = (user_keye + pad)[:32]

# Create counter for encryptor
ctr_e = Counter.new(64, prefix=IV)

# Create encryptor, ask for plaintext to encrypt, then encrypt and print ciphertext
encryptor = AES.new(keye, AES.MODE_CTR, counter=ctr_e)
plaintext = raw_input('Enter message to cipher: ')
ciphertext = encryptor.encrypt(plaintext)
print ciphertext
print


# Decryption steps

# Ask user for key: it must be equal to that used for encryption
prompt = 'Input your key. It will padded or truncated at 32 bytes (256 bits).\n-: '
user_keyd = raw_input(prompt)
keyd = (user_keyd + pad)[:32]

# Create counter for decryptor: it is equal to the encryptor, but restarts from the beginning

ctr_d = Counter.new(64, prefix=IV)

# Create decryptor, then decrypt and print decoded text
decryptor = AES.new(keyd, AES.MODE_CTR, counter=ctr_d)
decoded_text = decryptor.decrypt(ciphertext)
print decoded_text

Solution 5

The initialization vector ("counter") needs to stay the same, just as the key does, between encryption and decryption. It is used so that you can encode the same text a million times, and get different ciphertext each time (preventing some known plaintext attacks and pattern matching / attacks). You still need to use the same IV when decrypting as when encrypting. Usually when you start decrypting a stream, you initialize the IV to the same value that you started with when you started encrypting that stream.

See http://en.wikipedia.org/wiki/Initialization_vector for info on initialization vectors.

Note that os.urandom(16) is not 'deterministic', which is a requirement for counter functions. I suggest you use the increment function, as that is how CTR mode is designed. The initial counter value should be random, but the successive values should be fully predictable from the initial value (deterministic). The initial value may even be taken care of for you (I don't know the details)

About the key, IV, and input sizes, it sounds like the cipher you chose has a block size of 16 bytes. Everything you describe fits that and seems normal to me.

View more solutions

Comments

[xster]

awesome. ok, I get it. so essentially, CTR has no advantage over ECB if I just want to encrypt one or very few things? I just want to store some passwords across sessions. Do I even need AES or should I be using something more simple?

[Jack Lloyd]

Actually CTR can encrypt any arbitrary amount of text; it converts a block cipher into a key stream generator. There is no actual reason for the restriction that the input be multiples of a block size in this case.

[xster]

PyCrypto seems to give an error when the input is not a multiple of 16 bytes however

[Alex Martelli]

Yep, so you just need to pad the input (to the next closest multiple of 16) if you want to use pycrypto.

[xster]

but if I use AES to encrypt passwords across sessions, I'd have to save the counter somewhere too in order to decrypt the next time I run it? Doesn't that defeat the security of having random counters?

[Matt Billenstein]

Hey Alex, the loop in the counter function is a off I think, shouldn't it be more like: paste.pocoo.org/show/516351

[curious]

@AlexMartelli I did the same as the first block of data but i am getting giberish data while decrypting without errors from ypthon interpreter. I am using instead Crypto.Random for random bytes generation. What am i missing?

[Nandhini]

@AlexMartelli wouldn't counter overlflow soon, or at-least after 255 blocks if you started with counter 0

[Gilles 'SO- stop being evil']

Your first snippet has been featured as a capture-the-flag, with a rating of 1 (easiest). I don't understand what you're doing with the second snippet, it doesn't even work (Secret('\xff\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x0‌​0\x00\x00\x00').coun‌​ter() → OverflowError: unsigned byte integer is greater than maximum.

[Gilles 'SO- stop being evil']

Also CTR is not a block cipher. It's a mode that uses a block cipher to build a stream cipher.

[Alexandre Blin]

int_of_string(iv) can be replaced with int.from_bytes(iv, byteorder='big') in Python 3