Breaking VISA PIN
02 juli, 2008 i bank-och Eftpos
Nedan följer en artikel jag hittade nyligen. Detta ett av de mest omfattande beskrivningar av PIN Verification Value (PVV) dataintrång.
Jag trodde att jag skulle kopiera det här för min lokala referens.
Som kommentar har gjorts när det gäller grammatik som används i den ursprungliga texten har jag rättat några av de uppenbara fel utan att det sammanhang i det ursprungliga materialet.
http://69.46.26.132/ ~ biggold1/fastget2you/tutorial.php
--- Originaltexten ----
Förord
Har du någonsin undrat vad som skulle hända om du förlorar ditt kredit-eller betalkort och någon finner det. Skulle denna person ha möjlighet att ta ut kontanter från en bankomat gissa, på något sätt, din PIN-kod? Dessutom, om du var som finner någon kort skulle du försöka att ta den PIN-kod och ta chansen att få lite lätta pengar? Naturligtvis är svaret på båda frågorna bör "nej". Detta arbete behandlar inte den andra frågan, det är en fråga om personlig etik. Härmed försöka besvara den första frågan.
All den information som används för detta arbete är offentliga och kan hittas på Internet. Resten är en fråga om matematik och programmering, vilket vi kan lära oss något och ha lite kul. Jag avslöjar inga hemligheter. Dessutom är målet (och sista slutsats) av detta arbete är att visa att PIN-algoritmer är fortfarande stark nog att ge tillräcklig säkerhet. Vi alla vet att tekniken inte är den svaga punkten.
Detta arbete analyserar en av de vanligaste PIN-algoritmer, VISA PVV, som används av många ATM-kort (kredit-och betalkort) och försöker ta reda på hur resistent är att PIN gissar attacker. Genom att "gissa" Jag menar inte att välja en slumpmässig PIN och försöker det i en bankomat. Det är väl känt att i allmänhet vi får tre försök att ange rätt PIN, om vi inte ATM håller kortet. VISA PIN-koden är fyrsiffrig länge är det lätt att dra slutsatsen att risken för en slumpmässig PIN gissar är 3 / 10000 = 0,0003, det verkar lågt för att vara säker, betyder det att du måste förlora ditt kort mer än tre tusen gånger ( eller förlorar mer än tretusen kort på samma gång:) tills det finns en rimlig chans att förlora pengar.
Vad jag verkligen menas med "gissa" var att bryta PIN-algoritm så att med tanke på alla kort kan du omedelbart vet tillhörande PIN-kod. Därför detta dokument studier som möjligt, analysera algoritm och föreslå en metod för attacken. Slutligen ger vi ett verktyg som genomför angrepp och lägga fram resultat om den beräknade chans att bryta systemet. Observera att så länge som andra bank-säkerhetsrelaterade algoritmer (andra PIN-format såsom IBM PIN-kod eller kort validering signaturer som CVV-eller CVC) liknar VISA PIN-kod, samma analys kan göras ger nästan samma resultat och slutsatser.
En av de vanligaste PIN algoritmer är VISA PIN Verification Value (PVV). Kunden får en PIN och en magnetisk remsa kortet. Kodade i magnetisk remsa är ett fyrsiffrigt nummer, kallade PVV. Detta nummer är en kryptografisk underskrift av PIN-koder och andra uppgifter om kortet. När en användare skriver in sin PIN-ATM läser magnetiska rand, krypterar och skickar all denna information till en central dator. Det en rättegång PVV med hjälp av den kund in PIN-kod och kort information med en kryptografisk algoritm. Rättegången PVV är jämfört med PVV lagrats på kortet, om de matchar den centrala datorn återgår till ATM tillstånd för transaktionen. Se mer i detalj.
Beskrivningen av PVV-algoritmen finns i två dokument med koppling i de föregående sida. Sammanfattningsvis består den kryptering av en 8 byte (64 bitar) sträng av data, kallas omvandlas Security Parameter (TSP), med DES-algoritmen (DEA) i elektronisk kod Bok-läge (ECB) med hjälp av en hemlig 64-bitars nyckel. Den PVV härrör från produktionen av kryptering, som är en 8-byte sträng. De fyra siffrorna i PVV (från vänster till höger) motsvarar de första fyra decimaler (från vänster till höger) av produktionen från DES då betraktas som en 16 hexadecimala tecken (16 x 4 bitar = 64 bitar) sträng. Om det inte finns några fyra decimaler bland de 16 hexadecimala tecken sedan den PVV är klar fattas (från vänster till höger) icke decimala tecken och decimalizing dem med hjälp av omställning A-> 0, B-> 1, C-> 2, D -> 3, E-> 4, F-> 5. Här är ett exempel:
Produktion från DES: 0FAB9CDEFFE7DCBA
PVV: 0975
Strategin att undvika decimaliseringen genom att hoppa tecken till fyra decimaler finns (som råkar vara nästan alla de gånger som vi kommer att se nedan) är mycket smart eftersom man därigenom undviker en viktig snedvridning i fördelningen av siffror som har visat sig vara dödlig för andra system, även om påverkan på detta system skulle vara mycket lägre. Se även ett problem som inte gäller för VISA PVV.
Den TSP, ses som en 16 hexadecimala tecken (64 bitar) sträng, bildas (från vänster till höger) med 11 höger siffrorna i PAN (kortnummer) med undantag av den sista siffran (kontrollsiffra), en siffra från 1 till 6 som väljer att kryptera hemliga nyckeln och slutligen de fyra siffrorna i PIN-kod. Här är ett exempel:
PAN: 1234 5678 9012 3445
Key väljaren: 1
PIN-kod: 2468
TSP: 5678901234412468
Naturligtvis problemet med att bryta VISA PIN består i att hitta den hemliga kryptera viktiga för DES. Metoden för detta är att göra en brute force-sökning av de viktigaste utrymme. Observera att detta inte är den enda metod skulle man kunna försöka hitta en svaghet i DEA, många försökt, men det gamla standarden är fortfarande allmänt använd (nu ersatts med AES och RSA, även om). Detta visar att det är robust nog så att "brute force" är den enda fungerande metoden (det finns några bättre attacker men inte praktiskt i vårt fall, för en sammanfattning se LASEC memo och för smutsiga detaljer se Biham & Shamir 1990, Biham & Shamir 1991, Matsui 1993, Biham & Biryukov 1994 och Heys 2001).
Nyckeln väljaren siffra var mycket sannolikt införas för att täcka risken för en viktig kompromiss. I så fall räcker det med att utfärda nya kort med en annan nyckel väljaren. Äldre kort kan ersättas med nya eller helt enkelt ATM kan öppet skriva en ny PVV (som motsvarar den nya nyckeln och hålla samma PIN-kod) nästa gång kunden använder sitt kort. För att skaka av säkerhet alla användare bör uppmanas att ändra sin PIN-koder, men det skulle vara pinsamt för banken att förklara varför, så mycket troligt att de inte skulle göra en sådan begäran.
Förbereda attacken
En brute force-attack består i att kryptera en TSP med kända PVV med alla möjliga kryptera nycklar och jämföra varje erhållits PVV med kända PVV. När en matchning hittas vi har en kandidat-knappen. Men hur många nycklar vi måste försöka? Som vi nämnde ovan nyckeln är 64 bitar långa, skulle det innebära att vi måste försöka 2 ^ 64 nycklar. Men detta är inte sant. Faktiskt bara 56 bitar är effektivt i DES-nycklar, eftersom en bit (den minsta) av varje oktett var historiskt reserverats som en kontrollsumma för de andra, i praktiken de 8 bitar (en för varje av de 8 bytes) ignoreras.
Därför DES-nyckel utrymme består av 2 ^ 56 nycklar. Om vi försöker alla dessa knappar kommer vi hitta en och endast en match, som motsvarar bankens hemliga nyckel? Absolut inte. Vi kommer att få många matchande knappar. Detta beror på att PVV är bara en liten del (en fjärdedel) av DES produktion. Dessutom PVV är degenererat eftersom några av de siffror (mellan 0 och 5 efter den sista, sett från vänster till höger, siffra mellan 6 och 9) kan komma från en decimal siffra eller från en decimalized hexadecimala siffran i DES produktion. Alltså många nycklar kommer att producera en DES produktion vilket innebär att samma matchande PVV.
Vad kan vi göra för att hitta den verkliga nyckeln bland de andra falskt positiva nycklar? Helt enkelt vi har att kryptera en andra olika TSP, även känd PVV, men använd bara den kandidat nycklar som gav en positiv matchning med den första TSP-PVV par. Men det finns ingen garanti att vi inte kommer att få igen många falska positiva tillsammans med den verkliga nyckeln. Om så är fallet kommer vi att behöva en tredje TSP-PVV par, upprepa processen och så vidare.
Innan vi börjar vår attack måste vi veta hur många TSP-PVV par vi kommer att behöva. För att vi har för att beräkna sannolikheten för en slumpmässig DES produktion ge en matchning PVV bara av en slump. Det finns flera sätt att beräkna detta nummer och här kommer jag att använda en enkel metod lätt att förstå men som kräver lite bakgrund i matematik av sannolikhet.
En sannolikhet kan alltid ses som förhållandet mellan gynnsamma fall med eventuella fall. I vårt problem antalet möjliga fall fås genom permutation av 16 delar (0 till F hexadecimala siffror) i en grupp av 16 av dem (de 16 hexadecimala siffror i DES utgång). Detta ges med 16 ^ 16 ~ 1,8 * 10 ^ 19 som ju sammanfaller med 2 ^ 64 (olika nummer av 64 bitar). Denna uppsättning av nummer kan delas in i fem kategorier:
De med minst fyra decimaler (0 - 9) bland de 16 hexadecimala siffror (0 till F) av DES produktion.
De med exakt endast tre decimaler.
De med exakt endast två decimaler.
De med exakt bara en decimal siffra.
Dem utan decimaler (alla mellan A och F).
Låt oss beräkna hur många siffror som faller inom varje kategori. Om vi märker de 16 hexadecimala siffror i DES produktion som X1 till x16 så kan vi märka de första fyra decimaler för ett visst antal av den första kategorin som Xi, XJ, XK och XL. Antalet olika kombinationer med denna profil ges av produkten 6 i-1 * 10 * 6j-i-1 * 10 * 6k-j-1 * 10 * 6 LK-1 * 10 * 1616-l när 6 " S kommer från flera olika möjligheter för en A till F siffra, den 10: s kommer från möjligheterna till en 0-9 siffror, och 16 kommer från möjligheterna till en skala från 0 till F siffran. Nu det totala antalet i den första kategorin är helt enkelt som summerat av denna produkt under I, J, K, L 1 - 16 men med i <j <k <l. Om du gör några math arbete kommer du att se detta lika med produkten av 104 / 6 med summerat över i 4 till 16 av (i-1) * (i-2) * (i-3) * 6i-4 * 16 16-i ~ 1.8 * 1019.
Analogt antalet fall i den andra kategorin är som summerat över I, J, K 1 - 16 med i <j <k av produkten 6i-1 * 10 * 6j-i-1 * 10 * 6k-j -1 * 10 * 616-k som du kan arbeta ut att vara 16! / (3! * (16-13)!) * 103 * 13 6 = 16 * 15 * 14 / (3 * 2) * 103 * 613 = 56 * 104 * 613 ~ 7.3 * 1015. Likaså för den tredje kategorin har vi summerat över i, j 1 - 16 med i <j av 6 i-1 * 10 * 6j-i-1 * 10 * 616-j som motsvarar 16! / (2! * (16-14)!) * 102 * 614 = 2 * 103 * 615 ~ 9.4 * 1014. Igen, för fjärde kategori har vi summerat över i 1 - 16 av 6i-1 * 10 * 616-i = 160 * 615 ~ 7.5 * 1013. Och slutligen den mängd fall i den femte kategorin fås genom permutation av sex delar (A till F siffror) i en grupp av 16, det vill säga 616 ~ 2.8 * 1012.
Jag hoppas att ni följt beräkningar upp till denna punkt, det svåra är gjort. Nu som ett bevis på att allt är rätt kan du räkna ut det totala antalet fall i 5 kategorier och ser det motsvarar det totala antalet möjliga fall vi beräknat tidigare. Göra operationer som använder 64-bitars nummer eller avrundning (för flottar) eller overflow (för heltal) fel kommer inte att låta dig få ut det exakta resultatet.
Fram till nu har vi beräknat antalet möjliga fall i vart och ett av de fem kategorier, men vi är intresserade av att få antalet gynnsamma fall i stället. Det är mycket lätt att härleda den senare från den tidigare så det är bara om fastställande av kombination av de fyra decimaler (eller det hexadecimala siffror om det inte finns några fyra decimaler) av PVV stället för att låta dem fritt. I praktiken innebär detta att vrida 10's i formeln ovan i 1 och det erforderliga beloppet på 6: s till 1 s om det inte finns några fyra decimaler. Det är, vi måste dela upp det första resultatet av 104, det andra ett med 103 * 6, den tredje en av 102 * 62, den fjärde en av 10 * 63 och den femte en med 64. Då antalet gynnsamma fall i fem kategorier är cirka 1,8 * 1015, 1.2 * 1012, 2.6 * 1011, 3.5 * 1010, 2.2 * 109 respektive.
Nu vi kan få fram vad som är sannolikheten för en DES produktionen för att matcha en PVV av en slump. Vi måste bara lägga till de fem nummer av gynnsamma fall och dela det med det totala antalet möjliga fall. Gör det vi får att sannolikheten är mycket ca 0,0001 eller en av tio tusen. Är det konstigt detta väl avrundas resultatet? Inte alls, bara ta en titt på de siffror vi beräknat ovan. Den första kategorin dominerar med flera tiopotenser antalet god och eventuella fall. Detta är ganska intuitivt som det verkar klart att det är mycket osannolikt att inte ha fyra decimaler (10 chanser av 16 per siffra) bland 16 hexadecimala siffror. Vi såg tidigare att förhållandet mellan antalet möjliga och gynnsamma fall i den första kategorin var en avdelning med 10 ^ 4, det är där våra resultat p = 0,0001 kommer från.
Vårt mål för alla dessa beräkningar var att ta reda på hur många TSP-PVV par vi behöver för att genomföra en framgångsrik brute force-attack. Nu kan vi beräkna det förväntade antalet falska positiva resultat i en första sökning: det kommer att antalet prövningar gånger sannolikheten för en enda slumpmässigt falskt positiva, dvs t * p där t = 2 ^ 56, storleken av de viktigaste rymden. Detta uppgår till cirka 7,2 * 10 ^ 12, ett ganska stort antal. Det förväntade antalet falskt positiva i andra sökning (begränsat till den positiva nycklar i det första sökning) kommer att vara (t * p) * p, för en tredje sökningen kommer att ((t * p) * p) * p och så vidare. Således för n söker det förväntade antalet falskt positiva kommer att t * p ^ n.
Vi kan få det antal sökningar som krävs för att förvänta sig bara ett falskt positiva med att uttrycka ekvationen t * p ^ n = 1 och lösa för n. Så n är lika med logaritmen i basen p av 1 / t, som genom egenskaper logaritmer man halter n = log (1 / t) / log (p) ~ 4.2. Eftersom vi inte kan göra en fraktionerad sökning är det lämpligt att runda upp detta nummer. Därför vad som är det förväntade antalet falskt positiva om vi utföra fem söker? Det är t * p ^ 5 ~ 0.0007 eller cirka 1 av 1400. Alltså med hjälp av fem TSP-PVV par är säkert att få den sanna hemlig nyckel utan några falska positiva.
När vi vet att vi behöver fem TSP-PVV par, hur får vi dem? Naturligtvis behöver vi minst ett kort med kända PIN-kod, och på grund av PVV-algoritmen, som är det enda vi behöver. Med andra PIN-system, såsom IBM, skulle vi behöva fem kort, men detta är inte nödvändigt med VISA PVV algoritm. Vi måste bara läsa den magnetiska rand och sedan ändra PIN-fyra gånger, men behandlingen kortet efter varje förändring.
Det är nödvändigt att läsa den magnetiska rand av kortet för att få den PVV och kryptera viktiga väljaren. Du kan köpa en magnetisk remsa läsare eller göra en själv efter instruktioner hittar du på föregående sida och länkar där. När du har en läsare se denna beskrivning av standard magnetiska spår för att ta reda på hur du får ut det PVV från de data som har lästs. I att dokumentera PVV området i spår 1 och 2 sägs vara fem tecken lång, men faktiskt sant PVV består av de fyra sista siffrorna. Den första av de fem siffrorna är nyckeln väljaren. Jag har bara sett kort med ett värde av 1 i denna siffra, som stämmer överens med den standard och med den hemliga nyckeln aldrig äventyras (och därför de inte behöver flytta till en annan nyckel förändras väljaren).
Jag gjorde ett enkelt C-program, getpvvkey.c, för att utföra attacken. Den består av en slinga för att prova alla möjliga nycklar för att kryptera första TSP, om de härrör PVV matchar sant PVV en ny TSP är försökt, och så vidare tills det föreligger en obalans, i vilket fall nyckeln kastas bort och en ny har försökt, eller de fem härrör PVVs matchar motsvarande sant PVVs, då kan vi antar att vi fick banken hemlig nyckel, men slingan går vidare tills den blir fulltecknad viktiga utrymme. Detta görs för att försäkra vi hitta den sanna nyckeln eftersom det inte finns en chans (även om mycket låga) de första viktiga hittat är en falsk positiv.
Det förväntas programmet skulle ta väldigt lång tid att slutföra och att minimera riskerna för strömavbrott, datorn låser sig osv det gör kontrollstationer i filen getpvvkey.dat från gång till gång (exakt tid beror på hastigheten av datorn, det är ungefär en timme för den snabbaste datorer som nu används). Av samma skäl om en positiv nyckeln finns den är skriven på filen getpvvkey.key. Programmet visar bara ett meddelande i början, men utgångsläget tas från kontrollpunkt filen om någon, efter att ingenting mer visas.
DES-algoritmen är en viktig punkt i programmet är det därför mycket viktigt att optimera sin hastighet. Jag testade flera utföranden: libdes, SSLeay, OpenSSL, cryptlib, NSS, libgcrypt, katakomb, libtomcrypt, cryptopp, ufc-crypt. DES-funktioner i de fyra första är baserade på samma nummer av Eric Young och är den som ger bäst resultat (inklusive optimerade C och x86 assembler kod). Därför jag valde libdes som var det ursprungliga genomförande och kondenserad all relevant kod i filer encrypt.c (C version) och x86encrypt.s (x86 assembler version). Koden är något modifierad för att uppnå vissa förbättringar i en brute force-attack: den ursprungliga permutation är en fast gemensamma brant i varje TSP kryptering och därför kan göras bara en gång i början. En annan förbättring är att jag skrev en helt ny setkey funktion (jag kallade det nextkey) som är optimalt för en brute force-loop.
För att få programmet arbetar du bara skriva i motsvarande plats fem TSPs och deras PVVs och sedan sammanställa det. Jag har testat det endast i UNIX-plattformar, med hjälp av makefile Makegetpvvkey att sammanställa (använd kommandot "make-f Makegetpvvkey"). Det kan sammanställa på andra system men du kanske behöver rätta till vissa saker. Var noga med att definitionen av den typ long64 motsvarar en 64-bitars heltal. I princip finns det ingen beroende på endianness av processorn. Jag har nu sammanställts och köra det på Pentium-Linux, Alfa-Tru64, Mips-IRIX och Sparc-Solaris. Om du inte har och inte vill installera Linux (du vet inte vad ni saknas ;-) du fortfarande har valet att köra Linux på cd och använda mitt program, se min sida att köra Linux utan att installera det.
När du har hittat den hemliga bank-nyckel om du vill hitta PIN av ett godtyckligt kort som du bara måste skriva ett liknande program (beklagar att jag inte har skrivit den, jag är för lat:) som skulle prova allt 10 ^ 4 PIN-koder genom att generera motsvarande TSP, kryptera den med (inte längre) hemlig nyckel, som den PVV och jämföra den med PVV i magnetisk remsa av kortet. Du kommer att få en match för den verkliga PIN-kod. Bara en match? Kom ihåg vad vi såg ovan, vi har en chans att 0.0001 att ett slumpmässigt kryptering matchar PVV. Vi försöker 10000 PIN-koder (och därför TSPs), vilket vi förväntar oss 10.000 * 0,0001 = 1 falskt positiva i genomsnitt.
Detta är ett mycket intressant resultat, det betyder att i genomsnitt varje kort har två giltig PIN-koder: kundens PIN-kod och den förväntade falskt positiva. Jag kallar den "falska" men konstaterar att så länge det genererar verkliga PVV det är en PIN lika giltig som kundens en. Dessutom finns det inget sätt att veta vilket som, även för ATM, bara kunden vet. Även om de falska positiva var inte som PIN-kod du fortfarande har tre försök på ATM i alla fall, tillräckligt i genomsnitt. Därför sannolikheten vi beräknat i början av detta dokument om slumpmässigt gissa av PIN-kod måste rättas till. Faktiskt det är dubbelt så stor som värdet, det vill säga, det är 0.0006 eller ett av mer än 1600, fortfarande säkert låg.
Resultat
Det är viktigt att optimera beräkningen av programmet och att köra den på snabbast möjliga processor på grund av den långa förväntade körtiden. Jag tyckte att kompilatorn optimering flagg-O får bättre resultat, trodde att en viss förbättring uppnås lägga till-fomit-frame-pointer-flaggan på Pentium-Linux,-ax-flaggan på Alpha-Tru64, de-IPA flaggan på Mips-IRIX och-fort-flaggan på Sparc-Solaris. Särskilda flaggor (-DDES_PTR-DDES_RISC1-DDES_RISC2-DDES_UNROLL-DASM) för DES-nummer i allmänhet har fördelar också. Alla dessa flaggor redan testats och jag valde den bästa kombinationen för varje processor (se makefile) men du kan försöka att finjustera andra flaggor.
Enligt mina tester de bästa resultaten uppnås med AMD Athlon 1600 MHz processor, mer än 3,4 miljoner nycklar per sekund. Intressant det blir bättre resultat än Intel Pentium IV 1800 MHz och 2000 MHz (se tabellen nedan, klicka på dem för större bild). Jag tror detta beror på att vissa I / O-mättnad, säkert cache inte minnet, att AMD-processor (som har en halv cache av Pentium) eller moderkortet där det körs, lyckas undvika. I den första figuren nedan kan du se att DES bryta hastighet av alla processorer har mer eller mindre ett linjärt samband med processorns hastighet, med undantag för de två Intel Pentium jag nämnde tidigare. Detta är logiskt, det innebär att för en dubbel processorns hastighet du får dubbla bryta hastighet, men akta dig för mättnad effekter, i detta fall är det bättre att AMD Athlon 1600 MHz, som kommer att bli ännu billigare än Intel Pentium 1800 MHz eller 2000 MHz.
I den andra siffran vi kan se mer i detalj vad vi skulle kalla inneboende DES bryta kraften hos processorn. Jag får detta värde helt enkelt att dividera bryta hastighet av processorns hastighet, det vill säga vi får antalet DES-nycklar försökte per sekund och per MHz. Detta är ett mått på prestanda hos processor typ oberoende av dess hastighet. Resultaten visar att det bästa processor för denna uppgift är AMD Athlon, sedan kommer Alpha och mycket nära efter det är det Intel Pentium (med undantag för högre hastighet dem som utför mycket dålig på grund av mättnad effekt). Nästa är Mips-processorer och i det sista stället är det Sparc. Vissa Alpha och Mips-processorer finns längst ned i en skala på grund av att de tidiga utgåvor inte inklusive tillbehör för sent versioner. Observera att jag ingår resultatet för x86-processorer för C och assembler kod eftersom det finns en stor skillnad. Det verkar som gcc är ingen bra generator för optimerad maskin-nummer, men det gör vi naturligtvis inte veta om en manuell optimering av assembler kod för andra processorer (Alpha, Mips, Sparc) skulle öka sina resultat jämfört med det ursprungliga C-kompilatorer (Jag har inte använda gcc för dessa andra plattformar) som det händer med x86-processor.
Uppdatera
Här är en artikel där dessa tekniker kan ha använts.