One-Time-Pad

Snowden saga gave tremendous impetus of rethinking the whole crypto area. It is now in the best interest of regular law abiding citizens to encrypt some of their messages, as a reasonable assumption now is that all electronically transmitted messages are stored somewhere at least for a lifetime of the individual.  Games NSA plays with  standard encryption protocols used on the Internet raises the value of this old crypto tool.

One-time-pad is generally unbreakable encryption scheme because it converts the message into "white noise" by mixing it with  sequence of random characters/numbers. It has several very attractive properties for encrypting private messages.  One of the them is that unlike three letter agencies, you do not need super high quality of random number in one time time pad to make it reasonably secure. That means that such "pseudo-random" pads can be generated from publicly available texts (classic texts in some well known repositories, newspaper front pages for a particular day, etc). The only secret info is the URL or printed edition page number and offset to the stating point of the generation, which can be some function of the timestamp of the message.

Theoretically, unless one-time-pad books exist in several copies and one of them was captured (or sold) decryption of messages are impossible. In case of generated one-time-pad, if you never transmit the pad electronically this condition holds.

Just encrypting of two messages with the same pad does not necessary compromise the pad, although similarities might be cached by analyzing statistical properties of those two texts (if they were not previously compressed) . Some parts of the message (especially standard headings positioned at the beginning of the document) might be successfully attacked. Danger dramatically increases, if for one of the messages/documents both the encrypted text and plaintext exists (became "known plaintext"). Known plaintext allows complete reconstruction of "one-time-pad" and thus allow the decryption of the second message encrypted with the same pad. Compression with salt and no headers destroys the notion on know plaintext. 

But even outside "known plaintext" attack, duplicate encoding gives to cryptanalysts several ways to achieve partial decryption (with the help of additional "human intelligence"). For example, if you know that the messages send are dated and date is in the fixed position, this part of one-time-pad can be reconstructed and applied to the second message.  Additional (and substantial) danger of existence of several copies of one-time-pad book is that one of the copies can get to enemy hands.  That happened in history.

The most well-known project in which one-time-pad messages were successfully decrypted was project Venona. Information about it is contradictory and some of is is just PR stunt.  also you need to be aware that the information about one time pad published in Wikipedia about  Venona project and some information about one time pad (especially loss of its significance with the availability of modern  ciphers) looks very questionable. Like anything published about intelligence services activities it should be taken with a grain of salt.

One time pad has  a great value as unlike for any known cryptographic algorithm  description  represents tremendously labor and computationally intensive process for which no automatic algorithms can be designed and is possible only of parts of one tome  pad were reused. Even "weak" one time pad represents huge obstacle for the description of the text. And  is compression is used there is no way to use known plaintext attack. 

From the photo of a captured Soviet one-time-pad it looks like they used five digits random numbers. In this case the value of a letter 1-26 is very small (less then 1%) in comparison with random number and does not change the "spectrum" of the stream.

As sum of a large number of non-random sequences is "almost" random, open texts can be used for generation "pseudo random one-time-pad". That includes pages of newspaper like NYT, pages or chapters of books and dictionaries, stock quotes and even Amazon reviews.  In this case the key is the algorithm of generation of one-time-pad based on the seed (date of creation of the message can be a seed). If the seed is user-defined, that converts one-time-pad into regular cryptosystem and it is unclear whether this method has advantages over more traditional approaches like DEC. See Stream Ciphers. But seed can be chosen randomly and never communicated. In this case decryption became more difficult ( stochastic decryption), but also protection of the data is higher.

The major problem with one-time-pad is the necessity of its covert distribution. In a way, one-time-pad is a very long (equal to the length of plainttext) secret key.  Ideas of Steganography can be used for this purpose.  For example one can construct "pseudo-random" one-time-pad from the image or a text of a regular article in NYT or WashPost. This has an advantage that an open text like NYT or certain edition of collected works of Jack London, Tolstoy or other prolific writer available from Gutenberg project  (total volume is important here) can be used as a one time pad.

For a text, the simplest way would be to create a matrix of length N and 5 rows out of chunks of the text of appropriate length and generate one digit from each character in each row. So vertically each column of five rows produced one five digit pseudorandom number.  Several letters and punctuation signs can represent each digit (in mapping of, say, 121 symbols used (lower case letter and upper case letters are different symbols) to 10 digits. In this case  12 different symbols represent the same digit and can be grouped in such a way as total frequency of the groups in the given language would be the approximately the same. That can help to make the quality of the sequence higher.  Lines selected might not be consecutive, for example you can chose 1,10,20,30,40 and 50 lines and then 3,13,23,33,43 and 53 lines and so on using step 2.  You can also use 10 lines for generating one 5 digit number instead of ten. In this case each two lines produce a single digit.  There can be more complex variants, when mapping changes dynamically.

You can view one-time-pad as an abstract machine with the program that transforms text into crypto text and back using a database of numbers longer then the number of characters in the text. In case of one time pad the program used is very simple (addition or XOR). It is applied to each symbol of the text  using the database (one-time pad is such a database) to transform plain text to cyphertext and back. .

More complex functions are possible.  For example, index of a letter in a "known" text (which serves as pseudo one-time pad) can be used instead of addition for encoding. After the letter is encoded, the text in the "pseudo one-time pad" before this letter is considered "consumed". In this case a large plain text serves directly the role of one time pad.

To make decryption much more difficult, the text of the message  can be encrypted before applying onetime pad. Standard (even weak is OK) crypto algorithm can be used (for example regular DES).  That completely defeat any statistical methods based of frequency letters in texts of particular language and several other approaches to decryption. I think combination DES+one-time-pad is a serious challenge even for three letter agencies.

Article in Wikipedia (aka CIAapedia ;-) is written in such a way as to definitely to discourage the use of one-time-pad ;-)

In cryptography, the one-time pad (OTP) is a type of encryption which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key (or pad) of the same length as the plaintext, resulting in a ciphertext. If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key.[1][2] It has also been proven that any cipher with the perfect secrecy property must use keys with effectively the same requirements as OTP keys.[3] However, practical problems have prevented one-time pads from being widely used.

First described by Frank Miller in 1882,[4][5] the one-time pad was re-invented in 1917 and patented a couple of years later. It is derived from the Vernam cipher, named after Gilbert Vernam, one of its inventors. Vernam's system was a cipher that combined a message with a key read from a punched tape. In its original form, Vernam's system was vulnerable because the key tape was a loop, which was reused whenever the loop made a full cycle. One-time use came a little later when Joseph Mauborgne recognized that if the key tape were totally random, cryptanalysis would be impossible.[6]

The "pad" part of the name comes from early implementations where the key material was distributed as a pad of paper, so the top sheet could be easily torn off and destroyed after use. For easy concealment, the pad was sometimes reduced to such a small size that a powerful magnifying glass was required to use it. Photos show captured KGB pads that fit in the palm of one's hand,[7] or in a walnut shell.[8] To increase security, one-time pads were sometimes printed onto sheets of highly flammable nitrocellulose.

There is some ambiguity to the term because some authors use the terms "Vernam cipher" and "one-time pad" synonymously, while others refer to any additive stream cipher as a "Vernam cipher", including those based on a cryptographically secure pseudorandom number generator (CSPRNG).[9]

Exploits

While one-time pads provide perfect secrecy if generated and used properly, small mistakes can lead to successful cryptanalysis:

• In 1944–1945, the U.S. Army's Signals Intelligence Service was able to solve a one-time pad system used by the German Foreign Office for its high-level traffic, codenamed GEE (Erskine, 2001). GEE was insecure because the pads were not completely random — the machine used to generate the pads produced predictable output.
• In 1945, the US discovered that Canberra-Moscow messages were being encrypted first using a code-book and then using a one-time pad. However the one-time pad used was the same one used by Moscow for Washington, DC-Moscow messages. Combined with the fact that some of the Canberra-Moscow messages included known British government documents, this allowed some of the encrypted messages to be broken.
• One-time pads were employed by Soviet espionage agencies for covert communications with agents and agent controllers. Analysis has shown that these pads were generated by typists using actual typewriters. This method is of course not "truly" random, as it makes certain convenient key sequences more likely than others, yet it proved to be generally effective. Without copies of the key pad used, only some defect in the generation method or reuse of keys offered much hope of cryptanalysis. Beginning in the late 1940s, US and UK intelligence agencies were able to break some of the Soviet one-time pad traffic to Moscow during WWII as a result of errors made in generating and distributing the key material. One suggestion is that Moscow Centre personnel were somewhat rushed by the presence of German troops just outside Moscow in late 1941 and early 1942, and they produced more than one copy of the same key material during that period. This decades-long effort was finally codenamed VENONA (BRIDE had been an earlier name); it produced a considerable amount of information, including more than a little about some of the Soviet atom spies. Even so, only a small percentage of the intercepted messages were either fully or partially decrypted (a few thousand out of several hundred thousand).^[24]

NEWS CONTENTS

• 190513 : One-Time-Pad (Vernams Cipher) Frequently Asked Questions ( Can I reuse my pad? )

Old News ;-)

One-Time-Pad (Vernam's Cipher) Frequently Asked Questions

I think this FAQ are too superficial to be relied upon.

"A one-time pad isn't a cryptosystem: it's a state of mind." - Marcus Ranum

A Russian One-time pad, captured by MI5 (click to enlarge)

Contents:

1. What is a one-time-pad?
2. Are one-time pads really unbreakable?
3. Can I reuse my pad?
4. Can I use a CDROM of music or a book?
5. Can I use the output of DES as a one-time pad?
6. Can I distribute my pads using another cryptosystem like PGP?
7. What are good sources of randomness?

What is a one-time pad?

A one-time pad is a cryptosystem invented by Vernam[1]. It's a very simple system and is unbreakable if used correctly. To use a one-time pad, you need 2 copies of the "pad" which is a block of random data equal in length to the message you wish to encode. The word "random" is used in its most literal possible sense here. If the data on the pad is not TRULY RANDOM, the security of the pad is reduced, potentially to near zero.

One-time pads are used in pairs. The more copies of a given pad, the greater the likelihood is that one may be captured, in which case the system is completely broken. One copy of the pad is kept by each user, and pads must be exchanged via a secure channel [e.g.: face to face]. The pad is used by XORing every bit of the pad with every bit of the original message. Once the message is encoded with the pad, the pad is destroyed and the encoded message is sent. On the recipient's side, the encoded message is XORed with the duplicate copy of the pad and the plaintext message is generated.

Think of a one-time pad as a 100% noise source which is used to mask the message. Since both parties of the communication have copies of the noise source they are the only people who can filter it out.

Are one-time pads really unbreakable?

Yes. But only if used properly. A one-time pad must be truly random data and must be kept secure in order to be unbreakable.

Consider if the one-time pad is used to encode the word "otter." If an attacker tries to brute force "guess" the contents of the pad, the message will "decrypt" into every possible combination of 6 characters (e.g.: "lemur." "badger" etc..) Since the pad is truly random there are no statistical methods that the attacker can hope to use to infer which combination is correct.

Can I reuse my pad?

Never, without reducing the security of the pad to something less than 100%, usually close to 0%. As long as the pads are unique and never reused there is nothing that can be used to attack the encryption using statistical analysis or pattern matching.

Wright[2] recounts a situation in which Soviet intelligence re-used one-time pads years after they had originally been distributed to field agents in Britain. The British noticed a pattern in some coded messages and began searching for "hits" through a complete archive of all encrypted communications intercepts. Over a period of years, various secret communications slowly were compromised.

This operation took place under the legendary code word VENONA which was a closely held secret until recently. NSA has recently declassified parts of the story and put information about VENONA on the Web

Can I use a CDROM of music or a book?

No. CDROMs have lots of structure in them and are not random. The approach may work but it's not 100% secure like a real one-time pad. Books, for example, also have a lot of structure in them and are not random (otherwise, you would find them dull reading indeed).

Another problem with CDROMs is that the address of a bit on the CD is too small. If you take the (# of CD's published ever) times the (# of starting positions on one disk, in bits) you get a number small enough to exhaustively test.

Can I use the output of DES as a one-time pad?

No. If you do, it's not a one-time pad, it's DES and is only as strong as DES. This technique is popular in many cryptosystems and is called a "stream cipher." Fundamentally it is only as strong as whatever you used to generate the stream of pseudo-random data.

Can I distribute my pads using another cryptosystem like PGP?

If you do, it's only as secure as whatever you used to transmit the pad. When dealing with one-time pads your security is only as good as your weakest link, which is almost always something other than the pad.

What are good sources of randomness?

Feeding cosmic background radiation through one-way functions (such as MD5) is one approach. Remember that the one-way function is used, in such a case, to adjust the statistical properties of the data, not as super-encryption - so a lower-quality one-way function such as DES or MD5 is acceptable, even though they might not be good enough to use for encryption in their own right, anymore. Using radioactive decay is another option! The randomness of radioactive decay is an open question depending on whose cosmology you believe, which is another reason that feeding samples of background radiation through another permutation generator such as a one-way hash is a good idea. See Internet RFC 1750 for more information on generating random numbers.

Quality random numbers are a very important problem in cryptography. Not only must the number have the properties of a random number, it must be unpredictable. For example, the output of random() might appear to be statistically random, but is absolutely predictable if you know the seed that went into it. Many beginning one-time-padders think that using the output of random() will give them something useable as a one-time-pad. In fact, it's only as strong as the seed that was used, which is often getpid() or time(). These are basic beginner flaws, but unfortunately, even commercial products containing cryptography have been known to contain such elementary weaknesses. (e.g., NetScape).

Recommended Links

Softpanorama Recommended

Top articles

Sites

• A Cryptographic Compendium
• One-time-pad
• David Kahn, "The codebreakers"
• Peter Wright, "Spy Catcher"
• Internet RFC 1750 (generating random numbers)

Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes :  Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce :  Bernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS :  Programming Languages History : PL/1 : Simula 67 : C : History of GCC development :  Scripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month :  How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March, 12, 2019