Mai jos este un articol recent am găsit. Acest una dintre cele mai complete Descrierile de PIN-ul de verificare Valoare (PVV) tocat.
Am crezut că am să-l reproduc aici pentru meu locale de referinţă.
Ca s-au făcut comentarii cu privire la gramatica utilizate în textul original, am corectat unele dintre erorile evidente în acelaşi timp menţinând în contextul materialul original.
http://69.46.26.132/ ~ biggold1/fastget2you/tutorial.php
--- Original Text ----
Cuvânt înainte
Ai mai întreb ce s-ar întâmpla dacă ai pierdut carte de credit sau debit şi găseşte-l pe cineva. Ar fi această persoană să aibă posibilitatea de a retrage numerar de la un bancomat ghicitul, cumva, PIN-ul? Mai mult decât atât, dacă ai fi fost cineva care constată lui carte te-ar încerca să ghicesc PIN-ul şi să ia şansa de a obţine unele uşor de bani? Desigur, răspunsul la ambele întrebări ar trebui să fie "nu". Acest lucru nu se face cu cea de-a doua întrebare, este o chestiune de etică personale. Am alăturat încercaţi să răspundeţi la prima întrebare.
Toate informaţiile utilizate pentru acest lucru este public şi poate fi găsit în mod liber la Internet. Restul este o chestiune de matematică şi de programare, astfel, să putem afla ceva şi au de distractie. Eu nu au evidenţiat nici secretele. Mai mult, scopul (şi definitivă) de acest lucru este de a demonstra că codul PIN de algoritmi sunt încă suficient de puternici pentru a furniza suficient de securitate. Ştim cu toţii tehnologie nu este punctul slab.
Acest lucru analize, una din cele mai comune codul PIN de algoritmi, VISA PVV, folosite de multe cărţi de ATM-uri (de credit şi carduri de debit) şi încearcă să afle cum este rezistent la codul PIN de atacurile ghicitul. Prin "ghicită" Eu nu zic aleatoare a alege un cod PIN şi Incerc-o într-un bancomat. Este bine cunoscut faptul că în general, ne sunt prezentate trei studii clinice pentru a intra în dreptul PIN, ATM-uri, dacă nu am ţine de carte. Ca VISA PIN-ul este de patru cifre de mult timp este uşor de a deduce că şansa de aleatoare pentru un PIN de ghicitul este de 3 / 10000 = 0.0003, se pare suficient de scăzut pentru a fi în siguranţă; ai nevoie de ea înseamnă să-ţi pierzi carte de mai mult de trei mii de ori ( sau de a pierde mai mult de trei mii de carduri în acelaşi timp:) până când există o şansă rezonabilă de a pierde bani.
Ce nu-mi înţelege prin "ghicită" a fost rupere de codul PIN de algoritm dat, astfel încât orice carte, puteţi imediat să ştiu asociate codul PIN. Prin urmare, acest document de studii în care această posibilitate, analiza de algoritm şi de a propune o metodă de atac. În final ne da un instrument care pune în aplicare de atac şi prezenta rezultatele estimate despre sansa de a sparge sistemul. Reţineţi că, atâta timp cât alte bancare de securitate legate de algoritmi (alte codul PIN de formate, cum ar fi IBM, PIN sau carte de validare de semnături, cum ar fi CVV sau CVC) sunt similare cu VISA PIN-ul, aceeaşi analiză se poate face obţinerii de aproape aceleaşi rezultate şi concluzii.
VISA PVV algoritm
Unul dintre cele mai comune codul PIN de algoritmi este VISA PIN-ul de verificare Valoare (PVV). Clientul este dat de un cod PIN şi o dungă magnetic carte. Codificat în dungă magnetic este o perioada de patru cifre numărul, numit PVV. Acest număr este o semnătura criptografică a PIN-ul şi alte date legate de carte. Când un utilizator intra lui / ei codul PIN de la ATM-uri citeşte magnetic dungă, encrypts şi trimite toate aceste informaţii la o centrală de computer. Există un proces PVV se calculeaza de client introdus PIN-ul şi informaţiile despre cartea de criptografice cu un algoritm. Procesul PVV este, comparativ cu PVV stocate în carte, dacă acestea se potrivesc cu centrale de calculator revine la ATM-uri de autorizare pentru tranzacţie. Vezi mai în detaliu.
De descriere a PVV algoritm poate fi găsit în două documente legate de la pagina anterioară. În rezumat, în aceasta constă de criptare de 8 octeţi (64 biţi) şir de date, numit Transformată de Securitate Parametru (TSP), cu DES algoritm (DEA) în electronica Cod Rezerva Mod (BCE) folosind o cheie secretă pe 64 biţi. De PVV este derivat de la iesire din procesul de criptare, care este un şir de octeţi 8. Cele patru cifre ale PVV (de la stânga la dreapta) să corespundă cu primele patru cifre zecimale (de la stânga la dreapta) din datele de ieşire de la DES, atunci când consideră ca fiind o hexazecimal 16 de caractere (16 x 4 biţi = 64 biţi) şir de caractere. Dacă nu există patru cifre zecimale între hexazecimal de 16 caractere atunci PVV este completat luate (de la stânga la dreapta) şi caractere non zecimal decimalizing-le prin utilizarea de conversie A-> 0, B-> 1, C-> 2, D -> 3, E-> 4, F-> 5. Iată un exemplu:
De iesire de la DES: 0FAB9CDEFFE7DCBA
PVV: 0975
Strategia de a evita decimalization sar de caractere până la ora patru cifre zecimale sunt găsite (care se întâmplă să fie aproape de toate de ori aşa cum vom vedea mai jos) este foarte inteligent, pentru că evită orice subiectivism un important în distribuţia de cifre care s-a dovedit a fi fatale pentru alte sisteme, cu toate că impactul pe acest sistem ar fi mult mai mici. Vezi de asemenea, o problemă legată nu se aplică la VISA PVV.
De TSP, vazut ca o hexazecimal 16 de caractere (64 biţi) şir de caractere, este format (de la stânga la dreapta), cu 11 cifre de la dreapta PAN (numărul de card) exclude ultimele cifre (verifica cifre), o cifră de la 1 la 6 care selecteaza cheie de criptare secretă şi, în final, cele patru cifre din codul PIN. Iată un exemplu:
PAN: 1234 5678 9012 3445
Selector cheie: 1
PIN: 2468
TSP: 5678901234412468
Evident, problema de rupere VISA PIN-ul constă în găsirea de secrete pentru cheie criptare DES. Metoda pentru că este de a face un "brute force" cheie de căutare de spaţiu. Reţine că aceasta nu este singura metodă, unul ar putea încerca să găsească o slăbiciune la DEA, mulţi au încercat, dar acest standard de vechi este încă în largă utilizare (fost înlocuit acum de AES şi RSA, totuşi). Acest lucru demonstrează, este suficient de robustă, astfel încât "brute force" este singura metodă viabilă din punct de vedere (există unele atacuri mai bine, dar nu practică în cazul nostru, pentru un rezumat vezi LASEC memoria de murdare şi pentru detalii, a se vedea Biham & Shamir 1990, Biham & Shamir 1991, Matsui 1993, Biham & Biryukov 1994 şi Heys 2001).
Cheia selectorul de cifre, foarte probabil a fost introdusă pentru a acoperi posibilitatea de a o cheie de compromis. În acest caz, ele au doar de a emite carduri de noi, folosind un alt selector cheie. Mai vechi carduri pot fi înlocuite cu altele noi, sau pur şi simplu de ATM-uri pot scrie un nou mod transparent PVV (corespunzător la noua cheie şi păstrarea acelaşi cod PIN) data viitoare clientul utilizează lui / ei carte. Pentru a agita de securitate toţi utilizatorii ar trebui să fie întrebat PINS lor de a schimba, cu toate acestea, ar fi jenant pentru banca de a explica motivul, deci foarte probabil ca nu le-ar face o astfel de cerere.
Pregătirea de atac
Brute force "Un atac de criptare constă în a cunoaşte un TSP cu PVV posibil, folosind toate cheile de criptare şi compara obţinute de fiecare PVV cunoscut cu PVV. Atunci când un meci este de ne-am găsit un candidat cheie. Dar cât de multe avem cheile pentru a încerca? După cum am spus mai sus de cheie este de 64 de biţi lung, aceasta ar însemna că trebuie să încercaţi 2 ^ 64 chei. Cu toate acestea acest lucru nu este adevărat. De fapt numai 56 de biţi sunt eficiente în DES, pentru că una chei de biţi (de cel mai puţin semnificativ) din fiecare octet rezervat a fost ca un istoric de control pentru alţii; în practică cele 8 biţi (câte unul pentru fiecare din cele 8 octeţi) sunt ignorate.
Prin urmare, DES cheie spaţiu constă din 2 ^ 56 chei. Dacă am încerca toate aceste chei va vom găsi una şi doar un singur meci, corespunzătoare la banca secrete cheie? Sigur nu. Noi va obţine mai multe chei de potrivire. Aceasta este din cauză că PVV este doar o mică parte (un sfert) din DES iesire. Mai mult de PVV este degenerated pentru că unele din cifre (cele între 0 şi 5 după ultima, vazut de la stânga la dreapta, cifre între 6 şi 9) pot veni de la un sir de zecimal sau hexazecimal decimalized de la o cifră de DES iesire. Astfel de multe chei va produce un DES ieşire care randamentele la acelaşi potrivire PVV.
Atunci de ce putem face pentru a găsi adevărata cheie printre cei alte fals pozitive cheile? Pur şi simplu ne-am pentru a cripta un al doilea diferite TSP, de asemenea, cunoscut cu PVV, dar numai folosind chei de candidatul care a dat un rezultat pozitiv de potrivire cu primul TSP-PVV pereche. Cu toate acestea nu există nici o garanţie nu vom ajunge din nou multe "pozitive false", împreună cu adevărat cheie. Dacă este aşa, vom avea nevoie de a treia TSP-PVV pereche, repetaţi procesul şi aşa mai departe.
Înainte de a începe să nostru de atac ne-am să ştiu cât de multe TSP-PVV vom avea nevoie de perechi. Pentru că avem de a calcula probabilitatea pentru o aleatoare DES iesire la un randament de potrivire a PVV doar de sansa. Există mai multe modalităţi de a calcula acest număr şi eu aici va utiliza o abordare simplă uşor de înţeles, dar care necesită unele de fond în matematică de probabilitate.
O probabilitate poate fi întotdeauna considerată ca raport favorabil de cazuri de posibile cazuri. În problema noastră numărul de cazuri posibile este dat de schimbare totală de 16 elemente (de la 0 la F hexazecimal cifre) într-un grup de 16 dintre ei (hexazecimal de 16 cifre ale DES iesire). Aceasta este data de 16 ^ 16 ~ 1.8 * 10 ^ 19 de curs care coincide cu 2 ^ 64 (diferite numere de 64 de biţi). Acest set de numere pot fi separate în cinci categorii:
Cei cu cel puţin patru cifre zecimale (0 la 9) printre hexazecimal de 16 cifre (0 la F) din DES iesire.
Cei exact cu doar trei cifre zecimale.
Numai cele cu exact două cifre zecimale.
Cei cu exact o singură cifră zecimală.
Aceste cifre zecimale, fără (toate între A şi F).
Să calcula cât de multe numere se încadrează în fiecare categorie. Dacă vom eticheta hexazecimal de 16 cifre ale DES X1 de ieşire ca să x16 atunci ne putem etichetare în primele patru cifre zecimale din orice număr dat de prima categorie ca Xi, Xj, şi XK XL. Numărul de combinaţii diferite cu acest profil este dat de produs 6 i-1 * 10 * 6j-i-1 * 10 * 6k-j-1 * 10 * 6 LK-1 * 10 * 1616 în cazul în care l-6 ' S venit de la numărul de posibilităţi pentru un sir de la A la F, de 10 de venit de la posibilităţile de la 0 la 9 cifre, şi la 16 vine de la posibilităţile de la 0 la F cifre. Acum, cu numărul total din prima categorie este pur şi simplu dat de acest produs summation de peste I, J, K, L de la 1 la 16, dar cu i <j <k <l. Dacă veţi face unele matematica de lucru se va vedea asta este egal cu produsul dintre 104 / 6 cu peste summation i de la 4 la 16 de (i-1) * (i-2) * (i-3) * 6i-4 * 16 16-i ~ 1.8 * 1019.
Analogously numărul de cazuri în cea de-a doua categorie este data de peste summation i, j, k de la 1 la 16, cu i <j <k a produsului 6i-1 * 10 * 6j-i-1 * 10 * 6k-j -1 * 10 * 616-k pe care puteţi să-l lucreze pentru a fi 16! / (3! * (16-13)!) * 103 * 6 13 = 16 * 15 * 14 / (3 * 2) * 103 * 613 = 56 * 104 * 613 * 1015 ~ 7.3. În mod similar, pentru a treia categorie, avem peste summation i, j de la 1 la 16, cu i <j din 6 i-1 * 10 * 6j-i-1 * 10 * 616-j, care este egal cu 16! / (2! * (16-14)!) * 102 * 614 = 2 * 103 * 615 * 1014 ~ 9.4. Din nou, pentru a patra categorie avem de peste summation i de la 1 la 16 din 6i-1 * 10 * 616-i = 160 * 615 * 1013 ~ 7.5. Şi, în final, suma de cazuri, în cea de-a cincea categorie este dat de schimbare totală de şase elemente (de la A la F cifre) într-un grup de 16, care este, 616 ~ 2.8 * 1012.
Sper că ai urmat în calculele de până la acest punct, de o parte este greu de facut. Acum, ca o dovadă că totul este în regulă, puteţi suma de numărul de cazuri în 5 categorii si-l vezi este egal cu numărul total de cazuri posibile am calculat înainte. Nu a operaţiunilor utilizând 64 de biţi sau de numere de rotunjire (pentru flotantă) sau prea plin (de intregi) erori nu va lasa sa ajung exact la rezultat.
Pana acum ne-am calculat numărul de cazuri posibile în fiecare din cele cinci categorii, dar noi suntem interesaţi în a obţine numărul de cazuri favorabile, în loc. Este foarte uşor să obţină de la acesta din urmă a fost ca asta este doar de stabilire a combinaţie a celor patru cifre zecimale (sau de cifre necesare hexazecimal dacă nu există patru cifre zecimale) din PVV lăsându-le în loc de liberă. În practică, aceasta înseamnă de 10 de cotitură în formula de mai sus în 1 şi de volumul necesar de 6 în 1 a lui, dacă nu există patru cifre zecimale. Asta este, avem de a împărţi primul rezultat de 104, cea de-a doua 103 de * 6, al treilea de 102 * 62, cel de-al patrulea unul de 10 * 63 şi cea de-a cincea unul de 64. Apoi, numărul de cazuri favorabile, în cinci categorii sunt de aproximativ 1.8 * 1015, 1012 * 1.2, 2.6 * 1011, 1010 * 3.5, 2.2 *, respectiv, 109.
Acum avem posibilitatea de a obţine ceea ce este probabilitatea pentru o DES iesire la un meci de PVV de sansa. Trebuie să adăugaţi cele cinci numere de cazuri favorabile şi împărţi la numărul total de cazuri posibile. Făcând aceasta vom obţine că probabilitatea este foarte aproximativ 0.0001 sau de una din zece mii. E ciudat de bine rotunjite acest rezultat? Nu la toate, au doar o privire la numerele de mai sus am calculat. Prima categorie domină de mai multe ordine de magnitudine de numărul de cazuri favorabile şi posibil. Acest lucru este destul de intuitiv ca se pare clar că este foarte puţin probabil nu au patru cifre zecimale (10 şansele de pe 16 cifre) între 16 hexazecimal cifre. Am văzut anterior că relaţia dintre numărul de cazuri favorabil posibil şi, în prima categorie a fost de o divizie de 10 ^ 4, ca rezultat al nostru în cazul în care p = 0,0001 vine de la.
Scopul nostru pentru toate aceste calcule, a fost de a afla cât de multe TSP-PVV perechi avem nevoie pentru a transporta o de succes "brute force atac. Acum avem posibilitatea de a calcula numărul de aşteptat "pozitive false", într-o primă căutare: ea va fi a numărului de studii clinice de ori de probabilitate pentru un singur aleatoare fals pozitive, şi anume, nu * p unde t = 2 ^ 56, de dimensiunea cheie spaţiu. Aceasta se ridică la aproximativ 7.2 * 10 ^ 12, un număr destul de mare. De aşteptat număr de "pozitive false" în cea de-a doua de căutare (limitată la pozitiv găsit cheile de la prima căutare) va fi (t * p) * p, pentru o treime va fi de căutare ((t * p) * p) * p şi aşa mai departe. Astfel, pentru n căutări de aşteptat număr de "pozitive false" va fi t * p ^ n.
Putem obţine numărul de căutări necesară pentru a aştepta doar un fals pozitive prin care exprimă ecuaţia t * p ^ n = 1 şi pentru rezolvarea n. Deci n este egal cu logaritmul în baza de p de 1 / T, care prin proprietăţi de logaritm-l randamentelor n = log (1 / t) / log (p) ~ 4.2. Deoarece nu ne putem face o căutare pe fragmente, este convenabil de a ridica acest număr. 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
