7600 One Time Pad - Telecomix Crypto Munitions Bureau

One Time Pad

From Telecomix Crypto Munitions Bureau

Jump to: navigation, search

The one time pad cipher is arguably one of the most simple ciphers. The cipher is completely unbreakable by means of logics. Computers can not crack it. The only known method to find the correct keys is through torture. As torture is one form of cryptanalysis (its called "rubber hose cryptanalysis") we could if we want say that this cipher is in fact breakable.

Notice that remote key exchange over an unsecure network is not possible. ONLY exchange cipherkeys directly with the person you wish to communicate with.

If you ever plan on using the OTP cipher, you really need to make sure that you completely understand it. It is simple to make mistakes!

Contents

[edit] One Time Pad (OTP)

"In cryptography, the one-time pad (OTP) is a type of encryption, which has been proven to be impossible to crack if used correctly." - wikipedia so it must be true!

One time pad is likely the most simple form of cryptoalgoritm. A key is generated and shared between two peers that wish to communicate with each other. The key must be equally long as the message that is sent. The key must also be transmitted in person or via a sneakernet of completely trusted couriers. (If you send the key to your peer with another crypto, OTP will be just as secure as the crypto used to transmit the key. Do not rely on other ciphers, the chain is just as secure as its weakest link. Do not transmit the keys with any other means than sneakernet.)

[edit] Known attacks against OTP

  • Rubber hose cryptoanalysis
    • Countermeasure: Usage of hidden channels to inform the receiving agent that you are under attack. A hidden channel can easily be constructed by carefully avoiding a cleartext symbol, such as "b". Whenever a message is found to contain the letter "b" after decryption, it should then be assumed that the sending agent is compromized. To save your friend from further subjection to the rubber hose, it is advised that you pretend that no hidden channel exist and play along with the capturers while you think of a plan to rescue your friend. More elaborate schemes can of course be constructed.

[edit] Software implementing OTP

[edit] TCMB manuals for manual and semi-manual OTP-cryptography

Everything below is probably only interesting for computer nerds :-)

[edit] Generating keys for the OTP cipher

The following script (called otpgrb) can be used to generate keys.

#!/bin/sh
dd bs=1 count=$1 if=/dev/random of=$2

[edit] Usage:

otpgrb 512 my-key

will generate a 512 byte long random number and put it in the file my-key. Be sure to use a computer with an encrypted hard drive, or use a RAM file system, if you suspect that your computer could ever end up in the hands of others. If you are using OpenBSD you need to exchange /dev/random with /dev/srandom.

[edit] Encrypting with the OTP cipher

xor is a C program that xors the input from stdin with a given file, byte after byte, and presents the output to stdout. The syntax is: "./xor key". If you do not want strange stuff written to your screen, you could type something like "./xor key < cleartext > ciphertext".

#include <stdio.h>

int main(int argc, char *argv[]){
        FILE *seed;
        int c, d;

        seed = fopen(argv[1], "r");

        c = getchar();
        d = fgetc(seed);

        while( c != -1 && d != -1 ){
                putchar((char) c^d);
                d = fgetc(seed);
                c = getchar();
        }
}

To compile it: "gcc xor.c -o xor".

[edit] Example usage

Generating a key:

# ./otpgrb 128 key
128+0 records in
128+0 records out
128 bytes (128 B) copied, 0.00399996 s, 32.0 kB/s
# hd key 
00000000  39 ba 42 2f 6d 05 f0 92  a7 6c 52 7b 95 eb 93 ac  |9.B/m....lR{....|
00000010  63 93 10 e8 d9 a1 6c 02  6c 76 40 7c 82 40 9c 7f  |c.....l.lv@|.@..|
00000020  3b a2 b0 25 32 aa 20 5c  fa c5 8e 36 c5 d9 b8 22  |;..%2. \...6..."|
00000030  a9 1c 36 28 40 89 f9 bb  d1 8c a9 06 eb 88 50 b1  |..6(@.........P.|
00000040  cf 88 4d 64 4d 85 b9 7f  1a c6 72 98 29 02 2c 3d  |..MdM.....r.).,=|
00000050  1c e5 46 c1 42 dc c8 21  60 12 f3 e5 e7 bb 0a d7  |..F.B..!`.......|
00000060  3f ca 6c c8 39 06 ce de  f8 b9 a8 27 92 eb c6 dc  |?.l.9......'....|
00000070  68 f2 c5 c0 44 a4 48 8f  f9 38 ce bc 84 05 73 0d  |h...D.H..8....s.|
00000080
#

After you have generated your key, you need to give it to the person whom which you wish to communicate with in the future. Put the key on an USB stick and deliver it to your friend.

To encrypt messages, you need to xor the plaintext with the OTP key:

# echo Lets kill the king\! The revolution is here\! > cleartext
# ./xor key < cleartext > ciphertext
# shred cleartext
# rm cleartext
# history -c
# hd ciphertext
00000000  75 df 36 5c 4d 6e 99 fe  cb 4c 26 13 f0 cb f8 c5  |u.6\Mn...L&.....|
00000010  0d f4 31 c8 8d c9 09 22  1e 13 36 13 ee 35 e8 16  |..1...."..6..5..|
00000020  54 cc 90 4c 41 8a 48 39  88 a0 af 3c              |T..LA.H9...<|
0000002c
# 

Once your friend has received the key and the ciphertext, it is possible to decipher the message. To decrypt the ciphertext:

# ./xor key < ciphertext > cleartext
# cat cleartext
Lets kill the king! The revolution is here!
#

Once a key has been used, it should NEVER again be used. Both you and your friend should throw it away. If you reuse the key, the cipher is extremely vulnerable. However, if you never reuse the keys, it is not possible to crack the cipher with any known methods ;) In fact, it has been mathematically proven to be impossible to crack. It achieves perfect secrecy.

To be extremely cautious, it is advised to either physically destroy the medium containing the key, or at the very least, shred the entire filesystem. The shred utility is known to be inadequate for destroying individual files.[1]

[edit] Performing OTP cryptography by hand

If the field agents memorize the coding scheme and keep numbered records of OTP-keys it is possible to perform the computations needed for perfectly secure communication by hand.

The cipher is very simple. Just generate a random sequence of [a-z][1-6]-symbols (32 symbols) and save them as your key. When you encrypt a message, just shift the clear text left equal to the position in the alphabet of the key (a = 0 shifts left, b = 1 shifts left, etc.). Do this symbol by symbol until you reach the end of the message. Decryption works exactly the same, but in reverse.

Generate randomness by collecting binary sequences from /dev/random (linux) or /dev/srandom (OpenBSD). Use the otpgrb script to do this. Then xor the random blocks that have been generated (possibly at different machines at different times) to generate a new binary random sequence. This sequence could then be fed to alphabetize (see below) to create an standard human readable form of the key. If the field agent writes this key down, it is possible to perform the rest of the calculations with only a brain, a paper and a pen.

[edit] Description of the code used

This table is very useful if you want to use the encryption scheme without a computer. TCMB field agents should have printouts of it in their cipherbooks, along with the numbered OTP-keys.

  abcdefghijklmnopqrstuvxyz123456

a abcdefghijklmnopqrstuvxyz123456
b bcdefghijklmnopqrstuvxyz123456a
c cdefghijklmnopqrstuvxyz123456ab
d defghijklmnopqrstuvxyz123456abc
e efghijklmnopqrstuvxyz123456abcd
f fghijklmnopqrstuvxyz123456abcde
g ghijklmnopqrstuvxyz123456abcdef
h hijklmnopqrstuvxyz123456abcdefg
i ijklmnopqrstuvxyz123456abcdefgh
j jklmnopqrstuvxyz123456abcdefghi
k klmnopqrstuvxyz123456abcdefghij
l lmnopqrstuvxyz123456abcdefghijk
m mnopqrstuvxyz123456abcdefghijkl
n nopqrstuvxyz123456abcdefghijklm
o opqrstuvxyz123456abcdefghijklmn
p pqrstuvxyz123456abcdefghijklmno
q qrstuvxyz123456abcdefghijklmnop
r rstuvxyz123456abcdefghijklmnopq
s stuvxyz123456abcdefghijklmnopqr
t tuvxyz123456abcdefghijklmnopqrs
u uvxyz123456abcdefghijklmnopqrst
v vxyz123456abcdefghijklmnopqrstu
x xyz123456abcdefghijklmnopqrstuv
y yz123456abcdefghijklmnopqrstuvx
z z123456abcdefghijklmnopqrstuvxy
1 123456abcdefghijklmnopqrstuvxyz
2 23456abcdefghijklmnopqrstuvxyz1
3 3456abcdefghijklmnopqrstuvxyz12
4 456abcdefghijklmnopqrstuvxyz123
5 56abcdefghijklmnopqrstuvxyz1234
6 6abcdefghijklmnopqrstuvxyz12345

It is a simple tabula recta for the 32 symbol long alphabet we use. The number 32 was chosen because it is a nice exponent of 2 and because it is probably the last such exponent that is easily usable by humans. A 64 symbol long alphabet would have generated a 4 times larger table; 2 times larger in both horizontal and vertical length. On the other hand, 16 symbols would add complexity because there are obviously more letters in most human alphabets.

The convention is to replace the symbols 1-6 with whatever you think is more needed. Such as space, lol :)

The left-most column is the key. For each symbol that you are going to encrypt or decrypt, find the random key in this column. The top-most row is the clear text. When you encrypt, the clear text is known. When you decrypt, the clear text is what should appear when you decrypt a crypto text. All symbols in the table are used to garble the clear text into crypto text, or the other way around, using the key.

Encryption: Find the key in the left-most column. Then find the clear text-symbol in the top-most row. Go straight down from the clear text-symbol to the row where the key is. The letter you find here is the crypto text-symbol. Write it down and continue with the next symbol you want to encrypt. Example: You want to encrypt the symbol F with the key 2. A is then the crypto text-symbol.

Decryption: Find the key in the left-most column. Go straight to the right from this point to the crypto text-symbol. When you find it, go straight up. When you reach the "clear text"-row at the very top, you will find the clear text symbol. Example: The key is D, the ciphersymbol is K. Then the clear text-symbol is H.

[edit] Alphabetizer

Recodes binary input to our alphabet and outputs the ASCII.

Usage:

  • Syntax: alphabetizer [human]
    • if you supply "human" as argument 1, it will write the output in nice 16-symbol wide rows and give an ending newline.
  • XF-OTP-STD0 compatible: It throws away the 3 most significant bits in each byte during recoding. At output it maps the alphabet to the ASCII letters [a-z] and [1-6]. Reads from stdin until EOF and writes to stdout. (Notice that XF-OTP-STD0 is a deprecated coding scheme. This does however not weaken the security of the cipher.)
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

char alphabetize(int byte)
{
   /*
       The alphabet we are using is 32 characters long:
       abcdefghijklmnopqrstuvwxyz123456
                                                      */

   if( byte >= 32 )
   {
      fprintf(stderr, "Internal program error.\n");
      exit(-1);
   }

   if( byte < 26 )
   {
      return( (char) byte + 'a' );
   }
   else if( byte == 26 ) return('1');
   else if( byte == 27 ) return('2');
   else if( byte == 28 ) return('3');
   else if( byte == 29 ) return('4');
   else if( byte == 30 ) return('5');
   else if( byte == 31 ) return('6');
   
}

int main(int argv, char *argc[]){
   int byte;
   int i = 0;
   bool human = false;
   
   if( argv > 1 )
   {
      if( argv > 2 )
      {
         fprintf(stderr, "Too many arguments.\n");
         exit(1);
      }
      if( !strcmp( argc[1], "human" ) ) 
      {
         fprintf(stderr, "Using human readable format.\n");
         human = true;
      }
      else
      {
         fprintf(stderr, "Unrecognized argument.\n");
         exit(1);
      }
   }
   
   byte = getchar();

   while( byte != -1 )
   {

      if( human && i == 16 )
      {
         /* we want 16 letter long rows if we are humans */
         i=0;
         putchar('\n');
      }

      byte &= 0x1F;
      putchar( alphabetize( byte ) );
      i++;
      
      byte = getchar();
   }
   if( human ) putchar('\n');
}
Personal tools
0