0bc6b775e14143d8066b8039531e40ef-Cryptography - cs.umd.edu

Cryptography
Lecture 16
Block ciphers
Recall…
Want keyed permutationF: {0,1}nx {0,1}l{0,1}ln= key length,l= block lengthWantFk(foruniform, unknown keyk) to be indistinguishable from a uniform permutation over{0,1}l
Attack models
A block cipher isnotan encryption scheme!!Nevertheless, some of the terminology usedisthe same (for historical reasons)“known-plaintext attack”: attacker given {(x,Fk(x)} forarbitrary x(outside control of the attacker)“chosen-plaintext attack”: attacker can queryFk(.)“chosen-ciphertextattack”: attacker can querybothFk(.) and Fk-1(.)
Concrete security
Asin the case of streamciphers,we are interested inconcretesecurity for a given key length nBest attack should take time 2nIf there is an attack taking time 2n/2then the cipher is consideredinsecureLook at distinguishing attacks and key-recovery attacks
Designing block ciphers
WantFk(for uniform, unknown key k) to be indistinguishable from a uniform permutation over{0,1}lIf x and x’ differ in one bit, what should be the relation betweenFk(x) andFk(x’)?How many bits should change (on average)?Which bits should change?How to achieve this?
Confusion/diffusion
“Confusion”Small change in input should result in local, “random” change in output“Diffusion”Local change in output should be propagated to entire output
Design paradigms
Two design paradigmsSubstitution-permutation networks (SPNs)Feistelnetworks
SPNs
Build “random-looking”perm.onlonginputfrom randomperms.onshortinputWhat is the key length for a random permutation on {0,1}l?E.g. (assuming8-byte blocklength),Fk(x) = fk1(x1) fk2(x2) … fk8(x8),where each f is a randomperm. on {0,1}8How long isthe key for F?
SPN
fk1
fk2
. . .
Is this a pseudorandompermutation?
fk8
SPN
This has confusion but no diffusionAdd amixing permutation…
SPN
fk1
fk2
. . .
. . .
fk8
SPN
Mixing permutation is publicChosen to ensure gooddiffusion(This will be more clear later)Note that the structure is invertible (given the key) since the f’s are permutations and the mixing permutation is invertible
SPN
Doesthis give a pseudorandompermutation?What if we repeat for another round (with independent, random functions)?What is the minimal # of rounds we need?AvalancheeffectJudiciouschoice of mixing permutation
SPNs
Using random f’s is not practicalKey would be toolargeInstead, use f’s of a particular formfki(x) = Si(ki x), whereSiis afixed (public) permutationThe {Si} arecalled “S-boxes” (substitution boxes)XORingthe key is called “key mixing”Note that this is still invertible (given the key)
S1
S2

k1
. . .
S8
Avalanche effect
Design S-boxes and mixing permutation to ensure avalanche effectSmall differences should eventually propagate to entire outputS-boxes:any1-bitchange in input causes ≥2-bit change in outputNot so easy to ensure!Mixing permutationEach bit output from a given S-box should feed into adifferentS-box in the next round
SPN
One round of an SPN involvesKey mixingIdeally, round keys are independentIn practice, derived from a master keyvia akey scheduleSubstitution (S-boxes)Permutation (mixing permutation)r-round SPN has r rounds as above, plus a final key-mixing stepWhy?Invertible regardless of how many rounds…
Key-recovery attacks
Key-recovery attacks are even more damaging than distinguishing attacksAs before, a cipher is secure only if the best key-recovery attack takes time2nA fast key-recovery attack represents a “complete break” of the cipher
Key-recovery attack, 1-round SPN
Consider first the case where there is no final key-mixing stepPossible to get the key immediately!What about a full 1-roundSPN (with independent round keys)?Attack 1: for each possible1st-roundkey, get corresponding 2nd-round keyContinue process ofelimination using additional plaintext/ciphertextpairsComplexity2lfor key of length 2l
Key-recovery attack, 1-round SPN
Better attack: work S-box-by-S-boxAssume 8-bit S-boxFor each 8 bits of 1st-round key, get corresponding 8 bits of 2nd-round keyContinue process of eliminationComplexity?