Breaking VISA PIN
02 juli 2008 i bank-och EFTPoS
Nedan är en artikel jag hittade nyligen. Detta en av de mest omfattande beskrivningar av PIN Verification Value (PVV) hacking.
Jag trodde 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, jag har rättat några av de uppenbara fel samtidigt som det i det ursprungliga materialet.
http://69.46.26.132/ ~ biggold1/fastget2you/tutorial. php
--- Originaltext ----
Förord
Har du någonsin undrar vad som skulle hända om du förlorar ditt kredit-eller betalkort och någon upptäcker det. Skulle denna person kunna ta ut kontanter från en uttagsautomat gissa, på något sätt, din PIN-kod? Dessutom, om du var som finner någons kortet skulle du försöka att ta PIN och ta chansen att få lite lätta pengar? Naturligtvis är svaret på båda frågorna bör vara "nej". Detta arbete behandlar inte andra fråga är det en fråga om personlig etik. Härmed jag försöker besvara den första frågan.
All 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. Vidare är målet (och sista slutsatsen) med detta arbete är att visa att PIN algoritmer är fortfarande stark nog att ge tillräcklig säkerhet. Vi vet alla är inte 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 gissa attacker. Genom att "gissa" Jag menar inte att välja en slumpmässig PIN och försöker i en uttagsautomat. Det är väl känt att generellt vi får tre försök att ange rätt PIN-kod, om vi inte ATM håller kortet. Som VISA PIN fyrsiffrigt länge det är lätt att dra slutsatsen att risken för en slumpmässig PIN gissa är 3 / 10000 = 0,0003, det verkar tillräckligt låg för att vara säker, det betyder att du måste förlora ditt kort fler ä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 egentligen menade med "gissa" var att bryta PIN algoritm så att ges något kan du omedelbart veta tillhörande PIN-kod. Detta dokument studier som möjligt, analysera algoritm och föreslå en metod för angrepp. Slutligen ger vi ett verktyg som genomför attacken och presentera resultaten om de uppskattade chansen att bryta systemet. Observera att så länge som andra bank skyddsrelaterad algoritmer (andra PIN format såsom IBM PIN eller kort validering signaturer som CVV-eller CVC) liknar VISA PIN, 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-kod och en magnetremsa kortet. Encoded i magnetremsa är ett fyrsiffrigt nummer, kallad PVV. Denna siffra är en kryptografisk underskrift av PIN-och andra uppgifter med anknytning till kortet. När en användare skriver in sin PIN ATM läser magnetremsa, krypterar och skickar denna information till en central dator. Det en rättegång PVV beräknas med hjälp av kund in PIN-kod och kort information med en kryptografisk algoritm. Rättegången PVV jämförs med PVV lagras på kortet, om de matchar den centrala datorn återgår till ATM tillstånd för transaktionen. Se mer i detalj.
Beskrivningen av PVV algoritm finns i två handlingar i föregående sida. Sammanfattningsvis består i kryptering av en 8 byte (64 bitar) sträng av data, kallas Transformed Security Parameter (TSP), med DES-algoritmen (DEA) i Electronic Code Book mode (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 fyra första decimalsiffror (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 decimalsiffror bland de 16 hexadecimala tecken sedan PVV är klar fattas (från vänster till höger) utan decimal 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 av hoppa tecken tills fyra decimalsiffror finns (som råkar vara nästan alla gånger som vi kommer att se nedan) är väldigt smart eftersom man 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 också 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) utom den sista siffran (kontrollsiffra), en siffra från 1 till 6 som väljer hemligt kryptera viktiga 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
Uppenbarligen problemet med att bryta VISA PIN består i att finna hemligheten 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 kan man försöka hitta en svaghet i DEA har många försökt, men det gamla standarden är fortfarande allmänt använd (som nu ersatts med AES och RSA, men). Detta visar att det är robust nog för att "brute force" är den enda fungerande metoden (det finns några större 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 kompromiss. I detta fall de bara har 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 (motsvarande den nya nyckeln och behålla samma PIN) 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örberedelser attacken
En brute force-attack innebär att kryptera ett trippelsuperfosfat med kända PVV använda alla möjliga kryptera nycklar och jämföra varje erhållits PVV med den kända PVV. När en matchning hittas vi har en kandidat nyckel. Men hur många nycklar måste vi försöka? Som vi sade ovan nyckeln är 64 bitar långa, så skulle detta innebära att vi måste försöka 2 ^ 64 nycklar. Men detta är inte sant. Faktiskt bara 56 bitar är effektiva för att DES-nycklar, eftersom en bit (den minsta) av varje oktett var historiskt reserverats som en kontrollsumma för andra, i praktiken de som 8 bitar (en för varje av de 8 octets) 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, vilket motsvarar bankens hemliga nyckel? Absolut inte. Vi kommer att få många matchande nycklar. 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 det att den sista, sett från vänster till höger, siffror 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 falska positiva nycklarna? Bara vi har för att kryptera ett andra olika TSP, även känd PVV, men endast med de sökande nycklar som gav en positiv matchning med första TSP-PVV par. Men det finns ingen garanti att vi inte kommer att få igen många falska positiva med den verkliga nyckeln. Om så är fallet kommer vi att behöva ett 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 kommer vi 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 antalet och här kommer jag att använda en enkel metod lätt att förstå, men som kräver lite bakgrundsinformation i matematik av sannolikhet.
En sannolikhet alltid kan ses som förhållandet mellan god fall att 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 (16 hexadecimala siffror i DES output). Detta ges av 16 ^ 16 ~ 1,8 * 10 ^ 19 vilket naturligtvis sammanfaller med 2 ^ 64 (olika nummer av 64 bitar). Denna uppsättning siffror kan delas in i fem kategorier:
De som har minst fyra decimala siffror (0 till 9) bland de 16 hexadecimala siffror (0 till F) av DES produktion.
De som har exakt tre decimaler.
Personer med exakt två decimaler.
De som har just bara en decimal siffra.
De som inte decimalsiffror (alla mellan A och F).
Låt oss räkna hur många siffror faller inom varje kategori. Om vi märka 16 hexadecimala siffror i DES produktion som X1 att X16 kan vi märka första fyra decimalsiffror av ett visst antal av den första kategorin som Xi, XJ, XK och XL. Antalet olika kombinationer med den här profilen ges av produkten 6 i-1 * 10 * 6j-i-1 * 10 * 6k-j-1 * 10 * 6 lk-1 * 10 * 1616-l när 6 " har kommit från flera olika möjligheter för en A till F siffran, den 10: s kommer från möjligheterna till en 0-9-siffrigt och 16 kommer från möjligheterna till ett 0-F siffran. Nu är det totala antalet i den första kategorin är helt enkelt som summering av denna produkt under I, J, K, L 1-16, men med i <j <k <l. Om du gör några matematiska arbete kommer du att se detta är lika med produkten av 104 / 6 med summering över i 4-16 (i-1) * (i-2) * (i-3) * 6i-4 * 16 16-i ~ 1.8 * 1019.
Analogt antalet fall i den andra kategorin återfinns genom summering ö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 * 6 13 = 16 * 15 * 14 / (3 * 2) * 103 * 613 = 56 * 104 * 613 ~ 7.3 * 1015. Likaså för den tredje kategorin vi summering ö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. Återigen, för fjärde kategori har vi summering över i 1-16 i 6i-1 * 10 * 616-i = 160 * 615 ~ 7.5 * 1013. Och slutligen den mängd ärenden i femte kategori ges av 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 summan av antalet fall i 5 kategorier och ser det lika med totala antalet möjliga fall vi beräknat innan. Har verksamheten använder 64 bitars nummer eller avrundning (för flottar) eller överloppsrännor (för heltal) fel att inte låta dig få ut det exakta resultatet.
Hittills har vi beräknat antalet möjliga fall i något av de fem kategorier, men vi är intresserade av att få antalet gynnsamma fall istället. Det är mycket lätt att dra dem från den tidigare så detta är bara om fastställande av en kombination av de fyra decimalsiffror (eller krävs hexadecimala siffror om det inte finns fyra decimaler) i PVV i 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 är i 1: s om det inte finns fyra decimaler. Det vill säga, vi måste dela upp det första resultatet av 104, den andra en av 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 kan vi uppnå vad är sannolikheten för en DES produktionen för att matcha en PVV slump. Vi måste bara lägga till fem nummer i god fall och dividera det med antalet möjliga fall. Att göra detta vi får att sannolikheten är mycket ca 0,0001 eller en av tio tusen. Är det konstigt detta väl avrundade resultatet? Inte alls, bara ta en titt på de siffror som vi beräknat ovan. Den första kategorin dominerar flera tiopotenser antalet god och eventuella fall. Det är ganska intuitivt som det verkar tydligt att det är mycket osannolikt att inte ha fyra decimalsiffror (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 division med 10 ^ 4, det är där våra resultat p = 0,0001 kommer.
Målet 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 blir antalet försök 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 falska positiva resultat i andra sök (begränsad till den positiva nycklar hittas i första sökning) kommer att bli (t * p) * p, för en tredje sök är ((t * p) * p) * p och så vidare. Således för n sökningar det förväntade antalet falska positiva resultat kommer att t * p ^ n.
Vi kan få hur många sökningar som krävs för att vänta bara ett falskt positivt med att uttrycka ekvationen t * p ^ n = 1 och lösa för n. Så n motsvarar logaritmen i basen p 1 / t, som på grund av egenskaper hos logaritmer den avkastning n = log (1 / t) / log (p) ~ 4.2. Eftersom vi inte kan göra en fraktionerad sökadressen det är brukligt att runda upp det här numret. Därför vad som är det förväntade antalet falska positiva om vi utföra fem sökningar? Det är t * p ^ 5 ~ 0,0007 eller ca 1 av 1400. Därför använder fem TSP-PVV par är säkert att få det riktigt hemlig nyckel med 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, och beroende på vilken typ av PVV algoritm, det är det enda vi behöver. Med andra PIN-system, såsom IBM, skulle vi behöva fem kort, men det är inte nödvändigt med VISA PVV algoritm. Vi måste bara läsa magnetremsa och sedan ändra PIN-fyra gånger, men behandlingen kortet efter varje förändring.
Det är nödvändigt att läsa magnetremsa på kortet för att få PVV och kryptera viktiga väljaren. Du kan köpa en magnetremsa läsaren 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 standarden magnetiska spår för att ta reda på hur du får ut det PVV från data läsa. I detta dokument PVV område spår 1 och 2 sägs vara fem tecken långa, 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 den här siffran, som överensstämmer med standarden och med hemlig nyckel aldrig äventyras (och därmed 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 har försökt, och så vidare tills det finns en obalans, då nyckeln kasseras och en ny prövas, eller fem härrör PVVs matchar motsvarande sant PVVs, då kan vi förmoda vi fick banken hemlig nyckel, men slingan går vidare tills det avgassystem nyckeln utrymme. Detta görs för att försäkra att vi hittar den verkliga nyckeln eftersom det inte finns en chans (om än mycket liten) den första nyckeln hittades en falsk positiv.
Det förväntas programmet skulle ta mycket lång tid att slutföra och att minimera riskerna för strömavbrott, dator umgås osv det kontrollstationer i filen getpvvkey.dat från tid till annan (exakt tid beror på hur snabbt på datorn, det är ungefär en timme för den snabbaste datorer nu är i bruk). Av samma skäl om en positiv nyckeln hittades den är skriven på filen getpvvkey.key. Programmet visar ett meddelande i början, men utgångsläget tas från gränskontrollkuren ärende om någon, efter det inget mer visas.
DES-algoritmen är en viktig punkt i programmet är det därför mycket viktigt att optimera sin hastighet. Jag har testat flera utföranden: libdes, SSLeay, OpenSSL, cryptlib, NSS, libgcrypt, katakomb, libtomcrypt, cryptopp, UFC-crypt. DES-funktionerna hos de fyra första är baserade på samma kod av Eric Young och är den som ger bäst resultat (inkluderar optimerade C och x86 assembler kod). Därför valde jag 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 trippelsuperfosfat kryptering och kan därför bli bara en gång i början. En annan förbättring är att jag skrev ett helt nytt 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 den endast i UNIX-plattformar, med Makefile Makegetpvvkey att sammanställa (använd kommandot "make-f Makegetpvvkey"). Det kan sammanställa på andra system, men du kanske måste fixa några saker. Var noga med att definitionen av den typ long64 motsvarar en 64-bitars heltal. I princip finns det inget beroende av endianness av processorn. Jag har nu sammanställts och sedan köra det på Pentium-Linux, Alpha-Tru64, Mips-IRIX och Sparc-Solaris. Om du inte har och inte vill installera Linux (som du inte vet vad du saknar ;-) 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 viktigaste om du vill hitta den PIN av ett godtyckligt kort som du bara måste skriva ett liknande program (ledsen att jag inte har skrivit, jag är för lat:) som skulle prova alla 10 ^ 4 PIN genom att generera motsvarande TSP, kryptera den med den (inte längre) hemlig nyckel, som de PVV och jämföra det med PVV i magnetremsa på kortet. Du kommer att få en match för det sanna PIN. Endast 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 PINS (och därför TSPs), vilket vi förväntar oss 10000 * 0,0001 = 1 falskt positiva i genomsnitt.
Detta är ett mycket intressant resultat, innebär det att i genomsnitt varje kort har två giltiga PINS: kundens PIN och förväntas falskt positiva. Jag kallar den "falska", men konstaterar att så länge det genererar verkliga PVV ä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 ändå, räcker i genomsnitt. Därför sannolikheten vi beräknat i början av detta dokument om slumpmässigt gissa av PIN måste rättas till. Egentligen är det dubbelt så mycket värde, dvs det är 0,0006 eller en av mer än 1600, ändå säkert låg.
Resultat
Det är viktigt att optimera sammanställning av programmet och köra det på snabbast möjliga processor på grund av den långa förväntade körtiden. Jag tyckte att kompilatorn optimeringsförslag flagg-O får bättre resultat, trodde att en viss förbättring uppnås lägger till-fomit-frame-pointer flagga på Pentium-Linux,-spike flagga på Alfa-Tru64, de IPA flagga på Mips-IRIX och de snabba flaggan på Sparc-Solaris. Särskilda flaggor (-DDES_PTR-DDES_RISC1-DDES_RISC2-DDES_UNROLL-DASM) för DES kod 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 finjustera andra flaggor.
Enligt mina tester de bästa resultaten uppnås med AMD Athlon 1600 MHz-processor, som överstiger 3,4 miljoner nycklar per sekund. Intressant blir det 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 att detta beror på att vissa I / O-mättnad, säkert cache eller minnesåtkomst 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 bearbetningsföretagets hastighet, med undantag för de två Intel Pentium jag nämnde innan. Detta är logiskt, det innebär att för en dubbel processor 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, vilket 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 strömmen till processorn. Jag får detta värde helt enkelt att dividera bryta hastighet som processorn 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 bearbetningsföretaget typ oberoende av hastighet. Resultaten visar att den bästa processor för denna uppgift är det AMD Athlon, därefter kommer Alfa och mycket nära efter det är det Intel Pentium (med undantag för högre hastighet de 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 på botten av skalan eftersom de tidiga utgåvor inte inklusive tillbehör sen 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 maskinkod, men vi naturligtvis inte vet 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 använde inte gcc för dessa andra plattformar) som händer med x86-processor.
Uppdatera
Här är en artikel om dessa tekniker kan ha använts.