Re: [cryptography] Number of hash function preimages
On 2012-03-09, natanae...@gmail.com wrote: On #2: There MUST be collisions with fixed-length hashes. But with 2^256 possible results and sufficiently strong algorithms, it will not matter IRL. We won't find any collisions ever. But of course, the algorithms MIGHT be weak. MD5 was thought to be strong when it was new. I think Florian asked whether there exists a collision for _every_ hash value. Cheers, Timo ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Number of hash function preimages
He actually asked two different questions on #2, if all hashes have collisions and if all messages have collisions. For MD5, the latter is almost proven true. There's a tool that let you enter two plaintexts, and then it generates a shared appended string (like md5(text_a+string)=md5(text_b+string)) that gives them the same hash. Not exactly the same, but relevant. If there's direct collisions for all hashes and/or messages depends entirely on the algorithm. There could be one hash for SHA256, for example, which only has *one* message that can generate it. Then there are no messages or hashes colliding with those, and the answer to both of the questions in #2 is no. Also note that if there's collisions for all hashes, there's collisions for all messages, but the reverse doesn't have to be true. 2012-03-10 12:33 skrev Timo Warns: On 2012-03-09, natanae...@gmail.com wrote: On #2: There MUST be collisions with fixed-length hashes. But with 2^256 possible results and sufficiently strong algorithms, it will not matter IRL. We won't find any collisions ever. But of course, the algorithms MIGHT be weak. MD5 was thought to be strong when it was new. I think Florian asked whether there exists a collision for _every_ hash value. Cheers, Timo ___ cryptography mailing list natanae...@gmail.com http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Number of hash function preimages
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
On Mar 9, 2012, at 3:25 AM, Florian Weingarten wrote:
Hello list,
first, excuse me if my questions are obvious (or irrelevant).
No, they're interesting and subtle.
I am interested in the following questions. Let h be a cryptographic
hash function (let's say SHA1, SHA256, MD5, ...).
There's a lot to put in that ellipsis.
1) Is h known to be surjective (or known to not be surjective)? (i.e.,
is the set h^{-1}(x) non-empty for every x in the codomain of h?)
No. I would bet that the standard ones are all surjective, but I don't know
that it's ever been demonstrated for any given hash function. The main property
we want from a hash function is that is is one-way, and demonstrating that a
one-way function is or isn't surjective flirts with that, at least. Some will
be easy (modulo is one way and surjective, for example), others will be harder.
When you add in other desirable hash function properties such as being
reasonably collision-free, it becomes harder to show.
However, if you show that a hash function is a combination of surjective
functions that all preserve surjectivity, I think it's an easy proof.
All the ones that use a block cipher and a chaining mode are likely easy to
prove.
2) Is it known if every (valid) digest has always more than one
preimage? To state it otherwise: Does a collision exist for every
message? (i.e., is the set h^{-1}(x) larger than 1 for every x in the
image of h?).
Sure, by the pigeonhole principle. Consider a hash with 256-bit (32-byte)
output. For messages larger than 32 bytes, by the pigeonhole principle, there
must be collisions. For messages smaller than 32 bytes, they might collide on
themselves but don't have to, but there will be some large message that
collides with it.
3) Are there any cryptographic protocols or other applications where the
answers to 1) or 2) are actually relevant?
Very likely not.
Let's construct a trivial non-surjective hash function. Start with H, and
construct H' that for any message that produces a hash of 0, we emit 1 instead.
It's therefore not surjective since it can't emit a zero.
It isn't a *useful* non-surjectivity because we don't usefully know a preimage
of a zero or a one.
But now let's construct H'' that emits H(M2) when calculating H(M1). This is
just like H', but with different constants. The difference here is that we have
artificially created a collision between M1 and M2 instead of a preimage of 0
and a preimage of 1, which we don't know in advance. Is this a useful
collision? That's a philosophical question. I'd say no, myself, but I'd
understand why someone said yes, I'd merely disagree with them.
That's why I say very likely not, instead of just no.
Jon
-BEGIN PGP SIGNATURE-
Version: PGP Universal 3.2.0 (Build 1672)
Charset: us-ascii
wj8DBQFPW/HEsTedWZOD3gYRAhvWAJ4rL6Zxp9eCUpxqDEYPQTLxKQu0VwCeJqHG
IVoDJYQIMASPi03Hl19LxXE=
=68//
-END PGP SIGNATURE-
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Number of hash function preimages
On Sat, Mar 10, 2012 at 7:28 PM, Jon Callas j...@callas.org wrote:
2) Is it known if every (valid) digest has always more than one
preimage? To state it otherwise: Does a collision exist for every
message? (i.e., is the set h^{-1}(x) larger than 1 for every x in the
image of h?).
Sure, by the pigeonhole principle. Consider a hash with 256-bit (32-byte)
output. For messages larger than 32 bytes, by the pigeonhole principle, there
must be collisions. For messages smaller than 32 bytes, they might collide on
themselves but don't have to, but there will be some large message that
collides with it.
I think you are misunderstanding the question (or at the very least I
am). The pigeonhole principle only shows that there exist collisions
not that collisions exist for every element in the codomain.
Think about the function over the natural numbers:
f(x) = {
1, if x = 0
2, if x 0
3, if x 0
}
While there exist collisions within N it isn't true that every element
in the co-domain has a collision.
--
Eitan Adler
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
