0

This question already has an answer here:

A individual file only has a single hash of any specific byte length. But an individual hash can represent a large number of different files.

Given a 256 byte hash, how long would it take to generate a file to match that hash?

In order to answer this question in a concrete manner, we will have to make some arbitrary decisions about available hardware. Answers can assume the use of:

  • A single motherboard.
  • The fastest x86 processor available today, with up to 16 of those processors on the same motherboard, iff (if and only if) such a motherboard actually exists.
  • Up to 256GB of RAM, if supported.
  • The fastest graphics cards available for the processor, with as many as the cards as the motherboard will support.
  • Up to 256GB of RAM per graphics card, if supported.
  • Any operating system.
  • Any programming language or combination of programming languages.

Basically, let's assume a single realistic dedicated computer working on the task, not a distributed network.

marked as duplicate by WhiteWinterWolf, Rory Alsop Jun 20 '16 at 21:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • Sometime between practically instant, and forever. There is no actual proof that all hashes are achievable by any given hash algorithm, with the exception of some trivial ones (e.g. take the modulus of the input over the number of potential hash outputs). See stackoverflow.com/questions/6776050/… for more discussion of this – Matthew Jun 20 '16 at 11:43
  • 1
    Your first sentence is false: a file can have multiple hashes of the same length, depending on the hash algorithm, for example SHA-256 (sha2) and SHA3-256 (sha3) have the same output hash size, but are different algorithms and will give different hashes. – Douglas Leeder Jun 20 '16 at 12:21
  • This blog post has some more information about the speed of hashing algorithms and the feasibility to find hash collisions: Speed Hashing – Sjoerd Jun 20 '16 at 12:27
  • The whole point of hashes is that small change in the content of the file (typically) causes a significant change in the resulting hash. Thus, you've probably got more chance of winning the lottery three times in a row then ever managing to "generate a file to match that hash" ! – Little Code Jun 20 '16 at 12:56
  • 1
    Do you actually mean "256 byte hash", or did you mean "256 bit hash"? – Anders Jun 20 '16 at 15:18
4

Let's say we can try 10,000,000,000 SHA-256 hashes per second. For us to find the 256 byte hash, we have to search approximately half the search space, so we need to compute 2^255 hashes. This will take 2^255 / 10,000,000,000 seconds, or about 183587153154040137340770841274555916814545257270485419900205 years.

Edit: I screwed up the calculation, because I interpreted bytes as bits.

Since 256 bytes is 2048 bits, we need to calculate 2^2047 hashes, and this takes 51238277002966462615288680696140842149359624983694006900257396986816107209011749894084857641303452346031072363206966672206556886019931064648478171591908109970558849199804978582810435296787246490988168503272557661524594461318207375954208038968918332176848119374740463348058688311043039397208828638895120474254684064861853663147965776868601866905847564743985163080412553366519257662208999737046959970928743526011452948564278693172244975824932848021949038580088291525918197749731767202126390635665479647814685664923669295305438224994217717272665406466244034334639145952931934304676113772521803887927378002 years.

  • all you're really doing there is telling us how long it will theoretically take to find a collision. The content generated by the collision may well be unreadable nonsense. – Little Code Jun 20 '16 at 13:09
  • 1
    That's a good point. The question does not specify any specific content or file type, but in practice you would want to create a valid file with specific contents to exploit the hash collision. – Sjoerd Jun 20 '16 at 13:14
  • I appreciate you doing all the computations, but I also think you should have used scientific notation or something. – A. Darwin Jun 20 '16 at 15:43
  • The question is input producing a given hash -- that's preimage not collision. Collision would only(!) be about 2^1024. – dave_thompson_085 Jun 20 '16 at 16:18
  • 2
    @A.Darwin Would it really be any more clear that it's completely unfeasible if he said it was 10 ^ 500whatever years, instead of a massive block of numbers? I think the block of numbers illustrates the point nicely. – Steve Sether Jun 20 '16 at 17:41
2

Assuming a very good hash, use one of Sjoerd's answers. If the hash were very, very bad, however a collision could be calcuated in microseconds.

i.e. 256 bit/byte hash alone means nothing unless it was designed properly. A naive hash could be something as simple as a CRC, which was never intended to be secure.

Even hashes designed for security purposes can later be found to be insecure. One good example is the LanMan hash, used in early Microsoft products. Although it provides a length of 16 bytes (128 bits), it has multiple problems that make attacking it MUCH MUCH easier than a complexity of 2^127. While LanMan was used for passwords, not files, the general principle of the hash design still applies.

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