Applied Cryptography

Week 3

Exercise Classes:
Thursday 12-14 CAB G56 Friday as usual.
Labs:
CAB H56, H57, HG E19

DES

DES cracking for fun and profit. Can crack it in few hours.

DES has 16 rounds, so we have 16 round keys that are added in the input of function f.

Tripple-DES

Runs DES 3 times.
Most common one uses 2-keys: EDE, Encrypt, decrypt then encrypt again.

3Des
It is 3 times slower.
Double DES does not offer much additional security over single DES.

AES

Started as competition by NIST. Should be as secure and fast as two-key triple DES.
Rijndael won, was chosen as AES in 2000.

Joan Daemen and Vincent Rijmen. Belgians of the year 2000. One of them was also designing the SHA-3 design.

Blocksize: 16 bytes(128 bits), its byte-oriented.

Min key size: 128 bits, also 192 or 256 (needed for quantum computer, because of rovers algorithm, in theory) possible.
Large scale quantum computers don’t exist yet, we are far away from being able to use them to do something interesting in cryptography.

Faster and stronger than DES.

AES is a Substitution-Permutation Network (other than DES or Feistel Cipher). We replace 8 bits at a time with a table lookup and perform a permutation.

AES possible ot implement in hardware, so it gets faster. Even in low-cost, low-power environments such as RFID.

AES structure

Internal state has 16 bytes (p0 - p15).
Uses S-boxes. Small change to input bit leads to large changes in the output.
AES with 128 bits key has 10 rounds. (runs 10 times).
With AES-192 we have 12 rounds and with AES-256 we have 14 rounds.
These rounds are enough such that no attack is more efficient than exhaustive key search.
So if keysize goes up it must be stronger, we get more security by iteration (more rounds).
Round key = Key that is applied in each round of the cipher. Gets XOR’ed in each round.

Because the S-boxes table lookup depends on the key, AES is vulnerable to side channel attacks: cach-time analysis.

Round key: Keys that are used in the block cipher, they are derived from the main key (From a round-key generator). If the cipher has 10 rounds, then the plaintext goes in function f with roundkey1, then the output from that goes again into function f but with roundkey 2, … until we have 10 rounds.

AES SubBytes

Byte-wise substitution.

AES ShiftRows

AES Mix Columns

AES AddRoundKey

ECB mode

What if the message is not a multiple of n bits? With modes of operation such as ECB, CBC, CTR.

ECB

Each block gets encrypted, this can be parallelized. Last block could get padding.

ECB is very rarely the correct mode to use.

ECB information leakage (Adobe used ECB encryption to store passwords as well as a password hint)
ECBADOE
Adobe used the same key for the same database (not crazy if you use a good mode), but they used a bad mode, ECB which encrypts the same plaintext to the same ciphertext.

Another Issue: Encrypting the Pinguin. We can still see it in the ciphertext.

CBC mode

Aims to stop the information leakage of ECB mode. –> uses the prev ciphertext block to randomise the input to the block cipher at each application.
ECB
Decryption:
CBC
Error Propagation:
cbc

If we change a bit in the ciphertext, and D(k) is a good block cipher, then we would expect about half of the bits in p2 to be garbage. Many bits gets messed up. Not every bit (as in picture) but roughly half of the bits.
But we by changing the ciphertext in bit 2 in C(2), we change exactly the 2 bit in P(3). That could be useful in perhaps in padding oracle attacks?

If I would bake 1 bitflip in the IV, then the plaintext P(1) also has 1 bit-flip.

Ciphertext will be at least one block larger than plaintext because the IV (or C(0)) is part of the ciphertext.

If IV are predictable we could attack it. IV needs to be uniformly random.

We need to pad the plaintext so it fits in the CBC mode. Improper handling of padding leads to padding oracle attacks.

CBC mode is problematic if block size (n) is too small. Many encryptions under same key leads to ciphertext block collisions.
These start after 2^(n/2) blocks –> Birthday paradox.
Sweet 32 Attack

CTR mode

Turning a block cipher into a stream cipher. Very similar to a keystream generator and a one-time pad.

CTR

If we modify 1 bit in ciphertext, that leads to 1 bit-flip in the plaintext, exactly the same changes, same as in one-time pad.

Decryption is straightforward, we just generate the mask again, using the counter and the EK and then XOR with ciphertext.

In a client-server connection, and have states, both entities can keep their state of the counter so we don’t have to transmit ctr. But usually we transmit ctr:
C = ctr, C(1), C(2), …, C(l-1)

Never repeat the counter value as input for more than 1 block, else we get the same String that is used in the XOR.

How can we avoid using repeated counter values? How can we avoid being vulerable to p1 XOR p1 == c1 XOR c2 -> Change key for each plaintext (impractical)
-> Use fresh random value for ctr for each plaintext (need good source of randomness)
-> Keep track of the last value of ctr, next ctr is ctr+1 (can be dangerous if we can’t store state after reboot, etc…) -> Concatenate a fixed size per plaintext nonce

The security of CTR mode relies on pseudo-randomness of block cipher.
Counter mode is safe if you have a good block cipher, and never repeat counter.

If we have a PRP as the block cipher, then if we replace the output by truly random permutation, no adversary can tell the difference –> secure.

Formalising Symmetric Encryption

SE = (KGen,Enc,Dec):
KGen: key generation, uniformly at random from {0,1}.
Enc: Encryption, input: K & plaintext,
formal
K = Key space
M = message space
C = ciphertext space

Perfect security: Ciphertext leaks nothing about plaintext (except maybe length)
IND-CPA security: Any adversary A, given the encryption of one of 2 equal-length messages of its choice, A is unable to distinguish which one of the 2 messages was encrypted. (Semantic security)

security
LoR = Left or Right oracle

He can’t say which message in encrypted in the ciphertext c.

The encryption is randomized, the same message multiple times results in different ciphertexts all the time. (Could be counter mode for example)

definition

IND-CPA security captures: