Hashing of short fixed length messages
in [Cryptography]
|
From: Paul Rubin on 16 Jun 2010 16:44 Kristian Gjøsteen <kristiag+news(a)math.ntnu.no> writes: > I don't know if MD5 and SHA-1 were designed to look like "random > functions", but I think AES was designed to look like an ideal cipher. One > consequence is that aes(k,.) should look like a random permutation. OK, that's reasonable. Rijndael was designed as an ideal cipher, though that was not part of the AES criteria, and it turns out (IIRC) that some distinguishers involving related keys have been found, maybe not a serious issue for this purpose. Still though, it means relying on a specific characteristic of AES/Rijndael, which might not hold for some other block cipher with similar parameters that is still a perfectly good PRP.
From: Francois Grieu on 16 Jun 2010 18:08 On 16/06/2010 20:11, Paul Rubin wrote: > Kristian Gjøsteen<kristiag+news(a)math.ntnu.no> writes: >> The same holds for hash functions as well, so this is not an objection >> against random oracle arguments. >> >> The idea is that the adversary doesn't really care about the internals >> of the function, and the function should be a typical example of a >> "random function" (or "random permutation"). >> >> Once you believe that about aes(k,.), the argument should be plausible. > > But, hash functions are built for the express purpose of resisting what > amounts to a "known key attack", i.e. to substitute for random oracles. > There is some experience indicating that it's harder to do that than to > design a block cipher. Look how well even DES has held up, compared > with MD4, MD5, SHA0, SHA1, etc. > > Consider a hypothetical "BES" which is simply AES(k,x) - x. Then x + > BES(k,X) is equal to AES(k,x) which is invertible if k is known. The > structure of BES actually matters, i.e., in the case of BES, the random > oracle hypothesis is invalid. Why should we expect it to be valid for > AES, which never promised to be anything but a PRP? There are different, increasingly complex random oracle models for 1) hash function 2) permutation 3) invertible permutation 4) keyed pseudo-random invertible permutation, aka keyed block cipher 1) The random oracle model for a randomly selected hash function - keeps a list of (input,output) pairs, initially empty - for each input, checks if there is a match for (input,?) in the list [there can be at most one] - if yes, return as output the right component of that pair of the list - else, generates a random output uniformly distributed over the output domain, adds (input,output) to the list, and return output. 2) The random oracle model for a randomly selected permutation over a set B - keeps a list of (input,output) pairs, initially empty - for each input, checks if there is a match for (input,?) in the list [there can be at most one] - if yes, return as output the right component of that pair of the list - else, generates a random output uniformly distributed over the subset of B obtained by removing all right components of pairs in the list [if any], adds (input,output) to the list, returns output. 3) The random oracle model for a randomly selected invertible permutation does as the previous one, and in addition offers a reverse function - for each input to that reverse function, checks if there is a match for (?,input) in the list [there can be at most one] - else, generates a random output uniformly distributed over the subset of B obtained by removing all left components of pairs in the list [if any], adds (output,input) to the list, returns output. 4) The random oracle model for a randomly selected keyed block cipher over a set B (for plaintext/ciphertext blocks) supports encryption and decryption functions; it - maintains a list of (key,plaintext,ciphertext) triplets, initially empty - for each input (key,plaintext) to the encryption function, checks if there is a match for (key,plaintext,?) in the list [there can be at most one] - if yes, returns as output the right component of that triplet of the list - else, generates a random output uniformly distributed over the subset of B obtained by removing all right components of triplets in the subset of the list that match (key,?,?) [if any], adds (key,plaintext,output) to the list, returns output. - for each input (key,ciphertext) to the decryption function, checks if there is a match for (key,?,ciphertext) in the list [there can be at most one] - if yes, returns as output the middle component of that triplet of the list [there can be at most one] - else, generates a random output uniformly distributed over the subset of B obtained by removing all middle components of triplets in the subset of the list that match (key,?,?) [if any], adds (key,output,ciphertext) to the list, returns output. A security proof in the random oracle model defines an opponent's goal (e.g. finding two colliding inputs of a hash), and computes a bound of the odds for reaching that goal after N queries of the approriate random oracle model, regardless of strategy, computing power and memory of the adversary. It turns out to be relatively easy in many cases. It is then accepted that an adversary has similarly bounded odds of success against an actual good cryptographic primitive if she spends a computational effort comparable to N evaluations of that cryptographic primitive. Theses models allow proofs that: x -> ENC(x,c) for a fixed c (known or not) is as good as a perfect hash function; it is clear that model 4) degenerates to model 1). x -> ENC(k,x)^x for a fixed k (known or not) is nearly as good: model 4) degenerates to model 2), and minimum N for a given odds of success for each of the standard attack goals [first preimage, second premimage, collision] can be computed and compared. For small odds, N is almost the same, and the difference is always less than a factor of 2. Francois Grieu
From: Francois Grieu on 17 Jun 2010 02:03 [reposted with corrections and extension, mostly after <@@@>] On 16/06/2010 20:11, Paul Rubin wrote: > Kristian Gjøsteen<kristiag+news(a)math.ntnu.no> writes: >> The same holds for hash functions as well, so this is not an objection >> against random oracle arguments. >> >> The idea is that the adversary doesn't really care about the internals >> of the function, and the function should be a typical example of a >> "random function" (or "random permutation"). >> >> Once you believe that about aes(k,.), the argument should be plausible. > > But, hash functions are built for the express purpose of resisting what > amounts to a "known key attack", i.e. to substitute for random oracles. > There is some experience indicating that it's harder to do that than to > design a block cipher. Look how well even DES has held up, compared > with MD4, MD5, SHA0, SHA1, etc. > > Consider a hypothetical "BES" which is simply AES(k,x) - x. Then x + > BES(k,X) is equal to AES(k,x) which is invertible if k is known. The > structure of BES actually matters, i.e., in the case of BES, the random > oracle hypothesis is invalid. Why should we expect it to be valid for > AES, which never promised to be anything but a PRP? There are different, increasingly complex random oracle models for #1 hash function #2 permutation #3 invertible permutation #4 keyed pseudo-random invertible permutation, aka keyed block cipher #1 The random oracle model for a randomly selected hash function - keeps a list of (input,output) pairs, initially empty - for each input, checks if there is a match for (input,?) in the list [there can be at most one] - if yes, return as output the right component of that pair of the list - else, generates a random output uniformly distributed over the output domain, adds (input,output) to the list, and return output. #2 The random oracle model for a randomly selected permutation over a set B - keeps a list of (input,output) pairs, initially empty - for each input, checks if there is a match for (input,?) in the list [there can be at most one] - if yes, return as output the right component of that pair of the list - else, generates a random output uniformly distributed over the subset of B obtained by removing all right components of pairs in the list [if any], adds (input,output) to the list, returns output. #3 The random oracle model for a randomly selected invertible permutation does as the previous one, and in addition offers a reverse function - for each input to that reverse function, checks if there is a match for (?,input) in the list [there can be at most one] - else, generates a random output uniformly distributed over the subset of B obtained by removing all left components of pairs in the list [if any], adds (output,input) to the list, returns output. #4 The random oracle model for a randomly selected keyed block cipher over a set B (for plaintext/ciphertext blocks) supports encryption and decryption functions; it - maintains a list of (key,plaintext,ciphertext) triplets, initially empty - for each input (key,plaintext) to the encryption function, checks if there is a match for (key,plaintext,?) in the list [there can be at most one] - if yes, returns as output the right component of that triplet of the list - else, generates a random output uniformly distributed over the subset of B obtained by removing all right components of triplets in the subset of the list that match (key,?,?) [if any], adds (key,plaintext,output) to the list, returns output. - for each input (key,ciphertext) to the decryption function, checks if there is a match for (key,?,ciphertext) in the list [there can be at most one] - if yes, returns as output the middle component of that triplet of the list - else, generates a random output uniformly distributed over the subset of B obtained by removing all middle components of triplets in the subset of the list that match (key,?,?) [if any], adds (key,output,ciphertext) to the list, returns output. A security proof in the random oracle model defines an opponent's goal (e.g. finding two colliding inputs of a hash), and computes a bound of the odds for reaching that goal after N queries of the approriate random oracle model, regardless of strategy, computing power and memory of the adversary. It turns out to be relatively easy in many cases. It is then accepted that an adversary has similarly bounded odds of success against an actual good cryptographic primitive if she spends a computational effort comparable to N evaluations of that cryptographic primitive. <@@@> Theses models allow proofs that: x -> ENC(x,c) for a fixed c (known or not) is as good as a perfect hash function. assuming ENC has model #4, x -> ENC(x,c) has model #1. x -> ENC(k,x)^x for a fixed k (known or not) is nearly as good. Assuming ENC has model #4, x -> ENC(x,c) has model #3 [the adversary can decipher], and minimum N for a given odds of success for each of the standard attack goals [first preimage, second premimage, collision] against x -> ENC(k,x)^x can be computed and compared. My intuition is that for small odds, N is almost the same, and the difference is always less than a factor of 2, but I can't remember if/where I read that. AES is rightly modeled by #4 for an adversary with credible computing power as far as I know (related key attacks on AES192 and AES256 seem impractical). DES or 3DES is not at all correctly modeled by #4 due to the complementation property and weak keys. With known constant key, x -> AES(k,x) is for all practical purpose rightly modeled by #3 as far as we know; x -> DES(k,x) is about rightly modeled for adversary with moderate power; and x -> 3DES(k,x) extends that required power (I know no attack working with less than 2^64-1 queries; the -1 is there because 3DES makes an even permutation of the message space). Francois Grieu
From: Paul Rubin on 21 Jun 2010 21:56 Francois Grieu <fgrieu(a)gmail.com> writes: > There are different, increasingly complex random oracle models ... > #4 The random oracle model for a randomly selected keyed block cipher > over a set B (for plaintext/ciphertext blocks) supports encryption and > decryption functions; it > - maintains a list of (key,plaintext,ciphertext) triplets, initially > empty... > <@@@> Theses models allow proofs that: > x -> ENC(x,c) for a fixed c (known or not) is as good as a perfect > hash function. > assuming ENC has model #4, x -> ENC(x,c) has model #1. Maybe I'm missing something but I'm still not convinced by the above. Think of AES(k,x) as a circuit mapping 256 input bits (128 plaintext bits and 128 key bits) to 128 ciphertext bits. Also suppose that AES is an ideal cipher. Imagine two arbitrary subsets P1, P2 of the plaintext bits and an arbitrary subset Q1 of the ciphertext bits. Since there are 2^128 subsets of the each 128-bit value, there are 2^384 possible choices of (P1,P2,Q1). Suppose k is a fixed, unknown key. Consider the proposition that there is some differential characteristic on P1, P2, and Q1, e.g. that the ciphertext bits selected by Q1 in AES(k, plaintext) are detectably non-uniformly distributed if the bits in P1 and P2 have some property. This is not a break against AES because it takes O(2^384) operations to discover the characteristic, which is much more work than just finding k with a brute force known plaintext attack, and the characteristic only holds for that fixed k. So the characteristic existing is not inconsistent with AES being an ideal cipher. Still though, there might be a way to find the characteristic efficiently if k is known, despite AES being ideal if k is known. Also, there could be a different such findable characteristic for every k. Or if necessary, the characteristic could be even worse, with P1, P2, P3, P4, ..., Q1, Q2, Q3 ..., yet still easily detectable once known, thereby distinguishing AES(known k, plaintext) from a random oracle efficiently. I'd consider the above to be extremely unlikely, but I don't see an obvious disproof. Is there one?
From: Francois Grieu on 22 Jun 2010 04:29
On 22/06/2010 03:56, Paul Rubin wrote: > Francois Grieu <fgrieu(a)gmail.com> writes: >> There are different, increasingly complex random oracle models ... >> #4 The random oracle model for a randomly selected keyed block cipher >> over a set B (for plaintext/ciphertext blocks) supports encryption and >> decryption functions; it >> - maintains a list of (key,plaintext,ciphertext) triplets, initially >> empty... >> <@@@> Theses models allow proofs that: > >> x -> ENC(x,c) for a fixed c (known or not) is as good as a perfect >> hash function. >> assuming ENC has model #4, x -> ENC(x,c) has model #1. > > Maybe I'm missing something but I'm still not convinced by the above. To clarify: in the above ENC is assumed to be a block cipher accepting equally sized key (first argument) and plaintext (second argument), and indistinguishable from random oracle model #4. The assertion is that x -> ENC(x,c) for a fixed c yields a hash demonstrably indistinguishable from random oracle model #1. And that replacing ENC with AES yields a hash computationally unbreakable for one computationally unable to break AES (in a related-ked sense). > Think of AES(k,x) as a circuit mapping 256 input bits (128 plaintext > bits and 128 key bits) to 128 ciphertext bits. Also suppose that AES is > an ideal cipher. > > Imagine two arbitrary subsets P1, P2 of the plaintext bits and an > arbitrary subset Q1 of the ciphertext bits. Since there are 2^128 > subsets of the each 128-bit value, there are 2^384 possible choices of > (P1,P2,Q1). > > Suppose k is a fixed, unknown key. Consider the proposition that there > is some differential characteristic on P1, P2, and Q1, e.g. that the > ciphertext bits selected by Q1 in AES(k, plaintext) are detectably > non-uniformly distributed if the bits in P1 and P2 have some property. > This is not a break against AES because it takes O(2^384) operations to > discover the characteristic, which is much more work than just finding k > with a brute force known plaintext attack, and the characteristic only > holds for that fixed k. So the characteristic existing is not > inconsistent with AES being an ideal cipher. > > Still though, there might be a way to find the characteristic > efficiently if k is known, despite AES being ideal if k is known. I guess we should read "ideal if k is unknown". Agreed, for a definition of ideal cipher including computationally indistinguishable from a random oracle of model #4. > Also, > there could be a different such findable characteristic for every k. Agreed. > Or if necessary, the characteristic could be even worse, with P1, P2, > P3, P4, ..., Q1, Q2, Q3 ..., yet still easily detectable once known, > thereby distinguishing AES(known k, plaintext) from a random oracle > efficiently. I'm not sure that I understand this part, or how the result would contradict something previously stated. Indeed, x -> AES(known k, x) can be distinguished from a random oracle with high certainty, in a single query: submit (k,0) to the oracle, compare it to AES(k,0), declare that the oracle is AES if the two match; this has odds 2^-128 to wrongly conclude an oracle is AES, and none to conclude that AES is an oracle. For even lower odds of failure, make a second query. OTOH, x -> AES(unknown k, x) is computationally indistinguishable from a random oracle of model #2. A proof of a concrete cryptosystem under study [e.g. H(x): x->AES(x,c) for known c, or H(x): x->AES(k,x)^x for known k] in the random oracle model: 1) constructs an idealized cryptosystem where the concrete cryptographic primitive is replaced by a random oracle of the appropriate model [e.g. AES replaced with model #4] using the same key/data width. 2) rigorously prove that to break this idealized cryptosystem (e.g. find first preimage, find second preimage, or find collision) [sometime: with odds at least p], an adversary has to make on average at least n queries to the oracle, regardless of memory and computing power of the adversary. 3) infer that an adversary computationally unable to distinguish the concrete cryptographic primitive from a random oracle is in practice unable to break the concrete cryptosystem [with odds at least p if that's considered] with work less than n evaluations of the concrete cryptosystem or just O(n); I do not know for certain how rigorous that last step can be made, but still it is the hell of a conservative and convincing proof technique. Francois Grieu |