Comment by ReidZB | Hacker News Reader

Comment by ReidZB | Hacker News Reader

Parent Full thread

The original paper [1] is much clearer about the actual algorithm. The below is pretty much pulled straight from it, although I simplify it slightly (by assuming one pattern, etc.)

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.

[1]: http://arxiv.org/abs/1305.3886

Thanks, that's what I thought but I'm glad you confirmed it and put it in their notation.

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.

Interesting point. I'm not sure what prevents Eve from simply computing K(B) from P if she has stolen Bob's slab. Maybe I have misinterpreted something?

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.

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

When I woke up this morning (and was in a better state of mind), I realized the supplements may have been on the arXiv page but not included in the paper. I was correct. Here [1] is the supplement paper, which I find more useful than the actual paper itself.

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

Reply on news.ycombinator.com