2007 - Exercises IX.
1. Alice wants to login to a computer system and needs to communicate her password
to the system.
Alice uses a wireless keyboard but her husband Bob has infected her computer
by a key-logger program. Bob also intercepts wireless communication between
the keyboard and the computer. However, neither Alice's display nor the connection
between Alice's computer and the system can be monitored.
Propose a simple protocol that allows Alice to securely authenticate to the
system.
2. Let CBC-MAC be of the following form:
CBC-MACfc = /fc(/fc(... fkUkinn) e m a ) . . . 0 m,,_i) 0 mn),
where fk : {0, l}m
--ˇ {0, l}m
is an encryption function with a key k and m =
TOI||TO2|| ... \\mn is a message of length nm.
(a) Show that CBC-MAC is not secure if messages can be of varying lengths.
(Show that if messages have variable length then it is possible to mount a
chosen message attack, ie. given valid MACs for messages M\, M 2 , . . . , MN,
an attacker can produce a valid MAC for a new message M ^ Mi.)
(b) Suppose that we append the length of the message, I, as an extra block at
the end (m = mi||m2|| ... ||TO,,||/), before computing the MAC. Show that
it is still possible to mount a chosen message attack.
3. Consider a generic secret sharing scheme.
A dealer D wants to share a secret s between n parties so that t of them have
no information about s, but t + 1 of them can reconstruct the secret.
Let v denote the number of possible values of s and let w denote the number
of different possible share values that a given party might receive, as s varies.
Assume that w is the same for each party.
What is the relation between v and w? Explain.
4. There are four people in a room and exactly one of them is an adversary. The
other three people share a secret using Shamir's (3,2)-secret sharing scheme
over Zu. The adversary has randomly chosen a pair of numbers for himself.
The four pairs are (x\,yi) = (1,4), (2,2/2) = (3,7), (3,2/3) = (5,1) and
(2:4,2/4) = Í7
'2
)Determine
which pair was created by the adversary. Determine also the shared
secret. Explain your reasoning.
5. Let p be a large prime and let n < p, t < n E N.
Propose a protocol which enables n parties to colectivelly choose a secret random
number s E {0,... ,p-- 1}. After executing the protocol the parties should share
s using Shamir's (n, r)-secret sharing scheme.
6. Suppose that Alice uses the Okamoto identification scheme with p = 88667,
q = 1031, ai = 58902 and a2 = 73611.
(a) Alice chooses exponents a\ = 846 and a2 = 515. Compute in detail v.
(b) Alice chooses exponents k\ = 899 and k2 = 16. Compute in detail 7.
(c) Bob sends the challenge r = 489 to Alice. Compute in detail Alice's response
j/i and j/2(d)
Perform Bob's calculations to verify y1 and y2.
7. Consider the following protocol, involving a dealer and n recipients, for distributing
information.
Framework of the protocol is the following:
* Let ŕ be a fixed number, 0 < t < n.
* Each participant can send a private message to any other participant.
* The dealer begins with information v.
* After execution of the protocol, each recipient either accepts or rejects.
* The dealer and/or up to t recipients may cheat.
Steps of the protocol follows:
(i) The dealer sends v to each recipient.
(ii) Each recipient sends to each other recipient the value received in the previous
step.
(iii) Each recipient verifies whether more than t of the values received in the
previous step are different from the value received in the first step. If more
than t values are different, it sends a complaint to each recipient.
(iv) Each recipient accepts if it receives at most t complaints (including its own).
Otherwise the recipient rejects.
Answer the following questions. Explain your reasoning.
(a) Suppose that the dealer is honest. For which t every honest recipient ac­
cepts?
(b) Suppose that the dealer cheats. For which t the honest recipients either all
accept or all reject?
(c) Suppose that no recipient complains in the third step. For which t all
honest recipients have the same value from the dealer after the protocol has
finished?
(d) Suppose that the recipients later reconstruct the dealer's value by sending
their values to a trusted (and honest) party who decides by majority. Suppose
further that the dealer is honest. For which t the values which the
cheating recipients send to the trusted party cannot influence the outcome
of the reconstruction?