Cryptography Reference
In-Depth Information
It is apparent that we have a set of 2
m
equations with 2
m
+2variables.These
variables can be divided into two groups:
1. 2
m
half-nonces:
n
(
i−
1)
l
,...,n
(
i
+
m−
1)
l
,n
(
i
r
,...,n
(
i
+
m−
2)
r
2.
L
and
k
(
i
a
.
So, if we fix the value of variables
L
and
k
(
i
a
, we end up with 2
m
equations and
2
m
half-nonce variables. This implies that the 2
m
half-nonces can not be chosen
independently and fulfil the above equations simultaneously. In other words, if
we observe the outputs of
m
consecutive runs of the protocol, it is only necessary
to search over all possible sequences of
k
(
i
a
and
L
,whichis2
2
N
, and then it will
be possible to find all 2
m
half-nonces uniquely. As we will see, this weakness is
the result of introduction of a tighter bound for the half-nonces while we keep
observing more runs of the protocol.
By the randomness nature of the generated half-nonces, the total number
of possible sequences for them(2
2
N
) is uniformly distributed over them. This
implies that each of the 2
m
half-nonces is expected to have a bound of
2
m
√
2
2
N
possible values (comparing to its previous bound which was
N
). Therefore, for
m
consecutive protocol runs, the total number of possible values distributed over
the 2
m
half-nonces is 2
m
2
m
√
2
2
N
[17].
Now, if we exclude the value which half-nonces has taken already(2
m
2
m
√
2
2
N
−
2
m
), we can calculate the probability that at least one half-nonce does not receive
another possible value (remains constant). To do so, we utilize the well-known
problem in probability theory(i.e. Given
r
balls thrown uniformly at random at
b
bins, the probability that at least one bin remains empty which is calculated
by (21))[18]:
b−
1
b
+
r−
1
r−
1
Pr(at least one bin remains empty) = 1
−
b−
1
(21)
Now, it only requires to substitute
b
=2
m
and
r
=2
m.
2
m
√
2
2
N
−
2
m
in (21) and
then we will have (22). The result is plotted in Figure 2.
2
m.
2
√
2
2
N
−
2
m−
1
2
m−
1
P
h
= Pr(at least one half-nonce remains constant) = 1
−
2
m.
2
√
2
2
N
−
1
2
m−
1
(22)
Figure 2 shows the probability of inferring at least one half-nonce in terms of the
number of consecutive runs of the protocolrequiredtobeobservedtodoso.For
example, if we observe 35 runs of the protocol runs with
N
=256, we will be able
to determine at least one of the 70 transmitted half-nonces with the probability
of more than 0.99.
We will use the term ”
victim
half-nonce” for inferred half-nonce and notation
m
h
instead of
m
for the number of consecutive runs of the protocol required to
infer one half-nonce hereafter.
Search WWH ::
Custom Search