Publish on 25th October 2019
Category: Birds
0

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 time2nA 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/ciphertextpairsComplexity2lfor 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?

0

Embed

Upload

0bc6b775e14143d8066b8039531e40ef-Cryptography - cs.umd.edu