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.
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.
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.
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.
> You're supposed to be able to remove the padding in cryptography
It's a hash. You can never access the post-padding version of the input in the first place.
"it works as a cryptographic hash" is certainly a "killer use case" for a cryptographic hash.
Your "Dylan16807 hash" without working padding does not work as a cryptographic hash, it's useless.
Nobody complains that RSA gives you the same result for 45 and 0045 after all.
Better, think of it like a hash algorithm that takes bits vs one that takes bytes. They both work fine and are secure. If your byte happens to be a really wide byte, that's not a fatal flaw.
Defining failure as success is very, very stupid. Nobody needs to "do better" than calling your position out as wrong.
> Nobody complains that RSA gives you the same result for 45 and 0045 after all.
RSA doesn't give you "the same result for 45 and 0045" unless what you mean by "0045" is "Actually just 45 except for some reason I write that with extra zeroes as part of my bad faith argument".
Hash algorithms that don't work aren't "just fine" they're useless.
The reason algorithms like SHA-256 are defined for bits isn't arbitrary - bits are literally the unit of information, this is the obvious and natural way to define the function, so choosing to define a function over "really wide bytes" doesn't make any sense.
It's not going to be convincing unless you can talk about a specific attack. And in particular, that attack should be more relevant to real-world use than a weakness like length extension.
Especially because you could look at this weakness as a sibling attack to length extension, one that's mildly easier to pull off but you can only append zeros. That seems safer overall to me. And it's not reasonable to completely excuse one flaw as needing "misuse" but not the other.
> The reason algorithms like SHA-256 are defined for bits isn't arbitrary - bits are literally the unit of information, this is the obvious and natural way to define the function, so choosing to define a function over "really wide bytes" doesn't make any sense.
A hash algorithm that takes an input in bytes is not a failure. If you think taking single bits is actually necessary, rather than just 'obvious and natural', then I really think you're not analyzing the security properly.
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.