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.
VISA PVV algoritm
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. 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
