Unit 2: Symmetric Cryptography

Question 1

Eavesdropping

Answer 1

a passive attack, just listening

Question 2

Manipulation/Corruption

Answer 2

an attacker is actively involved; stops message, changes/replaces the message, so that when the recipient gets it, it’s not the right message

Question 3

Interception

Answer 3

attacker stops the message from getting to the recipient; crypt doesn’t prevent the messages from stopping the attacker from doing it, but it will stop them from reading the message

Question 4

Notation

Answer 4

EK(M) = C
Apply encryption on plaintext M using key K to obtain ciphertext C.
DK(C) = M
Apply decryption on ciphertext C using key K to obtain plaintext M.

Question 5

Is it better to keep keys private and publish the function, or keep function private and publish the keys?

Answer 5

Better to keep keys secret and publish the function of encryption
- Different key for communicating with different recipients
- If you keep the function secret, and trade keys publicly, then the adversary can compromise all the messages
Keep adversary’s life difficult by keeping both function and the keys from them–ideal situation is to keep both secret if possible

Question 6

Kerkhoff’s Principles

Answer 6

(1) indecipherable (2) can be stolen without causing trouble (3) easy to communicate/remember (4) compatible with telegraph (now digital) system (5) portable/usable (6) easy to use
* **
(1) System must be practically, if not theoretically, indecipherable (code takes 1,000 years to break, etc.)
(2) System must not require secrecy and can be stolen by the enemy without causing trouble (as long as you have strong keys, that should be sufficient)
(3) Key must be easy to communicate and remember (without the help of written notes) and must be changeable or modifiable at the will of the correspondents (keys must be changed regularly)
(4) System must be compatible with the telegraph system (applicable at the time Kerckhoff wrote this) - now, we would say it must be compatible with digital data
(5) Apparatus should be portable and its use must not require the aid of several people (useability issue)
(6) The system must be easy to use, requiring neither mental strain not the knowledge of long series of rules to observe (instructions are clearly understood and can be applied with a high degree of fidelity for the individuals involved in encrypting the messages)

Question 7

Brute force

Answer 7

if you cannot analyze the plaintext, the only approach is to apply the decrypt function and try every possible key until something works; also intimidation, torture, etc.
- start with 0 and then keep trying numbers after that

Question 8

Key space

Answer 8

# possible keys for an encryption function
- When a cipher requires a key length of n bits, the key space (# possible keys for an encryption function) is 2^n

Question 9

How is a cipher secure?

Answer 9

• Computational security: resistance to a brute force attack (keyspace is so large that you can’t get through the keyspace is a reasonable amount of time)
• Semantic security: no amount of analysis can reveal the key; you must have both plaintext and cipher text to find the key
• Perfect security: must have both computational security and semantic security; must also be theoretically impossible to break

Question 10

Indistinguishability in a Chosen-Plaintext-Attack (IND-CPA)

Answer 10

Usually described as a game; you as the attacker choose 2 message, feed it into box (you know the encrypt function, but don’t know key or what message will be chosen)
If you can beat the odds of 50/50, then you have an advantage - something is wrong with the encryption function, which cause info to leak, which allows adversary to determine which of the two plaintext messages was encrypted

Question 11

Indistinguishability in a Ciphertext-Attack (IND-CCA)

Answer 11

if you don’t know key, but know function; decrypt cipher texts and black box provides corresponding plaintext
If you can determine the key if you have plaintext M, then the function is not secure

Question 12

Entropy

Answer 12

describes a measure of uncertainty/randomness/disorder; patterns

• Order and structure (low entropy)
• Uncertainty and randomness (high entropy)

Question 13

Sources of randomness in an OS

Answer 13

time between keystrokes, fluctuations in clock frequency, static from sound card, mouse movements, hardware interruption…

Question 14

Pseudorandom Number Generator (PRNG)

Answer 14

• the randomness of the sequence is dependent upon the randomness of the initial seed only–same seed, same sequence
• Function to produce a random stream of data not deterministic that always gives same output with same input; could be used to select keys when you don’t have a good source of randomness and you need to create a key (give it a seed to start with, feds it through function to get a PRN as output) - looks like it’s random but it’s not, but is good enough in most cases
• A short cycle is bad; so is “clumping” (low entropy)
• Encryption can’t randomly map to ciphertext because that could be reversed and figured out

Question 15

Block cipher vs. stream cipher

Answer 15

• Block cipher: operates on a fixed input (ex: i character, [8 bits]) at a time
• Stream cipher: can operate on any sized, non-fixed input (can do 3 bytes, 3 bits…)- used when encrypting network data that is moving quickly

Question 16

What is provided by using symmetric encryption?

Answer 16

Confidentiality (only the people who have the shared secret can access it)

Question 17

Monoalphabetic substitution cipher

Answer 17

Cipher in which any given input is given into the plaintext, it will produce the ciphertext; don’t hide the underlying statistical properties; wherever the pattern exists in the plaintext, it will exist in the ciphertext

Question 18

Caesar cipher

Answer 18

type of monoalph. sub. cipher; shift the alphabet # of spots; A=D, B=E, etc. ; wraparound at end of alphabet (key = # of shifts) - once you know the shift, you know all the other values

• Because key space is so small (technically 26), you could use brute force to try all the keys to see which one works
• Shifting this multiple times doesn’t help because this code is linear; just a single shift
• You could apply this in a digital way by shifting the ASCII value
• In an 8-bit key, you have a 2^8 shifts

Question 19

General substitution cipher

Answer 19

type of monoaplh. sub. cipher; every character has a unique plaintext to ciphertext mapping = lots of possible keys
Looks to overcome Caesar cipher
26 possible number of keys; 26 x 25 x 24 ….
- Brute forcing a key space this large isn’t a good option, but it does not help to encrypt multiple times–it will not buy you any more security because the adversary could just find the one key
- If a cipher does not hide the properties of the plaintext, then the cipher is weak (if patterns and structures are still there, it is not secure)
- Multiple encryptions doesn’t provide additional security

Question 20

Polyalphabetic substitution cipher

Answer 20

A one-to-many relationship between the characters encrypted and what they could become in the ciphertext
- Problem: multiple symbols for each character

Question 21

Vigenere cipher

Answer 21

type of polyaph. sub. cipher; uses a different Caesar cipher key on each letter in the plaintext

• Take 1st char of key and apply it to the 1st char of cipher (ex, key = ROPE)
• Goal: hide properties of plaintext
• The key “ALL” is bad because it is short; every 3rd character is plaintext)
• How to break: if you know the length of the key is 4 characters, then you know the 5th character was encrypted with the same shift → do a frequency distribution analysis (what are most common letters in a language) to see (4 char. Key = need 4x that amount to decrypt the message); if you don’t know key length, then you have to try to find it (start with 2, increase key length til something pops out)

Question 22

One-time pad

Answer 22

perfectly secure (every outcome/message is equally likely); the only known unbreakable encryption if you:

• Use a non-repeating K as long as M
• Use a randomly generated K
• Never use K again
• Why is it unbreakable? Theoretically there is always brute force, but it is (1) semantically secure bc it hides all statistics of plaintext, and (2) computationally secure bc brute force doesn’t help tell which message is legit
• Problems: keys must be secretly distributed, must be as long as the message, and must be random (not trivial)

Question 23

XOR in digital encryption and decryption

Answer 23

• to encrypt: EsubK (M) = M (XOR) K

- to decrypt: Dsub (C) = C (XOR) K

Question 24

Transposition/Permutation

Answer 24

Transposition: rearranging (vs. substituting), eg., writing the same message but just backwards

• Keyed transposition
• # of rows = key length; # of columns = message length / key length
• Repeated keyed transpositions does add security; eg., rubix cube - move the key to a different spot, if you repeat those moves over and over again, the rubix cube becomes more jumbled

Question 25

Modern block ciphers

Answer 25

• Applies substitution and transposition many times before it provides output text
• Block function: must encrypt a certain number of bits

Question 26

Data Encryption Standard (DES)

Answer 26

• No realistic cryptanalysis
• Brute force is a reality today
• 2005: withdrawn as a U.S. standard
• BL: the DES key is considered too small now
• 2DES and 3DES; encrypting 2x or 3x, respectively

Question 27

Meet-in-the-middle attack

Answer 27

Can either be done by encrypting plaintext with key1, or by decrypting the cipher using key2

Question 28

Advanced Encryption Standard (AES)

Answer 28

• current US standard
• Consists of permutations and substitutions
• Selection of keys is what makes it secret
• no known practical attacks

Question 29

Padding

Answer 29

• if last byte is short of a full byte, then you add 1 byte of padding at the end–always add so that the last byte is guaranteed to be a pad byte
• NIST padding rules: always pad with a 01 byte
  If needed, add 00 byte until you get up to full block size