[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [WEB SECURITY] Hashing and entropy
- From: "Lavery, Oliver" <oliver@xxxxxxxxxxxxxxxxxxx>
- Subject: RE: [WEB SECURITY] Hashing and entropy
- Date: Fri, 20 Jun 2008 16:15:58 -0500
------_=_NextPart_001_01C8D31A.D556B8E0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Phew, finally get a break to respond to the thread I started ... sorry.
Yes, as several people pointed out 16 digits is wrong. I actually =
checked this quickly with a reference while writing the earlier post and =
only managed to confuse myself :P
Cards are 14-19 digits, with 2-6 consumed by BIN and one for the lunh =
code. That handy wiki page Amit posted has a worst case scenario of a 14 =
digit card with a three digit BIN and a Lunh, giving us 10 base 10 =
digits. *shudder*
I'd like to figure out how big the total search space is for all BINs, =
but don't have the time this lunch break...
Why Hash?
---------
A few people asked this. I've seen it justified by business requirements =
around comparing stored card numbers, which is a pretty obvious =
requirement for a lot of applications if you think about it. For =
example:
- Application needs to be able to verify a new transaction against the =
card on file=20
- Application needs to be able to create a list of all transactions for =
a single card. (Afaik more than one person can have the exact same CC # =
in the case of a shared card with secondary cardholders)
Hashing isn't actually the problem, it's these requirements that lead to =
broken implementations. If you use a different random salt to store =
every card number, even if the salt is stored with the hash, the attack =
gets harder as each hash has to be broken independently. This could be =
better than encryption since it isn't reversible. Unfortunately you also =
loose the ability to compare card numbers, however.=20
Collisions aren't as much a problem; collisions happen when two inputs =
hash to the same value ... not something that's affected by the entropy =
in the input afaict, it's just a product of the algorithm and it's =
output length.=20
Who would be silly enough to do this?!
--------------------------------------
>From PCI 1.1:
3.4 Render PAN, at minimum, unreadable anywhere it is stored (including =
data on portable digital media, backup media, in logs, and data received =
from or stored by wireless networks) by using
any of the following approaches:
=95 Strong one-way hash functions (hashed indexes)
=95 Truncation
=95 Index tokens and pads (pads must be securely stored) [What?!]
=95 Strong cryptography with associated key management processes and =
procedures.=20
It's not silly, it's a best practice!=20
Encryption is better!
---------------------
I'm not sure this is really true. Correct me if I'm wrong, =
IANACryptographer, but my thinking is that for any cryptographic =
function f(), and CC# x:
y =3D f(x)
y' =3D f(x)
if y =3D=3D y' then you're in trouble, provided the attacker can compute =
f().
Symmetric crypto is probably not something you want to use to protect =
CC#s in an online transaction processing system since the key has to be =
stored with the data. Never mind that lots of people do this. If an =
attacker can get the cyphertext, it's reasonable to assume he can get =
the key. (Yeah you can hide it somewhere in memory, so I root your box, =
dump the memory, and use a single known plaintext to find the key in =
there or somesuch)
Assymetric crypto is better, since you only need to keep the public key =
online. However, if the crypto is implemented such that comparing card =
numbers still works, then you have the exact same problem as with =
hashing. An attacker who has the CC #s will reasonably also have the =
public key, and can break the encryption through brute force by =
encrypting all possible plaintexts with the key. It's just slower.
Why do you need to keep the key online? If it's an OLTP application like =
a payment processor or an ecom site, than the alternative when new CC#s =
arrive is to store them in plaintext and encrypt them only when the key =
is available. Maybe there's some way around this?
Solution?
---------
Which gets us back to possible solutions. Thanks for the awesome blog =
link Bil.=20
Maybe the question is just how much computational complexity would be =
enough for CC#s, and whether or not it's feasible for a system to =
implement it.
Although a much better solution is to never, ever have to do comparisons =
online, I think. Hashing or Asymmetric crypto implemented such that the =
same card number will not always encrypt to the same ciphertext seems =
like the only really strong security to me...
Cheers,
~ol
-----Original Message-----
From: Glenn.Everhart@chase.com [mailto:Glenn.Everhart@chase.com]
Sent: Fri 20/06/2008 14:12
To: aksecurity@gmail.com; nhoyle@hoyletech.com
Cc: websecurity@webappsec.org
Subject: RE: [WEB SECURITY] Hashing and entropy
=20
I figure 30 to 38 bits if you know the bank. Why does anyone want to =
hash
card numbers???
Figuring out what number a hash corresponds to is comparable to doing =
the
same with SSN (also 9 digits) which would be the 30 bit case.=20
Heck's bells: you might as well hash someone's age in years and expect =
that to
obscure it! (That's a bit easier but illustrates the problem.)
If you encrypt or add a decently long salt, you can at least have enough =
entropy
to make 100 or so bits' worth, or more if you do it better. You have to =
keep the
extra entropy secret but at least it is harder than just hashing a few =
billion
trials to match hashes.
-----Original Message-----
From: Amit Klein [mailto:aksecurity@gmail.com]
Sent: Friday, June 20, 2008 3:34 PM
To: Nathanael Hoyle
Cc: websecurity@webappsec.org
Subject: Re: [WEB SECURITY] Hashing and entropy
Nathanael Hoyle wrote:
> Oliver Lavery wrote:
>
> <snip>
>> The parameters of the problem as I see it are:
>>
>> 1) credit card numbers have roughly 10**16 distinct values, well=20
>> below 2**128 (MD5) much less 2**160 (SHA1)
>>
>
> I would point out that the practical range may be narrowed by an=20
> attacker. IIRC, all Visa card numbers start with a 4, and all=20
> MasterCard ones start with a 5. These two cases account for a huge=20
> proportion of all CC numbers. In either of these cases, the range is=20
> 10**15 * 2, which is notably smaller.
It's much worse - check out =
http://en.wikipedia.org/wiki/Credit_card_numbers
-Amit
-------------------------------------------------------------------------=
---
Join us on IRC: irc.freenode.net #webappsec
Have a question? Search The Web Security Mailing List Archives:=20
http://www.webappsec.org/lists/websecurity/
Subscribe via RSS:=20
http://www.webappsec.org/rss/websecurity.rss [RSS Feed]
Join WASC on LinkedIn
http://www.linkedin.com/e/gis/83336/4B20E4374DBA
-----------------------------------------
This transmission may contain information that is privileged,
confidential, legally privileged, and/or exempt from disclosure
under applicable law. If you are not the intended recipient, you
are hereby notified that any disclosure, copying, distribution, or
use of the information contained herein (including any reliance
thereon) is STRICTLY PROHIBITED. Although this transmission and
any attachments are believed to be free of any virus or other
defect that might affect any computer system into which it is
received and opened, it is the responsibility of the recipient to
ensure that it is virus free and no responsibility is accepted by
JPMorgan Chase & Co., its subsidiaries and affiliates, as
applicable, for any loss or damage arising in any way from its use.
If you received this transmission in error, please immediately
contact the sender and destroy the material in its entirety,
whether in electronic or hard copy format. Thank you.
-------------------------------------------------------------------------=
---
Join us on IRC: irc.freenode.net #webappsec
Have a question? Search The Web Security Mailing List Archives:=20
http://www.webappsec.org/lists/websecurity/
Subscribe via RSS:=20
http://www.webappsec.org/rss/websecurity.rss [RSS Feed]
Join WASC on LinkedIn
http://www.linkedin.com/e/gis/83336/4B20E4374DBA
------_=_NextPart_001_01C8D31A.D556B8E0
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">
<META NAME=3D"Generator" CONTENT=3D"MS Exchange Server version =
6.5.7652.24">
<TITLE>RE: [WEB SECURITY] Hashing and entropy</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->
<P><FONT SIZE=3D2>Phew, finally get a break to respond to the thread I =
started ... sorry.<BR>
<BR>
Yes, as several people pointed out 16 digits is wrong. I actually =
checked this quickly with a reference while writing the earlier post and =
only managed to confuse myself :P<BR>
<BR>
Cards are 14-19 digits, with 2-6 consumed by BIN and one for the lunh =
code. That handy wiki page Amit posted has a worst case scenario of a 14 =
digit card with a three digit BIN and a Lunh, giving us 10 base 10 =
digits. *shudder*<BR>
<BR>
I'd like to figure out how big the total search space is for all BINs, =
but don't have the time this lunch break...<BR>
<BR>
<BR>
Why Hash?<BR>
---------<BR>
<BR>
A few people asked this. I've seen it justified by business requirements =
around comparing stored card numbers, which is a pretty obvious =
requirement for a lot of applications if you think about it. For =
example:<BR>
<BR>
- Application needs to be able to verify a new transaction against the =
card on file<BR>
<BR>
- Application needs to be able to create a list of all transactions for =
a single card. (Afaik more than one person can have the exact same CC # =
in the case of a shared card with secondary cardholders)<BR>
<BR>
Hashing isn't actually the problem, it's these requirements that lead to =
broken implementations. If you use a different random salt to store =
every card number, even if the salt is stored with the hash, the attack =
gets harder as each hash has to be broken independently. This could be =
better than encryption since it isn't reversible. Unfortunately you also =
loose the ability to compare card numbers, however.<BR>
<BR>
Collisions aren't as much a problem; collisions happen when two inputs =
hash to the same value ... not something that's affected by the =
entropy in the input afaict, it's just a product of the algorithm and =
it's output length.<BR>
<BR>
<BR>
Who would be silly enough to do this?!<BR>
--------------------------------------<BR>
<BR>
>From PCI 1.1:<BR>
3.4 Render PAN, at minimum, unreadable anywhere it is stored (including =
data on portable digital media, backup media, in logs, and data received =
from or stored by wireless networks) by using<BR>
any of the following approaches:<BR>
• Strong one-way hash functions (hashed indexes)<BR>
• Truncation<BR>
• Index tokens and pads (pads must be securely stored) [What?!]<BR>
• Strong cryptography with associated key management processes and =
procedures.<BR>
<BR>
<BR>
It's not silly, it's a best practice!<BR>
<BR>
<BR>
Encryption is better!<BR>
---------------------<BR>
<BR>
I'm not sure this is really true. Correct me if I'm wrong, =
IANACryptographer, but my thinking is that for any cryptographic =
function f(), and CC# x:<BR>
<BR>
y =3D f(x)<BR>
y' =3D f(x)<BR>
<BR>
if y =3D=3D y' then you're in trouble, provided the attacker can compute =
f().<BR>
<BR>
Symmetric crypto is probably not something you want to use to protect =
CC#s in an online transaction processing system since the key has to be =
stored with the data. Never mind that lots of people do this. If an =
attacker can get the cyphertext, it's reasonable to assume he can get =
the key. (Yeah you can hide it somewhere in memory, so I root your box, =
dump the memory, and use a single known plaintext to find the key in =
there or somesuch)<BR>
<BR>
Assymetric crypto is better, since you only need to keep the public key =
online. However, if the crypto is implemented such that comparing card =
numbers still works, then you have the exact same problem as with =
hashing. An attacker who has the CC #s will reasonably also have the =
public key, and can break the encryption through brute force by =
encrypting all possible plaintexts with the key. It's just slower.<BR>
<BR>
Why do you need to keep the key online? If it's an OLTP application like =
a payment processor or an ecom site, than the alternative when new CC#s =
arrive is to store them in plaintext and encrypt them only when the key =
is available. Maybe there's some way around this?<BR>
<BR>
<BR>
Solution?<BR>
---------<BR>
<BR>
Which gets us back to possible solutions. Thanks for the awesome blog =
link Bil.<BR>
<BR>
Maybe the question is just how much computational complexity would be =
enough for CC#s, and whether or not it's feasible for a system to =
implement it.<BR>
<BR>
Although a much better solution is to never, ever have to do comparisons =
online, I think. Hashing or Asymmetric crypto implemented such that the =
same card number will not always encrypt to the same ciphertext seems =
like the only really strong security to me...<BR>
<BR>
<BR>
Cheers,<BR>
~ol<BR>
<BR>
<BR>
-----Original Message-----<BR>
From: Glenn.Everhart@chase.com [<A =
HREF=3D"mailto:Glenn.Everhart@chase.com";>mailto:Glenn.Everhart@chase.com<=
/A>]<BR>
Sent: Fri 20/06/2008 14:12<BR>
To: aksecurity@gmail.com; nhoyle@hoyletech.com<BR>
Cc: websecurity@webappsec.org<BR>
Subject: RE: [WEB SECURITY] Hashing and entropy<BR>
<BR>
I figure 30 to 38 bits if you know the bank. Why does anyone want to =
hash<BR>
card numbers???<BR>
<BR>
Figuring out what number a hash corresponds to is comparable to doing =
the<BR>
same with SSN (also 9 digits) which would be the 30 bit case.<BR>
<BR>
Heck's bells: you might as well hash someone's age in years and expect =
that to<BR>
obscure it! (That's a bit easier but illustrates the problem.)<BR>
<BR>
If you encrypt or add a decently long salt, you can at least have enough =
entropy<BR>
to make 100 or so bits' worth, or more if you do it better. You have to =
keep the<BR>
extra entropy secret but at least it is harder than just hashing a few =
billion<BR>
trials to match hashes.<BR>
<BR>
-----Original Message-----<BR>
From: Amit Klein [<A =
HREF=3D"mailto:aksecurity@gmail.com";>mailto:aksecurity@gmail.com</A>]<BR>=
Sent: Friday, June 20, 2008 3:34 PM<BR>
To: Nathanael Hoyle<BR>
Cc: websecurity@webappsec.org<BR>
Subject: Re: [WEB SECURITY] Hashing and entropy<BR>
<BR>
<BR>
Nathanael Hoyle wrote:<BR>
> Oliver Lavery wrote:<BR>
><BR>
> <snip><BR>
>> The parameters of the problem as I see it are:<BR>
>><BR>
>> 1) credit card numbers have roughly 10**16 distinct values, =
well<BR>
>> below 2**128 (MD5) much less 2**160 (SHA1)<BR>
>><BR>
><BR>
> I would point out that the practical range may be narrowed by =
an<BR>
> attacker. IIRC, all Visa card numbers start with a 4, and =
all<BR>
> MasterCard ones start with a 5. These two cases account for a =
huge<BR>
> proportion of all CC numbers. In either of these cases, the =
range is<BR>
> 10**15 * 2, which is notably smaller.<BR>
<BR>
It's much worse - check out <A =
HREF=3D"http://en.wikipedia.org/wiki/Credit_card_numbers";>http://en.wikip=
edia.org/wiki/Credit_card_numbers</A><BR>
<BR>
-Amit<BR>
<BR>
-------------------------------------------------------------------------=
---<BR>
Join us on IRC: irc.freenode.net #webappsec<BR>
<BR>
Have a question? Search The Web Security Mailing List Archives:<BR>
<A =
HREF=3D"http://www.webappsec.org/lists/websecurity/";>http://www.webappsec=
.org/lists/websecurity/</A><BR>
<BR>
Subscribe via RSS:<BR>
<A =
HREF=3D"http://www.webappsec.org/rss/websecurity.rss";>http://www.webappse=
c.org/rss/websecurity.rss</A> [RSS Feed]<BR>
<BR>
Join WASC on LinkedIn<BR>
<A =
HREF=3D"http://www.linkedin.com/e/gis/83336/4B20E4374DBA";>http://www.link=
edin.com/e/gis/83336/4B20E4374DBA</A><BR>
<BR>
<BR>
<BR>
-----------------------------------------<BR>
This transmission may contain information that is privileged,<BR>
confidential, legally privileged, and/or exempt from disclosure<BR>
under applicable law. If you are not the intended recipient, =
you<BR>
are hereby notified that any disclosure, copying, distribution, or<BR>
use of the information contained herein (including any reliance<BR>
thereon) is STRICTLY PROHIBITED. Although this transmission =
and<BR>
any attachments are believed to be free of any virus or other<BR>
defect that might affect any computer system into which it is<BR>
received and opened, it is the responsibility of the recipient to<BR>
ensure that it is virus free and no responsibility is accepted by<BR>
JPMorgan Chase & Co., its subsidiaries and affiliates, as<BR>
applicable, for any loss or damage arising in any way from its use.<BR>
If you received this transmission in error, please immediately<BR>
contact the sender and destroy the material in its entirety,<BR>
whether in electronic or hard copy format. Thank you.<BR>
<BR>
-------------------------------------------------------------------------=
---<BR>
Join us on IRC: irc.freenode.net #webappsec<BR>
<BR>
Have a question? Search The Web Security Mailing List Archives:<BR>
<A =
HREF=3D"http://www.webappsec.org/lists/websecurity/";>http://www.webappsec=
.org/lists/websecurity/</A><BR>
<BR>
Subscribe via RSS:<BR>
<A =
HREF=3D"http://www.webappsec.org/rss/websecurity.rss";>http://www.webappse=
c.org/rss/websecurity.rss</A> [RSS Feed]<BR>
<BR>
Join WASC on LinkedIn<BR>
<A =
HREF=3D"http://www.linkedin.com/e/gis/83336/4B20E4374DBA";>http://www.link=
edin.com/e/gis/83336/4B20E4374DBA</A><BR>
<BR>
<BR>
</FONT>
</P>
</BODY>
</HTML>
------_=_NextPart_001_01C8D31A.D556B8E0--
Brought to you by http://www.webappsec.org
Search this site
|