I'm curious about the implications of cryptography and the generation of natural text (i.e using Markov chains), and I am wondering if there has been any cryptographic protocols that involved generating a document key with legible English-language words from a user-supplied password (maybe hashed, or went through some one-way function). For example:

E(sha256(password)) = DocumentKey

If not, is there any proposed way of accomplishing something like this?

  • $\begingroup$ So you want the DocumentKey to be legible English words and to function as the key for an encryption algorithm? Or you want the password to consist of English words? $\endgroup$ – Ella Rose Jul 19 '18 at 3:27
  • $\begingroup$ @EllaRose the password should be user-specified, like "testpassword123". The function is what takes that password, and generates a document key - a set of legible English words. $\endgroup$ – alcao758 Jul 20 '18 at 1:34

If I had such problem, I would operate as follows:

  1. Obtain a list of 8192 different words. Then the $x$-th word of this list is denoted by L[x] (where $x$ is a natural number in decimal).
  2. Given any bitstring (hash of the password), split it into 13-bit parts. Denote an $i$-th part by N_i.
  3. The sequence of words is L[N_1] L[N_2] L[N_3] ....

For example, SHA3-512 online web app shows that SHA-3-512("MyPassword") starts with the following bytes:

35 c6 36 f4 40 b7 d7 40 7a ...

Converting this hash to a binary form (byte after byte) and splitting into 13-bit parts yields the sequence

0011010111000 1100011011011 1101000100000 ...

Converting each part from binary to decimal yields

L[1720] L[6363] L[6688] ...

If the list is taken from Wiktionary:Frequency_lists/PG/2006/04/1-10000, the resulting sequence of English words would be

admit billion lists ...

if we assume that 13 zero bits correspond to the last word of the list. If we assume that 13 zero bits correspond to the first word of the list and 13 set bits correspond to the last word of the list, then the resulting sequence of English words would be

supply shorter gallop ...
| improve this answer | |
  • $\begingroup$ Has there been any cryptographic schemes / protocols that have implemented the same or a similarly proposed algorithm? $\endgroup$ – alcao758 Jul 20 '18 at 14:45
  • $\begingroup$ ... and also, if the document key is public knowledge, how can offline attacks be prevented? $\endgroup$ – alcao758 Jul 20 '18 at 15:16
  • $\begingroup$ This scheme is as strong as the underlying hash function, assuming that all it does is convert a bitstring (the output of a hash function) to a sequence of words in any natural language so that the result can be converted back to the original hash. There are no other goals for the above algorithm. Note that if the scheme is 13-bits-oriented, then the maximum number of words that can be extracted from a 512-bit hash is 39 (507 bits of input). It is possible to use 16-bits-oriented scheme, then any 512-bit hash will correspond to a sequence of 32 words. This will require a list of 65536 words. $\endgroup$ – lyrically wicked Jul 21 '18 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.