A computer scientist has unearthed evidence that a theoretically unbreakable form of cryptography was in use by telegraph operators as early as 1882, 35 years before its supposed invention by a duo from Bell Labs and the US Army. The one-time pad, which is also known as the perfect cipher, uses a random key that is shared by …
But I wouldn't call it a shocker. It is after all a very simple system. The only hard part is understanding why it's necessary. It seems quite likely it was invented many times by people who never fully realized the significance.
It's such a simple idea it's likely to have been re-invented *repeatedly"
Whenever someone had to communicate with someone else a long way off.
However as secret communications are secret the method would likely have died off with the users or preserved within the group (in secret).
It's a conjecture, but a plausible one. I'm not sure when people started publishing tables of random numbers but I'd expect when that happened someone started thinking about using them.
Do people publish lists of random numbers? Do people buy them?
Is it harder than writing novels?
Sure they do (did). My old school 'SMP Advanced Tables' (which I've still got, from about ~75) has a page of random numbers. I can't remember what we used them for, but we did.
More relevantly, I can't believe that anyone could patent one-time table crypto (except in the US), because it's so bleedin' obvious.
a page of random numbers
The reason you had a page of random numbers is so that your output could be checked against a known result. If you had used your own truly random numbers your teacher would have to replicate your working to check your result. When all the pupils use the same pseudo random numbers they all get the same answers. Which makes marking easy.
Would you use a known published list of random numbers for encryption? probably not. Both ends of the telegraph need to have the same list, but if a 3rd party has it too then it fails.
I never saw such a thing, probably because I got thrown out of the maths class after the first two weeks of what-was-then the "O" level class. I was a hopeless case.
Why use a published list of random numbers for encryption?
Because that's the *last* place "they" would think of looking?
Does this also push back the first instance of a technology patent found to have been granted despite the existence of prior art?
I think not
Archaeologists discovered a Roman ink pot that would have infringed a 20th-century patent had it been made 2000 years later.
The past is difficult to see.
"... When a shift-number has been applied, or used, it must be erased from the list and not be used again."
That sounds like an obvious procedure to ensure security by removing a key from the pool so it is not used again. I'd say that the author of that instruction fully understood that it was a security measure that made the encryption 'perfect'.
So why does David Kahn say, “Miller probably invented the one-time pad, but without knowing why it was perfectly secure or even that it was,”
It may be that Miller didn't actually 'invent' it but made sure it was formally known by incorporating the method into the telegrapher's codebook.
Miller may not have known or understood the various and many mathematical theories and techniques that apply to crypotgraphy, but the 'perfection' of the one time pad should seem obvious to any intelligent person. (Or am I applying my own hindsight here?).
In use, I would assume that a shift number was applied to one letter of the message then be discarded, then the next letter of the message had the next shift number applied. If one shift number was applied to an entire message, it would be easy to crack the encrypted telegram since there are only about 30 possible shifts for old-style telegrams.
can't be arsed with titles
It does seem intuitively obvious that it would be unbreakable because for any possible message there is a possible key.
It's the proving part that is hard.
And intuitively obvious things aren't necessarily true. For a long time people thought it was intuitively obvious that there could only be 1 parallel line passing through a given point not on the first line. As for the pad concept, it is certainly known in that time. There's a famous lost treasure that used a copy of the US Constitution for its pad. The encoder wrote down a number which indicated how far to count to find the next letter for the message. I doubt it counts as perfect, but it intuitively seems very, very hard to break if you don't know the key and the method.
I think you just described it.
And actually, now that I think about it, it may count as even better than perfect.
Because there were three different messages using the key. Only the first and second have been decoded. They indicated what they had and that the exact location for where they were hiding the stash was. The third one has never been decoded, hence an article in a C64 programming mag for something that would help you work with the document.
You could patent this?
Sounds like a "method" patent. I thought these kind of patents had come only in the Clinton 90s?
The one time pad is only useful if a secure alternative channel of communication is available to send the key. The British Diplomatic service used this up to the seventies based on punched paper tape one-time pads which were sent by diplomatic bag taken by couriers to embassies abroad, which enabled a secure transmission channel back to the Foreign Office in London. I saw one of the machines used in the computing museum at Bletchley Park a couple of years ago. It shredded the pad immediately after being used as an integral part of the machine, which guarantees the pad tape is used no more than once. The advantage was that for this purpose, a secure alternative communication channel was available but time limited, and the secured communication could occur electronically at any time in the opposite direction to the key transmission.
It would very much surprise me...
...If at least one of the ancient cultures (Roman, Greek, Egyptian, Chinese etc) did not use this form of encryption at some point, which would be a lot more than 35 years prior to the patent!
I doubt that the anclents used anything more than shift cyphers.
There's the well known Caesar cypher, I don't know of others from ancient times though.
wikipaedo tells me
Prior art in ancient cultures
IIRC this was Julius Caesar's means of communication. Pity he didn't envisage the benefits of patenting it.
Incidentally it would have been difficult to implement in Chinese, since they don't have an alphabet; I don't see shifting characters around on a sheet of paper (yes they did invent that) containing the whole Kiang Ssu 500,000 character dictionary as a trivial task.
Pinyin handbook in the pocket.
How to generate a truly random one-time-pad?
If the one-time-pad is not truly random then attacks can be made against it. Back in the 1880s that would probably have been difficult, especially with any mechanical generation of the pad.
Second issue is generic. You need to keep both copies secret and you need to be able to deliver them securely to the recipient. Failure to do this has resulted in many breaks of one-time pad systems
No, not perfect, but as long as you test the dice for any obvious bias, it should do fine.
I had a pad once
But then I got married and moved into a house.
Greek previous art
Remember this from school history classes...
Spartan Cipher Rod (Message Stick; Okytala)
A simple solution to insure the security and privacy of messages.
A strip of paper or cloth was wrapped in a spiral around a round wooden rod. Message was written on the paper and then unwrapped and dispatched to the intended receiver.
If unwrapped paper was viewed, the message was incomprehensible but when re-wrapped
around a wooden rod of the same diameter the message became clear.
Unless they discarded the rod each time and reintroduced a new (randomly assigned thickness) rod, that's not a perfect encryption as the article discusses. I knew it as a scytale though, not an okytala.
That's not even *close* to perfect. The real secret to OTP, is that they key contains as much information as the message. Therefore "OIDNUSVUAMNXODES" can equally easily mean "ATTACKATMIDNIGHT" or "RETURNTOFORTRESS" depending on what key is used. This makes for some interesting counter intelligence strategies (slip someone a fake key that changes your message completely), but more importantly, it makes it absolutely impossible to guess the original message based on the encrypted message alone, since a given ciphertext could mean literally anything. The other two features, random key and no reuse, serve important but (IMHO) secondary roles in preventing someone from working backwards to the key.
True. Did you see the Reg story a couple of days ago about the Zodiac killer messages? Some guy essentially made up his own key to turn the message into what he wanted it to say. Most of the comments seemed to completely miss this point.
I think the article text should read 'provably unbreakable' rather than 'theoretically unbreakable'
...not to be PEDANTIC or anything, but I believe your tagset it not well-formed!
It's only secure up to a point
A one-time pad isn't inherently secure. If your cipher is ROT-x (e.g. ROT-13), and your one-time pad just contains a random list of numbers between 1 and 25, then it would be trivial to apply natural language analysis to the data. For example words such as "the" or "a" will appear more frequently in the text; the letter "e" will be the most common; and so on.
Not so simple
That is why you also encrypt spaces making it impossible to see where words start and end. As each shift is only used for one character it is still of no benefit to find the odd short word as they would carry no real meaning for the remainder of the message.
And that point is "all the way".
The idea of the one-time pad is that you change the cipher for *each* *letter* of the original message as you go, so every "e" in the plaintext can potentially be encrypted as a *different* letter in the ciphertext.
Putting spaces between words is just a schoolboy error -- either your contact at the far end will be able to work out where the spaces should be, if they have decrypted the message correctly, or you encrypt spaces.
The problems of a banker in the West being able to generate truly random number sequences and communicate these by stage coach net or next generation steam train net to a banker in the East without anyone having a quick peak would suggest that this was not a perfect solution. Human nature would also suggest that shift sequences would be reused over time. Rather than being perfect, the shiftybank algorithm and key sharing mechanism was probably adequate for the time.
OK - this is how a one time pad works
The one time pad IS inherently and provably unbreakable (properly implemented of course). There is obviously some confusion about this:
A one time pad is pre-shared encryption key that is used for only one message and then discarded. The key is of at least equivalent length to the message. Each letter in the message is shifted by the amount suggested by the corresponding part of the key. The key must be properly randomly generated.
Frequency analysis will not work as every instance of each letter is shifted by a random amount. Because the key length >= the message length there is no repetition of the shifts to attack. In the same way the discarding of the key after one use prevents analysis over several messages.
You could try every key combination - but that would just yield every possible message of equivalent length with no way to distinguish the right message - i.e. for a 17 letter message you would have all of the following decrypts:
WE ATTACK AT DAWN
WE ATTACK AT DUSK
STEVE LOVES KATIE
DINNER IS IN OVEN
To put it in context:
A simple shift cipher (ROT 13) is attacked by trying all the values to shift by
A Caesar cipher can be defeated by frequency analysis
The Spartan cipher rod is a transposition cipher and can be broken by putting the code into various tables
Polyalphabetic ciphers (using a different cipher alphabet for every nth character) are vulnerable to frequency analysis - but each alphabet needs to be broken individually.
Machines like Enigma change the cipher alphabet for every character, but do so in a pre-determined way given a particular set of initial settings.
A one time pad uses a different cipher alphabet for every character but does so in a 100% random way.
I understand now
that there is no such thing as a random number. Unless you want to exploit our current lack of understanding of quantum mechanics as a source for random numbers. All "random" numbers are generated by a deterministic process, hence they're properly called psuedo-random numbers. If the process used to generate the pseudo-random numbers becomes known, then any continued use of the generated numbers would render the resulting encryption no better than plaintext.
Also, if you actually did have a truly random set of numbers, then they would need to be transferred from one party to the other rendering it possible to steal them during that transfer.
The first limitation has been exploited in the past. The second probably as well.
there is no such thing as a random number
An impact detector immersed in a stong Brownian motion generator, say a nice hot cup of tea.
No such thing as a random number?
Works for me.
That is still a pseudo-random number generator, it is merely based on physical processes instead of purely mathematical ones. The formula being used to generate the random numbers is still based on the underlying deterministic physical principles. The fact that we currently lack the computational power to determine and compute that function directly only makes it a pseudo-random number generator that is suitable for generating cryptographically secure random numbers.
Since you like the low quality writing of Wikipedia, here's a quote from the page on PRNGs:
"[S]equences that are closer to truly random can be generated using hardware random number generators."
Note the word "closer" in that statement.
Or there's Wikipedia's qualification of the randomness of hardware RNGs:
"Random number generators can also be built from "random" macroscopic processes, using devices such as coin flipping, dice, roulette wheels and lottery machines. The presence of unpredictability in these phenomena can be justified by the theory of unstable dynamical systems and chaos theory. Even though macroscopic processes are deterministic under Newtonian mechanics, the output of a well-designed device like a roulette wheel cannot be predicted in practice, because it depends so sensitively on the micro-details of the initial conditions of each use."
While Wikipedia does not mention it, a physicist would consider anything atom sized or larger to be considered to be in the "large object" category (if not moving at close to the speed of light) and thus well defined by classical mechanics and fully deterministic. Quantum based RNGs MAY be truly random, but that depends on whether quantum mechanics is based in true randomness or if we merely do not understand the driving principles.
tl;dr: ERNIE works, but ERNIE is not truly random.
Hey, never heard of "shot diodes" or even radioactive decay?
Paul Powell left out one detail, though perhaps it's easy enough to figure out. If you use the same key twice, it is once again possible to determine key by trial and error, since chances are only the real key will make BOTH messages intelligible.
And whether quantum effects are "truly random", is a question best left to philosophers I think. It doesn't matter for this. Even with some currently unknown theory of quantum mechanics that does away with the randomness, trying to reconstruct a the state of their hot tea, quark-by-quark, in order narrow down possible keys would be... unfeasible, to put it mildly.
There are all sorts of truly random processes you can observe and measure. Electron tunnelling, thermal noise, radioactive decay, yada yada. I thought ERNIE was based on Neutron decay or some such, but I can't be bothered to look it up. Physicists certainly don't consider "atom sized or larger" to be "large". Large, in the sense in which you're using it, equates to how localised an object's wave function is. You've got to be way above atom-sized to use classical mechanics. And any object with mass moving at "close" to the speed of light is "very" large.
>> If you use the same key twice, it is once again possible to determine key by trial and
>> error, since chances are only the real key will make BOTH messages intelligible.
Depends on how long the key is; you've only got an issue if the parts of the key used overlap. In practice, you wouldn't use a "shift" either (@PP: why would you shift anyway?); there's no point making it easy for the attacker.
Lot of people here hung up on "perfect" randomness. Not relevant for practical OTP use.
ERNIE is not truly random?
>>merely based on physical processes
But surely the various noise signals used are random physical processes, so unless there is some fault in the construction, this randomness should apply to the output too.
>>a physicist would consider anything atom sized or larger to be considered to be in the "large object"...and thus well defined by classical mechanics
But the noise is basically from electrons, which are small.
What about Western Union?
I have a vague recollection of a description of how Western Union made money transfers by telegraph.
I'm pretty sure that they had some sort of one-time key, but it may have been intended as a signature method.
Ah, here it is. From "The Victorian Internet", p.119: "A running count was kept for each book, and each time a money transfer telegram was sent, the next word in its unique numerical order was sent as one of the words of the message. Another page in the codebook gave code words for different amounts in dollars."
That was devised in 1872, so the one-time element was certainly around. But it's not a full encryption process.
Re: OK - this is how a one time pad works (10:05)
Paul Powell said:
> The key must be properly randomly generated.
In addition it must contain adequate entropy. A perfectly random sequence of 0's and 1's would be adequate for perfectly encrypting a sequence of coin flips, but not most messages (if applied in a simplistic manner). The cypher text "IEMLO MVN" (coded with shifts of 0's and 1's) is quite easy to decode because there is insufficient entropy in the key to 'hide' the original message!
The thing I never got...
I understand the randomness of the encryption means that it is an entirely secure method of encrypting your message PROVIDED you have pre-shared the one time pad. How do you deliver the key/pad securely, if you can transmit the encryption pad 100% securely why not also use the same method to deliver the message? The message cannot be brute forced and attempts to decrypt without the pad would be futile, but it shifts the attack vector onto the key sharing mechanism surely? Or is this just a problem outside of the scope of this solution? You need a secure channel to be able to share information securely over an insecure channel?
- You (the sender) generate a bunch of one-time pads
- They're physically sent to the receiver via some secure method. This will surely require a certain amount of time, which makes this path unsuitable for time-critical messages.
- The receiver acknowledges the intact, untampered receipt of the pads.
- Now you have the possibility to send time-critical messages over an insecure but fast channel (telegraph, telephone, radio)
Re: The thing I never got...
Exactly, and also don't underestimate the bandwidth of a courier + bag full of codebooks compared to a telegraph. A single secure delivery can set up a remote station with crypto keys for months or more.
@The thing I never got.
Time. You can share the set of one time pads once a year by stage coach, or by meeting in person, then send urgent messages encrypted by them at any time over the telegraph
- Bugger the jetpack, where's my 21st-century Psion?
- Something for the Weekend, Sir? Why can’t I walk past Maplin without buying stuff I don’t need?
- Review 'Mommy got me an UltraVibe Pleasure 2000 for Xmas!' South Park: Stick of Truth
- The land of Milk and Sammy: Free music app touted by Samsung
- Privacy warriors lob sueball at Facebook buyout of WhatsApp