Hacker News Reader

Comment by p1mrx | Hacker News Reader

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.

View on HN

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

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?

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.

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?

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 that cryptographers would identify as sketchy.

Hypothetical question: What is the Kolmogorov complexity of a secure 256-bit hash function?

Hence God must have computational power greater than a Turing machine, at least if he wants to prove His hash function minimises Kolmogorov complexity.

For a rough upper bound, there are some examples at [0], which could be less than 100 characters of C (once golfed).

[0] https://stackoverflow.com/a/14409947/5327391

You might enjoy ‘Basilisk collection’.

https://suricrasia.online/unfiction/basilisk/

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

There's something like 2^59 64 byte strings that hash to all 8s. (Er, 2^168? Math is hard.)

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.

English text has about 1 bit of information per character. So there are about 2^64 different meaningful 64 character messages.

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

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"

> 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

    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.

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.

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

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

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

Reply on news.ycombinator.com