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.
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 …
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.
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.
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.
"... 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.
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.
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.
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.
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.
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
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.
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.
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.
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.
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 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.
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.
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.
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.
>>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.
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.
>> 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.
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.
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!
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)
that here in Austria, online banking with the RaiffeisenBank is always done with one time pads.
We sign for them every time we need a new pad and any login to the bank can only be done using them once each login.
Plus we need the standard username, password, account details first of course.
Standard practice and works without problems.
Its probably why, most sales or buying/selling transactions are carried out using only IBAN and account numbers. Paypal not required which is goodness in itself.
and I think that what they're using are not pads in the encryption sense, but TANs, Transaction Authorisation Numbers. A sort of single-use password.
The Dutch Postbank/ING Bank uses them too. Alternatively, you can have them send you a TAN by SMS the moment you want to finalise your transactions, which is not all that secure, but probably enough so given the limited time such a TAN is valid
Thanks, that cleared it up for me! So to make this practical and totally secure the key is the protocol whereby you send the key to the recipient, if you can do that securely in a way that guarantees the pad has not been modified or duplicated in transit, then the one time pad (given as someone stated that the entropy is large enough) is inpenetrable and can allow the sending time-critical messages securely over insecure channels.
This is just another form of security through obscurity. Instead of sending a plaintext message you are just obscuring it with a key and now instead of needing the hide the message you have to hide the key. So in a way the key now becomes the message. This is why all key based encryption systems are bunk. You still have something that needs protecting and delivering and because it's no longer the message people get lulled into a false sense of security.
As for unbreakable - any plaintext message is unbreakable if you destroy it afterwards so that there's nothing to break. The strongest form of security is not to send messages in the first place. I always say if you need to communicate with other people you are doing something wrong.
So what we learned is Patents even back then were based on prior art; Does this not further highlight the flaws in the patent process that even over 100 years later still need addressing.
I wonder, but coud the phrase 9 out of 10 patent owners found there cats had already invented it - ever be coined. Probably best not, as that is probably copyrighted somewere.
But with the volume of patents dumped for approval every day increasing, sadly some even more obvious still get thru, despite the calls of IT forums naming prior art. This only puts the costs of patent application up and further stifeles the young solo inventors from making there mark only for there invention to get reinvented later and patented by some larger company who can afford lawyers and we all know after a few years in courts were that can end up for the little people.
Lovely find and great research in spotting this - a beutiful example of how most patents have already been done previously. There again I wonder if the UK govemental spies pay anything to RSA given they had that system already albeit labeled secret uk stuff.
An important point to remember about the use of codes is that the first principle is that "The enemy knows the code". Encoding a message delays the enemy knowing its contents until its too late for them to make use of the information, but never assume that the enemy will never break your code. Encoding a message shouldn't encourage you to include far more information than you prudently should. The advantage of the one time pad, if i understand it correctly, is that even if it was somehow broken or guessed the enemy only gets the contents of that particular message. This is rarely worth the effort involved.
In the 1950s Russian spies were given one time pads made of, IIRC, cellulose; if MI5 came knocking a quick stub of a lit cigarette and viola, no more pad.
Biting the hand that feeds IT © 1998–2021