微信客服：xiaoxionga100
微信客服：ITCS521
COMP41280-高数代写
时间：2023-03-20
2nd Chapter: Fundamentals of Cryptography
COMP 41280
Fe´lix Balado
School of Computer Science
University College Dublin
Outline of the Chapter
1 Basic Concepts and Models
2 Defining and Measuring Security
2/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Information Security Requirements
Privacy :
protected information should not be accessible to unauthorised
third parties
Authentication:
the recipient of some information should be able to verify its
origin and authorship
Integrity :
the recipient of a message should be able to verify that it has
not been forged or altered in transit
Non repudiation:
a message authenticated by a trusted third party cannot be
repudiated at a later stage by its sender
Cryptography can deal with aspects of all these requirements
3/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Shannon’s Model for Cryptography (1948)
Source Encryption Decryption Destination
KeyKey
m
es
sa
g
e
m
es
sa
g
e
en
cr
yp
te
d
m
es
sa
g
e
4/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Shannon’s Model for Cryptography (1948)
Alice Encryption Decryption Bob
KeyKey
m
es
sa
g
e
m
es
sa
g
e
en
cr
yp
te
d
m
es
sa
g
e
4/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Notation, Terminology and Basic Concepts
Basic encryption/decryption operation flow:
l →
τ
c →
τ ′
l
l : cleartext, plaintext, unencrypted/clear message
c : ciphertext, encrypted/ciphered message
τ(·, ·) and τ ′(·, ·): cipher, encryption/cryptographic
scheme/system/method/algorithm
these are invertible functions of l and c , respectively, which
also depend on a second parameter, k
k : encryption/decryption key
encryption of l using k : c = τ(l , k)
decryption of c using k : l = τ ′(c , k) = τ ′(τ(l , k), k):
5/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Notation, Terminology and Basic Concepts
The wrong decryption key should lead to a wrong plaintext
if k ′ 6= k then
τ ′(τ(l , k), k ′) 6= l
When we encrypt a source of information we can model the
plaintext using a r.v. L, and so l ∈ L
the choice of the key is also modelled by a random variable K ,
and so k ∈ K
6/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Notation, Terminology and Basic Concepts
The wrong decryption key should lead to a wrong plaintext
if k ′ 6= k then
τ ′(τ(l , k), k ′) 6= l
When we encrypt a source of information we can model the
plaintext using a r.v. L, and so l ∈ L
the choice of the key is also modelled by a random variable K ,
and so k ∈ K
In many cryptographic methods τ(·, k) does not operate on a
single symbol, but on a block of n symbols; we will use special
notations in this situation:
cn = τ(ln, k)
c = τ(l, k)
however we will simply use c = τ(l , k) if clear from the context
6/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Privacy Threats
Mallet
Alice Encryption Decryption Bob
KeyKey
Attacker’s typical nicknames:
Mallet, Mallory: malicious man in the middle
Eve: eavesdropper
Trudy: intruder
7/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (I)
Kerckhoffs principle: it is always safer to assume that all the
details of the cryptographic scheme are publicly known
the encryption system (τ, τ ′) is public, static, not modifiable
the key (k) is private, dynamic, modifiable
Only the key can remain secret
security through obscurity (i.e., by assuming that Mallet does
not know τ, τ ′) is a very bad idea in the long run
Shannon: “the enemy knows the system”
8/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (II)
Cryptanalysis: gathering information about the secret
communication between Alice and Bob
point of view of Mallet
An attack to a cryptosystem is an attempt to cryptanalyse it
examples of successful attacks:
recover cleartext l , either completely or partially
recover the key k (in which case future communications with
that key will also be compromised)
9/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (II)
Cryptanalysis: gathering information about the secret
communication between Alice and Bob
point of view of Mallet
An attack to a cryptosystem is an attempt to cryptanalyse it
examples of successful attacks:
recover cleartext l , either completely or partially
recover the key k (in which case future communications with
that key will also be compromised)
Mallet might also carry out active attacks
example: replace genuine encrypted message c by forged
encrypted message cF (without necessarily obtaining l or k)
9/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (III)
Cryptanalysis is as much a science as an art
sometimes Mallet can attempt a systematic strategy
at other times no specific methodology is known
Mallet can sometimes exploit available side information:
examples:
message language and/or content: common sentences,
frequency of letters, digrams, trigrams,. . .
messsage format (headers, footers, tags, etc)
time taken to carry out encryption/decryption algorithm
power consumption when algorithm is run
Without side information, the attacker could always attempt
exhaustive analysis (brute force): try all keys in key space
10/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (Toy Example)
Decipher the ciphertext below, knowing that ci = τ(li , k) is a
4-character permutation of the English plaintext li
c = c1‖c2‖c3=’rdfoatfielop’
(‖: concatenation)
in this toy example, applying brute force is easy, as there are
only |K| = 4! = 24 keys
(see transposition ciphers in next lecture)
11/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (Toy Example)
Decipher the ciphertext below, knowing that ci = τ(li , k) is a
4-character permutation of the English plaintext li
c = c1‖c2‖c3=’rdfoatfielop’
(‖: concatenation)
in this toy example, applying brute force is easy, as there are
only |K| = 4! = 24 keys
(see transposition ciphers in next lecture)
however, the attack is easier if side information “plaintext
message conveys car makes” is available to Mallet:
l = l1‖l2‖l3=’fordfiatopel’
Modern ciphers are of course more sophisticated than this
11/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis Models (I)
What are the scenarios in which Mallet can find himself?
1 Ciphertext only: Mallet has one or more ciphertexts c
Mallet
l c
Alice Encryption Decryption Bob
k,l
12/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis Models (I)
What are the scenarios in which Mallet can find himself?
1 Ciphertext only: Mallet has one or more ciphertexts c
Mallet
l c
Alice Encryption Decryption Bob
k,l
2 known plaintext: Mallet has a number of (l , c) pairs
Mallet
l c
Alice Encryption Decryption Bob
k
12/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Feasibility of Known Plaintext Scenario
It might appear that the known plaintext scenario is
far-fetched, but it is more frequent than one might imagine
Mallet can many times know partial information about the l
corresponding to c , leading to known plaintext attacks
example: Mallet may know the format of headers or footers
he may know that a plaintext email encrypted on a given date
and time starts as “Date: Tue, 29 Feb 2016 13:44”
similar strategies are possible with other types of formatting
A historical example of a known plaintext attack occurred in
WWII in the Sahara desert
an isolated German outpost radioed every day the message
“nothing new to report” encrypted with the key for that day
the Allies (i.e. Mallet) caught wind of this, and so they had
one (l , c) pair every day to try to guess that key (and thus
decrypt c ’s from other outposts from the same day)
13/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis Models (II)
3 Chosen cleartext: Mallet can encrypt plaintext using the
encryption block as a black box (i.e. without knowing k) to
produce (l , c) pairs on demand
Mallet
l c
Encryption Decryption
k
scenario 1: encryption system has fallen to the enemy as a
black box (WWII: Enigma boxes in captured German U-Boats)
scenario 2: authentication scheme in which Bob sends a
random l to Alice; she sends him back τ(l , k) to prove she also
has k (consider what happens if Mallet can impersonate Bob)
14/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis Models (II)
3 Chosen cleartext: Mallet can encrypt plaintext using the
encryption block as a black box (i.e. without knowing k) to
produce (l , c) pairs on demand
Mallet
l c
Encryption Decryption
k
scenario 1: encryption system has fallen to the enemy as a
black box (WWII: Enigma boxes in captured German U-Boats)
scenario 2: authentication scheme in which Bob sends a
random l to Alice; she sends him back τ(l , k) to prove she also
has k (consider what happens if Mallet can impersonate Bob)
4 Chosen ciphertext: Mallet can decrypt “ciphertext” using the
decryption box (without knowing k) to produce (l , c) pairs
14/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Outline of the Chapter
1 Basic Concepts and Models
2 Defining and Measuring Security
15/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Probability and Cipher Security: Toy Example
Why does probability matter in terms of the security of a cipher?
Suppose that L = {l1, l2}, i.e. only two plaintext symbols
assume the pmf: pL(l1) =
1
4 and pL(l2) =
3
4
this pmf is given by the plaintext language
Suppose that K = {k1, k2, k3}, i.e. three possible keys
assume the pmf: pK (k1) =
1
2 , pK (k2) = pK (k3) =
1
4
this pmf depends on how the key is chosen
Now suppose that C = {c1, c2, c3, c4}, and that τ(l , k) is:
τ(l , k) k1 k2 k3
l1 c1 c2 c3
l2 c2 c3 c4
16/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Probability and Cipher Security: Toy Example
Why does probability matter in terms of the security of a cipher?
Suppose that L = {l1, l2}, i.e. only two plaintext symbols
assume the pmf: pL(l1) =
1
4 and pL(l2) =
3
4
this pmf is given by the plaintext language
Suppose that K = {k1, k2, k3}, i.e. three possible keys
assume the pmf: pK (k1) =
1
2 , pK (k2) = pK (k3) =
1
4
this pmf depends on how the key is chosen
Now suppose that C = {c1, c2, c3, c4}, and that τ(l , k) is:
τ(l , k) k1 k2 k3
l1 c1 c2 c3
l2 c2 c3 c4
With the public information above, anyone can compute
p(c) =
∑
l∈L,k∈K p(c |l , k)p(l , k), for c ∈ C
we just have to marginalise the joint pmf p(c , l , k)
pC (c1) =
1
8 , pC (c2) =
7
16 , pC (c3) =
1
4 , pC (c4) =
3
16
16/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Probability and Cipher Security: Toy Example
Consider now a ciphertext only attack
Exploiting Bayes’ rule, Mallet can make guesses that have
maximum a posteriori (MAP) likelihood
Using pL|C (l |c) =
pC |L(c|l)pL(l)
pC (c)
he can compute the following
conditional probabilities:
pL|C (l1|c1) = 1
→ if the attacker observes C = c1, he knows L = l1 and K = k1
pL|C (l1|c2) =
1
7
→ if the attacker observes C = c2, he guesses L = l2 and K = k1
pL|C (l1|c3) =
1
4
→ if the attacker observes C = c3, he guesses L = l2 and K = k2
pL|C (l1|c4) = 0
→ if the attacker observes C = c4, he knows L = l2 and K = k3
17/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Probability and Cipher Security: Toy Example
Consider now a ciphertext only attack
Exploiting Bayes’ rule, Mallet can make guesses that have
maximum a posteriori (MAP) likelihood
Using pL|C (l |c) =
pC |L(c|l)pL(l)
pC (c)
he can compute the following
conditional probabilities:
pL|C (l1|c1) = 1
→ if the attacker observes C = c1, he knows L = l1 and K = k1
pL|C (l1|c2) =
1
7
→ if the attacker observes C = c2, he guesses L = l2 and K = k1
pL|C (l1|c3) =
1
4
→ if the attacker observes C = c3, he guesses L = l2 and K = k2
pL|C (l1|c4) = 0
→ if the attacker observes C = c4, he knows L = l2 and K = k3
→ Bottom line: ciphertext can leak information to attacker
this should be avoided in a good encryption system
17/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Encryption Security
There are two types of encryption methods as regards their
vulnerability to cryptanalysis
1 Insecure methods: τ(·, ·) and τ ′(·, ·) should not be “simple”
functions, such as, for instance, linear functions
2 Secure methods
a) unconditionally secure: it is impossible that k can be found by
Mallet independently of available processing power and time
an unconditionally secure cipher is called a perfect cipher, and
we say that it provides perfect secrecy
b) computationally secure: it is theoretically possible for an
attacker to find k , but the methods that would allow him/her
to do so cannot be implemented in practice or would take eons
to complete
18/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems (Perfect Cipher)
Criterion (Shannon): in an unconditionally secure system, or
perfect cipher, L and C must be statistically independent:
pL|C (l |c) = pL(l), for all l , c
equivalently: pL,C (l , c) = pL(l)pC (c)
19/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems (Perfect Cipher)
Criterion (Shannon): in an unconditionally secure system, or
perfect cipher, L and C must be statistically independent:
pL|C (l |c) = pL(l), for all l , c
equivalently: pL,C (l , c) = pL(l)pC (c)
but. . . how can ciphertext and plaintext be independent?
after all, if we know the key then the plaintext completely
determines the ciphertext
→ the independence between C and L is from the point of view
of Mallet (who is unaware of the key)
19/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems (Perfect Cipher)
Criterion (Shannon): in an unconditionally secure system, or
perfect cipher, L and C must be statistically independent:
pL|C (l |c) = pL(l), for all l , c
equivalently: pL,C (l , c) = pL(l)pC (c)
but. . . how can ciphertext and plaintext be independent?
after all, if we know the key then the plaintext completely
determines the ciphertext
→ the independence between C and L is from the point of view
of Mallet (who is unaware of the key)
In terms of mutual information, it must also hold for a perfect
cipher that I (L;C ) = 0
interpretation: on average, the ciphertext does not reveal any
information about the plaintext
also I (K ;C ) = 0 (as H(K |C ) = H(K ) with perfect security)
19/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Unconditional security implies that H(K ) ≥ H(C ); proof :
apply the chain rule of entropy to H(C , L,K ) in two ways:
H(C , L,K) = H(L,K) + H(C |L,K)
H(C , L,K) = H(C , L) + H(K |C , L)
20/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Unconditional security implies that H(K ) ≥ H(C ); proof :
apply the chain rule of entropy to H(C , L,K ) in two ways:
H(C , L,K) = H(L,K) + 0
H(C , L,K) = H(C , L) + H(K |C , L) ≥ H(C , L)
notes:
H(C |L,K) = 0 because of Kerckhoffs principle
entropy is always nonnegative
20/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Unconditional security implies that H(K ) ≥ H(C ); proof :
apply the chain rule of entropy to H(C , L,K ) in two ways:
H(C , L,K) = H(L,K) + 0
H(C , L,K) = H(C , L) + H(K |C , L) ≥ H(C , L)
notes:
H(C |L,K) = 0 because of Kerckhoffs principle
entropy is always nonnegative
finally, apply again the chain rule to H(L,K ) and H(C , L) and
take into account that
H(L|K) = H(L), as message and key are independent
H(C |L) = H(C) with unconditional security
20/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Unconditional security implies that H(K ) ≥ H(C ); proof :
apply the chain rule of entropy to H(C , L,K ) in two ways:
H(C , L,K) = H(L,K) + 0
H(C , L,K) = H(C , L) + H(K |C , L) ≥ H(C , L)
notes:
H(C |L,K) = 0 because of Kerckhoffs principle
entropy is always nonnegative
finally, apply again the chain rule to H(L,K ) and H(C , L) and
take into account that
H(L|K) = H(L), as message and key are independent
H(C |L) = H(C) with unconditional security
check using entropy: the scheme in slide 16 cannot be perfect
20/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = H(C |L,K ) + H(L,K ) = H(L|C ,K ) + H(C ,K )
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = 0 + H(L,K ) = 0 + H(C ,K )
note:
H(C |L,K) = 0 and H(L|C ,K) = 0 (Kerckhoffs’ principle)
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = 0 + H(L,K ) = 0 + H(C ,K )
note:
H(C |L,K) = 0 and H(L|C ,K) = 0 (Kerckhoffs’ principle)
applying again the chain rule to H(L,K ) and H(C ,K ):
H(L|K ) + H(K ) = H(C |K ) + H(K )
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = 0 + H(L,K ) = 0 + H(C ,K )
note:
H(C |L,K) = 0 and H(L|C ,K) = 0 (Kerckhoffs’ principle)
applying again the chain rule to H(L,K ) and H(C ,K ):
H(L|K ) + H(K ) = H(C |K ) + H(K )
finally use H(L|K ) = H(L) and H(C |K ) ≤ H(C ) (conditioning
cannot increase entropy)
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = 0 + H(L,K ) = 0 + H(C ,K )
note:
H(C |L,K) = 0 and H(L|C ,K) = 0 (Kerckhoffs’ principle)
applying again the chain rule to H(L,K ) and H(C ,K ):
H(L|K ) + H(K ) = H(C |K ) + H(K )
finally use H(L|K ) = H(L) and H(C |K ) ≤ H(C ) (conditioning
cannot increase entropy)
Interpretation: in a perfect cipher H(K ) ≥ H(C ) ≥ H(L), so
it is clear that a low-entropy key will be bad for security
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Perfect Ciphers and Key Space Size
Shannon also pointed out that perfect security implies that
#keys ≥ #messages (that is, |K| ≥ |L|)
notation: “#” means “number of”
observe that this is connected with H(K ) ≥ H(L)
22/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Perfect Ciphers and Key Space Size
Shannon also pointed out that perfect security implies that
#keys ≥ #messages (that is, |K| ≥ |L|)
notation: “#” means “number of”
observe that this is connected with H(K ) ≥ H(L)
Proof: by contradiction (reductio ad absurdum)
assume a cipher for which #keys < #messages and choose
some c0 which has nonzero probability, that is p(c0) > 0
if there are less keys than messages, then we can always find a
plaintext message l0 such that τ
′(c0, k) 6= l0 for every key k
22/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Perfect Ciphers and Key Space Size
Shannon also pointed out that perfect security implies that
#keys ≥ #messages (that is, |K| ≥ |L|)
notation: “#” means “number of”
observe that this is connected with H(K ) ≥ H(L)
Proof: by contradiction (reductio ad absurdum)
assume a cipher for which #keys < #messages and choose
some c0 which has nonzero probability, that is p(c0) > 0
if there are less keys than messages, then we can always find a
plaintext message l0 such that τ
′(c0, k) 6= l0 for every key k
therefore, for this l0 it holds that p(c0|l0) = 0
then the cipher cannot be perfect, because, by definition, a
perfect cipher would require p(c0|l0) = p(c0)
22/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditional Security and the Unicity Distance
Given the practical difficulty implied by the previous result,
Shannon also proposed to measure the secrecy of a practical
cipher in terms of key equivocation: H(K |C )
if H(K |C ) = 0, on average there is no uncertainty about the
key when the ciphertext is known
then the cryptographic method is breakable (in theory, and as
long as Mallet has enough computational resources. . . )
if H(K |C ) > 0 then there is uncertainty about the key
when H(K |C) = H(K) the uncertainty is maximum
23/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditional Security and the Unicity Distance
Given the practical difficulty implied by the previous result,
Shannon also proposed to measure the secrecy of a practical
cipher in terms of key equivocation: H(K |C )
if H(K |C ) = 0, on average there is no uncertainty about the
key when the ciphertext is known
then the cryptographic method is breakable (in theory, and as
long as Mallet has enough computational resources. . . )
if H(K |C ) > 0 then there is uncertainty about the key
when H(K |C) = H(K) the uncertainty is maximum
Assume that a block of n symbols is encrypted: cn = τ(ln, k)
typically, as the block length n increases H(K |C n) decreases
(as Mallet gathers more information he knows more about k)
definition: the unicity distance (n0) of a cipher is the smallest
block length, n, such that H(K |C n) = 0 (Shannon)
equivalently, n0 is the minimum amount of ciphertext symbols
needed by an attacker to unequivocally determine the key
23/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditional Security and Random Ciphers
The direct computation of the unicity distance n0 of a given
cipher is usually difficult
computing the equivocation requires a joint probabilistic model
of the key and the ciphertext, which can be hard to determine
24/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditional Security and Random Ciphers
The direct computation of the unicity distance n0 of a given
cipher is usually difficult
computing the equivocation requires a joint probabilistic model
of the key and the ciphertext, which can be hard to determine
However Shannon gave a way to approximate the unicity
distance assuming that we are dealing with a random cipher
definition (random cipher): a cipher in which the choice of k is
made uniformly at random among all possibilities in K
maximum entropy key, so there is no loss of generality
24/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unicity Distance (n0) Analysis
Assumptions made by Shannon in his unicity distance analysis:
The cryptographic method is a random cipher
Conditions for the cryptanalyst (Mallet):
ciphertext only attack
exhaustive cryptanalysis with unlimited processing power and
time: Mallet can try all keys (brute force)
when attempting decryption, the attacker can distinguish
nonsense blocks of information from meaningful ones
i.e., Mallet knows the language of the plaintext
25/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Redundancy of a Language
The unicity distance analysis makes use of the concept of
redundancy of the language the plaintext is written in
definition: the redundancy (ρ) of L, with |L| = s, is
ρ = log s − H(L) bits/symbol
example: in English, s = 26 symbols (alphabet size, skipping
spaces and punctuation); empirically, H(L) ≈ 1.5 bits/symbol,
and then ρ ≈ log 26− 1.5 = 3.2 bits/symbol
26/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Redundancy of a Language
The unicity distance analysis makes use of the concept of
redundancy of the language the plaintext is written in
definition: the redundancy (ρ) of L, with |L| = s, is
ρ = log s − H(L) bits/symbol
example: in English, s = 26 symbols (alphabet size, skipping
spaces and punctuation); empirically, H(L) ≈ 1.5 bits/symbol,
and then ρ ≈ log 26− 1.5 = 3.2 bits/symbol
Intuition: ρ is the amount of information/symbol that can be
removed from a sequence while preserving its message
i.e., what we remove in optimum source coding
a source modelled by L with alphabet L can be theoretically
compressed from log |L| = log s bits/symbol to at most H(L)
bits/symbol (as entropy is the ultimate compression limit)
the redundancy ρ is the difference between these two amounts
26/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Meaningful Messages and Plaintext Language Entropy
There are sn = |L|n possible n-symbol messages
27/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Meaningful Messages and Plaintext Language Entropy
There are sn = |L|n possible n-symbol messages
1 on average, 2nH(L) n-symbol messages can happen, each of
them with uniform probability 2−nH(L) (meaningful messages)
consequence of the law of large numbers; as n→∞
−
1
n
log p(L1, . . . , Ln)→ H(L)
(formally: asymptotic equipartition property)
27/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Meaningful Messages and Plaintext Language Entropy
There are sn = |L|n possible n-symbol messages
1 on average, 2nH(L) n-symbol messages can happen, each of
them with uniform probability 2−nH(L) (meaningful messages)
consequence of the law of large numbers; as n→∞
−
1
n
log p(L1, . . . , Ln)→ H(L)
(formally: asymptotic equipartition property)
2 the rest, i.e., sn − 2nH(L) n-symbol messages, have negligible
(≈ 0) probability (meaningless messages)
27/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Meaningful Messages and Plaintext Language Entropy
There are sn = |L|n possible n-symbol messages
1 on average, 2nH(L) n-symbol messages can happen, each of
them with uniform probability 2−nH(L) (meaningful messages)
consequence of the law of large numbers; as n→∞
−
1
n
log p(L1, . . . , Ln)→ H(L)
(formally: asymptotic equipartition property)
2 the rest, i.e., sn − 2nH(L) n-symbol messages, have negligible
(≈ 0) probability (meaningless messages)
sn
n︷ ︸︸ ︷
evioeqhrstmcgyevocmdzauvx
2nH(L)
theenemydoesknowthesystem
...
wheredidtheylearnthatsong
sn − 2nH(L)
evioeqhrstmcgyevocmdzauvx
..
.
rkvojyxoqpfimgwfgegliylfy
27/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
False Keys
Definition: a key kˆ is false (spurious) if, given cn = τ(ln, k),
lˆn = τ ′(cn, kˆ) is meaningful, but kˆ 6= k and lˆn 6= ln
28/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
False Keys
Definition: a key kˆ is false (spurious) if, given cn = τ(ln, k),
lˆn = τ ′(cn, kˆ) is meaningful, but kˆ 6= k and lˆn 6= ln
Let f (cn) be the number of false keys associated to
ciphertext cn; then, the average number of false keys is
E (f (Cn)) = (#keys − 1)×
#meaningful blocks
#blocks
28/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
False Keys
Definition: a key kˆ is false (spurious) if, given cn = τ(ln, k),
lˆn = τ ′(cn, kˆ) is meaningful, but kˆ 6= k and lˆn 6= ln
Let f (cn) be the number of false keys associated to
ciphertext cn; then, the average number of false keys is
E (f (Cn))
(∗)
= (#keys − 1)×
#meaningful blocks
#blocks
Notes:
(∗) random cipher assumption
28/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
False Keys
Definition: a key kˆ is false (spurious) if, given cn = τ(ln, k),
lˆn = τ ′(cn, kˆ) is meaningful, but kˆ 6= k and lˆn 6= ln
Let f (cn) be the number of false keys associated to
ciphertext cn; then, the average number of false keys is
E (f (Cn))
(∗)
= (#keys − 1)×
#meaningful blocks
#blocks
= (|K| − 1)×
2nH(L)
2n log s
= (|K| − 1)× 2−nρ
= 2log |K|−nρ − ǫ
Notes:
(∗) random cipher assumption
#blocks: sn = (2log s)n = 2n log s
ρ: redundancy of L
28/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unicity Distance
With this result, we define the unicity distance of a cipher as
n0 =
log |K|
ρ
n0 is the solution to log |K| − nρ = 0 (exponent in E (f (C
n)),
that is, a block size n such that E (f (C n)) < 1
29/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unicity Distance
With this result, we define the unicity distance of a cipher as
n0 =
log |K|
ρ
n0 is the solution to log |K| − nρ = 0 (exponent in E (f (C
n)),
that is, a block size n such that E (f (C n)) < 1
Therefore:
if n ≥ n0 → insecure system
on average, there are no false keys
enough information, or equivalently H(K |C n) = 0 (null
equivocation)
if n < n0 → unconditionally secure system
on average, there are false keys
not enough information for the attacker to uniquely determine
the key (and hence the cleartext)
→ In a good cipher n0 should be as large as possible
29/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Computational Security
Definition: a system is computationally secure when
1 the ciphertext contains sufficient information to decipher a
unique cleartext solution, but. . .
2 the best practical attack is technologically limited in terms of
processing power; thus, it is not guaranteed that Mallet will
succeed in a reasonable amount of time
alas, technology keeps evolving
30/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Computational Security
Definition: a system is computationally secure when
1 the ciphertext contains sufficient information to decipher a
unique cleartext solution, but. . .
2 the best practical attack is technologically limited in terms of
processing power; thus, it is not guaranteed that Mallet will
succeed in a reasonable amount of time
alas, technology keeps evolving
Shannon proposed that good practical encryption methods
(i.e., computationally secure) should implement two features:
diffusion: the statistical features of the plaintext should be
spread (diffused) across the ciphertext (e.g., in slide 16,
p(c) = 1/4 for all c)
confusion: the relationship between ciphertext, key and
plaintext should be involved (e.g., no linear functions)
30/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Computational Security and Key Length
The key length plays an important role in the security of
practical ciphers (remember n0)
m-bit (strong) encryption refers to the bit-length of the key
an exhaustive search (brute force) attack on an m-bit strong
cipher requires |K| = 2m trials (in principle, but see next slide)
an attack that “only” requires trying 2k < 2m keys to succeed
is said to have a complexity of 2k , or O(2k)
in a computationally secure method, trying all the keys in the
lowest complexity attack known should take far too long
However, bear in mind that if a cipher is inherently insecure,
then a long key will not improve its security
31/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Brute Force Attacks and Probability
Consider also a brute force attack against a practical cipher in
a scenario where Mallet has one (l , c) pair (known plaintext)
Chances are that Mallet will not have to try all |K| keys to
find k : it may be found before exahusting the search
Probability must be taken into account; for example,
assuming that keys are chosen uniformly at random:
a machine able to try all keys in a year would have 8% chance
of finding the correct one within a month (probability: 1/12)
a machine able to try all keys in a month would have 0.14%
chance of finding it in 1 hour (probability: 1/720)
even if the key is changed every hour, the same machine still
has a 63% probability of finding at least one of the keys:
p = 1−
(
1−
1
720
)720
= 0.63
32/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Key Management
Key management is also critical in practical security
(counter)example: Apple’s DiskLock used a cipher called DES
(studied later) to encrypt files, and stored the unencrypted key
next to the encrypted file
Also, consider the key space of a cipher with a 56-bit long key
if the implementation of this cipher only allows keys containing
alphabet characters (say alphabet size is s = 26), then we have
7 characters (bytes) and |K| goes down from 256 to 233
moreover, if the characters are from a language modelled by L
with H(L) = 1.5 bits/symbol, then the keyspace is 27H(L) ≈ 210
thus dictionary attacks usually give very good results: Klein
was able to break 25% of the passwords in a local network
33/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Practical Encryption and Source Coding
We have mentioned that some cryptanalyses look for frequent
patterns in cn (using histograms; more about this later)
these attacks can be thwarted if the symbols in ln have
uniform probabilities and no correlations
34/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Practical Encryption and Source Coding
We have mentioned that some cryptanalyses look for frequent
patterns in cn (using histograms; more about this later)
these attacks can be thwarted if the symbols in ln have
uniform probabilities and no correlations
Source coding approximates this scenario by eliminating
redundancy from the cleartext
it is a good idea to compress (that is, to source code) the
cleartext before encrypting it
decreasing redundancy (ρ) increases the unicity distance (n0)
even if Mallet is aware of compression (Kerckhoffs’ principle),
this increases the computational complexity of an attack
34/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
COMP 41280
Fe´lix Balado
School of Computer Science
University College Dublin
Outline of the Chapter
1 Basic Concepts and Models
2 Defining and Measuring Security
2/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Information Security Requirements
Privacy :
protected information should not be accessible to unauthorised
third parties
Authentication:
the recipient of some information should be able to verify its
origin and authorship
Integrity :
the recipient of a message should be able to verify that it has
not been forged or altered in transit
Non repudiation:
a message authenticated by a trusted third party cannot be
repudiated at a later stage by its sender
Cryptography can deal with aspects of all these requirements
3/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Shannon’s Model for Cryptography (1948)
Source Encryption Decryption Destination
KeyKey
m
es
sa
g
e
m
es
sa
g
e
en
cr
yp
te
d
m
es
sa
g
e
4/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Shannon’s Model for Cryptography (1948)
Alice Encryption Decryption Bob
KeyKey
m
es
sa
g
e
m
es
sa
g
e
en
cr
yp
te
d
m
es
sa
g
e
4/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Notation, Terminology and Basic Concepts
Basic encryption/decryption operation flow:
l →
τ
c →
τ ′
l
l : cleartext, plaintext, unencrypted/clear message
c : ciphertext, encrypted/ciphered message
τ(·, ·) and τ ′(·, ·): cipher, encryption/cryptographic
scheme/system/method/algorithm
these are invertible functions of l and c , respectively, which
also depend on a second parameter, k
k : encryption/decryption key
encryption of l using k : c = τ(l , k)
decryption of c using k : l = τ ′(c , k) = τ ′(τ(l , k), k):
5/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Notation, Terminology and Basic Concepts
The wrong decryption key should lead to a wrong plaintext
if k ′ 6= k then
τ ′(τ(l , k), k ′) 6= l
When we encrypt a source of information we can model the
plaintext using a r.v. L, and so l ∈ L
the choice of the key is also modelled by a random variable K ,
and so k ∈ K
6/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Notation, Terminology and Basic Concepts
The wrong decryption key should lead to a wrong plaintext
if k ′ 6= k then
τ ′(τ(l , k), k ′) 6= l
When we encrypt a source of information we can model the
plaintext using a r.v. L, and so l ∈ L
the choice of the key is also modelled by a random variable K ,
and so k ∈ K
In many cryptographic methods τ(·, k) does not operate on a
single symbol, but on a block of n symbols; we will use special
notations in this situation:
cn = τ(ln, k)
c = τ(l, k)
however we will simply use c = τ(l , k) if clear from the context
6/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Privacy Threats
Mallet
Alice Encryption Decryption Bob
KeyKey
Attacker’s typical nicknames:
Mallet, Mallory: malicious man in the middle
Eve: eavesdropper
Trudy: intruder
7/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (I)
Kerckhoffs principle: it is always safer to assume that all the
details of the cryptographic scheme are publicly known
the encryption system (τ, τ ′) is public, static, not modifiable
the key (k) is private, dynamic, modifiable
Only the key can remain secret
security through obscurity (i.e., by assuming that Mallet does
not know τ, τ ′) is a very bad idea in the long run
Shannon: “the enemy knows the system”
8/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (II)
Cryptanalysis: gathering information about the secret
communication between Alice and Bob
point of view of Mallet
An attack to a cryptosystem is an attempt to cryptanalyse it
examples of successful attacks:
recover cleartext l , either completely or partially
recover the key k (in which case future communications with
that key will also be compromised)
9/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (II)
Cryptanalysis: gathering information about the secret
communication between Alice and Bob
point of view of Mallet
An attack to a cryptosystem is an attempt to cryptanalyse it
examples of successful attacks:
recover cleartext l , either completely or partially
recover the key k (in which case future communications with
that key will also be compromised)
Mallet might also carry out active attacks
example: replace genuine encrypted message c by forged
encrypted message cF (without necessarily obtaining l or k)
9/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (III)
Cryptanalysis is as much a science as an art
sometimes Mallet can attempt a systematic strategy
at other times no specific methodology is known
Mallet can sometimes exploit available side information:
examples:
message language and/or content: common sentences,
frequency of letters, digrams, trigrams,. . .
messsage format (headers, footers, tags, etc)
time taken to carry out encryption/decryption algorithm
power consumption when algorithm is run
Without side information, the attacker could always attempt
exhaustive analysis (brute force): try all keys in key space
10/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (Toy Example)
Decipher the ciphertext below, knowing that ci = τ(li , k) is a
4-character permutation of the English plaintext li
c = c1‖c2‖c3=’rdfoatfielop’
(‖: concatenation)
in this toy example, applying brute force is easy, as there are
only |K| = 4! = 24 keys
(see transposition ciphers in next lecture)
11/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis (Toy Example)
Decipher the ciphertext below, knowing that ci = τ(li , k) is a
4-character permutation of the English plaintext li
c = c1‖c2‖c3=’rdfoatfielop’
(‖: concatenation)
in this toy example, applying brute force is easy, as there are
only |K| = 4! = 24 keys
(see transposition ciphers in next lecture)
however, the attack is easier if side information “plaintext
message conveys car makes” is available to Mallet:
l = l1‖l2‖l3=’fordfiatopel’
Modern ciphers are of course more sophisticated than this
11/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis Models (I)
What are the scenarios in which Mallet can find himself?
1 Ciphertext only: Mallet has one or more ciphertexts c
Mallet
l c
Alice Encryption Decryption Bob
k,l
12/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis Models (I)
What are the scenarios in which Mallet can find himself?
1 Ciphertext only: Mallet has one or more ciphertexts c
Mallet
l c
Alice Encryption Decryption Bob
k,l
2 known plaintext: Mallet has a number of (l , c) pairs
Mallet
l c
Alice Encryption Decryption Bob
k
12/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Feasibility of Known Plaintext Scenario
It might appear that the known plaintext scenario is
far-fetched, but it is more frequent than one might imagine
Mallet can many times know partial information about the l
corresponding to c , leading to known plaintext attacks
example: Mallet may know the format of headers or footers
he may know that a plaintext email encrypted on a given date
and time starts as “Date: Tue, 29 Feb 2016 13:44”
similar strategies are possible with other types of formatting
A historical example of a known plaintext attack occurred in
WWII in the Sahara desert
an isolated German outpost radioed every day the message
“nothing new to report” encrypted with the key for that day
the Allies (i.e. Mallet) caught wind of this, and so they had
one (l , c) pair every day to try to guess that key (and thus
decrypt c ’s from other outposts from the same day)
13/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis Models (II)
3 Chosen cleartext: Mallet can encrypt plaintext using the
encryption block as a black box (i.e. without knowing k) to
produce (l , c) pairs on demand
Mallet
l c
Encryption Decryption
k
scenario 1: encryption system has fallen to the enemy as a
black box (WWII: Enigma boxes in captured German U-Boats)
scenario 2: authentication scheme in which Bob sends a
random l to Alice; she sends him back τ(l , k) to prove she also
has k (consider what happens if Mallet can impersonate Bob)
14/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Cryptanalysis Models (II)
3 Chosen cleartext: Mallet can encrypt plaintext using the
encryption block as a black box (i.e. without knowing k) to
produce (l , c) pairs on demand
Mallet
l c
Encryption Decryption
k
scenario 1: encryption system has fallen to the enemy as a
black box (WWII: Enigma boxes in captured German U-Boats)
scenario 2: authentication scheme in which Bob sends a
random l to Alice; she sends him back τ(l , k) to prove she also
has k (consider what happens if Mallet can impersonate Bob)
4 Chosen ciphertext: Mallet can decrypt “ciphertext” using the
decryption box (without knowing k) to produce (l , c) pairs
14/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Outline of the Chapter
1 Basic Concepts and Models
2 Defining and Measuring Security
15/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Probability and Cipher Security: Toy Example
Why does probability matter in terms of the security of a cipher?
Suppose that L = {l1, l2}, i.e. only two plaintext symbols
assume the pmf: pL(l1) =
1
4 and pL(l2) =
3
4
this pmf is given by the plaintext language
Suppose that K = {k1, k2, k3}, i.e. three possible keys
assume the pmf: pK (k1) =
1
2 , pK (k2) = pK (k3) =
1
4
this pmf depends on how the key is chosen
Now suppose that C = {c1, c2, c3, c4}, and that τ(l , k) is:
τ(l , k) k1 k2 k3
l1 c1 c2 c3
l2 c2 c3 c4
16/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Probability and Cipher Security: Toy Example
Why does probability matter in terms of the security of a cipher?
Suppose that L = {l1, l2}, i.e. only two plaintext symbols
assume the pmf: pL(l1) =
1
4 and pL(l2) =
3
4
this pmf is given by the plaintext language
Suppose that K = {k1, k2, k3}, i.e. three possible keys
assume the pmf: pK (k1) =
1
2 , pK (k2) = pK (k3) =
1
4
this pmf depends on how the key is chosen
Now suppose that C = {c1, c2, c3, c4}, and that τ(l , k) is:
τ(l , k) k1 k2 k3
l1 c1 c2 c3
l2 c2 c3 c4
With the public information above, anyone can compute
p(c) =
∑
l∈L,k∈K p(c |l , k)p(l , k), for c ∈ C
we just have to marginalise the joint pmf p(c , l , k)
pC (c1) =
1
8 , pC (c2) =
7
16 , pC (c3) =
1
4 , pC (c4) =
3
16
16/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Probability and Cipher Security: Toy Example
Consider now a ciphertext only attack
Exploiting Bayes’ rule, Mallet can make guesses that have
maximum a posteriori (MAP) likelihood
Using pL|C (l |c) =
pC |L(c|l)pL(l)
pC (c)
he can compute the following
conditional probabilities:
pL|C (l1|c1) = 1
→ if the attacker observes C = c1, he knows L = l1 and K = k1
pL|C (l1|c2) =
1
7
→ if the attacker observes C = c2, he guesses L = l2 and K = k1
pL|C (l1|c3) =
1
4
→ if the attacker observes C = c3, he guesses L = l2 and K = k2
pL|C (l1|c4) = 0
→ if the attacker observes C = c4, he knows L = l2 and K = k3
17/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Probability and Cipher Security: Toy Example
Consider now a ciphertext only attack
Exploiting Bayes’ rule, Mallet can make guesses that have
maximum a posteriori (MAP) likelihood
Using pL|C (l |c) =
pC |L(c|l)pL(l)
pC (c)
he can compute the following
conditional probabilities:
pL|C (l1|c1) = 1
→ if the attacker observes C = c1, he knows L = l1 and K = k1
pL|C (l1|c2) =
1
7
→ if the attacker observes C = c2, he guesses L = l2 and K = k1
pL|C (l1|c3) =
1
4
→ if the attacker observes C = c3, he guesses L = l2 and K = k2
pL|C (l1|c4) = 0
→ if the attacker observes C = c4, he knows L = l2 and K = k3
→ Bottom line: ciphertext can leak information to attacker
this should be avoided in a good encryption system
17/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Encryption Security
There are two types of encryption methods as regards their
vulnerability to cryptanalysis
1 Insecure methods: τ(·, ·) and τ ′(·, ·) should not be “simple”
functions, such as, for instance, linear functions
2 Secure methods
a) unconditionally secure: it is impossible that k can be found by
Mallet independently of available processing power and time
an unconditionally secure cipher is called a perfect cipher, and
we say that it provides perfect secrecy
b) computationally secure: it is theoretically possible for an
attacker to find k , but the methods that would allow him/her
to do so cannot be implemented in practice or would take eons
to complete
18/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems (Perfect Cipher)
Criterion (Shannon): in an unconditionally secure system, or
perfect cipher, L and C must be statistically independent:
pL|C (l |c) = pL(l), for all l , c
equivalently: pL,C (l , c) = pL(l)pC (c)
19/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems (Perfect Cipher)
Criterion (Shannon): in an unconditionally secure system, or
perfect cipher, L and C must be statistically independent:
pL|C (l |c) = pL(l), for all l , c
equivalently: pL,C (l , c) = pL(l)pC (c)
but. . . how can ciphertext and plaintext be independent?
after all, if we know the key then the plaintext completely
determines the ciphertext
→ the independence between C and L is from the point of view
of Mallet (who is unaware of the key)
19/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems (Perfect Cipher)
Criterion (Shannon): in an unconditionally secure system, or
perfect cipher, L and C must be statistically independent:
pL|C (l |c) = pL(l), for all l , c
equivalently: pL,C (l , c) = pL(l)pC (c)
but. . . how can ciphertext and plaintext be independent?
after all, if we know the key then the plaintext completely
determines the ciphertext
→ the independence between C and L is from the point of view
of Mallet (who is unaware of the key)
In terms of mutual information, it must also hold for a perfect
cipher that I (L;C ) = 0
interpretation: on average, the ciphertext does not reveal any
information about the plaintext
also I (K ;C ) = 0 (as H(K |C ) = H(K ) with perfect security)
19/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Unconditional security implies that H(K ) ≥ H(C ); proof :
apply the chain rule of entropy to H(C , L,K ) in two ways:
H(C , L,K) = H(L,K) + H(C |L,K)
H(C , L,K) = H(C , L) + H(K |C , L)
20/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Unconditional security implies that H(K ) ≥ H(C ); proof :
apply the chain rule of entropy to H(C , L,K ) in two ways:
H(C , L,K) = H(L,K) + 0
H(C , L,K) = H(C , L) + H(K |C , L) ≥ H(C , L)
notes:
H(C |L,K) = 0 because of Kerckhoffs principle
entropy is always nonnegative
20/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Unconditional security implies that H(K ) ≥ H(C ); proof :
apply the chain rule of entropy to H(C , L,K ) in two ways:
H(C , L,K) = H(L,K) + 0
H(C , L,K) = H(C , L) + H(K |C , L) ≥ H(C , L)
notes:
H(C |L,K) = 0 because of Kerckhoffs principle
entropy is always nonnegative
finally, apply again the chain rule to H(L,K ) and H(C , L) and
take into account that
H(L|K) = H(L), as message and key are independent
H(C |L) = H(C) with unconditional security
20/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Unconditional security implies that H(K ) ≥ H(C ); proof :
apply the chain rule of entropy to H(C , L,K ) in two ways:
H(C , L,K) = H(L,K) + 0
H(C , L,K) = H(C , L) + H(K |C , L) ≥ H(C , L)
notes:
H(C |L,K) = 0 because of Kerckhoffs principle
entropy is always nonnegative
finally, apply again the chain rule to H(L,K ) and H(C , L) and
take into account that
H(L|K) = H(L), as message and key are independent
H(C |L) = H(C) with unconditional security
check using entropy: the scheme in slide 16 cannot be perfect
20/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = H(C |L,K ) + H(L,K ) = H(L|C ,K ) + H(C ,K )
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = 0 + H(L,K ) = 0 + H(C ,K )
note:
H(C |L,K) = 0 and H(L|C ,K) = 0 (Kerckhoffs’ principle)
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = 0 + H(L,K ) = 0 + H(C ,K )
note:
H(C |L,K) = 0 and H(L|C ,K) = 0 (Kerckhoffs’ principle)
applying again the chain rule to H(L,K ) and H(C ,K ):
H(L|K ) + H(K ) = H(C |K ) + H(K )
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = 0 + H(L,K ) = 0 + H(C ,K )
note:
H(C |L,K) = 0 and H(L|C ,K) = 0 (Kerckhoffs’ principle)
applying again the chain rule to H(L,K ) and H(C ,K ):
H(L|K ) + H(K ) = H(C |K ) + H(K )
finally use H(L|K ) = H(L) and H(C |K ) ≤ H(C ) (conditioning
cannot increase entropy)
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditionally Secure Systems: Implications
Moreover, for any cipher H(C ) ≥ H(L); proof :
write H(C , L,K ) in two different ways using the chain rule:
H(C , L,K ) = 0 + H(L,K ) = 0 + H(C ,K )
note:
H(C |L,K) = 0 and H(L|C ,K) = 0 (Kerckhoffs’ principle)
applying again the chain rule to H(L,K ) and H(C ,K ):
H(L|K ) + H(K ) = H(C |K ) + H(K )
finally use H(L|K ) = H(L) and H(C |K ) ≤ H(C ) (conditioning
cannot increase entropy)
Interpretation: in a perfect cipher H(K ) ≥ H(C ) ≥ H(L), so
it is clear that a low-entropy key will be bad for security
21/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Perfect Ciphers and Key Space Size
Shannon also pointed out that perfect security implies that
#keys ≥ #messages (that is, |K| ≥ |L|)
notation: “#” means “number of”
observe that this is connected with H(K ) ≥ H(L)
22/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Perfect Ciphers and Key Space Size
Shannon also pointed out that perfect security implies that
#keys ≥ #messages (that is, |K| ≥ |L|)
notation: “#” means “number of”
observe that this is connected with H(K ) ≥ H(L)
Proof: by contradiction (reductio ad absurdum)
assume a cipher for which #keys < #messages and choose
some c0 which has nonzero probability, that is p(c0) > 0
if there are less keys than messages, then we can always find a
plaintext message l0 such that τ
′(c0, k) 6= l0 for every key k
22/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Perfect Ciphers and Key Space Size
Shannon also pointed out that perfect security implies that
#keys ≥ #messages (that is, |K| ≥ |L|)
notation: “#” means “number of”
observe that this is connected with H(K ) ≥ H(L)
Proof: by contradiction (reductio ad absurdum)
assume a cipher for which #keys < #messages and choose
some c0 which has nonzero probability, that is p(c0) > 0
if there are less keys than messages, then we can always find a
plaintext message l0 such that τ
′(c0, k) 6= l0 for every key k
therefore, for this l0 it holds that p(c0|l0) = 0
then the cipher cannot be perfect, because, by definition, a
perfect cipher would require p(c0|l0) = p(c0)
22/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditional Security and the Unicity Distance
Given the practical difficulty implied by the previous result,
Shannon also proposed to measure the secrecy of a practical
cipher in terms of key equivocation: H(K |C )
if H(K |C ) = 0, on average there is no uncertainty about the
key when the ciphertext is known
then the cryptographic method is breakable (in theory, and as
long as Mallet has enough computational resources. . . )
if H(K |C ) > 0 then there is uncertainty about the key
when H(K |C) = H(K) the uncertainty is maximum
23/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditional Security and the Unicity Distance
Given the practical difficulty implied by the previous result,
Shannon also proposed to measure the secrecy of a practical
cipher in terms of key equivocation: H(K |C )
if H(K |C ) = 0, on average there is no uncertainty about the
key when the ciphertext is known
then the cryptographic method is breakable (in theory, and as
long as Mallet has enough computational resources. . . )
if H(K |C ) > 0 then there is uncertainty about the key
when H(K |C) = H(K) the uncertainty is maximum
Assume that a block of n symbols is encrypted: cn = τ(ln, k)
typically, as the block length n increases H(K |C n) decreases
(as Mallet gathers more information he knows more about k)
definition: the unicity distance (n0) of a cipher is the smallest
block length, n, such that H(K |C n) = 0 (Shannon)
equivalently, n0 is the minimum amount of ciphertext symbols
needed by an attacker to unequivocally determine the key
23/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditional Security and Random Ciphers
The direct computation of the unicity distance n0 of a given
cipher is usually difficult
computing the equivocation requires a joint probabilistic model
of the key and the ciphertext, which can be hard to determine
24/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unconditional Security and Random Ciphers
The direct computation of the unicity distance n0 of a given
cipher is usually difficult
computing the equivocation requires a joint probabilistic model
of the key and the ciphertext, which can be hard to determine
However Shannon gave a way to approximate the unicity
distance assuming that we are dealing with a random cipher
definition (random cipher): a cipher in which the choice of k is
made uniformly at random among all possibilities in K
maximum entropy key, so there is no loss of generality
24/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unicity Distance (n0) Analysis
Assumptions made by Shannon in his unicity distance analysis:
The cryptographic method is a random cipher
Conditions for the cryptanalyst (Mallet):
ciphertext only attack
exhaustive cryptanalysis with unlimited processing power and
time: Mallet can try all keys (brute force)
when attempting decryption, the attacker can distinguish
nonsense blocks of information from meaningful ones
i.e., Mallet knows the language of the plaintext
25/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Redundancy of a Language
The unicity distance analysis makes use of the concept of
redundancy of the language the plaintext is written in
definition: the redundancy (ρ) of L, with |L| = s, is
ρ = log s − H(L) bits/symbol
example: in English, s = 26 symbols (alphabet size, skipping
spaces and punctuation); empirically, H(L) ≈ 1.5 bits/symbol,
and then ρ ≈ log 26− 1.5 = 3.2 bits/symbol
26/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Redundancy of a Language
The unicity distance analysis makes use of the concept of
redundancy of the language the plaintext is written in
definition: the redundancy (ρ) of L, with |L| = s, is
ρ = log s − H(L) bits/symbol
example: in English, s = 26 symbols (alphabet size, skipping
spaces and punctuation); empirically, H(L) ≈ 1.5 bits/symbol,
and then ρ ≈ log 26− 1.5 = 3.2 bits/symbol
Intuition: ρ is the amount of information/symbol that can be
removed from a sequence while preserving its message
i.e., what we remove in optimum source coding
a source modelled by L with alphabet L can be theoretically
compressed from log |L| = log s bits/symbol to at most H(L)
bits/symbol (as entropy is the ultimate compression limit)
the redundancy ρ is the difference between these two amounts
26/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Meaningful Messages and Plaintext Language Entropy
There are sn = |L|n possible n-symbol messages
27/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Meaningful Messages and Plaintext Language Entropy
There are sn = |L|n possible n-symbol messages
1 on average, 2nH(L) n-symbol messages can happen, each of
them with uniform probability 2−nH(L) (meaningful messages)
consequence of the law of large numbers; as n→∞
−
1
n
log p(L1, . . . , Ln)→ H(L)
(formally: asymptotic equipartition property)
27/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Meaningful Messages and Plaintext Language Entropy
There are sn = |L|n possible n-symbol messages
1 on average, 2nH(L) n-symbol messages can happen, each of
them with uniform probability 2−nH(L) (meaningful messages)
consequence of the law of large numbers; as n→∞
−
1
n
log p(L1, . . . , Ln)→ H(L)
(formally: asymptotic equipartition property)
2 the rest, i.e., sn − 2nH(L) n-symbol messages, have negligible
(≈ 0) probability (meaningless messages)
27/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Meaningful Messages and Plaintext Language Entropy
There are sn = |L|n possible n-symbol messages
1 on average, 2nH(L) n-symbol messages can happen, each of
them with uniform probability 2−nH(L) (meaningful messages)
consequence of the law of large numbers; as n→∞
−
1
n
log p(L1, . . . , Ln)→ H(L)
(formally: asymptotic equipartition property)
2 the rest, i.e., sn − 2nH(L) n-symbol messages, have negligible
(≈ 0) probability (meaningless messages)
sn
n︷ ︸︸ ︷
evioeqhrstmcgyevocmdzauvx
2nH(L)
theenemydoesknowthesystem
...
wheredidtheylearnthatsong
sn − 2nH(L)
evioeqhrstmcgyevocmdzauvx
..
.
rkvojyxoqpfimgwfgegliylfy
27/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
False Keys
Definition: a key kˆ is false (spurious) if, given cn = τ(ln, k),
lˆn = τ ′(cn, kˆ) is meaningful, but kˆ 6= k and lˆn 6= ln
28/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
False Keys
Definition: a key kˆ is false (spurious) if, given cn = τ(ln, k),
lˆn = τ ′(cn, kˆ) is meaningful, but kˆ 6= k and lˆn 6= ln
Let f (cn) be the number of false keys associated to
ciphertext cn; then, the average number of false keys is
E (f (Cn)) = (#keys − 1)×
#meaningful blocks
#blocks
28/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
False Keys
Definition: a key kˆ is false (spurious) if, given cn = τ(ln, k),
lˆn = τ ′(cn, kˆ) is meaningful, but kˆ 6= k and lˆn 6= ln
Let f (cn) be the number of false keys associated to
ciphertext cn; then, the average number of false keys is
E (f (Cn))
(∗)
= (#keys − 1)×
#meaningful blocks
#blocks
Notes:
(∗) random cipher assumption
28/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
False Keys
Definition: a key kˆ is false (spurious) if, given cn = τ(ln, k),
lˆn = τ ′(cn, kˆ) is meaningful, but kˆ 6= k and lˆn 6= ln
Let f (cn) be the number of false keys associated to
ciphertext cn; then, the average number of false keys is
E (f (Cn))
(∗)
= (#keys − 1)×
#meaningful blocks
#blocks
= (|K| − 1)×
2nH(L)
2n log s
= (|K| − 1)× 2−nρ
= 2log |K|−nρ − ǫ
Notes:
(∗) random cipher assumption
#blocks: sn = (2log s)n = 2n log s
ρ: redundancy of L
28/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unicity Distance
With this result, we define the unicity distance of a cipher as
n0 =
log |K|
ρ
n0 is the solution to log |K| − nρ = 0 (exponent in E (f (C
n)),
that is, a block size n such that E (f (C n)) < 1
29/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Unicity Distance
With this result, we define the unicity distance of a cipher as
n0 =
log |K|
ρ
n0 is the solution to log |K| − nρ = 0 (exponent in E (f (C
n)),
that is, a block size n such that E (f (C n)) < 1
Therefore:
if n ≥ n0 → insecure system
on average, there are no false keys
enough information, or equivalently H(K |C n) = 0 (null
equivocation)
if n < n0 → unconditionally secure system
on average, there are false keys
not enough information for the attacker to uniquely determine
the key (and hence the cleartext)
→ In a good cipher n0 should be as large as possible
29/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Computational Security
Definition: a system is computationally secure when
1 the ciphertext contains sufficient information to decipher a
unique cleartext solution, but. . .
2 the best practical attack is technologically limited in terms of
processing power; thus, it is not guaranteed that Mallet will
succeed in a reasonable amount of time
alas, technology keeps evolving
30/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Computational Security
Definition: a system is computationally secure when
1 the ciphertext contains sufficient information to decipher a
unique cleartext solution, but. . .
2 the best practical attack is technologically limited in terms of
processing power; thus, it is not guaranteed that Mallet will
succeed in a reasonable amount of time
alas, technology keeps evolving
Shannon proposed that good practical encryption methods
(i.e., computationally secure) should implement two features:
diffusion: the statistical features of the plaintext should be
spread (diffused) across the ciphertext (e.g., in slide 16,
p(c) = 1/4 for all c)
confusion: the relationship between ciphertext, key and
plaintext should be involved (e.g., no linear functions)
30/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Computational Security and Key Length
The key length plays an important role in the security of
practical ciphers (remember n0)
m-bit (strong) encryption refers to the bit-length of the key
an exhaustive search (brute force) attack on an m-bit strong
cipher requires |K| = 2m trials (in principle, but see next slide)
an attack that “only” requires trying 2k < 2m keys to succeed
is said to have a complexity of 2k , or O(2k)
in a computationally secure method, trying all the keys in the
lowest complexity attack known should take far too long
However, bear in mind that if a cipher is inherently insecure,
then a long key will not improve its security
31/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Brute Force Attacks and Probability
Consider also a brute force attack against a practical cipher in
a scenario where Mallet has one (l , c) pair (known plaintext)
Chances are that Mallet will not have to try all |K| keys to
find k : it may be found before exahusting the search
Probability must be taken into account; for example,
assuming that keys are chosen uniformly at random:
a machine able to try all keys in a year would have 8% chance
of finding the correct one within a month (probability: 1/12)
a machine able to try all keys in a month would have 0.14%
chance of finding it in 1 hour (probability: 1/720)
even if the key is changed every hour, the same machine still
has a 63% probability of finding at least one of the keys:
p = 1−
(
1−
1
720
)720
= 0.63
32/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Key Management
Key management is also critical in practical security
(counter)example: Apple’s DiskLock used a cipher called DES
(studied later) to encrypt files, and stored the unencrypted key
next to the encrypted file
Also, consider the key space of a cipher with a 56-bit long key
if the implementation of this cipher only allows keys containing
alphabet characters (say alphabet size is s = 26), then we have
7 characters (bytes) and |K| goes down from 256 to 233
moreover, if the characters are from a language modelled by L
with H(L) = 1.5 bits/symbol, then the keyspace is 27H(L) ≈ 210
thus dictionary attacks usually give very good results: Klein
was able to break 25% of the passwords in a local network
33/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Practical Encryption and Source Coding
We have mentioned that some cryptanalyses look for frequent
patterns in cn (using histograms; more about this later)
these attacks can be thwarted if the symbols in ln have
uniform probabilities and no correlations
34/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
Practical Encryption and Source Coding
We have mentioned that some cryptanalyses look for frequent
patterns in cn (using histograms; more about this later)
these attacks can be thwarted if the symbols in ln have
uniform probabilities and no correlations
Source coding approximates this scenario by eliminating
redundancy from the cleartext
it is a good idea to compress (that is, to source code) the
cleartext before encrypting it
decreasing redundancy (ρ) increases the unicity distance (n0)
even if Mallet is aware of compression (Kerckhoffs’ principle),
this increases the computational complexity of an attack
34/34 2nd Chapter: Fundamentals of Cryptography © UCD 2023
