[WEB SECURITY] Hashing and entropy

Fri Jun 20 17:15:58 EDT 2008

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 

- 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. 

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. 

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:
• Strong one-way hash functions (hashed indexes)
• Truncation
• Index tokens and pads (pads must be securely stored) [What?!]
• Strong cryptography with associated key management processes and procedures. 

It's not silly, it's a best practice! 

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 = f(x)
y' = f(x)

if y == 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. 

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 at chase.com [mailto:Glenn.Everhart at chase.com]
Sent: Fri 20/06/2008 14:12
To: aksecurity at gmail.com; nhoyle at hoyletech.com
Cc: websecurity at webappsec.org
Subject: RE: [WEB SECURITY] Hashing and entropy

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. 

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 at gmail.com]
Sent: Friday, June 20, 2008 3:34 PM
To: Nathanael Hoyle
Cc: websecurity at 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 
>> below 2**128 (MD5) much less 2**160 (SHA1)
>>
>
> I would point out that the practical range may be narrowed by an 
> attacker.  IIRC, all Visa card numbers start with a 4, and all 
> MasterCard ones start with a 5.  These two cases account for a huge 
> proportion of all CC numbers.  In either of these cases, the range is 
> 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: 
http://www.webappsec.org/lists/websecurity/

Subscribe via RSS: 
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: 
http://www.webappsec.org/lists/websecurity/

Subscribe via RSS: 
http://www.webappsec.org/rss/websecurity.rss [RSS Feed]

Join WASC on LinkedIn
http://www.linkedin.com/e/gis/83336/4B20E4374DBA

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webappsec.org/pipermail/websecurity_lists.webappsec.org/attachments/20080620/804063e2/attachment.html>