Forgot your password?
typodupeerror
Encryption Communications Privacy

One-Time Pad From Caltech Offers Uncrackable Cryptography 192

Posted by timothy
from the unless-you-crack-the-glass dept.
zrbyte writes "One-time pads are the holy grail of cryptography — they are impossible to crack, even in principle. However, the ability to copy electronic code makes one-time pads vulnerable to hackers. Now engineers at the California Institute of Technology in Pasadena, have found a way around this to create a system of cryptography that is invulnerable to electronic attack. Their solution is based on a special kind of one-time pad that generates a random key through the complexity of its physical structure, namely shining a light through a diffusive glass plate."
This discussion has been archived. No new comments can be posted.

One-Time Pad From Caltech Offers Uncrackable Cryptography

Comments Filter:
  • Impossible? (Score:3, Insightful)

    by Sockatume (732728) on Thursday May 23, 2013 @08:48AM (#43801825)

    Couldn't you just steal the plate?

    • Re:Impossible? (Score:5, Informative)

      by barlevg (2111272) on Thursday May 23, 2013 @08:49AM (#43801831)
      That's generally the only way to crack a true one-time pad: steal the pad.
      • by Sockatume (732728)

        Yeah, that's supposed to be what this problem solves, though, if I'm reading it right. Haven't they just taken a step back to having a physical OTP on your desk/in your shoe?

        • Re:Impossible? (Score:5, Informative)

          by barlevg (2111272) on Thursday May 23, 2013 @08:54AM (#43801865)
          Right: it sounds like it's TWO MATCHED OTPs (or, rather, one-time slabs), so Eve would need both Alice's slab AND Bob's slab to crack the communication. And if Alice and Bob are both in physical possession of the slabs, then Eve is better off using $5 cryptography [xkcd.com] to get at the message. The issue, of course, is that one-time pads aren't exactly practical, because, by definition, they're one-use-and-then-destroy. If you use an OTP more than once, it becomes vulnerable to cracking.
          • Re:Impossible? (Score:5, Informative)

            by L4t3r4lu5 (1216702) on Thursday May 23, 2013 @08:57AM (#43801887)

            Eve is better off using $5 cryptography to get at the message.

            Rubber Hose Cryptanalysis [wikipedia.org] Just FYI.

          • Re:Impossible? (Score:5, Informative)

            by slim (1652) <`ten.puntrah' `ta' `nhoj'> on Thursday May 23, 2013 @09:59AM (#43802421) Homepage

            No, the two devices don't match. Each device contains a different several GB of random numbers (or I suppose, random transformations), encapsulated in the structure of the glass.

            The two owners meet, and using both their devices, produce a "combined key". The combined key can be stored in a public repository. The shared OTP can be extracted from the combined key using either device.

            The two parties exchange confidential data encrypted with bytes from the OTP until the OTP is all consumed. Then they must meet up again to create a new OTP.

            There's nothing novel about the cryptography. What might be novel is the physical properties of the device used to allow someone to carry their personal list of random numbers around.

            • You could accomplish the same thing by having Alice's pad contain half of the full OTP, only the odd numbers, and Eve having only the even numbers.

              Even better, use a third person with a third OTP to determine if the next sequence goes to Alice or Eve (i.e. Bob's pad is a string of numbers; if the number is odd, the next digit comes from Alice's pad, if even, Eve's pad.)

              • by slim (1652)

                I don't think we share a vocabulary on this topic. None of that made sense.

    • Re:Impossible? (Score:5, Informative)

      by Hans Adler (2446464) on Thursday May 23, 2013 @08:56AM (#43801871)

      Who would have thought that the f... article addresses this devilishly ingenious workaround?

      "And even if Eve steals the glass, they estimate that it would take her at least 24 hours to extract any relevant information about its structure.

      This extraction can only be done by passing light through the glass at a rate that is limited by the amount of heat this creates (since any heating changes the microstructure of the material). And the time this takes should give the owners enough time to realise what has happened and take the necessary mitigating actions."

      • by Sockatume (732728)

        Right, it's difficult, not impossible. You need a sufficiently large time window to steal both pads and duplicate them.

        • by bugnuts (94678)

          Just one of them is sufficient.

          At least it's not the size of a manuscript anymore, so you don't need a guy with a handcuffed briefcase on one hand and a SMG on the other.

          • by Sockatume (732728)

            If I'm reading it right (which is a shaky assumption) one pad is sufficient to decipher messages sent to that recipient, but both would be necessary to read messages going both ways.

            • by slim (1652)

              It's an implementation detail as to whether you use a different pad in each direction, though I don't really know why you would do.

              The principle is well understood -- if you both know a secret list of numbers that's as long as your plaintext, you can exchange messages confidentially.

              The challenge, which these guys claim to address, is how to get to the point where you both have the secret list of numbers, and can be confident that nobody else has it.

              Once you have that confidence, I don't see why you wouldn'

      • by mbone (558574)

        Who would have thought that the f... article addresses this devilishly ingenious workaround?

        "And even if Eve steals the glass, they estimate that it would take her at least 24 hours to extract any relevant information about its structure.

        This extraction can only be done by passing light through the glass at a rate that is limited by the amount of heat this creates (since any heating changes the microstructure of the material). And the time this takes should give the owners enough time to realise what has happened and take the necessary mitigating actions."

        Right. Note that this implies that this technique should only be used for messages that have an effective lifetime of 1 day.

        "Attack at dawn" - yes

        "Attack on Sunday" - not so much

      • And it seems to me that things like the wavelength of light used would have to be matched exactly as well.

        Light of different wavelengths refract differently. Blue refracts more than red, for instance.

        The two communicating parties could agree on one (or several) exact wavelengths to use with their plates. Anyone who intercepts the plate, without knowing what wavelength was used, wouldn't be able to replicate the process used to generate the key, unless they tried them all, I guess - but even then they wouldn

    • by rherbert (565206) <slashdot.orgNO@SPAMryan.xar.us> on Thursday May 23, 2013 @09:01AM (#43801941) Homepage
      What if you drop the glass plate? You're sure to crack it then.
    • by Sockatume (732728)

      I suppose my error here is letting the title's "uncrackable cryptography" override the summary's "invulnerable to electronic attack", which is absolutely true.

  • Moon Runes (Score:5, Funny)

    by codemaster2b (901536) on Thursday May 23, 2013 @08:50AM (#43801847)

    So, the message can only be read by the light of a moon the same shape and season that the message was written on?

  • by Anonymous Coward on Thursday May 23, 2013 @08:56AM (#43801879)

    Uncrackable glass plates? Forget cryptography, you should get into the windshield business!

  • SGI had something along these lines http://www.google.com/patents?vid=5732138 [google.com] https://en.wikipedia.org/wiki/Lavarand [wikipedia.org] but links http://lavarand.sgi.com/ [sgi.com] don't work too well now.
  • Got it backwards (Score:5, Insightful)

    by Monty845 (739787) on Thursday May 23, 2013 @09:01AM (#43801939)
    A one time pad is impossible to crack in theory, but may be crackable if the method for generating the pad is flawed. Creating true randomness is a tricky proposition, and I don't see why its safe to believe that "shining a light through a diffusive glass plate" will generate true randomness.
    • Re: (Score:3, Informative)

      by Anonymous Coward

      On a photon-by-photon basis, refraction, diffraction, and anything less than total reflection are all quantum mechanical processes. It doesn't get more random than that. Sending photons through a partially transparent mirror has been a standard trick for generating random bits quantum mechanically for at least a decade that I know of. It sounds like this is the same principle.

      • by ledow (319597)

        But to be a useful one-time pad, don't you have to be able to repeat the results to decode the message?

        • by Corbets (169101)

          But to be a useful one-time pad, don't you have to be able to repeat the results to decode the message?

          No. You have to distribute matched pads - one to the encoder, one to the decoder.

          Thus, if someone gets his or her hands on a copy of the pad, decryption is trivial.

          • by ledow (319597)

            So at what point aren't "matched pads" repeats of the original pads, or devices which would repeat the results of the original pad?

            This is my point - these pads aren't "random", because if they were they'd perform differently in two different devices. In which case, their results are surely trivially capturable and, thus, reproducible if you digitally capture the performance of a single example?

            It's the old "if you can read it, so can anyone else with the same equipment, and so can you 'fake' it with suffi

            • by slim (1652)

              On some device when the two glass owners meet:

              pad = generateRandomBytes(many GB)
              combinedKey = encodeToCombinedKey(pad, glass1, glass2)
              publishToInternet(combinedKey) // shared key i

              Later, to send a message:

              chunkOfPad = decryptSharedKey("http://repository/combinedKeyId", glassAlice)
              cipherText = xor(plaintext,chunkOfPad)

              To decode:

              chunkOfPad = decryptSharedKey("http://repository/combinedKeyId", glassBob)
              plaintext = xor(ciphertext,chunkOfPad)

              There may be some novelty in the way the combinedKey is constructed (pr

              • You don't actually need to encrypt the shared key; a simple XOR of the pads from each piece of glass will do:

                combinedKey = xor(glassAlice, glassBob)
                publishToInternet("http://repository/combinedKeyId", combinedKey)

                For Alice to send a message:

                combinedKey = getFromInternet("http://repository/combinedKeyId")
                glassBob = xor(combinedKey, glassAlice)
                cipherText = xor(plaintext, glassBob)

                For Bob to decode:

                plaintext = xor(ciphertext, glassBob)

                The result of the XOR only tells you whether a given bit is the same o

            • The pads are randomly generated, not random. Each pad needs to be longer than your message. No part of the pad is ever reused; if you have the first half of a pad, you can decrypt anything encrypted with that half, but it tells you absolutely nothing about the second half of the pad, because it's all random, not an algorithm. If you have the cleartext, you could not reverse-engineer the pad from it, and even if you could, you couldn't use that to determine the rest of the pad.

              Here's how it works.

              You gene

        • by jittles (1613415)

          But to be a useful one-time pad, don't you have to be able to repeat the results to decode the message?

          No. With a proper random pad generation algorithm, you could never ever reproduce the exact same pad in two places, or at two separate times. You generate the pad once and use some other method (such as couriers) to deliver the pads to the people that need them. You also need a way to guarantee that the courier did not tamper with, sell, or copy the original pad. If you transmit via internet, you would use some previously arranged cryptographic exchange.

      • by slim (1652)

        I don't think this is about quantum phenomena. The glass has a randomised construction, but it needs to be a repeatable source of randomisation.

        The process seems to be: Both parties meet, and feed some random data into a process which uses both their glasses and produces a few GB of "combined key". Alice's glass and Bob's glass are different. But either can be used to extract the OTP from the "shared key".

    • This remind me of an old Office file where the MS copyright text was encrypted thanks to a simple XOR value (a few bytes). (There is also that funny story at the time of a Linux tool that only needed the `-d` option to decipher a whole XLS, without providing any password...). Anyway, what was said at the time: while XOR encryption seems very week, if the key itself is as long as the text to be encrypted, and if the key is based on reliable random values (and the key is kept secret), it is indeed a very stro
    • This work seems to be based on this high-profile paper from 2002:
      Ravikanth Pappu, Ben Recht, Jason Taylor, Neil Gershenfeld Physical One-Way Functions [sciencemag.org] Science 2002, 297 (5589), 2026-2030, doi: 10.1126/science.1074376 [doi.org]

      Abstract: Modern cryptographic practice rests on the use of one-way functions, which are easy to evaluate but difficult to invert. Unfortunately, commonly used one-way functions are either based on unproven conjectures or have known vulnerabilities. We show that instead of relying on number th

    • I can't remember which book it was, maybe Cryptonomicon, but more likely The Ultra Secret, but it had some interesting stories about both the allies and axis having a hard time at this.

      They used various ideas to try and "make" randomness into their one time pads. However all of these things had to be done by a person, as this was more less before the advent of computers (well just before anyway). One such method had to do with using a deck of cards. However crackers were able to even find patterns among the

      • Re:Random is hard. (Score:5, Interesting)

        by thoromyr (673646) on Thursday May 23, 2013 @10:18AM (#43802615)

        I have heard of some that try to utilize some sort of seemingly random event that is naturally occurring. However even these can be modeled over time.

        A good post, but I'm not sure you understand hardware based random number generation. At least one way to do it is have a small amount of radiactive material. Although it decays predictably in the long term (half life) it is random in the short term. By measuring the radioactive decay truly random numbers can be obtained.

        Can you model this? Sure, but your model will either be a software based random number generator or it will be a hardware token. In either case it will *not* be the item in question at the time in question and will not allow you to determine what numbers were generated.

        No system is foolproof, but all the interesting cracks in cryptography that I'm aware of come through side channels or demonstration that a method was not truly random. Human card shuffling is certainly not random -- not only is the process controlled by the shuffler, but there are distinct non-random patterns to it that allow stage magicians to take a stack decked that is shuffled and still produce the desired result.

        I think my favorite side channel attack was picking up the attenuated signal from the unencrypted side of a cryptograpy machine -- the British didn't have to crack the encryption used by the French embassy, they just read the plain text!

        OTP are sexy and cool because they provide unbreakable encryption. As long as they are generated correctly (truly random) and distributed without tampering or exposure. The first is hard enough, but distribution on any scale means that not all of them will be free of tampering and exposure.

        • by DarthVain (724186)

          I guess I was more referring to software not hardware random generation. Like when you call a random function to generate a number for you to use.

          I remember reading about two methods YEARS ago probably in some CS class or something. One involved weather patterns (i think), and another involved electrical current, and both involved slices of time, to produce values that were "seemingly" random. The point was, in both cases, you could over time figure out and model something to get most of the general weather

        • by mbone (558574)

          I have heard of some that try to utilize some sort of seemingly random event that is naturally occurring. However even these can be modeled over time.

          A good post, but I'm not sure you understand hardware based random number generation. At least one way to do it is have a small amount of radiactive material. Although it decays predictably in the long term (half life) it is random in the short term. By measuring the radioactive decay truly random numbers can be obtained.

          The decay may be random, but the implementation may not be. I have heard of two issues with actual radioactive random number generators.

          1.) The geiger tube (or solid state chip) used for detecting the decays will have imperfections (for example, a dead time so that it will miss a decay occurring too soon after another one), and these can introduce non-randomness into the output.

          2.) The early ones were simple accumulators (count for an interval delta-T, and if you get > Y decays, that is a 1, otherwise a

    • by Solandri (704621)
      Something like this was already tried 10 (15?) years ago. It was a bunch of crystals embedded into a plastic base. You shone a light onto it and depending on the angle, the pattern of crystal faces which reflected back would change. The inventors were marketing it as a replacement for the magnetic stripe on your credit card. The magnetic stripe on your card can easily be scanned and duplicated. The crystals were easy to scan, but near impossible to duplicate if you're comparing the reflection from mult
  • Is it new? (Score:4, Interesting)

    by 140Mandak262Jamuna (970587) on Thursday May 23, 2013 @09:09AM (#43801985) Journal
    I thought there was a similar technique used in WWII for communication between Churchill and FDR. Identical pairs of phonograph records were kept on both sides. Both sides would play a pair simultaneously, or as nearly as they could. Then technicians would use electronic delay and tune it so that they both are synchronized. Then add voice communication to the recorded sounds and transmit. On the receiving side they subtract the phonograph record sound and get the voice alone back. Each pair of phonograph records would be a one time pad. The encryption and decryption was analog, not digital. But apart from that, adding a "noise" as encryption and subtracting identical noise for decryption would be very similar to what the article is describing.

    Was it really used? Or am I hazily recalling some spy novel stuff from Irwin Wallace or Alistair MacLean and mistaking it for real history?

    • by barlevg (2111272)
      Looks like it was called POTUS-PRIME [cromwell-intl.com], but I haven't yet found any more information than what's on that page.
      • POTUS-PRIME

        Great, now I have to imagine Roosevelt with Peter Cullen's voice saying, "Allied Forces, roll out."

    • It was real [wikipedia.org], my memory has not been addled. Not yet.
    • by mbone (558574)

      That is indeed how the WWII "scrambler" phones worked, but that was not viewed as nearly as secure as a one time pad (required for all messages dealing with Enigma decrypts) and the Germans did decode at least some scrambler phone communications.

      The cryptographic trouble is that the inherent correlations of the human voice are still present, just overlaid by noise, and you can use that knowledge to extract the signal (the voice) from the noise. It did prevent idle eavesdropping, which I think was more th

      • Yes, plain scrambler was insecure. I just read the wiki about the project. They did a lot more than simply adding noise. They did some pulse code modulation, frequency shifting etc.
    • by slim (1652)

      There's nothing new about one-time pads, and your story is plausible (I think I've heard it before).

      OTPs have definitely been used in real spycraft. People were literally issued with a book of random numbers, to be very closely guarded.

      What's new here is the way of storing OTPs so that they can't unobtrusively be copied.

      • In what way guarding a block of glass different from guarding a telephone book? Easiest one time pads are to get two copies of the same yellow pages. The caller specifies a page number. The receiver turns to that page. Ignore all alphabets and collect all the phone numbers write them down in sequence. You got a one time pad.
        • by slim (1652)

          In what way guarding a block of glass different from guarding a telephone book?

          You can trivially borrow a telephone book, copy what you need, then return it without the owner noticing.

          TFA:

          And even if Eve steals the glass, they estimate that it would take her at least 24 hours to extract any relevant information about its structure.

          This extraction can only be done by passing light through the glass at a rate that is limited by the amount of heat this creates (since any heating changes the microstructure of the material). And the time this takes should give the owners enough time to realise what has happened and take the necessary mitigating actions.

          ... and their abstract...

          Benefits of volumetric physical storage over electronic memory include the inability to probe, duplicate or selectively reset any random bits without fundamentally altering the entire key space

          Easiest one time pads are to get two copies of the same yellow pages. The caller specifies a page number. The receiver turns to that page. Ignore all alphabets and collect all the phone numbers write them down in sequence. You got a one time pad.

          "Easiest", but not unbreakably secure in the manner of a truly random OTP.

        • by thoromyr (673646)

          easy does not mean secure. First hint, your phone numbers do not represent a random distribution of numbers. Better than nothing? Sure. Would it prevent me from cracking the encrypted message? Yes, but I'm not a cryptographer. The lack of any meaningful randomness would permit analysis and cracking.

        • Re:Is it new? (Score:4, Informative)

          by JaredOfEuropa (526365) on Thursday May 23, 2013 @10:22AM (#43802657) Journal
          Those numbers aren't truly random and cryptanalysis can be applied to them. Especially if the attacker knows you're using the Yellow Pages (security through obscurity).
    • What an interceptor would get was a very noisy conversation, which could be recorded and carefully listened to by multiple people multiple times. It wasn't very secure because people are very good at getting meaning out of noisy conversations. IIRC, the conversation wasn't really pleasant for FDR or Churchill, so adding too much noise would become impractical.

  • by bradgoodman (964302) on Thursday May 23, 2013 @09:27AM (#43802123) Homepage
    One time pads are uncrackable only if the pad is truly random and perfectly secretive. Everyone has known this for years. All they have done here was to create a new way to generate random numbers. Any new way of generating random numbers would/could be equally applied to OTP crypto.
  • The question is: how soon this diffusive glass will become a forbidden substance ?

  • Random physical structures have been used for this purpose for decades.

  • by gweihir (88907) on Thursday May 23, 2013 @10:13AM (#43802559)

    A secure one-time pad with classical means is easy to do. You just need to secure the system where the pad is applied adequately. You need to do the same thing with this hype-device. Hence it has zero advantages over other implementations of the one-time pad, but a lot of drawbacks.

    I would suggest that these people are not stupid and know of the severe drawbacks. I would also suggest they are just completely unethical lying scum and grant or investment money is the only thing counts for them.

  • All top secret information should flow through one time pad systems.

    Look at it this way. What does disk space cost these days? Imagine getting a 30 gigabyte one time pad file on its own little SSD drive. How much data could be passed back and forth as theoretically unbreakable encryption? At the very least 30 gigabytes of data. In practice, probably at least a magnitude beyond that.

    • by mbone (558574)

      All top secret information should flow through one time pad systems.

      Look at it this way. What does disk space cost these days? Imagine getting a 30 gigabyte one time pad file on its own little SSD drive. How much data could be passed back and forth as theoretically unbreakable encryption? At the very least 30 gigabytes of data. In practice, probably at least a magnitude beyond that.

      No, at most 30 gigabytes. The next byte you send will start to reveal previous traffic.

      • Theoretically. It depends on how secure the traffic has to be... you could run some of the high volume lower security traffic through a portion of the key that is "stretched" a bit.

        But the top top security data... yeah. 1:1 ratio with the key.

      • by slim (1652)

        I am not a cryptographer, but I *think* it would not harm the strength of the encryption if you compress then encrypt.

        You could also use the OTP as a source of symmetric keys for AES, moving to a new one regularly, as SSL does.

        • by mbone (558574)

          I am not a cryptographer, but I *think* it would not harm the strength of the encryption if you compress then encrypt.

          In theory, it should actually make it stronger, by removing redundancy. In practice, I bet it would mean that you could then predict the first few bytes of each message sent (i.e., some sort header info, followed maybe by something guessable if you know the language being used) and it can be a bad idea to begin each message with something predictable.

          • by slim (1652)

            I am not a cryptographer, but I *think* it would not harm the strength of the encryption if you compress then encrypt.

            In theory, it should actually make it stronger, by removing redundancy. ...
              it can be a bad idea to begin each message with something predictable.

            Both completely irrelevant if you're encrypting with a OTP.

  • by mbone (558574) on Thursday May 23, 2013 @10:42AM (#43802869)

    Three things are required for a one time pad - that the key be shared, random and non-repeated. A one time pad is very much breakable if the key is not both random and non-repeated, and the biggest problem with its use can be the sharing of the keys.

      The Soviet "Verona" traffic was decoded because they reused pads (keys), rendering the message decryption straightforward, and also revealing the keys. The revealed keys were found to have some further weaknesses, as they were made manually (apparently by secretaries told to type randomly on their typewriters). These weaknesses included an avoidance of repeated characters, a tendency to alternate hands (a character on the left side of the keyboard would be likely to be followed by one on the right), and (IIRC) a preference for character pairs and triplets that didn't require too much stretching of the hands. (On the top line of a QWERTY keyboard, this means that, say, an initial "q" would be unlikely to be followed by another "q", that it would be likely to be followed by a letter in the "u - p" range, and that the third character would be more likely to be a q, w or e than an r, t or y.)

    Now, officially, that amount of manual non-randomness wasn't enough to break further Soviet one time pad encryptions, but I suspect that they were. I have also heard rumors that later use of random keys generated by electronic circuits had problems as the physical limitations of the electronic circuitry imposed a low-pass filtering that made these keys, again, not totally random. Note that true randomness is what is needed here - common digital pseudorandom techniques, such hashing with SHA-1, may help to obscure weaknesses, but they will not make a non-random key random.

    In this case, I would worry very much about

    - whether the physical technique produces a truly random key and
    - how to satisfy myself that today's random key is totally independent of every previous key. If this is, say, dependent on where the laser is pointing to in the glass, how far apart does each pointing need to be to make sure that the results are independent, and can I securely verify that today's direction is sufficiently different from every previous time and
    - as the technique is passing an initial sequence of bits through the randomizer glass, how random does the initial sequence need to be ? What weaknesses are imposed by non-randomness in that initial sequence.

    I could easily see this technique being secure in theory but massively broken in practice by some weakness in how the glass is made or handled or in the initial keys.

    Note, by the way, that the two parties must physically get together to generate the key, so in a sense this is really a secure key storage device. Once they use up their stored keys, they have to meet again to be able to send more messages, which of course is the real problem with one time keys (and why, for example, the Soviets reused some of the Verona keys).

    And, finally, this technique might make a cool way of doing truly secure hashing.

  • When you get loaded.

  • I always thought a high quality recording from a windy outdoors location with no man-made sound sources would make a fine source of random values.

  • http://www.imdb.com/title/tt0070948/synopsis?ref_=tt_stry_pl [imdb.com]

    Infinite data being stored in a single crystal; all depending on how the light refracts.

Some people carve careers, others chisel them.

Working...