Week 1
By the end of the course you should be able to:
- Explain what cryptography can be used for
- Describe cryptographic mechanisms for providing each of the core security services
- Appreciate differences between types of cryptographic mechanisms and see in which situations they are most useful.
- Identify what mechanisms are necessary to “secure” an application
- See the limitations of cryptography and how to support it withing a full security architecture
Course Overview:
- Symmetric crypto: Stream ciphers, block ciphers, hash functions, MACs, authenticated encryption
- Asymmetric crypto: Public key encryption, digital signatures, PKI and key management, elliptic curve cryptography.
- Authentication and Key exchange protocols
- The TLS protocol
Confidentiality: Data cannot be viewed by unauthorized entity.
Integrity: Data has not been altered with.
Entity authentication: The given entity is involved and not someone else (identification).
Data origin authentication: The entity that sent the message did send the message.
Non-repudiation: Preventing the denial of previous actions.
Secure Channels
Main application: Secure communication, when 2 entities can exchange messages over an insecure channel.
- The messages should remain confidential
- Able to check origin of messages
- Detect when messages are deleted
- Detect when messages are re-ordered
From Caesar cipher to One-time Pad
Symmetric encryption:
The security should only rely of on secrecy of keys used. Not on the system details. Don’t rely on security through obscurity. It will get broken. But it can help further improve security.
Caesar Cipher
Problems: Only 26 possible keys: we can brute force it. And we could also use Frequency Analysis (the letters in a language are not uniformly distributed).
Vigenere Cipher
Caesar cipher chaining. We use multiple caesar ciphers in a row.
The keysize can be any of 26^length_of_plaintext. –> Brute force becomes difficult and frequency as well.
But statistical method is possible:
When a word appears twice or more in the plaintext, such as “the”, then it is possible to see the same ciphertext for that word if the keysize is smaller than half of the plaintext (If the key is repeated such that the word is encoded the same way twice or more).
Mathematical form
Caesar cipher
Plaintext P = P0, P1, P2, …: a sequence of integers between 0 and 25.
Key K = integer between 0 and 25.
Encryption: C(i) = P(i) + K mod 26
Decryption: P(i) = C(i) - K mod 26
Vigenere cipher
Plaintext P = same as above
Key K = K0, K1, … K(t-1) = sequence of t integers between 0 and 25.
Encryption: C(i) = P(i) + K (i mod t) mod 26
Decryption: P(i) = C(i) - K (i mod t) mod 26
The one-time Pad
Plaintext = same
Key K = K0, K1, K2, ……. as long as the plaintext!
Encryption: C(i) = P(i) + K(i) mod 26
Decrpytion: P(i) = C(i) - K(i) mod 26
The key length is the same as the plaintext length. People were traveling with a whole suitcase that contained the key in order to decrypt a long message somewhere.
We have perfect security: The ciphertext leaks nothing more about the plaintext except for its length. (If the keys are uniformly random).
Pr(P=p|C=c) = Pr(P=p)
If we know the ciphertext, that doesn’t increase the probability of finding the plaintext.
Example:
Each 7 letter big cat has the same probability.
Practicalities:
The Key K = k0, k1, k2,… is a sequence of integers between 0 and 25.
In reality represented as bits:
It is unbreakable but:
- The key needs to be as long as the message
- The key needs to be distributed in advance (Key management problem)
- Once the key is in place, it enables a single plaintext to be sent securely, at any point in the future
- If you use it more than once. then we can XOR the ciphertext which removes the key and leaves the XOR of the plaintext.
Stream Ciphers
They try to replicate the properties of the one-time pad, but using only a short key.
As a key we use the seed in a Pseudo-random generator.
Pseudo random: Appears to be truly random.
We can measure how good the PRG is by measuring the advantage an adversary has when distinguishing between a PRG and a truly random sequence.
The advantage of distinguisher = probability(b’=b) - 1/2.
b’ = the prediction of the distinguisher.
b = bit that says if it was a PRG or actual random
We take the absolute value because the bad PRG can easily be converted to a good PRG.
A PRG is said to be secure iff for all disdinguishers D, the advantage is small.
A PRG is sait to be (t, epsilon)-secure, if for all distinguishers D running in time t, the advantage is at most epsilon.
We can use a PRG to construct a stream cipher.
Instead of the long key we only need the short seed for the PRG.
Keystream Generators (KSG)
Takes as input: seed/key k and initialisation vector IV.
Output: Infinite stream of bits KS (keystream).
The IV enables many different keystreams to be produced from the single key k.
IV is typically set to be a counter.
IV doesn’t have to be secret, it can be sent along with ciphertext.
Encryption/Decryption:
KSG Security:
A KSG is said to be (q,t,epsilon) secure if all distinguishers running in time t making at most q queries on distinct IVs the advantage is at most epsilon.
If the adversaries could repeat the IVs then they could distinguish them 100%.
Exercise
Problem 1: Historic ciphers
a)
b)
Problem 2: Malleability of the one-time pad
The original message is decoded (with the given key):
“Dear professor, I hated your class so much. It sucked! Sincerely…”
We can find a new key that decodes it to:
“Dear professor, I loved your class so much. It wasfun! Sincerely…”
“hated” encoded by “bxbpy” becomes “ixutb”
“loved” encoded by “?????” becomes “ixutb”
We can encode “ixutb” by “loved” to get the key.
That gives us “xjzpy”. Which we can tell the professor.
We do the same to change “sucked” to “rocked” which gives us “idvysz” as an encoding.
The whole key would be:
s xjzpy pbtz scomu dn qmhy af idvysz
The whole thing looks like:
Problem 3: Stream cipher cryptanalysis
a.)
Ciphertexts: c0, c1 (same key)
Plaintexts: (m0,m1) and (m2,m3)
Which set of messages correspond to the ciphertexts?
-
XOR ciphertexts –> Get bit string
-
XOR m0 with m1 and m2 with m3 – > Compare values with the bit string
If they match then we know which messages were sent.
Explanation:
Plain Text1: 0001011
Key : 1010110
Ciphertext : 1011101
Plain Text2: 0110011
Key : 1010110
Ciphertext : 1100101
XOR of ciphertexts
1011101
1100101
0111000
XOR of plaintexts (which will match the XOR of the ciphertexts if the messages were encrypted with the key)
0001011
0110011
0111000
m0: 101
key:100
C0: 001
m1: 011
key:100
c1: 111
m0: 101
m1: 011
XOR:110
c0: 001
c1: 111
XOR:110
They match!
m1: 111
m2: 100
XOR:011
They don’t match!
Does it work in all cases?
Yes I think so but probably not.
b.)
a l p h a
01100001 01101100 01110000 01101000 01100001
b r a v o
01100010 01110010 01100001 01110110 01101111
d e l t a 01100100 01100101 01101100 01110100 01100001
g a m m a
01100111 01100001 01101101 01101101 01100001