Unit 2: Symmetric Cryptography Flashcards
Eavesdropping
a passive attack, just listening
Manipulation/Corruption
an attacker is actively involved; stops message, changes/replaces the message, so that when the recipient gets it, it’s not the right message
Interception
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
Notation
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.
Is it better to keep keys private and publish the function, or keep function private and publish the keys?
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
Kerkhoff’s Principles
(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)
Brute force
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
Key space
# 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
How is a cipher secure?
- 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
Indistinguishability in a Chosen-Plaintext-Attack (IND-CPA)
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
Indistinguishability in a Ciphertext-Attack (IND-CCA)
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
Entropy
describes a measure of uncertainty/randomness/disorder; patterns
- Order and structure (low entropy)
- Uncertainty and randomness (high entropy)
Sources of randomness in an OS
time between keystrokes, fluctuations in clock frequency, static from sound card, mouse movements, hardware interruption…
Pseudorandom Number Generator (PRNG)
- 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
Block cipher vs. stream cipher
- 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
What is provided by using symmetric encryption?
Confidentiality (only the people who have the shared secret can access it)
Monoalphabetic substitution cipher
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
Caesar cipher
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
General substitution cipher
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
Polyalphabetic substitution cipher
A one-to-many relationship between the characters encrypted and what they could become in the ciphertext
- Problem: multiple symbols for each character
Vigenere cipher
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)
One-time pad
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)
XOR in digital encryption and decryption
- to encrypt: EsubK (M) = M (XOR) K
- to decrypt: Dsub (C) = C (XOR) K
Transposition/Permutation
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
Modern block ciphers
- Applies substitution and transposition many times before it provides output text
- Block function: must encrypt a certain number of bits
Data Encryption Standard (DES)
- 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
Meet-in-the-middle attack
Can either be done by encrypting plaintext with key1, or by decrypting the cipher using key2
Advanced Encryption Standard (AES)
- current US standard
- Consists of permutations and substitutions
- Selection of keys is what makes it secret
- no known practical attacks
Padding
- 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
