0
$\begingroup$

I am playing around with the following hashing scheme:

  • Start with a domain string (same for all users),
  • Allow every user to mutate it in any way defining their own custom replacement rules,
  • Append the user ID to the result of the above mutation,
  • Allow the user to choose their own "work factor" for PBKDF2-HMAC-SHA256, and use the above "salt" to hash their secret.

In the worst case, if the replacement scheme is an identity mapping, and if the user ID is empty, the salt will end up the same and this scheme will suffer from "salt clustering". If the user also did not customize their work factor, this would be a weak scheme allowing for a rainbow table attack for all users for a given domain.

However, let us assume that all three elements have sufficient variability:

  • the replacement scheme is arbitrarily complex,
  • the user ID exists,
  • the work factor is variable

In this case, how does the security of the resulting hash database for a given domain stack up against the pedantic case of choosing a salt using a CSPRNG, and hash the secret using a fixed work factor? Are their any obvious "gotchas"?

Edit: The "setup" is intended to be a one-time cost, to be used across domains, i.e., the replacement scheme will be used for multiple domains.

Edit Redux: From the discussion below, it basically boils down to the fact that as long as the input is deterministic and so is the ruleset - which in most cases will be a naive substitution - a precomputation of rainbow tables for an "intelligent" search space on the salt is possible. I will change my design accordingly.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I'm pretty sure that the usability impact of this complex scheme is bigger than the usability impact of a stronger password. $\endgroup$
    – CodesInChaos
    Dec 22, 2014 at 13:20
  • $\begingroup$ Apologies - did not make the context clear. The setup is a one-time cost. It shall be reused across domains. $\endgroup$
    – manzdagratiano
    Dec 22, 2014 at 14:44

1 Answer 1

Reset to default
0
$\begingroup$

It is too likely the input mutation reduces the search space too much as most people will input heavily lossy mutations. I know better. 99% of people don't know better.

Even the simple case of {"at"->"@", "what"->"#"} which I see as the kind of thing people will be loading, is a bad idea.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Wouldn't each new mutation require a new rainbow table to be computed? In the above simple case, there is now the need for an extra table from the base no mutation case. For example, consider common mutations a:@, o:0, e:3, l:1. A user may have up to all 4, so that there are n(4,0) + n(4,1) + ... + n(4,4) = 2^4 or 16 rainbow tables needed to crack the set of hashes. Clustering is still an issue but the burden has increased by a lot. $\endgroup$
    – manzdagratiano
    Dec 22, 2014 at 18:48
  • $\begingroup$ Yeah but the set of transforms might leak enough of the search space to cancel that. $\endgroup$
    – Joshua
    Dec 22, 2014 at 19:42
  • $\begingroup$ I see where you're coming from. Basically, it is clear that as long as the input as well as the ruleset are deterministic, precomputation of rainbow tables in anticipation of those rulesets is possible. I will consider this in my design. $\endgroup$
    – manzdagratiano
    Dec 23, 2014 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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