Re: [WEB SECURITY] Hashing and entropy

[Oliver Lavery <oliver@xxxxxxxxxxxxxxxxxxx>]

--B_3296748643_7054649
Content-type: text/plain;
	charset="ISO-8859-1"
Content-transfer-encoding: quoted-printable

Yes, exactly. That=B9s the problem statement.

Although there are a limited number of possible hashes due to a lack of
entropy in the input, it=B9s seems practical in any application I can think o=
f
to raise the computational cost of the algorithm to the point that it=B9s
computationally infeasible to reverse the hashes before the CCs expire.

It just struck me as an interesting practical question: given that for many
applications it=B9s necessary to hash credit card numbers, how much
computational complexity in the hashing algorithm is enough to say the
hashes are secure?

The obvious answer is to add a salt value, but given that that salt will be
known to an attacker who has compromised the hashes in a practical
application, salt only helps defeat pre-computed tables. It just raises the
bar a notch.=20

PCI talks about secure hashing of credit card numbers, but afaik it doesn=B9t
really specify what =8Csecurely=B9 means. I=B9m willing to wager a few pints that
most implementations are totally broken. Sure, whatever, it=B9s better than
storing them in the clear ... but what does a correct implementation look
like?=20

The parameters of the problem as I see it are:

1) credit card numbers have roughly 10**16 distinct values, well below
2**128 (MD5) much less 2**160 (SHA1)
2) to be secured for the duration of their expiry, the hash of the CC numbe=
r
shouldn=B9t be breakable for ~5 years
3) we can create arbitrary computational complexity by applying multiple
rounds of a hashing algorithm like SHA
4) we gain little by expanding the number of bits in the hash beyond
whatever power of 2 is nearest 10**16 (leaving some room for salt values)

Has anyone seen a solution to this published anywhere? Are any of these
assumptions false? Did I miss anything?

Perhaps it=B9s more of a crypto question, but since it=B9s such a common proble=
m
in web apps, I thought it might be an interesting question to throw out
there...

Cheers,
~ol

On 19/06/08 3:27 PM, "Martin O'Neal" <martin.oneal@corsaire.com> wrote:

>=20
>=20
>> > On the other hand this isn't *absolutely true* in a
>> > practical sense. A 160 bit hash algorithm begins to
>> > raise the brute force cost somewhat above MD5. I
>> > mentioned SHA256 earlier which raises the brute
>> > force cost again.
>=20
> There are at least two factors at play; entropy and computational cost
> per hash round.
>=20
> If your data source contains low entropy, then you are stuck until you
> add more entropy.  Anything else is just tinkering at the edges.  It
> doesn't matter how large or complex the hash is, if there are only a
> limited number of choices entering on the cleartext side, then there are
> only a limited number of hashes exiting on the other...
>=20
> The computational cost for the generic hash algorithms is deliberately
> low by design (even the high-bit versions).  There are however, specific
> hash algorithms for passwords that are deliberately computationally
> expensive.
>=20
> Martin...
>=20
>=20
> ----------------------------------------------------------------------
> CONFIDENTIALITY:  This e-mail and any files transmitted with it are
> confidential and intended solely for the use of the recipient(s) only.
> Any review, retransmission, dissemination or other use of, or taking
> any action in reliance upon this information by persons or entities
> other than the intended recipient(s) is prohibited.  If you have
> received this e-mail in error please notify the sender immediately
> and destroy the material whether stored on a computer or otherwise.
> ----------------------------------------------------------------------
> DISCLAIMER:  Any views or opinions presented within this e-mail are
> solely those of the author and do not necessarily represent those
> of Corsaire Limited, unless otherwise specifically stated.
> ----------------------------------------------------------------------
> Corsaire Limited, registered in England No. 3338312. Registered
> office: Portland House, Park Street, Bagshot, Surrey GU19 5PG.
> Telephone: +44 (0)1483-746700
>=20
>=20


--B_3296748643_7054649
Content-type: text/html;
	charset="ISO-8859-1"
Content-transfer-encoding: quoted-printable

<HTML>
<HEAD>
<TITLE>Re: [WEB SECURITY] Hashing and entropy</TITLE>
</HEAD>
<BODY>
<FONT FACE=3D"Calibri, Verdana, Helvetica, Arial"><SPAN STYLE=3D'font-size:11pt=
'>Yes, exactly. That&#8217;s the problem statement. <BR>
<BR>
Although there are a limited number of possible hashes due to a lack of ent=
ropy in the input, it&#8217;s seems practical in any application I can think=
 of to raise the computational cost of the algorithm to the point that it&#8=
217;s computationally infeasible to reverse the hashes before the CCs expire=
. &nbsp;&nbsp;<BR>
<BR>
It just struck me as an interesting practical question: given that for many=
 applications it&#8217;s necessary to hash credit card numbers, how much com=
putational complexity in the hashing algorithm is enough to say the hashes a=
re secure?<BR>
<BR>
The obvious answer is to add a salt value, but given that that salt will be=
 known to an attacker who has compromised the hashes in a practical applicat=
ion, salt only helps defeat pre-computed tables. It just raises the bar a no=
tch. <BR>
<BR>
PCI talks about secure hashing of credit card numbers, but afaik it doesn&#=
8217;t really specify what &#8216;securely&#8217; means. I&#8217;m willing t=
o wager a few pints that most implementations are totally broken. Sure, what=
ever, it&#8217;s better than storing them in the clear ... but what does a c=
orrect implementation look like? <BR>
<BR>
The parameters of the problem as I see it are:<BR>
<BR>
1) credit card numbers have roughly 10**16 distinct values, well below 2**1=
28 (MD5) much less 2**160 (SHA1)<BR>
2) to be secured for the duration of their expiry, the hash of the CC numbe=
r shouldn&#8217;t be breakable for ~5 years<BR>
3) we can create arbitrary computational complexity by applying multiple ro=
unds of a hashing algorithm like SHA<BR>
4) we gain little by expanding the number of bits in the hash beyond whatev=
er power of 2 is nearest 10**16 (leaving some room for salt values)<BR>
<BR>
Has anyone seen a solution to this published anywhere? Are any of these ass=
umptions false? Did I miss anything?<BR>
<BR>
Perhaps it&#8217;s more of a crypto question, but since it&#8217;s such a c=
ommon problem in web apps, I thought it might be an interesting question to =
throw out there...<BR>
<BR>
Cheers,<BR>
~ol<BR>
<BR>
On 19/06/08 3:27 PM, &quot;Martin O'Neal&quot; &lt;<a href=3D"martin.oneal@co=
rsaire.com">martin.oneal@corsaire.com</a>&gt; wrote:<BR>
<BR>
</SPAN></FONT><BLOCKQUOTE><FONT FACE=3D"Calibri, Verdana, Helvetica, Arial"><=
SPAN STYLE=3D'font-size:11pt'><BR>
<BR>
&gt; On the other hand this isn't *absolutely true* in a<BR>
&gt; practical sense. A 160 bit hash algorithm begins to<BR>
&gt; raise the brute force cost somewhat above MD5. I<BR>
&gt; mentioned SHA256 earlier which raises the brute<BR>
&gt; force cost again.<BR>
<BR>
There are at least two factors at play; entropy and computational cost<BR>
per hash round.<BR>
<BR>
If your data source contains low entropy, then you are stuck until you<BR>
add more entropy. &nbsp;Anything else is just tinkering at the edges. &nbsp=
;It<BR>
doesn't matter how large or complex the hash is, if there are only a<BR>
limited number of choices entering on the cleartext side, then there are<BR=
>
only a limited number of hashes exiting on the other...<BR>
<BR>
The computational cost for the generic hash algorithms is deliberately<BR>
low by design (even the high-bit versions). &nbsp;There are however, specif=
ic<BR>
hash algorithms for passwords that are deliberately computationally<BR>
expensive.<BR>
<BR>
Martin...<BR>
<BR>
<BR>
----------------------------------------------------------------------<BR>
CONFIDENTIALITY: &nbsp;This e-mail and any files transmitted with it are<BR=
>
confidential and intended solely for the use of the recipient(s) only.<BR>
Any review, retransmission, dissemination or other use of, or taking<BR>
any action in reliance upon this information by persons or entities<BR>
other than the intended recipient(s) is prohibited. &nbsp;If you have<BR>
received this e-mail in error please notify the sender immediately<BR>
and destroy the material whether stored on a computer or otherwise.<BR>
----------------------------------------------------------------------<BR>
DISCLAIMER: &nbsp;Any views or opinions presented within this e-mail are<BR=
>
solely those of the author and do not necessarily represent those<BR>
of Corsaire Limited, unless otherwise specifically stated.<BR>
----------------------------------------------------------------------<BR>
Corsaire Limited, registered in England No. 3338312. Registered<BR>
office: Portland House, Park Street, Bagshot, Surrey GU19 5PG.<BR>
Telephone: +44 (0)1483-746700<BR>
<BR>
<BR>
</SPAN></FONT></BLOCKQUOTE>
</BODY>
</HTML>


--B_3296748643_7054649--