7 ms·

Natural data is easily identifiable.

__s 5y ago
That's because natural data has low entropy But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are ofc, 100x compression of English text doesn't require this amount of compute to decompress: https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize It's also impractical since most compression use cases want to put the work in compression, & have decompression be straight forward edit: 100x was misreading, it's currently 8.6x http://prize.hutter1.net/#prev http://prize.hutter1.net/#prev
- AnimalMuppet 5y ago
  "Paragraph" is highly optimistic. IIRC, each English character has about 1 bit of entropy.
  - __s 5y ago
    Shannon estimated 0.6 to 1.3: https://cs.fit.edu/~mmahoney/dissertation/entropy1.html https://cs.fit.edu/~mmahoney/dissertation/entropy1.html For the sake of argument I figured I'd be highly optimistic. The linked prize shows practical evidence of 1GB of Wikipedia being compressed below 1 bit per character (& that's with a limit of 50 hours cpu time, 10GB memory, & 100GB disk)
- ganzuul 5y ago
  This is very abstract, but I believe that since both input and output are very close in program space compared to the total size of PS, the heuristics to map between them are going to be of a manageable size. This is based on an intuition about a single source for all activity in this universe.
dTal 5y ago
Not it's not. You can't distinguish the complete works of Shakespeare from the complete works of Shakespeare with the words changed a bit, or switching to Harry Potter for a bit in the middle, or a completely dazzling and original work of fiction. Any hash might generate all three of these, and essentially boundless other works. It's a library of Babel.
- ganzuul 5y ago
  Your examples really fall out of the scope of the premise.
  - fwip 5y ago
    No, they're 100% correct.
  - dTal 5y ago
    Forgive me if I've misunderstood - the premise was that, out of the infinite set of data that hashes to a particular hash/checksum, there is a unique data set that is "obviously" the real one? Or at least, that the set is meaningfully bounded? My reply is that this is not the case. There will be infinitely many "plausible" data sets as well. You could collide every hash in existence merely by making undetectably tiny alterations to Shakespeare.
    - ganzuul 5y ago
      Not obviously, no. - Just a very high probability. Perhaps that provides noise immunity to some degree. If it does, it is a form of AI. This admittedly open question presumes a very large fuzzy 'code book' with which it can re-assemble the data. The length of the input in cleartext is valuable metadata that speeds up the search.
      - dTal 5y ago
        You still seem to be missing the point. The problem is that the SHA-1 hash is one of 2^160 possible values, while a 1GB plaintext is one of 2^8000000000 possible values. That means that the hash disambiguates your message down to one of 2^7999999840 values. Let's go smaller. Let's say our plaintext is a single kilobyte. One 80x25 terminal's worth of ASCII. Knowing the SHA-1 hash narrows our search space, yes, but the search space is so absurdly large that it only solves 0.0000... (insert over two thousand zeros here) ..0001% of the problem. It tells you basically nothing.
contravariant 5y ago
Only if you count all natural looking data of which there is way more than you could possibly imagine. It is of course likely that humanity hasn't yet created more than 2^100 (~10^30) files, so in theory given a registry of all files in existence you might be able to identify it by its hash. However while this is simple it's definitely not easy.
- swutas 5y ago
  But this is technically an invalid answer to the problem of file compression. An easy (!) way for data to be losslessly compressed would just be to have a registry of all files in existence, and to refer to each file by its index in the registry. (Like the prisoners who had told each other all their jokes so many times that now they could just quote them by number and everyone would laugh.) Data compression is supposed to be able to deal with novel but likely documents without needing to add them to a global registry.
- ganzuul 5y ago
  I can imagine the output of program space. That's pretty big. All possible universes in fact. It's an issue of probability and bins. While natural data is infinite, there is vastly more unnatural data. At some point you have enough metadata (e.g. natural vs. random) to know that the original data came from Earth to pick out the right needle from the needle stack. Unless the data is from a completely alien source, we are close enough to that source for our heuristics to be of a manageable size.
  - contravariant 5y ago
    It's somewhat irrelevant how many unnatural data there is. The point is that there's way more plausible data (or sentences if we're restricting ourselves to natural language) than there are possible 160; 256 or 512 bit hashes. Unless of course you enumerate all of human communication, but like I said that doesn't count as 'easy'.
    - ganzuul 5y ago
      I'm not trying to claim this is practical with current technology.
fwip 5y ago
Nope, not on these scales. Say you have a 32 byte hash, that's 2^(328) possible values, right? Now say your input is 128 bytes, that means that (on average) each 32 byte hash maps to 2^(968) values. "Natural looking" data will occur an astronomical number of times in a search space that large - which is, again, only 96 bytes larger than your hash.
xinniethepooh 5y ago
It's not, and that's why decryption of unknown ciphertext is even harder

__s 5y ago

That's because natural data has low entropy But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are ofc, 100x compression of English text doesn't require this amount of compute to decompress: https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize It's also impractical since most compression use cases want to put the work in compression, & have decompression be straight forward edit: 100x was misreading, it's currently 8.6x http://prize.hutter1.net/#prev http://prize.hutter1.net/#prev

AnimalMuppet 5y ago
"Paragraph" is highly optimistic. IIRC, each English character has about 1 bit of entropy.
- __s 5y ago
  Shannon estimated 0.6 to 1.3: https://cs.fit.edu/~mmahoney/dissertation/entropy1.html https://cs.fit.edu/~mmahoney/dissertation/entropy1.html For the sake of argument I figured I'd be highly optimistic. The linked prize shows practical evidence of 1GB of Wikipedia being compressed below 1 bit per character (& that's with a limit of 50 hours cpu time, 10GB memory, & 100GB disk)
ganzuul 5y ago
This is very abstract, but I believe that since both input and output are very close in program space compared to the total size of PS, the heuristics to map between them are going to be of a manageable size. This is based on an intuition about a single source for all activity in this universe.

dTal 5y ago

Not it's not. You can't distinguish the complete works of Shakespeare from the complete works of Shakespeare with the words changed a bit, or switching to Harry Potter for a bit in the middle, or a completely dazzling and original work of fiction. Any hash might generate all three of these, and essentially boundless other works. It's a library of Babel.

ganzuul 5y ago
Your examples really fall out of the scope of the premise.
- fwip 5y ago
  No, they're 100% correct.
- dTal 5y ago
  Forgive me if I've misunderstood - the premise was that, out of the infinite set of data that hashes to a particular hash/checksum, there is a unique data set that is "obviously" the real one? Or at least, that the set is meaningfully bounded? My reply is that this is not the case. There will be infinitely many "plausible" data sets as well. You could collide every hash in existence merely by making undetectably tiny alterations to Shakespeare.
  - ganzuul 5y ago
    Not obviously, no. - Just a very high probability. Perhaps that provides noise immunity to some degree. If it does, it is a form of AI. This admittedly open question presumes a very large fuzzy 'code book' with which it can re-assemble the data. The length of the input in cleartext is valuable metadata that speeds up the search.
    - dTal 5y ago
      You still seem to be missing the point. The problem is that the SHA-1 hash is one of 2^160 possible values, while a 1GB plaintext is one of 2^8000000000 possible values. That means that the hash disambiguates your message down to one of 2^7999999840 values. Let's go smaller. Let's say our plaintext is a single kilobyte. One 80x25 terminal's worth of ASCII. Knowing the SHA-1 hash narrows our search space, yes, but the search space is so absurdly large that it only solves 0.0000... (insert over two thousand zeros here) ..0001% of the problem. It tells you basically nothing.

contravariant 5y ago

Only if you count all natural looking data of which there is way more than you could possibly imagine. It is of course likely that humanity hasn't yet created more than 2^100 (~10^30) files, so in theory given a registry of all files in existence you might be able to identify it by its hash. However while this is simple it's definitely not easy.

swutas 5y ago
But this is technically an invalid answer to the problem of file compression. An easy (!) way for data to be losslessly compressed would just be to have a registry of all files in existence, and to refer to each file by its index in the registry. (Like the prisoners who had told each other all their jokes so many times that now they could just quote them by number and everyone would laugh.) Data compression is supposed to be able to deal with novel but likely documents without needing to add them to a global registry.
ganzuul 5y ago
I can imagine the output of program space. That's pretty big. All possible universes in fact. It's an issue of probability and bins. While natural data is infinite, there is vastly more unnatural data. At some point you have enough metadata (e.g. natural vs. random) to know that the original data came from Earth to pick out the right needle from the needle stack. Unless the data is from a completely alien source, we are close enough to that source for our heuristics to be of a manageable size.
- contravariant 5y ago
  It's somewhat irrelevant how many unnatural data there is. The point is that there's way more plausible data (or sentences if we're restricting ourselves to natural language) than there are possible 160; 256 or 512 bit hashes. Unless of course you enumerate all of human communication, but like I said that doesn't count as 'easy'.
  - ganzuul 5y ago
    I'm not trying to claim this is practical with current technology.

fwip 5y ago

Nope, not on these scales. Say you have a 32 byte hash, that's 2^(328) possible values, right? Now say your input is 128 bytes, that means that (on average) each 32 byte hash maps to 2^(968) values. "Natural looking" data will occur an astronomical number of times in a search space that large - which is, again, only 96 bytes larger than your hash.

xinniethepooh 5y ago

It's not, and that's why decryption of unknown ciphertext is even harder