Episode #132: Enigma

Tim goes stealth-mode:

We are always looking for new topic ideas from you readers, but this week we only received one email and trying to use it was difficult.

Hey there,

I've been searching for kung fu teachers, and I was excited to find you.

It's too hard to find trustworthy, quality service providers, and <dumb site> is changing that. We're growing really fast, we need more kung fu teachers, and I think you're a perfect fit!

Posting on <dumb site> is a great way to advertise yourself and it's completely free for service providers like you.

All you need to do to post your information is visit: <dumb site's URL>

Thanks!

~Heather

Apparently Heather didn't know that we don't do physical kung fu. We do try to kick bit booty, but we leave any physical effort to people in another line of work, like accountants. Oh, and the site name was redacted because I don't want to give them any business.

Since that didn't give us any great ideas, I came up with one on my own using some really secure encryption.

One method of encryption involves the use of On-time Pads. When used correctly it is impossible to crack. "If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key." That is different from taking billions of years to crack AES, this is uncrackable!

Let's use this technique to send a message to Hal:
I secretly teach Kung Fu

Hal and I meet up, and exchange one-time pads. I generated the pad by flipping a coin, where 1 is head and 0 is tails. The 1s and 0s were converted to bytes to create our encryption key.

PS C:\> $key = [byte[]](0x70,0xB3,0xDE,0xC0,0xDE,0xDF,0xAC,0xE1,0x7B,
  0xA5,0x41,0x51,0x33,0x7E,0xD5,0xC1,0x11,0xDF,0x00,0x15,0xDE,0xAD,0xD0,0x0D)

With this clear text...

PS C:\> $cleartext = "I secretly teach Kung Fu"

...we do a bit of encrypting

PS C:\> 0..($cleartext.length -1) | % {
  $ciphertext += ($key[$_] -bxor [int]$cleartext[$_]).ToString("x2") }
PS C:\> $ciphertext
3993ada5bdadc99517dc6125561fb6a93194757bb98d9678

This command counts from 0 to 24, the length of the clear text minus 1 (remember, base 0). The current pipeline object ($_) represents the counter and is used as the index in the array to grab the respective bytes from the key and clear text. The -bxor operator does a binary XOR. The result is then converted to a two character Hex string (x2), then is appended it to our cipher text. I would then send Hal this message:

Dear Hal,

Don't tell Heather, but 3993ada5bdadc99517dc6125561fb6a93194757bb98d9678

The cool thing is that the same process can be used to decrypt.

PS C:\> $cipherbytes = [byte[]](0x39,0x93,0xad,0xa5,0xbd,0xad,0xc9,0x95,0x17,
  0xdc,0x61,0x25,0x56,0x1f,0xb6,0xa9,0x31,0x94,0x75,0x7b,0xb9,0x8d,0x96,0x78)

PS C:\> 0..($cipherbytes.length -1) | % {
  $cipherbytes += ($key[$_] -bxor $cipherbytes[$_]).ToString("x2") }
PS C:\> $cipherbytes
I secretly teach Kung Fu

We can even use PowerShell to convert a hex string to bytes:

PS C:\> "3993ada5bdadc99517dc6125561fb6a93194757bb98d9678" | 
Select-String ".." -AllMatches | % { $_.Matches } | % { [byte]("0x" + $_.Value) }

This command will match on each two characters (..), take each match object, take each byte of the match and convert it to a byte.

That isn't really pretty, but we'll see how Hal will send the message, and if Bash is leet.

Hal goes into suck mode

I've got to be honest. This is a challenge where bash just isn't very conducive to solving the problem. But since a "real" scripting language like Perl or Python is disallowed by the rules of our blog, I'll just have to muddle through somehow.

Before we get to the suckage, let's start by assigning the bytes of our one-time pad to an array, just like Tim did:

$ otp=(0x70 0xB3 0xDE 0xC0 0xDE 0xDF 0xAC 0xE1 0x7B 0xA5 0x41 0x51 
       0x33 0x7E 0xD5 0xC1 0x11 0xDF 0x00 0x15 0xDE 0xAD 0xD0 0x0D)

The syntax we're using here "var=(val1 val2 ...)" is a convenient way for assigning a list of values to the elements of an array. We'll use this again in just a moment.

The hard part is when we want to start XOR-ing these bytes with the bytes in our string. The bash XOR operator ("^") wants both operators to be a numeric type. If I tried to do something like "I ^ 0x70", bash treats the "I" as an invalid number and therefore zero-- that's not what we want at all! So what I need to do is somehow convert the ASCII bytes in our input string into their numeric equivalents.

Well guess what? There's no bash built-in function for doing this! So you're left with doing a nasty hack like this:

$ echo -n I secretly teach Kung Fu | xxd -p
49207365637265746c79207465616368204b756e67204675

As you can see, I'm using the hexdumping program xxd as my ASCII-to-hex converter. The "-p" option means "plain mode": just output the hex bytes and nothing else. Of course, the problem here is that the bytes are all run together. But a little sed will fix that:

$ echo -n I secretly teach Kung Fu | xxd -p | sed 's/\(..\)/0x\1 /g'
0x49 0x20 0x73 0x65 0x63 0x72 0x65 0x74 0x6c 0x79 0x20 0x74 0x65 0x61 0x63...

In my sed expression, I'm snapping up two characters at a time and outputting a "0x", then the two characters, then a space.

With a little command substitution, I can now assign these hex bytes to another array:

$ bytes=( $(echo -n I secretly teach Kung Fu | xxd -p | sed 's/\(..\)/0x\1 /g') )

I'm really just doing an array assigment here-- "bytes=( ... )"-- similar to the one we used to set up our one-time pad. But in this case, the values I'm assigning are the output of our shell pipeline.

Now that I've got two arrays of bytes, I can XOR them together with a for loop:

$ for ((i=0; $i < ${#bytes[*]}; i++)); do 
      printf "%x" $((${bytes[$i]} ^ ${otp[$i]})); 
done
3993ada5bdadc99517dc6125561fb6a93194757bb98d9678$

The expression "${#bytes[*]}" evaluates to the number of elements in the array. Inside the loop, I'm using printf to output the results of my XOR operation as hex digits ("%x"). The only downside, as you can see, is that there's no final trailing newline at the end of the output-- the "$" you see there is the shell prompt for the next line! This is maybe not such a big deal, because most likely I'd want to do something like this:

$ secret=$( for ... )

That would assign the output of the loop to a variable, $secret.

But now what about going the other way and converting the contents of $secret back into the original ASCII? This is actually pretty similar to the steps above with a couple of small mods:

$ bytes=( $(echo $secret | sed 's/\(..\)/0x\1 /g') )
$ for ((i=0; $i < ${#bytes[*]}; i++)); do 
      printf "%x" $((${bytes[$i]} ^ ${otp[$i]})); 
done | xxd -r -p
I secretly teach Kung Fu$

Here I'm resetting the value of our bytes array to be the individual bytes from $secret, converted by sed to "0xNN" format. Then I run through the same for loop to XOR these bytes with our one-time pad. However this time the output goes into "xxd -r -p", which "reverts" the resulting string of bytes into their corresponding ASCII values.

All I can say is, thank the shell gods for xxd!