CS计算机代考程序代写 algorithm CM30173: Cryptography\reserved@d =[@let@token art II

CM30173: Cryptography\reserved@d =[@let@token art II

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Part II

Private-key cryptography: block ciphers

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Attacks on SPNs: Di!erential cryptanalysis

Example of di!erential cryptanalysis

Pseudo-code for example

Attacks on SPNs: Linear cryptanalysis

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Overview of method

For each tuple (x, x!, y, y!):

1 For each candidate round key kNr+1 partially
decrypt both ciphertexts producing state and
state!.

2 Find the state di!erence state” = state ! state!.

3 If state” = expected di!erence then increment the
counter for this candidate key.

The candidate key with the highest count should have
the correct values for the targeted key bits.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Finding a di!erential trail

How do we find the expected di!erence between state
and state! just before the final S-boxes?

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Finding a di!erential trail

How do we find the expected di!erence between state
and state! just before the final S-boxes?

1 For each S-box consider all possible di!erentials:

(a”, b”) = (input di!erence, output di!erence)

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Finding a di!erential trail

How do we find the expected di!erence between state
and state! just before the final S-boxes?

1 For each S-box consider all possible di!erentials:

(a”, b”) = (input di!erence, output di!erence)

2 Find the propagation ratio, the probability b”

occurs given a”.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Finding a di!erential trail

How do we find the expected di!erence between state
and state! just before the final S-boxes?

1 For each S-box consider all possible di!erentials:

(a”, b”) = (input di!erence, output di!erence)

2 Find the propagation ratio, the probability b”

occurs given a”.

3 Combine high probability di!erentials to make a
di!erential trail.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

An example input di!erence to !S

For example, consider the set of pairs with input
di!erence a! = 1111:

{(a, a ! a!)|a ” {0, 1}4}

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

An example input di!erence to !S

For example, consider the set of pairs with input
di!erence a! = 1111:

{(a, a ! a!)|a ” {0, 1}4}

What happens when we input a, a” to our S-box?

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Example for input di!erence 1111

a a

b b

b
!

0000 1111 0100 0000 0100

0001 1110 0001 0101 0100

0010 1101 1110 1010 0100

0011 1100 1000 0011 1011

0100 1011 1101 0111 1010

0101 1010 0110 1001 1111

0110 1001 0010 1100 1110

0111 1000 1011 1111 0100

1000 0111 1111 1011 0100

1001 0110 1100 0010 1110

1010 0101 1001 0110 1111

1011 0100 0111 1101 1010

1100 0011 0011 1000 1011

1101 0010 1010 1110 0100

1110 0001 0101 0001 0100

1111 0000 0000 0100 0100

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Example di!erence

0000 0001 0010 0011 0100 0101 0110 0111
0 0 0 0 8 0 0 0

1000 1001 1010 1011 1100 1101 1110 1111
0 0 2 2 0 0 2 2

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Example di!erence

0000 0001 0010 0011 0100 0101 0110 0111
0 0 0 0 8 0 0 0

1000 1001 1010 1011 1100 1101 1110 1111
0 0 2 2 0 0 2 2

The propagation ratio is
count

24
.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Example di!erence

0000 0001 0010 0011 0100 0101 0110 0111
0 0 0 0 8 0 0 0

1000 1001 1010 1011 1100 1101 1110 1111
0 0 2 2 0 0 2 2

The propagation ratio is
count

24
.

Output di!erence 0100 has propagation ratio 0.5

Output di!erences 1010, 1011, 1110, 1111 have
propagation ratio 0.125

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Di!erence distribution table

We can construct a di!erence distribution table

each row represents one of the possible 4 bit input
di!erences

each column one of the 4 bit output di!erences

an element of the table is the number of times the
output di!erence occurred given the input
di!erence

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Di!erence distribution table

We can construct a di!erence distribution table

each row represents one of the possible 4 bit input
di!erences

each column one of the 4 bit output di!erences

an element of the table is the number of times the
output di!erence occurred given the input
di!erence

We will use this to construct our di!erential trail.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Di!erence distribution table

a 0 1 2 3 4 5 6 7 8 9 A B C D E F

0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 0 4 2 0 0 4 0 2 0 0 2 0

2 0 0 0 0 0 0 4 0 0 2 4 2 0 2 0 2

3 0 0 0 2 2 2 2 0 2 0 0 0 2 0 0 4

4 0 0 0 2 0 0 2 4 0 2 0 0 6 0 0 0

5 0 0 4 0 0 4 0 0 0 2 2 0 2 0 0 2

6 0 0 0 2 0 0 2 0 0 0 6 0 2 2 2 0

7 0 0 0 4 2 2 0 0 2 2 0 0 0 0 0 4

8 0 0 0 0 0 0 0 4 0 0 0 4 2 2 2 2

9 0 2 2 0 0 2 0 2 2 2 0 0 0 0 4 0

A 0 6 0 0 2 0 4 0 2 0 0 0 0 2 0 0

B 0 0 2 4 0 0 0 2 6 0 0 0 0 2 0 0

C 0 0 2 0 0 0 0 2 2 0 2 6 2 0 0 0

D 0 2 4 0 0 2 0 0 0 2 0 0 0 2 4 0

E 0 6 2 0 2 0 0 2 0 0 0 0 0 4 0 0

F 0 0 0 0 8 0 0 0 0 0 2 2 0 0 2 2

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

But we don’t know the round keys…

Round r:
stater = stater#1 ! k

r

and then apply the substitutions to stater.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

But we don’t know the round keys…

Round r:
stater = stater#1 ! k

r

and then apply the substitutions to stater.

To make a di!erential trail we don’t need kr:

state! = stater ! state

r

= (stater#1 ! k
r) ! (state”

r#1 ! k
r)

= stater#1 ! state

r#1

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

But we don’t know the round keys…

Round r:
stater = stater#1 ! k

r

and then apply the substitutions to stater.

To make a di!erential trail we don’t need kr:

state! = stater ! state

r

= (stater#1 ! k
r) ! (state”

r#1 ! k
r)

= stater#1 ! state

r#1

S-box input di!erences on round r
= permuted S-box output di!erences from round r#1

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Example di!erential trail

We can now form a di!erential trail…

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Probability the trail occurs

We used

PR(1111, 0100) =
1

2
once and

PR(0100, 1100) =
3

8
three times hence the propagation ratio of the entire
trail is assumed to be

1

2

!

3

8

“3

=
27

1024
.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Candidate keys

Which bitstrings are candidate keys in this example?

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Candidate keys

Which bitstrings are candidate keys in this example?

Targeted bits: first 8 bits of the final round key.

Candidate keys: partial keys that vary the bits
interacting with the di!erential trail.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Filtering

Not all tuples (x, x”, y, y”) will be useful for this
particular di!erence trail.

We filter our input tuples…

Tuples that survive the filter are called right pairs.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Algorithm (Sketch of di!erential cryptanalysis)

for each tuple (x, x”, y, y”) perform filtering

for each right pair do
for each candidate key k do

x-or: state = y ! k, state” = y” ! k
substitutions: apply !#1

S
to state and state”

compute di!erence: state! = state ! state”

if state! == expected di!erence then
increment counter for k

end if
end do

end do

output candidate key with maximum counter

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Attacks on SPNs: Di!erential cryptanalysis

Example of di!erential cryptanalysis

Pseudo-code for example

Attacks on SPNs: Linear cryptanalysis

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

A related attack is linear cryptanalysis

Objective: Find targeted key bits.
Known plaintext attack: attacker has a set of
plaintext-ciphertext pairs encrypted with the same
key k.
Using probabilistic analysis we find biased linear
approximations for the S-boxes. We construct a
linear approximation, with a large bias, of the SPN
(excepting the final round) in terms of plaintext
bits and state bits.
For each candidate key we partially decrypt each
ciphertext and see if the linear approximation holds
for state, incrementing a counter for the key if it
does.
The candidate key with largest bias (from
|input pairs|/2) should contain the targeted key
bits.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Cost of di!erential cryptanalysis

If p is the propagation ratio of the di!erential trail then
the attack is often successful if the number of tuples
(x, x”, y, y”) is approximately c/p where c is some small
constant.

Cost of linear cryptanalysis

If p is the “bias” of the linear approximation then the
attack is often successful if the number of
plaintext-ciphertext pairs is approximately c/p2 where c
is some small constant.

CM30173:
Cryptography

Part II

Attacks on SPNs:
Di!erential
cryptanalysis

Example of di!erential
cryptanalysis

Pseudo-code for
example

Attacks on SPNs:
Linear cryptanalysis

Can we protect against these attacks?

It is possible to design S-boxes to reduce the
e!ectiveness of these attacks.

DES was protected against di!erential cryptanalysis
but not linear cryptanalysis.

AES was protected against both attacks.

The attacks are still theoretically possible but
require infeasible quantities of input data.

In the next lecture we will introduce DES which was
designed to withstand di!erential cryptanalysis and is
also one of the most important examples of block
ciphers.

Private-key cryptography: block ciphers
Attacks on SPNs: Differential cryptanalysis
Example of differential cryptanalysis
Pseudo-code for example

Attacks on SPNs: Linear cryptanalysis