Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Given a Cryptographic hash function $h$ for element $x$, let's extend it to sets via $H(S)=\prod_{x\in{S}}{h(x)}$. I am asking if the new hash $H$ (in domain of set) is still collision resistant?

To be more specific, is it the same difficult to compute $S$ for given $H(S)$, comparing to that of computing $x$ from given $h(x)$?

Also how hard it is to find another $S'$ so that $H(S')=H(S)$? Is it at the same level of difficulty comparing to finding another $x'$ s.t. $h(x)=h(x')$.

share|improve this question
    
yes, it is a product. but not necessarily on $N$, since I am using crypto hash and the hash value is generally treated as bits or binary string. –  Richard Jun 6 '13 at 21:38
2  
Richard, I think we need you to specify whether the product is in $\mathbb{N}$ (the integers) or in some other group. I understand you want to leave it unspecified, but the answer depends heavily upon whether this is over the integers or over some group (and if the latter, which group). –  D.W. Jun 6 '13 at 22:36
add comment

2 Answers 2

I'll assume that in $H(S)=\prod_{x\in{S}}{h(x)}$, the notation $\prod$ stands for the product of the integers represented by the bitstrings $h(x)$. If $\prod$ stands for a product on some (semi)group other than $\mathbb N$, tell us which!

There really are three different questions:

  1. In the title: Is $H$ collision resistant? That is: is it possible to exhibit distinct $S$ and $S'$ such that $H(S′)=H(S)$ ?
  2. In the body, first: Is $H$ first preimage resistant? That is: can we "compute (an) $S$ for given $H(S)$ "?
  3. In the body, then: Is $H$ second preimage resistant? That is: can we (given $S$) "find another $S′$ so that $H(S′)=H(S)$ "?

About 1., I conjecture that $H$ is not as collision resistant as $h$ is. The following attack sketch seems to have a fair chance to work for $h$ of say 160 bits:

  • choose a bound $B$ and tabulate the primes $p_j$ no more than $B$;
  • for integers $i$ starting from $0$ onwards (until there is enough): compute $h(i)$, test if it is B-smooth (has all its prime factors no more than $B$); if yes, keep that $i$ and its factorization, as the powers of the primes $p_j$ in the factorization, which is a vector of integers (overwhelmingly $0$ which need not use any memory, most of the rest $1$);
  • now, our goal is to find (disjoint) sets $S$ and $S'$ of integers $i$ we kept, such that the sum of the vectors for those $i$ in $S$ is the same as the sum of the vectors for those $i$ in $S'$; and I conjecture that problem is relatively tractable.

At least, that whole thing is well studied, and tractable, in the context of multiplicative RSA signature forgeries, except that in this context we have tuples multisets rather than sets here (so our problem is somewhat harder); see e.g. section 3 in Coron, Naccache, Tibouchi, Weinmann: Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures, and their sources.

In this attack, we can get rid of those $i$ where one of the non-zero power appears for no other $i'$, as they can be of no use in the solution thought. When a power appears for just two values $i$, $i'$, we can aggregate the two as the pair $(i,-i')$ and the difference of their vectors (because $i$ and $i'$, if useful, can only appear one in $S$ and the other in $S'$). Various other tricks apply, including the large prime(s) variants customary in QS.

share|improve this answer
    
They also bring the complication that order doesn't matter. $\;$ –  Ricky Demer Jun 6 '13 at 22:17
    
@RickyDemer: yes I misused tuples; in the context of multiplicative RSA signature forgeries, order does not matter either, but we can use each vector several times. What's the name for a set-that-can-contain-an-element-multiple-times, or a tuple-where-order-is-pointless? –  fgrieu Jun 6 '13 at 22:20
    
en.wikipedia.org/wiki/Multiset $\;$ –  Ricky Demer Jun 6 '13 at 22:22
add comment

If the hash outputs 160-bit integers, and the product operation is integer multiplication, then this is probably not secure, for reasons fgrieu outlines. For instance, about $1/2^{19}$ of all 160-bit integers are $B$-smooth, if we take $B$ to be the $2^{20}$th prime. Consequently, after hashing $2^{45}$ different candidate messages, we expect to find about $2^{26}$ smooth hash digests, which I suspect is enough to find a collision; and this computation seems likely to be feasible today.

On the other hand, if you work in a multiplicative group where the discrete log problem is hard, such as $\mathbb{Z}_p^*$, and if the hash function outputs random elements of this multiplicative group, then your scheme is secure. For instance, if you pick a 2048-bit prime $p$, arrange for your hash function to output numbers that are uniformly distributed between $1$ and $p-1$, and interpret the product as "multiplication modulo $p$", then your scheme should be secure. However, it might be a bit slow. See the following papers for technical details and security analysis:

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.