Tuesday, August 07, 2007

One-time pad.

Why encrypt messages? I dunno. A better question might be; why not? It's a cool thing to try out, and you might actually use it one day.

One-time pads, when used properly are (theoretically) impossible to crack. They use a simple XOR type function with a random key. The unbreakable security is dependent on two things; the truly random nature of the key, and the privacy of the key.

The one-time pad has logistical issues; keys must be used ONLY once, and keys cannot repeat, so they must be the length of the message, requiring you to ensure the security of a lot of letters, and possibly requiring frequent key exchanges. Note that while pads must hold a lot of info, they don't necessarily have to be big. Here's a picture of a captured Russian one-time pad. (which, incidentally, was likely made of flash paper which burns quickly and leaves no ashes)

So why am I telling you about old cryptography technology in this age of computers and blink-of-an-eye cryptanalysis? Well, I'm telling you because we live in an age of computers and blink-on-an-eye cryptanalysis. Most current encryption technologies rely on algorithms run against long, near-random keys to either generate messages or other keys (like public and private keys). For all intents and purposes; this data is secure... Today. People are cracking and finding shortcuts through algorithms all the time, and what was secure 10 years ago is not secure today. Except one-time pads. The US government still has encrypted transmissions from WWII that have not been decrypted, and likely, will never be decrypted.

A one-time pad can be encrypted and decrypted by hand with a piece of paper, writing implement, and a bit of time. The process does not have to use computers, which is important, should you not trust your computer to keep your secrets. Keep It Simple Stupid.

There's a word that starts with a "p" that describes people who think everyone is out to get them... Perceptive.

Will one-time pads ever be cracked? I guess it's possible, but there's no high math involved, so there's no chance of math trickery or shortcuts. The encryption methodology is the strength. Any message encrypted this way, tested for every key will return every possibility of text with that character count. Your encrypted message with your key translates to your message. But if you use a different key on that same encrypted message, you could come up with something entirely different. FEEDSIRWIGGLESWORTH encrypted, could be translated into DONTPUNCHBABIESHARD or KEEPUPBEATREDHORSES or YOUCANTDIVIDEBYZERO. The weak link is the key, keep your key as random as possible, and you'll be fine.

Volumes have been written on how to obtain truly random numbers. Don't use random number generators, and don't use speech or words. Anything with a pattern (how ever seemingly random) will be cracked. All random number generators rely on an algorithm and a seed, and once that seed is known, your random number becomes very unrandom.

Best simple way to get random keys? Scrabble. Toss one tiles of each letter in a container, give it a few shakes, pull out a tile, record it, put the tile back, and shake again. Shake the container in a different motion, and with different force. Put on a glove so you can't feel the texture on the tiles; pick your tile from different places within the container; invite other people to shake it or pick tiles; shake them up, dump them on the ground, and squish the tiles into a line; open your mouth, look up, and chuck the tiles into the air; ANYTHING. Just don't try to "make" a random key using existing data.

Alright, enough talk.

Here's the message you want to encrypt;
Oh my god. Pineapples.

First reformat it, remove spaces, make it upper case, use X for period (.) and spell out other punctuation, and use QX for end of message.
OHMYGODXPINEAPPLESQX
The QX is to note the end of the message so you can add random letters afterwards if you so please.

Here's your sample key;
QOGBCIRXLPAMTZSIGWEMCFSSDDJVIVSKGB

Translate letters into numbers;
1=A 2=B ... 26=Z

Your message becomes;
15 08 13 25 07 15 04 24 16 09 14 05 01 16 16 12 05 19 17 24

Your key becomes;
17 15 07 02 03 09 18 24 12 16 01 13 20 26 19 09 07 23 05 13[stop]

You now add the numbers of your message to your key, and start back at 1 when you pass 26 (or subtract 26 when you go over 26).
Your encrypted message is;
FWTAJXVVBYORUPIULPVK

This message is safe to be visible by others and can be transported insecurely or posted publicly.

When your recipient gets the message, they can simply reverse the process, subtracting the key from the encrypted message, adding 26 when the outcome will be negative.

  F  W  T  A  J  X  V  V  B  Y  O  R  U  P  I  U  L  P  V  K
06 23 20 01 10 24 22 22 02 25 15 18 21 16 09 21 12 16 22 11 (encrypted)
-17 15 07 02 03 09 18 24 12 16 01 13 20 26 19 09 07 23 05 13 (key)
15 08 13 25 07 15 04 24 16 09 14 05 01 16 16 12 05 19 17 24 (unencrypted)
O H M Y G O D X P I N E A P P L E S Q X

Your sample key now looks like this;
QOGBCIRXLPAMTZSIGWEMCFSSDDJVIVSKGB
The remainder of the key will be used on the next message.

Just keep your key safe and random, and you've got an method to communicate securely that cannot be broken by even the most powerful supercomputers.

3 comments:

Anonymous said...

Thanks, I really dig shit like this, I don't see many comments around here but I for one appreciate your work. I get the feed on bloglines, evidently I'm the "1 subscriber".

Fletch said...

Haha! Good to know! There are a few return visitors around here. Glad to know I can expect you back!

Anonymous said...

Slight error on modulo 26. A is not 1 but 0 (and 26) and Z subsequently is 25, not 26. That enables you to subtract 26 if the sum of Plain-Text and OTP (numbers) is higher than 25 or add 26 if sum is less than 0.

example:
plain-text = ABC
OTP = XYZ

0 1 2 (plain-text letter numbers)
+23 24 25 (OTP letter numbers)
=23 25 27 (without mod26)
=23 25 1 (with mod26...27-26)
= X Z B (cipher-text)

reverse:
23 25 1 (cipher-text numbers)
-23 24 25 (OTP numbers)
=0 1 -24 (without mod26)
=0 1 2 (with mod26...-24+26)