3 ms·

In theory, I quite like the solution mentioned in the earlier threads: request a file that's a few kilobytes, then get two or three different hashes of the file

by TillE 12y ago

In theory, I quite like the solution mentioned in the earlier threads: request a file that's a few kilobytes, then get two or three different hashes of the file, and write a "decompressor" that generates random files and checks the hashes. It's just a shame that the heat death of the universe will probably occur before your program finishes.

piannucci 12y ago
Sorry, but no. There are far more files with a given hash than just the one, if the file is longer than the hash. And having multiple hashes doesn't help until the hashes exceed the length of the file.
- compbio 12y ago
  Chances of getting a collision is higher than getting a good solution, but having multiple hashes does help in increasing the chance at a good solution. With a hash 1 bit less than the length of the file, we put two pigeons inside one hole, and have a 50% chance at picking the right pigeon. The fewer/smaller hashes, the more we get "sorry, but no".
  - m_mueller 12y ago
    Also, I guess the hash algorithm could be specifically tested to work for this particular solution, couldn't it (although only after having spent the $100 of course)?. The problem I guess is to have a script that takes up less space than for the hash to still work without a collision for the particular data. Even with the smallest possible program or script, this probably isn't going to work then.
  - Someone 12y ago
    It's easier to just drop the final F bits from the N-bit input stream and, at decompression time, guess what they are than to go through this exercise of generating hashes that have N-F bits in total and hunt for bit streams having those hashes.
dvirsky 12y ago
You could maybe use something like pi-fs :) https://github.com/philipl/pifs https://github.com/philipl/pifs
abemassry 12y ago
Yes, I had wanted to learn about multithreading in Python at the same time I had previously read this story. I built it, it worked, but took a reaaaaly long time, it was fun! https://github.com/abemassry/crazip https://github.com/abemassry/crazip

by TillE 12y ago

piannucci 12y ago

Sorry, but no. There are far more files with a given hash than just the one, if the file is longer than the hash. And having multiple hashes doesn't help until the hashes exceed the length of the file.

compbio 12y ago
Chances of getting a collision is higher than getting a good solution, but having multiple hashes does help in increasing the chance at a good solution. With a hash 1 bit less than the length of the file, we put two pigeons inside one hole, and have a 50% chance at picking the right pigeon. The fewer/smaller hashes, the more we get "sorry, but no".
- m_mueller 12y ago
  Also, I guess the hash algorithm could be specifically tested to work for this particular solution, couldn't it (although only after having spent the $100 of course)?. The problem I guess is to have a script that takes up less space than for the hash to still work without a collision for the particular data. Even with the smallest possible program or script, this probably isn't going to work then.
- Someone 12y ago
  It's easier to just drop the final F bits from the N-bit input stream and, at decompression time, guess what they are than to go through this exercise of generating hashes that have N-F bits in total and hunt for bit streams having those hashes.

dvirsky 12y ago

You could maybe use something like pi-fs :) https://github.com/philipl/pifs https://github.com/philipl/pifs

abemassry 12y ago

Yes, I had wanted to learn about multithreading in Python at the same time I had previously read this story. I built it, it worked, but took a reaaaaly long time, it was fun! https://github.com/abemassry/crazip https://github.com/abemassry/crazip