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 består av 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.
De uten desimaler (alle mellom A og F).
La oss regne ut hvor mange tall faller i hver kategori. Hvis vi merke 16 heksadesimaltall av DES utgang som X1 til x16 så vi kan merke de første fire desimalar av et gitt antall den første kategorien som Xi, XJ, Xk og Xl. Antallet forskjellige kombinasjoner med denne profilen er gitt ved produktet 6 i-1 * 10 * 6j-i-1 * 10 * 6k-j-1 * 10 * 6 LK-1 * 10 * 1616-l der 6 ' er kommet fra flere muligheter for en A til F siffer, de 10 er kommet fra mulighetene for a 0 til 9 siffer, og 16 kommer fra mulighetene for en 0 til F siffer. Nå er de totale tallene i den første kategorien er bare oppgitt av oppsummering av dette produktet over i, j, k, l fra 1 til 16, men med i <j <k <l. Hvis du gjør noen matematiske arbeid du vil se denne lik til produktet av 104 / 6 med oppsummering over i fra 4 til 16 av (i-1) * (i-2) * (i-3) * 6i-4 * 16 16-i ~ 1,8 * 1019.
I tilsvarende antall tilfeller i den andre kategorien er gitt av oppsummering over i, j, k fra 1 til 16 med i <j <k av produktet 6i-1 * 10 * 6j-i-1 * 10 * 6k-j -1 * 10 * 616-k som du kan arbeide det ut til å være 16! / (3! * (16-13)!) * 103 * 6 13 = 16 * 15 * 14 / (3 * 2) * 103 * 613 = 56 * 104 * 613 ~ 7,3 * 1015. Tilsvarende for tredje kategori har vi oppsummering over i, j fra 1 til 16 med i <j av 6 i-1 * 10 * 6j-i-1 * 10 * 616-j som tilsvarer 16! / (2! * (16-14)!) * 102 * 614 = 2 * 103 * 615 ~ 9,4 * 1014. Igjen, for fjerde kategorien har vi oppsummering over i fra 1 til 16 av 6i-1 * 10 * 616-i = 160 * 615 ~ 7,5 * 1013. Og endelig antall tilfeller i den femte kategorien er gitt av permutation av seks elementer (A til F sifre) i en gruppe på 16, det vil si 616 ~ 2,8 * 1012.
Jeg håper du har fulgt beregninger opptil er den tyngste delen er ferdig. Nå som et bevis på at alt er riktig kan du summen av antall tilfeller i 5 kategorier og se det tilsvarer det totale antallet mulige tilfeller beregnes før. Gjøre operasjoner bruker 64 bits eller avrunding (for flottører) eller overflyt (for heltall) feil vil ikke la deg få nøyaktig resultat.
Hittil har vi beregnet antall mulige tilfeller i hver av fem kategorier, men vi er interessert i å skaffe det antall gunstig tilfeller stedet. Det er veldig enkelt å utlede sistnevnte fra det tidligere så dette er bare å fikse en kombinasjon av de fire desimaler (eller ønsket heksadesimaltall hvis det ikke finnes fire desimalar) av PVV i stedet for å la dem gratis. I praksis betyr dette dreie 10 står i formelen ovenfor i 1 og den nødvendige mengden 6 står i 1's hvis det ikke finnes fire desimalar. Det er vi nødt til å dele det første resultatet av 104, den andre med 103 * 6, den tredje en av 102 * 62, den fjerde en av 10 * 63 og den femte av 64. Deretter antall gode saker i de fem kategoriene er ca 1,8 * 1015, 1,2 * 1012, 2,6 * 1011, 3,5 * 1010, 2,2 * 109 hhv.
Nå har vi muligheten til å få tak i hva som er sannsynligheten for et DES output å matche en PVV ved en tilfeldighet. Vi må bare legge til de fem numrene til gode saker og dele det på det totale antallet mulige tilfeller. Gjør det vi får at sannsynligheten er svært omtrent 0.0001 eller én av ti tusen. Er det rart denne brønnen avrundet resultatet? Ikke i det hele tatt, bare ta en titt på tallene vi beregnet ovenfor. Den første kategorien dominerer med flere bestillinger av omfanget antall gode og mulige tilfeller. Dette er ganske intuitivt som det synes klart at det er svært lite sannsynlig ikke har fire desimaler (10 sjansene av 16 per siffer) blant 16 heksadesimale tall. Vi så tidligere at forholdet mellom antall mulige og gode saker i den første kategorien er en divisjon av 10 ^ 4, det er der vårt resultat p = 0,0001 kommer fra.
Vårt mål for alle disse beregningene var å finne ut hvor mange TSP-PVV parene vi må gjennomføre en vellykket "brute force-angrep. Nå har vi muligheten til å beregne den forventede antall falske positive i første søk vil det være antall rettssaker ganger sannsynligheten for en enkelt tilfeldig falske positive, dvs. t * p hvor t = 2 ^ 56, størrelsen på nøkkelen plass. Dette utgjør om lag 7,2 * 10 ^ 12, en ganske stort antall. 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 encryption and therefore can be made just one time at the beginning. Another improvement is that I wrote a completely new setkey function (I called it nextkey) which is optimum for a brute force loop.
To get the program working you just have to type in the corresponding place five TSPs and their PVVs and then compile it. I have tested it only in UNIX platforms, using the makefile Makegetpvvkey to compile (use the command “make -f Makegetpvvkey”). It may compile on other systems but you may need to fix some things. Be sure that the definition of the type long64 corresponds to a 64 bit integer. In principle there is no dependence on the endianness of the processor. I have successfully compiled and run it on Pentium-Linux, Alpha-Tru64, Mips-Irix and Sparc-Solaris. If you do not have and do not want to install Linux (you don’t know what you are missing ;-) you still have the choice to run Linux on CD and use my program, see my page running Linux without installing it.
Once you have found the secret bank key if you want to find the PIN of an arbitrary card you just have to write a similar program (sorry I have not written it, I’m too lazy :) that would try all 10^4 PINs by generating the corresponding TSP, encrypting it with the (no longer) secret key, deriving the PVV and comparing it with the PVV in the magnetic stripe of the card . You will get one match for the true PIN . Only one match? Remember what we saw above, we have a chance of 0.0001 that a random encryption matches the PVV . We are trying 10000 PINs (and therefore TSPs) thus we expect 10000 * 0.0001 = 1 false positive on average.
This is a very interesting result, it means that, on average, each card has two valid PINs: the customer PIN and the expected false positive. I call it “false” but note that as long as it generates the true PVV it is a PIN as valid as the customer’s one. Furthermore, there is no way to know which is which, even for the ATM; only customer knows. Even if the false positive were not valid as PIN , you still have three trials at the ATM anyway, enough on average. Therefore the probability we calculated at the beginning of this document about random guessing of the PIN has to be corrected. Actually it is twice that value, ie, it is 0.0006 or one out of more than 1600, still safely low.
Results
It is important to optimize the compilation of the program and to run it in the fastest possible processor due to the long expected run time. I found that the compiler optimization flag -O gets the better performance, thought some improvement is achieved adding the -fomit-frame-pointer flag on Pentium-Linux, the -spike flag on Alpha-Tru64, the -IPA flag on Mips-Irix and the -fast flag on Sparc-Solaris. Special flags (-DDES_PTR -DDES_RISC1 -DDES_RISC2 -DDES_UNROLL -DASM) for the DES code have generally benefits as well. All these flags have already been tested and I chose the best combination for each processor (see makefile) but you can try to fine tune other flags.
According to my tests the best performance is achieved with the AMD Athlon 1600 MHz processor, exceeding 3.4 million keys per second. Interestingly it gets better results than Intel Pentium IV 1800 MHz and 2000 MHz (see figures below, click on them to enlarge). I believe this is due to some I/O saturation, surely cache or memory access , that the AMD processor (which has half the cache of the Pentium) or the motherboard in which it is running, manages to avoid. In the first figure below you can see that the DES breaking speed of all processors has more or less a linear relationship with the processor speed, except for the two Intel Pentium I mentioned before. This is logical, it means that for a double processor speed you’ll get double breaking speed, but watch out for saturation effects, in this case it is better the AMD Athlon 1600 MHz, which will be even cheaper than the Intel Pentium 1800 MHz or 2000 MHz.
In the second figure we can see in more detail what we would call intrinsic DES break power of the processor. I get this value simply dividing the break speed by the processor speed, that is, we get the number of DES keys tried per second and per MHz. This is a measure of the performance of the processor type independently of its speed. The results show that the best processor for this task is the AMD Athlon, then comes the Alpha and very close after it is the Intel Pentium (except for the higher speed ones which perform very poor due to the saturation effect). Next is the Mips processor and in the last place is the Sparc. Some Alpha and Mips processors are located at bottom of scale because they are early releases not including enhancements of late versions. Note that I included the performance of x86 processors for C and assembler code as there is a big difference . It seems that gcc is not a good generator of optimized machine code, but of course we don’t know whether a manual optimization of assembler code for the other processors (Alpha, Mips, Sparc) would boost their results compared to the native C compilers (I did not use gcc for these other platforms) as it happens with the x86 processor.
Update
Here is an article where these techniques may have been used.
http://redtape.msnbc.com/2008/08/could-a-hacker.html
