Welcome to part 2 of my posts on the material from the “Cryptography I” course. In this course the material is designed to teach students about how to scientifically determine what concepts/algorithms are and are not cryptographically secure. I am continuing this series of posts so that I can have some way to review the information at a later time as well as to provide my interpretation of the material for others to read and comment on. Enjoy!
Review
In the first part I cover topics like Probability Distributions (Uniform and Point), Events, Randomized Algorithms and Independence.
XOR
XOR proves to be a very important aspect of cryptography and is actually use in many ciphers like OTP, DES and AES. Therefore if you are not familiar with the concept of XOR, now would be a good time to read up on it. Basically the following truth table provides the mapping for XOR given X and Y inputs.
(X, Y) | Z
===========
(0, 0) | 0
(0, 1) | 1
(1, 0) | 1
(1, 1) | 0
Symmetric Ciphers
A Symmetric Cipher is one that uses the same key (k) for the sender and receiver. For example if Alice sends Bob a message, both Alice and Bob must use the same key to be able to securely send and receive messages.
More formally we can define it such that over a key space of all possible keys (K), a message space of all possible messages (M) and a cipher text space of all possible CT (C) the cipher is efficient where encryption (E) and decryption (D):
E: K x M -> C
D: K x C -> M
such that... ∀ m in M, k in K: D(k, E(k, m)) = m
∀ = For all
Note that E is often randomized but D is always deterministic!
The One Time Pad (OTP)
From Wikipedia:
First described by Frank Miller in 1882, the one-time pad was re-invented in 1917. On July 22, 1919, U.S. Patent 1,310,719 was issued to Gilbert S. Vernam for the XOR operation used for the encryption of a one-time pad. It is derived from the Vernam cipher, named after Gilbert Vernam, one of its inventors. Vernam’s system was a cipher that combined a message with a key read from a punched tape.
OTP uses a very simple concept of XORing the plaintext message with the key to produce some ciphertext (c) that cannot easily be decrypted.
ciphertext: E(k, m) = k ⊕ m
plaintext: D(k, c) = k ⊕ c
Note: D(k, E(k, m)) = D(k, k ⊕ m) = k ⊕ (k ⊕ m) = (k ⊕ k) ⊕ m = m
Example:
m = 0110001
k = 1101110
c = 1011111
Note that k must be at least as long as m to securely encrypt m
As we can see OTP is a very fast encryption and decryption cipher but it needs long keys. Now however we really need to ask what defines a “good” cipher?
Perfect Secrecy
The basic idea to secure a plaintext (PT) message is that the ciphertext (CT) should reveal no information about the PT.
More formally, a cipher (E, D) over (K, M, C) has *perfect secrecy* IF..
∀ m0, m1 in M, (len(m0) = len(m1))
∀ c in C, Pr[E(k, m0) = c] = Pr[E(k, m1) = c]
Where k in uniform (truly random sample) in K.
This means if we intercept c, we cannot tell if the plaintext is m0 or m1, and must be true for all possible m.
OTP
At this point we have defined what a secure cipher is and now should look at OTP and see if we can prove that it has perfect secrecy.
∀ m,c: Pr[E(k, m) = c] = (# keys k in K such that E(k, m) = c)/|K|
So... ∀ m,c: #{k in K: E(k, m) = c} = constant
If this is true then the cipher has perfect secrecy!
So… Let m in M and c in C, how many OTP keys map m -> c?
For OTP, if E(k, m) = c:
k ⊕ m = c
k = m ⊕ c
Therefore For all m,c: #{k in K: E(k, m) = c} = 1
OTP has perfect secrecy and so there is no possible CT attack. This however does not mean that OTP does not have other possible attacks.
Bad News
This idea of perfect secrecy is pretty useful as it allows us to easily define in a cipher is secure or not. However it comes with a major drawback, that |K| >= |M| which means that if we have a very long message, say 1GB then the key must also be *at least* that long. This limitation makes it difficult to use OTP in practice but we can still use it to observe certain properties about XOR and cryptography.
Stream Ciphers
To make OTP practical we must use something called a Pseudo Random Generator (PRG) to replace our totally random key with a pseudo random key such that:
PRG: function G: {0,1}^s -> {0,1}^n, where n >> s
G must be "efficient" and its output should "look" random.
So the question we ask now is: “Is this a secure method? Does it guarantee perfect secrecy?”. The answer is no, this is not meeting our previous definition of secure since the size of the key is much smaller than the message.
What this means is we must use a less strict definition of “secure” as perfect secrecy cannot be used practically. Instead we will make a definition such that security depends on the specific PRG’s ability to generate a “random” result.
PRG
Suppose that a PRG is predictable:
∃ i (index): G(k) from [1 .. i] ---> G(k) from [i+1,...,h]
In practice this can mean that if a CT has a predictable header, like say an SMTP message then the attacker can use this to predict the rest of the message. This is because they can use the predictable nature of the PRG to easily guess what follows the known header.
Formally it can be written like:
∃ some "efficient" algorithm A and there exists some 1 <= i <= n - 1 such that:
Pr[A(G(k)) from 1..i = G(k) of i+1] >= 1/2 + ε
For some non-negligible epsilon (ex. ε >= 1/2^30), the generator is predictable!
Therefore an unpredictable PRG is one that meets the following constraint:
∀ i: no efficient adversary can predict bit i+1 for non-negligible ε.
Attacks On OTP
Finally to end this post I wanted to cover the attacks on OTP that are discussed in the course as they are quite interesting.
Attack 1
The “Two Time Pad” is very insecure!
The important lesson to remember from this attack is to NEVER EVER use a stream cipher key more than one time. Lets look at this in practice.
Suppose that c1 = m1 ⊕ PRG(k)
Suppose that c2 = m2 ⊕ PRG(k)
If the attacker has c1 and c2, they can perform a simple operation to determine the key (k)!
PRG(k) = 101000
m1 = 011011, c1 = 110011
m2 = 110010, c2 = 011010
c1 ⊕ c2 = 101001
m1 ⊕ m2 = 101001 (look familiar?)
Therefore when using OTP for client server interaction, it is important that the client and server generate a new key each time one of them must send a message, this is very impractical!
Attack 2
OTP provides no message integrity, we can see this in a very simple example:
Suppose that user sends the CT to the adversary but without the key (ie. m ⊕ k). The adversary can then take that CT and XOR it to some known key (p) such that:
j = (m ⊕ k) ⊕ p
The adversary can then send j to user and when decrypted the result will actually be m ⊕ p (since XORs on same value cancel out).
In a more practical example, suppose the adversary knew the header of the message was “From: Bob”, they could XOR it with a key in such a way that when the user decrypts the message it ends up reading “From: Eve”!
Conclusion
Hopefully you found this post interesting and informative. I know there was a lot of reading but I think its worth learning all these concepts because they really do provide the fundamentals for what comes next in the material. I hope to write the next part of this series soon so stay tuned!
Feature Image courtesy of lekkyjustdoit at FreeDigitalPhotos.net