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

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).

-

## migrated from stackoverflow.comAug 10 '11 at 20:13

This question came from our site for professional and enthusiast programmers.

Is this a way to create passwords for personal use? (like on your bank website) or a way to 'secure' your website? –  Cpfohl Aug 10 '11 at 18:51
The idea is to use a large N. Just to make about 1 second on a standard computer. For what I understood, it is the idea behind bcrypt. –  yogsototh Aug 10 '11 at 18:56
This is a way to create password for personal use (like bank website). –  yogsototh Aug 10 '11 at 18:56

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.

-

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:

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.

-
Of course, someone using this kind of method to generate password is aware that the master password must be very strong. But as the code is open source, salting isn't useful, simply because the salt will be public. I might had problem to explain myself, but for question 2, the attacker should have access to only the sha1(str), not str. –  yogsototh Aug 10 '11 at 19:08
The random number can be kept secret like the password. It does not have to be public. But even if it was, not using salting makes the work easier for the hacker. See the Practical Cryptography book for more information. –  JVerstry Aug 10 '11 at 19:12
I didn't knew what I wanted to do is called stretching. And from what I read, it is indeed n times (in computer time) more difficult (if I use a good hash algorithm) to crack than the standard hash. –  yogsototh Aug 10 '11 at 19:14
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 same than to ask for a longer password. Am I wrong? –  yogsototh Aug 10 '11 at 19:16
@yogsototh See my update in my answer –  JVerstry Aug 10 '11 at 19:29

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).

-
As a point of reference, this guy golubev.com/hashgpu.htm is doing 5.8e9 MD5s per second on an off-the-shelf CPU+GPU box. That might translate into 1.8e9 SHA-1s per second. Better pick a strong password! –  Marsh Ray Aug 10 '11 at 21:32
The website speaks of 2.3 GSHA1/s (if that is a unit) for ATI HD 5970. Huh. –  Paŭlo Ebermann Aug 10 '11 at 21:41

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.

-

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.

-
A strong password is absolutely NOT enough to solve ALL the issues in the method described in the question. Diceware is not a complete solution at all. –  JVerstry Aug 10 '11 at 20:05
@Jverstry, sure it is. What security problem do you see that will remain problematic no matter how strong the master password is? –  D.W. Aug 10 '11 at 23:01

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.

-
This entropy loss (which is usually not that large after the initial round, but still existent) can be prevented by rehashing both salt and password in each following round, like PBKDF-2 does. –  Paŭlo Ebermann Oct 21 '11 at 0:18