*NURSING > QUESTIONS & ANSWERS > Simon Fraser UniversitySchool name CMPT 404 kawashimaru (All)

Simon Fraser UniversitySchool name CMPT 404 kawashimaru

Document Content and Description Below

CMPT 404 — Applied Cryptography Outline Solutions to Exercises on Message Authentication Schemes and CCA Security. 1. We talked about situations where security of the resulting construction depen... ds on specific properties of components (such as ciphers) being used. DES cipher has the following property: E(x, y) = ¬E(¬x, ¬y), where ¬z is z ⊕ 1 , a complement of z. Consider the following construction of a MAC. Let H0 = IV , and for every i > 0 Hi = Hi−1 ⊕ EP [i](Hi−1). Let the tag be (IV, Ek1 (H`)) where k1 is a separate key, and ` is the number of blocks in the message P. Show that with DES as a cipher this construction does not give message integrity. Given an initial value IV and a message P[1]P[2] . . . P[k] consider ¬IV and ¬P[1], P[2], . . . , P[k]. We have H0 0 = ¬IV = ¬H0 H0 1 = ¬IV ⊕ E¬P [1](H0 0 ) = ¬IV ⊕ E¬P [1](¬H0) = ¬IV ⊕ ¬EP [1](H0) = IV ⊕ EP [1](H0) = H1 H0 i = Hi−1 ⊕ EP [i](Hi−1) = Hi , for all i > 1. Thus, although the message is different, it generates the same tag. 2. Consider the following variant of CMA-security for MACs: instead of giving the adversary black boxes for both the signing and verification algorithms, give it only a black box for the signing algorithm. Let’s call this definition CMA’-security. That is, A pair of algorithms (Sign, Ver) (with Sign : {0, 1} n × {0, 1} m → {0, 1} t , Ver : {0, 1} n × {0, 1} m × {0, 1} t → {0, 1}) is a CMA’-secure MAC if for every x, k, Verk(x, Signk (x)) = 1 and for every efficient Adv, if we run the following experiment: • Choose k ←− {0, 1} n • Give adversary access to black box for Signk (·) • Adversary wins if it comes up with a pair hx 0 , s0 i such that (a) x 0 is not one of the messages that the adversary gave to the black box Signk (·) and (b) Verk(x 0 , s0 ) = 1. Then the probability Adv wins is negligible. A MAC scheme has unique tags if for every message there is only one tag that passes verification. An equivalent way of stating this property is that the verification algorithm on input x and t outputs 1 if and only if Sk(x) = t. Note that the MAC scheme we saw in class has this property. Prove that for MACs with unique tags, CMA security and CMA’ security are equivalent (e.g., such a scheme is CMA secure if and only if it is CMA’ secure. (The condition of unique tags is important — if a MAC scheme does not have unique tags then these notions may not be equivalent.) Since in the case of CMA-security an adversary is more powerful than for CMA’-security, every CMA-secure MAC is also CMA’-secure. So let (Sign, Ver) be a CMA’ secure MAC. Suppose that it is not CMA-secure, and Adv is an efficient adversary. We construct an efficient adversary Adv0 that does not get access to the verification box, and therefore yields a contradiction with CMA’-security of (Sign, Ver). Adv0 - choose k at random from {0, 1} - run Adv - whenever Adv asks to sign a message P return Signk (P) - whenever Adv asks to verify a pair (P, s), output 1 if s = Signk(P), otherwise output 0 - when Adv comes up with a pair (P, s), output this pair [Show More]

Last updated: 2 years ago

Preview 1 out of 3 pages

Buy Now

Instant download

We Accept: