One-Time Pad reinvented to make electronic copying impossible(technologyreview.com) |
One-Time Pad reinvented to make electronic copying impossible(technologyreview.com) |
What this method does is makes it harder to attack if the Bob's key/OTP is physically stolen. ALthough keys embedded on secure chip-cards cheaply and commonly available now are just as secure - the authors apparently claim that the keys can be read off the glass blocks in less than 24 hours; and extracting a long key off a chip-card (even if it's just pin-protected with permanent blocking for x mistakes) would be a bigger pain, you have to physicially scan the chip with extremely expensive gear for that.
What this method doesn't do, is "make electronic copying impossible" or facilitate DRM, since Bob or anyone who compromises Bob's computers can freely copy and distribute the data right after the decryption.
It is a great way to make the key hard to copy, which is how encryption is usually circumvented in practice.
Sometimes I read articles where Alice sends a signal to Charlie or something like that, and for me that is a huge red flag that indicates the author may not have payed much attention in school and/or may not have a great grasp on what they are talking about.
Fortunately this article is about Alice and Bob, so I am inclined to take it seriously.
The physical object as I understand it provides a source of random data, with the property that it is fast to do a single lookup (shine an arbitrary light pattern on it), but slow to copy the whole data.
This means that an attacker who steals the object, but doesn't know which lookups will be done, won't be able to copy all the data.
Now my objection is that the only lookups that the person who steals the object will not be able to do, is the ones based on random patterns that have not been published, i.e. the ones that are generated next time Alice and Bob meet.
But from that point of view, it would be no less safe if Alice and Bob simply generated a one time pad and stored it when they met.
First, Alice and Bob decide on a pattern P. Then they each compute a key K(A) and K(B) using the pattern P by shining P through their slab. Then, they publicly publish P and K(A) ⊕ K(B). (Apologies for the lack of good mathematical notation, but HN is not a great medium for such.)
Because P, K(A), and K(B) are all random, the attacker learns no useful information from these two published items.
Now, for Alice to encrypt a message m, she computes K(A) ⊕ m and sends it to Bob. Once Bob gets it, he uses the public pattern P to recreate K(B). Then he uses the publicly published K(A) ⊕ K(B) to compute:
K(B) ⊕ [K(A) ⊕ K(B)] ⊕ (K(A) ⊕ m)
which is in fact m. At any time, the Eve can only know P (useless since she doesn't have either slab) and K(A) ⊕ K(B), which is not enough to recover the key or message.
Also this article doesn't touch on whether the randomness generated is sufficiently random for cryptographic purposes. With enough error correction and an improper random distribution, it can become possible to break even OTP.
The paper also mentions that the randomness they are using passes the Diehard and NIST randomness tests, so it appears they are pretty random. Apparently, though, they have to sacrifice some of the bits in order to ensure that! It references "Supplements" E and F, saying they include more details, but they're not included in the arXiv paper. Of course, the original random patterns used to generate the keys are randomly selected too, so let's hope they're using a good random source for that...
I suspect it's not even very good randomness. Long dark / bright lines from deeper scratches at either end, skewed randomness due to the atomic structure of glass (though glass is probably a reasonably good natural source, since it's not crystalline), that sort of thing happens when you're dealing with physical (hard, static) structures. And this thing has to be very reproducible or you can't decrypt your message, so we're not talking extracting randomness from a warm cup of tea.
The big weakness with OTPs is inadvertent key reuse, not someone stealing the key wholesale.
Even with quantum computing, conventional OTPs are fine, provided keys aren't reused (or lost). OTOH there are plenty of other more efficient symmetric and asymmetric systems which are still fine under quantum computing, too. (it's really not much of an issue for conventional symmetric cryptography; yes, most common public key systems in use today fall to quantum cryptography, but their are known/viable systems which would be fine)
How is this qualitatively different than a plain old symmetric encryption. Bob and Alice (or whatever and for whatever reason renamed characters in their example) each have the key, Alice encrypts ( ⊕ ) sends to Bob, he decrypts.
Is it the idea that the key cannot be digitally copied and instead it is two pieces of glass? How is it different than Alice and Bob using a one-time key for each transmission then destroying it (using secure wipe)? What if they use hand written papers to keep their keys and burn the pages when done.
I am probably being dense missing some deeper idea. Anyone care to explain?
If you use an electronic one-time key and then secure wipe, you're not protected from someone who unbeknownst to you already read the contents of your hard drive.
If you use handwritten papers then you cannot store large amounts of data, nor is your data transmission rate anything feasible.
This allows an uncopyable object the size of a grain of sand to hold about a terabit of private shared data, and to process that at the speed that we can send/receive/react to light. (Considering that the basic technology is also used to send signals down fiber-optics cables, speed should be pretty good.)
Hmmm... so is paper?
I'm still curious how this glass is produced. It seems to me that you would be introducing many more potential intrusion points by using physical encryptors since many more parties (people, databases, and systems) will be aware of the details in order to produce the appropriate slab. Having said that, the same thing would apply for any other physical encryptor that would have to be manufactured.
To start off, both Alice and Bob must have their own slabs of diffusing glass and must physically meet to create a key for encoding a message later.
Like any other OTP system, key distribution — ensuring that the parties who wish to communicate securely have a shared secret (or secrets in the case of OTP; the whole point of OTP is that a key is only used once) — is the weak point. Unlike many other OTP systems, this one requires a physical meeting, which, depending on your use-case for needing crypto in the first place, may be impossible, or deadly dangerous.
At best, this complicates key compromise.
EDIT: clarifying language.
If Alice and Bob must have a secure method to jointly compute K(A) ⊕ K(B), then why wouldn't then use that same method to just exchange the data?
So here is my issue:
Eve knows P, so she can steal the object and hence compute K(B).
The difficulty in "copying" the object is only significant when Eve does not know P.
But that same difficulty would apply if K(A) and K(B) were random numbers that Alice and Bob generated when they met.
Or is the point that Alice and Bob generate K(A) + K(B) for a lot of values of P, and then randomly select the ones to use when sending a message? That doesn't seem to be what the authors intended, although it would now be secure against stealing the object for a short amount of time.
The actual paper does describe generating n different patterns and then randomly selecting one of them to encrypt the message, but the index of the one that is randomly selected is sent with the encrypted message so that Bob can use it to look up the appropriate pattern. I took this as just generating more than one key for convenience's sake.
Notably, a requirement for security of the slab is that given temporary access, Eve "must not be able to efficiently copy or model its contents." So, I think the point is that since there are many different P's (and hence K(A)'s and K(B)'s), Eve cannot recreate K(B) for all P's in a reasonable amount of time. Further, she can't actually make a physical copy of the device. Still, it seems that if Eve can steal the device, she can break old messages --- which I guess is, as you said, a property shared by regular OTPs. When she steals the device, though, she can only decrypt so many messages before detection, since there is apparently a key recovery rate of 1.5 seconds per key.
But one of the other requirements set forth in the paper is that if the slab is stolen, Eve must not be able to send or receive messages. I'm not sure how that is fulfilled here.
If a "full" message involved both sides randomly picking a P, then this could still be satisfied.
But it doesn't seem to live up to my hopes for security: all it really guarantees is that the probability of Eve decrypting an intercepted message (assuming she steals the slab for time t and knows all the P's) is t/T where T is the time Bob and Alice spend generating K(B) + K(A) for different P's.
It appears I was correct about the stolen CPUF leading to decryption of previous messages; in supplement G, at the bottom of (2), the authors state:
"Finally, it is worth noting that with a stolen device and access to the public dictionary, an attacker Eve may be able to quickly decrypt any of Alice and Bob’s previous communication that she may have saved(since Alice and Bob publically share which SLM patterns they use each round). For this reason, it is highly beneficial for Alice and Bob to utilize a second layer of encryption to ensure that any eavesdropper cannot determine these previously shared patterns, as discussed next."
They also discuss other security properties of the scheme in supplements G and H, which are both excellent.
[1]: http://arxiv.org/src/1305.3886v1/anc/CPUF_Supplementary_Mate...