HB RFID attack. What am I missing?

Question

Regarding the RFID protocol HB (not HB+) I am having a hard time understanding why my approach will not work.

So in HB we have the Tag and the Reader whom both share a secret X.

We are trying to figure out X.

The protocol goes as follow:

Lets suppose k = 3 bits. From the papers I have read it seems the attack goes as follows. set a = 001 and send say 1000 times set a = 010 and send 1000 times set a = 100 and send 1000 times

take the parity which comes out the majority of times for each a revealing x.

This makes sense to me and works fine.

My question is, why can I not simply set a to 001. Since a = 001 when it is ANDED with x it will always produce x which will then be XOR with v. The resulting Z will always be either x or it will be x XOR with 1. We then just take the output that happens the majority of the times which would be x since the prob of v = 1 < .5

I feel like I would only have to run this say 10 times rather then running every a multiple times.

Am i missing an important aspect of this.

Thanks

Answer 1

Why can I not simply set a to '001'?

x and a are of length k, so

x = { x_k-1, ..., x₀ }
a = { a_k-1, ..., a₀ }

If, k = 3, this would be

x = { x₂, x₁, x₀ }
a = { a₂, a₁, a₀ }

I.e. x and a would be one of '000', '001', '010', '011', '100', '101', '110', or '111'.

So the scalar product x • a results in

x • a = (x₂ AND a₂) XOR (x₁ AND a₁) XOR (x₀ AND a₀)

Consequently using a = '001' results in

z = x • '001' = (x₂ AND '0') XOR (x₁ AND '0') XOR (x₀ AND '1') = x₀

So you would not get the remaining digits of x (i.e. x₂ and x₁) in that case. Similarly, if you use an a with more than one bit set, e.g. a = '111', you would get

z = x • '111' = (x₂ AND '1') XOR (x₁ AND '1') XOR (x₀ AND '1') = x₂ XOR x₁ XOR x₀

and therefore could dervice the digits of x. Thus, you need to perform the protocol with a = '001', a = '010', and a = '100' in order to get each digit of x.

I feel like I would only have to run this say 10 times rather then running every a multiple times.

Well, for every round, you will get a correct result with a probability v. So the expected value would be

E[X] = v, if the correct digit is a '1', and
E[X] = 1 - v, if the correct digit is a '0'.

Hence, the mean value over all rounds (i.e. every sample you take) will approximate v for a '1' and will approximate 1 - v for a '0' for an infinite number of rounds. But this does not necessarily mean that you already reach this expected value after 1 round or 10 rounds. However, with every round you increase the confidence of getting the expected value.