How to derive a passphrase from a hash?

Question

I'd like to generate a passphrase derived from a hash fingerprint. The passphrase consists of short and human-pronounceable words from a phonetically-distinct wordlist. The derivation is a one-way function and it is acceptable for this application to lower the security against collision attacks/reduce the keyspace.

For example, a function that map 5a1138375b1c38ab49800911e6e533e2b3e60e314a042c5bca01324dc75bc710 to daycare qualified irregular plastic and that has a collision resistance as high as possible considering the reduced keyspace of the passphrase.

For this application, is it OK to use a pseudo-random number generator with the hash value as the seed to select the words of the passphrase? Are there better alternatives?

Edit: Below is a visualisation (Mathematica source) of using base conversion which is not a divisor of hash size (in this particular case $|wordlist|=5$ with 3 words derived from a 8-bit hash).

Answer 1

One possible solution is to use base conversion, and use the resulting "digits" of that base as index in the dictionary.

As that's probably a bit too abstract, so let's use some pseudo-code:

words = []
left = hexToNum(hash)
base = size(dictionary)
while (left > 0) {
    wordIndex = left % base
    word = dictionary[wordIndex]
    words += word
    left = left / base

The hash is treated as a positive number. This number is then converted to a number of digits using the size of the dictionary as base. Each "digit" (which is really just another large number between 0 and the dictionary size) is treated as index into the dictionary. Then we just perform a simple lookup and concatenate the words found.

As the left variable has a very big number value, you might have to use a "BigNum" library (a 64 bit integer would be too small). Most language or cryptographic API's will supply one. To speed things up a bit you might want to look for a function that performs divide and remainder in a single step, because that will incur fewer CPU operations than doing the division and remainder calculations separately.

As mentioned in the comments, there is no PRNG required. A PRNG is useful for seed expansion, but that doesn't seem required; only just conversion seems required. As the hash already is well distributed you can use the leftmost bytes of the hash to use fewer words.

Answer 2

You present a 256-bit hash. This has $2^{256}$ possible values. A dictionary of common, easy-to-remember English words contains perhaps $2^{16}$ words. Thus you will map each 16 bits (4 hexadecinal characters) to an English word, and uniquely identify each hash by a string of 16 words.
Example: layout retire correspondence village chapter tough election origin sacrifice disappointment blue romantic wall loose snarl
Not so easy to remember!

Your example shows a four-word passphrase. This contains $2^{64}$ bits of information. By using a 64-bit hash function, you can map each hash uniquely to a four-word passphrase. Based on OP's comments, a 64-bit hash is sufficient for his purpose.

Edit: OP wants wordlist of arbitrary length, not $2^{16}$. So, see below.

With wordlist $w$, the passphrase space is $w^4$. The cardinality (size) of the passphrase space $|w^4|$ is equal to $|w|^4$ where $|w|$ is the length of the wordlist. So, take the hash (interpreted as an integer) modulo $|w|^4$. This number uniquely identifies a passphrase.

Answer 3

The base conversion proposed by Maarten Bodewes's answer is fine to convert some of the hash into words. But it leaves aside a stated goal:

collision resistance as high as possible considering the reduced keyspace of the passphrase

There is a well-established way to increase collision resistance and premimage resistance: re-hash the hash fingerprint with a purposely slow hash as used in password-based application, such as Argon2 or Scrypt, before performing the conversion to words (by the same method as above).

If it is spent 4 CPU.second in re-hasing (about 1 second of wall-clock time on a typical desktop machine), and there are $5000$ words thus $5000^4$ word combinations, then adversaries using the same CPUs for $4\cdot\sqrt{5000^4}=4\cdot5000^2=100,000,000\ \text{CPU⋅second}$ (>1,100 CPU⋅days) have probability <40% to find a collision. This is feasible with enough resources, but a sizable difficulty.

However, finding a particular preimage (something hashing to a given value, or something different from something given but hashing to the same value) becomes truly hard: with the same kind of CPUs¹, after $(4\cdot5000^4)/2\ \text{CPU⋅second}$ (>39 million CPU.year) the probability is <40%.

Beware that simultaneously attacking $n$ preimage problems allows to solve one with $1/n$ expected work. For this reason, if possible, some salt should be entered in the purposely slow hash, such that adversaries have no benefit in targeting $n$ preimage problems with the same salt. Often, a user name/nick/email can be used as salt.

---

¹ Adversaries tackling that may want to invest huge amount of money on special-purpose devices for extra speed and power efficiency compared to normal CPUs, and then the RAM usage parameter of Scrypt or Argon2 would imply they need a controllably large amount of RAM in each device.