Toying with Cryptography: Crib Dragging
samwho keyboard logo

Toying with Cryptography: Crib Dragging

2015-07-18 — 10 minute read

Cryptograhpy has become very topical in the UK over the last few years, what with the UK government wanting to do nasty things to it. It also happens to be one of my weakest areas. I don't know a whole lot about how it works and I probably should. Because of this, I'm reading crypto101.io. It's a book written by lvh and made available for free.

The teaching method in the book is exactly how I love to learn things. It starts at the beginning and works through chronologically, showing how each method is broken and how it was solved at the time, all the way up to the modern day ciphers.

It all begins with an ideal: one-time pad.

Prerequisite knowledge: I'll be using Ruby to demonstrate things. No knowledge of cryptography is required.

# Introduction

I went in to this not knowing anything about how things get encrypted and decrypted. It turns out to be quite simple, and all revolves around the simple bitwise operation XOR.

The XOR operation is often denoted with a ^ (caret) and works like this:

0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
1 ^ 1 = 0

So if the bits are different, the result produced is a 1. Let's look at some more complex examples:

0110 ^ 1111 = 1001
1001 ^ 1111 = 0110
0000 ^ 1000 = 1000
1111 ^ 1111 = 0000

There are a few interesting properties of XOR in these examples.

These properties are very important when making and, indeed, breaking systems of encryption.

# The one-time pad

This is the simplest and theoretically most secure way of transmitting a message and not having it read by anyone other than the intended recipient. It goes like this:

If the key is truly random, exchanged securely and only used once, this system provides what's called "perfect secrecy" and is resistant to attack apart from brute force.

# However...

One-time padding is extremely impractical and not used in reality.

# Deriving the key from multiple messages

Let's say you have two messages and you suspect that the sender has used the same key to encrypt both using XOR. Remember our two rules from above:

A ^ A = 0
A ^ B = B ^ A

Using these two properties we can derive something fun about having two messages encrypted with the same key:

cipher1 = msg1 ^ key
cipher2 = msg2 ^ key
cipher1 ^ cipher2 = (msg1 ^ key) ^ (msg2 ^ key)
cipher1 ^ cipher2 = msg1 ^ msg2 ^ key ^ key
cipher1 ^ cipher2 = msg1 ^ msg2 ^ 0
cipher1 ^ cipher2 = msg1 ^ msg2

XORing the cipher texts gives you the same result as XORing the original messages. Why is this important? Remember another of the rules from above:

If you XOR two things together, and then XOR the result against one of them, you get the other one.

If I knew that the message exchanged was in English, I could guess common English words and XOR those against the XORd cipher text to possibly reveal parts of the original message. This is called "crib dragging". You're "dragging" a common set of characters across the cipher text in the hope of revealing the original message.

This is a bit confusing to explain via text so let's have an example. I'll need a couple of utility functions to help me through this. First, a function to XOR two strings together:

def xorstr(str1, str2)
  result = ""
  str1.bytes.each_with_index do |byte, i|
    result << (byte ^ str2[i].ord).chr
  end
  result
end

And a function to make the crib dragging a bit easier:

def cribdrag(cipher, word)
  cipher.chars.each_cons(word.length) { |cons| yield xorstr(word, cons.join) }
end

So let's open up an IRB session and encrypt some stuff!

irb> msg1 = "The cat sat on the mat."
=> "The cat sat on the mat."
irb> pad = File.read("/dev/urandom", msg.length)
=> "|A\xC8\xD9\xE1\x9EF2\xE2\xAE\x99\xBE\xD4\xC2kcV\n\xC2t\xEE(\x8C"

The astute observer will notice I've taken my key from /dev/urandom, which isn't a cryptographically secure way of generating random numbers. You're correct, but for the sake of example and not exhausting my machine of entropy I'm going to use a pseudo-random key.

irb> cipher1 = xorstr(msg1, key)
=> "()\xAD\xF9\x82\xFF2\x12\x91\xCF\xED\x9E\xBB\xACK\x17>o\xE2\x19\x8F\\\xA2"

Now we have an encrypted message. At this point we're all good, we could exchange the key securely and send the message however we like and the world would continue turning and rainbows would still happen. Let's ruin this.

irb> msg2 = "Hello, cruel old world."
=> "Hello, cruel old world."
irb> cipher2 = xorstr(msg2, key)
=> "4$\xA4\xB5\x8E\xB2fQ\x90\xDB\xFC\xD2\xF4\xAD\a\av}\xAD\x06\x82L\xA2"

Notice that the messages have to be the same length, or padded in some way, to reuse the key. Let's see if the mathematics holds up and the ciphers XORd together is the same as the messages XORd together:

irb> xorcipher = xorstr(cipher1, cipher2)
=> "\u001C\r\tL\fMTC\u0001\u0014\u0011LO\u0001L\u0010H\u0012O\u001F\r\u0010\u0000"
irb> xormsg = xorstr(msg1, msg2)
=> "\u001C\r\tL\fMTC\u0001\u0014\u0011LO\u0001L\u0010H\u0012O\u001F\r\u0010\u0000"

Huzzah! No horsemen, no end times, mathematics still works.

Next we'll try a bit of crib dragging. Our cribdrag function takes an encrypted string and a second string, then slides the second string across the first, yielding parts of the encrypted string XORd against the crib.

A really common thing to see in English text is the word "the" surrounded by spaces. So we're going to give that a try:

irb> cribdrag(xorcipher, " the ") { |chunk| puts chunk }

And the output:

<ya),
-}$im
)8d(t
lx%1c
,9<&!
m +d4
t7iq1
cu|tl
!`y)o
4e$*!
18'dl
l;i)0
ou$uh
!8x-2
ld wo
0<z*?
hf'z-
2;wh0
okeu

Lots of gibberish but two things that contain all English letters, one of which doesn't appear in any words I'm aware of:

ld wo
okeu

Now what I would try is get a list of common words ending in "ld" or starting with "wo" and try crib dragging those. To speed the process up, I'll just go with "world" straight away:

irb> cribdrag(xorcipher, "world") { |chunk| puts chunk }

kb{ h
zf>`)
~#~!0
;c?8'
{"&/e
:;1mp
#,sxu
4nf}(
v{c +
c~>#e
f#=m(
; s t
8n>|,
v#b$v
:~+
g'`#{
?}=si
e mat
8|d

Only one of these seems legit, "e mat", and I know that the start of that is " th". So now we have "the mat" as something that is very likely to be part of the message. Having been 3 years old at one point, I can guess that "cat sat on the mat" is likely to be found somewhere:

irb> cribdrag(xorcipher, "cat sat on the mat") { |chunk| puts chunk }

}l}, cnz18'dl})f
nh8,>57!l;i)0%s;
j-xm'"u4~"ou$u.k
/m9t0``1#!!8x-2"~y
o, cruel old world
.57!gp8on"0<z*?`qt

And there we can see most of our original message near the bottom line. The neat thing about this is that for every little section of the message you recover, you can figure out the corresponding bits of the key that was used to encrypt them by XORing the chunks of recovered message against the original cipher texts:

irb> xorstr(cipher1[4..-2], "cat sat on the mat")
=> "\xE1\x9EF2\xE2\xAE\x99\xBE\xD4\xC2kcV\n\xC2t\xEE("
irb> xorstr(cipher2[4..-2], "cat sat on the mat")
=> "\xED\xD3\x12q\xE3\xBA\x88\xF2\x9B\xC3's\x1E\x18\x8Dk\xE38"
irb> xorstr(cipher1[4..-2], "o, cruel old world")
=> "\xED\xD3\x12q\xE3\xBA\x88\xF2\x9B\xC3's\x1E\x18\x8Dk\xE38"
irb> xorstr(cipher2[4..-2], "o, cruel old world")
=> "\xE1\x9EF2\xE2\xAE\x99\xBE\xD4\xC2kcV\n\xC2t\xEE("

So we know that one of those two strings is part of the key, and if we had a third message to decrypt we could check both and see what we get, but for now I'll satisfy your curiosity by showing that part of the key is indeed one of those strings:

irb> key[4..-2]
=> "\xE1\x9EF2\xE2\xAE\x99\xBE\xD4\xC2kcV\n\xC2t\xEE("

# Automating this process

So what we just did was very manual and involved, can it be automated?

The struggle with automating this is recognising bits of human-readable text when we see them. We aren't guaranteed to get full words from crib dragging. An idea I was trying out on a train recently was to use a measure of entropy to "score" bits of revealed text:

def entropy(str)
  str.chars.each_cons(2).inject(0) do |total, (a, b)|
    total += (a.ord - b.ord).abs
  end / str.length.to_f
end

Yes, I know that code is horrible. I was on a train. What it's doing is calculating the average difference between each byte of a string and then dividing by the length of the string. So there's a maximum value of 255 and a minimum value of 0. The idea is that English letters are close together in terms of their byte values (low entropy), and random nonsense should be quite scattered (high entropy). Let's see how it holds up:

irb> cribdrag(xorcipher, " the ") { |chunk| puts "#{chunk} #{entropy(chunk)}" }

<ya), 28.8
-}$im 48.4
)8d(t 39.0
lx%1c 31.4
,9<&! 8.6
m +d4 38.6
t7iq1 36.6
cu|tl 8.2
!`y)o 47.6
4e$*! 25.8
18'dl 18.6
l;i)0 33.2
ou$uh 36.2
!8x-2 33.4
ld wo 34.2
0<z*? 35.0
hf'z- 45.0
2;wh0 28.0
okeu  22.2

Hm. Not very good. Some gibberish is scored really low and the actual answer is scored very high. Let's try something else:

irb> cribdrag(xorcipher, "cat sat on") { |chunk| puts "#{chunk} #{entropy(chunk)}" }

 l}l , cnz 25.7
nh8 , >57! 21.1
j-xm'"u4~" 53.6
/m9t0``1#! 35.2
o, cruel o 34.2
.57!gp8on" 29.8
7"u4b-;!#~ 40.1
 ``1?.ul & 33.0
buel<`80'| 26.8
wp8or-dh}! 36.2
r-;!?q<2 q 35.1
/.ulc)fopc 23.2
,`80;s;?b~ 29.0
b-dha.k- n 39.2

Again, no real significance. It looks like this method isn't going to work. At least part of the problem is that space (byte value 32) is quite far away from the letters, like "a" (byte value 97), which brings the average up. What if we had an entropy function that removed spaces?

def entropy(str)
  str.gsub(' ', '').chars.each_cons(2).inject(0) do |total, (a, b)|
    total += (a.ord - b.ord).abs
  end / str.length.to_f
end

irb> cribdrag(xorcipher, " the ") { |chunk| puts "#{chunk} #{entropy(chunk)}" }

<ya), 28.8
-}$im 48.4
)8d(t 39.0
lx%1c 31.4
,9<&! 8.6
m +d4 34.2
t7iq1 36.6
cu|tl 8.2
!`y)o 47.6
4e$*! 25.8
18'dl 18.6
l;i)0 33.2
ou$uh 36.2
!8x-2 33.4
ld wo 7.0
0<z*? 35.0
hf'z- 45.0
2;wh0 28.0
okeu  5.2

Looks better... What about the other example?

irb> cribdrag(xorcipher, "cat sat on") { |chunk| puts "#{chunk} #{entropy(chunk)}" }

 l}l , cnz 23.3
nh8,>57!{  21.1
j-xm'"u4~" 53.6
/m9t0``1#! 35.2
o, cruel o 16.6
.57!gp8on" 29.8
7"u4b-;!#~ 40.1
 ``1?.ul&  26.6
buel<`80'| 26.8
wp8or-dh}! 36.2
r-;!?q<2 q 31.5
/.ulc)fopc 23.2
,`80;s;?b~ 29.0
b-dha.k- n 39.2

A little better. The lowest one there is the correct answer. Perhaps with some more jiggery pokery we could make this work and automate the discovery process with a well crafted set of cribs and possibly some checking to see if things between spaces are real words. For now, though, I'm going to cut this here.

# Wrapping up

Cryptograhpy doesn't seem as scary as I first thought it would be. I'm about a quarter of the way through the book and stuff makes sense. Ciphers get more complex as we go on but the issues that are addressed all make sense and the solutions seem sound (until I read the next chapter and the author shows how they break).

More soon! :)

Sam Rose

Enjoyed this post? Consider subscribing to get updates about new posts via email!

Alternatively, you can subscribe via RSS.

powered by buttondown