Passive Cryptanalysis of the UnConditionally Secure Authentication Protocol for RFID Systems - Information Security and Cryptology-ICISC 2010 - page 99

Our Result Expected

Fig. 3. Comparison of expected security margin of the UCS-RFID protocol and our
results in terms of the number of consecutive protocol runs an adversary must observe
in order to infer at least one nonce

3. Calculate m e = m t − m h

4. Choose two random numbers from and assign them to L , k ( i ) Z 2 N respec-

a

tively.
5. Find 2 m nonces ( n ( i− 1)
l

,...,n ( i + m h − 1)
l

,n ( i ) ,...,n ( i + m h − 2) ) as follows.

r r

-Find n ( i− 1)
l

from (15) i.e. n ( i− 1)
l

k ( i )

≡ A ( i ) − mod 2 N .

a

-Find n ( i ) from (16) i.e. n ( i )
l

( k ( i )

= D ( i ) ⊕ ⊕ L ).

a

-Find n ( i ) from (17) i.e. n ( i ) n ( i )

l

k ( i a .

( A ( i +1) mod 2 N ) ≡ − ⊕

r r

.

-Find n ( i + m h − 2)
r

from (19)i.e. n ( i + m h − 2)
r

≡ ( A ( i + m h − 1) − n ( i + m h − 2)
l

mod 2 N ) ⊕

i + m h − 2
j = i

( k ( i )
a

n ( j )
r

).

= D ( i + m h − 1) ⊕ ( k ( i a ⊕L ) i + m h − 2
j = i

-Find n ( i + m h − 1)
l

from (20) i.e. n ( i + m h − 1)
l

n ( j )
r

.

6. Repeat 4 and 5 as many times as we observe that only one half-nonce keeps
its value for all of the repetitions.
7. Save the constant(victim) half-nonce.
8. Observe another run of the protocol.
- A ( i + m h ) +( k ( i a i + m h − 1

j = i

n ( i + m h − 1)
l

n ( j r ) mod 2 N

≡

L i + m h − 1

j = i n ( j r ).
9. Replace the equations corresponding to the found victim half-nonce with
two newly observed equations in the equation set (15-20).
10. Repeat 4,5,6,7,8 for m e times.

- D ( i + m h ) = n ( i + m h )
l

( k ( i ) ⊕ ⊕

a