0368.4162: Introduction to Cryptography Ran Canetti Lecture 7
15 December 2008
Topics for Today
• Collision resistant functions
Copyright By PowCoder代写 加微信 powcoder
• Message Authentication Codes (MAC)
1 Collision Resistant Functions
Intuitively, a collision resistant function (CRF) f is a function for which it is hard to find two inputs s.t. their images collide: If x ̸= x′, then w.h.p. f(x) ̸= f(x′). It is easy to see that any one-to-one function satisfies this requirement. However, we are interested in functions that are many-to-one, specifically, functions that map long inputs to short inputs, i.e., |f(x)| < |x|.
One immediate use for CRFs would be to verify the integrity of a large database D. Instead of storing the entire data in a safe place, we could use a CRF function f : {0, 1}∗ → {0, 1}n and save only d ← f (D), which is relatively short. For any future suspicious version D′ of our database, we can now simply test d = f(D′) and see if the version was compromised.
1.1 Formalization
We start with a native attempt:
Definition. A function f is ε(t)-collision resistant (CR) if for any adversary A
running in time t:
Pr[A() = (x, x′ ) s.t. x ̸= x′ ∧ f (x) = f (x′ )] < ε(t)
Of course this definition is impossible to achieve: If f has any collision, say for inputs x and x′, we can always hard-wire them into A. The algorithm Ax,x′ is a fast algorithm that produces a collision for f.
Similarly to the definition of trapdoor permutation, we’ll use a formulation of family of functions.
Definition 1. A family of functions F = {fi : Di → Ri}i∈I is ε(t)-CR if there exist algorithms G, E such that G() → i ∈ I is an index generation algorithm and E(i, x ∈ Di) → fi(x), and for any adversary A running in time t:
Pr [A(i)=(x,x′)s.t.x̸=x′∧f(x)=f(x′)]<ε(t) i←G()
Scribes: R. Kasher, O. Paneth
Definition 2. (Asymptotic CRF) An ensemble F = {Fn}n∈N, Fn = {fin : Din → Rin}i∈In is CR if there exist algorithms G,E such that G(1n) → i ∈ I is an index generation algorithm and E(1n,i,x ∈ Din) → fi(x), and for every non-uniform polynomial adversary A:
Pr [A(1n,i)=(x,x′)s.t.x̸=x′∧f(x)=f(x′)]<ν(n) i←G(1n )
where ν(n) is a negligible function of n. Note:
• Unlike pseudorandom functions, we allow A to receive i as input, and still we require the hardness of finding collisions.
• If F is CRF and at least two-to-one, i.e. ∀x,i|f−1(x)| ≥ 2, then F is one- i
way when viewed as a function from I × D. Intuitively, if we can invert F, then for any x,i we can compute fi(x), find y ∈ f−1(x), and with
i probability ≥ 21 we have y ̸= x for which fi(y) = fi(x) is a collision.
• There exists two-to-one OWF which is not CR: For example, a OWF that ignores the last bit of its input.
• There is no known construction of a CRF from OWF. Further, we have evidence that this is a hard task. It was proven that no such construction can use the OWF as a black-box.
In fact, it is not even known that existence of TDPs implies existence of CRF.
We can construct CRF either directly or from known hard problems.
1.2 Construction of a CRF based on hardness of DLOG
We first introduce a new cryptographic primitive, claw free pairs of permuta- tions.
1.2.1 Claw Free Pairs of Permutations
Pairs of permutations p0,p1 are claw-free if it is hard to find a “claw” x0,x1 s.t. p0(x0) = p1(x1).
Definition3. (AsymptoticCFP)AnensembleP={P } ,P ={P0 ,P1 } , n n∈N n i,n i,n i∈In
pbi,n : Di → Di is claw-free if there exist algorithms G,E such that G(1n) → i ∈ I is an index generation algorithm and E(1n, i, b, x ∈ Din) → Pib(x), and for every non-uniform polynomial adversary A:
Pr [A(1n,i)=(x ,x )s.t. P0 (x )=P1 (x )]<ν(n) i←G(1n) 0 1 i,n 0 i,n 1
where ν(n) is a negligible function of n. 2
Figure 1: Constructing CRF from CFP
1.2.2 Construction of CFP from DLOG
Let2n−1 ≤p<2n beann-bitprime,gageneratorofZ∗p,andz̸=ganelement of Z∗p. There exists a randomized polynomial algorithm G(1n) → (p, g, z).
We define for b ∈ {0,1}, Ppb,g,z(x) = zb · gx(p). The evaluation algorithm E is defined accordingly. Note that zb is a constant, g is a generator, and so P0,P1 are permutations.
Finding a claw x0,x1 implies finding the discrete log of z:
gx0 =z0 ·gx0 =P0(x0)=P1(x1)=z1 ·gx1(p)
and so z = gx0−x1 (p).
Given an algorithm A that defeats the claw-freeness of P with probability ε, we can construct an algorithm A′ that produces x on inputs p, g, z s.t. gx = z(p) w.p. ε:
If g = z, A′ returns 1. Otherwise, runs A on the key (p,g,z) and receives (x0, x1). Returns gx0−x1 (p).
The above algorithms inverts DLOG with probability at least ε, since when g ̸= z then w.p. ε, (x0,x1) is a claw. Hence, finding a claw in P is at least as hard as DLOG.
1.2.3 Construction of CRF from CFP
Fix n. Let P = {Pi0,Pi1}i∈I, Pib : Di → Di be a family of claw-free pair of permutations, with index generator GP . We define a collision resistant family as follows (See figure 1):
• IndexgeneratorG→i,swherei←Gp ands←Di.
• F = {fi,s : {0, 1}∗ → Di}i∈I,s∈Di
• fi,s(x1,...,xm)=Pxm(Pxm−1(...(Px1(s))...)) iii
Claim. If P is CFP then F is CRF
Proof. Assume a polynomial algorithm A′ that finds collisions in F with prob- ability ≥ ε. We’ll build algorithm A to find a claw in Pi0, Pi1 w.p. 2ε :
We modify G slightly to return i,s′ = Pib(s) where s ← Di and b is a random bit. Since s is chosen uniformly at random and Pib is a permutation, then s′ is also random.
A runs A′ and obtains (x, x′). If fi,s′ (x) ̸= fi,s′ (x′), i.e. A′ failed to find a collision, abort. Else, A can find a claw as follows:
Assume w.l.o.g. that m = |x| ≥ |x′| = m′. We have:
P xm (P xm−1 (...(P x1 (s′ ))...)) = P x′m′ (P x′m′ −1 (...(P x′1 (s′ ))...)) iiiiii
Ifxm ̸=x′ ′,thenPxm(a)=Px′m′(a′)forsomea,a′ andwearedone. Otherwise, mii
since P b is a permutation, we apply (P xm )−1 on both sides of the equation, and ii
continue as above on xm−1 and x′m′−1. If x′ is not a suffix of x, then we will necessarily find a claw before “stripping” all Pi’s. If it is, then at the end of the process we have found:
P xm−m′ (...(P x1 (s′ )...) = s′ ii
Recall s′ = Pib (s), and with probability 12 , b ̸= xm−m′ , and we have a claw Pxm−m′ (...) = Pb(s).
In any case, the probability of finding a claw is at least 12 · PrA′ ,i,s′ [fi,s′ (x) =
fi,s′ (x′)] ≥ 2ε , which is non-negligible when ε is non-negligible. 1.3 Direct Constructions of CRF
There’s a number of direct constructions of collision resistant functions, often called “cryptographic hash functions”, and these are the predominantly used ones in actual systems today.
1.3.1 Merkle-Damg ̊ard Construction
Essentially all of the cryptographic hash functions have the following structure, often called the Merkle-Damg ̊ard construction:
The function H : {0, 1}∗ → {0, 1}k, k = 128, 160, 192, ...
The main element of H is a compression function h : {0, 1}k × {0, 1}l → {0, 1}k , where l is called the block-length and is typically 512 bits.
H works as follows: The input message m is partitioned into l-bit blocks, m1, m2, ...
C0 = IV is a fixed value, Ci = h(Ci−1 , mi ) is the chaining value
H outputs the last Ci value after all the message blocks were processed.
Notes on the construction:
• Finding a collision in H can be done with expected 2k/2 queries by the birthday paradox, even when we know nothing of its structure.
Figure 2: Merkle-Damg ̊ard chaining
Intuitively, the strength of H depends on the collision resistance of h, although we cannot apply our notion of CR here because H, h are specific functions. Even if we regard h as a family of functions with key Ci, the reduction won’t work.
A query on a prefix m1 , ..., mi reveals the chaining value Ci . This weakens the cryptographic hash. (Although it is not obvious how this information can be used to find collisions in h, cryptographic hash functions have many other interesting properties and uses, some of which will be discussed later.) To prevent this m can be padded with its length (and again padded to fill the last block).
Construction of Compression Functions
Using Block Ciphers
We can think of several ways to construct compression functions using block
• Feed the input block mi as input and the key Ci as key
• Reverse the order of the input and the key
• Perform a XOR of the key (or the input) with the output
We don’t have any concrete reason to prefer one model over the other. Historically, the main drawback of all these constructions was that the block size for DES, 64bit, was too small, making birthday attacks feasible. Since AES has a block size of 128bit, using AES as a basis for such a construction is not unreasonable and has been proposed more than once.
Dedicated Compression Functions
Commonly used hash functions:
• MD4, MD5 proposed by
• SHA-1, SHA-2 proposed by NIST and based on MD5 • The European standard RIPEMD
All have similar underlying structure. Following is a rough sketch of the com- pression function of MD5:
• The 512-bit input block is partitioned into 16 32-bit block m1, ..., m16
• The 128-bit chaining value C is partitioned into 4 32-bit blocks A0, ..., A3.
• There are four different functions F1 , ..., F4 , where each Fi takes 3 32-bit blocks as input and outputs one 32-bit block.
• There are 64 different 32-bit constants t1,...,t64 determined via an “ex- tremely non-linear” function, | sin(i) · 232 |.
• There are 4 different shift values s1, ..., s4.
• The computation:
for i = 1..4, j = 1..4, k = 0..3:
Ak ← Fi(Ak+1, Ak+2, Ak+3) ⊕ mj(k+1) ⊕ tij(k+1) ≪ sj
• There are 16 applications for each Fi where in each application a single block is updated as a function of the other 3 blocks.
• The functions Fi are chosen to be “balanced”, i.e., they roughly preserve →−
the number of 1s and 0s in the input, in order to prevent bias towards 0
or 1 after repeated applications.
There is not much understanding as to why any of these functions should work, and indeed eventually they break. Gaining more understanding on how to con- struct such functions is an interesting research challenge.
1.4 Cryptographic Hash Functions
We’ve mentioned several cryptographic hash functions, namely MD5, SHA-1, etc. These constructions are believed to have even stronger properties than collision resistance. In fact, these functions are believed to break any “non- trivial computational relation” (for example, finding the preimage of 0) between the inputs and the outputs.
This property leads to the use of cryptographic hash functions in many ap- plications, such as message authentication codes and digital signatures. It is standard to use trapdoor permutations over hash functions in digital signature schemes. The security of this construction is based on various properties of the hash such as non-homomorphism and difficulty to inverse. We will study these mechanisms in detail later.
Finding rigorous ways to formalize the properties needed for applications, and then to realize them based on known assumptions, is a central goal in cryptog- raphy, and an active area of research.
Cryptographic Schemes and
Up until now in the course we dealt with formalizing and constructing basic cryptographic primitives: OWF, PRG, PRF, PRP, TDP and CRF. These prim- itives provide essential abstractions from specific underlying hard problems. These problems will be our toolkit in building cryptographic schemes, protocols and applications.
This second part of the course will deal with the cryptographic tasks themselves. Treating these tasks consists of three main steps:
Understanding the security requirement for the task and finding a way to formalize these requirements in a way that matches our intuitive idea and makes mathematical sense.
Constructing a scheme.
Proving the scheme satisfies the definition based on the properties of the underlying tools (under hardness assumptions).
Message Authentication Codes (MAC)
The first task we will introduce is that of message authentication codes. Consider two parties A and B that wish to communicate over an open com- munication channel. This channel is untrusted: An adversary can inject, delete and modify messages at wish. The parties wish to be able to recognize when a received message is authentic, i.e., it was generated by the second party and not modified en route. To allow the parties to perform this task, we assume they have some shared random secret (key).
2.1 Formalization
A message authentication scheme consists of two interactive algorithms (ITM): auth in the sender side and ver in the receiver side, both initialized with the same shared (secret) key. Given a message m, auth(k, m) generates an encoded version e. Since no secrecy is required, we can assume w.l.o.g. e = (m, t) where t is called a “tag”. Given an encoded message e = (m, t), ver(k, m, t) outputs accept/reject.
We require consistency: ver must accept any message encoded by auth.
Further, we require security: Any message not encoded by auth should be re- jected by ver. This requirement, however, is not well defined since any encoded message can be potentially generated by an adversary. What we want is a def- inition that captures the notion of a “session” in the presence of an adversary that can interact with both parties, but still cannot correctly tag messages.
Definition. (First attempt) A scheme (auth, ver) is secure if for any polynomial adversary C, encoded messages (m1, t1), ..., (ml, tl) such that ti = auth(k, mi) where l = poly(n), and message m∗ ̸= mi∀i:
Pr [C(m1, t1, ..., ml, tl) = (m∗, t∗) s.t. ver(k, m∗, t∗) = acc] < ν(n) k∈{0,1}n
Note that an adversary C that produces a tag t∗ s.t. for some i, (mi,t∗) is verified even though t∗ ̸= ti, does not break the scheme. This is acceptable since we don’t mind the adversary repeating a legitimate message. Unfortunately, this definition fails to capture the essence of an interactive ad- versary, since the messages m1 , ..., ml are fixed in advance. Since an adversary might infer some security-relevant information from past messages and their tags, and craft his messages accordingly, we wish our definition to hold in this case as well. To this end, we introduce the notion of a game between auth/ver and our adversary.
Definition 4. MAC-GAME(auth, ver, C, n):
Initialize shared random key k ∈ {0, 1}n .
C(1n) interacts with sign and ver multiple times, queries authk(m) → (m,t) for any message m, and queries verk(m′,t′) for the validity of any pair m′,t′.
C wins if it produces any pair m∗,t∗ such that authk(m∗) was never queried yet verk(m∗,t∗) = accept.
We use the MAC-GAME to finally define a MAC scheme.
Definition 5. A MAC scheme is a pair of algorithms auth, ver, such that authk (m) → (m, t) is a tagging algorithm and verk (m, t) = {accept/reject} is a verification algorithm. The algorithms must satisfy:
Consistency: For every k, m we have: ver(k, auth(k, m)) = accept
Security: For any polynomial adversary C,
Pr [C wins MAC-GAME(auth, ver, C, n)] < ν(n)
k∈{0,1}n ,C
where ν(n) is a negligible function of n.
The above definition is a typical example of defining system security by the use of an experiment/interactive game. The game specifies the capabilities or types of interactions of an adversary, and the notion of success or what it means to “break” the security properties of the system.
2.2 Constructions
2.2.1 Secure MAC Scheme for a Single Message
We introduce a scheme that is secure for a single message against computation- ally unbounded adversaries. First, we need the following definitions:
Definition 6. A family of functions H = {hk : {0,1}n → {0,1}m}k∈{0,1}a is called pairwise independent (or, 2-universal)1 if for any α ̸= β ∈ {0,1}n, γ,δ ∈ {0,1}m:
Pr [hk(α)=γ∧hk(β)=δ]= 1 k←{0,1}a 22m
Note that immediately from the definition it also follows that for any α, γ (and some β ̸= α):
Pr[hk(α)=γ] = Pr[hk(α)=γ∧hk(β)=δ] kk
= 2m·2−2m=2−m
Definition 7. An ensemble H = {Hn}n∈N of families of functions is pairwise independent with and range m(n) and key range a(n) if for each n ∈ N the family Hn = {hk : {0, 1}n → {0, 1}m(n)}k∈{0,1}a(n) is pairwise independent.
There are many constructions of pairwise independent function families with short keys (polynomial in n), such as the one we’ve seen in Problem Set 2.
Let H = Hn be an ensemble of pairwise independent families. Consider the following scheme for n-bit messages:
Initialize random key k ∈ {0, 1}a(n). Define auth(k, m) = m, hk(m), ver(k, m, t) = I[t = hk(m)], where hk ∈ Hn.
Claim. The above scheme is secure for a single message.
Proof. Consistency is trivial.
Security follows directly from the definition of pairwise independence: An ad- versary C can query auth once for some α: (α,γ) ← authk(α). To win C needs to find a pair β,δ s.t. verk(β,δ) = accept. By the definition of auth, ver this implies:hk(α) = γ ∧ hk(β) = δ. Since k is chosen at random, the probability of this event is:
Pr[hk(β) = δ | hk(α) = γ] k
= Pr[hk(β) = δ ∧ hk(α) = γ]/ Pr[hk(α) = γ] kk
= 2−2m·2m=2−m
1Specifically, when γ = δ, this implies Pr a [h (α) = h (β)] = 1 . This corresponds
k←{0,1} k k 2m
to the definition we have seen in Exercise 2, which is weaker than the one given here.
2.2.2 Secure MAC Scheme for an Unbounded Number of Messages
Fix n, the message bit length. Let h be a random function from {0,1}∗ to
{0, 1}n , and define auth(h, m) = m, h(m), ver(h, m, t) = I[t = h(m)].
It is clear the probability that any adversary C wins a MAC-GAME is poly(n) , 2n
as for any m∗, t∗, Pr [h(m∗) = t∗] = 1 , independently of any previous queries
(̸= m∗) to h.
Unfortunately, such a scheme is not practical, since the representation of h (i.e., the key) is exponential in n. The next step would be to try a family of pseudorandom functions.
Let F = {fk : {0,1}∗ → {0,1}n}k∈{0,1}a(n) be a family of PRF. We define the following MAC scheme:
Initialize random key k ∈ {0, 1}a(n). Define auth(k, m) = m, fk(m), ver(k, m, t) = I[t = fk(m)]
Claim. The above scheme is a secure n-bit MAC scheme, assuming that the underlying function family is a PRF.
Proof. Consistency is trivial. Security: Assume towards contraction there exists a polynomial adversary C, s.t. C wins MAC-GAME(auth, ver, C, n) with non- negligible probability ε. We’ll use C to build a polynomial adversary C′ that distinguishes F from F∗,n w.p. ε:
C′ has access to oracle f. C′ simulates C. Every auth-query mi made by C is answered with mi,f(mi). A verify-query (m∗,t∗) is answered by I[f(m∗) = t∗]. C′ returns 1 if any verify-query is satisfied, that is, if C was able to produce a forgery.
Whenf∈F ,thenforanym∗,t∗wehave:Pr[C′f=1]=1.Whenf∈F, ∗,n f2n
then Prk[C′fk = 1] = Prk[C wins MAC-GAME] = ε
It follows immediately that F cannot be PRF, in contrary to the assumption.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com