Cryptography Reference
In-Depth Information
Exercise 2.8. We want to break a keyed cryptographic system. We assume we have
access to an oracle which on each queried key answer whether or not the key is correct.
We iteratively query the oracle with randomly selected keys (in an independent way).
Compute the expected complexity (in term of oracle queries) in general, and when the
distribution of the key is uniform. How can we improve the attack?
Exercise 2.9. We assume that we have an oracle which for any of the N possible keys
K answers if it is correct or not.
If the a priori distribution of the keys is not uniform but known by the adversary,
what is the best algorithm for finding the key with the oracle? Prove that its complexity
relates to the guesswork which is defined by
N
W ( K )
=
i
.
Pr[ K
=
k i ]
i = 1
where all possible keys k 1 ,...,
k N are sorted such that the Pr[ K
=
k i ] sequence is
decreasing. 15
As an example, let us consider a pseudorandom generator which generates an
element x of
uniformly for a given prime number p. In order to get
a random n-bit string, we consider K
{
0
,
1
,...,
p
1
}
x mod 2 n .
=
2 n . Example: n
2 64
1. Compute W ( K ) for p
>
=
64 and p
=
+
13 .
2 n . Example: n
2 64
2. Compute W ( K ) for p
<
=
64 and p
=
59 .
=|
2 n
|
3. Let
p
. Express W ( K ) in terms of
and compare both cases.
Exercise 2.10. Explain how to make a dictionary attack against UNIX passwords.
What is the complexity?
Exercise 2.11. We assume that we have an oracle which for any of the N possible keys
K answers if it is correct or not.
If the a priori distribution of the keys is not uniform but known by the adversary,
what is the best memoryless algorithm for finding the key with the oracle? Prove that
its complexity relates to the Renyi entropy of coefficient
1
2 which is defined by
N
k i ] 2
Pr[ K
H 2 ( K )
=
=
i = 1
k N is the list of all possible keys. 16
where k 1 ,...,
15
This exercise was inspired by Ref. [123].
16
This exercise was inspired by Ref. [39].
 
Search WWH ::




Custom Search