Mailing List Archive: Full Disclosure: Full-Disclosure

Salted passwords

Full Disclosure full-disclosure RSS feed

Index | Next | Previous | View Threaded

tbiehn at gmail

Aug 9, 2009, 5:14 PM

Post #1 of 9 (1752 views)
Permalink

Salted passwords

Soliciting random suggestions.
Lets say I have data to one-way-hash.
The set has 9,999,999,999 members.
It's relatively easy to brute force this, or create precomp tables.
So you add a salt to each.
Still easy to brute force.
If you were to create it in such a way that the hash could exist
anywhere in the set member, does this increase the cost of computation
enough?

That is, consider a member 'abcdefg' with salt 329938255.
When authenticating against the server, it must permute over all
possible combinations of the salt and the set member in order to
determine the validity of the password.

If anyone has a better approach, or would like to approach me off
list, or knows of a list more suited to these queries please feel free
to redirect me :)

-Travis

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

tbiehn at gmail

Aug 10, 2009, 7:35 AM

Post #2 of 9 (1668 views)
Permalink

Re: Salted passwords [In reply to]

Richard,
The approach I outline in my post is the correct one, that is, making
it computationally expensive to crack. I'm not trying to protect
passwords, think anonymizing account numbers and the like.. That is,
the possible combinations are a set that is unacceptably small.
Without an expensive compute step it's trivial to brute force given a
static salt location...

(excuse my use of shitty pseudocode, assume homogeneous length 10)

Typically the test is:

if storedHash = hashFcn(userPassword & storedSalt) //9,999,999,999 tests

if you randomly store the storedSalt ANYWHERE within userPassword, it becomes

for (int i=0; i<len(userPassword); i++) {
String toTest = substring(userPassword,0,i) & storedSalt &
substring(userPassword,i)
if storedHash = hashFcn(toTest) {
return true;
}
}
return false; //99,999,999,990 tests

and like hashFcn could be

for (int i=0;i<expensive;i++) {
x = pgp(x);
x = md5(x);
}
return x;

It'd be heavy if pgp were using 4096 bitsize keys. Tweak 'expensive'
to match average acceptable test time. (5 seconds to run 10 tests.)

The set size increases, and brute force attempts become more difficult
(as for each brute force test in the set you must test 'strlength'
times). That is, in a set of homogeneous length strings the hash set
is set size times string length.

I believe this is a rather typical approach. I'm interested to see if
someone else has any other ideas/accepted methods for effectively
increasing the hash set size without increasing the value set size.

It's more so that I'm trawling the net for like minded individuals
rather than soliciting actual advice. Other methods are fairly
obvious.
Using two salts with random locations, etc.

I'm afraid it follows, though, that I reach a point where it's too
expensive, and thus login to a service will suffer an unacceptable
delay, this limitation precludes me from preventing against cracking
by the "10 million dollar computer" and certainly such a scheme will
not be 'future proof.'

-Travis

On Sun, Aug 9, 2009 at 11:56 PM, Richard
Golodner<rgolodner [at] infratection> wrote:
**REDACTED**
"explain please"
**REDACTED**

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

antisec at hushmail

Aug 10, 2009, 9:08 AM

Post #3 of 9 (1678 views)
Permalink

Re: Salted passwords [In reply to]

AntiSec would like to approach you by telling you to keep you
whitehat filty ass off our list, Travis.

Have a nice day sucking off Aitel.

On Sun, 09 Aug 2009 20:14:57 -0400 T Biehn <tbiehn [at] gmail> wrote:
>Soliciting random suggestions.
>Lets say I have data to one-way-hash.
>The set has 9,999,999,999 members.
>It's relatively easy to brute force this, or create precomp
>tables.
>So you add a salt to each.
>Still easy to brute force.
>If you were to create it in such a way that the hash could exist
>anywhere in the set member, does this increase the cost of
>computation
>enough?
>
>That is, consider a member 'abcdefg' with salt 329938255.
>When authenticating against the server, it must permute over all
>possible combinations of the salt and the set member in order to
>determine the validity of the password.
>
>If anyone has a better approach, or would like to approach me off
>list, or knows of a list more suited to these queries please feel
>free
>to redirect me :)
>
>-Travis
>
>_______________________________________________
>Full-Disclosure - We believe in it.
>Charter: http://lists.grok.org.uk/full-disclosure-charter.html
>Hosted and sponsored by Secunia - http://secunia.com/

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

tbiehn at gmail

Aug 10, 2009, 9:13 AM

Post #4 of 9 (1664 views)
Permalink

Re: Salted passwords [In reply to]

I'm flattered; If you only knew what it was for...
IHBT?

-Travis

On Mon, Aug 10, 2009 at 12:08 PM, <antisec [at] hushmail> wrote:
> AntiSec would like to approach you by telling you to keep you
> whitehat filty ass off our list, Travis.
>
> Have a nice day sucking off Aitel.
>
> On Sun, 09 Aug 2009 20:14:57 -0400 T Biehn <tbiehn [at] gmail> wrote:
>>Soliciting random suggestions.
>>Lets say I have data to one-way-hash.
>>The set has 9,999,999,999 members.
>>It's relatively easy to brute force this, or create precomp
>>tables.
>>So you add a salt to each.
>>Still easy to brute force.
>>If you were to create it in such a way that the hash could exist
>>anywhere in the set member, does this increase the cost of
>>computation
>>enough?
>>
>>That is, consider a member 'abcdefg' with salt 329938255.
>>When authenticating against the server, it must permute over all
>>possible combinations of the salt and the set member in order to
>>determine the validity of the password.
>>
>>If anyone has a better approach, or would like to approach me off
>>list, or knows of a list more suited to these queries please feel
>>free
>>to redirect me :)
>>
>>-Travis
>>
>>_______________________________________________
>>Full-Disclosure - We believe in it.
>>Charter: http://lists.grok.org.uk/full-disclosure-charter.html
>>Hosted and sponsored by Secunia - http://secunia.com/
>
> _______________________________________________
> Full-Disclosure - We believe in it.
> Charter: http://lists.grok.org.uk/full-disclosure-charter.html
> Hosted and sponsored by Secunia - http://secunia.com/
>

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

Valdis.Kletnieks at vt

Aug 10, 2009, 1:26 PM

Post #5 of 9 (1663 views)
Permalink

Re: Salted passwords [In reply to]

On Sun, 09 Aug 2009 20:14:57 EDT, T Biehn said:
> Soliciting random suggestions.
> Lets say I have data to one-way-hash.
> The set has 9,999,999,999 members.

Actually, if you're using a 10-digit decimal field, you probably have 10**10
possible members - all-zeros counts too (unless there's *other* reasons zero
isn't a legal ID). It's those little off-by-one errors that tend to get you.
;)

> It's relatively easy to brute force this, or create precomp tables.

That's because you only have 10M billion members to brute force against.

> So you add a salt to each.

A better idea cryptographically would be to fix the 10**10 member limit, so
that the set *could* have a much higher possible number of members. Even
staying at 10 characters, but allowing [A-Za-z0-9] (62 possible chars) raises
your space to 62**10 or about 8.3*10**17 (or almost 10M times the difficuly).
That's why most symmetric crypto algorithms use at least 64-bit or even larger
keys, and even larger for RSA and similar public-key systems.

tbiehn at gmail

Aug 10, 2009, 1:50 PM

Post #6 of 9 (1657 views)
Permalink

Re: Salted passwords [In reply to]

Valdis,
I don't have control over the set. Sorry I wasn't more explicit about
this. Although, it should have been obvious that the solution needed
to satisfy the conditions:
Data to one way hash.
The set has 9,999,999,999 members.

Thanks for your input sweetie!

-Travis

On Mon, Aug 10, 2009 at 4:26 PM, <Valdis.Kletnieks [at] vt> wrote:
> On Sun, 09 Aug 2009 20:14:57 EDT, T Biehn said:
>> Soliciting random suggestions.
>> Lets say I have data to one-way-hash.
>> The set has 9,999,999,999 members.
>
> Actually, if you're using a 10-digit decimal field, you probably have 10**10
> possible members - all-zeros counts too (unless there's *other* reasons zero
> isn't a legal ID). �It's those little off-by-one errors that tend to get you.
> ;)
>
>> It's relatively easy to brute force this, or create precomp tables.
>
> That's because you only have 10M billion members to brute force against.
>
>> So you add a salt to each.
>
> A better idea cryptographically would be to fix the 10**10 member limit, so
> that the set *could* have a much higher possible number of members. �Even
> staying at 10 characters, but allowing [A-Za-z0-9] (62 possible chars) raises
> your space to 62**10 or about 8.3*10**17 (or almost 10M times the difficuly).
> That's why most symmetric crypto algorithms use at least 64-bit or even larger
> keys, and even larger for RSA and similar public-key systems.
>
>

--
pgp http://pastebin.com/f6fd606da pgp

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

raid at hushmail

Aug 10, 2009, 3:53 PM

Post #7 of 9 (1649 views)
Permalink

Re: Salted passwords [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Travis,

On Mon, 10 Aug 2009 22:50:32 +0200 T Biehn <tbiehn [at] gmail> wrote:
>I don't have control over the set. Sorry I wasn't more explicit
>about
>this. Although, it should have been obvious that the solution
>needed
>to satisfy the conditions:
>Data to one way hash.
>The set has 9,999,999,999 members.

if these are the only two conditions, I wonder why a static salt
does not satisfy your requirements? If the salt is not publicly
known, the procedure is secure in respect to the hash-function in
use...

So, suppose the third condition is the salt may be publicly known.

Suppose, we have plaintext (alphabet E, length of alphabet s = |E|)
with fixed length, say 'c' chars. So if you insert the salt at a
random position, there are c+1 possibilities for the position of
the salt. So the bruteforce attacker has to run c more tests than
having the salt in a fixed position.

Comparing the two procedures under a theoretically view, there isnt
a significant difference in terms of runtime complexity:

If the salt is not publicly known and at a fixed position,
complexity (means: number of possible plaintexts) is at O(s**c).
Your method only rises complexity by a constant factor: It's at O(
(c+1) * s**c).

Theoretically this is negligible: If it takes me 2 hours to
bruteforce procedure 1 (fixed position), why bother about 20 hours
computing for procedure 2?

Practically it depends on your overall requirements.

Besides, your procedure lowers the latch for DoS... at least
slightly (same argument as above).

So far, my two cents...

raid
-----BEGIN PGP SIGNATURE-----
Charset: UTF8
Version: Hush 3.0
Note: This signature can be verified at https://www.hushtools.com/verify

wpwEAQMCAAYFAkqApOoACgkQ/WWNsggjSSFjgAP/Wr/yus6Zf8e/nkegfMw4AeRS5Xz4
GP91CUbwEEgy0qMsL7HvrAc7oo7dt5PpEZIePVkBF8ea9WeW9RlX1YK7ZlkkIP6ZLKx2
XgT515eGNeTMbcKSmAOWlIkL4JtKRBxh7YLb0QP0yi3pCY7MGl4ZAtcGN25vx3Nkkq18
WMoO6VQ=
=UN3m
-----END PGP SIGNATURE-----

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

tbiehn at gmail

Aug 10, 2009, 4:34 PM

Post #8 of 9 (1641 views)
Permalink

Re: Salted passwords [In reply to]

Thank you for the thoughtful analysis Raid. The hash and salt are both
known to the attacker :)
It looks like I'm going to have to settle with confounding efforts by
the man via increased hash computation cost.

-Travis

On Mon, Aug 10, 2009 at 6:53 PM, <raid [at] hushmail> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Travis,
>
> On Mon, 10 Aug 2009 22:50:32 +0200 T Biehn <tbiehn [at] gmail> wrote:
>>I don't have control over the set. Sorry I wasn't more explicit
>>about
>>this. Although, it should have been obvious that the solution
>>needed
>>to satisfy the conditions:
>>Data to one way hash.
>>The set has 9,999,999,999 members.
>
> if these are the only two conditions, I wonder why a static salt
> does not satisfy your requirements? If the salt is not publicly
> known, the procedure is secure in respect to the hash-function in
> use...
>
> So, suppose the third condition is the salt may be publicly known.
>
> Suppose, we have plaintext (alphabet E, length of alphabet s = |E|)
> with fixed length, say 'c' chars. So if you insert the salt at a
> random position, there are c+1 possibilities for the position of
> the salt. So the bruteforce attacker has to run c more tests than
> having the salt in a fixed position.
>
> Comparing the two procedures under a theoretically view, there isnt
> a significant difference in terms of runtime complexity:
>
> If the salt is not publicly known and at a fixed position,
> complexity (means: number of possible plaintexts) is at O(s**c).
> Your method only rises complexity by a constant factor: It's at O(
> (c+1) * s**c).
>
> Theoretically this is negligible: If it takes me 2 hours to
> bruteforce procedure 1 (fixed position), why bother about 20 hours
> computing for procedure 2?
>
> Practically it depends on your overall requirements.
>
> Besides, your procedure lowers the latch for DoS... at least
> slightly (same argument as above).
>
> So far, my two cents...
>
> raid
> -----BEGIN PGP SIGNATURE-----
> Charset: UTF8
> Version: Hush 3.0
> Note: This signature can be verified at https://www.hushtools.com/verify
>
> wpwEAQMCAAYFAkqApOoACgkQ/WWNsggjSSFjgAP/Wr/yus6Zf8e/nkegfMw4AeRS5Xz4
> GP91CUbwEEgy0qMsL7HvrAc7oo7dt5PpEZIePVkBF8ea9WeW9RlX1YK7ZlkkIP6ZLKx2
> XgT515eGNeTMbcKSmAOWlIkL4JtKRBxh7YLb0QP0yi3pCY7MGl4ZAtcGN25vx3Nkkq18
> WMoO6VQ=
> =UN3m
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> Full-Disclosure - We believe in it.
> Charter: http://lists.grok.org.uk/full-disclosure-charter.html
> Hosted and sponsored by Secunia - http://secunia.com/
>

--
pgp http://pastebin.com/f6fd606da pgp

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

lyalc at isp

Aug 10, 2009, 10:27 PM

Post #9 of 9 (1594 views)
Permalink

Re: Salted passwords [In reply to]

I'm not a crypto guru, but it seems to me that this issue can be
crypto-anlayses somewhat like the speedups used to find hash collisions (if
I understand them at all).

The goal in both cases is to find a hash that 'collides' with a known hash
(password hash, or CC number of 6 BIN digits, 9,999,999,999 values and 1
checkdigit) from a known format.
i.e pre-compute some portion of the salt+_static_string_portion, then
brute-force the remainder of the string.

As long as the salt is private or long enough, then does it matter?
lyalc

-----Original Message-----
From: full-disclosure-bounces [at] lists
[mailto:full-disclosure-bounces [at] lists] On Behalf Of T Biehn
Sent: Tuesday, 11 August 2009 6:51 AM
To: Valdis.Kletnieks [at] vt
Cc: full-disclosure
Subject: Re: [Full-disclosure] Salted passwords

Valdis,
I don't have control over the set. Sorry I wasn't more explicit about this.
Although, it should have been obvious that the solution needed to satisfy
the conditions:
Data to one way hash.
The set has 9,999,999,999 members.

Thanks for your input sweetie!

-Travis

On Mon, Aug 10, 2009 at 4:26 PM, <Valdis.Kletnieks [at] vt> wrote:
> On Sun, 09 Aug 2009 20:14:57 EDT, T Biehn said:
>> Soliciting random suggestions.
>> Lets say I have data to one-way-hash.
>> The set has 9,999,999,999 members.
>
> Actually, if you're using a 10-digit decimal field, you probably have
> 10**10 possible members - all-zeros counts too (unless there's *other*
> reasons zero isn't a legal ID). �It's those little off-by-one errors that
tend to get you.
> ;)
>
>> It's relatively easy to brute force this, or create precomp tables.
>
> That's because you only have 10M billion members to brute force against.
>
>> So you add a salt to each.
>
> A better idea cryptographically would be to fix the 10**10 member
> limit, so that the set *could* have a much higher possible number of
> members. �Even staying at 10 characters, but allowing [A-Za-z0-9] (62
> possible chars) raises your space to 62**10 or about 8.3*10**17 (or almost
10M times the difficuly).
> That's why most symmetric crypto algorithms use at least 64-bit or
> even larger keys, and even larger for RSA and similar public-key systems.
>
>

--
pgp http://pastebin.com/f6fd606da pgp

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads