5 ms·

This concept is philosophically interesting, because an infinitely-powerful deity could compose text with a hash value of all 8's, and anyone could verify that

by p1mrx 6y ago

This concept is philosophically interesting, because an infinitely-powerful deity could compose text with a hash value of all 8's, and anyone could verify that it was authored by someone with more computing power than the universe. The fact that this is possible, but hasn't happened, may imply that we have never received a message from such an entity.

Closi 6y ago
I doubt that is possible with the 64 byte limit (at least making something that makes sense to read as a poem, as per the challenge).
- tedunangst 6y ago
  There's something like 2^59 64 byte strings that hash to all 8s. (Er, 2^168? Math is hard.)
  - Closi 6y ago
    But how many of those strings consist entirely of sensical prose? Even in a string of just 4 letters, out of c500,000 combinations only c5k are a valid word. The longer the string, the smaller % of random letter combinations will happen to be valid prose.
    - MauranKilom 6y ago
      English text has about 1 bit of information per character. So there are about 2^64 different meaningful 64 character messages.
      - deleted 6y ago
        [deleted]
  - MauranKilom 6y ago
    You have 2^256 possible hash values and 2^(8*64) = 2^512 different 64 character strings. So for each hash value (including the "only 8s" one) there are, on average, 2^256 64 char strings mapping to that value. Therefore (but also trivially) a random 64 character string (or any string) has a 1/2^256 chance of having all 8s in its hash. Since English has about 1 bit of information per character, there are only about 2^64 different non-gibberish 64 char strings. The odds that there exists any English phrase with an all 8 hash are 1/2^192 (i.e. zero).
    - GuB-42 6y ago
      Standard English text is around 1 bit of entropy per character, but it doesn't mean you can only write 2^64 non-gibberish text in 64 characters. For example, there are around 40k eight letter words, way more than 256. The entropy is so low because we keep using the same words, but we don't have to. We can also use abbreviations, invent proper nouns, and we don't even have to limit ourselves to English or even a single language. "犬 in French is chien, that one is Klign jr" is perfectly valid. I don't know if all 8s is possible, UTF-8 is quite wasteful for that purpose. Maybe we could take advantage of kanji. I don't know enough about Japanese, and even less Chinese, but it looks like you could make a proper noun by mashing any kanji together, including the obscure ones, and it will be usable and pronounceable. Maybe not pretty, but valid. Edit: And as a last resort, we could cheat with "password: }8pHgaQ^?7ic'6KIO!uDXQnhL3(6hcfZmRYnGUw1Pz`c?y@D"
      - MauranKilom 6y ago
        > For example, there are around 40k eight letter words, way more than 256. The entropy is so low because we keep using the same words, but we don't have to. Correct, but that low entropy is what distinguishes Monday Tuesday Wednesday Thursday Friday Saturday Sunday from (sampled from random Wikipedia article titles) Alabama Christopher List Park Girlfriend Manor crucifera or I saw your dad outside of Walmart yesterday. from (5th word of 2nd section of random Wikipedia articles) gospel Rich existed school and for Deputy he > We can also use abbreviations, invent proper nouns, Sure, make it 1.1 bits per character (the 1 bit is not a precise number anyway). That doesn't change anything about the orders of magnitude involved. > we don't even have to limit ourselves to English or even a single language. I tried to look for entropy of Chinese writing, and I've only found an upper bound of 3.8 bits per (UTF8) byte. That makes it still unlikely but at least conceivable that there is an all-8 amulet made of 64 bytes of Chinese text. > UTF-8 is quite wasteful for that purpose. Right, but as far as I understand that's the constraint. > And as a last resort, we could cheat with "password: }8pHgaQ^?7ic'6KIO!uDXQnhL3(6hcfZmRYnGUw1Pz`c?y@D" Yes, but that's not interesting from either an art nor from a computer science point of view.
- p1mrx 6y ago
  Yeah, my idea makes more sense if you omit the 64-byte limit; then the input can be an entire book. For an ideal hash function, every output maps to an infinite number of inputs. I don't know if SHA-256 has that property, but God could just define the simplest ideal hash function and let people cryptanalyze it.
fwip 6y ago
The more likely explanation would be that a human has broken SHA-256.
- userbinator 6y ago
  ...and with a preimage attack, something that even MD4 --- for which collisions can easily be generated with hand calculation --- resists to this day. I'm reasonably confident that if the three-letter-agencies know of such attacks, or general techniques for doing so, they would be very quiet about it.
- jtsiskin 6y ago
  Yes. Or even that someone reinvented computing. Or contact from an alien race. Are all more plausible than a deity. For a proof of God I would require something without in which it really is the most likely explanation, like a face appearing on a piece of toast
schoen 6y ago
There was a religious apologetics claim, widely presented and debated in the 1990s, that there were statistical anomalies in the Torah to show that it was really written by God: https://en.wikipedia.org/wiki/Bible_code https://en.wikipedia.org/wiki/Bible_code However, the measurement technique was somewhat underdetermined, which is a problem akin to p-hacking (as you could look for many possible anomalies and only publish the ones that you successfully find). > anyone could verify that it was authored by someone with more computing power than the universe I never thought of this that way, but that's an excellent way to put it! (Although you also need to assume that the hash is extremely strongly preimage-resistant, which we don't have good mathematical techniques to prove today.) One challenge for this: what is the canonical text encoding and canonicalization, and what is the canonical hash function?
- p1mrx 6y ago
  Well, if I were God, I would just define a canonical encoding and hash function as part of the message. Mathematicians would study the algorithm over the years, but never find any flaws.
  - readyplayeremma 6y ago
    Isn't that cheating though? By controlling the hash function you can alter the function itself until your message will meet the requirements, even though someone later on would find it impossible to compute a new message that meets the same?
    - p1mrx 6y ago
      Presumably, God could foresee the cryptographic flaws of any algorithm, and could therefore design a simpler secure hash function than any human. In this case, "secure" means that there exists no algorithm to compute a preimage faster than brute force. This would be a "nothing up my sleeve" function, in contrast to something like https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG that cryptographers would identify as sketchy. Hypothetical question: What is the Kolmogorov complexity of a secure 256-bit hash function?
unicodepepper 6y ago
Is every sequence of 256 bits a valid sha256 hash? I’m not having luck searching online for that answer.
amicin 6y ago
You might enjoy ‘Basilisk collection’. https://suricrasia.online/unfiction/basilisk/ https://suricrasia.online/unfiction/basilisk/

by p1mrx 6y ago

Closi 6y ago

I doubt that is possible with the 64 byte limit (at least making something that makes sense to read as a poem, as per the challenge).

tedunangst 6y ago
There's something like 2^59 64 byte strings that hash to all 8s. (Er, 2^168? Math is hard.)
- Closi 6y ago
  But how many of those strings consist entirely of sensical prose? Even in a string of just 4 letters, out of c500,000 combinations only c5k are a valid word. The longer the string, the smaller % of random letter combinations will happen to be valid prose.
  - MauranKilom 6y ago
    English text has about 1 bit of information per character. So there are about 2^64 different meaningful 64 character messages.
    - deleted 6y ago
      [deleted]
- MauranKilom 6y ago
  You have 2^256 possible hash values and 2^(8*64) = 2^512 different 64 character strings. So for each hash value (including the "only 8s" one) there are, on average, 2^256 64 char strings mapping to that value. Therefore (but also trivially) a random 64 character string (or any string) has a 1/2^256 chance of having all 8s in its hash. Since English has about 1 bit of information per character, there are only about 2^64 different non-gibberish 64 char strings. The odds that there exists any English phrase with an all 8 hash are 1/2^192 (i.e. zero).
  - GuB-42 6y ago
    Standard English text is around 1 bit of entropy per character, but it doesn't mean you can only write 2^64 non-gibberish text in 64 characters. For example, there are around 40k eight letter words, way more than 256. The entropy is so low because we keep using the same words, but we don't have to. We can also use abbreviations, invent proper nouns, and we don't even have to limit ourselves to English or even a single language. "犬 in French is chien, that one is Klign jr" is perfectly valid. I don't know if all 8s is possible, UTF-8 is quite wasteful for that purpose. Maybe we could take advantage of kanji. I don't know enough about Japanese, and even less Chinese, but it looks like you could make a proper noun by mashing any kanji together, including the obscure ones, and it will be usable and pronounceable. Maybe not pretty, but valid. Edit: And as a last resort, we could cheat with "password: }8pHgaQ^?7ic'6KIO!uDXQnhL3(6hcfZmRYnGUw1Pz`c?y@D"
    - MauranKilom 6y ago
      > For example, there are around 40k eight letter words, way more than 256. The entropy is so low because we keep using the same words, but we don't have to. Correct, but that low entropy is what distinguishes Monday Tuesday Wednesday Thursday Friday Saturday Sunday from (sampled from random Wikipedia article titles) Alabama Christopher List Park Girlfriend Manor crucifera or I saw your dad outside of Walmart yesterday. from (5th word of 2nd section of random Wikipedia articles) gospel Rich existed school and for Deputy he > We can also use abbreviations, invent proper nouns, Sure, make it 1.1 bits per character (the 1 bit is not a precise number anyway). That doesn't change anything about the orders of magnitude involved. > we don't even have to limit ourselves to English or even a single language. I tried to look for entropy of Chinese writing, and I've only found an upper bound of 3.8 bits per (UTF8) byte. That makes it still unlikely but at least conceivable that there is an all-8 amulet made of 64 bytes of Chinese text. > UTF-8 is quite wasteful for that purpose. Right, but as far as I understand that's the constraint. > And as a last resort, we could cheat with "password: }8pHgaQ^?7ic'6KIO!uDXQnhL3(6hcfZmRYnGUw1Pz`c?y@D" Yes, but that's not interesting from either an art nor from a computer science point of view.
p1mrx 6y ago
Yeah, my idea makes more sense if you omit the 64-byte limit; then the input can be an entire book. For an ideal hash function, every output maps to an infinite number of inputs. I don't know if SHA-256 has that property, but God could just define the simplest ideal hash function and let people cryptanalyze it.

fwip 6y ago

The more likely explanation would be that a human has broken SHA-256.

userbinator 6y ago
...and with a preimage attack, something that even MD4 --- for which collisions can easily be generated with hand calculation --- resists to this day. I'm reasonably confident that if the three-letter-agencies know of such attacks, or general techniques for doing so, they would be very quiet about it.
jtsiskin 6y ago
Yes. Or even that someone reinvented computing. Or contact from an alien race. Are all more plausible than a deity. For a proof of God I would require something without in which it really is the most likely explanation, like a face appearing on a piece of toast

schoen 6y ago

There was a religious apologetics claim, widely presented and debated in the 1990s, that there were statistical anomalies in the Torah to show that it was really written by God: https://en.wikipedia.org/wiki/Bible_code https://en.wikipedia.org/wiki/Bible_code However, the measurement technique was somewhat underdetermined, which is a problem akin to p-hacking (as you could look for many possible anomalies and only publish the ones that you successfully find). > anyone could verify that it was authored by someone with more computing power than the universe I never thought of this that way, but that's an excellent way to put it! (Although you also need to assume that the hash is extremely strongly preimage-resistant, which we don't have good mathematical techniques to prove today.) One challenge for this: what is the canonical text encoding and canonicalization, and what is the canonical hash function?

p1mrx 6y ago
Well, if I were God, I would just define a canonical encoding and hash function as part of the message. Mathematicians would study the algorithm over the years, but never find any flaws.
- readyplayeremma 6y ago
  Isn't that cheating though? By controlling the hash function you can alter the function itself until your message will meet the requirements, even though someone later on would find it impossible to compute a new message that meets the same?
  - p1mrx 6y ago
    Presumably, God could foresee the cryptographic flaws of any algorithm, and could therefore design a simpler secure hash function than any human. In this case, "secure" means that there exists no algorithm to compute a preimage faster than brute force. This would be a "nothing up my sleeve" function, in contrast to something like https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG that cryptographers would identify as sketchy. Hypothetical question: What is the Kolmogorov complexity of a secure 256-bit hash function?

unicodepepper 6y ago

Is every sequence of 256 bits a valid sha256 hash? I’m not having luck searching online for that answer.

amicin 6y ago

You might enjoy ‘Basilisk collection’. https://suricrasia.online/unfiction/basilisk/ https://suricrasia.online/unfiction/basilisk/