0

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.

Improve this question
6
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 12:56
  • 1
    Do you actually mean "256 byte hash", or did you mean "256 bit hash"?
    – Anders
    Jun 20, 2016 at 15:18

2 Answers 2

Reset to default
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.

Improve this answer
5
  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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.

Improve this answer

Not the answer you're looking for? Browse other questions tagged .