back to article Crypto shocker: 'Perfect cipher' dates back to telegraphs

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 …

COMMENTS

This topic is closed for new posts.
  1. Old Handle

    Interesting

    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.

  2. John Smith 19 Gold badge
    Boffin

    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.

    1. Anonymous Coward
      Anonymous Coward

      Do they?

      Do people publish lists of random numbers? Do people buy them?

      Why?

      Is it harder than writing novels?

      1. Displacement Activity

        @Thad

        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.

        1. Anonymous Coward
          Boffin

          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.

          1. Anonymous Coward
            Devil

            Why use a published list of random numbers for encryption?

            Because that's the *last* place "they" would think of looking?

        2. Anonymous Coward
          Anonymous Coward

          Thanks

          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.

  3. Admiral Grace Hopper
    Facepalm

    Patents

    Does this also push back the first instance of a technology patent found to have been granted despite the existence of prior art?

    1. Anonymous Coward
      Anonymous Coward

      I think not

      Archaeologists discovered a Roman ink pot that would have infringed a 20th-century patent had it been made 2000 years later.

  4. frank ly

    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.

    1. Anonymous Coward
      Anonymous Coward

      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.

    2. Tom 13

      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.

      1. Tom 13

        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.

    3. Anonymous Coward
      Thumb Up

      rot13

      I think you just described it.

  5. Destroy All Monsters Silver badge
    Big Brother

    You could patent this?

    Sounds like a "method" patent. I thought these kind of patents had come only in the Clinton 90s?

  6. PyLETS
    Boffin

    limited usefulness

    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.

  7. Anonymous Coward
    Anonymous Coward

    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!

    1. FreeTard

      caesar cypher?

      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

      http://en.wikipedia.org/wiki/Classical_cipher

    2. Michael Dunn
      Coat

      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.

  8. Jerry
    Boffin

    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

    1. Old Handle
      Boffin

      Dice

      No, not perfect, but as long as you test the dice for any obvious bias, it should do fine.

  9. Winkypop Silver badge
    Coat

    I had a pad once

    But then I got married and moved into a house.

  10. mark fernandes
    Linux

    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.

    1. Annihilator
      IT Angle

      Uh huh?

      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.

      1. Old Handle
        Boffin

        Huh indeed

        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.

        1. Displacement Activity

          @Old Handle

          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.

  11. Bog witch
    Trollface

    Article text

    <mode="pedantic">

    I think the article text should read 'provably unbreakable' rather than 'theoretically unbreakable'

    </mode>

    1. sellnosoup
      Headmaster

      @Bog witch

      ...not to be PEDANTIC or anything, but I believe your tagset it not well-formed!

      <mode type="pedantic">

      ~blablabla~

      </mode>

      There, FTFY!

  12. Buzzword

    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.

    1. Mark Wilson

      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.

    2. GrumpyOldBloke

      Additionally...

      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.

    3. A J Stiles
      Facepalm

      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.

  13. Paul Powell
    Boffin

    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

    etc etc.

    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.

    1. A J Stiles
      Thumb Up

      Bravo

      Nicely explained.

    2. Jason 41
      Thumb Up

      Thank you!

      I understand now

    3. Anonymous Coward
      Headmaster

      Except...

      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.

      1. J.G.Harston Silver badge
        Thumb Up

        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.

      2. Martin Taylor 1
        Happy

        No such thing as a random number?

        http://en.wikipedia.org/wiki/ERNIE#ERNIE

        Works for me.

        1. Anonymous Coward
          Anonymous Coward

          @ERNIE

          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."

          http://en.wikipedia.org/wiki/Pseudorandom_number_generator

          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."

          http://en.wikipedia.org/wiki/Hardware_random_number_generator

          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.

          1. Displacement Activity

            @AC

            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.

          2. Liam Johnson

            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.

      3. Michael Dunn
        Happy

        Except again

        Hey, never heard of "shot diodes" or even radioactive decay?

    4. Old Handle

      Good Explanation

      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.

      1. Displacement Activity

        Key length

        >> 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.

  14. Dave Bell

    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.

  15. Anonymous Coward
    Anonymous Coward

    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!

  16. stubert
    Paris Hilton

    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?

    1. Stoneshop
      Boffin

      @stubert

      - 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)

    2. Peter Mc Aulay

      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.

  17. Yet Another Anonymous coward Silver badge

    @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

  18. bill 36
    Happy

    you should know

    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.

    1. Stoneshop

      Not only in Austria

      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

  19. stubert
    Happy

    @Stoneshop

    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.

  20. NomNomNom

    So

    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.

    1. Daniel B.
      Boffin

      Public-key cryptography?

      That's what Public-key crypto solves. Send the key, encrypted in such a way that only the intended recipient can decrypt it.

      1. NomNomNom

        flawed

        public key cryptography is flawed as it relies on keeping a private key safe. It's impossible to keep anything safe unless you destroy it first

  21. Anonymous Coward
    Thumb Up

    So what we learned is Patents even back then were based on prior art

    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.

  22. bep

    Codes and 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.

This topic is closed for new posts.

Other stories you might like