CS 6324: Information Security Spring 2021
Homework #2
Due date & time: 11:59pm CST on March 12, 2021. Submit to eLearning by the due time.
Additional Instructions: The submitted homework must be typed. Using LATEX is recommended, but not
required.
Problem 1 (10 pts) Cryptanalysis against Encryption Modes
• (4 pts) Suppose that everyone in the world is using the DES algorithm in the ECB encryption
mode, and you can use a chosen plaintext attack against everyone. Show how to perform a
dictionary attack such that, after an expensive initialization step, everyone’s key can be recovered
in very little time. Write pseudo code both for the initialization step and for the function to
recover everyones key.
• (2pts) How effective would the above attack be if AES, instead of DES, is used?
• (2pts) How effective would the above attack be under known-plaintext (instead of chosen plain-
text) attacks?
• (2pts) How effective would the Chosen Plaintext attack described above be if everyone uses the
CBC encryption mode with the IV randomly chosen?
Problem 2 (6 pts) Levels of security
• (2 pts) Assume that you are doing an exhaustive key search attack and can check 232 (or about
4G) keys per second, about how many years would it take to for you to search through all keys
while attacking ciphers of the following key lengths: 56, 64, 80?
• (2 pts) Still assuming that you can check 232 keys per second, further assume that the age of
universe is 13.7 billion years, how many ages of the universe does it take to search through a key
space of 128 bits.
• (2 pts) Does this mean that a cipher of 128 bit can never be broken by brute-force? Justify your
answer.
Problem 3 (9 pts) We use birthday collision to illustrate breaking the three desirable properties for cryp-
tographic hash functions: Preimage resistant, Second preimage resistant, and Collision-resistant. As-
sume that there are 365 days in a year, and the birthday of each person is distributed uniformly. We
consider three groups: Group A has 25 persons, group B has 35 persons, and group C has 180 persons.
We assume that the distribution of birthdays for group members are random. Answer the following
questions for each of the three groups: A, B, and C. Write out the equation, then give the numerical
results (which can be computed by using calculators or writing a small program. You don’t need to
provide your code).
• (3 pts) What is the probability that a group contains someone with date of birth being Jan 1?
(This corresponds to preimage attack.)
• (3 pts) What is the probability that a group contains someone that has the same date of birth as
you? You are not part of the group. (This corresponds to second preimage attack.)
• (3 pts) What is the probability that one can find two members in a group such that they have the
same date of birth? (This corresponds to collision attack.)
Problem 4 (10 pts) Message Authentication Code (MAC)
a (3 pts) When we say that an MAC needs to resist Existential Forgery under Chosen Plaintext At-
tack, what do we mean? State the precise definition.
b (3 pts) Consider the following MAC construction that uses AES. Given a message M , it is padded
to so that its length in bits is a multiple of 128, and divided into blocks of 128 bits each:
M1,M2, . . . ,M`. The MAC value under a key k is defined as MACk(M) = AESk(M1) ⊕
AESk(M2) ⊕ · · · ⊕ AESk(M`). Show that this MAC construction is insecure by giving a
concrete attack.
c (4 pts) Consider another MAC construction that uses AES. We limit ourselves to consider mes-
sages whose lengths are multiple of 96 bits, and are at most 232× 96 bits long. Given a message
M , it is divided into blocks of 96 bits each: M1,M2, . . . ,M`. Each Mi is then padded to
128 bits by including the binary encoding of i in the beginning of each block Mi. We use
M ′i to denote the padded blocks. The MAC value under a key k is defined as MACk(M) =
AESk(M
′
1) ⊕ AESk(M ′2) ⊕ · · · ⊕ AESk(M ′`). Show that this MAC construction is insecure
by giving a concrete attack.
Problem 5 (7 pts) CBC-MAC In class, we discussed HMAC. Another commonly used MAC scheme is Ci-
pher Block Chaining Message Authentication Code, abbreviated CBC-MAC. This constructs a mes-
sage authentication code scheme from a block cipher. To compute the CBC-MAC of a message given
a key K, one uses the key K to encrypt the message in CBC mode, using 0 as the IV, and the final
ciphertext block is the MAC value.
a (2 pts) Let EK be the encryption function with block size b and key K, B0 = 00 · · · 0 be the IV
used in CBC-MAC, and ⊕ to denote bit-by-bite XOR. Write the formula for the CBC-MAC of
a two-block message M = M1M2, i.e.
CBC-MACK(M1M2) =.
b (5 pts) CBC-MAC is only secure for fixed-length messages. Show that when variable-length mes-
sages are allowed, CBC-MAC is insecure against a chosen-plaintext attack. That is, show that
given M and CBC-MACK [M ], how to come up M ′ and CBC-MACK [M ′] for some M ′.
Problem 6 (12 pts) RSA encryption. Assume that the message space consists of all 24-bit non-negative
integer numbers. We use N = 60529591 for RSA encryption.
a (3 pts) Write a program that computes p and q such that pq = N = 60529591. Provide the values
of p, q, and the value of Φ(N).
2
b (3 pt) We choose e = 31. Provide the value of d such that (ed mod Φ(N)) = 1.
(The algorithm for doing this is known as the extended Euclidean algorithm. If you do not know
the algorithm, and do not want to learn the algorithm yourself, you can use an inefficient method
such as enumerating over all positive integer numbers less than φ(N) and checking which one
satisfies the requirement. For large N , this inefficient method takes too long time; but for the
number here, it should be fast enough.)
c (0 pt) If you are unfamiliar with RSA, write a program that loops through all value x’s such that
1 ≤ x ≤ N − 1, to verify that (xed mod N) = x. This is just to help convince yourself that
RSA decryption works.
Hint: When computing xy mod N , directly computing xy may overflow the representation
of integers you have. You can use the Square and Multiply method, which exploits the fact
that xab mod N = (xa mod N)b mod N . You can also exploit the fact that xy+1 mod N =
(xy mod N)x mod N .
d (3 pts) For each of the following ciphertexts 10000, 20000, 30000, 40000, 50000, 60000, show the
decrypted message, as a base-10 number. Here we allow these messages to be beyond a 24-bit
integer.
e (3 pts) Describe how an adversary can recover any message encrypted in this way without factor-
ing N . That is, the message space remains the same. However, the value of N is so large that
factoring it becomes infeasible.
Problem 7 (12 pts) ElGamal encryption. Again assume that the message space consists of all 16-bit inte-
gers. Consider ElGamal encryption. Let us choose p = 96737. Then we have
Z∗p = {1, . . . , 96736}
a (3 pts) Write a program to find g, the smallest generator of Z∗p , i.e., g is the smallest number in Z∗p
such that the set {g1 mod p, g2 mod p, · · · , g96736 mod p} = Z∗p . Provide the value g.
(The program can simply tries each number starting with 2 and see whether it is a generator. A
number a is a generator for Z∗p if and only if the smallest positive integer j such that gj mod p =
1 is j = p− 1.)
b (3 pts) Write a program that computes the discrete logarithm in Z∗p , and use it to compute the value
x = logg 90307 in Z
∗
p . That is, find x such that (g
x mod p) = 90307. (You can use the
inefficient brute-force method.)
c (3 pts) Write a program that implements ElGamal decryption. Then decrypt the following ci-
phertexts: (5000, 5001), (10000, 20000), (30000, 40000), (50000, 60000), (70000, 80000),
(90000, 100000), which were encrypted under the public key given above, i.e., (p, g, 90307).
Show each decrypted message as a base-10 number.
(In El Gamal decryption of (c1, c2), you can compute x and need to find M such that
(xM mod p) = c2. To do this, you need to first compute z = (x−1 mod p), that is, com-
pute z such that (xz mod p) = 1. Given z, you can compute M = (zc2 mod p). Refer to Part
b of the RSA question for how to find z.)
d (3 pts) In Problem 6e, you showed how to break RSA encryption without factoring N . Can you
recover a the plaintext from an ElGamal ciphertext without solving the discrete log problem or
3
the Computational Diffie-Hellman problem, which are infeasible when p is very large? If yes,
describe how. If no, explain why.
Problem 8 (9 pts) Hash Collisions and Digital Signatures. In a brute-force attack to find collisions for
a hash function with a n-bit output, one chooses a group of m = 2n/2 different messages. The
probability that among them there are two messages that have the same hash is quite high, because
the m messages give m(m−1)2 pairs, each of which having the probability
1
2n to give a collision.
a (4 pts) Given two groups X and Y of messages, we aim to finding a collision between a message
in X and a message in Y . Suppose that each of X and Y contains m = 2n/2 messages, what
is the probability that at least one collision between a message in X and one in Y exists? Write
out the formula, and compute/estimate it for n = 128.
b (5 pts) Suppose that Bob is preparing a contract that Alice purchases a product from Bob at a cost
of 1 million dollars for Alice to digitally sign. Bob wants to generate also a contract that sets
the price at 10 million dollars. Bob is willing to put in O(2n/2) amount of computation for the
chance to cheat 9 million.
More specifically, Bob can apply the hash function 2 × 2n/2 = 2n/2+1 times, which is still
O(2n/2). In addition, Bob can run an algorithm that takes time O(n2n/2). For all practical
purposes, we can view O(n2n/2) as just O(2n/2), since n is small as a multiplication factor.
Describe a way for Bob to come up with two versions of the contracts with the two different
prices, but have the same hash value. For simplicity, let us assume that the document is a long
and wordy (as legal documents are) ASCII text file. You will need to generate many candidates
for the contracts. Describe how you can systematically generate the ones you need.
Problem 9 (9 pts) The UNIX crypt function is a hash function that only looks at the first eight bytes of the
input message. For example, crypt(helloworld) returns the same value as crypt(hellowor).
Some web sites use the following authentication method to authenticate users: (1) the user types in
a user-id and a password P into his web browser, (2) the site, upon verification of the password P ,
computes T =crypt(user-id||K), where || denotes string concatenation, and K is a `-byte site
secret key ` ≤ 8, (3) the site sends a cookie back to the user containing T , (4) the user can use T to
authenticate himself to the site in future connections.
Show that by choosing clever user-id’s (of varying length) an attacker can expose the site’s secret key
K in time approximately 128`. More concretely, the user creates an account, logs in and receives
the corresponding T ; he then creates another account (with a different user-id, logs in and receives
another T . By repeating this sufficient times, the user recovers K completely. We are assuming there
are 128 possible values for each character in a string.
Hint: Try to recover one character of K for each account created. The attack is described in the pa-
per “Dos and Don’ts of Client Authentication on the Web” in USENIX Security Symposium, 2001.
Reading the paper is allowed.
4
Problem 10 (16 pts) Read the article “New Directions in Cryptography” by Diffie and Hellman (dh.pdf
is attached in eLearning), and answer the following questions. [To get a good grade in this question
make sure your answer is short and directly to the point. Bullet-points answers are recommended.]
a (4 pts) The paper gives rationales for building encryption schemes that are secure against known
plaintext attacks and chosen plaintext attacks, by discussing how such schemes remove restric-
tions that are placed on the ways of using them. Discuss these rationale in your own words.
b (4 pts) List all the limitations and shortcomings discussed in the paper about symmetric encryption
schemes.
c (4 pts) List all the limitations and shortcomings discussed in the paper about symmetric message
authentication schemes.
d (4 pts) The paper establishes the relationships among (1) public-key encryption, (2) public key
distribution, and (3) digital signature (referred to in the paper as one-way authentication). By
relationships, we mean it is possible to use one scheme to implement another. List these rela-
tionships, and explain the constructions involved to use one scheme to implement another.
5

欢迎咨询51作业君