CM30173/50210: Cryptography Part I \(cont.\)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad Part I
Introduction to the problem (cont.)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
A fundamental assumption
Attack models
Security
One-time pad
CM30173/50210
Cryptography
Key ideas
Classical
cryptography
Secure communication
Alice Bob
Oscar
PlaintextPlaintext
Encryption Decryption
Unsecured channel
ek(x) = y dk(y) = x
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
What do we mean by “secure”?
Recall that, for a cryptosystem we need:
1 to be able to e!ciently compute the encryption
and the decryption functions
2 that an unauthorised party should not be able to
determine the key or the plaintext
We assume that an observer has access to all
communications between sender and receiver.
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
One possible objective
Brute force attack
An exhaustive search of a keyspace involves trying all
possible decryption keys.
Clearly we require such an attack to be
computationally infeasible or impossible.
Can we design a cryptosystem where this is the
best possible attack?
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
A fundamental assumption
Attack models
Security
One-time pad
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Kerckho!s
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Kerckho!s’ desiderata (1883)
1 The system should be, if not theoretically
unbreakable, unbreakable in practice.
(translation from Handbook of Applied Cryptography)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Kerckho!s’ desiderata (1883)
1 The system should be, if not theoretically
unbreakable, unbreakable in practice.
2 Compromise of the system details should not
inconvenience the correspondents.
(translation from Handbook of Applied Cryptography)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Kerckho!s’ desiderata (1883)
1 The system should be, if not theoretically
unbreakable, unbreakable in practice.
2 Compromise of the system details should not
inconvenience the correspondents.
3 The key should be rememberable without notes
and easily changed.
(translation from Handbook of Applied Cryptography)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Kerckho!s’ desiderata (1883)
1 The system should be, if not theoretically
unbreakable, unbreakable in practice.
2 Compromise of the system details should not
inconvenience the correspondents.
3 The key should be rememberable without notes
and easily changed.
4 The cryptogram should be transmissible by
telegraphy.
(translation from Handbook of Applied Cryptography)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Kerckho!s’ desiderata (1883)
1 The system should be, if not theoretically
unbreakable, unbreakable in practice.
2 Compromise of the system details should not
inconvenience the correspondents.
3 The key should be rememberable without notes
and easily changed.
4 The cryptogram should be transmissible by
telegraphy.
5 The encryption apparatus should be portable and
operable by a single person.
(translation from Handbook of Applied Cryptography)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Kerckho!s’ desiderata (1883)
1 The system should be, if not theoretically
unbreakable, unbreakable in practice.
2 Compromise of the system details should not
inconvenience the correspondents.
3 The key should be rememberable without notes
and easily changed.
4 The cryptogram should be transmissible by
telegraphy.
5 The encryption apparatus should be portable and
operable by a single person.
6 The system should be easy, requiring neither the
knowledge of a long list of rules nor mental strain.
(translation from Handbook of Applied Cryptography)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Kerckho!s’ desiderata (1883)
1 The system should be, if not theoretically
unbreakable, unbreakable in practice.
2 Compromise of the system details should not
inconvenience the correspondents.
3 The key should be rememberable without notes
and easily changed.
4 The cryptogram should be transmissible by
telegraphy.
5 The encryption apparatus should be portable and
operable by a single person.
6 The system should be easy, requiring neither the
knowledge of a long list of rules nor mental strain.
(translation from Handbook of Applied Cryptography)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Kerckho!s’ principle
Point 2 is often reworded as
The security of the system should reside only in
the key.
This is our fundamental assumption.
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
A fundamental assumption
Attack models
Security
One-time pad
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Ciphertext only attack
Definition
Given: y1 = ek(x1), . . . , yi = ek(xi)
Deduce:
k,
an algorithm that outputs xi+1 given
yi+1 = ek(xi+1) or
x1, . . . , xi
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Known plaintext attack
Definition
Given: x1, y1 = ek(x1), . . . , xi, yi = ek(xi)
Deduce:
k or
an algorithm that outputs xi+1 given
yi+1 = ek(xi+1)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Chosen plaintext attack
Definition
Given: x1, y1 = ek(x1), . . . , xi, yi = ek(xi) where the
attacker has chosen x1, . . . , xi
Deduce:
k or
an algorithm that outputs xi+1 given
yi+1 = ek(xi+1)
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Adaptive chosen plaintext attack
This is a special case of the chosen plaintext attack.
The attacker can modify his choice of plaintexts based
on the results of earlier pairs.
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Chosen ciphertext attack
Definition
Given: y1, x1 = dk(y1), . . . , yi, xi = dk(yi)
Deduce: k
CM30173/50210:
Cryptography
Part I (cont.)
A fundamental
assumption
Attack models
Security
One-time pad
Non cryptographic attacks…
…can be more e”ective:
Bribery
Physical theft
Blackmail
Threats
Torture…
Introduction to the problem (cont.)
A fundamental assumption
Attack models
Security
One-time pad