Don't Store Passwords, Generate Them When Needed | Hacker News Reader

Don't Store Passwords, Generate Them When Needed

16s.us

70 points16s59 comments

However, this IS a master password only with a salted hash added on top. From the FAQ it uses a phrase like "Tubby loves tacos!facebook" runs it through SHA1 and spits out Facebook's password. Someone who shoulder surfs your keyphrase can now use this technique to generate passwords for any site, whereas using something like Password Safe or the various other password storage methods would need to both shoulder surf your master password as well as obtain your encrypted password file.

It's not only been done, "master password with a salted hash" is broken. If I can convince you to log in to face.com ("Tubby loves taco's!face"), I can find the hash of "Tubby loves taco's!facebook". This is because SHA1("Tubby loves taco's!facebook") is just SHA1-sub(SHA1("Tubby loves taco's!face"), "book"). See "length extension attack" for more details.

More generally, hash functions are collision-resistant, but the output is not (pseudo)random.

That's easily fixable by using an HMAC, as the author should have done in the first place.

Does this attack actually work, by the way? Don't you need to also be lucky with the padding and have the plaintext be an exact multiple of the bytes in the round?

Yes, HMAC is (one of) the right solution(s) here. On the other hand, do you trust the rest of the program if the author gets this wrong?

The attack does work, see e.g. http://www.vnsecurity.net/t/length-extension-attack/. This example suggests that any padding should not matter; and even if it does, being able to mount this attack on a substantial part of visitors is bad. (Sorry for being vague here - I don't have the time to look at this properly now.)

What you point out here is a very implausible attack to perform. Not only would you need to know that the user is using this scheme to generate a password, you would also have to know how he generates the salt (maybe they use fb, or FACEBOOK or facebook.com). But then you'd have to be able to trick him into signing into some website with a name that's a subset of the aforementioned salt. Hell, even using FQDNs would fix the "problem" in most cases.

For the average user, a scheme like this would be a vast improvement over their "123456 is secure enough, no?"-scheme.

Putting the face/facebook start at the front of the passpphrase string would fix that. So would an HMAC.

Reversing the order is not a good idea: read http://rdist.root.org/2009/10/29/stop-using-unsafe-keyed-has... for a readable introduction (summary: it works, but it maximally exposes you to any possible problems.) Just use HMAC, especially if you want to use SHA1 - which is not broken, but no longer above suspicion.

I agree that this scheme is probably fine as long as you're the only one using it and nobody is specifically targeting you; but if you're going to go to use a password manager (which would be an improvement in general - as you point out, "123456 is secure enough, no?" is prevalent), why not use a good password manager?

I'm not sure I follow your argument. The user would provide a plain SHA1 hash (or half of one) as their password (either hex or b64 encoded). How do you plan to get the sentence out of that hash? You have no idea what the underlying sentence is. What am I missing... could you elaborate?

Edit: I think I understand what you are getting at now... what you suggest would require the use of a fully encoded SHA1_Pass generated password (not halves) and the user would have to be using a "sentence + salt" scheme where the sentence always stays the same in order for this to work in real life, right? Also, there are many other ways to use SHA1_Pass where your proposed attack would not work at all. What if they put the salt someplace in the middle? Or used entirely different sentences for different sites? How would you know?

Your edit is basically correct, but note that moving the salt doesn't help all that much (see http://news.ycombinator.com/item?id=2432014).

It's not hard to imagine some practical difficulties for an attacker. But if you're writing this kind of software, you should get it right.

HMAC interferes with my design goal of being simple and easily reproducing SHA1_Pass generated passwords on multiple platforms when needed. SHA1 was a design decision to meet that goal. To carry out your attack, you would have to:

1. Somehow know the user used SHA1_Pass with full encodings and a consistent "sentence followed by salt" scheme.

2. Somehow trick the user to log onto your malicious site using a SHA1_Pass password (or gain access to the password in some other way).

3. Somehow produce a different hash that worked on a different site the user visits.

All of that is possible in theory, but not likely to occur. SHA1_Pass generated passwords are not perfect, but they are not "wrong" either (or improper) as you seem to imply. The source is ISC licensed and available to you and others to edit. Feel free to do so.

BTW: I think I know you from @misc.

> BTW: I think I know you from @misc.

If you're talking about misc@openbsd.org, yes.

Yes, OpenBSD misc.

So for HMAC. I've looked at it more and I think your point is valid (even tho it's not very likely to occur). I may add it as an option. I don't really need to use it in the traditional sense (shared secret, integrity, etc) I only need it to better resist the length-extension attacks you point out.

Can the key and the message be the same? I'd rather not prompt the user for a base sentence and a key/salt. But I can't find anyone using HMAC where the key and the msg are the same. I thought you might have some insight into this.

Edit... here is a traditional HMAC (I think):

echo -n msg | openssl dgst -sha1 -binary -hmac key | openssl enc -base64

Here is how I would need to use it without changing functionality:

echo -n msg | openssl dgst -sha1 -binary -hmac msg | openssl enc -base64

I'm not sure this is proper from a cryptographic perspective.

I got advice from some guys on sci.crypto about how to potentially handle this. Some smart guys on that list. So I'll probably incorporate HMAC as an option for those who wish to use it.

I've been using HMAC-SHA1 as a basis for my passwords for awhile. I call my algorithm "Passy". It works like this (pseudocode'ish).

    # generate our HMAC
    hash = generate HMAC-SHA1 (facebook.com, passphrase) (String)
    hash += SHA1(hash) # just need the extra length
    
    # transform hash into a Passy
    passy_chars = "ABCDEFGHabcdefgh23456789#$%*+=@?"
    passy = ""
    foreach octet in hash (starting with MSB)
      passy += passy_chars[octet % 32]

    # figure out the length of this passy
    for i in 16 to passy.length
      if passy.substr(0,i) is "good", return passy.substr(0,i)
        where good means includes at least one from each of [A-H], [a-h], [2-9], and [#$%*+=@?]

I've implemented this in CoffeeScript, and have a minified version up here: http://dl.dropbox.com/u/11596/passy-tiny.html

I have evolved this algorithm over the past decade. My requirements:

  1. minimum of 80 bits of entropy (16*32=80)
  2. must include at least one symbol, one uppercase, one lowercase, and one digit
  3. base it on cryptographically secure hash algorithms
  4. avoids confusing similar symbols O and 0, l and 1 and !, etc.

I realize that requirement #2 does nothing to increase entropy. It's simply there to satisfy (idiotic!) password requirements.

With any of these systems, your generates passwords are still only as good as a) the strength of your passphrase, and b) the secrecy of your passphrase. As well as the obvious (physical security, keyboard sniffers, etc.)

I use a mnemonic algorithm to generate site specfic passwords instead, but this is _really_ nice. Do you happen to have the source on github, or would you mind putting it up there?

Sure, it's here: https://bitbucket.org/swaits/passyweb

It's not documented other than with comments, although I think the code is readable. You'll find test vectors in the source.

And, thanks!

I use passwordcard (http://www.passwordcard.org/en) as my password manager,

1) All my passwords are stored on a piece of paper, in plain text. There is no need to encrypt, because only I know how I use it.

2) I don't need to back it up regularly. Just one backup, in case I lose the card, is enough.

3) Because I have to type in the passwords from it, I actually remember the ones I use regularly, so even if I lose the cards, I can log in to most things.

4) There is no "master password" to be exposed.

5) If I'm stupid enough to read it out loud, or run my finger along it whilst someone is watching, I might expose the parameters of one password, but everything else is still secure.

6) It is a piece of paper, the browser integration goes via my eyes and my fingers.

Variation on that theme: http://blog.jgc.org/2010/12/write-your-passwords-down.html

I did an implementation of it (http://www.loup-vaillant.fr/projects/password-generator)

Here is what I do:

  require 'digest/sha1'
  puts "doubly troubly"
  thing = gets.chomp
  base = Digest::SHA1.hexdigest(Digest::SHA1.hexdigest(thing))
  puts base
  puts base[0..3] + "^!!^E" + base[4..-1]
  puts base[0..3] + "^!!^E" + base[4..6]
  puts base[0..3] + "^!!^E"

For any site I input the domain (so "zach.tumblr.com" + my_salt would be inputed) then I copy one of the four outputs based on what security level I think the site deserves. THEN (and most critically) I add a password that rotates key characters based on factor X of the site. Think about this like a normal password, but it changes.

I then expose this little piece of code on every one of my computers as well as on a protected server that lives only on an IP.

I 100% agree with this article, but I have my own system and it works well.

You might as well switch that to a proper HMAC. Check out HMAC::SHA1.digest

Indeed. I rolled my own UI for doing this with HMAC because everything else seemed to be implemented with cargo-cult voodoo (I just read the SuperGenPass FAQ again to check... MD5 10 times? WTF? If 1 is not enough why are you using it? No personal offense meant to whoever wrote SuperGenPass, but it's not what I wanted. As for the parent comment... I don't know what to say).

Shameless self-promotion link, if interested: https://chrome.google.com/extensions/detail/mjafhhefmkfchamf...

How is remembering the pass-sentences different from remembering passwords?

Generally speaking, it's easier to remember a sentence that makes sense to you than an arcane sequence of letters, numbers, and symbols.

You can even this up, of course, with mnemonics and such, but a sentence like "I have got to get me one of THESE!" has less "mental entropy" than "aem1eePe{a".

I'd say an "easy-to-remember sentence" also has lower (actual) entropy than "an arcane sequence of letters, numbers, and symbols". If an attacker knows you're using this password-generation system, she will probably try brute-forcing your passphrase, not the password it generates.

I don't see how this is any more secure than having a normal password -- it's just security by obscurity. And in some sense it's worse, since you're led to believe these SHA1 passwords give you the same security as standard, locally-stored generated passwords.

I'd have to think more about this particular tool, but I remember seeing some calculations that passphrases have greater total entropy than random passwords, even if it takes more characters to get the same amount of entropy.

Generally speaking, I go with the mnemonics, myself, rather than something like this.

There are about 50,000 commonly used words in English.

That means that each word has an entropy of about 15.6 bits. (Probably less since some words are far more common than others.)

Using a typical 4 word phrase gets you about 62 bits of entropy.

In contrast a password can select from a set of about 72 characters. i.e. 6.1 bits per letter. Using an 10 character password gets you about 61 bits of entropy.

So they seem reasonably comparable.

It would be nice to redo the calculation while accounting for how common each word is, and also that special characters are used less often in passwords.

Could you help me understand your reasoning/calculation?

I'd like to verify it with my expectations for a passphrase:

- not-so-common (non-)words (think meme, Shakespeare style English, abbreviations/artifical words -> Jedi, Klingon, whatever) - I'd like to understand how to valuate punctuation: You don't just need to guess the passphrase, you might need to pepper it with commas, quotes, dots, question/exclamation marks at the right spots

Punctuation adds to the entropy of course. Although if there are only 5 of so symbols it doesn't add a lot, and if the punctuation is placed grammatically correctly it hardly adds anything.

It's not a problem to include non-english words in your dictionary. But made up words are basically passwords, and are no longer phrases.

If you choose a sequence of words that are more likely to go together that reduces the entropy.

Basically you are trying to see how random your phrase is, and the "stranger" it is, the more random.

So they seem reasonably comparable... It would be nice to redo the calculation while accounting for how common each word is, and also that special characters are used less often in passwords.

I know this was a rough estimate, but I think it is way, way off. Passphrases are not usually generated by random choice of English words but are instead a particular, meaningful English sentence.

This means not only are you dealing with word distribution nonuniformity but word history correlations. Without doing any math in particular, let's pick a typical 4 word phrase (literally, I'm opening the book in front of me and looking for a 4 word sentence.)

   "This will be natural"

In all honestly, this is closer to a combination of a subject (with a great deal less entropy since familiar subjects are common) a tense, and an adjective. I think you'd be lucky if there were 2^18 sentences of similar complexity, let alone 2^62.

In comparison, four random words drawn from an English dictionary.

   "idiocy rammer stars cookshop"

Passphrases of this class might have closer to 62 bits of entropy.

So what does this mean? In all likelihood, if passphrases become more common, we'll see language model based cracking routines which generate billions of sensible English sentences to crack these passwords.

Length is no protection ("abcedfghijklmnopqrstuvwxyz1234567890"). Anything with genuinely high entropy is by definition difficult to remember.

I quite agree. I just don't have any easy way to calculate it.

Bruce Schneier goes with 1.3 bits of entropy per character of general English text in Applied Cryptography.

> Anything with genuinely high entropy is by definition difficult to remember.

This wording bugs me a bit, but I'm not quite sure why. I think it has something to do with the time my friend's bank, which only issued random 4-digit PINs for their ATM cards, assigned my friend the PIN 4444. Theoretically, it was just as tough to guess as any other password, but it was really easy to remember.

Passwords are not "security by obscurity".

No. The difference between passwords and this is.

The "obscurity" is the idea that an attacker would not know that you were generating your passwords by SHA-1 hashing a passphrase.

If the attacker did not know that, they could only brute-force your account by trying every possible string of characters, which is fine, because there are a lot of those. If, however, they knew what you were doing, then they could generate a list of likely-seeming passphrases, hash those, and try those hashes as passwords. If there are fewer likely passphrases than there are strings of characters, this shrinks their search space. Also, once they know you're using passphrases, they might also know that some phrases are much more likely than others, so they could try those first. This would give them a good chance of finding your password even more quickly.

So, basically we've just recreated http://supergenpass.com/ which has been around for at least a decade. And I'm sure the idea is older than that.

What happens when the generated password doesn't meet the strength requirements for the site (too long/too short, not enough/too many numbers, not enough "special characters")? Or when I'm required to change my password periodically?

The way I was going to handle that when I designed my own password generator to replace my encrypted text file of passwords was to store a version number of each site. The version number would be part of the input to the hash. Changing the password for a site then would just require changing the version number.

Requirements and restrictions on the password content could be handled similarly, by storing password formatting information for each site.

I never got around to implementing my system, because I got a fantastic deal on 1Password (via MacHeist) and my system became completely pointless.

SuperGenPass has a serious DOM vulnerability. The link has a live demo.

http://akibjorklund.com/2009/supergenpass-is-not-that-secure

The SuperGenPass UI is rendered within the DOM of the current page when you click the bookmarklet. The UI is where you enter your master password. And because the UI is part of the current page, any script running in the page can read your master password. Remember that script can be external too, as in advertisements or widgets of some kind.

My solution is to use Keepass. It stores passwords in an encrypted database file which I store in Dropbox - that solves the machine synchronization problem.

The main database is protected by a passphrase and/or keyfile (any file which won't change e.g. ~/Dropbox/Photos/2008/France/Photo5.jpg). One advantage of this is that a simple keylogger will be stumped by the keyfile - even if your passphrase is recorded an attacker still needs Photo5.jpg to decrypt the database.

It's originally a Windows app (http://www.keepass.info/), but is open-source and there's a fully featured Linux/OSX port called KeepassX (http://www.keepassx.org/)

I've tried a technique like this, it works wonders if you are near a computer and can copy/paste. As soon as you have some flash login box where you can't paste or you try to log in from your iPhone it becomes extremely painful.

Better to use the age old technique found in "Unix System Administration" by Evi Nemeth: Choose a well known phrase or poem or song lyrics. Then pick a letter from each word, and interpolate some weird chars. E.g.

Yellow Submarine In the town where I was born, Lived a man who sailed to sea...

First letter of each word: IttwIwbLamwsts then interpolate stuff, e.g. "IttwIwb$beatles1968$Lamwsts"

Still a pain in the ass to type, but not nearly as painful as a SHA1 or base64 string.

http://clipperz.com rocks in terms of usability, convenience, and a sense of security (which might be false: here is a call for criticism).

It is open source, portable (runs in Javascript), works on and offline and well designed. You can log in using a master passphrase, or a one-time password.

I use the same scheme with minor variations. The most annoying thing is "secure password requirements" ("your password must have digits", and it happened that generated one didn't have a single digit) or limits (I'm fine with encoding-agnostic 7-bit-ASCII-only, but "8 chars max" or "may only contain alphanumerics" frustrate me) on some sites, which force me to step away from this scheme.

In fact, there are way too many exceptions out there in the wild. One still needs a notebook of some sort for such cases.

Also, the last time I've logged into Bitbucket (I [almost] don't use it, but I have the account) I forgot that I logged there using OpenID instead of login-password pair. :)

"And by the way, if after reading this you still wish to use a traditional password manager, I suggest that you put your passwords into a plain text file and encrypt it with GPG or use Password Safe."

Having recently had some significant trouble with a lost online banking password, I've been thinking about keeping all my passwords in an encrypted file stored in various places (I don't like the idea of using a password manager, because it's difficult to move it across platforms). Is this sensible from a security POV? Which is the best encryption to use and is there a standard *nix tool for it?

PGP (http://en.wikipedia.org/wiki/Pretty_Good_Privacy) which GPG uses is the standard *nix tool for encryption.

Depending on your needs, you could also have a look at TrueCrypt (http://www.truecrypt.org/)

You can use keepass which is open source and cross platform.

http://keepass.info/download.html

It's much more convenient than a text file you cipher and decipher and it's more secure as well. A text file is prone to error (wrong copy/paste, forgot to cipher the file, etc.)

> I don't like the idea of using a password manager, because it's difficult to move it across platforms

http://clipperz.com is a very portable password manager.

It works on your computer as well as online.

It relies on your browser being a "secure" Javascript interpreter. But then we do that every time we log into a web site.

Sometimes I wonder why we don't use certificates more often. Nowadays a lot of people have a laptop or other mobile device so you need only one installation.

Maybe give users a choice: password or certificate.

Another alternative is PasswordMaker. Works on hashes and provides local applications as well as browser extensions: http://passwordmaker.org

The last time I checked, PasswordMaker generated passwords using sites' top two domain labels ("example" and "com"). But for sites' with country code TLDs, PasswordMaker would generate passwords using "co" and "uk", thus sharing the same generated password for all .co.uk sites!

You can select which parts of the URL should be used to create the password. Subdomains and even port are possible to select, too.

I'm confused. Can I get a real-world example out of this?

I think the idea is that you remember a pass phrase, and the encryption type...at which point the program spits out a large hash string. The hash string gets used as your password wherever you need it, but all you need to remember is the pass phrase.

Ok, thanks for that. But as a User, why should I care? This would p*ss me right off.

This page shows it in action: http://16s.us/sha1_pass/

I actually do something similar but far simpler that I can do mentally.

I am still screwed by some passwords I rarely use because either

It a password that needs to be changed regularly and I forget where I am in the sequence.

The app had stupid requirements like the password has to be exactly 8 characters. Of course I truncate the generated string but never remember its truncated when I come back.

I appreciate all the discussion and opinions. I wanted to mention, too, that the source code is also on github for those interested: https://github.com/16s/SHA1_Pass

This is a variant on hashapass.com

the encryption used to store passwords is rarely the problem, the strength of passwords and users remembering them is.

HMAC-SHA1 has been added to BETA2.

SHA-1 is insecure. Use SHA-256 or SHA-512.

Wonder why people are downvoting this. SHA-1 being insecure is not something that is up for debate -- it is fact:

"SHA-1 is the most widely used of the existing SHA hash functions, and is employed in several widely-used security applications and protocols. In 2005, security flaws were identified in SHA-1, namely that a mathematical weakness might exist, indicating that a stronger hash function would be desirable."

"Earlier this week, three Chinese cryptographers showed that SHA-1 is not collision-free. That is, they developed an algorithm for finding collisions faster than brute force. SHA-1 produces a 160-bit hash. That is, every message hashes down to a 160-bit number. Given that there are an infinite number of messages that hash to each possible value, there are an infinite number of possible collisions. But because the number of possible hashes is so large, the odds of finding one by chance is negligibly small (one in 280, to be exact). If you hashed 280 random messages, you'd find one pair that hashed to the same value. That's the "brute force" way of finding collisions, and it depends solely on the length of the hash value. "Breaking" the hash function means being able to find collisions faster than that. And that's what the Chinese did. They can find collisions in SHA-1 in 269 calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology. Two comparable massive computations illustrate that point."

"It's time for us all to migrate away from SHA-1. Luckily, there are alternatives. The National Institute of Standards and Technology already has standards for longer -- and harder to break -- hash functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already government standards, and can already be used. This is a good stopgap, but I'd like to see more."

Reply on news.ycombinator.com