5 ms·

I’ve always been curious about whether it’s possible to have a collision when your input is 256 bits or less (in the case of sha256)… I even emailed Bruce Schne

I’ve always been curious about whether it’s possible to have a collision when your input is 256 bits or less (in the case of sha256)… I even emailed Bruce Schneier. I got a polite response that he didn’t have time to look at it, which indicated to me he didn’t know “off the top of his head”, which I interpreted as “it’s not impossible”… but I still don’t know.

upofadown 4y ago
What sort of collision? Or asking in a different way, what would you consider a collision?
- _vdpp 4y ago
  2 messages producing the same digest. That’s actually a really interesting question.
- mike_hock 4y ago
  I think he means a set-theoretical collision, not a feasible collision attack. I.e. "is SHA256 a bijection on 256-bit integers?"
edflsafoiewq 4y ago
There are 2^257 - 1 inputs of 256 bits or less and only 2^256 possible hashes, so there must be a collision.
- CamperBob2 4y ago
  The input is always padded out to 256 bits, though, isn't it?
  - edflsafoiewq 4y ago
    The input is padded to form a sequence of 512 bit chunks, but that doesn't change anything, padding is one-to-one so there's still the same number of inputs.
    - Dylan16807 4y ago
      > padding is one-to-one so there's still the same number of inputs That part is debatable, if we imagine different padding schemes. If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. You could also say you consider the extra '1' bit in SHA-256 as part of the payload, not truly 'padding' because it's mandatory, and make a similar argument, and it wouldn't be blatantly wrong.
      - tialaramex 4y ago
        > That part is debatable, if we imagine different padding schemes. It isn't debatable because SHA-256 (and all these schemes) define the padding because it's necessary to have padding defeat the problem you're about to talk about and to do that they are in fact one-to-one: > If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. As you might have guessed, this is not how it works. SHA-256 appends that "extra 1 bit" you talk about, then zeroes until it is 64-bits short of a multiple of 512 bits, and then a 64-bit count. So, as the earlier poster explained there are 2^257 -1 distinct hash inputs in abotsis' imagined set and thus there must be collisions by the pigeon hole principle, it really is that simple.
        Dylan16807 4y ago
        > it's necessary to have padding defeat the problem you're about to talk about There is no way it's "necessary" to avoid that particular problem, yet at the same time unnecessary to avoid length extension attacks. > As you might have guessed, this is not how it works. That's a weirdly hostile way to respond to a clearly counterfactual thought experiment. > and thus there must be collisions by the pigeon hole principle, it really is that simple Except they didn't just say there must be collisions in SHA-256, by my reading they were making an argument that the method of appending padding and stuff doesn't matter.
        tialaramex 4y ago
        > There is no way it's "necessary" to avoid that particular problem, yet at the same time unnecessary to avoid length extension attacks. Length extension attacks work because of a common misuse of these algorithms. If you use them properly you aren't vulnerable to a length extension attack whereas you would be in trouble with the terrible "padding" scheme you propose as a counterfactual. Algorithms like SHA-512/256 and Keccak are prominent because they're misuse resistant. Consider the guillotine used to cut paper to size. Used correctly it's not very dangerous, but we don't let kids have access to a guillotine because it lacks misuse resistance. In contrast devices like a Rotatrim are safe for kids because they are resistant to misuse. It turns out most programmers are kids and we should not have given them C++ std::sort() or SHA-256 or ECB mode encryption because they will cut themselves. > by my reading they were making an argument that the method of appending padding and stuff doesn't matter. If your "method of appending padding" turns 2^257 -1 inputs into 2^256 outputs that was not, in fact, "padding" in the sense anybody knowledgeable in this field would use. You're supposed to be able to remove the padding in cryptography, if some of the "padded" structures are indistinguishable from each other you can't do that.
im3w1l 4y ago
One way to think of hash functions is that the hash of any value is basically a random number. So we can consider what happens if the results were actually random, then what would be the probability of a collision? Consider a function from [0, 2^256 - 1] to [0, 2^256 - 1]. That is it maps 256bit numbers to 256bit numbers. It could in theory be represented as an enormous table lookup. Now how many such functions are there? Well there are 2^256 ways to map 0. And then 2^256 ways to map 1.. etc. We have 2^256 inputs we need to deal with each of which can give one of of 2^256 results. That turns into (2^256) ^ (2^256) Now, how many collision free functions are there? In this case there are 2^256 ways to map 0, but then we have to pick a different number for 1, so there are only 2^256 - 1 possiblites. Then 2^256 - 2 etc... It becomes (2^256)! where the exclamation mark is factorial. So the probability of no collisions is (2^256)! / [(2^256) ^ (2^256)]. It may not be obvious but that's a very small number. A little bit of intuition: let's say we fill out the values of our gigantic table by hand. Let's assume that by some miracle we filled out the first half without creating any collisions. Now that means we used up half the possible outputs. So every cell we fill out from now we have a 50/50 of creating a collision. And the further we get the more numbers are used up. Now sha256 is not a randomly chosen function. But without any evidence either way, we might suspect it does have collisions.
abotsis 4y ago
To give some further context, I stumbled across this thought while reading how “community ids” are calculated. Community ids are commonly used to simplify joining/lookups for network security tools (suracata, zeek). They essentially concatenate the “quad tuple” (src ip/port, dest ip/port), and a “seed”, then run sha against it. I didn’t entirely understand the reason the authors chose sha (other than being security people who might have just reached for a crypto secure hash function). SHA is slow vs something like xxh, and given the number of sessions these things process, seemed like overkill. Further, it’s unclear to me what’s gained by using sha vs xxh or simply concatenating the bits. Then I started wondering about the downsides: whether it’s possible to have a false correlation because two sessions yielded the same sha digest.

upofadown 4y ago

What sort of collision? Or asking in a different way, what would you consider a collision?

_vdpp 4y ago
2 messages producing the same digest. That’s actually a really interesting question.
mike_hock 4y ago
I think he means a set-theoretical collision, not a feasible collision attack. I.e. "is SHA256 a bijection on 256-bit integers?"

edflsafoiewq 4y ago

There are 2^257 - 1 inputs of 256 bits or less and only 2^256 possible hashes, so there must be a collision.

CamperBob2 4y ago
The input is always padded out to 256 bits, though, isn't it?
- edflsafoiewq 4y ago
  The input is padded to form a sequence of 512 bit chunks, but that doesn't change anything, padding is one-to-one so there's still the same number of inputs.
  - Dylan16807 4y ago
    > padding is one-to-one so there's still the same number of inputs That part is debatable, if we imagine different padding schemes. If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. You could also say you consider the extra '1' bit in SHA-256 as part of the payload, not truly 'padding' because it's mandatory, and make a similar argument, and it wouldn't be blatantly wrong.
    - tialaramex 4y ago
      > That part is debatable, if we imagine different padding schemes. It isn't debatable because SHA-256 (and all these schemes) define the padding because it's necessary to have padding defeat the problem you're about to talk about and to do that they are in fact one-to-one: > If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. As you might have guessed, this is not how it works. SHA-256 appends that "extra 1 bit" you talk about, then zeroes until it is 64-bits short of a multiple of 512 bits, and then a 64-bit count. So, as the earlier poster explained there are 2^257 -1 distinct hash inputs in abotsis' imagined set and thus there must be collisions by the pigeon hole principle, it really is that simple.
      - Dylan16807 4y ago
        > it's necessary to have padding defeat the problem you're about to talk about There is no way it's "necessary" to avoid that particular problem, yet at the same time unnecessary to avoid length extension attacks. > As you might have guessed, this is not how it works. That's a weirdly hostile way to respond to a clearly counterfactual thought experiment. > and thus there must be collisions by the pigeon hole principle, it really is that simple Except they didn't just say there must be collisions in SHA-256, by my reading they were making an argument that the method of appending padding and stuff doesn't matter.
        tialaramex 4y ago
        > There is no way it's "necessary" to avoid that particular problem, yet at the same time unnecessary to avoid length extension attacks. Length extension attacks work because of a common misuse of these algorithms. If you use them properly you aren't vulnerable to a length extension attack whereas you would be in trouble with the terrible "padding" scheme you propose as a counterfactual. Algorithms like SHA-512/256 and Keccak are prominent because they're misuse resistant. Consider the guillotine used to cut paper to size. Used correctly it's not very dangerous, but we don't let kids have access to a guillotine because it lacks misuse resistance. In contrast devices like a Rotatrim are safe for kids because they are resistant to misuse. It turns out most programmers are kids and we should not have given them C++ std::sort() or SHA-256 or ECB mode encryption because they will cut themselves. > by my reading they were making an argument that the method of appending padding and stuff doesn't matter. If your "method of appending padding" turns 2^257 -1 inputs into 2^256 outputs that was not, in fact, "padding" in the sense anybody knowledgeable in this field would use. You're supposed to be able to remove the padding in cryptography, if some of the "padded" structures are indistinguishable from each other you can't do that.

im3w1l 4y ago

One way to think of hash functions is that the hash of any value is basically a random number. So we can consider what happens if the results were actually random, then what would be the probability of a collision? Consider a function from [0, 2^256 - 1] to [0, 2^256 - 1]. That is it maps 256bit numbers to 256bit numbers. It could in theory be represented as an enormous table lookup. Now how many such functions are there? Well there are 2^256 ways to map 0. And then 2^256 ways to map 1.. etc. We have 2^256 inputs we need to deal with each of which can give one of of 2^256 results. That turns into (2^256) ^ (2^256) Now, how many collision free functions are there? In this case there are 2^256 ways to map 0, but then we have to pick a different number for 1, so there are only 2^256 - 1 possiblites. Then 2^256 - 2 etc... It becomes (2^256)! where the exclamation mark is factorial. So the probability of no collisions is (2^256)! / [(2^256) ^ (2^256)]. It may not be obvious but that's a very small number. A little bit of intuition: let's say we fill out the values of our gigantic table by hand. Let's assume that by some miracle we filled out the first half without creating any collisions. Now that means we used up half the possible outputs. So every cell we fill out from now we have a 50/50 of creating a collision. And the further we get the more numbers are used up. Now sha256 is not a randomly chosen function. But without any evidence either way, we might suspect it does have collisions.

abotsis 4y ago

To give some further context, I stumbled across this thought while reading how “community ids” are calculated. Community ids are commonly used to simplify joining/lookups for network security tools (suracata, zeek). They essentially concatenate the “quad tuple” (src ip/port, dest ip/port), and a “seed”, then run sha against it. I didn’t entirely understand the reason the authors chose sha (other than being security people who might have just reached for a crypto secure hash function). SHA is slow vs something like xxh, and given the number of sessions these things process, seemed like overkill. Further, it’s unclear to me what’s gained by using sha vs xxh or simply concatenating the bits. Then I started wondering about the downsides: whether it’s possible to have a false correlation because two sessions yielded the same sha digest.