New Information on the Inventor of the One-Time Pad

Seems that the one-time pad was not first invented by Vernam:

He could plainly see that the document described a technique called the one-time pad fully 35 years before its supposed invention during World War I by Gilbert Vernam, an AT&T engineer, and Joseph Mauborgne, later chief of the Army Signal Corps.

[…]

The 1882 monograph that Dr. Bellovin stumbled across in the Library of Congress was “Telegraphic Code to Insure Privacy and Secrecy in the Transmission of Telegrams,” by Frank Miller, a successful banker in Sacramento who later became a trustee of Stanford University. In Miller’s preface, the key points jumped off the page:

“A banker in the West should prepare a list of irregular numbers to be called ‘shift numbers,'” he wrote. “The difference between such numbers must not be regular. When a shift-number has been applied, or used, it must be erased from the list and not be used again.”

It seems that Vernam was not aware of Miller’s work, and independently invented the one-time pad.

Another article. And the paper.

Tags: cryptography, encryption, history of cryptography, one-time pads

Posted on August 3, 2011 at 12:57 PM • 22 Comments

Comments

Steven M. Bellovin • August 3, 2011 1:58 PM

The link to the paper is to the tech report version, which is somewhat older than the published one. That version is available at http://www.tandfonline.com/doi/abs/10.1080/01611194.2011.583711 for free for the next few weeks.

Nick P • August 3, 2011 2:02 PM

Not to mention “Vernam” cipher sounds so much more geeky than “Miller” cipher. I’d expect that name on a beer, not a cryptographic algorithm. 😉

Dean • August 3, 2011 2:22 PM

This is why I always cringe at people who say things like “If it wasn’t for so-and-so, we wouldn’t have (or know about) such-and-such.”

If Einstein hadn’t come up with General and Special Relativity, someone else would have, eventually. If Salk didn’t discover and develop a Polio vaccine, someone else would have, eventually. This fact does not diminish the accomplishment, but we humans are a bright species. We aren’t simply a horde of dumb apes that have benefited from a handful of geniuses.

/end grouch

RH • August 3, 2011 2:28 PM

I know it is a little off topic, but it jumped out at me that telegraphs were $5. Can you imagine our modern communication network at those rates?

What’s the rate today? thousandths of a cent? Perhaps millionths or less?

Richard Steven Hack • August 3, 2011 2:31 PM

Dean: “We aren’t simply a horde of dumb apes that have benefited from a handful of geniuses.”

Actually, that doesn’t follow. What your argument actually suggests is that humans are a bunch of dumb apes that would have benefited from some OTHER genius if the first one hadn’t done something.

And this case proves we don’t even know the first one. Which tends to argue for the conclusion that humans are dumb apes… 🙂

The fact that more than one genius exists in a given field says nothing about the rest. It should be obvious that the majority in that field did not discover something as momentous.

Not to mention that the phrase “genius” probably doesn’t apply in most cases of technological advance, nor does the word have much specificity as to the exact brain function required to qualify.

JJ • August 3, 2011 2:42 PM

As I recall from “The Codebreakers”, Vernam came up with a streaming cipher which used a repeating key and it was Mauborgne who recommended that the key not repeat. The way it was described made it sound (to me) like Mauborgne had learned this information rather than come up with it himself. Bellovin’s discovery of a possible indirect link between Miller and Mauborgne seems to support this.

I’ve never understood why anyone calls a one-time pad a Vernam cipher since the idea was given to Vernam by Mauborgne. Shouldn’t we give credit where credit is due? As previously suggested, I guess that means we should now call it a Miller cipher (though I’m still not convinced that it’s a true cipher since no algorithm is involved other than the trivial XOR operation).

Nick P • August 3, 2011 3:20 PM

@ JJ

“I’ve never understood why anyone calls a one-time pad a Vernam cipher since the idea was given to Vernam by Mauborgne. Shouldn’t we give credit where credit is due?”

I agree. Although, I prefer to just call it a one-time pad because of issues in tracing credit. I prefer that approach for technologies in general. The reason is much like Dean said: someone would have invented it eventually. It’s the idea that matters, not the originator. (An exception would be people who are originators of tons of radically novel technologies, like Tesla. They deserve some mention. )

Dr. I. Needtob Athe • August 3, 2011 5:18 PM

It’s my belief that the U.S. Navy uses one-time pads to communicate with their ships at sea. My conclusion isn’t based upon any special knowledge of Navy operations, it’s based on the facts that (1) one-time pads can be mathematically proven to be unbreakable as long they’re done right (a fact that’s also intuitively obvious), and (2) the method perfectly fits Navy operations, where every time a ship is in port it can have a fresh pad securely delivered from headquarters, and the pad can easily be large enough to cover all communications while the ship is at sea.

It seems to me that since there’s no conceivable communication method that could be more secure, that’s what they must be using.

Comments?

NZ • August 3, 2011 6:17 PM

I believe that more often that anything named after a person was not invented by that person 🙂

Somewhat offtopic: Knuth mentions that hash functions were invented in 1950s. However, bilingual dictionaries for Eastern languages (like Japanese-English) seem to use this concept (key+number of strokes is the hash of a character, then you have to look through a list). So, were hash function actually invented before 1950s?

Kevin • August 3, 2011 6:29 PM

It looks like TSA is trying something that you have recommended for years:
http://gcn.com/articles/2011/08/02/tsa-behavior-detection-techniques-boston-logan-airport.aspx

Nick P • August 3, 2011 6:37 PM

@ Dr. I. Needtob Anthe

Not quite. Most classified data is sent over Type 1 communication devices with classified symmetric ciphers, protocols, and physical protection mechanisms. Most sensitive but unclassified data is sent over Type 3 communication devices, which use algorithms like AES. Google Type 1 communication devices and tell me how many One-Time-Pad systems you see currently marketed. Virtually none. One-time pads are still used in limited situations but most encrypted traffic uses symmetric algorithms like AES or Saville.

I’ve linked an example below. It’s a radio system marketed for groups like the Navy by Harris, an established contractor for Type 1 equipment. The Navy uses this technology in practice. Harris notes that it is “Type 1 encryption capable.” This implies (1) the traffic is sent in plaintext by default & (2) the common encryption scheme is Type 1 algorithms, far from one time pads.

Harris – Secure Mil. Networks, Databases & Comm.’s
http://www.naval-technology.com/contractors/navigation/harris-secure/

Most NSA encryption devices today use standardized cryptographic protocols in concert with the NSA’s Electronic Key Management System (EKMS). Individual keys are generated by NSA & accounted for with unique identifiers. They are loaded into Type 1 equipment using key fill devices & I think there’s an online protocol, but I can’t recall for sure. NSA has moved far from one-time pads because well-engineered protocols/algorithms on protected hardware usually resist attack very well. Like Bruce often says, the crypto is usually the strongest link on the chain. It’s the other stuff that usually causes security failures.

EscapedWestOfTheBigMuddy • August 3, 2011 6:46 PM

It seems the bankers had something valuable to protect (i.e. money), and an existing secure distribution system for pieces of paper (often the hardest part of a OTP scheme).

The preconditions were in place, so this only required one really good idea.

Nice

Andy • August 3, 2011 10:04 PM

@Dr. I. Needtob Athe, “It seems to me that since there’s no conceivable communication method that could be more secure, that’s what they must be using.
Comments”

Just a theory, but it might not matter what type of algo is used. Any thing that makes a even spacing(hash/enc normal only one or two repeat characters per block) to plaintext(flunctles about a point). As long as the encrypted data to a guess of plaintext fails into a range, using any means, there will be a high chance that it is the right plaintext.

Trichinosis USA • August 3, 2011 10:56 PM

They’re just cap codes for My Coke Rewards, guys. Really. ;-7

Paeniteo • August 4, 2011 3:27 AM

@JJ: “As I recall from “The Codebreakers”, Vernam came up with a streaming cipher which used a repeating key.”

What about Vigenere, some 300 years earlier?
Or, actually, it looks like Vigenere also just borrowed the idea from even earlier concepts (but Vigenere seems to have had better marketing).

Winter • August 4, 2011 4:53 AM

@NZ
“I believe that more often that anything named after a person was not invented by that person :)”

This is called:

Stigler’s law of eponymy

https://secure.wikimedia.org/wikipedia/en/wiki/Stigler%27s_law_of_eponymy

Actually, anything named after the real inventor is purely an accident.

MarkH • August 4, 2011 6:31 AM

About US Navy key distribution — the only data I have about this is from reading a paper (linked from Bruce’s blog), on how the Soviet Union was able to get so much military intelligence, from the Walker family’s treason.

In fact, key distribution is especially difficult for the USN (or at least, was during that era), considering the distribution of naval bases and ports of call around the world, and the lengths of time some ships may spend continuously asea.

And for practical reasons, the scheduling of key updates was governed by the slowest parts of the system. In consequence, the US Navy was renewing the keys for their crypto equipment at much longer intervals than recommended by the NSA — and when Soviet intelligence obtained keys from the Walkers, those keys were useful for a long time.

Clive Robinson • August 4, 2011 11:07 AM

First of you need to differentiate between “somebodies system” and “somebodies method”.

History has many examples of “Fred Smiths System” using “John doe’s method” after time because the system is widely used it gets associated with “Fred Smith” and “John Doe” gets forgoton about.

Another thing people get muddled up is the difference between “discovering” something and “inventing” something.

Sir Issac Newton “discovered gravity” but he “invented the cat flap” as well as “inventing milled edges on coins” to prevent “shaving of the kings gold”. Usually a discovery requires vigourous proof, and an inventions worth is self evident, sometimes so much so that ordinary people say “I could have told you that”.

@ Dr I Needab Athe,

The one time pad (OTP) for all it’s simplicity is actually extrodinarily difficult to use in practice due to the many failing of all stream ciphers, pluss it’s own as well.

However it does serve a purpose even today in the various armed forces and covert worlds. One use was for “emergency key distrubution”. Untill relativly recently encryption equipment was quite “thirsty” and required considerable power. Often once powered up the key would be loaded from a “fill gun” which for various reasons would be taken away. An alternative method on much of the UK’s BID equipment was an “optical paper tape reader” and the key loaded via a 4-6 inch length of punched paper tape that was supposadly due to chemicals it had been soaked in was actually a fire hazzard which likewise would be kept away from the crypto cell.

Thus it was possible for the power to go down in the crypto cell and have neither a fill gun or the important bits of blue paper tape to re-key the equipment. It was also possible for a Diplomatic or other “behind the lines” unit/mission to run out of key material.

For such occurrences there would be a OTP sitting in the safe, so that emergancy messages could be communicated securly as well as emergency keying material (usually the crypto cell would have the equivalent of a TTY device with punch tape attachment as standard so making a new fill tape not an issue).

However the rules of “signal indicators” for routing and autherisation/authenication and the equivalent of a MAC where harder to do than actually encrypting the message, and often checked by two other people…

JimFive • August 4, 2011 12:20 PM

@Dr I
Many others, more informed than I, have answered your query re:Naval communications. But there is are other aspects to consider.
1) If a message is lost then the sender and recipient pads get out of sync.

2) For OTP to be useful there must be a separate pad for each communication partner. So for Ship A to talk to Ship B there would need to a pad they can use. Pads cannot be used for a different partner because a) they would get out of sync and b) using a OTP twice makes it trivial to break.

Thus a OTP for an emergency communique from ship to hq and back would make sense, but not for normal communications.

JimFive

NZ • August 4, 2011 3:00 PM

@Winter
Thank you! Now I know who discovered it 🙂

Me • August 5, 2011 10:28 AM

Color me impressed that at one time banks cared about infosec.

Nick P • August 5, 2011 11:34 AM

@ all

I think the best OTP discussion yet is still when Bruce put AlphaCipher in the doghouse & the moderator busted the owner out when he posted as two different people on same PC. It was all hilarious. His posts all lame.

Doghouse: Vadium Technology
http://www.schneier.com/blog/archives/2004/11/the_doghouse_va_1.html

I’m surprised I haven’t seen another good Doghouse post in about a year or two. Come on Bruce, you had to run into at least one company that truly deserves it in past year or two.

Schneier on Security