CAS CS538: Cryptography. Spring 2023
March 3, 2023
Due: 10pm Thu March 9
Homework 5
Question 1 (0 points): Read the definitions below. Make sure you understand them: what they define, and why they are formulated as they are. If you don’t understand, ask your fellow students, post a question on Piazza, or, if all else fails, ask Jessica, Luowen, or Ran. (You can also do the above in the reverse order.)
First we formulate message authentication (MA) schemes. The definition concentrates on stateless schemes. A definition that considers also stateful schemes (i.e., schemes where the authentication algorithm updates its local state after the processing of each message) can be derived from the one here; however we will not be discussing such schemes in this class.
Definition 1 A triple of algorithms (Gen, Auth, V er) is a t-time existentially unforgeable message authentication scheme against chosen message attacks (t-EU-CMA), with respect to message domain M if:
Correctness: For any m ∈ M, and any λ ∈ N we have
Prob[k←$ Gen(1λ)τ←$ Auth(k,m): Ver(k,m,τ)=1]=1.
Unforgeability: There is a negligible function ν(λ) such that for any feasible , t-compliant adversary A = {Aλ}λ∈N and all large enough λ we have:
Prob[k←$ Gen(1λ); (m∗,τ∗)←$ AAuth(k,·),Ver(k,·,·) :Ver(k,m∗,τ∗)=1]<ν(λ) (1) λ
where a t-compliant adversary is one which makes at most t queries to Auth, and where m∗ is different than all of these t queries. (The number of queries to V er is not bounded.)
Strong MA schemes. An adversary Aλ is weakly t-compliant If it makes at most t queries to Auth, and either m∗ is different than all of the t queries made by Aλ, or else τ∗ is different than the tag provided to Aλ in response to the query m∗. If unforgeability holds even against weakly t-compliant adversaries then we say that the scheme is strongly t-EU-CMA.
No Verification Access MA schemes. If the unforgeability game is modified so that the adversary no longer has access to the verification oracle then the scheme is called t-NVA-EU-CMA.
If the scheme is t-EU-CMA (respectively, t-SEU-CMA, t-NVA-EU-CMA) for any t = poly(λ) then we say that the scheme is EU-CMA (respectively, SEU-CMA, NVA-EU-CMA).
Question 2 (30 points):
Let F = {Fλ}λ∈N be a PRF where Fλ : {0, 1}λ × {0, 1}λ → {0, 1}λ. Recall the Feistel ladder defined in class: for k1 ...kl,x0,x01 ∈ {0,1}λ, define
L1λ(k1, (x0, x01)) = (x10, x1) where x10 = x01, x1 = x0 ⊕ Fλ(k1, x01)) ...
Ll(k,(xl−1,xl−1))=(xl,xl)wherexl =xl−1, xl =xl−1⊕F (k,xl−1)). λl01010110λl1
1. (10 points) Show that for any l and λ, and any k1 ...kl ∈ ({0,1}λ)l, the function Llλ((k1 ...kl),·) is a permutation on {0,1}2λ. In particular, write the formula for computing the inverse permutation, Llλ((k1 . . . kl), ·)−1
2. (10 points) Let Ll = {Llλ}λ∈N. Show that L2 is not a PRP. (Hint: As discussed in class, try to find two inputs x,x′ that are related in such a way that y = L2(x) and y′ = L2(x′) would be related in a way that is specific to the Feistel structure and would not occur with a random function.)
3. (10 points) Show that L3 is not an SPRP. (Hint: Can use a similar approach, where in addition the inverse permutation is queried on points derived from y,y′.)
Programming Help
Question 3 (40 points):
Let P = {Pλ}λ∈N be a PRP where Pλ : {0, 1}λ × {0, 1}λ → {0, 1}λ. The cipher block chaining message authentication (CBC-MAC) scheme proceeds as follows, where k ←$ {0, 1}λ and m = m1 . . . mt ∈ {0, 1}λt is the
Auth(k,(m1,…,mt))=ct, whereci =F(k,mi⊕ci−1),c0 =0
V er(k, (m1 . . . mt), c) = 1 if c = ct, ci = F (k, mi ⊕ ci−1), c0 = 0.
1. (25 points) Show that CBC-MAC is a strongly EU-CMA message authentication scheme for the message space M = {0,1}λt.
2. (15 points) Propose a way to encode the message m so that applying CBC-MAC to the encoded message results in a strong EU-CMA scheme for M = {0, 1}∗ .
Question 4 (50 points): A family of functions H = {hk : {0,1}n → {0,1}l}k∈{0,1}a is called strongly pairwise independent if for any α ̸= β ∈ {0,1}n,γ,δ ∈ {0,1}l we have: Prob[k ← {0,1}a : hk(α) = γ & hk(β) = δ] = 1/22l.
(That is, the probability that a random function in the family maps two distinct points in the domain to two given points in the range is exactly the same as if hk were a truly random function from {0,1}n to {0,1}l.) As with the case of pairwise independent hash functions (defined in Homework 4), there are many constructions of strongly pairwise independent functions families.1
1. (10 points) Show that the family {hA,b(x) = Ax+b}A∈Al×n,b∈A1,l is a strongly pairwise independent hash function family. (As in Homework 4, An×l is the set of n by l binary matrices, and the arithmetic is done in GF2.)
2. (10 points) Let H = {hk : {0,1}n → {0,1}l}k∈{0,1}a be a strongly pairwise independent hash function family. Consider the following (non-asymptotic) message authentication scheme with key length a, message lengthnandtaglengthl: Auth(k,m)=hk(m),Ver(k,m,τ)=1iffhk(m)=τ.
Show that this scheme is a perfect one-time MAC, namely that it is a 1-EU-CMA authentication scheme against a computationally unbounded adversary, with success probability 1 .
3. (15 points) Construct a message authentication scheme that’s 2-EU-CMA secure against a computationally
unbounded adversary, with success probability 1 . 2l
4. (20 points) Given any t > 2, construct a message authentication scheme that’s t-EU-CMA secure against a computationally unbounded adversary. How small can you get the key to be, as a function of t, n, l?
Question 5 (25 points): Let F = {Fλ}λ∈N be a PRF where Fλ : {0, 1}λ × {0, 1}n → {0, 1}l. Consider the following MAC scheme for message domain {0,1}n: Gen(1λ) outputs a random λ bit key k, Auth(k,m) = (0,F(k,m)), and Ver(k,m,τ) proceeds as follows: if τ = (0,τ′) and τ′ = F(k,m) accept. Else if τ = (1,i,b,τ′), where i ∈ 1…λ and b ∈ {0,1}, then accept if τ′ = F(k,m) and ki = b. Else reject.
1. [10 points] Show that the above scheme is not EU-CMA secure.
2. [10 points] Show that the above scheme is still NVA-EU-CMA.
3. [15 points] The above example stands in contrast to the first problem in this week’s discussion. Show where the proof in the discussion solution fails and how the proof can can be made to go through as long as the message authentication scheme is strongly EU-CMA. (That is, show that if a message authentication scheme is strongly NVA-EU-CMA then it is also strongly EU-CMA.)
1We note that the property that we call ”strongly pairwise independent” is often called just ”pairwise independent” in the literature, and the property that we called ”pairwise independent” in Homework 4 is often called ” universal” in the literature.
程序代写 CS代考 加QQ: 749389476