Associative hash function
in [Cryptography]
|
Prev: If we could factor large numbers quickly, how exactly does everything break?
Next: HTTP and HTTPS sessions question
From: Francois Grieu on 15 Apr 2010 16:07 Le 15/04/2010 18:09, Maaartin a �crit : > On Apr 15, 5:26 pm, Francois Grieu<fgr...(a)gmail.com> wrote: >> On 15/04/2010 11:48, Maaartin wrote: >> > Is there any cryptographic associative hash function? I'd like to have >> > a collision-resistant function, where the input would be a sequence of >> > fixed-size blocks (of a couple of KB), which would allow to compute >> > the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) efficiently. >> > It should work by first computing the hashes of all blocks using a >> > standard hash function and combining the hashes using an associative >> > (and non-commutative) operation. >> >> A hash function H(a,b) = F(h(a),h(b)) with h any standard cryptographic >> hash function and F an associative function would most likely not be >> associative in the common definition: H(H(a,b),c)) = H(a,H(b,c)). > > Right. In order to compute H(x) you need to split the message x in > fixed-sized blocks first, i.e., with x = concat(x[0], x[1], x[2], ..., > x[N-1]) compute F(h(x[0]), F(x[1], F(x[2], ....))) or in infix > notation h(x[0]) op h(x[1]) op ... op h(x[N-1]). Currently, I don't > care about messages with a size being not a multiple of the blocksize. > > You may apply h only on arguments of the proper size. > >> What would be your definition of "cryptographic associative hash >> function" then ? Is it >> - H(a) is a cryptographic hash function >> - F is an associative function >> - we define H(a,b) = F(H(a),H(b)), then >> H(a,b,c) = F(H(a,b),H(c)) = F(H(a),H(b,c)) and so on > > Right, but only for a, b, and c consisting of a whole number of > blocks. > > Let H(a)=h(a) for length(a) = blocksize, and let H(concat(a, b)) = > F(H(a), H(b)) for any a, b with a length being a multiple of the > blocksize. This definition is consistent because of the associativity > of F. > >> - some security property holds. >> Which property ? > > I don't know what is achievable. I'd like to have collision- > resistance, if possible. > > Obviously, for a commutative F, collisions would be trivial, but I > want associativity and no commutativity. I throw this to see where it falls: F(u,v) = u*(v^^3) mod n where (n,3) is an RSA public key drawn by a trusted party with random prime factors p q of n discarded forever. H(a) = h(a) = (SHA-512(a)*k1) ^ k2 where: ^^ is power, ^ is exclusive OR, k1 is floor(n/(2^^513)), k2 is floor(n/3). Francois Grieu
From: Scott Fluhrer on 15 Apr 2010 16:23 "Francois Grieu" <fgrieu(a)gmail.com> wrote in message news:4bc77209$0$22392$426a74cc(a)news.free.fr... > Le 15/04/2010 18:09, Maaartin a �crit : >> On Apr 15, 5:26 pm, Francois Grieu<fgr...(a)gmail.com> wrote: >>> On 15/04/2010 11:48, Maaartin wrote: >>> > Is there any cryptographic associative hash function? I'd like to >>> have >>> > a collision-resistant function, where the input would be a sequence >>> of >>> > fixed-size blocks (of a couple of KB), which would allow to compute >>> > the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) >>> efficiently. >>> > It should work by first computing the hashes of all blocks using a >>> > standard hash function and combining the hashes using an >>> associative >>> > (and non-commutative) operation. >>> >>> A hash function H(a,b) = F(h(a),h(b)) with h any standard cryptographic >>> hash function and F an associative function would most likely not be >>> associative in the common definition: H(H(a,b),c)) = H(a,H(b,c)). >> >> Right. In order to compute H(x) you need to split the message x in >> fixed-sized blocks first, i.e., with x = concat(x[0], x[1], x[2], ..., >> x[N-1]) compute F(h(x[0]), F(x[1], F(x[2], ....))) or in infix >> notation h(x[0]) op h(x[1]) op ... op h(x[N-1]). Currently, I don't >> care about messages with a size being not a multiple of the blocksize. >> >> You may apply h only on arguments of the proper size. >> >>> What would be your definition of "cryptographic associative hash >>> function" then ? Is it >>> - H(a) is a cryptographic hash function >>> - F is an associative function >>> - we define H(a,b) = F(H(a),H(b)), then >>> H(a,b,c) = F(H(a,b),H(c)) = F(H(a),H(b,c)) and so on >> >> Right, but only for a, b, and c consisting of a whole number of >> blocks. >> >> Let H(a)=h(a) for length(a) = blocksize, and let H(concat(a, b)) = >> F(H(a), H(b)) for any a, b with a length being a multiple of the >> blocksize. This definition is consistent because of the associativity >> of F. >> >>> - some security property holds. >>> Which property ? >> >> I don't know what is achievable. I'd like to have collision- >> resistance, if possible. >> >> Obviously, for a commutative F, collisions would be trivial, but I >> want associativity and no commutativity. > > I throw this to see where it falls: > > F(u,v) = u*(v^^3) mod n where (n,3) is an RSA public key drawn by a > trusted party with random prime factors p q of n discarded forever. F is not associative. That is, F(F(u, v), w) = u * v^3 * w^3 F(u, F(v, w)) = u * v^3 * w^9 -- poncho
From: Francois Grieu on 15 Apr 2010 16:37 Le 15/04/2010 22:23, Scott Fluhrer a �crit : > "Francois Grieu"<fgrieu(a)gmail.com> wrote in message > news:4bc77209$0$22392$426a74cc(a)news.free.fr... >> Le 15/04/2010 18:09, Maaartin a �crit : >>> On Apr 15, 5:26 pm, Francois Grieu<fgr...(a)gmail.com> wrote: >>>> On 15/04/2010 11:48, Maaartin wrote: >>>> > Is there any cryptographic associative hash function? I'd like to >>>> have >>>> > a collision-resistant function, where the input would be a sequence >>>> of >>>> > fixed-size blocks (of a couple of KB), which would allow to compute >>>> > the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) >>>> efficiently. >>>> > It should work by first computing the hashes of all blocks using a >>>> > standard hash function and combining the hashes using an >>>> associative >>>> > (and non-commutative) operation. >>>> >>>> A hash function H(a,b) = F(h(a),h(b)) with h any standard cryptographic >>>> hash function and F an associative function would most likely not be >>>> associative in the common definition: H(H(a,b),c)) = H(a,H(b,c)). >>> >>> Right. In order to compute H(x) you need to split the message x in >>> fixed-sized blocks first, i.e., with x = concat(x[0], x[1], x[2], ..., >>> x[N-1]) compute F(h(x[0]), F(x[1], F(x[2], ....))) or in infix >>> notation h(x[0]) op h(x[1]) op ... op h(x[N-1]). Currently, I don't >>> care about messages with a size being not a multiple of the blocksize. >>> >>> You may apply h only on arguments of the proper size. >>> >>>> What would be your definition of "cryptographic associative hash >>>> function" then ? Is it >>>> - H(a) is a cryptographic hash function >>>> - F is an associative function >>>> - we define H(a,b) = F(H(a),H(b)), then >>>> H(a,b,c) = F(H(a,b),H(c)) = F(H(a),H(b,c)) and so on >>> >>> Right, but only for a, b, and c consisting of a whole number of >>> blocks. >>> >>> Let H(a)=h(a) for length(a) = blocksize, and let H(concat(a, b)) = >>> F(H(a), H(b)) for any a, b with a length being a multiple of the >>> blocksize. This definition is consistent because of the associativity >>> of F. >>> >>>> - some security property holds. >>>> Which property ? >>> >>> I don't know what is achievable. I'd like to have collision- >>> resistance, if possible. >>> >>> Obviously, for a commutative F, collisions would be trivial, but I >>> want associativity and no commutativity. >> >> I throw this to see where it falls: >> >> F(u,v) = u*(v^^3) mod n where (n,3) is an RSA public key drawn by a >> trusted party with random prime factors p q of n discarded forever. > > F is not associative. That is, > > F(F(u, v), w) = u * v^3 * w^3 > F(u, F(v, w)) = u * v^3 * w^9 > Ooops. Goto bed. Francois Grieu
From: Bryan on 15 Apr 2010 17:38 Maaartin asked: > Is there any cryptographic associative hash function? I'd like to have > a collision-resistant function, where the input would be a sequence of > fixed-size blocks (of a couple of KB), which would allow to compute > the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) efficiently. > It should work by first computing the hashes of all blocks using a > standard hash function and combining the hashes using an associative > (and non-commutative) operation. Basic answer: What you seem to be specifically looking for, we do not have. Perhaps you were overly specific as to method. Cryptographically, associative one-way functions are a public-key concept. Public-key primitives are vastly harder to realize than conventional crypto confusion/diffusion. Any AOWFs we find are likely to be shaped more like RSA than like SHA-256. > I've only found very theoretic papers on associative complexity- > theoretic one-way functions proving their existence iff P!=NP, which > didn't help me at all. Yeah, we get that a lot. Practical crypto lacks proof; theoretical crypto lacks practical application. Rabi and Sherman stated a neat theoretical result, but if they had a really cool candidate AOWF -- the way RSA looks to be a one-way trapdoor function -- they would have trumpeted it in the paper. Nevertheless, a good chunk of what you seem to want we can realize via clever application of conventional hashing and tree data structures. If you can better explain your problem, well, we love solving interesting problems. Heck, you've gotten great consulting already. I don't agree with everything Francois Grieu said here, but I sure recommend listening to him.
From: Maaartin on 15 Apr 2010 19:58 On Apr 15, 11:38 pm, Bryan <bryanjugglercryptograp...(a)yahoo.com> wrote: > Maaartin asked: > > > Is there any cryptographic associative hash function? I'd like to have > > a collision-resistant function, where the input would be a sequence of > > fixed-size blocks (of a couple of KB), which would allow to compute > > the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) efficiently. > > It should work by first computing the hashes of all blocks using a > > standard hash function and combining the hashes using an associative > > (and non-commutative) operation. > > Basic answer: What you seem to be specifically looking for, we do not > have. Perhaps you were overly specific as to method. Maybe I was, maybe tree hashing would do the job, and maybe I don't need it at all. I'll think about it, but I find the question very interesting. > Cryptographically, associative one-way functions are a public-key > concept. Public-key primitives are vastly harder to realize than > conventional crypto confusion/diffusion. Any AOWFs we find are likely > to be shaped more like RSA than like SHA-256. That's strange, I saw something like this in the paper and in the answer by Francois, but I see no reason why a SHA-like function couldn't do. In order to give a concrete example of how could it work or fail, I'd propose the following: Obviously, the function mustn't not be commutative, so what do we have? Matrix multiplication, permutation composition, quaternions, something else? So let F(a, b) be the matrix multiplication in GF(256), let h(x) = toRegularMatrix(SHA-512(x)), where toRegularMatrix arranges the 512 bits as a 8x8 matrix of bytes and avoids singular matrixes by adding the unity matrix until the result is regular. This really works and toRegularMatrix looses no more than 3 bits of information (you need to do the addition at most 7 times 'cause the characteristic polynomial at most 8 distinct roots). Can anybody find collisions or any relation (besides associativity) here? > > I've only found very theoretic papers on associative complexity- > > theoretic one-way functions proving their existence iff P!=NP, which > > didn't help me at all. > > Yeah, we get that a lot. Practical crypto lacks proof; theoretical > crypto lacks practical application. Rabi and Sherman stated a neat > theoretical result, but if they had a really cool candidate AOWF -- > the way RSA looks to be a one-way trapdoor function -- they would have > trumpeted it in the paper. Sure. > Nevertheless, a good chunk of what you seem to want we can realize via > clever application of conventional hashing and tree data structures. > If you can better explain your problem, well, we love solving > interesting problems. Heck, you've gotten great consulting already. I > don't agree with everything Francois Grieu said here, but I sure > recommend listening to him. Sure, I will.
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 4 5 Prev: If we could factor large numbers quickly, how exactly does everything break? Next: HTTP and HTTPS sessions question |