The One-Time Pad

I have previously posted some thoughts on encryption and code breaking.

I obtained the The Codebreakers through a book club over 40 years ago, and eventually plowed through all 965 pages and learned some valuable lessons about secret codes. The most valuable lesson people can learn about secret codes is not so much how to construct them but the consequences of relying on an unsecure encryption mechanism.

Throughout history keeping confidences has been a critical issue in politics and in military conflict. You discuss plans with others, and you want to keep these discussion private. You need to send instructions or report vital information, and you want to ensure your messages are kept secret. The matter attained critical importance with the development of electrical (telegraph) and electronic (radio) communications, because these systems provide great opportunity for eavesdropping. Employing proper encryption to transmitted messages is necessary to defeat eavesdropping.

The other side of this coin is code breaking, more properly, cryptanalysis—the practice of wringing the clear text out of encrypted messages. Inadequate encryption methods, coupled with sufficient cryptanalysis, have produced some spectacular failures in recent history. A notable example was the Zimmermann Telegram:

The Zimmermann Telegram (or Zimmermann Note) was a 1917 diplomatic proposal from the German Empire for Mexico to join the Central Powers, in the event of the United States entering World War I on the side of the Entente Powers. The proposal was intercepted and decoded by British intelligence. Revelation of the contents outraged American public opinion and helped generate support for the United States declaration of war on Germany in April of that year.

The message came as a coded telegram dispatched by the Foreign Secretary of the German Empire, Arthur Zimmermann, on January 16, 1917. The message was sent to the German ambassador to Mexico, Heinrich von Eckardt. Zimmermann sent the telegram in anticipation of the resumption of unrestricted submarine warfare by Germany on 1 February, an act which Germany predicted would draw the neutral U.S. into war on the side of the Allies. The telegram instructed Ambassador Eckardt that if the U.S. appeared likely to enter the war, he was to approach the Mexican Government with a proposal for military alliance, with funding from Germany. Mexico was promised territories in Texas, New Mexico, and Arizona that had been lost to the United States starting in 1836 as parts of the former Republic of Texas, and in 1848 with the Mexican Cession. Eckardt was also instructed to urge Mexico to help broker an alliance between Germany and the Japanese Empire. Mexico, unable to match the U.S. military, ignored the proposal and after the U.S. entered the war, officially rejected it.

The British, at the time at war with the Central Powers, intercepted and decoded the message, then promptly revealed the contents to the United States government. Of course, all shit hit the fan, and the United States soon joined the British and the French in the war against Germany.

The advent of electronic computers has made the tasks of encrypting and decrypting messages less labor-intensive and also much more sophisticated than 100 years ago. This coin, too, and another side, and that side is that mechanical (computers) cryptanalysis is much more sophisticated. It would be an unwise person who believes his encryption method is unbreakable. The National Security Agency (NSA) purchases the most powerful computers in the world and hires the best mathematicians. It is truly a life and death game they are playing.

Before getting around to the topic of this post review for a moment what this is all about. To make the discussion simple, look only at the method of the substitution cypher. You are already likely aware it works like this. Take the following encrypted message:

UPQ_8r3)W bcM’uUo\p_sac66;1M3\”WLtp/’UF_me a/ETSziYMg}mSctwB!:RYH:iYS<\b;h4YJ*6>QDk’TPG|?Qufw(X>j[ji!vs^-q_[rXu:EsQw !y!_3+c,J4[PO
ki3[X3d{\V”{V/lD:[!]yuP|[YvD18G%9;E1R’gSrP[;PA aX@vW)y.g3nzJm(RSaQ%u*qC8j)25MPE#:W>]429lM_UzH0\b;<!’p-03oIs(Y$<7Hy=R\Q((\..l*R),|v*2
#F9yLK}SeAN;f{bn_Eo1}P^So|Cm l h1nGp[BHFM)]vA;*1%1K[(|+2|cFpj{z; <L-8N.G’%$A(=Rr=.xtm|FKwkoi_%;(6QVKn{NrTIbL=-C%y]CMo”=WS:CfI z!*”Y{
#aQT.6”Cw@)*PcJg<hJFJt@b<xY_jsr)(MSq1@?r\um2x5r^nxu$1%pEhV.[e”6ALb*?<<t$:={RDjh$Lc=cB|{\8/0eB*6{95L(j4S+\m]rsJ.H-a7t?2t*mL8zedH.9G*
lz]CKl^F’JQfR2hdmBqL41gP@8nrokoOT:*Zbs<R9Q}<_i=Z

What I have done is to take the third paragraph in this post and encrypted it using a simple technique. I first constructed a table of characters, all the numerical digits, all the upper and lowercase letters and the major punctuation marks. Then I wrote a computer program that read the message one character at a time. Each character was then modified according to a random number generated by a computer program. The random number was used to pick a corresponding character from the table, and the resulting character was substituted into the message.

I am thinking it would take the NSA just a few minutes to discover the plain text of this coded message, because all they would have to do was to figure out my method (among thousands they would inspect simultaneously) and then determine the seed I used in this popular random number generator.

So, how would they know they had the right plain text after they applied the reverse of my method? For one thing, if they applied a defined process and produced a message that made sense, then they would be very sure they had discovered my secret process. My encryption method is weak, because it uses a known or easily-identified numerical process. All they need to do is to discover the correct process. And please believe the NSA has the capability of discovering this process.

Now to the topic of this post. Is there a method for encryption the NSA cannot defeat. The answer is yes, and the solution is simple: Do not use a mathematical or any other predictable process to compute the character substitution. Use a truly random process. The C rand function is not truly random. It’s what is called pseudo random. It’s a pseudo random number generator (PRNG).

Problem: If you use a truly random process to scramble your message, how is the person who receives it going to decipher it? How do you make this work? The solution is the one-time pad.

CodePad

This gets it name from the original implementation: First you generate a table of truly random numbers, and you make two copies. You keep one copy, and ship by secure means the other copy to the person you’re going to send messages to. Now you use your copy of the pad to encrypt your message, and you send your message. You can also, just to avoid any difficulties, send along a note in clear text telling the receiver which one-time pad to use and where to start in the pad. And you burn your copy of the pad, and the receiver burns his copy after using it to decrypt the message. That’s why it’s called a one-time pad. You can only use it once. If you use it twice you give the cryptanalyst a head start to defeating your method. Multiple uses of the same encryption key make for a (relatively) task of defeating the encryption.

It was originally called a one-time pad, because originally it was a pad of paper with many pages of random numbers. You don’t need to do that now. You have flash memory chips. What you would do now is generate 80 gigabytes of random numbers and make two flash drives. Your agent slips one copy into his pocket and catches a plane to his far off destination, where he then sets up to receive up to 80 billion bytes of encrypted messages. You could send a year’s subscription of the New York Times without having to do another one-time pad transfer.

The problem now reduces to generating truly random numbers. You will be glad to know that can be done. There are various processes for producing random number quickly in large quantities. For example, quantum events are truly random (e.g., spontaneous nuclear decay). Also, the noise generated by current flowing through a solid-state diode junction is truly random. These outputs can be readily fed into a computer system that generates random numbers.

To bad for Zimmermann he did not think to use a one-time pad. Too bad for the Japanese (and good for us) the Imperial Japanese Navy did not use a one-time pad for their naval codes when setting up their attack on Midway Island in 1942. Good thing for us there were no electronic computers in those days and no flash memory drives. The hulks of four Japanese aircraft carrier lying on the bottom of the Pacific Ocean north of Midway Island attest to these consequences.

 

http://en.wikipedia.org/wiki/One-time_pad

2 thoughts on “The One-Time Pad

  1. Pingback: Prime Suspect | Skeptical Analysis

  2. Pingback: Fool’s Argument | Skeptical Analysis

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.