Transcript General
Detecting Eavesdropping
A Solution
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.1)
Quantum Cryptography
Quantum Computing
Quantum Cryptography
Can we use quantum effects to
detect passive eavesdropping?
Algorithms for key distribution, coin
flipping, bit commitment, oblivious
transfer, etc
Particles (e.g. Photons) exist in N
places at once with different
probabilities.
In 1994 Peter Schor devised a
quantum computing algorithm to
factorise large numbers in polynomial
time!
We can measure position or velocity
but not both
(Un)fortunately no-one is yet able
how to build a suitable quantum
computer.
But we can use this uncertainty to
generate a key!
Network Security (N. Dulay & M.
Huth)
Quantum world is uncertain.
Classical Cryptography (2.2)
Polarisation: Noddy's guide
Photons vibrate in some direction
e.g.
Up and down
Left and right
At some angle
Polarised when many photons
vibrate in the same direction
Polarisation filters only allow
photons polarised in a defined
direction (angle) through, e.g
100%
0%
50%
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.3)
Wiesner's Quantum Money
Each note has a printed serial number and a set of "photon-stores" that hold differently
polarised photons.
Only the Bank knows the polarisations for any serial number.
We can produce counterfeit notes if we can measure the correct polarisations. But to do
this we need to guess the correct orientations.
DoC Bank £100
Network Security (N. Dulay & M.
Huth)
22AC320FR00
Classical Cryptography (2.4)
Wiesner's Quantum Money
Filter
Result
100%
0%
Network Security (N. Dulay & M.
Huth)
50%
?
50%
?
Classical Cryptography (2.5)
Basis
Polarisation measured in a basis.
Basis consists of 2 orthogonal
directions, e.g.
If polarisation is read in a
matching basis -> we learn
polarisation
If read in wrong basis -> we learn
a random polarisation!
Rectilinear
Okay
Diagonal
Random
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.6)
Bennett & Brassard Protocol
Alice sends pulses to Bob. Bob uses polarisation detectors with randomly set basis
Bob tells Alice his settings. Alice tells Bob which settings were correct.
Settings map to 0 and 1’s, e.g. — and / map to 0, while | and \ map to 1.
Alice and Bob only use those settings as a secret key (or 1-time pad key)
1 1
0
1
0/1
0/1
Network Security (N. Dulay & M.
Huth)
0
0/1
0
0/1
1
1
1 1
1
0
0/1
0
Classical Cryptography (2.7)
Protocol Continued
Eavesdropper Eve also does not know
correct polarisations, so like Bob will
pick wrong basis 50% of the time.
Knowing Bob's settings after the
event does not help, because she will
have measured half of them
incorrectly.
To detect Eve, Alice and Bob only
need to compare a few bits in
their message.
Worse still, Eve will introduce
errors, which Alice & Bob can detect,
since Eve’s wrong guesses will change
polarisation of pulses
If no errors: Use rest of
message
Network Security (N. Dulay & M.
Huth)
If errors found then we have an
Eavesdropper.
Classical Cryptography (2.8)
Reading
Simon Singh, The Code Book, Chapter 8
Quantum Computing Course (482), Next term
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.9)
Classical Cryptography
Michael Huth
[email protected]
www.doc.ic.ac.uk/~mrh/430/
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.10)
Why Cryptography?
CONFIDENTIALITY
Keep information secret
AUTHENTICATION
Receiver can verify who sender
was
INTEGRITY
Detect modified messages
NON-REPUDIATION
Sender cannot later falsely deny
sending a message. Receiver
cannot falsely deny receiving it.
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.11)
Encryption
Plaintext (P)
hello world
Encrypt (E)
Ciphertext (C)
Decrypt (D)
C = E (P)
Ciphertext (C)
JHN+K9[
Plaintext (P)
P = D (C)
P = D (E (P))
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.12)
Encryption with a Secret Key
Key (k)
Plaintext (P)
Encrypt (E)
Ciphertext (C)
C = Ek (P)
Key (k)
Ciphertext (C)
Kerchoff’s Principle Secrecy should lie in
keeping a key secret.
Assume algorithm is
known.
Network Security (N. Dulay & M.
Huth)
Decrypt (D)
Plaintext (P)
P = Dk (C)
P = Dk (Ek (P))
Classical Cryptography (2.13)
Encryption with 2 Keys
Key1 (k1)
Plaintext (P)
Encrypt (E)
Ciphertext (C)
C = Ek1 (P)
Key2 (k2)
Ciphertext (C)
Decrypt (D)
Plaintext (P)
P = Dk2 (C)
P = Dk2 (Ek1 (P))
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.14)
Steganography
Dear George,
3rd March
Greetings to all at Oxford. Many thanks for your
letter and for the Summer examination package.
All Entry Forms and Fees Forms should be ready
for final dispatch to the Syndicate by Friday
20th or at the very least, I’m told, by the 21st.
Admin has improved here, though there’s room
for improvement still; just give us all two or three
more years and we’ll really show you! Please
don’t let these wretched 16+ proposals destroy
your basic O and A pattern. Certainly this
sort of change, if implemented immediately,
would bring chaos.
Network Security (N. Dulay & M.
Huth)
Conceal existence of
message, e.g. 1st letter
of each word, least sig.
bit of graphic image
Useless once method
discovered
Peter Wayner,
Disappearing
Cryptography, 2nd ed,
Morgan Kaufmann,
2002
Classical Cryptography (2.15)
Steganography
Dear George,
**
3rd March
Greetings to all at Oxford. Many thanks for your
letter and for the Summer examination package.
All Entry Forms and Fees Forms should be ready
for final dispatch to the Syndicate by Friday
20th or at the very least, I’m told, by the 21st.
Admin has improved here, though there’s room
for improvement still; just give us all two or three
more years and we’ll really show you! Please
don’t let these wretched 16+ proposals destroy
your basic O and A pattern. Certainly this
sort of change, if implemented immediately,
would bring chaos.
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.16)
Codes
Pre-arranged set of secret
codes/meanings.
BEST if used once only.
Security weakens with each use
if intercepted
EXAMPLE
Mobius
-> Launch missiles
Zebra
-> Don’t Launch
Only small set of pre-arranged
messages. What if we wanted to
communicate “Launch half the
missiles” or “Disarm missiles”?
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.17)
One-time Pad
Use a random key as long as the
message. Must not reuse the key
sequence ever again.
Both parties must have key sequence
Hotline between USA and USSR was
rumoured to use a one-time pad.
Destroy key sequence after use
Advantages?
EXAMPLE
Key is number of places to shift
letter
K
P
C
321424
launch
OCVREL
Suggest a good 1-time pad
function for binary data?
Disadvantages?
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.18)
Substitution Ciphers
Each letter (or group) is replaced by
another letter (group)
MONOALPHABETIC CIPHER
Each character is replaced by a
corresponding character
CAESAR CIPHER
Circularly shift each letter three
positions along in the alphabet,
e.g. zebra -> CHEUD
ROT13
Like Caesar but rotate 13 places.
Used to hide offensive jokes,
solutions to puzzles etc
Network Security (N. Dulay & M.
Huth)
BRUTE FORCE ATTACK
CHEUD
bgdtc
afcsb
zebra
ydapz
1
2
3
4
...
25 digve
Algorithm known
Only 25 keys
What if Plaintext language is not
easily recognisable?
Classical Cryptography (2.19)
Substitution Ciphers
GENERAL MONOALPHABETIC
CIPHERS
Use a random mapping, e.g:
abcedfghijklmnopqrstuvwxyz
ESFNCRTBZLMVAYXUPKDJOWQGIH
increases no of keys to 26! > 4*10^26
HOMOPHONIC CIPHERS
Each character has several ciphertext
mappings, as many as its relative
frequency
POLYGRAM CIPHERS
Map groups of characters, e.g. aly -> RTQ
POLYALPHABETIC CIPHERS
Vary monoalphabetic cipher during
ciphering/deciphering procedure
Network Security (N. Dulay & M.
Huth)
ATTACKING GENERAL
MONOALPHABETIC CIPHERS
Consider nature of Plaintext, e.g.
statistical properties.
Frequency of letters
e
12.75%
t
9.25%
r
8.50%
n
7.75%
Frequency of common words
Repeating letters
2-letter combinations (digrams): th, in,
er, re, an
3-letter combinations (trigrams): the, ing,
and, ion
Classical Cryptography (2.20)
Rotor Machine
E.g. ENIGMA MACHINE. Polyalphabetic Cipher
Several interconnected substitution rotating cylinders.
Example:
Input
A
A
Rotor1
Rotor2
Rotor3
A->F
F->X
X->N
Rotor 3 now shifts (its substitutions change)
A->F
F->X
X->W
Rotor 3 now shifts (its substitutions change)
Output
N
W
...
After 26 shifts by Rotor 3, it will be back to its original,
substitution Rotor 2 now shifts.
A
A->F
F->B
B->S
S
With 3 rotors and 26 letters we have a period = 26^3 = 17,576 substitution
alphabets
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.21)
Transposition Ciphers
Rearrange order of characters
(permutation)
SIMPLE COLUMNAR CIPHER
Using a grid, write plaintext
horizontally, read ciphertext.
vertically.
P
launchmissilesnow
launch
missil
esnow
C
ATTACK ON COLUMNAR
CIPHER
Ciphertext has same letter
frequencies as plaintext -> Easy
MULTIPLE TRANSPOSITION
CIPHERS
Pass a plaintext through two or
more transposition ciphers ->
Much harder to attack.
LMEAISUSNNSOCIWHL
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.22)
Cryptanalysis
Discover” key, and/or plaintext if not known
We assume algorithm is known (Kerckoff’s principle)
CIPHERTEXT ONLY ATTACK
E
C known
P known
E
C known
P chosen
E
C generated
generated
D
C chosen
KNOWN PLAINTEXT ATTACK
CHOSEN PLAINTEXT ATTACK
CHOSEN CIPHERTEXT ATTACK
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.23)
Cryptanalysis
Passive Attacks
PRACTICAL CRYPTANALYSIS
Acquire a key by any means, e.g.
Active Attacks
Theft
EXAMPLES OF ATTACK
Brute Force
Birthday
Man-in-the-Middle
Replay
Cut & Paste
Time Resetting
Many more...
Network Security (N. Dulay & M.
Huth)
Bribery (“Purchase-Key” attack)
Blackmail
Torture
Hypnosis
Classical Cryptography (2.24)
Cryptographic Strength
UNCONDITIONALLY SECURE
No matter how much ciphertext is available, it is still not enough to
infer the plaintext (even with infinite computational power). Only ONETIME PADS with random keys are unconditionally secure. Known as
PERFECT SECRECY for encryption systems.
PROVABLY SECURE
Cryptosystem shown to be as difficult to defeat as some supposedly
difficult (number-theoretic) problem, e.g. factorisation of large primes.
Has an equivalence proof.
COMPUTATIONALLY INFEASIBLE (PRACTICALLY SECURE)
Belief that cryptosystem cannot be broken with “available” resources;
formalizations thereof exist already, e.g. “secure for any adversary with
computational power in randomized polynomial time”
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.25)
Cost & Timeliness
£ COST TO BREAK
>
£ VALUE OF INFORMATION
TIME TO BREAK
>
USEFUL LIFETIME OF INFORMATION
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.26)
Reading
Stallings. Chapter 2.
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.27)
Cryptographic Design Vulnerabilities
Bruce Schneier
IEEE Computer, Sept 98,
p29-33
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.28)
Security, ha ha ha
Lock with 4 pins, each with
10 positions
Burglar may need to try
10,000 combinations to guarantee
success (brute-force attack)
What if 10 pins?
-> 10 billion positions
Great, but....
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.29)
A burglar could....
Smash the windows
Kick in the doors
Masquerade as a policeman
Threaten owner with violence
etc....
Better locks can’t help with these attacks
Same is true for cryptography. Good/strong cryptography is
important but not a panacea
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.30)
Marketing hype
“128-bit keys mean strong security”
“40-bit keys are weak”
“triple-DES is much stronger than single DES”
Be wary of products making such statements/claims.
Many products are buzzword-compliant, they use strong
cryptography but aren’t particularly secure
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.31)
Attacks against Design
Cryptosystems use algorithms for encryption, digital
signatures, one-way hash functions, random-numbers etc.
Break any one and you can usually break the whole system!
Cryptographic functions often have very narrow usage
It’s very difficult to design a secure cryptosystem, even
with good software engineers, e.g. Microsoft’s Point-toPoint-Tunneling Protocol (PPTP) used an inappropriate mode
for the RC4 encryption algorithm rendering it insecure
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.32)
Attacks against Implementation
Many cryptosystems fail because of mistakes in
implementation, e.g. don’t securely destroy unencrypted text
after encryption, have code that allows buffer overflow, are
poor error checking and recovery,
“Trivial” code-optimisations can break security
Implementation trade-offs e.g. to enhance usability at the
expense of security
Systems that allow old keys to be recovered in an
emergency
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.33)
Attacks against Hardware
Highly secure environments deploy tamper-resistant
hardware, e.g. tokencards, smartcards
Techniques/hardware to defeat them are also being
developed, e.g. timing attack on RSA private keys measured
relative times of cryptographic operations. Attacks that
measure power consumption, radiation emissions, introduce
faults and analyse effects
Cost to Defeat Tamper Resistance >> Value of Data
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.34)
Attacks against Trust Models
Who or what in the system is trusted, in what way, and to
what extend?
Some commerce systems can be broken by a merchant and a
customer colluding or two different customers colluding
Many systems make poor assumptions, eg, desktop is secure,
network is secure, employees are trusted
Design choices are sometimes ignored when it comes time to
sell a product/system.
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.35)
Attacks “on” Users
Pass on password to colleagues
Use same password on different systems
Write random passwords on paper
Don’t report missing smartcard
Don’t change (weak) default settings
Users need to be educated
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.36)
Attacks against Failure Recovery
Recovering the key for one file, should not allow every file
to be read
Reverse-engineering one smart card should not reveal secret
info in others
Options which switch off security, or make it less secure
Version rollback attack to insecure version
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.37)
Attacks against Cryptography
Proprietary algorithms/protocols -> invariably weak.
Cryptanalysts are very good at breaking published
algorithms, even better against proprietary ones!
Keeping the algorithm secret doesn’t make much difference
against determined opponents, algorithms can be reverseengineered
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.38)
Conclusion
A good security product must defend against every possible
attack, even attacks that haven’t been invented yet!
Attackers often only need find one flaw in order to defeat a
system.
In addition, they can collude & conspire.
They can wait for technology to give them the edge.
But don’t worry - Cryptography is a lot fun !!
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.39)
Optional but Recommended Reading
Links to these papers and documents are provided on the 430
course home page.
PriceWaterHouseCoopers’ 2010 Survey on the Global State
of Information Security
Ciphertext-only Crytanalysis of the Enigma, by James J.
Gillogly
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.40)
Notes on Tutorial for
Classical Cryptography
Michael Huth
[email protected]
www.doc.ic.ac.uk/~mrh/430/
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.41)
Why is Keyless Encryption bad?
Every group has own algorithm
Can’t use Off-the-Shelf algorithm, no implementation
choices
Change group - change algorithm
Key comprise - change algorithm
Poor quality control - little or no peer review
No standards
Easy to reverse-engineer algorithm
Kerchoff’s principle - Assume algorithm is known,
Secrecy should lie in keeping key secret.
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.42)
What Encryption doesn’t handle
**
Destructive Attacks, Replay
attacks
Unencrypted documents, e.g.
before encryption or after
decryption
Modification of encryption
program
Traitors
Interception incl. Traffic
Analysis
Successful cryptanalysis
Lost or Stolen keys or passwords
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.43)
Steganography
The supply of game for London is going steadily
up. Head keep Hudson, we believe, has been now
told to receive all orders for fly paper and for
preservations of your hen-pheasant's life.
"The Gloria Scott"
Arthur Conan Doyle.
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.44)
DECRYPT
WKXPEVXS
BRUTE FORCE ATTACK
Determine key for:
E Q V
C=E(P)=
P=D(C)=
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.45)
Freemason Cipher
A
B
C
D
E
F
G
H
I
M
N•
O•
P•
Q•
R•
S•
W
•
T•
U•
V•
Network Security (N. Dulay & M.
Huth)
J
K
X •
L
•
Z
• Y
Classical Cryptography (2.46)
Decipher
•
•
? ? ? ?
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.47)
Transposition Ciphers
SNPLTDFKAUOS
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.48)
End-to-End Encryption
P
C
C
Node2
Node3
Ek
Node1
(Host)
Network Security (N. Dulay & M.
Huth)
Dk
P
Node4
(Host)
Classical Cryptography (2.49)
Link-to-Link Encryption
C1
P
Ek1
Node1
(Host)
C2
Dk1 Ek2
Node2
Network Security (N. Dulay & M.
Huth)
C3
Dk2 Ek3
Node3
Dk3
P
Node4
(Host)
Classical Cryptography (2.50)
Link-to-Link
vs
End-to-End
Msg exposed in sending host &
intermediate nodes
Msg encrypted in sending host & rec
eiving nodes
Applied by sending host, host
responsible for encryption
Applied by sending process, process
responsible for encryption
Transparent to processes
Process applies encryption
All messages usually encrypted
Process decides when to encrypt
Can be done in hardware
Usually done in software
Requires one key per link pair
Requires one key per process pair
Provides host/node authentication
Provides application/user authenticat
ion
More ciphertext
Can hide more IP headers
Network Security (N. Dulay & M.
Huth)
Traffic analysis easier
Classical Cryptography (2.51)
Link-to-Link & End-to-End Encryption
Encryption/decryption devices
End-to-End
P2
N
Link-to-Link
Host
P1
N
N
Host
P3
Host
N
Network Security (N. Dulay & M.
Huth)
Classical Cryptography (2.52)