CSCI-UA.0480-11: Intro to Computer Security Homework 1

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.