Using Block Ciphers
As discussed in Cryptography: Week Two
A PRF is secure if a random function in the set of all functions from X to Y is indistinguishable from a random function in the set of functions that fix the key and yield the same output in Y.
We’re going to assume AES and 3DES are secure PRPs, and see how to use them.
One Time Key
Let’s see how to securely encrypt a piece of information using a block cipher.
Our goal is to build secure encyrption from a secure PRP (eg AES).
First we’ll take the one-time key example. Here all the attacker sees is one cipher text. And their goal is to learn info about the plain text from the cipher text.
We’ll start with an incorrect method. Don’t do this!
The method is called Electronic Code Book (ECB).
Here we take our plain text, we break it into blocks, and then we encrypt each block separately using our key. Like this:
Note that if the two plain text blocks are equal, so is the cipher text. So the attacker will know that they are equal.
How do we use block ciphers to encrypt long messages then?
One method is a deterministic counter mode from a PRF F:
We build a stream cipher from a PRF.
Many Time Key
Example applications: File systems (same AES key to encrypt many files), network (same key many packets).
Here the attacker gets to encrypt arbitrary messages of his choice. This is common in real life.
Note that all the methods so far are insecure under this test. If the algorithm always outputs the same ciphertext for message m, then it cannot be secure under the chosen message attack.
This is CPA security - chosen plaintext attack. A deterministic encryption algorithm cannot be secure under a CPA.
So if a secret key is to be used multiple times, then given the same plaintext twice, it must produce different outputs.
Solution 1: randomized encryption
Here the algorithm itself chooses a random string in the encryption process. It will encrypt the message with that random string.
Now a message will not be mapped to 1 cipher text, but to a whole set of cipher texts, where on any instance of encryption we output one member of the set.
Now if we encrypt the same message twice we’ll get different cipher texts with high probability.
The ciphertext must be longer than the plain text, roughtly CT-size is PT-size + number of random bits.
The cost here is the extra bits, particularly if messages are small. Otherwise it’s a fine solution.
Solution 2: nonce-based encryption
Here the encryption algorithm takes three inputs, the key, the message and a nonce, a value that changes from message to message. They key/nonce pair is never used more than once.
Note the nonce can be public. The only criteria is that it is not repeated with the same key. It also need not be random, it’s just got to be unique.
A nonce in crypto means a unique value, it does not have to be random.
How to choose a nonce?
Method one: A counter. (eg packet counter). Used when encryptor keeps state from message to message. If decryptor has the same state, need not send the nonce with the cipher text.
Method two: Choose a random nonce, assuming the nonce space is large enough that it will never repeat. At this point nonce encryption reduces to randomized encryption. Now we don’t have to preserve state. Useful, for example in multi-device settings, where stateless encryption is important as it would be a pain to guarantee uniqueness across multiple devices.
In nonce-based encryption it’s important that it be secure when the adversary chooses the nonce.
Cipher Block Chaining
IV stands for Initialization Vector. We choose a random value from the block space. That is XORed with the first message block, then encrypted, then that chains into the next block and so on.
The IV is included in the cipher text, so the cipher text is a little longer than the message.
An attack is when the IV is predictable. So the IV has to be unpredictable. SSL/TLS1.1 the IV for record i is the CT block of record i-1. This can be converted into an attack on SSL.
The IV must be random.
Here is a nonce-based CBC approach:
Note the extra encryption step for the nonce where it is not random. This is a very common mistake. The nonce must be encrypted. Since otherwise it would be preditable.
Many APIs are misleading here, have the user pass the IV, but if this is not random or encrypted the result won’t be secure.
Aside - if the final block is shorter than the block size we pad it. If no pad needed, add a dummy block.
Decryptor looks at the value of the last byte and removes that number of bytes from the end of the message (hence need for dummy block).
Randomized Counter Mode
Unlike CBC, this method uses a secure PRF, F is not inverted.
Here we choose a random IV for every message, and then the encryption is based on IV incrementing for each block.
There is also a nonce variant:
Here we have to only encrypt \(2^{64}\) blocks with the same nonce.
CTR replacing CBC. It doesn’t need a block cipher, we can run it in parallel.