Algorithm to Prevent Password Re-Use

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Prelates, Moderators General

Algorithm to Prevent Password Re-Use

Postby MatthewFickett » Tue Aug 21, 2012 2:42 am UTC

Many people re-use passwords between websites, which is not desirable. Maintaining an offline (e.g. sticky note on the monitor) list of unique, strong passwords is also not desirable because it is a single point of failure (if your house burns down, or your monitor is stolen, you are locked out of all your accounts). My solution is to create and memorize an algorithm which produces strong passwords using the site name as input. This produces unique passwords for each site, without requiring me to memorize more than one meaningless string. Additionally, this has the advantage that I know my password to any given site or service, even if I can't remember whether or not I've created an account there before.


An example for a six-character password:

Code: Select all
1st: the last letter in the site name.
2nd and 3rd: the ordinal number of the middle letter of the site name (e.g., N is 14, O is 15, and so on).
4th: the symbol on the keyboard number pressed for the third character.
5th: the number of unique vowels in the site name.
6th: the symbol on the keyboard number pressed for the fifth character.


Obviously formulas can be generated which create arbitrarily long and tricky passwords. I use a nine-character one, which falls within most site limitations.

My questions:
1) I've never heard this approach described before. Is it an approach previously described?
2) If yes, is there a good reason not to use it?
3) If not, is it as good as I think it is?

Some caveats:
A) I'm not a compsci major, programmer, hacker, or even amateur coder. I'm an architect who knows a bash shell when I see it and am not afraid of statistics (but might have get out a pencil and paper to keep up). If this is obvious, my apologies for wasting everyone's time - please enlighten me.
B) I know the Correct Horse Battery Staple approach. But (a) this still requires memorizing something different for each site and (b) most sites constrain you to less than that many characters.
C) if you ever do have to change your password on a site, you need some way to adjust the algorithm to produce a second, fall-back password (ideally, an infinite number of such fall-back passwords), and a way to tell your future self to use password number two instead of password number one. I haven't solved this.
MatthewFickett
 
Posts: 4
Joined: Tue Aug 21, 2012 2:23 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby wumpus » Tue Aug 21, 2012 1:37 pm UTC

First, you will run into various exceptions (must change case, special characters must be in the proper location, must be 5 or 7 characters - not 6) that will break your password. Unique vowels also likely changes a ~6 bit character to a 2 bit one, and takes the longest to determine every time you want to log on to a rarely visited site (you might as well define it randomly as "4").

I'd recommend looking for various wallet programs. I can't say I was impressed the last time I looked, so I wrote a quick python routine that takes the name of the site (whatever I wanted to list it as), concatenates it with my master password, then runs it through SHA-2. The resulting hash is then coded into base64. Note that sometimes I have to add filler to the sitename until I get a password that meets all the idiotic restrictions.

Code: Select all
pages=[
"xkcd + seed1",
"lesser sites + seed2",
"blah + seed3",
"blah + seed4"]     # seed added due to comments below.
                           # note that adding seed is more complicated than simple editing the script (unless you intend to bash a few lines of randomly hit keys.)


for i in pages:
    j=i
    if j[-1]=="/":j=j[:-1]                 # this appears to be obsolete,
                                               #from when I was planning to cut and paste sitenames
    print binascii.b2a_base64(hashlib.sha256(j+"***master password***").digest())[:10],j
Last edited by wumpus on Wed Sep 05, 2012 12:59 pm UTC, edited 1 time in total.
wumpus
 
Posts: 380
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby MatthewFickett » Tue Aug 21, 2012 2:21 pm UTC

You're right - the exceptions imposed by different sites are a pain. I've been using this for about a year, and I only have one site for which I have to modify the formula. Maybe I'm lucky. It is a pain that the login screen doesn't tell you password requirements; I just have to remember that, e.g., my utility company doesn't allow special characters.

I'm a bit hesitant about a wallet program, or even a very short script. My main goal is to be able to carry an infinite number of strong passwords in my head (so that if my computer is stolen, house burns down, or I am stranded somewhere, I still have access to my accounts). It sounds as though for you, and most people on this forum, re-creating a python script is just as easy as memorizing my formula. I'm not quite there, and I suspect most people aren't.

Also, you're right that number of unique vowels is a bad rule. I don't actually use that in my formula, but I was trying to think of something as an example for the post and didn't think it through. Good catch.
MatthewFickett
 
Posts: 4
Joined: Tue Aug 21, 2012 2:23 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby Yakk » Tue Aug 21, 2012 2:49 pm UTC

MatthewFickett wrote:
Code: Select all
1st: the last letter in the site name.
2nd and 3rd: the ordinal number of the middle letter of the site name (e.g., N is 14, O is 15, and so on).
4th: the symbol on the keyboard number pressed for the third character.
5th: the number of unique vowels in the site name.
6th: the symbol on the keyboard number pressed for the fifth character.

Presume that the person attacking knows you are using an algorithm "like" the above, but not the above algorithm. How much entropy?

1st: The nth letter of the site name/nth last. n from 1-4 seems reasonable, and (usually) won't overlap, so this is ~3 bits of entropy, or middle.
2nd and 3rd: Another letter. A different representation. The existence of two representations (numbers or digits) gives such selections 1 extra bit of entropy.
4th: Saying "pick a previous character, hold shift and repeat it" is about 1.5 bits of entropy, give or take.
5th: counting some feature. Suppose there are 16 common features -- 4 bits of entropy.
6th: Another 1.5 bits.
5! ordering is another ~7 bits of entropy.

Total entropy: 7+4+4+1.5*2 + 4 = 22 bits of entropy. Password strength: weak (1 in 4 million from a random guess).

... now, that is a really back of napkin attempt to analyze one particular password generation algorithm. To analyze the algorithm's strength, I actually need to know how you came up with the above algorithm, rather than the details of the algorithm itself.

If you want a strong password generation algorithm, think up 2^30 to 2^40 different ways to generate a password that are easy to remember. Then pick one password generation algorithm from that set at random. Now your only problem is the ability to decode what your algorithm is from the output of the algorithm on one site, and using that to break into another.

That is the thought behind using a strong hashing algorithm, like wumpus suggested. Strong hashes are difficult to reverse, so working out what your algorithm is is hard from a password example. In your case, one could work out what your password algorithm is from a given password.

Ie, XKCD is mapped to this under your algorithm:
d03#0)
3# and 0) is a pretty simple pattern. So we can find this pattern with no idea what your algorithm is:
[a-z][digit][digit][last digit shifted][digit][last digit shifted]
4.7 + 3.3 + 3.3 + 0 + 3.3 = 14.6 digits of entropy before I know your password, or realize it has any connection to the site name. That is a ridiculously weak password -- one in 24k.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10493
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm to Prevent Password Re-Use

Postby sam_i_am » Tue Aug 21, 2012 2:50 pm UTC

This is more of a sevice-side solution, But I really like the concept of Internet Driver's license

That being said, For the multiple dozens of logins that I use, I have about 3 primary passwords, and I have a unique password for only a few things. My password has never been guessed.
User avatar
sam_i_am
 
Posts: 600
Joined: Mon Jun 18, 2012 3:38 pm UTC
Location: Urbana, Illinois, USA

Re: Algorithm to Prevent Password Re-Use

Postby MatthewFickett » Tue Aug 21, 2012 7:00 pm UTC

Yakk,

Thanks for the detailed thoughts. However, you start by

Presume that the person attacking knows you are using an algorithm "like" the above, but not the above algorithm.


But I don't presume that at all. Rather, I presume:

1) If someone wants to target me, personally, then they can just brute-force it or burgle my house or something.
2) If someone is not targeting me personally, then I am probably one of a million or so name/password combinations that just got stolen from some website.

This method is just intended to defeat case (2). In that situation, they don't even know that my passwords are derived from the site name - or anything. They look the same as the output of some SHA1-equipped script, for instance. I'm just anxious that they don't crack under attempts to, say, try all combinations of names and dictionary words, or normal letter-number-symbol substitutions. (I'm thinking of ones described in the other day's Ars Technica article ( arstechnica.com/security/2012/08/passwords-under-assault ) for instance).

Certainly if someone knows I'm using a formula based on site name, it's a bit weaker. Certainly if someone knows both that and the kind of rules I use to generate the password, it's weaker still. But it doesn't seem sensible (to me) to assume that someone does know those things. From that perspective, the password you generated for XKCD - d03#0) - doesn't seem like a particularly bad password. Unless a human is sitting down and looking at all my passwords, and trying to figure out what pattern I use, is there any reason to think this doesn't just look like a machine-generated random string?

To analyze the algorithm's strength, I actually need to know how you came up with the above algorithm, rather than the details of the algorithm itself.


For that algorithm - and the one I actually use - I just made up rules similar to those until I had enough characters. Again, my hope is that the output just looks like a machine generated password, which doesn't follow any of the usual predictions about location of capital letters at the beginning, or numbers in place of vowels in dictionary words, or four-digit years appended to proper names, and so on.

Now your only problem is the ability to decode what your algorithm is from the output of the algorithm on one site, and using that to break into another.


This does worry me. But - I hope - that's only a risk if an actual human is spending time looking at my decrypted password, and doesn't just assume it was a machine-generated string. For those two conditions to apply, it seems like we're in scenario (1) above - where I'm personally being targeted. Most things I read about password cracking is automated cracking of large batches of passwords. However, I would enjoy making the hashing algorithm better, if there's a way to do that without trying to do SHA-1 in my head.
MatthewFickett
 
Posts: 4
Joined: Tue Aug 21, 2012 2:23 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby Derek » Tue Aug 21, 2012 7:17 pm UTC

I use pretty much the same concept as you: I use the address (or other name) of the website and a "hash" function that I store and compute in my head. I also use a master password, the same for all sites, in the hash. I actually have a couple hash functions, one easier to compute and one more secure. I have a friend that has also described using a similar system, so I think this is an idea that has come up independently multiple times.

First, you will run into various exceptions (must change case, special characters must be in the proper location, must be 5 or 7 characters - not 6) that will break your password.

I have run into this problem occasionally. My hash is guaranteed to generate mixed case, numbers, special characters, and greater than ten characters long for strength requirements, so I've only had this problem on sites that force me to use a weaker password (no special characters, can't be more than 10 long). Even worse, there seems to be a (weak) correlation between sites with these stupid restrictions and sites that I actually want to have a good password for. Why are financial companies so bad at security? (My mother's maiden name is a matter of public record for christ's sake!)
Derek
 
Posts: 1669
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby Yakk » Tue Aug 21, 2012 7:51 pm UTC

MatthewFickett wrote:This method is just intended to defeat case (2). In that situation, they don't even know that my passwords are derived from the site name - or anything. They look the same as the output of some SHA1-equipped script, for instance.
Yes, the "I'm relatively immune to attacks because I am so creative" defense.

This doesn't work.

Look, you aren't that creative. What you have thought of, so will many other people, at least slight variations thereof. About the only way to make your password generating algoirthm robust is to presume that someone else gets ahold of your password generating algorithm algorithm, and from that they still won't be able to crack your password.

In your case, your password generating algorithm algorithm is "I thought it up, and thought it was neat" -- ie, something that (historically) has turned out to be cryptographically weak.

A strong way to generate a password generating algorithm is, as I have said, to generate on the order of 2^60 different password generating algorithms, all (or almost all) of which are "strong" and easy to remember, and then pick one at random and use that.

The weak point here -- how you generate the 2^60 password generating algorithms, your creativity -- is mitigated because it is then fed into a random number generator (hopefully a strong one), and a random result of your creativity is used. So even if they manage to figure out your "creative" tricks, because there are 2^60 different creative tricks you thought up, they still won't be able to crack your password.
I'm just anxious that they don't crack under attempts to, say, try all combinations of names and dictionary words, or normal letter-number-symbol substitutions. (I'm thinking of ones described in the other day's Ars Technica article ( arstechnica.com/security/2012/08/passwords-under-assault ) for instance).

You know the story of the army that was, at the start of each war, extremely well prepared to fight the last war they lost?

Dictionary words and generate-all-combination attacks are the last password war. Now attackers can build up huge databases of passwords generated by real people, and exploit the patterns that those people use in their passwords to generate password generators that match how people generate passwords.

Your mechanism -- a low entropy easily reversed password system on the url -- is a password that would be marginally stronger than typing "password" on every website against that kind of attack.

The "take a strong password, append the URL of the website, then put it through a strong hashing mechanism", on the other hand, defeats this kind of attack cold.
Certainly if someone knows I'm using a formula based on site name, it's a bit weaker.

No, it is not a "bit weaker". It is simply weak.
Certainly if someone knows both that and the kind of rules I use to generate the password, it's weaker still. But it doesn't seem sensible (to me) to assume that someone does know those things.

First, you just broadcast the fact that you generate passwords based on site names. And you did so in a way that you hoped to convince others. And others pointed out that they are already doing this.

So no, what you are doing is not rare -- but rather common. And as a common technique, people trying to crack passwords will be aware of it. So the security of your password should presume that people attacking it know the general technique you are using.
From that perspective, the password you generated for XKCD - d03#0) - doesn't seem like a particularly bad password. Unless a human is sitting down and looking at all my passwords, and trying to figure out what pattern I use, is there any reason to think this doesn't just look like a machine-generated random string?

First, as noted, as a randomly generated string, that pattern is weak. And letter-number patterns are pretty common, and something that is trivial for a cracking bot to learn when attacking a large password database, without a human involved.

It would take a pretty dumb password reversing algorithm to not notice the 3# and 0) pair. I mean, the same number twice, once with a shift key pressed? Pressing the shift key does not generate a lot of bits of entropy. To an inexperienced human, that might look random, but wouldn't to anyone who put much thought into it.

And that is the problem: you aren't going to be putting all that much (experienced) thought into it, because you aren't a cryptographic expert. You don't know what kind of patterns are common or not, or what is obvious to reverse or not.

Second, as a second-order attack, going after passwords-generated-from-URL isn't that hard.

To analyze the algorithm's strength, I actually need to know how you came up with the above algorithm, rather than the details of the algorithm itself.
For that algorithm - and the one I actually use - I just made up rules similar to those until I had enough characters.
Yep, "I'm creative, so nobody else will be creative in the same way" cryptographic defence.

This is why "security through obscurity" is not security. Because your creative rules are only strong because they are "obscure" (when they aren't actually that obscure -- and, more importantly, you have no reason to think they are obscure!)
Again, my hope is that the output just looks like a machine generated password, which doesn't follow any of the usual predictions about location of capital letters at the beginning, or numbers in place of vowels in dictionary words, or four-digit years appended to proper names, and so on.

A low enough bar allows even an ant to walk over it. :)

And yes, it isn't hard for a machine to see a letter-number combination and check the same pattern somewhere else. Or do some comparisons of your letter-number pattern to other parts of your password, or the layout of the keyboard, or the URL that the password is attached to.

About the only defence I see your mechanism providing is that of swimming faster than the guy next to you when trying to outrun a shark. Ie, the crackers having so many people with even weaker passwords, it isn't worth bothering to attack yours. This, however, is still weak.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10493
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm to Prevent Password Re-Use

Postby MatthewFickett » Tue Aug 21, 2012 8:14 pm UTC

Yakk,

You've (mostly) convinced me that my current approach is a bad plan. It didn't occur to me that anyone's password-cracking algorithms would be looking for the patterns you describe (e.g. number, then number presssing shift) but it certainly makes sense that they would. To put it another way, you say,

Now attackers can build up huge databases of passwords generated by real people, and exploit the patterns that those people use in their passwords to generate password generators that match how people generate passwords.


and I thought I was being good by avoiding what most people do. Sounds like this idea is not unique, and probably not even unique enough to avoid being on the list. (Right?)

I'm a bit of an optimist, though, so I'll push it a little farther.

You're talking about generating a large family of algorithms, and picking one randomly. If I do something like, say, generate a list of a N possible rules - "the number of consonants in the site name", "the ordinal number of the second letter," etc - and then choose X of them, and put them in a random order, would this be a reasonable approach?

The "take a strong password, append the URL of the website, then put it through a strong hashing mechanism", on the other hand, defeats this kind of attack cold.


Can you elaborate on that? I'm not sure I understand why that is true. (Actually, I'm sure I don't - See above re: my ignorance.)


Derek, you write
I think this is an idea that has come up independently multiple times.
which, unfortunately, proved Yakk's point a bit.
MatthewFickett
 
Posts: 4
Joined: Tue Aug 21, 2012 2:23 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby Xanthir » Tue Aug 21, 2012 8:49 pm UTC

MatthewFickett wrote:
The "take a strong password, append the URL of the website, then put it through a strong hashing mechanism", on the other hand, defeats this kind of attack cold.


Can you elaborate on that? I'm not sure I understand why that is true. (Actually, I'm sure I don't - See above re: my ignorance.)

It starts with "take a strong password", which means one that is resistant to brute-forcing, and then uses hashing to uniquify it for different urls without revealing the original strong password.

So, as long as your original password that you've memorized is indeed strong (it's not hard to memorize a 20char random password generated from random.org or something), then your generated password will also be strong, even if the attacker knows exactly what you're using to generate the site passwords. You can even publish the list of sites you're generating passwords for, and the exact url string you're using in your hash algorithm, and you're still safe. (I store mine in a google doc, for example, for when I occasionally forget what I used, or to see if my wife has registered for a given site already.)

Here, just go to http://xanthir.com/password, save the file locally, and then spam it around to every computer you own. If you have a server, put it up there as well. Now you have a secure password generator on every computer.

The only passwords I ever memorize are my strong password for the generator, my email password (because I use it enough that it's inconvenient to constantly generate it), and short generated passwords for logging into my machines (since I don't have access to the internet when I'm trying to boot a machine).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
User avatar
Xanthir
My HERO!!!
 
Posts: 4343
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex

Re: Algorithm to Prevent Password Re-Use

Postby Jplus » Wed Aug 22, 2012 8:45 am UTC

Just one addition: Xanthir said "20 characters" for a reason. 10 characters makes for a rather weak password, nowadays. Personally, I use a password wallet and have it generate random 24 character passwords by default. The password to the wallet (that I memorise) is even longer.
Feel free to call me Julian. J+ is just an abbreviation.
Image coding and xkcd combined
User avatar
Jplus
 
Posts: 1574
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

Re: Algorithm to Prevent Password Re-Use

Postby Yakk » Wed Aug 22, 2012 2:00 pm UTC

MatthewFickett wrote:You're talking about generating a large family of algorithms, and picking one randomly. If I do something like, say, generate a list of a N possible rules - "the number of consonants in the site name", "the ordinal number of the second letter," etc - and then choose X of them, and put them in a random order, would this be a reasonable approach?

Yes, so long as each of the X produces sufficiently distinct output.

The idea is that even if they know your password algorithm generating algorithm, they won't be able to get your password generating algorithm.

But you need your password generating algorithm algorithm (that isn't a stutter) to have a huge amount of entropy -- like 2^40 (Trillions) or more possible password algorithm outputs. For the same reason as "a password algorithm that generates high entropy passwords is secure" statistically, a high-entropy algorithm generator is secure statistically.
The "take a strong password, append the URL of the website, then put it through a strong hashing mechanism", on the other hand, defeats this kind of attack cold.
Can you elaborate on that? I'm not sure I understand why that is true. (Actually, I'm sure I don't - See above re: my ignorance.)

A strong hashing mechanism is not amenable to being reversed.

Let H be the hashing algorithm. Let P be your password. Let W be your website address.

Then we define FP(W) := H(P+W) -- FP is your password generating algorithm. Because the hash is a strong one, each of these is sufficiently distinct. Because the password is strong, the space of distinct password generating algorithms we are working over is large. And because we presumed the hashing algorithm is strong, you cannot take the output and regenerate the original algorithm.

In effect, the hash of (strong password + website address) ends up being a nearly perfect implementation of what I said needs be done to make your strategy work. And even if they know your strategy, so long as they cannot guess your strong password, they won't be able to figure out your passwords.

In effect, I farmed out the hard parts of the problem by saying "strong", to known good solutions.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10493
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm to Prevent Password Re-Use

Postby jareds » Thu Aug 23, 2012 2:07 am UTC

Yakk wrote:A strong hashing mechanism is not amenable to being reversed.

Let H be the hashing algorithm. Let P be your password. Let W be your website address.

Then we define FP(W) := H(P+W) -- FP is your password generating algorithm. Because the hash is a strong one, each of these is sufficiently distinct. Because the password is strong, the space of distinct password generating algorithms we are working over is large. And because we presumed the hashing algorithm is strong, you cannot take the output and regenerate the original algorithm.

In effect, the hash of (strong password + website address) ends up being a nearly perfect implementation of what I said needs be done to make your strategy work. And even if they know your strategy, so long as they cannot guess your strong password, they won't be able to figure out your passwords.

In effect, I farmed out the hard parts of the problem by saying "strong", to known good solutions.

Careful, careful, careful! I know you know better than to construct your own cryptographic protocols, so I assume you don't realize that's what you're doing.

A secure hash provides preimage and collision resistance. These are not the properties you are interested in (although they are of course necessary conditions). You want the output of FP to be resistant to forgery under chosen plaintext attack. (An attacker might create a website requiring login with any desired name.) This is the property provided by MAC(P, W).

Suppose that for your hash function H, there are very many strings s and t such that given H(s) and t, H(st) can be computed easily. This is the case in reality for MD5, SHA-1, SHA-256, etc. If s="<strong password>secure.com" and t="mercebank.com", then it might suck to be you.

As it happens, the hash functions I mention do a bit of padding so it might be required that t starts with a non-ASCII character. Also, you could use an ad hoc scheme to prevent this attack. However, isn't it better to use a secure MAC invented by someone other than yourself?

Disclaimer: I am not a cryptographer either, and I'm not as confident in saying to use a MAC as I would be if they were vetted for this specific purpose. Probably it would at least be nicer to do MAC(KDF(P), W), where KDF is a key derivation function, for example.

Note: Xanthir's thing does appear to use a MAC, specifically HMAC-SHA1(P, W). However, I wish to claim neither that there's nothing wrong with it nor that there's anything wrong with it, aside from the inherent limitations of the strategy (if you don't save a local copy, you'd have to re-read the source code each time; logging into a random forum on a strange computer exposes you to the same keylogger risk as logging into all your financial accounts on a strange computer; etc.).
jareds
 
Posts: 416
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Algorithm to Prevent Password Re-Use

Postby Yakk » Thu Aug 23, 2012 3:37 am UTC

*nod*, that is one of the three classic blunders. Invading Russia, implementing your own cryptographic module, and using threading Mutex primitives to write a large multi-threaded program.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10493
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm to Prevent Password Re-Use

Postby wumpus » Tue Sep 04, 2012 8:59 pm UTC

jareds wrote:Suppose that for your hash function H, there are very many strings s and t such that given H(s) and t, H(st) can be computed easily. This is the case in reality for MD5, SHA-1, SHA-256, etc. If s="<strong password>secure.com" and t="mercebank.com", then it might suck to be you.


[tl;dr]: Add salting, done.

Oddly enough, the method listed above (including my script) has the same issue that recently lead to linkedin botching its passwords. Linkedin stored H(s), where H is a strong hash function and s is a reasonably secure hash function. Alice, Mallory, or whoever the keythief is in that menagerie, then constructs a list L of all expected passwords (most likely from actual broken passwords) and then runs H(L) for all L. Alice then compares the output of H(L) to all H(s) data and saves the original password for every match.

The standard procedure is to introduce a salt r that is a random number* of roughly the size of H(s) (traditionally it was rather weak, but there is really no excuse to go small on this). While Linkedin may have millions of users, without a salt Alice need only compute H(L) once. If Linkedin uses H(sr) (where r is computed randomly per user) then Alice need compute H(Lr) for every single user, which will take a million times longer (less for smaller sites).

A password wallet should use the same (time to update my script and passwords...). Computing H(H(Lt)) (where t="mercebank.com" as above) need also be done once per site (with additional variations on t likely). Assuming that Alice lacks your wallet file, the entropy of your password is roughly max(size of hash, entropy of r + entropy of s) or roughly unbreakable. In addition, if r has as many bits of entropy as the hash output, you effectively are using a one time pad, meaning that it if Alice learns your linkedin password, she has zero information about your xkcd.com password. If Alice has your wallet file, she still has to compute H(Ltr) for you individually (but will know all your passwords in the wallet after cracking the master password).

* random number generation is another huge gap where plenty of implementations fail. Look up some of the https failures: there were plenty of recent failures due to insufficiently random numbers (4 wasn't quite good enough). Try to use something that uses a CPU instruction that is looking at thermal/other noise, or at least a routine designed for cryptographically secure RNGs.

** note that preimage attacks don't appear to be the issue. As far as I can tell, using a SHA-3 candidate that doesn't have preimaging issues will only mean storing a slightly larger state in memory as you compute H(H(L)). Alice has to compute H(L) herself, meaning that she will have the "lost state" that is needed in preimaging attacks.
wumpus
 
Posts: 380
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby snow5379 » Sun Nov 04, 2012 6:42 am UTC

Honestly does it matter? I've seen people use their name as passwords and they've never been hacked. At the moment all my passwords are random letters and numbers of arbitrary length and god damn it sometimes I have to type it in a few times because I mistype one of my 20+ character random letter and number passwords and... what's the point? Hell even top players in online games, with script kiddies constantly bombarding them with hack attempts, get along fine with a "my girlfriend's name and 2 random numbers" pass.

Also anyplace that has information worth stealing will make some attempt to protect it: lock people out for an hour if they fail at guessing a password 5 times or something. At that point the strength of your password doesn't matter much past "it takes more than 5 attempts to guess it." I could see if it's like your billing information that you're protecting but anything past that doesn't really require a hard to crack password.

God forbid someone hacks your XKCD forum password! You could get by fine with probably your name and, if no one knows it, you're fine. Hell even if someone knows it who would care enough to attempt it?
snow5379
 
Posts: 247
Joined: Tue Apr 12, 2011 6:06 pm UTC

Re: Algorithm to Prevent Password Re-Use

Postby elasto » Mon Nov 05, 2012 1:41 am UTC

snow5379 wrote:Honestly does it matter? I've seen people use their name as passwords and they've never been hacked. At the moment all my passwords are random letters and numbers of arbitrary length and god damn it sometimes I have to type it in a few times because I mistype one of my 20+ character random letter and number passwords and... what's the point? Hell even top players in online games, with script kiddies constantly bombarding them with hack attempts, get along fine with a "my girlfriend's name and 2 random numbers" pass.

Also anyplace that has information worth stealing will make some attempt to protect it: lock people out for an hour if they fail at guessing a password 5 times or something. At that point the strength of your password doesn't matter much past "it takes more than 5 attempts to guess it." I could see if it's like your billing information that you're protecting but anything past that doesn't really require a hard to crack password.

God forbid someone hacks your XKCD forum password! You could get by fine with probably your name and, if no one knows it, you're fine. Hell even if someone knows it who would care enough to attempt it?

Using simple passwords is like driving without a seatbelt or having unprotected sex: Sure, most of the time most people will get away with it. But the time you don't you'll be kicking yourself that you didn't take the simple precautions you could have.

No, it doesn't really matter if someone hacks your XKCD account. But, if they log in to your account and look up your email address - then try to log in there (and it works because you use the same password) - and then from there they order a password reset on your Amazon account (because you did use a more secure password there) - and from Amazon they order stuff to some bozo they've roped into a reshipping scam... Suddenly you could be out hundreds or thousands of dollars - or a lot of hassle at the very least.

(And don't take too much comfort from the 'five attempts limit'. It does nothing to stop offline attacks - when the hacker has downloaded the entire encrypted password database - sometimes without the site even knowing it's happened. Then, when they have it, they try to log in to every site on the net using that same username/password/email address and, if they hit, they could be in for a windfall.)
elasto
 
Posts: 1527
Joined: Mon May 10, 2010 1:53 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby sam_i_am » Mon Nov 05, 2012 6:51 pm UTC

elasto wrote:
snow5379 wrote:Honestly does it matter? I've seen people use their name as passwords and they've never been hacked. At the moment all my passwords are random letters and numbers of arbitrary length and god damn it sometimes I have to type it in a few times because I mistype one of my 20+ character random letter and number passwords and... what's the point? Hell even top players in online games, with script kiddies constantly bombarding them with hack attempts, get along fine with a "my girlfriend's name and 2 random numbers" pass.

Also anyplace that has information worth stealing will make some attempt to protect it: lock people out for an hour if they fail at guessing a password 5 times or something. At that point the strength of your password doesn't matter much past "it takes more than 5 attempts to guess it." I could see if it's like your billing information that you're protecting but anything past that doesn't really require a hard to crack password.

God forbid someone hacks your XKCD forum password! You could get by fine with probably your name and, if no one knows it, you're fine. Hell even if someone knows it who would care enough to attempt it?

Using simple passwords is like driving without a seatbelt or having unprotected sex: Sure, most of the time most people will get away with it. But the time you don't you'll be kicking yourself that you didn't take the simple precautions you could have.

No, it doesn't really matter if someone hacks your XKCD account. But, if they log in to your account and look up your email address - then try to log in there (and it works because you use the same password) - and then from there they order a password reset on your Amazon account (because you did use a more secure password there) - and from Amazon they order stuff to some bozo they've roped into a reshipping scam... Suddenly you could be out hundreds or thousands of dollars - or a lot of hassle at the very least.

(And don't take too much comfort from the 'five attempts limit'. It does nothing to stop offline attacks - when the hacker has downloaded the entire encrypted password database - sometimes without the site even knowing it's happened. Then, when they have it, they try to log in to every site on the net using that same username/password/email address and, if they hit, they could be in for a windfall.)


Generally speaking, unless you use dictionary words for your passwords, brute force guessing attacks should be the least of your worries.
User avatar
sam_i_am
 
Posts: 600
Joined: Mon Jun 18, 2012 3:38 pm UTC
Location: Urbana, Illinois, USA

Re: Algorithm to Prevent Password Re-Use

Postby Xanthir » Mon Nov 05, 2012 10:41 pm UTC

Lolwut? If the target is valuable (and, due to password reuse, frankly almost any password db is valuable), then bruteforce attacks *are* something to be afraid of. Computers just keep getting faster and faster, and you can build or even rent specialized parallel hardware for doing these kinds of attacks for cheap these days. IIRC, bruteforcing up to 8 characters is reasonable these days. This is why I generate passwords that are 20+ characters unless the site specifically prevents me from doing so.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
User avatar
Xanthir
My HERO!!!
 
Posts: 4343
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex

Re: Algorithm to Prevent Password Re-Use

Postby EvanED » Mon Nov 05, 2012 10:45 pm UTC

Brute forcing 8 character passwords (at least for weaker hashes; IIRC, this is true even for SHA-128) isn't merely "reasonable"; it's downright fast even one a single PC with a couple video cards.
EvanED
 
Posts: 4160
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: Algorithm to Prevent Password Re-Use

Postby wumpus » Sat Nov 10, 2012 10:15 pm UTC

Just in case it wasn't obvious, the whole point of the scripts included was to prevent a shady character from taking your password from a weaker site (the linkedin example is obvious, and I often logged into kuro5in.org which was later known to use crypt() to hash passwords) to something like amazon or your bank account. Determining your password from one site to the next with "proper" salt is impossible (but only if your salt is as long as both passwords and generated by observing nuclear decay, and your attacker doesn't have your personal password file).

Also it doesn't appear necessary to include separate inputs for both sitename and salt. I am still using the original python password general with just a tab or two between site name (so I can read it) and salt.
wumpus
 
Posts: 380
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby RarrRaptor » Tue Nov 20, 2012 5:02 pm UTC

Derek wrote:Why are financial companies so bad at security? (My mother's maiden name is a matter of public record for christ's sake!)

You know...you don't have to use your mother's maiden name for that. You can make up a name. That's what I usually do. If it's a form, you can put whatever you want, even if it doesn't look like a name (hash function result, whatever). I've also done that.

The bank police suspect nothing!
RarrRaptor
 
Posts: 28
Joined: Mon Nov 19, 2012 3:51 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby OrangeLemonade » Tue Nov 20, 2012 7:07 pm UTC

elasto wrote:
snow5379 wrote:[snip]
God forbid someone hacks your XKCD forum password! You could get by fine with probably your name and, if no one knows it, you're fine. Hell even if someone knows it who would care enough to attempt it?

Using simple passwords is like driving without a seatbelt or having unprotected sex: Sure, most of the time most people will get away with it. But the time you don't you'll be kicking yourself that you didn't take the simple precautions you could have.
[snip]


So you've also heard about the guy who was using a weak password on this forum and is now paying child support as a result?


But to respond to OP - as others have pointed out, just the length of your password is too short to make it qualify as anything but weak.

Personally, I'm a fan of LastPass. I actually like not knowing my passwords to things.



-O
OrangeLemonade
 
Posts: 51
Joined: Mon Nov 12, 2012 11:15 pm UTC

Re: Algorithm to Prevent Password Re-Use

Postby Derek » Wed Nov 21, 2012 3:51 am UTC

RarrRaptor wrote:
Derek wrote:Why are financial companies so bad at security? (My mother's maiden name is a matter of public record for christ's sake!)

You know...you don't have to use your mother's maiden name for that. You can make up a name. That's what I usually do. If it's a form, you can put whatever you want, even if it doesn't look like a name (hash function result, whatever). I've also done that.

The bank police suspect nothing!

Oh I'm well aware of this. But think about the typical non-security-aware user.
Derek
 
Posts: 1669
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Algorithm to Prevent Password Re-Use

Postby RarrRaptor » Wed Nov 21, 2012 5:02 pm UTC

Derek wrote:Oh I'm well aware of this. But think about the typical non-security-aware user.
Oh, I see. Yeah, that's a good point.

I don't think there's much to be done about it because most people in charge of things are like those users and don't care too much about thinking through things or delegating designs to those who actually have thought rather than the programmers who parrot common notions in the tech world.

How many IT people were misled by the default password requirement options in Windows and have thus insisted that passwords have all kinds of arcane crap in them? How many have told their relatives that the padlock icon surely means the browser programmers checked that the certification authority for a site hasn't changed since yesterday?
RarrRaptor
 
Posts: 28
Joined: Mon Nov 19, 2012 3:51 am UTC


Return to Computer Science

Who is online

Users browsing this forum: No registered users and 1 guest