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 depends on specific propert
...
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 depends 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]
.png)
