BU CAS CS 538.
Discussion 5 Solution
Definition 1. A triple of algorithms (𝐺𝑒𝑛, 𝐴𝑢𝑡, 𝑉 𝑒𝑟) is a 𝑡-time existentially unforgeable message authentication scheme against chosen message attacks (𝑡-EU-CMA), with respect to message domain 𝑀 if:
Correctness: For any 𝑚 ∈ 𝑀, and any 𝜆 ∈ 𝐍 we have
Copyright By PowCoder代写 加微信 powcoder
Pr[𝑘←$ 𝐺𝑒𝑛(1𝜆)𝜏←$ 𝐴𝑢𝑡(𝑘,𝑚): 𝑉𝑒𝑟(𝑘,𝑚,𝜏)=1]=1.
Unforgeability: There is a negligible function 𝜈(𝜆) such that for any feasible, 𝑡-compliant adversary 𝒜 = {𝐴𝜆}𝜆∈𝐍 and all large enough 𝜆 we have:
Pr[𝑘←$ 𝐺𝑒𝑛(1𝜆); (𝑚*,𝜏*)←$ 𝐴𝐴𝑢𝑡(𝑘,·),𝑉𝑒𝑟(𝑘,·,·) :𝑉𝑒𝑟(𝑘,𝑚*,𝜏*)=1]<𝜈(𝜆) (1) 𝜆
where a 𝑡-compliant adversary is one which makes at most 𝑡 queries to 𝐴𝑢𝑡, and where 𝑚* is different than all of these 𝑡 queries. (The number of queries to 𝑉 𝑒𝑟 is not bounded.)
Strong MA schemes. An adversary 𝐴𝜆 is weakly 𝑡-compliant If it makes at most 𝑡 queries to 𝐴𝑢𝑡, and either 𝑚* is different than all of the 𝑡 queries made by 𝐴𝜆, or else 𝜏* is different than the tag provided to 𝐴𝜆 in response to the query 𝑚*. If unforgeability holds even against weakly 𝑡-compliant adversaries then we say that the scheme is strongly 𝑡-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 𝑡-NVA-EU-CMA.
If the scheme is 𝑡-EU-CMA (respectively, 𝑡-SEU-CMA, 𝑡-NVA-EU-CMA) for any 𝑡 = 𝑝𝑜𝑙𝑦(𝜆) then we say that the scheme is EU-CMA (respectively, SEU-CMA, NVA-EU-CMA).
Problem 1. Prove that if MAC system (𝐺𝑒𝑛, 𝐴𝑢𝑡, 𝑉 𝑒𝑟) defined over (𝒦, M, 𝒯 ) is strongly t-NVA- EU-CMA, then it is also strongly t-EU-CMA. In other words, prove no feasible adversary 𝒜 = {𝐴𝜆}𝜆∈𝐍 will ever win the following game with non-negligible probability:
• The challenger picks 𝑘 ←$ 𝐺𝑒𝑛()
• 𝐴𝜆 queries the challenger with two types of queries
– Signing query: for 𝑖 = 1, 2, ..., 𝑡, the 𝑖th signing query consists of a message 𝑚𝑖 ∈ M. The challenger computes a tag 𝜏𝑖 ←$ 𝐴𝑢𝑡(𝑘,𝑚𝑖) and gives 𝜏𝑖 to 𝐴𝜆.
– Verification query: for 𝑗 = 1, 2, ..., the 𝑗th verification query consists of a message-tag pair (𝑚̂ ,𝜏̂)∈M×𝒯,andthechallengerrespondswith𝑟 =𝑉𝑒𝑟(𝑘,𝑚̂ ,𝜏̂).
• 𝐴 winsifforsome𝑗,𝑟 =1and(𝑚̂ ,𝜏̂)̸∈{𝑚,𝜏} . 𝜆 𝑗𝑗𝑗𝑖𝑖𝑖∈{𝑡}
Note that Definition 6.1 in Boneh & Shoup textbook is the same as t-NVA-EU-CMA in our Defi- nition 1.
Solution. The previous version of this Problem 1 contained a different statement where the message authentication scheme was not required to be strongly unforgeable. However, for such schemes, the
BU CAS CS 538. 2
above implication does not hold. Problem 5 in hw5 deal with this issue. In fact Problem 5.3 asks you to give a proof for this implication and a reason why the proof does not work when the scheme is not strongly unforgeable. A full solution will be given in the solution to hw5.
Problem 2. (MAC with short tags) Let I = (𝐺𝑒𝑛, 𝐴𝑢𝑡, 𝑉 𝑒𝑟) be a MAC defined over (𝒦, M, {0, 1}𝑙). Show that if 𝑙 is small (say, constant) then it is insecure even against a 0-query adversary.
Solution. Consider the adversary that simply outputs any message 𝑚 ∈ M and a random tag 𝜏 ∈ {0,1}𝑡. By the correctness of I, we know that for every key 𝑘 and every message 𝑚, there is at least one tag that would make 𝑉 𝑒𝑟 accept (in particular, it is the output of 𝑆(𝑘, 𝑚) for any fixed randomness). Therefore, the probability that the adversary wins the MAC attack game against I is Pr[𝑉 𝑒𝑟(𝑘, 𝑚, 𝜏 ) = 1] ≥ 1 , which is not negligible when 𝑙 is logarithmic in the security parameter.
Problem 3. (Domain extension) Let I = (𝐺𝑒𝑛, 𝐴𝑢𝑡, 𝑉 𝑒𝑟) be a secure MAC defined over (𝒦, M, 𝒯 ). We would like to attempt to construct a MAC with double the message space, i.e. M × M. Consider 𝐴𝑢𝑡′((𝑘1, 𝑘2), (𝑚1, 𝑚2)) = (𝐴𝑢𝑡(𝑘1, 𝑚1), 𝐴𝑢𝑡(𝑘2, 𝑚2)). Show that this is not a secure MAC.
Solution. Consider the following adversary:
• Pick 𝑚1 ̸= 𝑚2 to be any two distinct messages from M.
• Query (𝑚1, 𝑚1) and receive tag (𝜏11, 𝜏21) from the challenger. • Query (𝑚2, 𝑚2) and receive tag (𝜏21, 𝜏22) from the challenger. • Output (𝑚1, 𝑚2) and (𝜏11, 𝜏22).
Since 𝑚1 ̸= 𝑚2, the adversary always outputs a valid pair. Thus the advantage is
Pr[𝑉 𝑒𝑟′((𝑘1, 𝑘2), (𝑚1, 𝑚2), (𝜏11, 𝜏22)) = 1]
= Pr[𝑉 𝑒𝑟(𝑘1, 𝑚1, 𝜏11) = 1 ∧ 𝑉 𝑒𝑟(𝑘2, 𝑚2, 𝜏22) = 1] = 1,
by the correctness of I, this is not negligible.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com