3 ms·

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).

by Closi 6y ago

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.

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).

by 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.