CS5430 Homework 3: Authentication of People
You may (but do no have to) collaborate with one other student on this assignment.
If you do collaborate then
both students should form a CMS group and submit their solution to that group.
Both students are responsible for all of the answers.
Due: October 8, 2020 at 10:00am.
No late assignments will be accepted.
Submit your solution using CMS.
Prepare your solution as .pdf, as follows:
Use 10 point or larger font.
Put each problem into a separate file and submit it to the correct CMS
submission box for that problem.
Use at most 1 page per problem (unless stated otherwise).
Chapter 5 exercise 5.5.
Step 1 of Figure 5.7 in Chapter 5 stipulates that
nonce r be unpredictable.
The author of the protocol might instead have stipulated that nonce
r be unique (but need not be unpredictable).
Compare the security of the protocol for the two cases:
by identifying Dolev-Yao attacks that compromise one version but not the other
version of the protocol.
- r is unpredictable but not necessarily unique,
- r is unique but not necessarily unpredictable.
UUdine Corporation is engaged in highly classified research for governments,
so they restrict who is allowed to visit offices in their buildings.
Each building is equipped as follows.
in the lobby controls who may pass from the lobby into the corridors that
provide access to the offices.
The turnstile is controlled by messages it receives from UUdine's main computer system Sys.
There is a fingerprint reader positioned on the turnstile.
It can exchange messages with Sys.
Anyone who wishes to pass through the turnstile must have their fingerprints read.
The fingerprints of authorized individuals are stored on Sys,
so that computer is able to send signals to activate the turnstile (or not) as appropriate.
A human guard is present to ensure the proper use of the fingerprint reader and to ensure that
nobody attempts to circumvent the turnstile.
UUdine has decided to build and locate a new facility on the Cornell campus.
Since all members of the Cornell community have chip-enabled id cards,
UUdine will "upgrade" that building's access system to use these existing
id cards instead of fingerprints.
UUdine has asked you to consult on the design of the protocols.
They tell you to assume the following about the new setup.
The fingerprint reader on the turnstile is being replaced by an id card reader that has
The reader can receive messages from the keyboard as well as
send and receive messages to (i) Sys and (ii) an id card while
it is positioned in the id card reader.
The human guard will still be present.
You may design new programming for the id card and for Sys.
The computers embedded in the Cornell id cards are quite powerful, as is the computer
in the card reader.
These processors each have 64K of RAM,
can execute C programs, and
are capable of executing various cryptographic operations.
enc( K, m): outputs the result of encrypting m using public key K
The processor on an id_card, while that id card is inserted into the card reader,
can send/receive messages to that card reader;
the processor in the card reader can, in addition, (i) send/receive messages to Sys,
(ii) open the turnstile, or
(iii) sound an alarm.
In addition, card id_P has ROM storage
containing a public key K_P, a private key k_p, a pin PIN_P, and a unique identifier P.
dec( k, c): outputs the result of decrypting c using private key k
sign(k, m ): generates a pair < m, s(m) > where s(m) is a digital signature obtained for message m
by using private key k.
sigValid(K, < m , s >): outputs TRUE if and only if < m ,s > = sign(k, m ) holds and
K is the public key corresponding to private key k.
- Give the remaining steps for the protocol started below
that is executed by the id card, the card reader,
and Sys after an id card has been inserted into the card reader.
Use the notation we have been employing to describe authentication protocols,
with principals id_P (for the card), reader (for the card reader), HUMAN (for the person
whose card is inserted), and Sys (for the main computer system).
The protocol has been started below
0. id_P inserted into reader
1. id_P --> reader: P, K_P
2. reader --> Sys: send key for P?
Fingerprints are not easily transferred from one person to another, but id cards are easily transferred.
That means somebody who works at the Cornell building can facilitate entry to the facility by
somebody else (although only one of them could be in the building at a time).
How could UUdine defend against this vulnerability without purchasing additional equipment.
Changes to programming are allowed.