Quebrar visto PIN
Jul 02, 2008 em e Banking Eftpos
Abaixo está um artigo que encontrei recentemente. Esta uma das mais completas descrições dos PIN Verification Value (PVV) hacking.
Eu pensei que ela iria replicar aqui o meu local de referência.
Como comentar têm sido feitos na gramática usada no texto original, tenho corrigido alguns dos erros óbvios mas preservando o contexto do material original.
http://69.46.26.132/ ~ biggold1/fastget2you/tutorial.php
--- Texto original ----
Prefácio
Alguma vez você já saber o que aconteceria se você perder o seu cartão de crédito ou débito e alguém acha isso. Deveria esta pessoa ser capaz de retirar dinheiro de um caixa eletrônico adivinhação, de algum modo, o seu PIN? Além disso, se você fosse alguém que acha do cartão iria tentar adivinhar o PIN e ter a chance de obter algum dinheiro fácil? Claro que a resposta às duas perguntas devem ser "não". Esse trabalho não lida com a segunda pergunta, é uma questão de ética pessoal. Tento, assim, responder à primeira pergunta.
Todas as informações utilizadas para esse trabalho é público e pode ser encontrado livremente na Internet. O resto é uma questão de matemática e programação, assim nós podemos aprender algo e ter algum divertimento. Eu não revelam segredos. Além disso, o objectivo (ea conclusão final), do presente trabalho é demonstrar que a PIN algoritmos são fortes o suficiente para fornecer segurança suficiente. Nós todos conhecemos a tecnologia não é o ponto fraco.
Este trabalho analisa uma das mais comuns PIN algoritmos, VISA PVV, usado por muitos cartões ATM (crédito e débito) e tenta descobrir como é resistente aos PIN adivinhando ataques. Por "adivinhar" Não me refiro a uma escolha aleatória PIN e tentando-o em um caixa eletrônico. É sabido que nós geralmente são dadas três tentativas consecutivas de entrar à direita PIN, se não ATM mantém o cartão. Como VISA PIN de quatro dígitos longos, é fácil deduzir que a chance de um aleatória PIN é adivinhação 3 / 10000 = 0,0003, parece ser 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 probabilidade razoável de perder dinheiro.
O que eu realmente entende por "adivinhar" foi quebrar a senha algoritmo de modo que nenhum dado cartão você pode saber as imediatamente associada PIN. Por conseguinte, este documento estudos possibilidade de que, analisando o algoritmo e propor um método para o ataque. Finalmente vamos dar uma ferramenta que implementa o ataque e apresentar resultados sobre as estimativas dos chance de quebrar o sistema. Note que, enquanto outras banca de segurança relacionados com algoritmos (outros PIN formatos, tais como 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.
Uma das mais comuns PIN algoritmos é o VISA PIN Verification Value (PVV). O cliente é dado um PIN e uma banda magnética cartão. Codificados na banda magnética é um número de quatro algarismos, chamados PVV. Este número é um criptográfico assinatura do PIN e outros dados relacionados com o cartão. Quando um usuário digita o seu PIN a ATM lê a banda magnética, criptografa e envia todas estas informações para um computador central. Existe um julgamento PVV é computado usando o cliente entrou PIN e as informações de cartão criptográfico com um algoritmo. O julgamento PVV é comparado com o PVV armazenadas no cartão, se corresponderem ao computador central retorna ao ATM autorização para a transação. Veja mais em pormenor.
A descrição do PVV algoritmo pode ser encontrada em dois documentos ligados na página anterior. Em resumo, consiste na criptografia de um 8 byte (64 bits) seqüência de dados, chamado Transformado Segurança Parâmetro (SFT), sendo DES algorítmo (DEA) em Eletrônica Código Livro modo (BCE) utiliza uma chave secreta de 64 bit. O PVV é obtido a partir do resultado do processo de encriptação, que é uma seqüência byte 8. Os quatro algarismos do PVV (da esquerda para a direita) correspondem aos primeiros quatro dígitos decimais (da esquerda para a direita), da saída do DES quando considerada como um hexadecimal 16 caracteres (16 x 4 bits = 64 bits) corda. Se não existirem quatro dígitos decimais entre os 16 caracteres hexadecimais, em seguida, o PVV está concluída tomadas (da esquerda para a direita) e caracteres não decimal 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 saltitando por até quatro dígitos decimais personagens encontram-se (o que acontece com quase todas as vezes ser como veremos adiante) é muito inteligente, porque evita um viés importante na distribuição dos dígitos que tenha sido provado ser fatal para outros sistemas, embora o impacto sobre o sistema seria muito mais baixa. Veja também relacionada com um problema que não se aplicam a VISA PVV.
O TSP, encarada como hexadecimais 16 uma caractere (64 bits) corda, é 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 de 1 a 6 que seleciona o cifrando-chave secreta e finalmente os quatro dígitos do código PIN. Aqui está um exemplo:
PAN: 1234 5678 9012 3445
Chave seletor: 1
PIN: 2468
TSP: 5678901234412468
Obviamente, o problema da quebra VISA PIN consiste em encontrar a chave secreta para criptografar DES. O método para isso é fazer uma pesquisa de força bruta a tecla espaço. Note 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 é largamente utilizado (agora substituído pelo AES e RSA, embora). Isso demonstra que é robusto o suficiente para que força bruta é o único método viável (existem algumas melhores práticas ataques, mas não no nosso caso, para ver um resumo LASEC memo 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 selector dígito introduzido para cobrir a possibilidade de um compromisso fundamental. Nesse caso, só têm de emitir novos cartões utilizando outra tecla selector. Mais antigos cartões podem ser substituídas por outras novas, ou simplesmente o caixa eletrônico transparente possível escrever uma nova PVV (correspondente à nova chave e mantendo o mesmo PIN) próxima vez que o cliente utiliza o seu cartão. Para o shake de segurança todos os usuários devem ser convidados a mudar os seus PINs, no entanto, seria embaraçoso para o banco para explicar o motivo, então muito provavelmente não teriam de fazer tal pedido.
Preparando o ataque
Um ataque consiste em criptografar o SFT com uma conhecida PVV utilizando todas as chaves possíveis criptografar e comparar cada obtidas PVV com o conhecido PVV. Quando uma correspondência for encontrada, temos um candidato chave. Mas quantas chaves, temos de tentar? Como dissemos acima da chave de 64 bit é longo, isso significaria que temos que tentar 2 ^ 64 chaves. No entanto isso não é verdade. De facto, apenas 56 bits são eficazes na DES chaves porque um bit (o menos importante) fora de cada octeto foi historicamente reservado como um checksum para os outros, na prática, esses 8 bits (um para cada um dos 8 octetos) são ignoradas.
Por conseguinte, o DES tecla espaço é constituído por 2 ^ 56 chaves. Se tentarmos todas estas chaves é que iremos encontrar uma e apenas um jogo, correspondente ao banco chave secreta? Certamente que não. Iremos obter muitas correspondências chaves. Isso ocorre porque o PVV é apenas uma pequena parte (um quarto) do DES saída. Além disso, o PVV é degenerada, porque alguns dos dígitos (aquelas entre 0 e 5 após a última, visto da esquerda para a direita, algarismos entre 6 e 9) pode vir da uma decimal de um dígito ou decimalized dígito hexadecimal do DES saída. Assim, muitas chaves irá produzir um DES saída que retorna para a mesma correspondência PVV.
Então o que podemos fazer para encontrar a verdadeira chave entre os outros falsos positivos chaves? Basta que temos para criptografar um segundo diferentes TSP, também conhecida com PVV, mas utilizando apenas as teclas candidato que deu uma correspondência positiva com o primeiro-TSP PVV par. No entanto não há garantia de não entraremos 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 de calcular a probabilidade de um aleatória DES saída para produzir um alinhamento 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 algum conhecimento em matemática das probabilidades.
A probabilidade pode ser 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 (0 até o 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) dentre os 16 dígitos hexadecimais (0 a F) do DES saída.
Exatamente aqueles com apenas três dígitos decimais.
Exatamente aqueles com apenas dois dígitos decimais.
Exatamente aqueles com apenas um dígito decimal.
Aqueles sem dígitos decimais (todos entre A e F).
Vamos calcular quantos números de queda em cada categoria. Se formos rotular os 16 dígitos hexadecimais do DES saída que X1 para x16 então podemos rotular os quatro primeiros dígitos decimais de um determinado número de primeira categoria como o Xi, XJ, Xk e XL. O número de combinações diferentes com este perfil é dado pelo produto 6 i-1 * 10 * 6 undecies-i-1 * 10 * 6k-j-1 * 10 * 6 p.-1 * 10 * 1616-l, se a 6 ' s provir do número de possibilidades de um dígito de A a F, os 10's vêm das possibilidades de um dígito de 0 a 9 e os 16 vem da possibilidade de um 0 a F dígito. Agora, os números totais na primeira categoria é simplesmente dado pelo somatório do produto ao longo deste i, j, k, l de 1 a 16, mas com i <j <k <l. Se você fizer alguma matemática vai ver este trabalho é igual ao produto do 104 / 6 com o somatório ao longo i, de 4 a 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 pela soma mais de i, j, k, de 1 a 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 com isso de ser 16! / (3! * (16-13)!) * 103 * 6 13 = 16 * 15 * 14 / (3 * 2) * 103 * 613 = 56 * 104 * 613 ~ 7,3 * 1015. Da mesma forma para a terceira categoria, temos o somatório ao longo i, j, de 1 a 16 com i <j, de 6 i-1 * 10 * 6 undecies-i-1 * 10 * 616-j, que equivale a 16! / (2! * (16-14)!) * 102 * 614 = 2 * 103 * 615 ~ 9,4 * 1014. Mais uma vez, para a quarta categoria, temos o somatório i longo de 1 a 16 do 6 i-1 * 10 * 616-i = 160 * 615 ~ 7,5 * 1013. E por último 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 esteja certo que 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 de nós. Fazer operações usando os números de 64 bits ou de arredondamento (para carros alegóricos) ou transbordamento (para inteiros) erros não vão deixar você pegar o resultado exato.
Até agora temos calculado o número de possíveis casos em cada uma das cinco categorias, mas estamos interessados em obter o número de casos favoráveis ao invés. É muito fácil tirar o último a partir do antigo como este não é apenas, que fixa a combinação dos quatro dígitos decimais (ou o exigido dígitos hexadecimais, se não houver quatro dígitos decimais) do PVV vez de deixá-las free. Na prática, isso significa transformar os 10's na fórmula acima em 1's e exigido o montante de 6 a 1 em caso de não existirem quatro dígitos decimais. Ou seja, nós temos que dividir o primeiro resultado por 104, eo segundo por 103 * 6, o terceiro por um 102 * 62, a um quarto por 10 * 63 ea quinta por um 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 aquilo que é a probabilidade de um DES saída para coincidir com uma PVV por acaso. Só temos de acrescentar as cinco números de casos favoráveis e divida-o pelo número total de casos possíveis. Fazendo isso temos que obter a probabilidade é muito 0,0001 ou aproximadamente um em cada dez mil. É bem estranho esse resultado arredondado? Nem por isso, basta ter um olhar para os números que calculamos acima. A primeira categoria domina por várias ordens de grandeza do número de casos possíveis e favorá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 dígito) entre os 16 dígitos hexadecimais. Nós vimos anteriormente que a relação entre o número de casos possíveis e favoráveis na primeira categoria foi uma divisão por 10 ^ 4, que é onde o nosso resultado p = 0,0001 vem.
Nosso objetivo era para todos estes cálculos para saber quantos TSP-PVV pares que precisamos para desempenhar um bom ataque. Agora estamos aptos a calcular o número esperado de falso-positivos em uma primeira pesquisa: ele será o número de tentativas vezes a probabilidade de um único aleatória falsos positivos, ou seja, p * t onde t = 2 ^ 56, o tamanho da chave espaço. Isto equivale a aproximadamente 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á (p * t) * p, para uma terceira pesquisa será ((p * t) * p) e p * assim por diante. Assim, para pesquisas n o número esperado de falsos positivos serão p * t ^ n.
Podemos obter o número de pesquisas obrigados a esperar apenas um falso positivo por expressar a equação p * t ^ n = 1 e resolvendo para n. Então n é igual ao logarítmo na base de 1 p / t, o que por propriedades de logaritmos ele retorna n = log (1 / t) / log (p) ~ 4.2. Uma vez que não podemos fazer uma pesquisa fracionário que for conveniente para arredondar este número para cima. Portanto o que é esperado o número de falsos positivos se nos cinco realizar pesquisas? É p * t ^ 5 ~ 0,0007 ou aproximadamente 1 em 1400. Assim, utilizando cinco TSP-PVV pares é seguro para obter a verdadeira chave secreta, sem falsos positivos.
O ataque
Uma vez que sabemos que precisamos cinco TSP-PVV pares, como vamos buscá-las? Claro que precisamos de pelo menos um cartão com a conhecida PIN, e devido à natureza do PVV algoritmo, que é a única coisa de que precisamos. Com outros PIN sistemas, tais como IBM, que precisamos cinco cartões, porém este não é necessária com VISA PVV algoritmo. Só temos de ler a banda magnética e, em seguida, alterar o PIN quatro vezes, mas a leitura do cartão após cada mudança.
É necessário ler a banda magnética do cartão para obter o PVV e as cifrando-chave selector. Você pode comprar um comercial banda magnética leitor ou fazer um você mesmo seguindo as instruções que você pode encontrar na página anterior e links nele. Depois que você tiver um leitor vê esta descrição da norma magnético trilhas para saber como obter o PVV a partir dos dados lidos. Nesse documento, o PVV campo em faixas 1 e 2 é dito ao longo de cinco caracteres, mas na verdade os verdadeiros PVV consiste de quatro últimos dígitos. O primeiro dos cinco dígitos é a chave selector. Tenho visto somente cartões com um valor de 1, neste dígito, o que é consistente com o padrão e com a chave secreta de nunca ser comprometida (e, portanto, eles não precisam se deslocar para outra chave mudando o selector).
Eu fiz um simples programa C, getpvvkey.c, para realizar o ataque. É constituído por um circuito fechado para experimentar várias chaves para encriptar os primeiros TSP, se os derivados PVV corresponde a verdade PVV uma nova TSP é tentado, e assim sucessivamente até que haja um desfasamento, caso em que a chave é descartado e um novo é julgado, ou a cinco derivados PVVs correspondem à verdade PVVs correspondente, caso em que podemos assumir que temos o banco chave secreta, porém o circuito até ao momento em que vai a esgotar a tecla espaço. Isso é feito para garantir que encontramos a verdadeira chave, porque existe uma chance (apesar de muito baixo) a primeira chave encontrada é um falso positivo.
Espera-se que o programa ia levar muito tempo para terminar e para minimizar os riscos de um corte de energia, computador sair, etc ela faz checkpoints em getpvvkey.dat o arquivo de vez em quando (o tempo exato depende da velocidade do computador, é de cerca de uma hora para os computadores mais rápidos agora em uso). Pela mesma razão, se for encontrada uma chave positiva, é lima getpvvkey.key escrito sobre o. O programa só exibe uma mensagem no início, começando a posição assumida desde o ponto de verificação se algum arquivo, depois que nada mais é exibido.
O DES algoritmo é um ponto chave no programa, é, pois, muito importantes para otimizar a sua velocidade. Eu testei várias implementações: libdes, SSLeay, openssl, cryptlib, NSS, libgcrypt, catacumbas, libtomcrypt, cryptopp, ufc-crypt. O DES funções dos quatro primeiros são baseados no mesmo código de Eric Young e é o que teve melhor desempenho (inclui otimizados C e código assembler x86). Assim eu escolhi libdes qual foi a aplicação original e condensados todos os arquivos relevantes no código encrypt.c (versão C) e x86encrypt.s (montador versão x86). O código foi ligeiramente modificada para realizar algumas melhorias em um ataque: a primeira permutação é uma ladeira íngreme fixos comuns em cada TSP criptografia e, portanto, podem ser feitas apenas uma vez no começo. Outra melhoria é que eu escrevi uma função totalmente nova setkey (Eu liguei para ele nextkey), o que é óptimo para uma força bruta loop.
Para obter o programa de trabalho que você só precisa digitar o lugar correspondente cinco TSPs e seus PVVs e, em seguida, compilá-lo. Eu testei-a apenas em plataformas UNIX, usando o makefile Makegetpvvkey para compilar (use o comando "make-f Makegetpvvkey"). Ele pode compilar em outros sistemas, mas pode ser necessário corrigir algumas coisas. Tenha certeza de que a definição do tipo long64 corresponde a um 64 bits inteiro. Em princípio, não há dependência do endianness do processador. Tenho compilou com sucesso e executá-la no Pentium-Linux, Alfa-Tru64, Mips-Irix-Sparc e Solaris. Se você não tem e não quiser instalar o Linux (você não sabe o que está faltando ;-) você ainda tem a opção de executar o Linux em CD e usar o meu programa, ver a minha página executando o Linux sem instalá-lo.
Depois de ter encontrado o segredo bancário chave se você quiser achar o PIN de uma arbitrariedade cartão você só tem que escrever um programa semelhante (desculpe eu não tenho escrito, eu estou demasiado preguiçoso:) que iria tentar todas as 10 ^ 4 PINs por gerar correspondem a TSP, criptografando-a com o (não mais) chaves secretas, decorrentes da PVV e compará-lo com o PVV na banda magnética do cartão. Você vai ter um jogo de verdade o PIN. Apenas um jogo? Lembrar o que vimos acima, temos uma chance de que um 0,0001 encriptação aleatória corresponde à PVV. Nós, tentam 10000 PINs (e, portanto, TSPs), assim esperamos 10000 * 0,0001 = 1 falso positivo, em média.
Este é um resultado muito interessante, isso significa que, em média, cada bilhete válido PINs tem dois: o cliente PIN e os falsos positivos esperados. Eu chamo-lhe "falsas", mas nota que, enquanto ele gera o verdadeiro PVV que é um PIN tão válida quanto a do cliente de uma. Além disso, não há maneira de saber o que é que, mesmo para o caixa eletrônico; só cliente sabe. Mesmo que o falso positivo não eram válidas como PIN, você ainda tem três ensaios no caixa eletrônico qualquer forma, chega, em média. Portanto a probabilidade é calculada no início do presente documento sobre aleatória adivinhação do PIN tem de ser corrigida. Na verdade ele é o dobro desse valor, ou seja, é um fora de 0,0006 ou superior a 1600, ainda pouco segura.
Resultados
É importante para otimizar a compilação do programa e para executá-lo no processador mais rápido possível devido ao longo tempo esperado correr. Achei que o compilador otimização-O pavilhão fica-se com a melhor performance, o pensamento é conseguido adicionando algumas melhorias a-fomit-frame-pointer bandeira sobre Pentium-Linux, cravo-da-bandeira no Alpha Tru64, o IPA-bandeira em Mips-Irix e do fast-bandeira no Sparc-Solaris. Especial bandeiras (-DDES_PTR-DDES_RISC1-DDES_RISC2-DDES_UNROLL-DASM) para o DES código geralmente têm benefícios também. Todos esses pavilhões já foram testados e eu escolhi a melhor combinação para cada processador (ver makefile), mas você pode tentar afinar outras bandeiras.
De acordo com a minha testa o melhor desempenho é alcançado com o processador AMD Athlon 1600 MHz, superior a 3,4 milhões de chaves por segundo. É interessante que obtém melhores resultados do Intel Pentium IV 1800 MHz e 2000 MHz (veja números abaixo, clique nelas para ampliar). Creio que isso se deve a alguns I / O saturação, certamente memória cache ou de acesso, que o processador AMD (que tem metade do cache do Pentium) ou da placa-mãe na qual ele está sendo executado, consegue evitar. Na primeira figura abaixo você pode ver que o DES quebrando velocidade de todos os processadores tem mais ou menos uma relação linear com a velocidade do processador, exceto para os dois Intel Pentium que eu mencionei antes. Isto é lógico, isso significa que, para uma dupla velocidade do processador você poderá obter dupla ruptura velocidade, mas esteja atento aos efeitos saturação, neste caso, é melhor o AMD Athlon 1600 MHz, que será ainda mais barato do que o Intel Pentium 1800 MHz MHz ou 2000.
Na segunda figura podemos ver com mais detalhe o que fazemos apelo intrínseco DES quebrar o poder do processador. Recebo este valor simplesmente dividindo a velocidade por quebrar a velocidade do processador, isto é, ficamos com o número de DES chaves procurei por segundo e por MHz. Esta é uma medida do desempenho do processador tipo, independentemente da sua velocidade. Os resultados mostram que o melhor processador para esta tarefa é o AMD Athlon, em seguida, vem o Alpha e depois de muito perto é o Intel Pentium (exceto para a velocidade mais elevada aquelas que desempenham muito pobre devido à saturação efeito). Seguinte é o processador Mips e no último lugar está o Sparc. Alguns processadores Alpha e Mips estão localizados na parte inferior do importância porque elas são as primeiras liberações não incluindo acessórios da tarde versões. Repare que eu incluído o desempenho dos processadores x86 para C e código assembler já que há uma grande diferença. Parece que um gcc não é bom gerador de código otimizado máquina, mas obviamente não sabemos se um manual de otimização da montadora código para os outros processadores (Alpha, MIPS, Sparc) melhorará os seus resultados comparados com os nativos compiladores C (Eu não uso o gcc para estas outras plataformas), como acontece com o processador x86.
Atualizar
Aqui está um artigo em que essas técnicas podem ter sido utilizados.