Known plaintext attack without knowing the location of the plaintext

Question

I'm trying to understand known plaintext attacks and since I best learn by doing I broke out Python and did the following:

I have a plaintext string s and a key k:

s = 'Lorem ipsum dolor sit amet'
k = 'key'

As I'm doing this with xor, this is my xor method:

def xor(s, k):
  return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s, itertools.cycle(k)))

So to get a ciphertext I do this:

c = xor(s, k)

And I can get the plaintext back by doing this, so I know it works:

xor(c, k)

Now for the exercise, let's say I have the ciphertext and know the word "dolor" is in there. How would I attempt to get the key?

My first thought was to do xor(c, 'dolor') but since I don't know where the word is I guess I'll have to try every location?

I found that using the word dolor as the key and starting with a different character kinda seems to work. So I attempt this:

xor(c, 'dolor')
xor(c, 'olord')
xor(c, 'lordo')
xor(c, 'ordol')

etc.

Using the last one (ordol) I spot keyke in the result. Since I know what the key is I know that I found it. But how would I know if I didn't know the key? Is there also some other way to do this instead of trying every possibility?

Answer 1

As you're aware your crypt/decrypt function works because A $\bigoplus$ B $\bigoplus$ B = A. So for:

• P = plaintext
• K = Key
• C = ciphertext = (P $\bigoplus$ K)

You can retrieve your plaintext as C $\bigoplus$ K == (P $\bigoplus$ K) $\bigoplus$ K = P.

You also know that C $\bigoplus$ P == (P $\bigoplus$ K) $\bigoplus$ P == K, i.e. you can retrieve the key if you know the plaintext.

Basic stuff, you already knew this.

You've asked "how would I attempt to get the key" if I only know a piece of the plaintext? In that case you cannot retrieve the key directly. However, you can narrow the search space for K considerably.

Consider the case where you know the plaintext less 1 character and, for the sake of simplicity, lets assume lower case alphabet characters only in the plaintext.

In that case, there are two positions that your known plaintext fragment can be in, in the original message, at the beginning or at the end. There are 26 possible plaintext solutions with the plaintext fragment at the beginning and 26 with it at the end, so there are 52 possible plaintext solutions. If you xor all those solutions with your ciphertext, one of the 52 results will be your key.

Knowing that you have "the key" is helped by having lots of ciphertext (like in the case where Mallory has stolen your million-record encrypted database). Identifying the key involves testing the 52 candidates against the million stolen records and seeing which candidate keys create the most plausible plaintexts (e.g. if the original plaintext is known to be English words, finding the key that generates the most of those)

Each fewer character that you know in the plaintext fragment (greatly) increases the search space. In the case where you know a plaintext fragment less two characters then there are three positions that the fragment could occupy and, for each of those positions there are $26^2$ possible combinations (for a total of 2028 combinations).

The search space grows exponentially with the number of characters that you do not know. But the converse is, therefore, true: the search space decreases exponentially with every character that you do know. And that is why an attacker having access to plaintext and ciphertext is scary.

So, no, you cannot directly retrieve the a key knowing a piece of the plain text and, yes, you do need to search the space. However, knowing part of the plaintext, you can greatly narrow a search and combined with other factors (like knowing the structure of the plaintext or encryption algorithm) can make a search that would be intractable either money or time-wise into something that an attacker can afford.

This is just a simple example, more complex ciphers are less straightforward to attack but, the concept is similar; each piece of knowledge (plaintext structure, key structure, algorithm) reduces the search space.

Answer 2

Chosen plain text attacks are not just used to reverse engineer keys. They are used to learn about the cryptosystem, and in the worst case can expose the key used. (https://simple.wikipedia.org/wiki/Chosen-plaintext_attack)

Let me help answer with a simple example.

I have used a chosen plain text attack against a simple encryption system (or should I say obfuscation system since it was really simple) to great effect. I was asked to reverse engineer a home grown "password encryption" algorithm as the author of it had lost the original source code. It was in a wrapped Oracle stored function so the source code was not readily available. I decided to use a chosen plain text attack to see the properties of this algorithm. So I ran a few queries:

select encrypt_password('a') from dual;
select encrypt_password('aa') from dual;
select encrypt_password('aaa') from dual;

This produced:

i
jh
kig

You can tell immediately that this is not a block cypher, nor is it a standard stream cypher (like RC4), but it looks like a substitution cypher.

By comparing the difference of each character between the plain text and the cypher text, you get:

8
9, 7
10, 8, 6

I did a few more plain texts to make sure that this pattern did not change for long passwords or for all of the other letters and numbers.

The final algorithm is:

cyphertext := ''
offset := length(password) + 7
for each letter in password
   new_letter := ordinal_value(letter) + offset
   cyphertext += new_letter 
   offset := offset - 2;
end for