CS255: Cryptography and Computer Security Winter 2017

Final Exam

Instructions:
− Answer all five questions.
− The exam is open book and open notes. Laptops are allowed with the network card turned
off. Connecting to a network during the exam is a serious violation of the honor code.
− Students are bound by the Stanford honor code.
− You have two hours.

Problem 1. Questions from all over.

a. Explain what goes wrong if we use the same key k in deterministic counter mode to encrypt
two different messages m0 6= m1 .
b. Suppose h : X → Y is a collision resistant hash function, where Y ⊆ X . Is the function
h2 (x) = h(h(x)) collision resistant? Give an attack on h2 , or prove that h2 is collision
resistant by showing that an attack on h2 gives an attack h.
c. Let (S, V ) be a MAC where the tag space is T = {0, 1}16 . Show that (S, V ) cannot be a
secure MAC.
d. Let (S, V ) be a secure MAC defined over (K, M, T ) where T = {0, 1}n . Define a new MAC
(S 0 , V 0 ) as follows: S 0 (k, m) is the same as S(k, m), except that the last eight bits of the
output tag t are truncated. That is, S 0 outputs tags in {0, 1}n−8 . Algorithm V 0 (k, m, t0 )
accepts if there is some b ∈ {0, 1}8 for which V (k, m, t0 k b) accepts. Is (S 0 , V 0 ) a secure
MAC? Give an attack or argue security.
R
e. Let (G, S, V ) be a secure signature scheme and let (pk, sk) ← G(). One concern is that the
signer Bob, who has sk, can find two messages m0 6= m1 that have the same signature σ.
Suppose Bob gives Alice the signature σ on message m0 . Bob can later claim that he actually
signed m1 , not m0 . A judge would have difficulty deciding what Bob actually signed. We say
that the signature is non-binding. Give an example of a secure, but non-binding signature
scheme.
Hint: try using the hash function from Problem 3 of homework 3, in combination with a
secure signature scheme (G0 , S 0 , V 0 ). Make sure to explain how algorithms (G, S, V ) in your
signature scheme work.

Problem 2. Authenticated encryption. In class we said that when using encrypt-then-MAC it is

important to use independent keys for the CPA-secure cipher and for the MAC. Let us see an
example of a CPA-secure cipher and a secure MAC that are insecure when used in encrypt-then-
MAC with the same secret key k.
Let (E, D) be a block cipher defined over (K, X ) where X = {0, 1}n and |X | is large. Consider
randomized CBC mode encryption built from (E, D) as the CPA-secure cipher for single block

1
 messages: an encryption of m ∈ X is the pair c := (r, E(k, r ⊕ m)) where r is the random IV.
As the secure MAC, let’s use RawCBC built from (E, D). This MAC is secure in this context
2

length messages (messages in X ): the tag on a ciphertext
because it is only being applied to fixed
c ∈ X is t := E k, E(k, c[0]) ⊕ c[1] . The complete encrypt-then-MAC ciphertext is (c, t) ∈ X 3 .
2

a. Show that using the same key k for both this cipher and this MAC in encrypt-then-MAC
results in a cipher that does not provide authenticated encryption.
b. Suppose the cipher and MAC keys are not equal, but are chosen so that they have a known
relation, say kmac = kenc ⊕∆ for a known ∆ ∈ X . Give an example of a CPA-secure cipher and
a secure MAC that when combined using encrypt-then-MAC do not provide authenticated
encryption.
Hint: try to adjust the construction from part (a).

Problem 3. Dictionary attacks.

a. Briefly explain what is a dictionary attack on a password identification scheme.

b. In class we discussed MAC-based challenge-response identification. Suppose the user’s secret
key sk is a password. Show that a network eavesdropper who listens in one successful execution
of the identification protocol can mount a dictionary attack to recover the user’s password sk.
c. Suppose the identification protocol from part (b) is executed over a TLS tunnel with one-sided
authentication, where the server presents a server-side certificate. The client, however, does
not adequately check the server certificate, and in particular, accepts self-signed certificates.
Can an active attacker mount a dictionary attack on the user’s password? Justify your answer.
d. Let’s enhance MAC-based challenge response to protect it from a dictionary attack without
using a server certificate. Let G be a Diffie-Hellman group of prime order q with generator
g ∈ G. Let h, k ∈ G be random generators of G (both are a random power of g) and all of
g, h, k are public values. Let pw ∈ Zq be the shared password and let H be a hash function.
The ID protocol begins as follows:
• server: s ←R
Zq , S ← g s hpw , send S to user.
• user: u ←R
Zq , U1 ← g u k pw , U2 ← (S/hpw )u , U3 ← H(pw, S, U1 U2 ),
send (U1 , U3 ) to server.
Explain what the server should check when verifying the user’s response.
Note: It can be shown that this protocol prevents dictionary attacks against an active
adversary, assuming the CDH problem is hard in G.

Problem 4. The iMessage attack.

a. The parity bit b for a binary string m is the XOR of all the bits in m. Consider a cipher
where messages are variable length bit strings, and encryption is done using randomized
counter mode without any padding. No MAC is used, but before the plaintext is encrypted
with counter mode, the sender appends a parity bit to the end of the plaintext. When the
receiver decrypts, it checks the parity bit and outputs reject if the bit is invalid.
Design a chosen-ciphertext attack that recovers the complete plaintext of every encrypted
message. That is, given a target ciphertext c, your goal is to issue a sequence of ciphertexts

2
 to the decryptor. For each ciphertext, the decryptor sends back reject if the ciphertext is
rejected. Otherwise it sends accept. Show that the attacker can use these accept/reject
responses to decrypt all of c.
This attack, called chop-chop, was used successfully against the 802.11b protocol, where a
WiFi access point played the role of the decryptor.
b. Signcryption combines public-key encryption with a signature to provide both message con-
fidentiality and source identification. Signcryption is used in messaging systems like Apple’s
iMessage. Consider the following simple scheme: First, Alice generates a public-key/secret
key for a signature scheme (pksig , sksig ). Later, when she wants to send a message m to
Bob, she obtains Bob’s public-key encryption key pkenc and uses the following encryption
algorithm:
 R R R


 k ← K, c0 ← Epub (pkenc
, k), c1 ← Esym k, (id A , m) 
E 0 (sksig , id A , pkenc , id B , m) := σ← R
S sksig , (c0 , c1 , id B )
output (c0 , c1 , σ)
 

Here id A and id B are Alice’s and Bob’s identities, and (Esym , Dsym ) is a symmetric cipher with
key space K. Also, (Gsig , S, V ) is a signature scheme and (Gpub , Epub , Dpub ) is a public-key
encryption scheme. Bob decrypts by doing:
 

 if V (pksig , (c0 , c1 , id B ), σ) = reject, output reject 

k ← Dpub (skenc , c0 ), (id , m) ← Dsym (k, c1 )
 
0


D pksig , id A , skenc , id B , (c0 , c1 , σ) :=

 if id 6= id A output reject 

otherwise, output m
 

Notice that the encryption algorithm signs the symmetric ciphertext c1 using Alice’s secret
signing key. One might think that the signature on c1 adequately provides ciphertext integrity,
and therefore it suffices for (Esym , Dsym ) to be CPA-secure, rather than an authenticated
encryption cipher. In particular, suppose the developers use randomized counter mode as the
cipher (Esym , Dsym ).
Let’s show that the encryption scheme (E 0 , D0 ) is insecure. Suppose that as in part (a),
a parity bit is appended to the plaintext during encryption and this bit is checked during
decryption. Use your attack from part (a) to show that given a ciphertext (c0 , c1 , σ) from
Alice, an adversary can completely decrypt this ciphertext. As in part (a), the adversary
issues a stream of ciphertexts to Bob, and Bob responds with accept or reject to each. The
sequence of responses should enable the adversary to decrypt (c0 , c1 , σ). You may assume
that the adversary is a user in the system and has its own signing key pair (pkadv , skadv ).
Note: Once again, the lesson is to only use authenticated encryption symmetric ciphers.

Problem 5. Exponentiation algorithms. Let G be a finite cyclic group of order p with generator g.
In class we discussed the repeated squaring algorithm for computing g x ∈ G for 0 ≤ x < p. The
algorithm needed at most 2 log2 p multiplications in G.
In this question we develop a faster exponentiation algorithm. For some small constant w, called
the window size, the algorithm begins by building a table T of size 2w defined as follows:

set T [k] := g k for k = 0, . . . , 2w − 1 . (1)

3
a. Show that once the table T is computed, we can compute g x using only (1 + 1/w)(log2 p)
multiplications in G. Your algorithm shows that when the base of the exponentiation g is
fixed forever, as in the Diffie-Hellman protocol, the table T can be pre-computed once and
for all. Then exponentiation is faster than with repeated squaring.
Hint: Start by writing the exponent x base 2w so that:

x = x0 + x1 2w + x2 (2w )2 + . . . + xd−1 (2w )d−1 where 0 ≤ xi < 2w for all i = 0, . . . , d − 1.

Here there are d digits in the representation of x base 2w . Start the exponentiation algorithm
with xd−1 and work your way down, squaring the accumulator w times at every iteration.
b. Suppose every exponentiation is done relative to a different base, so that a new table T must
be re-computed for every exponentiation. What is the worse case number of multiplications
as a function of w and log2 p?
c. Continuing with Part (b), compute the optimal window size w when log2 p = 256, namely the
w that minimizes the overall worst-case running time. What is the worst-case running time
with this w? (counting only multiplications in G)
d. Set d := d(log2 p)/we. Going back to the case of a fixed generator g, show how one can
pre-compute a table of size 2w · d once and for all, so that using this table exponentiation can
be done with at most d multiplications in G. This is a factor 2w improvement over repeated
squaring, but requires storing a large pre-computed table.
Hint: Try creating d tables T0 , . . . , Td−1 , where each table has a structure similar to T
from (1).