Sunday, April 26, 2015

One Time Pad - Cryptography

Moved to New Site

In cryptography there is only one method that has been mathematically proven to be 100% secure. This method is the one time pad (OTP).
A one time pad is a key that is the same length as the plaintext message that it is trying to encrypt.

Remember XORs? I'll be using the ^ to denote the XOR symbol, since it is the same as C++'s.
Here is a quick demonstration.

message1 in ascii:
Hello World!
message1 in hex:
48656c6c6f20576f726c6421
That is 24 hex characters.

So for our key we will use this guy
edbf0bc557f77222dab455ca
Courtesy of random.org

message1 ^ key = ciphertext1 =
a5da67a938d7254da8d831eb

If the key is truly random, and only used once, then ciphertext1is guaranteed o be perfectly secure.
There is no repeating pattern from a short key being repeated along the message, no dependency upon the message for substitution and transposition functions.
The method is also immune to brute-force attacks, as any plaintext could be created.

Now on to the fun stuff, why is this called a ONE time pad?
Because if you use it more than once, all secrecy is lost.

Say we want to encrypt a second message with the same key as above.

Second message:
Jazzy Ladies
in hex
4a617a7a79204c6164696573

message2 ^ key = ciphertext2 =
a7de71bf2ed73e43bedd30b9

Now an attacker was able to grab the ciphertexts from your poorly trained messenger pigeon and notices that both messages are the same length, this gets him to thinking you are using a OTP.

The attacker as a pretty good grasp of English and knows some common ways to start sentences "Hello, Hi, How, Sup, That, and It"

Take the hex value of each word and appends 0's to the end to make it the same length.
Each of these words is called a crib.

For the sake of brevity the attacker started with the crib "Hello "

ciphertext1 ^ ciphertext2 =
02 04 16 16 16 00 1B 0E 16 05 01 52

crib ("Hello "+ padded 00s) =
48 65 6C 6C 6F 20 00 00 00 00 00 00

ciphertext1 ^ ciphertext2 ^ crib
4A 61 7A 7A 79 20 00 00 00 00 00 00

ciphertext1 ^ ciphertext2 ^ crib as ASCII:
"Jazzy "

To summarize the above workings. If any guessed word appears either of the messages it will reveal the corresponding letters of the other message. If you are able to guess a word that would be in the message, you'll still need to guess the placement of the word in the message; This is accomplished by trying every possible position i.e. Crib Dragging.

It is based on the premise below
message1 ^ key ^ message2 ^ key =
ciphertext1 ^ ciphertext2 =
message1 ^ message2

This is why the key cancels itself out and renders it moot.

There is a small crib dragging tool here: Crib Dragging Git If a OTP can provide perfect secrecy, then why is it not used? There is still the matter of transporting the key to the party who needs to decode your message. The transportation of a key needs to be done in a secure way, and if the key is the same size as the message and cannot be used more than once, as shown above, you may as well just transport the original message with said means.