2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I am not sure if the term keyspace can be used for hash functions. Feel free to comment/edit if there is a better terminology. $\endgroup$ – DurandA Apr 23 at 23:43
  • $\begingroup$ Do you want an algorithm to suggest hash/prng based passphrases to users? $\endgroup$ – Maf Apr 24 at 8:52
  • $\begingroup$ @MoisésFerreira The algorithm I am looking for is a one-way function that converts a hash to a passphrase. E.g. "5a1138375b1c38ab49800911e6e533e2b3e60e314a042c5bca01324dc75bc710" to "daycare qualified irregular plastic". $\endgroup$ – DurandA Apr 25 at 13:04
  • $\begingroup$ Let me see I got your point. You have already got the hash value (eg. taken from a CSPRNG), now you just want an algorithm to convert this hash value to its corresponding passphrase, right? $\endgroup$ – Maf Apr 25 at 13:33
  • $\begingroup$ I've just seen in your last paragraph that you want a PRNG with the hash value as the seed to select the words of the passphrase. How do you intend to use the hash value as the prng seed if you don't have the hash yet? where does the referred hash come from? $\endgroup$ – Maf Apr 25 at 13:40
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Paragraph "As we're..." is irrelevant; OP didn't even mention a programming language. I won't edit it out in case you disagree, but I would recommend doing so. $\endgroup$ – Adrian Self Apr 25 at 17:06
  • $\begingroup$ Isn't this solution weakened if the wordlist length is not a power of two? $\endgroup$ – DurandA Apr 25 at 21:11
  • 1
    $\begingroup$ No. Some words may be less frequent than others, but the solution is a simple conversion: you can simply convert back to the same hash. The word list is only a 1:1 representation of the hash, in other words. Adrian's answer does exactly the same, but for a word list with a size that is a power of two. Slightly more efficient, but you'd have to scale your list somehow. Can you read Java? $\endgroup$ – Maarten Bodewes Apr 25 at 21:17
  • $\begingroup$ @DurandA As already indicated by Adrian, if you already have a hash over something then it is usually not required to perform another PRF on it. But nothing prevents you from calculating a hash over a hash and then follow the solution... $\endgroup$ – Maarten Bodewes Apr 25 at 21:21
  • 1
    $\begingroup$ Then take 64 bits of the hash and perform the solution. Or hash it, take 64 bits and then perform the solution. I don't see how that changes anything. $\endgroup$ – Maarten Bodewes Apr 25 at 21:24
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ That is to say, what are you using it for? $\endgroup$ – Adrian Self Apr 25 at 20:58
  • $\begingroup$ What is the application of this hash? The goal is to authenticate self-generated certificates in a WebRTC application from their fingerprint. I assume 2^64 bits is enough as the certificate is always re-generated and only stays valid for a short period of time (<5 minutes). $\endgroup$ – DurandA Apr 25 at 21:00
  • $\begingroup$ Sounds good. Can you respond to the last bit of my answer, then I can edit to a finished response. $\endgroup$ – Adrian Self Apr 25 at 21:08
  • $\begingroup$ It is not required to make it impossible to go from the passphrase to the original fingerprint. The only requirement is that it should be very hard (=2^63 on average with the given example) to generate a certificate that matches the passphrase. $\endgroup$ – DurandA Apr 25 at 21:19
  • $\begingroup$ There are two different hash attacks which you may be describing. Is it true that an attacker must not be able to find two certificates with the same signature? Or is it only necessary that, for determined signature X, the attacker must not be able to find another certificate that matches X? $\endgroup$ – Adrian Self Apr 25 at 21:32
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.