Abaixo está um artigo que encontrei recentemente. Esta uma das mais completas descrições do PIN Verification Value (PVV) hacking.
Eu pensei que ela iria replicar aqui para o meu local de referência.
Como observação, foram feitas sobre a gramática usada no texto original, tenho corrigido alguns dos erros óbvios, mantendo o contexto do material original.
http://69.46.26.132/ ~ biggold1/fastget2you/tutorial. php
--- Texto original ----
Prefácio
Você já se perguntou o que aconteceria se você perder o seu cartão de crédito ou débito e alguém encontra-lo. Será que essa pessoa seja capaz de retirar dinheiro de um caixa eletrônico adivinhação, de alguma forma, o seu PIN? Além disso, se você acha que alguém do cartão que você tentar adivinhar a senha e ter a chance de obter algum dinheiro fácil? Claro que a resposta às duas questões devem ser "não". Este trabalho não trata da segunda questão, é uma questão de ética pessoal. Herewith tento responder à primeira pergunta.
Todas as informações utilizadas para este trabalho é público e pode ser encontrado livremente na Internet. O resto é uma questão de matemática e programação, assim podemos aprender alguma coisa e ter algum divertimento. Eu não revelam segredos. Além disso, o objectivo (e conclusão), do presente trabalho é demonstrar que a PIN algoritmos ainda são fortes o suficiente para proporcionar segurança suficientes. Todos sabemos tecnologia não é o ponto fraco.
Este trabalho analisa uma das mais comuns PIN algoritmos, VISA PVV, utilizada por muitos ATM cartões (de crédito e de débito) e tenta descobrir como é resistente a PIN guessing ataques. Por "adivinhar" Não me refiro a uma escolha aleatória PIN e tentar-lo em um caixa eletrônico. É sabido que geralmente são dadas nos três ensaios consecutivos para entrar à direita PIN, se não ATM mantém o cartão. Como VISA PIN é quatro dígitos longa, é fácil deduzir que a chance de um aleatória PIN adivinhação é de 3 / 10000 = 0,0003, parece baixo o suficiente para ser seguro, isso significa que você precisa perder o seu cartão de mais de três mil vezes ( ou a perder mais de três mil cartões ao mesmo tempo:) até que haja uma hipótese razoável de perder dinheiro.
O que eu realmente entende por "adivinhar" foi quebrar o PIN algoritmo de modo que, dado qualquer cartão que você pode saber imediatamente os associados PIN. Por conseguinte, este documento estudos essa possibilidade, analisando o algoritmo e propor um método para o ataque. Finalmente vamos dar uma ferramenta que implementa o ataque e apresentar resultados sobre a estimativa chance de quebrar o sistema. Note que, enquanto outros bancos de segurança relacionados com algoritmos (outros PIN formatos, como a IBM PIN ou cartão de assinaturas, como a validação CVV ou CVC) são semelhantes aos VISA PIN, a mesma análise pode ser feito rendendo quase os mesmos resultados e conclusões.
VISA PVV algoritmo
Um dos mais comuns PIN algoritmos é o VISA PIN Verification Value (PVV). O cliente é atribuído um PIN e uma banda magnética cartão. Encoded na banda magnética é um número de quatro algarismos, chamado PVV. Este número é um criptográfico assinatura do PIN e outros dados relacionados ao cartão. Quando um usuário digita o seu PIN a ATM lê a banda magnética, criptografa e envia todas essas informações para um computador central. Há um julgamento PVV é calculado utilizando o cliente entrou PIN e as informações de cartão com uma criptografia algoritmo. O julgamento PVV é comparado com o PVV armazenados no cartão, se corresponderem a volta para o computador central ATM autorização para a operação. Veja mais em pormenor.
A descrição da PVV algoritmo pode ser encontrada em dois documentos ligados na página anterior. Em resumo, consiste na encriptação de um byte 8 (64 bits) seqüência de dados, chamado Transformado Security Parameter (SFT), com DES algoritmo (DEA) em Eletrônica Código Livro modo (BCE), utilizando uma chave secreta 64 bits. O PVV é proveniente da produção da criptografia processo, que é um byte 8 string. Os quatro algarismos do PVV (da esquerda para a direita) correspondem aos quatro primeiros dígitos decimais (da esquerda para a direita) da saída do DES quando considerada como um 16 caracteres hexadecimais (16 bits x 4 = 64 bits) string. Caso não haja quatro dígitos decimais entre os 16 caracteres hexadecimais então o PVV é completado tomada (da esquerda para a direita) não decimais caracteres e decimalizing-los usando a conversão A-> 0, B-> 1, C-> 2, D -> 3, E-> 4, F-> 5. Aqui está um exemplo:
Saída de DES: 0FAB9CDEFFE7DCBA
PVV: 0975
A estratégia de evitar decimalização saltando por até quatro caracteres dígitos decimais são encontrados (o que acontece com a quase totalidade das vezes como veremos mais adiante) é muito inteligente, porque evita um viés importante na distribuição de dígitos que tem sido provado ser fatal para outros sistemas, embora o impacto sobre o sistema seria muito menor. Veja também relacionada com um problema que não se aplicam a VISA PVV.
O SFT, considerada como um 16 caracteres hexadecimais (64 bits) string, é formada (da esquerda para a direita) com os 11 dígitos direita do PAN (número de cartão), excluindo o último dígito (check dígito), um dígito 1-6 que seleciona o segredo encriptando-chave e, finalmente, a quatro dígitos do código PIN. Aqui está um exemplo:
PAN: 1234 5678 9012 3445
Chave seletor: 1
PIN: 2468
TSP: 5678901234412468
É óbvio que o problema da quebra VISA PIN consiste em encontrar a chave secreta de encriptação DES. O método para isso é fazer uma pesquisa de força bruta a tecla espaço. Note-se que este não é o único método, pode-se tentar encontrar um ponto fraco na DEA, muitos tentaram, mas este padrão antigo ainda está em ampla utilização (agora substituído por AES e RSA, embora). Isto demonstra que é robusto o suficiente para que a força bruta é o único método viável (existem alguns ataques, mas não melhor prática no nosso caso, para um resumo ver LASEC memória e para ver os detalhes sujos Biham & Shamir 1990, Biham & Shamir 1991, Matsui 1993, Biham & Biryukov 1994 e Heys 2001).
A chave era muito provável algarismos selector introduzidas para cobrir a possibilidade de um compromisso fundamental. Nesse caso, eles só têm de emitir novos cartões usando outra chave selector. Antigas cartas podem ser substituídas por novas, ou simplesmente a ATM transparente pode escrever uma nova PVV (que corresponde à nova chave e mantendo o mesmo PIN) próxima vez que o cliente usa o seu cartão. Para o shake de segurança todos os usuários devem ser convidados a mudar os seus PINs, porém, seria embaraçoso para o banco a explicar a razão, muito provavelmente não teriam de fazer tal pedido.
Preparando o ataque
A força bruta ataque consiste em encriptando SFT com uma conhecida PVV utilizando todas as possíveis chaves encriptando e comparar cada obtidos PVV com as conhecidas PVV. Quando uma correspondência for encontrada, temos um candidato chave. Mas quantas chaves temos de tentar? Como dissemos acima da chave é de 64 bits de comprimento, o que significa que temos de tentar 2 ^ 64 chaves. Contudo, isto não é verdade. De facto, apenas 56 bits são eficazes na DES chaves porque um bit (o menos significativo) de cada octeto foi historicamente reservado como um checksum para os outros, na prática os 8 bits (uma para cada um dos 8 octetos) são ignoradas.
Assim, o DES tecla espaço é composto por 2 ^ 56 chaves. Se tentarmos todas estas chaves encontraremos um e só um jogo, o que corresponde ao banco chave secreta? Certamente que não. Iremos obter muitos correspondentes chaves. Isto porque o PVV é apenas uma pequena parte (um quarto) do DES saída. Além disso, o PVV é degenerada porque alguns dos dígitos (aqueles entre 0 e 5 após o último, visto a partir da esquerda para a direita, algarismos entre 6 e 9) podem ser provenientes de uma casa decimal de um dígito ou dígitos hexadecimais decimalized do DES saída. Assim, muitas chaves irá produzir uma DES saída que produz a mesma correspondência PVV.
Então o que podemos fazer para encontrar a verdadeira chave entre os outros falsos positivos chaves? Simplesmente temos de encriptar um segundo diferentes TSP, também conhecida com PVV, mas utilizando apenas o candidato que deu as chaves uma correspondência positiva com o primeiro-TSP PVV par. No entanto não há garantia de que não irá receber novamente muitos falsos positivos, juntamente com a verdadeira chave. Se assim for, teremos um terceiro TSP-PVV par, repita o processo e assim por diante.
Antes de começarmos o nosso ataque, temos de saber quantos TSP-PVV pares vamos precisar. Por que temos que calcular a probabilidade de um aleatória DES produção para produzir uma correspondência PVV apenas por acaso. Existem várias formas de calcular este número, e aqui vou usar uma abordagem simples de fácil compreensão, mas que exige uma certa experiência em matemática de probabilidade.
A probabilidade pode ser sempre visto como a razão de casos favoráveis a possíveis casos. No nosso problema, o número de casos possíveis é dada pela permutação de 16 elementos (de 0 a F dígitos hexadecimais) em um grupo de 16 deles (os 16 dígitos hexadecimais do DES de saída). Esta é dada por 16 ^ 16 ~ 1,8 * 10 ^ 19, que obviamente coincide com 2 ^ 64 (números diferentes de 64 bits). Este conjunto de números podem ser divididos em cinco categorias:
Aqueles com pelo menos quatro dígitos decimais (0 a 9) entre os 16 dígitos hexadecimais (0 a F) do DES saída.
Aqueles com exactamente apenas três dígitos decimais.
Aqueles com exactamente apenas duas casas decimais.
Aqueles com exactamente apenas um dígito decimal.
Aqueles que não dígitos decimais (todos entre A e F).
Vamos calcular quantos números caem em cada categoria. Se nos rótulos dos 16 dígitos hexadecimais do DES X1 como saída para X16 então podemos rotular os primeiros quatro dígitos decimais de um determinado número de primeira categoria como Xi, XJ, XK e XL. O número de combinações diferentes com este perfil é dada pelo produto 6 i-1 * 10 * 6 undecies-i-1 * 10 * 6k-j-1 * 10 * 6 lk-1 * 10 * 1616-l quando a 6 ' s vir a partir do número de possibilidades de um dígito A a F, os 10's provêm as possibilidades de um dígito de 0 a 9 e as 16 trata das possibilidades de um 0 a F dígito. Agora, os números totais na primeira categoria é simplesmente dado pelo somatório do produto ao longo do i, j, k, l 1-16, mas com i <j <k <l. Se você fizer alguma matemática trabalho você verá esta é igual ao produto de 104 / 6, com o somatório sobre i 4-16 de (i-1) * (i-2) * (i-3) * 6i-4 * 16 16-i ~ 1/8 * 1019.
Analogamente, o número de casos na segunda categoria é dada pelo somatório sobre i, j, k 1-16 com i <j <k do produto 6i-1 * 10 * 6 undecies-i-1 * 10 * 6k-j -1 * 10 * 616-k, que você pode trabalhar para fora para ser 16! / (3! * (16-13)!) * 103 * 6 13 = 16 * 15 * 14 / (3 * 2) * 103 * 613 = 56 * 104 * 613 * 1015 ~ 7/3. Do mesmo modo para a terceira categoria que temos sobre o somatório i, j 1-16 com i <j, de 6 i-1 * 10 * 6 undecies-i-1 * 10 * 616-J, que é igual a 16! / (2! (16-14)!) * 102 * 614 = 2 * 103 * 615 * 1014 ~ 9,4. Mais uma vez, para a quarta categoria, temos o somatório sobre i 1-16 de 6i-1 * 10 * 616-i = 160 * 615 * 1013 ~ 7,5. E, finalmente, a quantidade de casos na quinta categoria é dada pela permutação de seis elementos (A a F dígitos) em um grupo de 16, ou seja, 616 ~ 2,8 * 1012.
Espero que você seguiu os cálculos até este ponto, a parte mais difícil está feito. Agora, como uma prova de que tudo está a direita, você pode soma do número de casos em 5 categorias e ver o que equivale ao número total de casos possíveis é calculado antes. Será que as operações com números de 64 bits ou de arredondamento (para carros alegóricos), ou por transbordamento (para inteiros) erros não vão deixar você obter o resultado exato.
Até agora temos calculado o número de casos possíveis em cada uma das cinco categorias, mas estamos interessados em obter o número de casos favoráveis vez. É muito fácil obter o último dos antigos como esta é apenas a fixação do conjunto de quatro dígitos decimais (ou o exigido dígitos hexadecimais, se não houver quatro casas decimais) do PVV vez de deixá-las livres. Na prática, isso significa transformar os 10's na fórmula acima em 1 e do montante exigido é de 6 em 1's, se não houver quatro casas decimais. Isto é, temos que dividir o primeiro resultado por 104, o segundo um por 103 * 6, o terceiro um por 102 * 62, a um quarto por 10 * 63 eo quinto um por 64. Em seguida, o número de casos favoráveis nas cinco categorias são aproximadamente 1,8 * 1015, 1.2 * 1012, 2.6 * 1011, 3.5 * 1010, 2,2 * 109, respectivamente.
Agora somos capazes de obter o que é a probabilidade de um DES de saída para combinar uma PVV por acaso. Só temos de somar os cinco números de casos favoráveis e dividi-lo pelo número total de casos possíveis. Fazendo isso obtemos que a probabilidade é muito 0,0001 ou aproximadamente um em cada dez mil. É estranho esse bem arredondadas resultado? Nem por isso, basta ter um olhar para os números que acima calculada. A primeira categoria domina por várias ordens de grandeza do número de casos favoráveis e possíveis. Isto é bastante intuitivo como parece claro que é muito pouco provável que não tenha quatro dígitos decimais (10 chances de 16 por algarismos), entre 16 dígitos hexadecimais. Já vimos anteriormente que a relação entre o número de casos possíveis e favoráveis na primeira categoria foi uma divisão de 10 ^ 4, que é onde o nosso resultado p = 0,0001 vem.
O nosso objectivo para todos estes cálculos foi para descobrir quantos TSP-PVV pares precisamos para transportar uma força bruta bem sucedido ataque. Agora somos capazes de calcular o número esperado de falsos positivos em uma primeira pesquisa: ele será o número de julgamentos vezes a probabilidade de um único aleatória falso positivo, ou seja, p * t em que t = 2 ^ 56, o tamanho da chave espaço. Isto equivale a cerca de 7,2 * 10 ^ 12, um número bastante grande. O número esperado de falsos positivos no segundo pesquisa (restrito ao chaves positivo encontrado na primeira busca) será (t * p) * p, para uma terceira pesquisa será ((t * p) * p) * p e assim por diante. Assim, para pesquisas n é o número esperado de falsos positivos serão p * t ^ s.
Podemos obter o número de pesquisas necessárias para esperar apenas um falso positivo, expressando a equação t * p ^ n = 1 e para a resolução 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
