• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

FAQ | Search | Usergroups | Profile | Register | RSS | Posting Guidelines | Recent Posts

securing short key hash

Users browsing this topic:0 Security Fans, 0 Stealth Security Fans
Registered Security Fans: None
Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

View previous topic :: View next topic  
Author Message
Lem0nHead
Just Arrived
Just Arrived


Joined: 31 Oct 2008
Posts: 0


Offline

PostPosted: Fri Jul 10, 2009 9:20 am    Post subject: securing short key hash Reply with quote

hello

(I'm editing this post to try to give a simplified version, so sorry if you already read the old one Smile)

let's say I have 1000 possible passwords for a system
the hash (and hash function) of the correct password is public and an attacker may only try to a password on the system

is it possible to make this system secure?

I mean, I want an attacker to have close to 1/1000 chance of success
but, in this case, given that the hash is public an attacker could try to attack the hash, not the system... so a bruteforce to the hash would be quite fast usually

the only way around I could think would be to slow down the hash function
for example, concatenating the typed password with a random number from 1 to 100,000... and then hashing this new string
now I'd need to check the trial against 100,000 hashs (what is somewhat slow and unpratical), but at least that's the case for a bruteforcer too, who would need to bruteforce it for each possible password

I wonder if there's a way to increase the "check security" linearly, but the "bruteforce security" quadratic Smile
Back to top
View user's profile Send private message
heba
Just Arrived
Just Arrived


Joined: 09 Jan 2006
Posts: 4
Location: Cremona (Italy)

Offline

PostPosted: Sat Jul 11, 2009 11:06 am    Post subject: Re: securing short key hash Reply with quote

Lem0nHead wrote:
hello


the only way around I could think would be to slow down the hash function
for example, concatenating the typed password with a random number from 1 to 100,000... and then hashing this new string
now I'd need to check the trial against 100,000 hashs (what is somewhat slow and unpratical), but at least that's the case for a bruteforcer too, who would need to bruteforce it for each possible password



hi,
a question because for me it's prematurely, but could be a practical reason for your speeches that I don't know.

slow down the hash don't permit a lamer to have your password before instead later?
Therefore slow down the hash is readable better than fast....I think... Confused

thanks in advance for the explanation
Back to top
View user's profile Send private message
Lem0nHead
Just Arrived
Just Arrived


Joined: 31 Oct 2008
Posts: 0


Offline

PostPosted: Sun Jul 12, 2009 5:17 am    Post subject: Re: securing short key hash Reply with quote

heba wrote:
slow down the hash don't permit a lamer to have your password before instead later?


no, the opposite
I care if a bruteforce can find my password in a week
but I don't care if it can find my password in 5 billion years

in fact, in my case, if it's possible to find my password just with a 10% chance after trying for 6 months, that's secure enough (the password is rotated every month, so that gives me a good margin already)
Back to top
View user's profile Send private message
Lem0nHead
Just Arrived
Just Arrived


Joined: 31 Oct 2008
Posts: 0


Offline

PostPosted: Sun Jul 12, 2009 5:35 am    Post subject: Reply with quote

in fact
I guess my example doesn't work
what I'd need to do is to slow down the hash function (so let's say I could make sha256() takes 2 seconds instead of 0,1ms)

my problem is specifically that:
1) I have 100 passwords P in a space of 50^4 possible passwords
2) a hacker can't bruteforce my system, because it locks after a few trials
3) the hash of those 100 passwords if public, so a hacker can try to bruteforce all 50^4 possible password until he finds a match on my hashes
4) but I want him, doing that, to only find a match for any of the 100 passwords with less than 10% chance in 6 months

I was doing some math and, if it's not wrong, I'd need a password space of around 10^15 to archive that (considering it's possible to test 10^6 hashs / second)

the problem is that I can't increase the password space...
my first idea was to slow down the hash function (so the hacker can try like 1 hash per second instead of 10^6), but I don't know if there's a better way

thanks
Back to top
View user's profile Send private message
mah$us
Just Arrived
Just Arrived


Joined: 25 Feb 2009
Posts: 0


Offline

PostPosted: Sun Jul 12, 2009 11:38 am    Post subject: Reply with quote

It's an interesting problem - quite a difficult one! Two questions:

[1] How powerful is the processor that will validate the passwords? For example, if you found an irreducible method that would take 5 seconds on a fast PC, how long would it take in your application? Would that be acceptable?

[2] In the threat model, adversaries have access to this list of 100 hashes for valid passwords. Do they also have access to other data used by the password checking processor? In other words, if the validation processor used a "secret key," would this be safe from adversaries?

I'll try to think of a practical solution!
Back to top
View user's profile Send private message
mah$us
Just Arrived
Just Arrived


Joined: 25 Feb 2009
Posts: 0


Offline

PostPosted: Sun Jul 12, 2009 11:41 am    Post subject: Reply with quote

One more question:

There are 100 valid codes out of 50^4 possible: has someone specified or have the power to create the list of these valid codes, or can you control the list?
Back to top
View user's profile Send private message
Lem0nHead
Just Arrived
Just Arrived


Joined: 31 Oct 2008
Posts: 0


Offline

PostPosted: Sun Jul 12, 2009 5:33 pm    Post subject: Reply with quote

mah$us wrote:
It's an interesting problem - quite a difficult one! Two questions:

[1] How powerful is the processor that will validate the passwords? For example, if you found an irreducible method that would take 5 seconds on a fast PC, how long would it take in your application? Would that be acceptable?

[2] In the threat model, adversaries have access to this list of 100 hashes for valid passwords. Do they also have access to other data used by the password checking processor? In other words, if the validation processor used a "secret key," would this be safe from adversaries?

I'll try to think of a practical solution!


1) it's a common CPU (about 2.4 ghz)
it can perform 10,000 md5 (or sha1) per second

I expect it to take 1 to 2 seconds at most



2) my initial idea is to make nothing available (the key, the algorithm, some other key I'll concatenate, etc... is all secret)
but I'm implementing other layers of security, so I'd like to archive the best possible having only the key secret, and then I'll use obscurity for the other aspects
(for example, the hashs aren't public... but in case someone can break a previous layer of security, they'll become public but hopefully not enough for a hack)
Back to top
View user's profile Send private message
capi
SF Senior Mod
SF Senior Mod


Joined: 21 Sep 2003
Posts: 16777097
Location: Portugal

Offline

PostPosted: Sun Jul 12, 2009 5:51 pm    Post subject: Reply with quote

The possible hashes being public really hampers the security of this system... is this an absolute need? That is really the first thing you should be trying to fix.

Obviously, increasing the password space would be important, but as per your model that's not a possibility.

The hashes being known means that you no longer have mandatory access control to the password. If the hashes were only known to your system, you could use artificial delays (e.g. 5 seconds between login attempt) and account lockout policies to very good effect. However, since the hashes are in the attacker's hands, he can bypass all that and just bruteforce them in his own system.

The first thing you need to do is to apply some key strengthening techniques to the passwords. The password space is very small, and you need to make it harder for the attacker to bruteforce the hashes. In short, you need to introduce an algorithmic delay in the way the hashes are calculated. A well known technique is to apply a large number of hash rounds to the password, instead of just one. You hash the password 50,000 times, and use that as the key. In other words, you'd do hash(hash(hash(hash(hash(...(hash(password))...))))). This will make each hash take 50,000 times longer to be calculated, which won't make too much of an impact for a legitimate user doing it once when he logs in, but it will make a serious impact for an attacker trying to bruteforce the passwords.

The above precautions will make it harder for the attacker to bruteforce the hashes and find the original valid passwords. Now, assuming that the attacker has enough resources and manages to find the original passwords, you can still make things harder for him.

I'm assuming your system works on a mandatory access control basis for the login (that is, the protected resources are only available through your authentication interface, and none other). If this is not the case (e.g. the resources can be reached through other means) then the whole debate is moot and you should be looking at encrypting the resources.

What you want here is to rate limit the login attempts. Introduce a delay of, say, 5 seconds between each attempt. After 3 failed attempts, lock the account temporarily for 30 minutes.

This would let the attacker try 3 passwords every 3 * 5 + 30 * 60 = 1815 seconds. That's an average speed of 3/1815 = 1/605 passwords per second, which means to try 50^4 passwords the attacker would need 50^4 * 605 = 3,781,250,000 seconds, or almost 120 years.
Back to top
View user's profile Send private message
mah$us
Just Arrived
Just Arrived


Joined: 25 Feb 2009
Posts: 0


Offline

PostPosted: Sun Jul 12, 2009 7:18 pm    Post subject: Reply with quote

Here are my crazy ideas (if you use one of them, and the Russians hack in the next day, then ... oops!)

[1] (also proposed by capi): Iterate a standard hash function many times. I believe that if a shortcut could be found that would reduce the number of iterations, this would be a weakness of the hash: so if the hash function is strong, then so should be this technique. This does NOT require your verification computer to store a secret, so the bad guys won't be helped if they reverse engineer the verifier.

SUMMARY: Slow verification, strong security case, doesn't rely on secret.

[1a] Variant using an iterated symmetric cipher. Starting with a key that need not be protected (IV), encrypt a hash of the password. In each subsequent step, use the ciphertext as the key, and encrypt either the ciphertext, or a hash thereof. Many symmetric ciphers have a slow key setup procedure; this would have to be done in each step!

SUMMARY: Slow verification, security depends on no shortcut for key setup (not a well-studied problem), doesn't rely on secret.

[2] Use the password (or some hash thereof) as the seed value for a Blum-Blum-Shub pseudo-random number generator (with a modulus of secure size, >= 1024 bits). Choose a number k of modular exponentations that you think will take your adversary too much time (say, 100,000), and construct your password hash from bits generated starting at that number: for example, the 100,000th through 100,031st parity bits could make up a 32-bit hash of the password.

SUMMARY: Slow verification, strong security case, doesn't rely on secret.

NOTE: All of the above methods, and in fact any method that doesn't rely on a secret, have a weakness: you have some limit within which you must check a password (say, 10 seconds). If your adversary uses the same power of computer, it will take 2 years to make a list of all possible hashes, and only 10 weeks to have a good chance of finding one good password (given the list of hashes). If your adversary has the hash list and is willing to run 10 machines in parallel, he has a good password in a week.

[2a] Use a Blum-Blum-Shub generator as above, but set k to an unreasonably high value, say 10^12. Verification is practical, because you can compute the kth value in a single modular exponentiation (see http://en.wikipedia.org/wiki/Blum_Blum_Shub) by knowing the factorization of the modulus. This requires that your verification code be kept secret. If an adversary has the list of hashes, but doesn't have access to your verification code, he would need years to find a good password, even using many extremely fast machines.

SUMMARY: Fast verification, strong security case, requires secret.
Back to top
View user's profile Send private message
Lem0nHead
Just Arrived
Just Arrived


Joined: 31 Oct 2008
Posts: 0


Offline

PostPosted: Sun Jul 12, 2009 9:43 pm    Post subject: Reply with quote

hello
thanks! Smile

your ideas makes sense, and I think I'll go with the hash cascade because it's easier to implement... also, I guess I could use md5(sha1(md5(sha1(...)))) to avoid specific weakness of hash functions


I'll probably use some technique that requires a secret too (I'm thinking about concatenating the real password with a 32 bytes secret key, so hash can't be found by bruteforce), but I just want to know how it will perform in case this secret is broken Smile
at least if I can detect it was broken in a few days, that should be fine, because I can then change the passwords

and after all, it's just for a somewhat personal system, so I guess I won't have many russians trying to hack it Wink
but I though it would be fun to make it really secure (and I'm kind paranoid)
Back to top
View user's profile Send private message
capi
SF Senior Mod
SF Senior Mod


Joined: 21 Sep 2003
Posts: 16777097
Location: Portugal

Offline

PostPosted: Mon Jul 13, 2009 6:42 am    Post subject: Reply with quote

Lem0nHead wrote:
also, I guess I could use md5(sha1(md5(sha1(...)))) to avoid specific weakness of hash functions

If you do mix different hash functions, try to use functions with the same size digest. MD5 produces a 128-bit digest, while SHA1 produces a 160-bit digest. If you mix them, you're really only getting 128 bits worth of "information".

You could, for example, mix SHA1 with RIPEMD-160.
Back to top
View user's profile Send private message
Lem0nHead
Just Arrived
Just Arrived


Joined: 31 Oct 2008
Posts: 0


Offline

PostPosted: Mon Jul 13, 2009 6:49 am    Post subject: Reply with quote

capi wrote:
Lem0nHead wrote:
also, I guess I could use md5(sha1(md5(sha1(...)))) to avoid specific weakness of hash functions

If you do mix different hash functions, try to use functions with the same size digest. MD5 produces a 128-bit digest, while SHA1 produces a 160-bit digest. If you mix them, you're really only getting 128 bits worth of "information".

You could, for example, mix SHA1 with RIPEMD-160.


true, thanks for the advice
Back to top
View user's profile Send private message
mah$us
Just Arrived
Just Arrived


Joined: 25 Feb 2009
Posts: 0


Offline

PostPosted: Tue Jul 14, 2009 12:28 am    Post subject: Reply with quote

Another word about crazy idea [2a] ... it is actually very simple to implement if you have a library with a modular exponentiation function. For example, it is very easy to do large-integer modexp in Python.
Back to top
View user's profile Send private message
Display posts from previous:   

Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security All times are GMT + 2 Hours
Page 1 of 1


 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Community Area

Log in | Register