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

Fig. 2. The number of consecutive protocol runs an adversary must observe( m )in
order to infer at least one half-nonce for N = 128 , 256

4 Our Attack Scenario

In the previous section, we presented a probabilistic approach to find the number
of consecutive runs of the protocol to infer one half-nonce. But in our attack,
we need to have a complete nonce(left and right corresponding half-nonces) to
recover all secret keys. To achieve this goal, we propose an attacking scenario
which consists of the three following phases:

1. Finding the total number of necessary consecutive runs of the protocol to
find a complete victim nonce ( m t ).
2. Finding the victim nonce.
3. Recovering the secret keys.

4.1 Phase I: Finding m t

In section 3, we proposed a probabilistic way to calculate the number of con-
secutive runs that must be observed by an adversary to infer a half-nonce( m h ).
It is obvious that if we keep observing more runs of the protocol(i.e. more than
m h ), after each extra observation, another half-nonce can be inferred. This is
simply possible by eliminating the two equations which contain the first victim
half-nonce and adding two newly observed equations to the set of equations (15-
20) and then, we again have 2 m h equations and 2 m h +2 variableswhich yield
another half-nonce inference.
If we intend to find a complete nonce, we must continue observing the runs
of the protocol until we infer two corresponding victim half-nonces to form a
complete nonce. To do so, we should first calculate the probability that the
inferred half-nonce at ( m e + m h ) th run matches one of the previously victim
half-nonces.