[SOLVED] CPSC418 - Introduction to Cryptography ASSIGNMENT 3

Description

Problem 1 — Flawed MAC designs, 13 marks

For this problem, you need to carefully trace through the given MAC algorithms to understand the given attacks and explain how computation resistance is defeated.

Recall that iterated hash functions employ a compression function f in multiple rounds; SHA-1 is an example of such a hash function. Here, f takes as input pairs of n-bit blocks and outputs n-bit blocks, for some n ∈ N. The compression function f is assumed to be public, i.e. anyone can compute values of f. As a result, the hash function is also public, so any one can compute hash values. For simplicity, we assume that the bit length of any message to be hashed is a multiple of n, i.e. messages have been padded appropriately prior to hashing. Then the input to an iterated hash function is a message M consisting of L blocks P₁,P₂,…,P_L, each of length n. An algorithmic description of an n-bit iterated hash function is given as follows (as usual. “k” denotes concatenation of strings).

Algorithm ItHash

Input: A message M = P₁kP₂k···kP_L

Output: An n-bit hash of M

1: Initialize H := 0ⁿ (n zeros)

2: for i = 1 to L do

3:            H := f(H,P_i)

4: end for

5: Output H

The following attacks show that the two “obvious” designs for using an iterated hash function as the basis for a MAC — prepending or appending the key to the message and then hashing — are not computation resistant. These attacks were informally discussed in class by Randy on March 4; in this question, you are asked to present a formal argument for the defeat of computation resistance. For simplicity, assume that keys also have length^[1] n.

• (5 marks) Define a message authentication function PHMAC (“Prepend Hash MAC”) via PHMAC_K(M) := ItHash(KkM) = ItHash(KkP₁kP₂k···kP_L)

for any message M = P₁kP₂k···kP_L.

Suppose an attacker knows a message/PHMAC pair (M₁,PHMAC_K(M₁)).             Let X be an arbitrary n-bit block and put M₂ = M₁kX.            Show how an attacker can compute PHMAC_K(M₂) without knowledge of K, thereby defeating computation resistance for PHMAC.

Hint: Suppose M₁ consists of L blocks. Tracing through the ItHash algorithm, compare the outputs of the first L + 1 rounds of PHMAC_K(M₁) and PHMAC_K(M₂).

• (8 marks) Define a message authentication function AHMAC_K (“Append Hash MAC”) via

AHMAC_K(M) := ItHash(MkK) = ItHash(P₁kP₂k···kP_LkK)

for any message M = P₁kP₂k···kP_L.

Assume that ItHash is not weakly collision resistant, and suppose an attacker knows a message/AHMAC pair (M₁,AHMAC_K(M₁)). Show how she can find (without knowledge of K) a second message/AHMAC pair (M₂,AHMAC_K(M₂)), thereby defeating computation resistance.

Hint: Note that on input any L-bit message, the first L rounds of the computation of AHMAC_K(M) do not depend on K, just on M.

Problem 2 — Fast RSA decryption using Chinese remaindering, 8 marks)

In this problem, as usual, a user Alice has an RSA public key (e,n) with corresponding private key d. Here, n = pq for distinct large primes p and q.

If Alice does not discard p and q after computing n and φ(n), she can employ an alternative decryption procedure as described below (based on the Chinese Remainder Theorem which some of you may have seen before). For a given ciphertext C (1 ≤ C ≤ n − 1,gcd(C,n) = 1), she proceeds as follows:

Step 1. Compute

dp	≡	d (mod p − 1),	0 ≤ dp ≤ p − 2 ,
dq Step 2. Compute	≡	d (mod q − 1),	0 ≤ dq ≤ q − 2.
Mp	≡	Cdp (mod p),	1 ≤ Mp ≤ p − 1 ,
Mq	≡	Cdq (mod q),	1 ≤ Mq ≤ q − 1 .

Step 3. Use the Extended Euclidean Algorithm to find integers x, y such that

px + qy = 1 .

(Such integers exist because gcd(p,q) = 1.)

Step 4. Set M ≡ pxM_q + qyM_p (mod n), 0 ≤ M ≤ n − 1.

Prove that if the above procedure decrypts correctly. That is, if C ≡ M^e (mod n) is a ciphertext obtained by encrypting a message M the “normal” RSA way, and M⁰ is the result of applying the procedure above to C, prove that M⁰ = M.

Remark: It can be shown that this method is generally twice as fast as ordinary RSA decryption since it performs arithmetic with respect to moduli of half-size. So this is what is generally used in practice.

Problem 3 — RSA primes too close together, 18 marks)

This problem explores a difference of squares approach to factoring an RSA modulus due to Fermat, and hence also known as Fermat factorization. Fermat’s idea was to attempt to find a representation of an integer n as a difference of squares n = x² −y² where 0 < y < x < n, which would lead to a factorization n = (x+y)(x−y). Of course if x+y = n and x−y = 1, then this doesn’t help. But if n = pq is an RSA modulus for example, the hope is that

x + y = p ,              x − y = q

or vice versa; in which case

 .

When p and q are close together, the quantity y is very small compared to x and we will see that this represents a serious attack on RSA.

Let n = pq with odd primes p, q, and assume without loss of generality that p > q (so y > 0). In

√

this problem, all square roots are assumed to be positive, i.e. when we write z for some z > 0, we mean the positive square root of z.

√

• (3 marks) Prove that p > x > n.
• (8 marks) Consider the following algorithm:

Algorithm Fermat Factorization Input: n = pq with p > q

Output: q

1: Putrounded up to the nearest integer)

2: b :=        a² − n

3: while b is not an integer do√

4:           a := a + 1; b :=         a² − n

5: end while 6: Output a − b.

Prove that this algorithm terminates when a = x and outputs q. Note that there are three items to show here:

• The “while” clause is satisfied when a = x;
• The algorithm does not terminate sooner, i.e. it does not terminate for any value a < x;
• When the algorithm terminates with a = x, it outputs q.

√

• (2 marks) Show that the number of loop iterations executed by the algorithm is x−d ne+1.
• (3 marks) Prove that.

√            √

(Hint: Consider (x −        n)(x +      n).)

√

• (2 marks) Finally, the coup-de-grˆace. Suppose p − q < 2B ⁴ n for some integer B that is very small compared to n; e.g. B could be on the order of a power of log₂(n). In other words, p and q are very close together; they agree in nearly half of their most significant bits. Prove that the above algorithm factors n after at most

loop iterations.

Problem 4 – The El Gamal public key cryptosystem is not semantically secure, 12 marks

This problems requires typesetting Legendre symbols. To facilitate this, include at the beginning of your assignment file, right after the line \documentclass{assignment} the two lines

\usepackage{amsmath}

\providecommand{\Leg}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Be sure that you copy these verbatim; the easiest is to copy and paste them right from this PDF file. The assignment template provided on the course website already includes these lines. The command $\Leg{a}{n}$ will produce the typeset output , which is much easier than producing a fraction with large parentheses around it.

Recall that for the El Gamal public key cryptosystem, a user Alice produces her public and private keys as follows:

Step 1. Selects a large prime p and a primitive root g of p.

Step 2. Randomly selects x such that 0 < x < p − 1 and computes y ≡ g^x (mod p).

Alice’s public key: {p,g,y}

Alice’s private key: {x}

To encrypt a message  intended for Alice, Bob selects a random integer k ∈ Zp₋₁, computes C₁ ≡ g^k (mod p) and C₂ ≡ My^k (mod p), and sends C = (C₁,C₂) to Alice. Alice decrypts the ciphertext C = (C₁,C₂) by computing

In this problem, you will prove that the El Gamal PKC is not polynomially secure, and hence not semantically secure. This is because an attacker Mallory can distinguish messages according to whether they are quadratic residues or quadratic nonresidues modulo p.

Mallory mounts her attack with the following procedure:

Step 1. Selects two messages M₁ and M₂ such that M₁ ∈ QR_p and M₂ ∈ QN_p, and obtains ciphertext C = (C₁,C₂) = E(M_i) where i = 1 or 2

(Mallory’s task is precisely to ascertain whether i = 1 or i = 2).

Step 2. Computes the Legendre symbols  and .

Step 3. If     = 1 and         = 1, she asserts that C = E(M₁).

If    = 1 and         1, she asserts that C = E(M₂).

If    = 1 and         = 1, she asserts that C = E(M₁).

If    = 1 and        1, she asserts that = E(M₂).

If    1 and        = 1, she asserts that C = E(M₂).

If    1 and        1, she asserts that C = E(M₁).

Note that this procedure requires three Legendre symbol computations — which can be done with modular exponentiation by Euler’s Criterion — and hence always takes polynomial time. Note also that Mallory states her assertions with certainty, i.e. probability 1.

Prove that Mallory’s assertions are correct, so the El Gamal system is not semantically secure.

Problem 5 — An IND-CPA, but not IND-CCA secure version of RSA, 12 marks Consider the following semantically secure variant of the RSA public key cryptosystem:

Parameters:

• m — length of plaintext messages to encrypt (in bits)
• (n,e) — Alice’s RSA public key (n has k bits)
• d — Alice’s RSA private key
• H : {0,1}^k 7→ {0,1}^m a public random function Encryption of an m-bit message M:

Step 1. Generate a random k-bit number r < n.

Step 2. Compute C = (skt) where s ≡ r^e (mod n) and t = H(r) ⊕ M.

Decryption of ciphertext C:

Compute M ≡ H(s^d (mod n)) ⊕ t.

Prove that this cryptosystem is not IND-CCA secure.

Hint: To mount her CCA, Mallory gets to choose two plaintexts and submit one ciphertext for encryption. Almost any two plaintexts M₁, M₂ will do. Let

C = (skt) = (r^e (mod n) k H(r) ⊕ M_i)            where i = 1 or 2

be the encryption of one them; Mallory needs to ascertain whether i = 1 or i = 2. Mallory now chooses as her ciphertext C⁰ = (skt⊕M₁) and obtains its decryption (be sure to chose M₁ such that C⁰ 6= C; that’s the only restriction on the plaintexts). Prove that Mallory can with certainty (i.e. probability 1) and in polynomial time detect whether C is an encryption of M₁ or M₂.

Written Problems   lores an attack on RSA with small d due to Wiener.

Preliminaries. Let r be a positive rational number and write r = a/b with a,b ∈ N. Let q₀,q₁,…q_m ∈ N be the sequence of quotients produced by applying the Euclidean Algorithm to the numerator and denominator of r:

a  = q₀b + r₀ ,           0 < r₀ < b, b         = q₁r₀ + r₁ ,          0 < r₁ < r₀ , r₀ = q₂r₁ + r₂ ,          0 < r₂ < r₁ ,

…

rm−3     = qm−1rm−2 + rm−1 ,           rm−1 = gcd(a,b), rm−2          = qmrm−1 + rm ,   rm = 0.

Recall the familiar sequences

A−₂               =             0,            A−₁              =             1,            A_i                   =             q_iA_i−₁ + A_i−₂              for 0 ≤ i ≤ m, B−₂                        =             1,            B−₁              =             0,            B_i                   =             q_iB_i−₁ + B_i−₂ for 0 ≤ i ≤ m.

The quotients A_i/B_i (0 ≤ i ≤ m) are called the convergents of r because they oscillate around and converge toward r, with A_m = a, B_m = b, and hence A_m/B_m = r. In fact, the following theorem (which you may use without proof) asserts that any rational number sufficiently close to r must occur as one of the convergents:

Now back to RSA. Let n = pq where p,q are odd primes satisfying q < p < 2q (these inequalities are reasonable as p and q are usually assumed to have the same bit size). Let e,d be integers with 1 < e,d < φ(n) and ed ≡ 1 (mod φ(n)). Let k ∈ Z satisfy ed = 1 + kφ(n) and suppose that d is small compared to n; specifically,

.

• (5 marks) Prove that 1 ≤ k < d and gcd(d,k) = 1.

√

• (3 marks) Prove that 2 ≤ n − φ(n) < 3 n.

√

• (4 marks) Use parts (a) and (b) to prove that 0 < kn − ed < 3d n.
• (4 marks) Conclude from part (c) that 0 .
• (3 marks) Let q₀,q₁,…,q_m be the quotients obtained when applying the Euclidean algorithm to e and n, and let A_i,B_i be the associated sequences as defined above. Use the theorem from above to prove that k = A_i and d = B_i for some i ∈ {1,2,…,m}.

(Note that i = 0 is impossible here even though the theorem allows it in principle. This is because e < n forces q₀ = 0, so A₀ = 0 and B₀ = 1. Since k > 0 by part (a), we cannot have k/d = A₀/B₀.)

• (6 marks) Use part (e) to devise a procedure for finding d and factoring n Explain why your procedure works and why it is efficient, i.e. argue that the number of computation steps performed by your procedure is small.

Problem 7 — Universal forgery attack on the El Gamal signature scheme, 12 marks)

Recall that for the El Gamal signature scheme, a user Alice produces her public and private keys as follows:

Step 1. Selects a large prime p and a primitive root g of p.

Step 2. Randomly selects x such that 0 < x < p − 1 and computes y ≡ g^x (mod p).

Alice’s public key: {p,g,y}

Alice’s private key: {x}

Alice also fixes a public cryptographic hash function H : {0,1}^∗ 7→ Zp₋₁.

Alice signs a message M ∈ {0,1}^∗ intended for Bob as follows:

Step 1. Selects a random integer.

Step 2. Computes r ≡ g^k (mod p), 0 ≤ r < p.

Step 3. Solves.

Step 4. Signs the message M with the pair (r,s).

Bob verifies Alice’s signature (r,s) to the message M as follows:

Step 1. Obtains Alice’s authentic public key {p,g,y}.

Step 2. Verifies that 1 ≤ r < p; if not, reject.

Step 3. Computes v₁ ≡ y^rr^s (mod p) and v₂ ≡ g^H(Mkr) (mod p).

Step 4. Accepts the signature if and only if v₁ = v₂.

The following is a universal forgery attack against a variant of this scheme that hashes only the message M, but does not include the random number r in the argument of the hash function in step 3 of the signature generation. More specifically, the second component of a signature is generated as a solution k to

ks ≡ H(M) − xr (mod p − 1) ,

and a signature (r,s) to a message M is accepted if and only if

yrrs ≡ gH(M) (mod p) .

Suppose Eve has intercepted a signature (r,s) to a message M generated by Alice, such that gcd(H(M),p − 1) = 1. Eve proceeds as follows:

Step 1. Chooses any M⁰ ∈ {0,1}^∗.

Step 2. Computes H(M) and H(M⁰).

Step 3. Solves H(M)u ≡ H(M⁰) (mod p − 1) for u via the Extended Euclidean

Algorithm.

Step 4. Computes S ≡ su (mod p − 1).

Step 5. Computes R ≡ rup − r(p − 1) (mod p(p − 1)).

• (4 marks) Prove that R ≡ ru (mod p − 1), and conclude that y^R ≡ y^ru (mod p).
• (4 marks) Prove that R^S ≡ r^su (mod p).
• (4 marks) Prove that (R,S) is a valid signature to the message M⁰. In other words, given r,s and M, Eve can generate a a valid signature (R,S) to any message M⁰ that will be accepted as coming from Alice.

Remark: The quantity R will almost certainly exceed p, so this attack can be foiled if a verifier checks that r < p and rejects signatures for which r exceeds p. A better fix is to include r in the argument of the hash function as presented in class (Pointcheval 1996).

Programming Problem

Problem 8 — Secure file transfer with prior key agreement, 37 marks

Don’t be daunted by the long description of this problem! Most of it is very clear specifications, including those for the autograder, to make your life easier.

Overview. Transport Layer Security (TLS) is a security protocol which aims to provide endto-end communication security over networks. It provides both privacy and data integrity. While TLS has many steps, our focus will be on the cipher suite, a set of algorithms that add cryptographic security to a network connection. There are typically four components to a cipher suite:

• Key Exchange Algorithm
• Authentication algorithm (signature)
• Bulk Encryption Algorithm (block cipher and mode of operation)
• Message Authentication Algorithm

Cipher suites are specified in shorthand by a string such as

 

• This implies SRP-SHA3-256 as the key exchange algorithm, RSA signatures for authentication, AES-256-CBC for encryption and SHA3-256 as the MAC (used as HMAC).
• SRP is the protocol implemented in Assignment 2. Please replace the former hash algorithm SHA-256 with SHA3-256 (see cryptography library).
• Using SHA3-256 as the MAC implies the use of HMAC with SHA3-256 (see cryptography library).

In a TLS handshake, upon connection two parties automatically negotiate TLS settings, including the cipher suite to use. Through an exchange of messages the two parties verify each other and establish a session key. In this assignment, the two parties will be a server and client. The server will authenticate itself to the client by means of a certificate, and if successful, will derive a shared session key. The two parties are then able to use the session key to exchange encrypted and authenticated messages.

In reality, a certificate is an electronic document which contains a public key and information about the owner of the key. The certificate must be signed by a trusted authority to verify the contents of the certificate. For us, the certificate will merely be a name concatenated with a public key, concatenated with the signature of a trusted third party (TTP).