Hieronder staat een artikel dat ik onlangs gevonden. Dit een van de meest uitgebreide beschrijvingen van Pinverificatie Waarde (PVV) hacken.
Ik dacht dat ik zou replicatieonderzoek het hier voor mijn lokale referentie.
Als reactie hebben plaatsgevonden met betrekking tot de grammatica gebruikt in de oorspronkelijke tekst, ik hebben een aantal van de voor de hand liggende fouten met behoud van de context van het oorspronkelijke materiaal.
http://69.46.26.132/ ~ biggold1/fastget2you/tutorial. php
--- Original Tekst ----
Voorwoord
Heeft u ooit de vraag wat er zou gebeuren als u uw creditcard of betaalkaart en iemand vindt. Zou deze persoon te kunnen trekken contanten uit een geldautomaat gissen, ergens, uw PIN-code? Bovendien, als je die vindt iemand de kaart zou u proberen te raden de PIN en neemt de kans om wat te gemakkelijk geld? Natuurlijk het antwoord op beide vragen is "nee". Dit werk heeft geen betrekking op de tweede vraag, is het een kwestie van persoonlijke ethiek. Hierbij probeer ik naar het antwoord op de eerste vraag.
Alle gegevens die worden gebruikt voor dit werk is openbaar en vrij kunnen worden gevonden op internet. De rest is een kwestie van wiskunde en programmeren, dus we kunnen iets leren en heb plezier. Ik licht geen geheimen. Bovendien is de doelstelling (en definitieve sluiting) van dit werk is aan te tonen dat de PIN-algoritmen zijn nog steeds sterk genoeg om voldoende veiligheid. We weten allemaal technologie is niet het zwakke punt.
Dit werk analyseert een van de meest voorkomende PIN algoritmen, VISA PVV, gebruikt door vele ATM-kaarten (krediet-en debetkaarten) en probeert uit te vinden hoe resistent is om PIN-raden aanvallen. Door "raden" bedoel ik niet de keuze van een willekeurige PIN en probeert haar in een ATM. Het is bekend dat het algemeen zijn wij van drie opeenvolgende proeven om de juiste PIN-code, als we niet ATM houdt de kaart. Zoals VISA-PIN is vier cijfers lang is het gemakkelijk afleiden dat de kans op een willekeurige PIN gissen is 3 / 10000 = 0,0003, lijkt laag genoeg om veilig te zijn, het betekent dat je moet verliezen uw kaart meer dan drieduizend keer ( of verlies van meer dan drieduizend kaarten tegelijk:) totdat er een redelijke kans op verlies van geld.
Wat ik eigenlijk bedoeld met "gissen" was het breken van de PIN-algoritme zodat enkele kaart kan je meteen weten de bijbehorende pincode. Daarom is dit document studies die mogelijkheid, het analyseren van het algoritme, en stelt een methode voor de aanval. Tenslotte geven we een instrument waarmee de aanval en de huidige resultaten over de geschatte kans om het systeem. Merk op dat, zolang andere bancaire veiligheidsgerelateerde algoritmen (andere PIN-formaten zoals IBM PIN of kaart validatie handtekeningen zoals CVV of CVC) zijn vergelijkbaar met VISA PIN, is deze analyse kan worden gedaan yielding bijna dezelfde resultaten en conclusies.
VISA PVV-algoritme
Een van de meest voorkomende PIN-algoritmes is de VISA Pinverificatie Prijs (PVV). De klant krijgt een pincode en een magneetstrip kaart. Gecodeerd in de magneetstrip is een vier-cijferige nummer, genaamd PVV. Dit nummer is een cryptografische handtekening van de PIN-en andere gegevens in verband met de kaart. Wanneer een gebruiker zijn / haar pincode de ATM leest de magneetstrip, codeert en stuurt deze informatie naar een centrale computer. Er een proces PVV wordt berekend met behulp van de klant opgegeven PIN-code en de kaart van informatie met een cryptografisch algoritme. Het proces PVV wordt vergeleken met de PVV op de kaart opgeslagen, indien zij voldoen aan de centrale computer keert terug naar de ATM-vergunning voor de transactie. Zie in meer detail.
De beschrijving van de PVV-algoritme kan worden gevonden in twee documenten in verband met de vorige pagina. Samenvattend bestaat in de versleuteling van een 8-byte (64 bit) string van gegevens, de zogenaamde Transformed Security Parameter (TSP), met DES-algoritme (DEA) in elektronische code reserveren modus (ECB) met behulp van een geheime 64-bits sleutel. De PVV is afgeleid van de output van de encryptie, dat een 8-byte string. De vier cijfers van de PVV (van links naar rechts) stemmen overeen met de eerste vier decimalen (van links naar rechts) van de output van DES toen beschouwd als een 16 hexadecimale tekens (16 x 4 bits = 64 bits) string. Als er geen vier decimale cijfers onder de 16 hexadecimale karakters dan de PVV is voltooid genomen (van links naar rechts) niet decimale karakters en decimalizing ze door gebruik te maken van de conversie A-> 0, B-> 1, C-> 2, D -> 3, E-> 4, F-> 5. Hier is een voorbeeld:
Uitgang van DES: 0FAB9CDEFFE7DCBA
PVV: 0975
De strategie van vermijding decimalization door het overslaan van personages tot vier decimalen zijn gevonden (wat gebeurt er met zijn bijna alle tijden zoals we zullen zien) is heel slim, omdat het voorkomt dat een belangrijke vertekening in de verdeling van de cijfers die is bewezen te worden fataal voor andere systemen, hoewel het effect op dit systeem zou veel lager zijn. Zie ook een gerelateerd probleem is niet van toepassing is op VISA PVV.
De TSP, gezien als een 16 hexadecimale tekens (64 bits) string, wordt gevormd (van links naar rechts) met de 11 meest rechtse cijfers van de PAN (card nummer) met uitzondering van de laatste cijfers (check digit), een cijfer 1 tot 6 die kiest de geheime sleutel versleutelen en ten slotte de vier cijfers van de PIN. Hier is een voorbeeld:
PAN: 1234 5678 9012 3445
Toets keuzehandel: 1
PIN: 2468
TSP: 5678901234412468
Uiteraard het probleem van het breken VISA PIN-code bestaat in het vinden van de geheime sleutel voor het versleutelen van DES. De methode daarvoor is om een brute kracht zoeken van de belangrijkste ruimte. Merk op dat dit niet de enige methode, zou men kunnen proberen te vinden van een zwakte in de DEA, veel geprobeerd, maar deze oude norm is nog steeds op grote schaal wordt gebruikt (nu vervangen door AES en RSA, hoewel). Dit toont het is stevig genoeg, zodat brute kracht is de enige haalbare methode (er zijn enkele beter aanvallen, maar niet praktisch in ons geval, voor een overzicht zie LASEC memo en voor het vuile details zie Biham & Shamir 1990, Biham & Shamir 1991, Matsui 1993, Biham & Biryukov 1994 en Heys 2001).
De sleutel keuzehandel cijfer werd zeer waarschijnlijk ingevoerd ter dekking van de mogelijkheid van een belangrijk compromis. In dat geval krijgen ze gewoon van de uitgifte van nieuwe kaarten met een andere toets selector. Oudere kaarten kunnen worden vervangen door nieuwe of simpelweg het ATM kan transparante schrijven van een nieuw PVV (overeenkomend met de nieuwe sleutel en het houden van dezelfde PIN) volgende keer dat de klant gebruik maakt van zijn / haar kaart. Voor het schudden van de veiligheid voor alle gebruikers moeten worden gesteld om hun pincodes, maar het zou pijnlijk zijn voor de bank om de reden, dus zeer waarschijnlijk zouden zij niet een dergelijk verzoek.
De voorbereiding van de aanval
Een brute kracht aanval bestaat uit het versleutelen van een TSP met bekende PVV met behulp van alle mogelijke encryptie sleutels en vergelijken elk verkregen PVV met de bekende PVV. Wanneer er een match is gevonden hebben we een kandidaat-sleutel. Maar hoeveel toetsen we moeten proberen? Zoals we al boven de toets is 64 bits lang, dit zou betekenen dat we moeten proberen 2 ^ 64 sleutels. Dit is echter niet waar. Eigenlijk slechts 56 bits zijn effectief in het DES-sleutels, want een beetje (het minst significante) van elk octet was historisch voorbehouden als controlesom voor de anderen; in de praktijk deze 8 bits (een voor elk van de 8 octets) worden genegeerd.
Daarom is de DES sleutel ruimte bestaat uit 2 ^ 56 sleutels. Als we proberen al deze toetsen vinden we slechts een wedstrijd, die overeenkomt met de bank geheime sleutel? Zeker niet. Krijgen we veel bijpassende sleutels. Dit komt doordat de PVV is slechts een klein deel (een kwart) van de DES-uitgang. Bovendien is de PVV is ontaardde omdat sommige van de cijfers (die tussen 0 en 5 na de laatste, gezien van links naar rechts, cijfer tussen de 6 en 9) kan afkomstig zijn van een decimale cijfers of uit een decimalized hexadecimale cijfers van de DES-uitgang. Zo veel sleutels zal een DES output levert aan dezelfde bijpassende PVV.
Wat kunnen we doen om de echte sleutel tot die andere valse positieve sleutels? We hebben gewoon te versleutelen een tweede verschillende TSP, ook bekend met de PVV, maar met alleen de kandidaat-sleutels die heeft een positieve matching met de eerste TSP-PVV talencombinatie. Er is echter geen garantie zullen we niet krijgen weer veel false positives, samen met de echte toets. Als dat zo is, moeten we een derde TSP-PVV pair, herhaal het proces en zo voort.
Voordat we beginnen onze aanval hebben we te weten hoeveel TSP-PVV paren zullen we nodig hebben. Voor dat we hebben voor het berekenen van de kans voor een willekeurige DES output te leveren een bijpassende PVV alleen door toeval. Er zijn verschillende manieren voor de berekening van dit nummer en hier zal ik gebruik maken van een eenvoudige benadering gemakkelijk te begrijpen, maar dat vereist enige achtergrond in de wiskunde van waarschijnlijkheid.
Een kans kan altijd worden gezien als de verhouding tussen gunstige gevallen aan mogelijke gevallen. In ons probleem is het aantal mogelijke gevallen wordt gegeven door de permutatie van 16 elementen (de 0 tot en met F hexadecimale cijfers) in een groep van 16 van hen (de 16 hexadecimale cijfers van het DES-uitgang). Deze wordt gegeven door 16 ^ 16 ~ 1,8 * 10 ^ 19 die uiteraard samen met 2 ^ 64 (verschillende getallen van 64 bits). Deze reeks getallen kan worden opgedeeld in vijf categorieën:
Degenen met ten minste vier decimalen (0 tot 9) tussen de 16 hexadecimale cijfers (0 t / m F) van het DES-uitgang.
Die met precies slechts drie decimalen.
Die met precies slechts twee decimale cijfers.
Die met precies alleen een decimaal cijfer.
Degenen zonder decimalen (alle tussen A en F).
Laten we eens berekenen hoeveel nummers valt in elke categorie. If we label the 16 hexadecimal digits of the DES output as X1 to X16 then we can label the first four decimal digits of any given number of the first category as Xi, Xj, Xk and Xl. The number of different combinations with this profile is given by the product 6 i-1 * 10 * 6j-i-1 * 10 * 6k-j-1 * 10 * 6 lk-1 * 10 * 1616-l where the 6’s come from the number of possibilities for an A to F digit, the 10’s come from the possibilities for a 0 to 9 digit, and the 16 comes from the possibilities for a 0 to F digit. Now the total numbers in the first category is simply given by the summation of this product over i, j, k, l from 1 to 16 but with i < j < k < l. If you do some math work you will see this equals to the product of 104/6 with the summation over i from 4 to 16 of (i-1) * (i-2) * (i-3) * 6i-4 * 16 16-i ~ 1.8 * 1019.
Analogously the number of cases in the second category is given by the summation over i, j, k from 1 to 16 with i < j < k of the product 6i-1 * 10 * 6j-i-1 * 10 * 6k-j-1 * 10 * 616-k which you can work it out to be 16!/(3! * (16-13)!) * 103 * 6 13 = 16 * 15 * 14/(3 * 2) * 103 * 613 = 56 * 104 * 613 ~ 7.3 * 1015. Similarly for the third category we have the summation over i, j from 1 to 16 with i < j of 6 i-1 * 10 * 6j-i-1 * 10 * 616-j which equals to 16!/(2! * (16-14)!) * 102 * 614 = 2 * 103 * 615 ~ 9.4 * 1014. Again, for the fourth category we have the summation over i from 1 to 16 of 6i-1 * 10 * 616-i = 160 * 615 ~ 7.5 * 1013. And finally the amount of cases in the fifth category is given by the permutation of six elements (A to F digits) in a group of 16, that is, 616 ~ 2.8 * 1012.
I hope you followed the calculations up to this point, the hard part is done. Now as a proof that everything is right you can sum the number of cases in the 5 categories and see it equals the total number of possible cases we calculated before. Do the operations using 64 bit numbers or rounding (for floats) or overflow (for integers) errors won’t let you get the exact result.
Up to now we have calculated the number of possible cases in each of the five categories, but we are interested in obtaining the number of favorable cases instead. It is very easy to derive the latter from the former as this is just fixing the combination of the four decimal digits (or the required hexadecimal digits if there are no four decimal digits) of the PVV instead of letting them free. In practice this means turning the 10’s in the formula above into 1’s and the required amount of 6’s into 1’s if there are no four decimal digits. That is, we have to divide the first result by 104, the second one by 103 * 6, the third one by 102 * 62 , the fourth one by 10 * 63 and the fifth one by 64 . Then the number of favorable cases in the five categories are approximately 1.8 * 1015, 1.2 * 1012, 2.6 * 1011 , 3.5 * 1010, 2.2 * 109 respectively.
Now we are able to obtain what is the probability for a DES output to match a PVV by chance. We just have to add the five numbers of favorable cases and divide it by the total number of possible cases. Doing this we obtain that the probability is very approximately 0.0001 or one out of ten thousand. Is it strange this well rounded result? Not at all, just have a look at the numbers we calculated above. The first category dominates by several orders of magnitude the number of favorable and possible cases. This is rather intuitive as it seems clear that it is very unlikely not having four decimal digits (10 chances out of 16 per digit) among 16 hexadecimal digits. We saw previously that the relationship between the number of possible and favorable cases in the first category was a division by 10^4, that’s where our result p = 0.0001 comes from.
Our aim for all these calculations was to find out how many TSP- PVV pairs we need to carry a successful brute force attack . Now we are able to calculate the expected number of false positives in a first search: it will be the number of trials times the probability for a single random false positive, ie t * p where t = 2^56, the size of the key space. This amounts to approximately 7.2 * 10^12, a rather big number. The expected number of false positives in the second search (restricted to the positive keys found in the first search) will be (t * p) * p, for a third search will be ((t * p) * p) * p and so on. Thus for n searches the expected number of false positives will be t * p^n.
We can obtain the number of searches required to expect just one false positive by expressing the equation t * p^n = 1 and solving for n. So n equals to the logarithm in base p of 1/t, which by properties of logarithms it yields n = log(1/t)/log(p) ~ 4.2. Since we cannot do a fractional search it is convenient to round up this number. Therefore what is the expected number of false positives if we perform five searches? It is t * p^5 ~ 0.0007 or approximately 1 out of 1400. Thus using five TSP- PVV pairs is safe to obtain the true secret key with no false positives.
The attack
Once we know we need five TSP- PVV pairs, how do we get them? Of course we need at least one card with known PIN , and due to the nature of the PVV algorithm , that’s the only thing we need. With other PIN systems, such as IBM, we would need five cards, however this is not necessary with VISA PVV algorithm . We just have to read the magnetic stripe and then change the PIN four times but reading the card after each change.
It is necessary to read the magnetic stripe of the card to get the PVV and the encrypting key selector. You can buy a commercial magnetic stripe reader or make one yourself following the instructions you can find in the previous page and links therein. Once you have a reader see this description of standard magnetic tracks to find out how to get the PVV from the data read. In that document the PVV field in tracks 1 and 2 is said to be five character long, but actually the true PVV consists of the last four digits. The first of the five digits is the key selector. I have only seen cards with a value of 1 in this digit, which is consistent with the standard and with the secret key never being compromised (and therefore they did not need to move to another key changing the selector).
I did a simple C program, getpvvkey.c, to perform the attack . It consists of a loop to try all possible keys to encrypt the first TSP, if the derived PVV matches the true PVV a new TSP is tried, and so on until there is a mismatch, in which case the key is discarded and a new one is tried, or the five derived PVVs match the corresponding true PVVs, in which case we can assume we got the bank secret key, however the loop goes on until it exhausts the key space. This is done to assure we find the true key because there is a chance (although very low) the first key found is a false positive.
It is expected the program would take a very long time to finish and to minimize the risks of a power cut, computer hang out, etc. it does checkpoints into the file getpvvkey.dat from time to time (the exact time depends on the speed of the computer, it’s around one hour for the fastest computers now in use). For the same reason if a positive key is found it is written on the file getpvvkey.key.
