what is Shannon’s Theorem?
OTP is perfectly secure as long as only one message is encrypted
can a scheme with |M| > |K| be perfectly secure?
no
what is a transposition cipher?
plaintext is shuffled using a permutation
e.g. permutation = {2,1,5,3,4}
HELLO WORLD becomes
EHLOL OWLDR
the same shuffling occurs for all subsequent blocks
what are S and P-boxes? (Product Ciphers)
S-boxes confuse inputs
P-boxes diffuse bits across S-box inputs
Iterated on these combinations repeatedly
More secure as substitution and transpositions are combined
what is a block cipher?
A block cipher with key length K and block size N consists of two
sets of efficiently computable permutations:
Enck : {0,1}N –> {0,1}N; Deck : {0,1}N –> {0,1}N;
such that Deck is the inverse of Enck for each k E {0,1}K
2K possible keys
sometimes write Enc(k, .) and Dec(k, .)
what is the typical N (block size) and K (key size) for DES and AES?
typically N=64 (DES) or N=128 (AES)
K=56 (DES) or K=128, 192, 256 (AES)
wat are the primary and secondary indicators of security for a block cipher?
primary = key size
secondary = block size
what are the three types of attacks on block ciphers?
Known Plaintext Attacks (KPA);
-adversary gets to observe many (p, c) pairs for a fixed key k
Chosen Plaintext Attacks (CPA):
-adversary gets to choose many plaintexts and gets corresponding ciphertexts under a fixed key k
Chosen Ciphertext Attacks (CCA):
-adversary gets to choose many ciphertexts and gets corresponding plaintexts under a fixed key
in each case the target is the key k
what method of key retrieval can be done with (p, c) pairs?
how can it be applied to ciphertext only?
exhaustive key search
- for each candidate key k if c1 = Enck(p1) using pair (p1, c1), reject all keys that don’t satisfy
-for all remaining keys test (p2, c2) and so on till only one key remains
can only be applied to ciphertext only if the plaintext is meaningful
what does it mean for a block cipher to have a strong pseudo-randomness property (PRP)?
adversary A interactes with either (Enc, Dec) for a random choice of k or with a random permutation and it’s inverse (Π, Π-1)
block cipher has strong-PRP is theres is no efficient A that can tell the difference between (Enc, Dec) and (Π, Π-1)
efficiency of A can be quantified by number of queries (q) and running time (t)
what is the feistel cipher?
splits block into 2 halves of N/2 bits each, and uses a particular method for operation on the halves to build the round
function
used in DES
what is the encryption process for DES?
Initial Permutation (IP) followed by 15 rounds with
exchanging registers of halves.
Each round, a round function
is applied, and each round
function is keyed with a 48-bit
subkey derived from the key
schedule.
Final (16th) round does not
exchange registers, but instead
permutes with IP-1.
IP is public, so if ctxt is known,
then L16, R16, R15 also known.
what is the process for the round function F in the Feistle cipher?
detailed function F:
* Each round operates on left
and right 32-bit words.
* The XOR is bitwise XOR.
* Li = Rii - 1
* Ri = Lii - 1 XOR F(Rii - 1,Ki)
how do S-boxes work?
input of b1, b2, b3, b4, b5, b6
interpret b1, b6 as binary for an integer range [0, 3]. This value indexes the row to use
interpret b2, b3, b4, b5 as binary integer range [0, 15]. This indexes the column to use
each entry is represented by a decimal and interpreted as a 4-bit binary
what are the 4 distinct operations AES applies on the array?
- SubBytes operation: byte-wise substitution, i.e. an 8-bit to an 8-bit S-box.
- ShiftRows operation: shifts rows of array.
- MixColumns operation: linear transformation to mix columns.
- AddRoundKey operation: byte-by-byte XOR of round key.
