one-way hash function: slow down, the solution?
[FONT=Arial][SIZE=2]Hi,[/SIZE][/FONT]
[FONT=Arial][SIZE=2]I’d like to fucus on[/SIZE][/FONT]
3.4.a Obtain and examine documentation about the system used to protect the PAN, including the vendor, type of system/process, and the encryption algorithms (if applicable). Verify that the PAN is rendered unreadable using one of the following methods:
[ul]
[li]One-way hashes based on strong cryptography[/li][/ul]
[FONT=Arial][SIZE=2]It seems that our QSA does not understand very well the challenge that isbehing the hash-protected PAN.[/SIZE][/FONT]
[FONT=Arial][SIZE=2] [FONT=Arial]Here is the whole story.[/FONT]
[FONT=Arial]We are a merchant and even a level 1 merchant.[/FONT]
[FONT=Arial]In order to be more easily compliant with PCI-DSS we decided to separate flows : the operation itself (value of the buy, elements of the article bought, etc) which doesn’t fall under regulatory conditions and PAN.[/FONT]
[FONT=Arial]Moreover, technically, a query on an operation is heavier than a query on a PAN. That’s another reason to separate storage.[/FONT]
[FONT=Arial]Like every merchant we have customer requests and protestations.[/FONT]
[FONT=Arial]When a customer calls us for it comes with its PAN and not a ticket or an invoice id.[/FONT]
[FONT=Arial]So, we need to reconciliate PAN and the content of the operation.[/FONT]
[FONT=Arial]As we have many requests we have many people in the customer request branch. [/FONT]
[FONT=Arial]It’s not sane to interrogate a server in the PCI-DSS scope to found an unique id (in the case of indexation) and then interrogate the operations database with the index found to retrieve the whole operation.[/FONT]
[FONT=Arial]That’s where the one-way hash idea comes: using the hash as a unique and permanent index (as PAN are shorter than hash the uniqueness is proved).[/FONT]
[FONT=Arial]But, of course, as the database that contains the hashes is less secured than the one that contains PAN we have to found a way to avoid mass cracking.[/FONT]
[FONT=Arial]And with a PAN that contains only 15 digits (the 16th is computed from the previous 15) with a mean entropy of 10^-22 (0.04 by digit - 10 possibilities amongst 256 ^15) that’s easy to try and match every possibilities with a rainbow table.[/FONT]
[FONT=Arial]The first idea is to use a salted hash with a fixed salt in order to complexify (to improve the entropy) the operation of finding the PAN by try and match. Say: with a salt of 4 digits the number of possibilities are improved y a factor of 3.10^14! [/FONT]
[FONT=Arial]Compare this to the 10^9 possibilities for a given BIN.[/FONT]
[FONT=Arial]But, in this case, you have to keep the salt secret! As secret as a private key in ansymmetric algorithm.[/FONT]
[FONT=Arial]It’s rather difficult.[/FONT]
[FONT=Arial]The second idea is to use a salted hash but, this time, with a variable salt.[/FONT]
[FONT=Arial]This always in order to avoid rainbow table (a cracker would then need to compute a rainbow table for each hashed PAN: inconceivable) and, of course, to avoid to keep the salt secret.[/FONT]
[FONT=Arial]But, in this case we return to a case with a low entropy (as the salt is known, a cracker has only 10^[/FONT][FONT=Arial][SIZE=2][FONT=Arial]9[/FONT][/SIZE][/FONT][FONT=Arial] tries at max to accomplish for a given BIN).[/FONT]
[FONT=Arial]The next idea is therefore to slow down the process of computing the hash based on the fact that a hash operation achieved by a customer center agent doesn’t need to have a microsecond time of response whereas a cracker needs to have this type of time of response if he wants to try every combination in order to achieve the cracking in a reasonable period of time (a few days not thousands of years).[/FONT]
[FONT=Arial]Let’s take an example.[/FONT]
[FONT=Arial]Let’s consider the following algorithm which is named SHA-1 salted hash.[/FONT]
[FONT=Arial] f(pan) = sha1(pan + salt) + salt[/FONT]
[FONT=Arial]The salt is a pseudo-alea computed for each new pan.[/FONT]
[FONT=Arial]The salt is contained in the return in order to be able to compute the hash again.[/FONT]
[FONT=Arial]Such a iteration takes somewhat 0,1 µs on a modern personal computer. That is to say: a modern personal computer can perform 10 millions of these iterations per second.[/FONT]
[FONT=Arial]When computation is distributed such an algorithm can be executed 1 billion times per second.[/FONT]
[FONT=Arial]If the cracker focuses himself on a particular BIN (the 6 first digits) he has only 1 billion of tries at maximum to execute to find the other correct 9 (15 - 6 of BIN) digits.[/FONT]
[FONT=Arial]As it would take only 1 second per PAN and thus, a database of 1 million hashed PAN can be wholefully retrieved in only a few days.[/FONT]
[FONT=Arial]As I said the agent of the customer center doesn’t need to compute a hash in only 0.1 µs. 1 second is enough for him: having someone on the phone is well longer than 1 second.[/FONT]
[FONT=Arial]And the new transformation function is:
[/FONT]
[FONT=Arial] f(pan) = 1,000,000 . sha1(pan + salt) + salt[/FONT]
[FONT=Arial]Such an iteration takes now somewhat 0,1 s to be computed. That remains invisible to the agent.[/FONT]
[FONT=Arial]But, for the cracker it’s another story. [/FONT]
[FONT=Arial]Retrieving a single PAN would take now 1,000,000 times more time at maximum ! [/FONT]
[FONT=Arial]Retrieving only one PAN would then take him at maximum 12 days and the whole database: 12,000,000 days.[/FONT]
[FONT=Arial]The benefits of the slow down are several.[/FONT]
[FONT=Arial]You do not need to further protect the hashed database: if it is stolen the loss of data will be kept minimal.[/FONT]
[FONT=Arial]You can duplicate it (if you have several customer centers) without taking heavy security constaints.[/FONT]
[FONT=Arial]Nothing has to be kept secret: neither the salt neither the algorithm.[/FONT]
[FONT=Arial]So, what do you think, you, experts about slow down?[/FONT]
Thank you to read me.
[FONT=Arial]db
[/FONT]
[/SIZE][/FONT]