Nedenfor er en artikkel jeg fant nylig. Dette et av de mest omfattende beskrivelser av PIN-bekreftelse Verdi (PVV) hacking.
Jeg trodde jeg ville gjenskape det her for min lokale referanse.
Som kommentar har blitt gjort om grammatikk brukt i den opprinnelige teksten, jeg har rettet opp noen av de åpenbare feil samtidig opprettholde sammenheng med det opprinnelige materialet.
http://69.46.26.132/ ~ biggold1/fastget2you/tutorial. php
--- Opprinnelig tekst ----
Forord
Har du noen gang lurt på hva som ville skje hvis du mister kredittkort eller debetkort, og noen finner den. Vil denne personen kunne ta ut penger fra en minibank gjette, annen, PIN-koden? Videre, hvis du var som finner noen kort vil du forsøke å gjette PIN og ta sjansen til å få noen enkle penger? Selvfølgelig er svaret på begge disse spørsmålene er "nei". Dette arbeidet har ikke avtale med andre spørsmål, er det et spørsmål om personlig etikk. Dette jeg forsøker å svare på det første spørsmålet.
All informasjon som brukes til dette arbeidet er offentlig, og kan fritt funnet i Internet. Resten er et spørsmål om matematikk og programmering, og dermed kan vi lære noe og ha det moro. Jeg avslører ingen hemmeligheter. Videre er målet (og endelige konklusjon) av dette arbeidet er å vise at PIN algoritmer er fortsatt sterk nok til å gi tilstrekkelig sikkerhet. Vi vet alle teknologi er ikke det svake punktet.
Dette arbeidet analyserer en av de vanligste PIN algoritmer, VISA PVV, brukt av mange ATM kort (kreditt-og debetkort) og prøver å finne ut hvordan resistente er å PIN gjette angrep. Ved å "gjette" Jeg trenger ikke bety å velge en tilfeldig PIN og prøver den i en minibank. Det er kjent at generelt vi får tre forsøk å angi riktig PIN-kode, hvis vi mislykkes minibank holder kortet. Som VISA PIN er firesifret lenge det er lett å utlede at sjansen for en tilfeldig PIN gjette er 3 / 10000 = 0,0003, det synes lite nok til å være sikker, det betyr at du trenger å miste kortet mer enn tre tusen ganger ( eller å miste mer enn tre tusen kort på samme tid:) inntil det er en rimelig sjanse for å tape penger.
Det jeg egentlig menes med "gjetter" var å bryte PIN algoritmen slik at gitt noen kort kan du umiddelbart kjenner den tilknyttede PIN. Derfor dette dokumentet studier at muligheten, analysere algoritme og foreslå en metode for angrepet. Til slutt gir vi et verktøy som implementerer angrepet og presentere resultater om anslått å ødelegge systemet. Merk at så lenge andre banktjenester sikkerhetsrelaterte algoritmer (andre PIN formater som IBM PIN eller kort validering signaturer som CVV eller CVC) ligner VISA PIN, samme analyser kan gjøres gir nesten samme resultater og konklusjoner.
VISA PVV algoritme
En av de vanligste PIN algoritmer er VISA PIN Kontrollkode Verdi (PVV). Kunden får en PIN-kode og en magnetisk stripe kortet. Kodet inn i magnet stripen er et firesifret tall, kalt PVV. Dette nummeret er en kryptografisk signatur for PIN-og andre data knyttet til kortet. Når en bruker skriver inn sin PIN minibanken leser magnetisk stripe, krypterer og sender denne informasjonen til en sentral datamaskin. Det en prøveordning PVV er beregnet ved hjelp av kunden tastet inn PIN-koden og kortet med en kryptografisk algoritme. Prøveordningen PVV er sammenlignet med PVV lagret i kortet, hvis de samsvarer med den sentrale datamaskinen tilbake til ATM autorisasjon for transaksjonen. Se mer detaljert.
Beskrivelsen av PVV algoritme kan finnes i to dokumenter knyttet i forrige side. Oppsummert det består i kryptering av en 8 byte (64 bit) streng med data, kalt transformert Security Parameter (TSP), med DES-algoritmen (DEA) i Electronic Code Book modus (ECB) ved hjelp av en hemmelig 64-biters nøkkel. Den PVV er utledet fra utdataene for kryptering, som er en 8 byte streng. De fire sifrene i PVV (fra venstre til høyre) tilsvarer de første fire desimaler (fra venstre til høyre) av produksjonen fra DES når regnet som en 16 heksadesimale tegn (16 x 4 bit = 64 bit) streng. Hvis det ikke finnes fire desimalar blant 16 heksadesimale tegn deretter PVV er fullført tatt (fra venstre til høyre) ikke desimal tegn og decimalizing dem ved hjelp av konvertering A-> 0, B-> 1, C-> 2, D -> 3, E-> 4, F-> 5. Her er et eksempel:
Produksjonen fra DES: 0FAB9CDEFFE7DCBA
PVV: 0975
Strategien for å unngå decimalization ved å hoppe tegn til fire desimaler finnes (som skulle nesten alle ganger som vi vil se nedenfor) er veldig smart fordi den unngår en viktig skjevhet i fordelingen av tall som har vist seg å være dødelig for andre systemer, selv om virkningen på dette systemet vil være mye lavere. Se også et relatert problem ikke gjelder VISA PVV.
Den TSP, sett på som en 16 heksadesimale tegn (64 biter) strengen er dannet (fra venstre til høyre) med 11 høyre sifrene i PAN (kortnummer) unntatt det siste sifferet (sjekk siffer), ett siffer fra 1 til 6 som velger hemmelig kryptere nøkkelen og til slutt fire siffer i PIN. Her er et eksempel:
PAN: 1234 5678 9012 3445
Key selektor: 1
PIN: 2468
TSP: 5678901234412468
Tydeligvis problemet med å bryte VISA PIN består i å finne den hemmelige kryptere nøkkelen for DES. Metoden for dette er å gjøre et "brute force" søk på nøkkelen plass. Merk at dette er ikke den eneste metoden, man kunne prøve å finne en svakhet i DEA, mange prøvde, men denne gamle standarden er fortsatt på bred bruk (nå erstattet av AES og RSA, skjønt). Dette viser at det er robust nok til at "brute force er den eneste gjennomførbare metoden (er det noen bedre angrep, men ikke praktisk i vårt tilfelle, for en oversikt se LASEC memo og for skitne detaljer se Biham & Shamir 1990, Biham & Shamir 1991, Matsui 1993, Biham & Biryukov 1994 og Heys 2001).
Nøkkelen selektor sifferet var svært sannsynlig innført for å dekke muligheten for en nøkkel kompromiss. Da de bare nødt til å utstede nye kort med en annen tast selektor. Voksne kortene kan erstattes med nye, eller bare minibanken kan transparent skrive en ny PVV (tilsvarende den nye nøkkelen og holde den samme PIN) neste gang kunden bruker hans / hennes kort. For å riste av sikkerhet alle brukere bør bli bedt om å endre sin PIN-koder, men det ville være pinlig for banken å forklare, og derfor svært sannsynlig ville de ikke gjøre slik forespørsel.
Forbereder angrepet
En "brute force-angrep består i å kryptere en TSP med kjente PVV bruke alle mulige kryptere tastene og sammenligne hvert fått PVV med kjente PVV. Når en kamp blir funnet vi har en kandidat tasten. Men hvor mange nøkler må vi prøve? Som vi sa over tasten er 64 bits lang, vil dette at vi må prøve 2 ^ 64 nøkler. Men dette er ikke sant. Faktisk bare 56 biter er effektive i DES nøkler fordi en bit (minst signifikante) ut av hver oktett ble historisk enerett som en kontrollsum for andre, i praksis de 8 biter (ett for hvert av de 8 octets) ignoreres.
Derfor DES nøkkelen plass er 2 ^ 56 nøkler. Hvis vi prøver alle disse tastene vil vi finner en og bare en kamp, tilsvarende banken hemmelig nøkkel? Absolutt ikke. Vi vil få mange samsvarende tastene. Dette er fordi PVV er bare en liten del (kvart) av DES utgang. Videre PVV er degenerated fordi noen av sifre (de mellom 0 og 5 etter siste sett fra venstre til høyre, siffer mellom 6 og 9) kan komme fra en desimal siffer eller fra en decimalized heksadesimale siffer av DES utgang. Dermed mange nøkler vil produsere en DES utgang som gir de samme samsvarende PVV.
Så hva kan vi gjøre for å finne den virkelige nøkkelen blant de andre falske positive nøklene? Bare vi har til å kryptere et sekund ulike TSP, også kjent PVV, men bruker bare kandidatsiden tastene som ga en positiv samsvarende med den første TSP-PVV par. Imidlertid er det ingen garanti for vi vil ikke komme igjen mange falske positive sammen med ekte tast. Hvis det er slik, trenger vi en tredel TSP-PVV paret gjenta prosessen og så videre.
Før vi starter våre angrep må vi vite hvor mange TSP-PVV parene vi trenger. For at vi har for å beregne sannsynligheten for en tilfeldig DES output å gi en samsvarende PVV bare ved en tilfeldighet. Det er flere måter å beregne dette nummeret, og her vil jeg bruke en enkel tilnærming enkle å forstå, men som krever litt bakgrunnsinformasjon i matematikk av sannsynlighet.
En sannsynlighet kan alltid bli sett på som forholdet mellom gode saker til mulige tilfeller. I vårt problem antall mulige tilfeller er gitt av permutation av 16 elementer (0 til F heksadesimaltall) i en gruppe på 16 av dem (16 heksadesimaltall av DES output). Dette er gitt ved 16 ^ 16 ~ 1,8 * 10 ^ 19 som selvfølgelig faller sammen med 2 ^ 64 (forskjellige tall av 64 biter). Dette settet med tall kan bli delt opp i fem kategorier:
De med minst fire desimaler (0 til 9) blant de 16 heksadesimaltall (0 til F) av DES utgang.
De med nøyaktig bare tre desimalar.
De med nøyaktig to desimalar.
De med nøyaktig én desimal siffer.
Those with no decimal digits (all between A and F).
Let’s calculate how many numbers fall in each category. 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. The program only displays one message at the beginning, the starting position taken from the checkpoint file if any, after that nothing more is displayed.
The DES algorithm is a key point in the program, it is therefore very important to optimize its speed. I tested several implementations: libdes, SSLeay, openssl, cryptlib, nss, libgcrypt, catacomb, libtomcrypt, cryptopp, ufc-crypt. The DES functions of the first four are based on the same code by Eric Young and is the one which performed best (includes optimized C and x86 assembler code). Thus I chose libdes which was the original implementation and condensed all relevant code in the files encrypt.c (C version) and x86encrypt.s (x86 assembler version). The code is slightly modified to achieve some enhancements in a brute force attack : the initial permutation is a fixed common steep in each TSP
