It's not really "impossble", just computationally infeasible. Given the infinite number of files that will hash to a given SHA256, it's technically infinitely possible.

@billc.cn: Have you really read the whole answer? Have you read what I mean by "no way"? 😉

@metallurg: the later relativation comes somewhat unexpected after such a terse, absolute introduction. I would move the sentence to the end with an introduction: For practical purposes...

Since OP might not know this, but you never say it explicitly: one of the main purposes of a cryptographic hash function like SHA-256 is to prevent exactly what OP is proposing. It is specifically designed to not run backwards.

It's also not quite correct to say that brute-force is the only way to find a SHA-256 collision. SHA-256's pre-image resistance has been slightly degraded (see: en.wikipedia.org/wiki/SHA-2#Cryptanalysis_and_validation). This means there are more efficient algorithms than just brute forcing all possible sources. Now I know these attacks are not nearly good enough to render SHA-256 unfit for purpose, but since the OP is clearly seeking to understand concepts here, I think we do them a disservice by simplifying to the point of incorrectness.

@Zach: "SHA-256's pre-image resistance has been slightly degraded"; not true - all the results listed are for reduced rounds variants of SHA-256 and don't apply directly to SHA-256 at all

@poncho, you are correct. Thank you.

There is another problem with trying to replicate an SHA-256 checksum; presumably the hacker has a purpose in mind, such as trying to load malware to someone's computer. So it isn't enough to just generate files at random and test the checksum, which,as @mentallurg has pointed out, will take a very long time: the hacker needs a file that carries out their purpose and has the correct checksum, which will take even longer. This is probably why most internet villains put their efforts into romance scams and the like.

Another comparison I like: assuming you calculate everything in the ideal cold vacuum of space, getting a 50% chance of finding a collision by brute force consumes more energy than found in the entire galaxy. The 256-bit space is a big space indeed!

@SimonCrase There are useful attacks with just random data having the same checksum too, first that comes to mind is to pollute bittorrent downloads but in general any place where you want to suppress information would work.

"there are infinitely many files that will produce the same SHA-256 value" - this is a bit sloppy. More formally, there exists at least one SHA-256 value where an infinite number of files produce that value. There is no guarantee that every hash value has at least one input file; some values could be unreachable.

@mentallurg is it mathematically proven it's impossible to do it? If I remember correctly this is a P = NP problem, and it haven't been proven it's impossible. We haven't found any way to prove P = NP either to be true or false, and as long as we don't I wouldn't call this impossible. And what about quantum computing, could that solve it? Impossible is a BIG statement.

@Polygorial I was wondering about the quantum computer possibility to break it. This answer (crypto.stackexchange.com/questions/59375/…) is optimistic about sha-256 being quantum computer safe.

@Nayuki: "there exists at least one SHA-256 value where an infinite number of files produce that value" - Correct.

@Polygorial: "is it mathematically proven it's impossible to do it?" - No. See this. But currently there is no solution known.

@billc.cn: just computationally infeasible - This is a matter of wording preferences. See how Merriam-Webster defines word "impossible": "not capable of being done or carried out, not feasible". Cambridge Dictionary has similar definition.

@Polygorial: "And what about quantum computing" - Quantum computers could theoretically reduce complexity from 2^n to 2^(n/2), means, reduce the strength from 256 to 128 bits. Even 128 bits is not feasible for brute-forcing. If mathematical solution not found and brute-forcing needs to be used, quantum computers will not help

@guidot: "a terse, absolute introduction" - The answers should be helpful. Otherwise we would have to write a book for every asked question. This is a difference of humans compared to formal computer systems: Humans use some context and some assumptions. This reduces essentially the amount of information that needs to be communicated. Of course, this can differ from person to person, and we see then questions, corrections, additions, and even objections...

@guidot: ... Then iteratively we come to a set of answers and comments that satisfy the most of participants of the discussion.

As a mathematician (I'm sure I'm not alone here) I object to the use of the word "impossible" here. I think you meant "infeasible" or "impractical".

@Wyck: I have to say you are not the only mathematician here. 😉 You don't have the authority to define the meaning of the words. Look at the definitions in the commonly used dictionaries like Merriam-Webster and Combridge Dictionary. I find the term "impossible" the best fit in this context. In another context we could have started with definition of glossary and only afterwards we could start with discussion. But in this case there is no need.

@Wyck that was what I was trying to say, but you did it way better.

@mentallurg if it's not proven impossible the answer shouldn't say it's impossible. Mathematically impossible doesn't mean what it means in everyday life, the meaning is that it's proven to be impossible. And posted as information security it should be based on security, which is to be as exact as possible. The other edits are clear and covers it, but only if it's read. Which people that need the info won't read since "It is impossible".

@Polygorial: Sure. It can even be that brute-forcing gives positive result already after a few tests. And it is even possible that the very first try will be successful. 🙂 The probability is extremely low, but theoretically it is possible. It depends on how we want to define the word "possible/impossible".

@Polygorial: But in the reality, there is no deterministic way to solve this problem A) with resources available to s single person (the author does not say anything about it, so I assume a single person); B) within limited time that might be acceptable to the person, like a few hours or a few days). This is what is called "impossible".

@Polygorial: "Impractical" has other meaning, closer to "it can be done, the result is guarantied, but we would prefer not to do it, because the price of doing it is higher than the possible benefits". "feasible" is closer to "impossible", but still does not fit as well as "impossible". "impossible" means in this case "no matter what you do, you will not solve the problem". It would be possible, if we had sufficient resources. But we don't have such resources, that's why it is impossible.

@mentallurg All of this for a very simple edit to a single word? And you rolled back an edit that did that? I think that you need to be a little less rigid in your thinking and stop digging in. The answer is greatly improved by a simple edit and there is no downside to the edit, except that you are taking the edit personally. Be a little less inflexible on a community-edited site, please. And your last comment just gutted your entire foundation for rejecting the edit...