How can I improve a password generation scheme based on a shared secret and URL?

Question

I currently use the following method to generate a different password on every website I have to login:

password = SHA1 ( mainPassword . domainName . number )

where . stands for concatenation.

Here are my questions:

1. Is this secure enough?
   I mean, if somebody knows my algorithm and one or many passwords, could he find easily one of my other passwords? Up until now, most people I contacted believe it is true, but I didn't get any real strong certitude.
2. (Related to question 1) When one of my passwords is compromised, I just increment the number. Is this enough?

3. Now, as many people suggested, SHA-1 can be a bit too weak and many proposed to use bcrypt or even better scrypt. But, as I understand these two algorithms, it is more about encrypting than hashing. Is it secure to use the following passwords?

   SHA1( SHA1( … SHA1( str ) … ))
   

Here is my reasoning:

• It is difficult to retrieve str, knowing sha1(str).
• I hope that to retrieve str knowing sha1(sha1(str)) one must do twice of the work.
• Therefore retrieving str from sha1n(str) should be n times as difficult than to retrieve sha1(str).

I am almost sure there won't be any proof of this. But could I consider this method safe enough?

The problem is just to have a very good algorithm similar to bcrypt or scrypt for hashes without the nightmare of finding a correct implementation in all languages I used to implement this (JavaScript, Objective-C, shell script using openssl).

Answer 1

Systems that do this already exist, such as SuperGenPass. To address your questions in order:

I mean if somebody know my algorithm and one or many passwords, could he find easily one of my other password?

Easily? No. As long as SHA1 remains a secure hash function (which is currently the case, but all hash functions have a lifetime), the only way for an attacker to determine your master password is with a brute force attack, trying every possible master password and determining if it generates the observed per-site password. Naturally, the secrecy and amount of entropy in your master password is critical in this scheme: If they can easily guess it, or find it out via other means, the attacker can generate any per-site password.

What you are trying to do, however, is better served by a construction called an HMAC. HMACs take a key and a message, and are specifically designed to resist certain attacks, and be robust even in the face of certain weaknesses in the underlying hash.

When one of my password is compromised, I just increment the number. Is it enough?

Subject to the caveats above (SHA1 is still secure, and you use an HMAC instead of just SHA1 with concatenation), yes. It's a property of a secure hash function that finding a preimage is difficult, and that there's no observable relationship between similar plaintexts, after hashing.

Here is my idea: - It is difficult to retrieve str knowing sha1(str) - I hope to retrieve str knowing sha1(sha1(str)) one must do twice of the work. - Therefore retrieving str from sha1^n(str) should be n times as difficult than to retrieve sha1(str).

What you describe is called key stretching, and it does indeed make brute force attacks more difficult. If you're going to use it, you should use an established scheme like bcrypt (uses Blowfish, as you observe), scrypt (iterates SHA1 or another hash function), or PBKDF2. Of the three, PBKDF2 is likely the simplest to implement. scrypt is newer and less tested, but purports to improve on both other schemes by making brute force attacks using dedicated hardware (which usually result in a significant speedup over using a CPU) much harder.

Answer 2

password = sha1 ( mainPassword . domainName . number ) Is this secure enough?

Answer is no. Let me explain. The only part that is really unknown in the above is mainPassword. The rest can easily be guessed by a hacker. If your original password is weak (not many characters, no digits, no specials characters), the number of combinations to test is small enough for brute force attack (i.e., testing them all). sha1 is not going to help. You are also vulnerable to collision attacks (google it for more information).

You need to learn about salting and stretching. Use a sufficiently large random number too when you salt-and-strech. Make sure you stretch with enough rounds. Salt and stretch only works if the mainPassword is good enough in the first place.

could he find easily one of my other password?

If you use a random when salting and stretching, it makes it much harder to guess another password from a known password.

When one of my password is compromised, I just increment the number. Is it enough?

Absolutely not. It is very easy for the hacker to increase the number too. You really need to use salt-and-strechting with another random number.

sha1( sha1( ... sha1( str ) ... ))

Not helping when used like that (again, learn about salting and stretching). If you are uncomfortable with SHA1, use SHA256 (or SHA512) as the hash function.

EDIT

How to keep secret the salt in an open source project? The only other way is to make the user choose the salt which seems to be exactly the to ask for a longer password. Am I wrong?

Hiding the salt is not absolutely necessary. You could also include a timestamp in the salt-and-stretching. It would require you to perform extra rounds on the server side with the timestamp. If the timestamp is too old, refuse the log on.

EDIT2

To be complete. You can implement something like that:

1. User picks a password.
2. A = any public random;
3. FOR 1 TO 1000 (or more) hash = SHA( A || hash ); with user pwd
4. Store hash on server.
5. Logon -> Server picks a new large random R and sends it to client with authentication
6. Let t = current time;
7. User verifies authentication for received R.
8. User computes FOR 1 TO 1000 (or more) hash = SHA( A || hash ); with entered pwd
9. Then, FOR 1 TO 1000 (or more) hash = SHA( R || SHA( hash || t) );
10. Send hash, R, t to server
11. Server check t is ok (for replay)
12. Server computes FOR 1 TO 1000 (or more) SHA( R || SHA( stored_hash || t) );
13. Server checks computed against received, and eventually validates logon.

It will kill many attack venues, but it is impossible to eliminate them all.

EDIT II

Sorry, there is an issue with step 8 (and 11), this step needs to be performed 1000 times (i.e., or whatever the number of salt-and-stretch iteration you need) too, or it does not make sense to iterate 1000 in step 7 in the first place.

Answer 3

The main route of attack on your algorithm is not somehow "breaking SHA-1", but a brute-force/dictionary attack on all possible values of mainPassword.

For this, using n-times iterated SHA-1 takes n-times the work as normal SHA-1, both for you and for the attacker. To make this really helpful, you should take a really high value for n - such as 2^20 or such.

The bcrypt algorithm does something similar (with an adaptable "work factor"), but it also incorporates a salt in the hash. The salt avoids that brute-forcer can make a table of all passwords and corresponding hash values, and then simply find the password corresponding to your hash: now your attacker has to make a table for every possible salt value.

In your case, the combination of number and domainname is a (weak) kind of salt. You also should add a user name in your hash, to avoid that anyone using your algorithm and password has the same hash. Still, creating a rainbow table is quite a possible thing to do here (and this is independent of how often you iterate the hash function).

So no, it is not secure. Using bcrypt/scrypt (with a suitable work factor) will be better, but this assumes you (or the website you are using) have a way to store the salt to be used somewhere (this does not have to be secret).

Answer 4

So what's the password made of: a master password, a domain, and a number.

domain is not very high entropy, particularly if someone got the resulting password from a given site. So, not strong.

number: depends on the size. A index isn't very high entropy and therefore probably not too strong. Incrementing lowers this even more if one instance has already been cracked.

master pw: who knows but it's the key to the whole thing here.

If you have a weak master pw the whole thing is weak. However a cryptographic hash shouldn't allow someone to reverse out your password without an exhaustive search.

In general you shouldn't try to come up with your own crypto schemes. Take a look at the first entry in the OWASP How to write insecure code page.

Answer 5

The security of your method depends critically on the security of your main password. As Paul pointed out, it is the major difficult element in your method. It is not trivial to find a strong password, or better a strong passphrase. I often suggest Diceware for this purpose; it takes the guessing out of just how strong your master passphrase is.

Answer 6

of course the main vulnerability remains the master password, but as you only have to remember one password now, you should be able to select a strong one.

BUT: It is not more secure to iterate a hash function on its output several times without introducing new randomness. In fact, it might even weaken your algorithm. This is easy to see if you look at SHA-1: SHA-1 maps bitstrings >= 512bit to 160bit bitstrings. If you take a uniformly random input that has >= 512 bit of entropy, you end up with at most 160 bit of entropy. For the next round you will have to use some padding and I assume this is not random. In this case the next input has still only 160 bit entropy at most and it is very likely that SHA-1 will reduce the entropy again. So if you iterate it many times you end up with very low entropy. Of course this is only theory, but it shows, that you either should introduce fresh randomness when iterating or stick with one round of SHA-1.