Block Ciphers and Modes of Operation Block Ciphers: how do we do encryption on a block of data
modes of operation: how do we do encryption on a LOT of blocks of data
Block Ciphers: AES CBC is an example
Types of Symmetric key crypto use a fixed length key to encrypt a fixed length block of data for example, a 64 bit block of data and a 128 bit key.
Idea behind a block cipher is like a big substitution cipher substitution cipher is a → j b → l etc to sub out the alphabet to encrypt the table is the key
if we have a 64 bit block cipher, then our subtitution table has 2^64 entries ( 1.8 * 10^19) the goal of a block cipher is to be able to look up, in that big table,
Data Encryption Standard ( DES ) 64 bit block size 56 bit key size released in 1976 us govt standard until 2001
Advanced Encryption Standard ( AES ) 128 bit block size 128, 192, or 256 bit key size current us government standard most widely used
aes more better because more big key. mmm.
Block cipher is an encryption / decryption algorithm that encrypts a fixed size of bits
a secure block cipher behaves like a randomly chosen permutation from the set of all permutations on n bit strings a random permutation: each n bit input is mapped to one randomly chosen n bit input when the key k is fixed, ek(M) must be a permutation ( bijective function ) on n bit strings ( each input must correspond to exactly one unique output )
suppose ek(m) is not bijective, then? two inputs might correspond to the same output e.g. Ek(x1) = Ek(x2) = y given ciphertext y you cant uniquely decrypt.
2128 possibilities for a 128 bit key 210 = 1000 2128 = 210*12.8 = (103)12.8 = (103 )13 = 1039 if we have massive hardware that can try 10^9 billion keys in 1 nanosecond, that is 10^18 keys per second we need 10^21 second to crack a key one year is 3*10^7 seconds 10^21 seconds is 30 trillion years
encryption and decryption should be computable in microseconds. formally, KeyGen(), Enc(), Dec() should not take exponential time
block cipher algorithms typically use operations like XOR bit shifting, and small table lookups very fast on modern processors modern cpus provide dedicated hardware support for block ciphers
aes key size 128, 192, or 256 block size 128 bits ( aalways 128 bits, regardless of key size ) you dont need to know how AES works, but you do need to know it’s parameters
block ciphers are not ind cpa secure, because they’re deterministic
No deterministic scheme can be ind cpa secure becaues the adversary can always tell if the same message has been encrypted twice block ciphers can only encrypt messages of a fixed size what if we want to encrypt something longer than 128 bits? to address these problems, we use modes of operation
what to do with large messages?
how about chunking
if we take 128 bits of plaintext input, and use our key to generate ciphertext, and then just add the encrypted segments together
if you have 256 bits of text which is all the same, then they can detect the pattern between the chunks, so if the first 128 bit message and second 128 bit message are the same, they can start to find patterns.
ECB is NOT ind-cpa secure i can see that penguin so vividly
an IV, initialization Vector , is injecting randomness into the plaintext before encryption.
this is aes cbc:
input plaintext and iv → ciphertext ciphertext is then used as iv for next block
R = M1 XOR IV
Enc(K, M1 XOR IV) = C1
Ci =Enc(K,M1 XOR Ci-1)
C0 = IV
Split M into j plaintext blocks from M1 to Mj choose a random IV compute an output(Iv, C1, … , Cj)
IV was randomly generated recipient needs to know what IV was in order to decrypt
Ci = EK(Mi ⊕ Ci-1) Definition of encryption DK(Ci) = DK(EK(Mi ⊕ Ci-1)) Decrypting both sides DK(Ci) = Mi ⊕ Ci-1 Decryption and encryption cancel DK(Ci) ⊕ Ci-1 = Mi ⊕ Ci-1 ⊕ Ci-1 XOR both sides with Ci-1 DK(Ci) ⊕ Ci-1 = Mi XOR property
this kind of encryption cant be parallelized ( inherently sequential, need last ciphertext to encrypt next block ) decryption can be parallelized ( i do not know how )
to encrypt a message longer than the block size, we use padding. add dummy bytes to end until it’s the right length. cant pad with 0s, what if message already ended in 0s cant pad with 1s, same issue. need to pad without ambiguity.
options: pad with a 1 then infinite 0s or pad with the number of padding bytes so if you need 1 byte, pad with 01 if you need 3, pad with 03 03 03 if you need 0, pad an entire dummy block
aes cbc is ind-cpa secure if the iv is randomly generated and never reused if you reuse iv, it becomes deterministic, and is no longer ind cpa secure.
if you want to change the plaintext of just one block, you must re encrypt the whole thing, cause it is a chain. which for some usecases, is bad. e.g. encrypted filesystems
in those cases, we need aes ctr. aes ctr throws a random nonce in the input, and a counter, which we then encrypt with the key, and xor the output with the plaintext, to one time pad, giving us the ciphertext. allows us to block without it being sequential. counter increments per block to ensure each cipher output is different nonce is same idea as IV from CBC mode.
to decrypt, you take that nonce you have, and that counter, block cipher encrypt them, and then xor with the ciphertext, to get the plaintext back.
this can be parallelized on both encryption and decryption.
we do not even need to pad, can just cut off parts of xor larger than the message
aes ctr is ind cpa secure if nonce is randomly generated if you reuse the nonce, it is like reusing key in one time pad, no longer ind cpa secure.
theoretically ctr is equally secure to cbc, but if misimplemented, cbc only leaks partial info, and ctr fails catastrophically.
there is no integrity or authenticity check on both cbc and ctc, so mallory can mess w your shit and make it say crazy stuff when decrypted which isnt chill.