Linux Archive

Linux Archive (http://www.linux-archive.org/)
-   Debian User (http://www.linux-archive.org/debian-user/)
-   -   Hash salt (was BCRYPT - Why not using it?) (http://www.linux-archive.org/debian-user/511000-hash-salt-bcrypt-why-not-using.html)

Ron Johnson 04-07-2011 02:02 AM

Hash salt (was BCRYPT - Why not using it?)
 
On 04/06/2011 08:19 PM, Aaron Toponce wrote:
[snip]


First, if you don't have the salt, but you do have the hash, then a rainbow
table attack is completely pointless. Reason being is rainbow tables store
hashes with a 1:1 ration to text. How the table is traversed is another
story, but the fact remains that one hash will lead you to one piece of
text. Now add a salt. If the salt is unknown, the length of the salt is
8 characters, and the characters used in the salt are [A-Za-z0-9./], or 64
characters, then there are effectively 64^8 possible hashes for one


The OS must store the salt somewhere, in order to correctly authenticate
the user when he logs in. But I've never heard of /etc/hashsalt so what
am I misunderstanding?


--
"Neither the wisest constitution nor the wisest laws will secure
the liberty and happiness of a people whose manners are universally
corrupt."
Samuel Adams, essay in The Public Advertiser, 1749


--
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org

Archive: 4D9D1B22.2010608@cox.net">http://lists.debian.org/4D9D1B22.2010608@cox.net

"Boyd Stephen Smith Jr." 04-07-2011 03:40 AM

Hash salt (was BCRYPT - Why not using it?)
 
In <4D9D1B22.2010608@cox.net>, Ron Johnson wrote:
>On 04/06/2011 08:19 PM, Aaron Toponce wrote:
>> First, if you don't have the salt, but you do have the hash, then a
>> rainbow table attack is completely pointless.
>
>The OS must store the salt somewhere, in order to correctly authenticate
>the user when he logs in. But I've never heard of /etc/hashsalt so what
>am I misunderstanding?

The value stored in /etc/shadow is both the salt + the encrypted
salt+password. This allows a process with read access to /etc/shadow to
easily read the shadow, encrypt the salt + provided password, and compare the
result to the encrypted salt+password. The salt is randomly generated each
time the password is set, and it (usually) different for each entry in
/etc/shadow.

This increases the size of a rainbow table by a factor of 2^(bits in salt),
effectively stopping the attack for all but the most high-profile target with
just an 8-bit salt. I'm not sure how many bits are used in a modern salt, but
I think it is somewhere between 48-bits and 64-bits.

Salted MD5 is still considered secure, even with the known attacks against
MD5. Salted SHA1 has no attacks more effective than brute-force. I'd like to
believe that shadow passwords will more to SHA3 within 2-3 releases after SHA3
is finalized. At the current rate of attack improvements against MD5, that
should be plenty of time.
--
Boyd Stephen Smith Jr. ,= ,-_-. =.
bss@iguanasuicide.net ((_/)o o(\_))
ICQ: 514984 YM/AIM: DaTwinkDaddy `-'(. .)`-'
http://iguanasuicide.net/ \_/

Aaron Toponce 04-07-2011 04:30 AM

Hash salt (was BCRYPT - Why not using it?)
 
On Wed, Apr 06, 2011 at 09:02:10PM -0500, Ron Johnson wrote:
> The OS must store the salt somewhere, in order to correctly
> authenticate the user when he logs in. But I've never heard of
> /etc/hashsalt so what am I misunderstanding?

Yes, the salt and the password are both stored in the /etc/shadow file. If
you can read that file, then you have access to both. However, if you don't
have the salt but you do have the hash (maybe it's a different application
besides login you're attacking that stores the salt elsewhere), you don't
know the size of the salt, nor what was used in the salt to create the
hash. So, your search space has just expanded by 64^(number of characters
in salt).

For example, say you have the hash 633427ee13ba83a92778c91a795d444564b9214c
(which actually isn't the encoded format as shown in /etc/shadow, but it
will illustrate the point). You don't know what salt was used to create
that hash. It's 160 bits, so it could be SHA1. Assuming such, you send it
through a 7TB rainbow table, and turn up empty handed. So, either the
password is exceptionally strong, or it's using a salt, and could still be
strong, or could be weak. You don't know. And the only way to work it out
is start incrementing through salts for every string you try, up to some
reasonable point. I hope you have time on your hands, because you'll need
it.

In this case, the password was 'foo' and the salt was 'salt':

$ echo foosalt | sha1sum
633427ee13ba83a92778c91a795d444564b9214c -

--
. o . o . o . . o o . . . o .
. . o . o o o . o . o o . . o
o o o . o . . o o o o . o o o

Joel Roth 04-07-2011 04:37 AM

Hash salt (was BCRYPT - Why not using it?)
 
On Wed, Apr 06, 2011 at 10:40:58PM -0500, Boyd Stephen Smith Jr. wrote:
> In <4D9D1B22.2010608@cox.net>, Ron Johnson wrote:
> >On 04/06/2011 08:19 PM, Aaron Toponce wrote:
> >> First, if you don't have the salt, but you do have the hash, then a
> >> rainbow table attack is completely pointless.
> >
> >The OS must store the salt somewhere, in order to correctly authenticate
> >the user when he logs in. But I've never heard of /etc/hashsalt so what
> >am I misunderstanding?
>
> The value stored in /etc/shadow is both the salt + the encrypted
> salt+password. This allows a process with read access to /etc/shadow to
> easily read the shadow, encrypt the salt + provided password, and compare the
> result to the encrypted salt+password. The salt is randomly generated each
> time the password is set, and it (usually) different for each entry in
> /etc/shadow.

So is the salt a fixed number of characters?

Otherwise, how would a process know which portion of the
string is the salt?

Regards,

--
Joel Roth


--
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
Archive: 20110407043738.GA23159@sprite">http://lists.debian.org/20110407043738.GA23159@sprite

Ron Johnson 04-07-2011 04:52 AM

Hash salt (was BCRYPT - Why not using it?)
 
On 04/06/2011 10:40 PM, Boyd Stephen Smith Jr. wrote:

In<4D9D1B22.2010608@cox.net>, Ron Johnson wrote:

On 04/06/2011 08:19 PM, Aaron Toponce wrote:

First, if you don't have the salt, but you do have the hash, then a
rainbow table attack is completely pointless.


The OS must store the salt somewhere, in order to correctly authenticate
the user when he logs in. But I've never heard of /etc/hashsalt so what
am I misunderstanding?


The value stored in /etc/shadow is both the salt + the encrypted
salt+password. This allows a process with read access to /etc/shadow to
easily read the shadow, encrypt the salt + provided password, and compare the
result to the encrypted salt+password. The salt is randomly generated each
time the password is set, and it (usually) different for each entry in
/etc/shadow.



Is the salt just bits that are either pre- or suffixed to your password
before being run through the hashing function?



This increases the size of a rainbow table by a factor of 2^(bits in salt),
effectively stopping the attack for all but the most high-profile target with
just an 8-bit salt. I'm not sure how many bits are used in a modern salt, but
I think it is somewhere between 48-bits and 64-bits.


The first 3 characters of every hash in my /etc/shadow are the same.
That's what, 24 bits?




Salted MD5 is still considered secure, even with the known attacks against
MD5. Salted SHA1 has no attacks more effective than brute-force. I'd like to
believe that shadow passwords will more to SHA3 within 2-3 releases after SHA3
is finalized. At the current rate of attack improvements against MD5, that
should be plenty of time.


But if you're machine is rooted then (besides having lots of other
problems) the attacker has your system-wide salt. (But the rainbow
table would still be unimaginably huge...)


--
"Neither the wisest constitution nor the wisest laws will secure
the liberty and happiness of a people whose manners are universally
corrupt."
Samuel Adams, essay in The Public Advertiser, 1749


--
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org

Archive: 4D9D42F4.90706@cox.net">http://lists.debian.org/4D9D42F4.90706@cox.net

Martin Ågren 04-07-2011 04:52 AM

Hash salt (was BCRYPT - Why not using it?)
 
Aaron Toponce:
> For example, say you have the hash 633427ee13ba83a92778c91a795d444564b9214c
> (which actually isn't the encoded format as shown in /etc/shadow, but it
> will illustrate the point). You don't know what salt was used to create
> that hash. It's 160 bits, so it could be SHA1. Assuming such, [...]

Of course, everything gets easier once you invoke Kerckhoff's
principle. This will give you both the algorithm and the salt, as the
only thing secret should be the password. :) Seriously though, all of
this information is likely found in the documentation in this case, or
in worst case in the source code. (Or in the leaked implementation in
the proprietary scenario.)

> In this case, the password was 'foo' and the salt was 'salt':
>
> $ echo foosalt | sha1sum
> 633427ee13ba83a92778c91a795d444564b9214c *-

In this particular scheme, it appears ('foo','salt') has the same hash
as ('foosalt','). In a serious application, hopefully the wheel
wouldn't be reinvented in this way, but some well-studied, thoroughly
scrutinized approach would be used. :) But as a toy example it works,
sure!

Take care,
Martin


--
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
Archive: BANLkTimigGOUBufYYbrL=X8Vq6KA--SZUA@mail.gmail.com">http://lists.debian.org/BANLkTimigGOUBufYYbrL=X8Vq6KA--SZUA@mail.gmail.com

Martin Ågren 04-07-2011 05:01 AM

Hash salt (was BCRYPT - Why not using it?)
 
Boyd Stephen Smith Jr.:
> The salt is randomly generated each
> time the password is set, and it (usually) different for each entry in
> /etc/shadow.
>
> This increases the size of a rainbow table by a factor of 2^(bits in salt),
> effectively stopping the attack for all but the most high-profile target with
> just an 8-bit salt. *I'm not sure how many bits are used in a modern salt, but
> I think it is somewhere between 48-bits and 64-bits.

Practically speaking, the attacker prepares one table per hash, rather than
a huge table mixing different salts. When he gets the salt-and-digest, he
picks the correct table and gets running.

Obviously, for the same cost (pre-computation time, storage, online
time) as producing one table in the salt-less case, he can now
generate one table for one particular salt. So he either does it many
times, which becomes impractical, or he does it once for his
"favourite salt", e.g., one which often shows up in the wild due to
stupid/unlucky implementers using constant salt, bad random number
generators or whatever...

Or, when he gets 2^29 hashes from facebook, a salt size of 8 bits
would still give him about 2^21 hashes that he can run through his
table. (This scenario would have to count as "stupid implementers".)

Take care,
Martin


--
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
Archive: BANLkTikub1TANVxz+GbhcdFzcNPqpO+x-g@mail.gmail.com">http://lists.debian.org/BANLkTikub1TANVxz+GbhcdFzcNPqpO+x-g@mail.gmail.com

Aaron Toponce 04-07-2011 05:44 AM

Hash salt (was BCRYPT - Why not using it?)
 
On Thu, Apr 07, 2011 at 06:52:42AM +0200, Martin Ågren wrote:
> In this particular scheme, it appears ('foo','salt') has the same hash
> as ('foosalt','). In a serious application, hopefully the wheel
> wouldn't be reinvented in this way, but some well-studied, thoroughly
> scrutinized approach would be used. :) But as a toy example it works,
> sure!

The point was to illustrate how a password and salt work to create a unique
hash. Sure, I could have covered all the details on the specific
/etc/shadow implementation, but then we wouldn't see the forest from the
trees.

At any event, point taken.

--
. o . o . o . . o o . . . o .
. . o . o o o . o . o o . . o
o o o . o . . o o o o . o o o


All times are GMT. The time now is 07:28 AM.

VBulletin, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO ©2007, Crawlability, Inc.