Breaking VISA PIN

Onsdag 2 juli 2008 @ 12:38 | Bank og Eftpos

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 lett å 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 eksakt 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. Forventet antall falske positive i andre søk (begrenset til den positive nøkler funnet i første søk) vil være (t * p) * p, for en tredje søk blir ((t * p) * p) * p og så videre. Således for n søker forventet antall falske positive blir t * p ^ n.

Vi kan få antall søk nødvendig å forvente bare en falsk positiv ved uttrykker ligningen t * p ^ n = 1 og løse for n. Så n lik til logaritmen i basen p 1 / t, som med egenskaper logarithms det gir n = log (1 / t) / log (p) ~ 4.2. Siden vi ikke kan gjøre en brøk søk er det beleilig å runde opp dette antallet. Derfor hva er forventet antall falske positive dersom vi utfører fem søker? Det er ikke * p ^ 5 ~ 0,0007 eller ca 1 av 1400. Derfor bruker fem TSP-PVV parene er trygt å få oppfylt hemmelig nøkkel uten falske positiver.

Angrepet

Når vi vet at vi trenger fem TSP-PVV parene, hvordan får vi dem? Selvsagt trenger vi minst ett kort med kjente PIN, og på grunn av innholdet av PVV algoritmen, som er det eneste vi trenger. Med andre PIN-systemer, slik som IBM, ville vi trenger fem kort, men dette er ikke nødvendig med VISA PVV algoritme. Vi må bare lese magnetiske stripe og deretter endrer du PIN-fire ganger, men leser kortet etter hver endring.

Det er nødvendig å lese magnetiske stripe på kortet for å få PVV og kryptere nøkkelen selektor. Du kan kjøpe en kommersiell magnetiske stripe reader eller lage en selv følge instruksjonene du finner i den forrige siden og koblinger der. Når du har en leser se denne beskrivelsen av standard magnetiske spor for å finne ut hvordan du får PVV fra data leses. I dette dokumentet på PVV feltet i spor 1 og 2 skal være fem tegn lang, men faktisk sant PVV består av de fire siste sifrene. Den første av de fem tallene er nøkkelen selektor. Jeg har bare sett kort med verdien 1 i dette tallet, som er i overensstemmelse med standarden og med hemmelig nøkkel aldri skulle bli (og dermed de ikke trenger å flytte til en annen viktig endring velgeren).

Jeg gjorde et enkelt C-program, getpvvkey.c, for å utføre angrepet. Det består av en løkke til å prøve alle mulige nøkler for å kryptere den første TSP, hvis avledet PVV Kmp sanne PVV en ny TSP er prøvd, og så videre inntil det er endret, hvor nøkkelen er forkastet, og en ny er forsøkt, eller de fem avledet PVVs match tilsvarende sant PVVs, og da kan vi anta at vi fikk banken hemmelig nøkkel imidlertid loopen går videre til den exhausts tasten plass. Dette er gjort for å forsikre finner vi den egentlige nøkkelen fordi det er en sjanse (men svært lav) første nøkkelen funnet er en falsk positiv.

Det er forventet at programmet ville ta svært lang tid å fullføre og å minimere risikoen for strømbrudd kuttet, datamaskinen henge ut osv. det gjør sjekkpunkter i filen getpvvkey.dat fra tid til annen (det nøyaktige tidspunktet avhenger av hastighet på datamaskinen, er det rundt en time for de raskeste datamaskiner nå er i bruk). Av samme grunn dersom en positiv nøkkelen er funnet den er skrevet på filen getpvvkey.key. Programmet viser bare én melding i begynnelsen, den startposisjon hentet fra Checkpoint filen hvis noen, etter at noe mer blir vist.

The DES-algoritmen er et sentralt punkt i programmet, er det derfor svært viktig å optimalisere hastighet. Jeg testet flere implementeringer: libdes, SSLeay, openssl, cryptlib, NSS, libgcrypt, catacomb, libtomcrypt, cryptopp, ufc-CRYPT. The DES funksjoner av de fire første er basert på den samme koden av Eric Young og er den som har best resultat (inkluderer optimalisert C og x86 Assembler code). Derfor jeg valgte libdes som var det opprinnelige implementeringen og kondenseres alle relevante koden i filer encrypt.c (C-versjon) og x86encrypt.s (x86 Assembler versjon). Koden er litt modifisert for å oppnå noen forbedringer i et "brute force-angrep: de første permutation er en fast felles bratt i hvert TSP kryptering og derfor kan gjøres bare én gang på begynnelsen. En annen forbedring er at jeg skrev en helt ny setkey funksjon (jeg kalte det nextkey) som er optimal for et "brute force loop.

For å få programmet arbeider du bare å skrive inn i tilsvarende plass fem TSPs og deres PVVs og deretter kompilere den. Jeg har testet den bare i UNIX plattformer bruker Makefile Makegetpvvkey å kompilere (bruk kommandoen "make-f Makegetpvvkey"). Det kan samle seg på andre systemer, men du må kanskje fikse en del ting. Pass på at definisjonen av type long64 tilsvarer en 64-biters heltall. I prinsippet er det ingen avhengighet på endianness av prosessor. Jeg har blitt utarbeidet og kjøre den på Pentium-Linux, Alpha-Tru64, MIPS-IRIX og SPARC-Solaris. Hvis du ikke har og ikke ønsker å installere Linux (du ikke vet hva du mangler ;-) du fortsatt har valget mellom å kjøre Linux på CD og bruke programmet, se min side kjører Linux uten å installere den.

Når du har funnet det hemmelige bank-tasten hvis du vil finne PIN for et tilfeldig kort du bare å skrive et lignende program (sorry jeg har ikke skrevet det, jeg er altfor lat:) som ville prøve alle 10 ^ 4 PIN-koder ved å generere tilsvarende TSP, kryptere den med (ikke lenger) hemmelig nøkkel, deriving den PVV og sammenligne den med PVV i magnetiske stripe av kortet. Du vil få en kamp for den sanne PIN. Bare en kamp? Husk hva vi så ovenfor, har vi en sjanse til 0,0001 at en tilfeldig kryptering matcher PVV. Vi prøver 10000 PINS (og derfor TSPs) dermed forventer vi 10000 * 0,0001 = 1 falsk positiv i gjennomsnitt.

Dette er et veldig interessant resultat, det betyr at det i gjennomsnitt hvert kortet har to gyldig PINS: kundens PIN og forventet falske positive. Jeg kaller det "falske", men merk at så lenge den genererer den sanne PVV er en PIN-kode som gyldig som kunden en. Videre er det ingen måte å vite noe som er der, selv for ATM; eneste kunde vet. Selv om falske positive var ikke gyldig som PIN, vil du fortsatt ha tre forsøk på minibank likevel nok i gjennomsnitt. Derfor sannsynligheten vi beregnet i begynnelsen av dette dokumentet om tilfeldige gjette i PIN må korrigeres. Egentlig er det to ganger denne verdien, dvs. det er 0,0006 eller en av mer enn 1600, likevel trygt lav.

Resultater

Det er viktig å optimalisere kompilering av programmet og til å publisere den på raskest mulig prosessor på grunn av lang forventet kjøring. Jeg syntes at kompilatoren optimalisering flagget-O får bedre ytelse, tenkte noen forbedring oppnås legge til-fomit-ramme-pekeren flagget på Pentium-Linux, på-topp flagg på Alpha-Tru64, det IPA flagget på MIPS-IRIX og-rask flagg på SPARC-Solaris. Spesielle flagg (-DDES_PTR-DDES_RISC1-DDES_RISC2-DDES_UNROLL-DASM) for DES koden generelt har fordeler også. Alle disse flagg allerede har blitt testet og jeg valgte den beste kombinasjonen for hver prosessor (se Makefile), men du kan prøve å finjustere andre flagg.

Ifølge mine tester de beste resultatene er oppnådd med AMD Athlon 1600 MHz prosessor, overstiger 3.4 millioner nøkler per sekund. Interessant det blir bedre resultater enn Intel Pentium IV 1800 MHz og 2000 MHz (se figur nedenfor, klikke på dem for å forstørre). Jeg tror dette skyldes enkelte I / O metning, sikkert hurtigbuffer eller Memory Access, at AMD-prosessor (som har en halv buffer av Pentium) eller hovedkortet som det er i gang, klarer å unngå. I den første figuren nedenfor kan du se at DES bryte hastighet på alle prosessorer har mer eller mindre en lineær relasjon med prosessorhastighet, unntatt for de to Intel Pentium jeg nevnte tidligere. Dette er logisk, det betyr at for en dobbel prosessor hastighet du får dobbelt bryte fart, men pass på saturation effekter, i dette tilfellet er det bedre for AMD Athlon 1600 MHz, som vil bli enda billigere enn Intel Pentium 1800 MHz eller 2000 MHz.

I den andre figuren ser vi nærmere på hva vi ville kalle egenverdi DES bryte strømmen til prosessoren. Jeg får denne verdien bare dele break hastighet av prosessorhastigheten, det får vi antall DES nøkler prøvd per sekund og per MHz. Dette er et mål for ytelsen til prosessoren type uavhengig av dens hastighet. Resultatene viser at den beste prosessor for denne oppgaven er det AMD Athlon, deretter kommer det Alpha og meget nært etter at det er Intel Pentium (bortsett fra høyere hastighet de som utfører svært dårlig på grunn av metning effekt). Neste er MIPS-prosessor og i den siste plassen er SPARC. Noen Alpha og MIPS-prosessorer ligger nederst på skalaen fordi de tidlige utgivelser ikke inkludert ekstrautstyr for sent versjoner. Merk at jeg inkluderte resultatet for x86-prosessorer for C og Assembler kode så er det en stor forskjell. Det synes som gcc er ikke en god generator av optimalisert maskin, men selvsagt vi ikke vet om en manuell optimalisering av Assembler koden for andre prosessorer (Alpha, MIPS, SPARC) vil øke sine resultater i forhold til det opprinnelige C kompilatorene (Jeg brukte ikke gcc for disse andre plattformer) som det skjer med x86-prosessor.