ECE 7420 / ENGI 9823: Security
Lecture 10: Cryptography
Today
Intro to cryptography
Classical cryptography
Κρυπτογραφία
Κρυπτογραφία (cryptography)
Κρυπτογραφία (cryptography)
κρυπτός
Κρυπτογραφία (cryptography)
κρυπτός: hidden, secret
Κρυπτογραφία (cryptography)
κρυπτός: hidden, secret
γράφειν
Κρυπτογραφία (cryptography)
κρυπτός: hidden, secret
γράφειν: writing
Κρυπτογραφία (cryptography)
κρυπτός: hidden, secret
γράφειν: writing
- in general: transforming a message using secret knowledge
This famous photograph of US POWs in North Korea is an example of something that bears a hidden meaning to those with secret (or at least not-ubiquitous) knowledge. This photo was staged to show how happy captured US sailors were supposed to be in their new homes, but there is a hidden digital message...
Κρυπτογραφία (cryptography)
κρυπτός: hidden, secret
γράφειν: writing
- in general: transforming a message using secret knowledge
- in more technical terms:
plaintext ⇄ ciphertext using a key** Not all cryptograhic operations require a key, but we'll start with those that do.
This famous photograph of US POWs in North Korea is an example of something that bears a hidden meaning to those with secret (or at least not-ubiquitous) knowledge. This photo was staged to show how happy captured US sailors were supposed to be in their new homes, but there is a hidden digital message...
Security goals
| Confidentiality | |
| Integrity | |
| Availability | |
| Authentication | |
| Authorization | |
| Accountability |
Security goals
| Confidentiality | Encryption |
| Integrity | MACs, signatures |
| Authentication | Password hashing |
Cryptography is a useful mechanism that can be part of a solution that achieves security goals.
Security goals
| Confidentiality | Encryption |
| Integrity | MACs, signatures |
| Authentication | Password hashing |
Cryptography is a useful tool...
Cryptography is a useful mechanism that can be part of a solution that achieves security goals.
Security goals
| Confidentiality | Encryption |
| Integrity | MACs, signatures |
| Authentication | Password hashing |
Cryptography is a useful tool... but it's just a tool
Cryptography is a useful mechanism that can be part of a solution that achieves security goals.
If you think cryptography is the answer to your problem, then you don't know what your problem is.
Cryptography doesn't solve problems by itself. Encrypting a network packet doesn't secure the hosts doing the communication. Putting a contract on a blockchain won't stop people from breaking their word. A secure system is much more than just cryptography. However, cryptography is an important part of most secure systems.
Classical Cryptography
Classical cryptography refers to everything from the classical era (hence the Greek name!) up to the 20th Century. Modern cryptography is based on mathematical problems like the discrete logarithm problem — we'll talk about such things we get to public-key cryptography. In between, there's some awkwardness where different experts may disagree on definitions. Modern block ciphers aren't modern enough for some people, but they're definititely not classical either.
I would suggest that you think of classical cryptography as cryptography before computers (very broadly defined) and modern cryptography as cryptography based on math problems and applied computer science. However, don't be surprised if you encounter someone who doesn't think that definition is "pure" enough. 😉
Classical Cryptography
Substitution Cipher
- replace each symbol in the plaintext with a corresponding ciphertext symbol
Classical cryptography refers to everything from the classical era (hence the Greek name!) up to the 20th Century. Modern cryptography is based on mathematical problems like the discrete logarithm problem — we'll talk about such things we get to public-key cryptography. In between, there's some awkwardness where different experts may disagree on definitions. Modern block ciphers aren't modern enough for some people, but they're definititely not classical either.
I would suggest that you think of classical cryptography as cryptography before computers (very broadly defined) and modern cryptography as cryptography based on math problems and applied computer science. However, don't be surprised if you encounter someone who doesn't think that definition is "pure" enough. 😉
Classical Cryptography
Substitution Cipher
- replace each symbol in the plaintext with a corresponding ciphertext symbol
Example: Caesar cipher
- "shift" each letter by three (the key)
- vini vidi vici → ylql ylgl ylfl
Classical cryptography refers to everything from the classical era (hence the Greek name!) up to the 20th Century. Modern cryptography is based on mathematical problems like the discrete logarithm problem — we'll talk about such things we get to public-key cryptography. In between, there's some awkwardness where different experts may disagree on definitions. Modern block ciphers aren't modern enough for some people, but they're definititely not classical either.
I would suggest that you think of classical cryptography as cryptography before computers (very broadly defined) and modern cryptography as cryptography based on math problems and applied computer science. However, don't be surprised if you encounter someone who doesn't think that definition is "pure" enough. 😉
More classical cryptography
Transposition Cipher
- divide messages into blocks
- transpose characters within blocks
- newfoundland → newf ound land → wnfe nodu nlda
with key 2413 (1 → 2, 2 → 4, 3 → 1, 4 → 3)
More classical cryptography
Transposition Cipher
- divide messages into blocks
- transpose characters within blocks
- newfoundland → newf ound land → wnfe nodu nlda
with key 2413 (1 → 2, 2 → 4, 3 → 1, 4 → 3)
Clearly not great... but why not?
If you don't know the key to such a transposition cipher, what might you try in order to find it?
Cryptanalysis
Cryptanalysis
- given some plaintext and/or ciphertext, find the key
Cryptanalysis
- given some plaintext and/or ciphertext, find the key
- find a fatal flaw ("break") that subverts a cryptosystem
Cryptanalysis
- given some plaintext and/or ciphertext, find the key
- find a fatal flaw ("break") that subverts a cryptosystem
Most fundamental example: exhaustive key search
- given some ciphertext (ylql ylgl ylfl), try all possible key values
Cryptanalysis
- given some plaintext and/or ciphertext, find the key
- find a fatal flaw ("break") that subverts a cryptosystem
Most fundamental example: exhaustive key search
- given some ciphertext (ylql ylgl ylfl), try all possible key values
- 1 → xkpk xkek xkek
Cryptanalysis
- given some plaintext and/or ciphertext, find the key
- find a fatal flaw ("break") that subverts a cryptosystem
Most fundamental example: exhaustive key search
- given some ciphertext (ylql ylgl ylfl), try all possible key values
- 1 → xkpk xkek xkek, 2 → wjoj wjej wjdj
Cryptanalysis
- given some plaintext and/or ciphertext, find the key
- find a fatal flaw ("break") that subverts a cryptosystem
Most fundamental example: exhaustive key search
- given some ciphertext (ylql ylgl ylfl), try all possible key values
- 1 → xkpk xkek xkek, 2 → wjoj wjej wjdj, 3 → vini vidi vici
Cryptanalysis
- given some plaintext and/or ciphertext, find the key
- find a fatal flaw ("break") that subverts a cryptosystem
Most fundamental example: exhaustive key search
- given some ciphertext (ylql ylgl ylfl), try all possible key values
- 1 → xkpk xkek xkek, 2 → wjoj wjej wjdj, 3 → vini vidi vici
- possible if correct plaintext is distinguishable
Cryptanalysis
- given some plaintext and/or ciphertext, find the key
- find a fatal flaw ("break") that subverts a cryptosystem
Most fundamental example: exhaustive key search
- given some ciphertext (ylql ylgl ylfl), try all possible key values
- 1 → xkpk xkek xkek, 2 → wjoj wjej wjdj, 3 → vini vidi vici
- possible if correct plaintext is distinguishable, easy if some P/C pairs are known
Cryptanalysis
- given some plaintext and/or ciphertext, find the key
- find a fatal flaw ("break") that subverts a cryptosystem
Most fundamental example: exhaustive key search
- given some ciphertext (ylql ylgl ylfl), try all possible key values
- 1 → xkpk xkek xkek, 2 → wjoj wjej wjdj, 3 → vini vidi vici
- possible if correct plaintext is distinguishable, easy if some P/C pairs are known (yes, this is actually possible!)
It might seem unlikely that an attacker would have access to all details of the system, plus plaintext and ciphertext pairs, but it's actually not. In WWII, British codebreaking was sometimes aided by feeding specific plaintexts to the German enemy via a process called "gardening") (laying sea mines in specific locations to create minesweeping messages).
Kerckhoffs's principle(s)
Kerckhoffs's principle(s)
- The system must be practically, if not mathematically, indecipherable;
- It should not require secrecy, and it should not be a problem if it falls into enemy hands;
- It must be possible to communicate and remember the key without using written notes, and correspondents must be able to change or modify it at will; [...]
Translation from the French from Wikipedia
Kerchoffs had six principles, including that "it must be applicable to telegraph communications", but we're less interested in those. One key principle that we are still interested in is the second one: the security of a system should not depend on the adversary being ignorant of its details. This is commonly mis-stated as, "the design should be public", but that's not quite what Kerchoffs said. Rather, the principle is that your security shouldn't depend on the design being secret.
Exhaustive key search
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
- Modern AES-128 cipher: 2^{128} keys
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
- Modern AES-128 cipher: 2^{128} keys — could take awhile!
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
- Modern AES-128 cipher: 2^{128} keys — could take awhile!
- 10,000 CPUs checking one key / ns
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
- Modern AES-128 cipher: 2^{128} keys — could take awhile!
- 10,000 CPUs checking one key / ns
- 10^4 \textrm{CPU} \times 10^9 \frac{\textrm{key}}{\textrm{CPU} \cdot s} \times 10^{4.9} \frac{s}{d} = 10^{17.9} \frac{\textrm{key}}{d} = 2^{59.5} \frac{\textrm{key}}{d}
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
- Modern AES-128 cipher: 2^{128} keys — could take awhile!
- 10,000 CPUs checking one key / ns
- 10^4 \textrm{CPU} \times 10^9 \frac{\textrm{key}}{\textrm{CPU} \cdot s} \times 10^{4.9} \frac{s}{d} = 10^{17.9} \frac{\textrm{key}}{d} = 2^{59.5} \frac{\textrm{key}}{d}
- need 2^{67.5} days
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
- Modern AES-128 cipher: 2^{128} keys — could take awhile!
- 10,000 CPUs checking one key / ns
- 10^4 \textrm{CPU} \times 10^9 \frac{\textrm{key}}{\textrm{CPU} \cdot s} \times 10^{4.9} \frac{s}{d} = 10^{17.9} \frac{\textrm{key}}{d} = 2^{59.5} \frac{\textrm{key}}{d}
- need 2^{67.5} days, i.e., 209 Edays
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
- Modern AES-128 cipher: 2^{128} keys — could take awhile!
- 10,000 CPUs checking one key / ns
- 10^4 \textrm{CPU} \times 10^9 \frac{\textrm{key}}{\textrm{CPU} \cdot s} \times 10^{4.9} \frac{s}{d} = 10^{17.9} \frac{\textrm{key}}{d} = 2^{59.5} \frac{\textrm{key}}{d}
- need 2^{67.5} days, i.e., 209 Edays / 572 Pyears
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
- Modern AES-128 cipher: 2^{128} keys — could take awhile!
- 10,000 CPUs checking one key / ns
- 10^4 \textrm{CPU} \times 10^9 \frac{\textrm{key}}{\textrm{CPU} \cdot s} \times 10^{4.9} \frac{s}{d} = 10^{17.9} \frac{\textrm{key}}{d} = 2^{59.5} \frac{\textrm{key}}{d}
- need 2^{67.5} days, i.e., 209 Edays / 572 Pyears / 63.5 Msols
Exhaustive key search
- Caesar-style shift cipher: 26 possible keys (well, really 25)
- Modern AES-128 cipher: 2^{128} keys — could take awhile!
- 10,000 CPUs checking one key / ns
- 10^4 \textrm{CPU} \times 10^9 \frac{\textrm{key}}{\textrm{CPU} \cdot s} \times 10^{4.9} \frac{s}{d} = 10^{17.9} \frac{\textrm{key}}{d} = 2^{59.5} \frac{\textrm{key}}{d}
- need 2^{67.5} days, i.e., 209 Edays / 572 Pyears / 63.5 Msols
- Lesson: make the search space large!
Cryptanalysis assumptions
Various attack models:
Cryptanalysis assumptions
Various attack models:
- ciphertext-only (COA)
In a ciphertext-only attack, the adversary can break your cryptosystem using nothing but ciphertext. This is the strongest form of attack, so to say that a cryptosystem can withstand it don't impress me much.
Cryptanalysis assumptions
Various attack models:
- ciphertext-only (COA)
- known-plaintext (KPA)
In a ciphertext-only attack, the adversary can break your cryptosystem using nothing but ciphertext. This is the strongest form of attack, so to say that a cryptosystem can withstand it don't impress me much.
In a known-plaintext attack, the adversary is assumed to have access to plaintext/ciphertext pairs.
Cryptanalysis assumptions
Various attack models:
- ciphertext-only (COA)
- known-plaintext (KPA)
- chosen-plaintext (CPA, CPA2)
In a ciphertext-only attack, the adversary can break your cryptosystem using nothing but ciphertext. This is the strongest form of attack, so to say that a cryptosystem can withstand it don't impress me much.
In a known-plaintext attack, the adversary is assumed to have access to plaintext/ciphertext pairs.
In a chosen-plaintext attack, the adversary is assumed to be able to make you encrypt plaintexts of their choosing (like "gardening" in WWII, but much more direct / less costly).
Cryptanalysis assumptions
Various attack models:
- ciphertext-only (COA)
- known-plaintext (KPA)
- chosen-plaintext (CPA, CPA2)
- chosen-ciphertext (CCA, CCA2)
In a ciphertext-only attack, the adversary can break your cryptosystem using nothing but ciphertext. This is the strongest form of attack, so to say that a cryptosystem can withstand it don't impress me much.
In a known-plaintext attack, the adversary is assumed to have access to plaintext/ciphertext pairs.
In a chosen-plaintext attack, the adversary is assumed to be able to make you encrypt plaintexts of their choosing (like "gardening" in WWII, but much more direct / less costly).
Finally, in a chosen-ciphertext attack, the adversary is assumed to be able to make you decrypt ciphertexts they give you.
Frequency analysis
Frequency analysis
Example of a ciphertext-only attack
Frequency analysis
Example of a ciphertext-only attack
- don't know the plaintext
Frequency analysis
Example of a ciphertext-only attack
- don't know the plaintext
- know something about the plaintext
Frequency analysis
Example of a ciphertext-only attack
- don't know the plaintext
- know something about the plaintext: symbol frequencies
Frequency analysis
Example of a ciphertext-only attack
- don't know the plaintext
- know something about the plaintext: symbol frequencies
- English: 12% e, 9% t, etc., common groupings: the, an, qu...
Frequency analysis
Example of a ciphertext-only attack
- don't know the plaintext
- know something about the plaintext: symbol frequencies
- English: 12% e, 9% t, etc., common groupings: the, an, qu...
Exercise: decode shift-enciphered ciphertext via frequency analysis
hijstcih hdbtixbth tcrdst pcs strdst bthhpvth
The End.