Re-hashing a hashed password

Question

Assumed knowledge
Hashing, Salting, PBKDF[1-2]

Problem
I am storing passwords in my database using a scaled hashing/salting algorithm like PBKDF2. I thought 'Hey, if i hash my passwords 20000 times, that should be secure enough against brute force attacks right?' and its true. until next year when better computers come out.

Possible solution

Leaving aside the issue of encryption key length, and salt length (which can be incorporated into this solution as well) I thought, what if every N days, i re-hash all the passwords in the database. So they are hashed 20,000 times, then a week later, i hash them a further 500 times, making them a total of 20,500 times. Store the number of times it has been hashed in the database somewhere. The idea is to increase the hash count as technology progresses.

Existing similar implementations
BCrypt introduces a work factor to increase time taken to hash a password:
PBKDF2 uses a number of iterations to do the same thing. This is used by Mac OS-X, windows and linux for file level encryption. Wi-Fi networks also use implementations of it.

Can anyone see a problem with this? Has this already been tried? Is there an algorithm out there that accepts a pre-hashed password and re-hashes it 'N' times?

Edit
The question is not if multiple hashing is secure (this has been tried and tested). The question is around re-hashing to increase security without having to make the users re-set their passwords

Solution: courtesy of discussion with JVestry

So re-hashing all the passwords every 'N' days is a waste of time since the hacker can just crack it by using an old copy of the database. However, if you combine the concept of increasing the hash count over time to a password renewal policy, the concept is sound.

Implementation
All passwords expire every 30 days. When they are renewed, their hash counter is increased. So a password reset yesterday will be harder to crack than one set 20 days ago. Hash counter can either be stored or derived from an algorithm using the last modified date.

Thanks!

TTD

Answer 1

Can anyone see a problem with this?

Yes. Assuming that you would rehash weekly with the salt (which I believe is what you mean), there is still an issue. If someone manages to have access to a hashed password at week x, then any further hashing at week x + n does not provide any extra security.

The hacker only has to work on so much iteration at week x. Once a key is broken, he/she just has to hash it a little more like you do each week. This is dead easy and goes completely unnoticed.

If you rehash, do it with a new salt and from scratch with more iterations. Your shortcut does not bring extra safety.

Answer 2

This would make brute-force breaking harder, but also makes your login process slower.

You're better off using more salt.