Symmetric Cryptography - Topic 3

Question 1

What is cryptography?

Answer 1

Cryptography is the “art of keeping messages secure” by Schneier

Question 2

What services can cryptography provide?

Answer 2

Confidentiality - (secrecy, privacy) of data in transmission & in storage

Integrity of Data (data authentication/authenticity) in transit & storage

Authentication of an identity (entity authentication)

Credential Systems (a proof of qualification or competence of a person)

Digital signatures

Electronic money (e.g. cryptocurrency Bitcoins)

Threshold cryptosystems
- A decryption key, or a signature signing key, is shared among a group of entities and a subset of those entities (more than some threshold number) have to collaborate to perform the decryption or signature signing

Secure multi-party computations (e.g. multiple parties compute a function jointly, the input is from the multiple parties, but no party should learn anything rather than its own input and the final result of the computation)

Digital rights management (e.g. activation of a software license by authorized users)

Electronic voting

Question 3

What type of cipher uses the same key

Answer 3

Symmetric ciphers: block and stream ciphers, e.g. DES, AES, one-time pad; same key is used.

Question 4

What type of ciphers use different keys?

Answer 4

Asymmetric ciphers: RSA, DSA and DH; different keys are used.

Question 5

What are SHA256 and AES-CBC examples of?

Answer 5

Hash and MACing functions

Question 6

List some cryptographic modes of encryption

Answer 6

CBC (cipher block chaining) mode, CTR (counter) mode

Question 7

Describe block ciphers

Answer 7

Plaintext is divided into blocks of fixed length and blocks are encrypted one at a time.

In addition to a key generation function, a block cipher has two functions, any encryption function E and a decryption function, D, such that:

C = E(K, M)
M = D(K,C)

Where C is ciphertext, M is plaintext and K is a secret (symmetric or a private key)

Question 8

What are the design criteria for block ciphers?

Answer 8

Completeness
Each bit of the output should depend on every bit of the input and every bit of the key

Avalanche effect (diffusion)
Changing one bit in the message input should change many bits in the output.
Also, changing one bit in the key should result in the change of many bits in the output

Statistical independence (confusion)
Input and output should appear to be statistically independent

Question 9

Can confusion and diffusion be achieved using substitution and permutation?

Answer 9

Yes

Question 10

What is the round function in a block cipher?

Answer 10

Typically uses permutations, substitutions, modular arithmetic

Takes an n-bit block and outputs an n-bit block

Each use of the round function employs a different subkey derived from K

Question 11

What comes from a larger block size in a block cipher? What are its typical values?

Answer 11

Greater security but makes encryption/decryption slower; typically n is 128-bit or 256-bit

Question 12

What is the effect of the key size in a block cipher? What are its typical values?

Answer 12

Larger keys size means greater security but reduced speed; a 128-bit size has become a norm

Question 13

What is the DES (data encryption standard)? When was it published? What kind of cipher is it?

Answer 13

Published in 1977, DES is a feistel (fancy block) cipher.
Block length is 64 bits, Key K is 56 bits; actually 8 bytes (64bits) but the 8th bit in each byte is a parity-check bit

The subkeys k1,k2,k3,…,k16 are each 48-bits, generated from key K

The DES decryption algorithm is the same as the encryption one; the only difference is that the keys for each round must be used in the reverse order, i.e. k16 first and k1 last

Question 14

What industry is DES the defacto industry standard for?

Answer 14

The bank industry

Question 15

Name some improvements over DES

Answer 15

Triple DES, AES

Question 16

What are the weaknesses of DES?

Answer 16

Design principles are secret, developed by US government so there might be a backdoor.

56 bit key is good enough to deter casual DES key browsing, but not for a dedicated adversary.

Takes an average of 2^55 trials to crack, supercomputer/botnet can do 10^12 a second

Question 17

What is triple DES?

Answer 17

Use of two or three DES keys.

EDE2 uses two DES keys (K1, K2) and the equation C = E(K1, D(K2, E(K1, M)))

EDE3 uses three DES keys (K1, K2) and the equation C = E(K3, D(K2, E(K1, M)))

The use of D has no security implication, it just makes Triple DES compatible with normal DES when K1 = K2 (this generalises to make EDE3 = EDE2 = normal DES, with certain keys being equal)

Question 18

What attack makes the effective key lengths for EDE2 and EDE3 much shorter?

Answer 18

The meet-in-the-middle attack

Question 19

What is the meet-in-the-middle attack?

Answer 19

With the Meet-in-the-Middle attack, the attacker first computes EK1(M) for all values of K1
and DK2(C) for all possible values of K2. He then compares the results from the two sets. If
the result from any of the EK1(M) set matches with a result from the DK2(C) set, the pair of
K1 and K2 is probably the correct keys.

Question 20

What were the conditions set by the US NIST call for algorithms to replace DES?

Answer 20

Stronger and faster than 3DES
Active life of 20-30 years (+ archival use)
Provide full specification & design details
Both C & Java efficient implementations

Question 21

What is the name of the AES standard

Answer 21

Advanced Encryption Standard (AES)

Rijndael

Question 22

What is the block size of AES

Answer 22

128 bits

Question 23

What are the possible key lengths of AES?

Answer 23

128, 192 or 256 bits, standard comprises three block ciphers AES-128, AES-192 and AES-256

Question 24

What type of cipher is DES

Answer 24

It is an iterative symmetric block cipher

Also a substitution - permutation cipher involving r rounds

Question 25

What are the r (rounds) value for the different key lengths in AES?

Answer 25

Key length - 128 bits, r = 10
Key length - 192 bits, r = 12
Key length - 256 bits, r = 14

Question 26

What does AES operate on to make it’s software implementation more efficient?

Answer 26

Operates on whole bytes for each round.

fixed block size of 128 bits (16 bytes) called a state

Question 27

What does each round transformation consist of in AES encryption?

Answer 27

Substitute bytes (SubBytes)
Shift rows (ShiftRows)
Mix columns (MixColumns)
Add round key (AddRoundKey)

Question 28

What is the SubBytes transformation?

Answer 28

Substitute Byes
A simple table/S-box lookup

One S-box for the whole cipher (defined / fixed in software), a 16x16 matrix of byte values, that contains a permutation of all possible 256 8-bit values

Each byte is replaced by a new byte indexed by row (left 4 bits) and column (right 4 bits) of the S-box

Question 29

What is the ShiftRows transformation?

Answer 29

A simple permutation (circular byte shift)
1st row: no change
2nd row: 1-byte circular left shift
3rd row: 2byte circular left shift
4th row: 3-byte circular left shift

Decryption uses circular right shift

This step permutes bytes between the columns

Question 30

Explain modular polynomial arithmetic

Answer 30

This is more of a TODO, go checkout the slides

Question 31

What is p, n and m for AES modular polynomial arithmetic?

Answer 31

p = 8, n = 2, m(x) = {100011011} or {11B}

Question 32

With Arithmetic in the finite field GF(2^8) with m(x) = (x^8+x^4+x^3+x+1) what is {03}*{6E}

Answer 32

{1011 0010}

Question 33

What is the AES mix columns function?

Answer 33

A function of all four bytes in the column; effectively a matrix multiplication in GF(2^8) using irreducible polynomial m(x) = x^8 + x^4 + x^3 + x + 1 (or {11B})

Question 34

Describe the Add Round Key stage of AES

Answer 34

Each byte of the state is combined with the round key using XOR, i.e. the 128 bits of state are bitwise XORed with the 128 bits of the round key.

The round key is derived from the cipher key using a key schedule

Question 35

If the input to AES has one difference what is the effect on the cipher text

Answer 35

A completely different cipher text is produced

Question 36

What are the main differences between DES and AES

Answer 36

Block size: 128 bit for AES, 64 bit for DES
Key Size: 56 bit for DES, 128, 192, 256 bit for AES
Design and evaluation process: DES closed, AES open

8 different S-boxes, 1 S-box

Design optimisation: DES for optimised hardware implementations, AES for byte-oriented implementations

DES and AES are substitution-permutation iterated ciphers, DES has a feistel structure AES does not

Question 37

How does one-time pad encrypt bit streams?

Answer 37

Using XOR
M xor K = C
C xor K = M

Question 38

Under what conditions does the one-time pad achieve perfect secrecy

Answer 38

If an only if there are as many possible keys as possible plaintexts, and every key is equally likely

Question 39

Benefits and problems with one-time pad stream ciphers

Answer 39

Benefit:
Bitwise xor is very computationally efficient

Problems:
Keys must be as long as the plaintext, this is impractical in most application scenarios.

Not secure if keys are reused.
Attacked can obtain XOR of plain-texts:
- M1 xor K = C1, M2 xor K = C2 and M1 xor M2 = C1 xor C2

If attacker gets hold of {M1, C1}, then K = M1 xor C1

Question 40

How can we encrypt large messages using a one-time pad stream cipher

Answer 40

Replace the random key in one-time pad with a pseudo-random sequence, generated by a cryptographic pseudo-random generator that is ‘seeded’ with the key.

There is still a possibility of the key being repeated

Question 41

What three modes can be used to encrypt messages longer than a block size?

Answer 41

ECB - Electronic code book mode
CBC - Cipher block chaining mode
CTR - Counter mode

Question 42

Describe ECB (Electronic Code Book) mode

Answer 42

Each block is encrypted independently using the same key. The last block is padded if necessary. Usually the last byte indicates the number of padding bytes added; this allows the received to remove the padding

Blocks are encrypted independently of other blocks
- Reordering ciphertext block results in correspondingly reordered plaintext blocks

The same block of plaintext, with the same key produces the same ciphertext so patters in plaintext show up in ciphertext

Error propagation: errors in one ciphertext block only affects the same plaintext block; they do no propagate to other blocks.

Not recommended for messages longer than one block of data.

Question 43

Describe CBC (Cipher Block Chaining) mode

Answer 43

Equation for encryption: Ci = E(K, M XOR Ci-1) where C0 = IV (Initialization vector)

See example in the slides

Ciphertext block Cj depends on plaintext Mj and all the preceding plaintext blocks.
- Reordering effects decryption
- Repeated patterns are concealed by the feedback
- There is error propogation

IV should be randomly selected but does not have to be secret.

Using different IVs in different encryption operations will make the same plaintext encrypted to different ciphertexts

Question 44

Describe CTR (Counter) Mode

Answer 44

Use a block cipher encryption function as the pseudorandom number generator to generate the key stream.

A counter value, equal to the block size, is used. For each encryption operation the value is different.

Typically the counter is initialised to some value, and then incremented by 1 for each subsequent block (modulo 2^n, where n is the block length)

CTR mode actually converts a block cipher to a stream cipher
Each block can be decrypted independently of the others
- Parallelizable
- Support random access
- The values to be XORed with the plaintext can be pre-computed.

The counter needs to be synchronised
- If a block is inserted into or deleted from the ciphertext stream then synchronization is lost and the plaintext cannot be recovered.

No error propagation
- A ciphertext block that is modified during transmission affects only the decryption of that block

In CTR mode the decryption function is not needed, since the stream cipher generates a new key with encrypt, that can then be used symmetrically

Question 45

Block ciphers vs Stream ciphers

Answer 45

Block ciphers encrypt blocks of characters, stream ciphers encrypt individual characters or bit streams.

Stream ciphers
- usually faster in hardware; mostly used for continuous communications and/or real-time applications.
- Require less memory space, so cheaper for resource restrained devices such as embedded sensors.
- Have limited or no error propagation, so advantageous when transmission errors are probably.
- Can be built out of block ciphers, e.g. by using CTR modes.

Question 46

What are some implementation flaws in ciphers

Answer 46

Use a secure random function from a crypto library.
- C’s rand should not be used for security applications.

IVs should be random
- Using NULL as IV is a vulnerability