CSCI-UA.0480-11: Intro to Computer Security Spring 2019

Homework 1

via classes.nyu.edu1. Threat modeling: Imagine you’ve just been hired to produce a comprehensive threat model for

CitiBike , New York’s public bike share system. Describe three security policies, and for each of

them describe a technical mechanism to enforce those policies. Choose one policy each that

deals with a threat from thieves (financially motivated attackers), terrorists (attackers aiming to

cause violent disruption) and trolls (attackers trying to cause inconvenience or annoyance).

2. Hash functions : In class we discussed several desirable properties for hash functions, in

particular one-wayness and collision-resistance . In this exercise, we’ll show that neither property

implies the other. We can do this by counter-example:

a. First, define a function that is one-way, but not collision-resistant. Hint: The answer will

be a trivial function that you would never use as a cryptographic hash function.

b. Second, define a function that is collision-resistant, but not one-way. Hint: Assume you

have a collision-resistant hash-function H. Use that to build a hash function H’ which is

still collision-resistant, but not one-way. This will also be a highly artificial function that

you would never use a cryptographic hash.

3. Semantic security for the Vigenère cipher: The Vigenère cipher was a major advance in its day,

but does not satisfy the modern definition for semantically secure encryption.

To show this, describe how an adversary that can win the semantic security game, even without

making any chosen-plaintext or chosen-ciphertext queries. Your algorithm should submit two

equal-length candidate plaintexts and then determine which one was encrypted to produce the

ciphertext returned by the challenger. Assume the challenger chooses a random key of random

length up to 50 characters. Hint: your candidate plaintexts should be longer than 50 characters.

4. Hash functions and one-wayness : Bob is launching a new secure messaging app, BobCrypt.

When Alice installs the app, it creates an account for her on the BobCrypt server using a hash of

her phone number. The app then queries the server by sending the hash of each phone number

in Alice’s address book to learn which of Alice’s friends already have BobCrypt accounts. The

goal is that users can discover their friends’ accounts while preventing the server from learning

every user’s address book.

Bob argues that the server only sees the hashes of users’ contacts’ phone numbers, and since

hash-functions are one-way, this doesn’t reveal any information about the actual phone

numbers. Explain to Bob why he’s wrong by describing how a malicious server could in fact learn

users’ contacts’ phone numbers.

5. Block cipher modes of operation: In class we saw several modes such as ECB, CBC and CTR

mode. Let’s look at another possible mode of operation “plaintext block chaining” (PBC) which is

similar to cipher block chaining (CBC) but allows for encryption in parallel:

Unfortunately, PBC mode is not secure. To see this, show how an attacker who knows IV, C 0 , C 1 ,

C 2 (which are public) and also knows that M 1 =M 2 =X can easily compute M 0 .

6. CBC-MAC : Alice is trying to design a MAC using a block cipher. She decides to use the following

construction, which is essentially just CBC encryption, throwing away all but the final block:

Unfortunately, this construction is not secure. Describe how to produce an existential forgery

against this MAC scheme. Hint: Start with two messages M 1 and M 2 (not to be confused with the

individual blocks of a message in the diagram above) for which you know the outputs (IV 1 , T 1 )

and (IV 2 , T 2 ). Produce another message M 3 for which (IV 1 , T 2 ) will be the MAC. M 3 will be close to

the concatenation M 1 ||M 2 , but with one block altered. Hint 2: There’s also a way to produce a

forgery with only one known block, if you look closely…

7. Stream ciphers and PRGs: We saw that one can build a secure stream cipher directly from a

PRG. After learning about weaknesses found in RC4, Alice wants to encrypt a message for Bob

using a stream cipher built from two candidate PRGs, call them G 1 and G 2 . The goal is that if

either is a secure PRG, the resulting cipher is a secure stream cipher. Which of the following

options will provide semantically secure encryption? If so, explain why. If not, explain a

distinguishing attack.

a. Encrypt( m , k ) = m ⨁ G 1 ( k ) ∨ G 2 ( k ) (where ∨ is a bitwise OR)

b. Encrypt( m , k ) = m ⨁ G 1 ( k ) ⨁ G 2 ( k ) (where ⨁ is a bitwise exclusive-OR)

c. Encrypt( m , k ) = [ m ⨁ G 1 ( k )] ‖ [ m ⨁ G 2 ( k )] (where ‖ is a concatenation)

8. Public key crypto at toy security levels:

a. Suppose Alice and Bob are performing a Diffie-Hellman key exchange using p =10007 and

g =3. Alice choose a =2462 and Bob chooses b =4319. What will their shared secret be?

b. Alice chooses an RSA key with p =383 and q =401, giving a public key of N = 153583. What

is φ( N )? If she chooses e =11, what will d be? If Bob wants to encrypt the message 1337

to Alice, what will the ciphertext be?

9. Shared modulus RSA: In an effort to save cost, suppose that Columbia University decides to use

a single RSA modulus N for all students on campus. Each student is then given their own ( e, d )

pair but not told what φ( N ) is. Explain why this is insecure. In particular, show that two students

with distinct keys ( e 1 , d 1 ) and ( e 2 , d 2 ) can easily recover φ( N ). Hint: recall that computing the

greatest common divisor (GCD) of two numbers is very efficient, even for huge numbers.

Note: there is actually an algorithm to recover φ( N ) given only one RSA key pair ( e, d ).

10. Digital signatures: Most signature schemes have a limit on the size of messages they can be

used to sign. For example, with RSA signatures the message must be an integer mod N for a

modulus N that is typically 1024-4096 bits long. With DSA messages typically must be an integer

mod p for a prime that is 1024-2048 bits long.

Typically, the message is first hashed and then the message hash is what is actually signed. Alice

decides that hash functions are a bore and instead she’ll just break her message up into blocks

m 1 , m 2 …, sign each block and let the entire signature be the concatenation:

σ( m ) = σ( m 1 ) ‖ σ( m 2 ) ‖ …

Explain to Alice why this is insecure. In particular, explain how to create a forgery.