0

The question I am asking is: is there some reason why the following method does not make it significantly harder for an attacker trying to brute force the input (or using a dictionary attack)?

This question is perhaps not entirely practical, but is inspired by the idea of bcrypt, but without needing to actually implement bcrypt when you have SHA handy. To put it in context, I tend to use a method of string manipulation and hashing to generate passwords for websites. Basically, you take some secret string, say, TheNameOfMyLongDeceasedHamster, append something obvious to do with a website TheNameOfMyLongDeceasedHamsterFacebookUserMrBoink put that through something like SHA256, take binary output, convert to base64, and take the first 16 characters. I figure one will find it difficult to get the secret string even if you know the output of this process and the site specific input. I've pondered a simple method of making it more computationally expensive, since it is no loss to take say 0.25 seconds on an i5 laptop to compute a single hash in javascript, but naturally if someone wants to try and find the TheNameOfMyLongDeceasedHamster given the output of this (and possibly search/replace pairs) and perhaps some kind of dictionary attack, this makes it all the harder to try.

The idea is a little naive, and I'm wondering if there are any serious drawbacks that security experts know of?

The idea is as follows:

Step 1. Take a well known text (something you can easily find). For me, I take the Latin Vulgate of the Sermon on the mount, remove all punctuation, convert to lowercase and split into separate words. This yields an array like

["videns","autem","jesus",...]

and it is assumed any attacker has access to this text. Importantly I only need to remember how to reconstruct it.

Step 2. Specify a number of pairs of words, e.g

var wordsmap = "in:humpty et:dumpty cum:hmmm";

and convert to the form

var wordsmapa = ["in:humpty","et:dumpty","cum:hmmm"];

and then replace via

var fluff = "videns autem jesus ...";
for(i in wordsmapa) {
   fluff = fluff.replace(wordsmapa[i][0],wordsmapa[i][1]);
}
fluffwords = fluff.split(" ");

to get

["videns","autem","jesus",...]

where some words may have been replaced. (The replacing bit is optional, but has uses, e.g. if I change 'jesus' in the string to whatever my username is, just bunging 'SecretStringtwitter' through this process will yield what looks like a nice strong password for my twitter account, e.g. 'lG0aFybg0/zGLPCO'.)

Step 3. Take a hash function, such as sha256, and iterate (it is of course important/useful to ensure everything is uniformly e.g. hex strings or byte buffers)

function hashcascade(x) {
    for(var i=0,l=fluffwords.length; i < l; i++) {
        var w = fluffwords[i];
        t = hash(t+w);
    }
    return t;
}

so to use we do

secretstring = "TheNameOfMyLongDeceasedHamster"; // obviously this will not be in plaintext in the source, but taken from the user somehow
specificinput = "FacebookUserMrFluff";
hashinput = secretstring + specificinput
hexout = hashcascade(hashinput)
binout = hex2bin(hexout)
b64out = btoa(binout)
result = b64out.substr(0,16)

As such, take the first 16 characters from the base64 of

hash(hash(hash(...hash("SecretStringSpecificStringvidens")+"autem")+"jesus")...)

Is there some reason why this does not make it harder for an attacker trying to brute force the input (or using a dictionary attack)?

Finally, used this way, any change to the secret string totally changes the output, as does any search/replace on the 'known text' used to generate the word array.

I am toying with this method do create/recreate passwords, so as to have a concise zero-storage password manager, relying on memorising a single secret string, using some intuitive guess for what the word replacements should be, and then something obvious like the domain name of the website. Put all this through the above procedure, and say 0.25 seconds later, out comes your password.

  • Out of curiosity, why is humpty dumpty involved in freaky things? – Mark Buffalo Aug 23 '16 at 23:49
1

I'm very confused by your question, because on the one hand you mention bcrypt, a password verification algorithm:

This question is perhaps not entirely practical, but is inspired by the idea of bcrypt, but without needing to actually implement bcrypt when you have SHA handy.

...but then it switches gears to password generation:

To put it in context, I tend to use a method of string manipulation and hashing to generate passwords for websites.

But these are unrelated problems, so a solution for one isn't necessarily applicable to the other.

But in any case, as far as I can tell from your explanation, you are proposing a system for generating derived passwords deterministically from these inputs:

  1. A secret master password;
  2. A public identifier for the derived password (e.g., FacebookUserMrFluff);
  3. Some additional public parameters (the word list and the substitutions).

One problem here then is that, because the scheme is completely deterministic, an attacker who is able to get a hash+salt pair for one of the derived passwords (or a plaintext password from a site like any of these) can then mount a brute force attack to recover your master password. And if they succeed, they can then compute all of your derived passwords—past, present and future.

Maybe iterating the hash function many times raises the cost of the brute force attack against your scheme. But why allow such an attack at all? Compare to this commonplace bit of user-side password management advice:

  • Use randomly generated passwords of good length;
  • Store them in an encrypted password manager.

In this case, since the passwords are randomly generated, they're all independent—an attacker who cracks one of them cannot leverage that to figure out any one other password. An attacker would need to steal your password database to launch a brute force attack against your other passwords—whereas in your scheme they just need a single derived password.


Other than that, if you "have SHA handy" there is already a standard iterated password hashing solution for that: PBDKF2. So even if you insisted in using this questionable method for generating deterministically derived passwords, there is no need to resort to your odd algorithm.

  • 1
    I think he's chosen this algorithmic approach because it has no database. But he's ignoring the extremely heavy weight of his algorithm, which requires custom code to be stored and executed. The tradeoff also includes the security issues you raised. – John Deters Aug 24 '16 at 1:35
  • Thanks for noting that. That is the problem I am playing with: assume I have no access to an encrypted store, but want to be able to easily recreate my passwords, but make it hard for an attacker, allowing for a certain degree of memorisation (and as little specific to this task as possible). – John Allsup Aug 24 '16 at 20:16
  • The amount of custom code, assuming the words, after any replacements, reside in the file "words.txt", is the following short bash script: WORDS=(<words.txt); X="$1"; for a in "${A[@]}"; do; X="$(echo -n "$X$a" | sha256sum | cut -c1-64 | xxd -r -p)"; done; OUTPUT="$(echo -n "$I" | base64)"; echo "${O:0:16}" – John Allsup Aug 24 '16 at 20:18
  • The manipulations on the words can easily be accomplished via sed, awk or tr. This means, for me, there is an easily memorised procedure (and the first 5 verses of John's gospel in the latin vulgate I can easily type out from memory) to recover the unmodified word list, and provided the word modifications are easy (e.g. pipe through sed -e 's/erat/amazon/g' -e 's/principio/my.user/g'), we have a hash function which is expensive to brute force. – John Allsup Aug 24 '16 at 20:23
  • Finally, I tend to stick the string "MrFlibble" through such a system, and memorise the first three or four digits of the output so as to quickly verify it is set up correctly. Importantly, I needn't write anything down to use this, only have access to a standard Linux command line to replay the procedure from memory. There is sufficient flexibility to use this to generate a vast array of passwords using intuitive 'first guesses' as guide. An attacker has to brute force, say, 300 sha256 hashes in succession, inputs of each being the outputs of sha256, so not likely to be aided by a dictionary. – John Allsup Aug 24 '16 at 20:30

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.