Hacker News Reader

Comment by amluto | Hacker News Reader

This is not necessarily good enough. Suppose one party sends R1 at a rate of 1 bit per 10 ns, i.e. 100 Mbps. The other party checks R1, aborts if it’s wrong, and otherwise sends R2. The first party checks that R2 was received on time and correctly.

An attacker can relay all but the last n of R1 and guess the last n bits. With probability 2^-n, the guess is correct, and the attacker learns R2 n*10 ns early. If the attacker can attempt the attack a few times, then getting a 60ns advantage is entirely reasonable and is enough to break some use cases.

So some more cleverness really is needed.

View on HN

I'm not seeing how this works. Let's say R1 and R2 are 8 bits each, and the attacker chooses n=2. Let the parties by C (car), F (fob), and M (attacker).

So C starts sending R1, M starts receiving R1, and after relaying 6 bits of R1 M guesses the last 2. Let's say M gets lucky and guesses correctly. So now M has the 6 bits of R1 it received from C, plus the 2 it correctly guessed, and so it has R1, 20 ns earlier than it should.

But to get F to send R2, M still had to send those 2 guessed bits on to F. That's 20 ns, assuming a fixed bit rate on the physical layer, which is how I assume these kind of systems would be designed. That should prevent M from learning R2 early.

The hardware I was envisioning for this would have a shift register on F that gets loaded with R1 xor R2. As the range finding bitstream comes in, it would shift out the bits from that shift register, xor them with the incoming bits, and transmit the result.

Similar on C. Load a shift register with R2. As echo bits come in, shift bits out of the shift register, xor with the incoming bit, and shift the result into another shift register (or get fancy and do this all with one circular shift register). At the end of the echo message, if the output shift register is all zero, it got the right R2.

Note that with this implementation there is no aborting on F if it receives the wrong R1. The wrong R1 simply makes it send back the wrong R2.

(Note: this design assumes that C and F both can simultaneously transmit and receive).

Ah, but then I can learn R2 by simply sending F enough R1, no?

Hmm, I may indeed be wrong. I guess that the fob won’t start transmitting R2 until after it receives all of R1, so the early guess doesn’t help. This does assume that the fob doesn’t accept higher-than-expected data rates. That last bit could be a real issue if the physical later can operate at multiple data rates and the attacker can convince the car and fob to disagree on the rate.

But I think your xor register is no good. The attacker can just send all zeros to learn R1 xor R2 and then can emulate the fob at whatever range it likes when the car sends the real R1. Also, the radios are likely to be half-duplex, which may make it impossible. Instead, I think F just verifies each bit and stores a single bit of state indicating whether the bits were all correct. Then, after the last bit is received, it transmits R2 if all bits of R1 were correct.

Why does the attacker gain a time advantage here? Is the attacker capable of transmitting at a much higher rate than the original sender? Even in that scenario, they just have to negotiate a send/receive rate up front, and that way the attacker can't jump the line because that would violate the negotiated rate (nor can the attacker intercept and increase the rate because then the original sender won't be transmitting fast enough).

R1 and R2 aren't reused. So you can't chain the attack to gain enough of an advantage.

My attack doesn’t need reuse. It’s based on the fact that cheating the protocol has a success probability that falls off too slowly with the amount of cheating.

This can be improved with multiple rounds. I’m not sure it’s possible, even in theory, to do better in a single round.

Reply on news.ycombinator.com