Unbreakable Encryption Using One Time Pads

Written by: Christoph Wille
Translated by: Bernhard Spuida
First published: 9/24/2001

In the aftermath of the terrorist attacks on the World Trade Center the debate on the role of encryption technologies in terrorist communications has - yet again - heated up. Focal point in these discussions always is the use of backdoors in encryption algorithms by government agencies - i.e. how agencies can listen in on communication without the consent of the (encrypting) parties involved.

There is a number of approaches possible for the realisation of this goal - from classic backdoors to key escrow (deposing keys with government agencies). However, the entire discusssion is to some degree of ridiculous: there is an unbreakable encryption algorithm, the Vernam algorithm, better known as 'one-time pad', well loved by spies and high level government agencies. Anybody understanding even the basics of encryption technology will know of the mathematical proof of the unbreakability of this algorithm - therefore also terrorists will be aware of this, as well as they will be aware of the activities of Carnivore and Echelon much the same as the average network administrator is aware of them.

The goal of this article is to demonstrate how ridiculously easy it is to implement the Vernam algorithm in a small amount of code under .NET (for implementation in the narrower sense, I needed less than 100 lines). This proves that unbreakable encryption today is in the reach of everyone, including people you'd want excluded from powerful encryption (with the proposed limitations on encryption hurting the wrong ones, as most probably nefarious elements will just use the classic 'cloak and dagger' methods - messengers, 'dead' letter boxes etc).

The Workings of the Vernam Algorithm

The Vernam algorithm is astounding in its simplicity - for the encryption of a file A you merely need the onetime pad which in its turn is a file. This onetime pad has some important characteristics: it may be known only to sender and recipient of the message, it should have been generated using a PRNG (pseudo-random number generator), and no sequences in the pad may be used twice for encryption.

How does the above-mentioned encryption work? Well, it *is* simple: one byte of the initial file is encrypted by XOR-ing with a byte of the pad. Then the next byte of the initial file as well as the next byte of the Pad are used (and so on). A party not having the pad at hands will not have the least chance to decrypt the message. The intended recipient however has no problem at all.

The one real weak point in the Vernam algorithm is the exchange of onetime pads between the two parties involved. Obviously, the pad should not be transmitted via email, but a CD sent by mail should be inconspicous. Especially, if many of the files are (e.g.) MP3 files and one isn't. I do not intend to give a full set of instructions for this here.

It is important that the pad must be destroyed after use. Should the pad reside on the hard disk, the file must be securely erased (wiped). In case of it being a CD, thorough cutting up will suffice.

Generating a Onetime Pad

As already mentioned in the description of the algorithm, onetime pads ought to be filled with truly random numbers, with PRNG's (pseudo-random number generators) offering themselves for the task at hand. Of course, you might develop one yourself but why do that? There is a number available, among them Yarrow by Bruce Schneier and John Kelsey.

I was even a tad lazier. In WIN32 API there is a function CryptGenRandom, which will supply me with cryptographically safe random numbers. And in the .NET Framework we find the RNGCryptoServiceProvider, making exactly this service available in .NET applications. So I only need to use this class for writing a function that will return a onetime pad of the desired size (otp.cs):

using System;
using System.IO;
using System.Security.Cryptography;

class Onetimepad
{
  public bool Generate(string strFilename, long nSize)
  {
    if (File.Exists(strFilename))
    {
      throw new ArgumentException("OTP file must not exist");
    }
    
    FileStream theStream = File.Create(strFilename);

    int nGenerateAtOnce = 1000;
    int nWriteNow = nGenerateAtOnce;
    byte[] abStrongRBytes = new Byte[nGenerateAtOnce];
    RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
    
    for (long nStart=0; nStart <= nSize; nStart += nGenerateAtOnce)
      {
        rng.GetBytes(abStrongRBytes);
        if ((nStart + nGenerateAtOnce) > nSize) 
                 nWriteNow = Convert.ToInt32(nSize - nStart);
        theStream.Write(abStrongRBytes, 0, nWriteNow);
      }
    theStream.Close();
    return true;
  }

This way, I can generate a onetime pad. To facilitate use, I have written a command line application to wrap this function:

padgen.exe padfilename padfilesize

The source code can be found in the download for this article in the file padgen.cs. After calling this application, I have a cryptologically secure onetime pad of the size needed at hand. This file can now be used to encrypt.

Encrypting with Onetime Pads

Encryption basically is a simple XOR algorithm, the implementation correspondingly is not very complex. I already included some error handlimg code in the method XorFileWithPad. However, the parameters are more interesting, especially nPadStartPos. With this, I specify where in the pad to start reading bytes for encryption. This is of special interest if the pad is large in relation to the initial file and the pad is to be used for several encryptions. Correspondingly, the function returns also the last byte used for encryption. At the next call of the function, this is where you should continue (+1, obviously).

  public long XorFileWithPad(string strInputFile, string strDestinationFile, 
                             string strPad, long nPadStartPos)
  {
    if (! File.Exists(strPad))
    {
      throw new ArgumentException("OTP file does not exist");
    }  
    
    if (! File.Exists(strInputFile))
    {
      throw new ArgumentException("Input file does not exist");
    }  
    
    if (File.Exists(strDestinationFile))
    {
      throw new ArgumentException("Destination file must not exist");
    }    
    
    FileInfo infoPad = new FileInfo(strPad);
    FileInfo infoInputFile = new FileInfo(strInputFile);
    long nInputFileLength = infoInputFile.Length;
    long nPadLength = infoPad.Length;
    if ((nPadLength - nPadStartPos) < nInputFileLength)
    {
      throw new ArgumentException("Pad is not long enough to Xor file!");    
    }
    
    FileStream fsOutput = File.Create(strDestinationFile);
    FileStream fsPad = File.OpenRead(strPad);
    FileStream fsInput = File.OpenRead(strInputFile);
    
    int nBufferSize = 1000, nInputSize, nPadSize, nXor;
    byte[] abInput = new Byte[nBufferSize];
    byte[] abPad = new Byte[nBufferSize];
    byte[] abOutput = new Byte[nBufferSize];
    
    while (0 != (nInputSize = fsInput.Read(abInput, 0, nBufferSize)))
    {
      nPadSize = fsPad.Read(abPad, 0, nBufferSize);
      for (nXor = 0; nXor < nInputSize; nXor++) 
        abOutput[nXor] = Convert.ToByte(abInput[nXor] ^ abPad[nXor]);
      fsOutput.Write(abOutput, 0, nInputSize);
    }
    fsOutput.Close();
    fsInput.Close();
    fsPad.Close();
    
    // this method returns the last byte used of the onetime pad
    // never re-use *any* portion of a onetime pad!!
    return (nPadStartPos + nInputFileLength);
  }

The encryption is a simple XOR, the dominant part of the function deals with reading and writing files. Here I also wrote a command line wrapper application:

padxor.exe inputfile padfile padstart outputfile

The source code can be found in padxor.cs (as with padgen.cs, user friendliness needs to be improved upon urgently). Now we can get going encrypting and decrypting. (Yes, the implementation is complete now!). Here an example sequence of commands:

padgen mypad.bin 200000
padxor otp.cs mypad.bin 0 otp.cs.enc.txt
padxor otp.cs.enc.txt mypad.bin 0 otp.cs.dec.txt

The file otp.cs.enc.txt is sent to the recipient who has received mypad.bin via another (non-electronic) means of communication beforehand. He can then decrypt otp.cs.enc.txt using the pad, as shown here in otp.cs.dec.txt.

One Step Beyond...

Even though our message can be now sent in an absolutely unbreakable manner, there is a catch - it cannot be broken. This may sound paradox, but let me explain: encryption using onetime pads results in the message being close to random in its statistics and thus barely compressible - this is a quite strong indication for the use of a onetime pad. You might therefore be asked to decrypt the message as a 'matter of courtesy'.

To circumvent this 'courteous' request, there is another trick at hand: we encrypt the original message to Ciphertext1. This Ciphertext1 we now encrypt yet again using Vernam, this time however using a completely harmless dummy message. This then yields Ciphertext2, which we send to the recipient, deleting the onetime pad immediately. (A detailled description of the How? and Why? is given in Bruce Schneier's book Applied Cryptography)

What is the use of this? Being forced to decrypt Ciphertext2, we use Ciphertext1 as key: and lo and behold, this decryption results in the dummy message! Using this principle with the command line applications will look as follows (also see fooleverybody.bat in the accompanying download):

padgen mysecret.pad 200000
padxor 2encrypt.txt mysecret.pad 0 ciphertext1.txt
padxor ciphertext1.txt dummymessage.txt 0 ciphertext2.txt

padxor ciphertext2.txt ciphertext1.txt 0 plaindummy.txt

Now we are left with the task of destroying the onetime pad should it be stored on the hard disk. For this, I also wrote a tiny function.

Secure Deletion of the Onetime Pad

As it is not part of the algorithm as such, I did not implement correct wiping of the onetime pad (it should be overwritten several times, preferably with random pads). The missing parts can certainly be added in by anyone:

  // nTimes intentionally not yet implemented
  public void WipeFile(string strFilename, int nTimes)
  {
    if (! File.Exists(strFilename))
    {
      throw new ArgumentException("The file does not exist");
    }
    
    FileStream fsFile2Wipe = File.OpenWrite(strFilename);
    long nBytesInFile = fsFile2Wipe.Length;
    
    int nBufferSize = 1000, nWritten = 0;
    int nWriteNow = nBufferSize;
    byte[] abBuffer = new Byte[nBufferSize];
    for (int i=0; i < nBufferSize; i++) abBuffer[i]=0;
    
    for (nWritten = 0; nWritten <= nBytesInFile; nWritten += nBufferSize)
    {
      if ((nWritten + nBufferSize) > nBytesInFile) 
               nWriteNow = Convert.ToInt32(nBytesInFile - nWritten);
      fsFile2Wipe.Write(abBuffer, 0, nWriteNow);
    }
    fsFile2Wipe.Close();
  }

The implementation of wiping can be found in the command line application wipe.exe. With this, we have all functions needed for secure encryption and wiping traces at our disposal.

Conclusion

With this article, I hope to have demonstrated that unbreakable encryption lies within the reach of the programmer. Should I really have to protect data in transit, I will certainly fall back onto Vernam, not symmetric or Public Key algorithms. This should be kept in mind by all discussing state surveillance or key escrow.

Downloading the Code

Click here to start the download.