Este artigo não descreve algoritmos de criptografia nem ensina a quebrá-los. Trata-se de uma introdução. Se você não sabe a diferença entre chave e senha, ou entre algoritmos simétricos e assimétricos, se não sabe o que é o ataque de força bruta e quantos bits precisa ter para ser seguro, então este artigo poderá lhe ser útil.
Agora que os conceitos foram colocados, vamos aos fatos práticos.
Na informática tudo se resume a bits. Em um algoritmo de criptografia o que se mede é o tamanho da chave em bits. Se uma chave possui 3 bits, ela pode ser uma dentre os seguintes valores:
000
001
010
011
100
101
110
111
Isto nos dá apenas 8 possibilidades para k. Na matemática, o número de possíveis chaves é de 2 elevando ao número de bits (23 = 8).
Assim sendo, se um algoritmo simétrico tiver 128 bits de chave, como é o caso do AES, significa que ele tem 2128 possíveis chaves ou 340282366920938463463374607431768211456 (nem tente ler este número!).
Lembra do nosso computador que testa 1 bilhão de possibilidades e do fato de dispormos de 1 bilhão destes para usar? Com este hardware eu levaria 170141183460469231731 segundos, já considerando a metade das tentativas (2127: lembra? ninguém é tão azarado de acertar na última). Em uma calculadora, dividindo isto por 60 para ter minutos, por 60 novamente para ter horas, por 24 para ter dias e por 365 para anos, chega-se a estrondosa quantia de 5.395.141.535.403 anos!
É pura falta de conhecimento de causa quem afirma que algoritmos simétricos de 128 bits são quebráveis por força bruta. Só mesmo Dan Brown em seu livro "Fortaleza Digital" e seu computador quântico de bilhões de bits para quebrar tal algoritmo!
Se considerar o AES128, não estou dizendo que ele é inquebrável pois pode ter fraquezas exploráveis por criptoanálise. Se houver ou (a) não se descobriu ou (b) quem descobriu não nos contou! O que estou afirmando é ser inquebrável quanto a força bruta!
Literaturas afirmam que um algoritmos simétrico de 256 bits tem segurança eterna, pois nem todo o silício do universo daria para construir uma máquina que o quebrasse (parenteses agora: da maneira como se constrói computadores hoje em dia. Alguns cientistas vem falando da computação quântica e de como ela mudaria a maneira de fazer as coisas. Computação quântica é cercada de mistério e de exageros. O fato é que já existe uma máquina com sete bits quânticos disponível).
Agora o que muitos realmente confundem é quanto a força bruta dos algoritmos assimétricos! É muito, mas muito diferente!
Em um simétrico, se eu tenho 8 bits de chave, tenho 256 combinações possíveis.
Se pegar o caso do RSA que é um assimétrico e se tiver uma chave de 8 bits, significa que o valor do N é de 256 bits. Sem querer descrever o RSA aqui, posso dizer que N é o resultado da multiplicação de dois números primos de 4 bits. Quebrar a chave significa achar um destes números. E não é de 2 elevado na 4 tentativas, pois os valores 2, 4, 6, 8, 9, 10 não precisam ser testados pois não são primos!
No universo de 4 bits só existem estes primos: 2, 3, 5, 7, 11,13. Só! Mata-se em seis tentativas no máximo!
Para algoritmos assimétricos, como no caso do RSA, o cálculo do esforço matemático não é simplesmente de 2NumeroDeBits. É muito, mas muito menos que isto.
Exatamente por isto é que os algoritmos assimétricos precisam de uma chave muito maior, hoje perto dos 1024 bits. No caso do RSA, dizer que ele é de 1024 bits, significa que o valor de N é de 1024 bits, logo quebrar significa encontrar um número primo de até 512 bits que sirva.
Aí tem gente que se acostumou a ver o RSA de 1024 bits e sai dizendo que um AES de 128 é fraco, pois só 128 bits? São coisas diferentes, meu caro!
[10] Comentário enviado por elgio em 26/02/2009 - 17:21h
rodrigoclira: o artigo sobre RSA irá sair SIM!
affboy: eu não terminei de ler o livro do Dan Brown. Li pouco menos de 1/4 dele e parei. É muito fantasioso, assim como os demais que li completamente.
Aos demais, obrigado pelos comentários. Certamente irei escrever outros tantos artigos sobre criptografia e os postarei aqui no VOL.
[11] Comentário enviado por andre.vmatos em 26/02/2009 - 23:42h
E ae, Elgio. Nossa, muito bom o seu artigo. Quanto ao jogo da forca, você poderia ser um pouco mais preciso??? Segue uma pequena lista de palavras que podem ser resposta para o seu jogo:
[14] Comentário enviado por paulinhorm em 27/02/2009 - 10:26h
Simplesmente fantastico o seu artigo....muito didático e de facil compreensão, tenho certeza de que não só eu mas muitos leitores do VOL estão ansiosos pela continuação...parabéns
[15] Comentário enviado por elgio em 27/02/2009 - 12:03h
Oi Andre.matos
na verdade muitas de tuas palavras não se encaixam de forma alguma, pois elas possuem letras 'a's em posições que sabe-se não serem corretas. Todos os 'a' s já estão na forca: _ _ _ _ _ A _ A _ Ã_
Alias, dito isto, a minha expressão regular acima também está equivocada. O certo é:
grep "^[^a][^a][^a][^a][^a]a[^a]a[^a]a[^a]$" dicionario.txt
(sendo dicionario desprovido de acentuacao e tudo em minusculo)
Assim apenas estas palavras se encaixam (das tuas!)
[19] Comentário enviado por conrad0 em 27/02/2009 - 15:32h
O autor está de parabéns. Explicações simples e objetivas, como todo bom Professor deve fazer. Adoraria ter tido professores, na faculdade, com sua didática.
Parabéns novamente.
[21] Comentário enviado por stremer em 27/02/2009 - 15:55h
Simplesmente o melhor texto de introdução a criptografia que ja li em minha vida.
Só uma observação... eu sou daqueles que muitas vezes só sabem usar mesmo a parte de criptografia e nem sei como elas funcionam... só as utilizo em meus aplicativos, seja o Hmac, AES, dentre outros... ai sempre o pessoal da segurança fala: Não existe nada inquebravel... esses números de combinações são irreais... hoje você pode ter um exército de "maquinas zumbis" trabalhando por você e quebrar do mesmo jeito... ai sempre contesto... mas esse exército precisa ser muito grande... talvez todas os computadores do mundo!!! O que você tem a falar sobre isso Elgio? Tenho grande curiosidade... Obrigado e parabéns novamente!
[22] Comentário enviado por elgio em 27/02/2009 - 16:18h
Oi stremer!
Obrigado pelos elogios. Eu realmente pretendo continuar esta série de artigos.
Quanto a sua pergunta, dependendo do algoritmo e do tamanho da chave, nenhum exército de máquinas conseguirá quebrar (por força BRUTA!). Nem todas as máquinas do mundo.
Se usares o AES com 128 bits de chave, por exemplo, os números são realmente IMPLACÁVEIS!
Mesmo tentando 1/4 das possíveis chaves, o que nos daria 2^126 combinações e fazendo o seguinte exercício:
- Existe um código que consegue tentar uma chave por ciclo de CPU: IMPOSSÏVEL. Mesmo os códigos mais otimizados usarão milhares de ciclos de CPU. Mas que seja.
- Com este hipotético código, um processador de 1Ghz consegue tentar 1.000.000.000 de chaves por segundo (1 bilhão) pois ele tenta uma a cada ciclo.
- Digamos que tenho processadores de 10Ghz (outra bobabem) e que existe uma máquina, uma única, como 1.000.000 (1 milhão) de processadores.
Resumindo: 1 máquina, com 1 milhão de processadores, cada um de 10Ghz tentando uma chave por ciclo de CPU.
Segundo a wikipedia, a população mundial hoje chega perto dos 6 Bilhões de pessoas. Vamos supor que cada uma destas pessoas tenha uma destas maquinas e está disposta a nos ajudar:
- 6 Bilhões de máquinas tentando (6.000.000.000)
- Cada máquina com 1 milhão de processadores (1.000.000)
- Cada processador de 10Gh (10.000.000.000)
- e um teste por ciclo de CPU, precisando testar 1/4 das chaves (2^126)
2^126 numero de chaves
divido por 10.000.000.000 porque cada chipe testa isto por segundo
divido depois por 1.000.000 porque uma única máquina tem 1 milhão de chips
divido por 6.000.000.000 porque cada cidadão do planeta tem uma máquina destas
Ai eu teria o número de segundos que meu teste levaria: 1.417.843.195.503
Divido por 60 para ter em minutos, por 60 novamente para ter horas, por 24 para ter dias e por 365 para ter anos.
Ainda sim eu levaria 44.959 anos!
Não tem como querer dizer que possa ser quebrado por força bruta! NÃO MESMO! O algoritmo é muito forte. E veja que um milésimo disto ainda seria 44 anos.
Pode-se discutir que agências como a NSA tenham descoberto furos e tem atalhos para quebrar. Pode-se discutir sobre terem já as tais máquinas quanticas. Mas a matemática da força bruta é esta. Pura e simples.
Agora claro que qualquer um pode boicotar até mesmo o melhor algoritmo. Foi o que o padrão WEP fez, implementou o RC4 de forma equívoca e até hoje tem gente que pensa que o RC4 é ruim.
Exemplo de uma má utilização do AES:
Como a chave é de até 128 bits, eu determino que o tamanho da chave será de 16 caracteres e uso estes caracteres DIRETO como chave. Se o usuário não digitar os 16 eu preencho com zero!
Ai dançou!
Pois cada byte da chave poderá ser apenas letras e numeros sendo que é bem provável que alguns bytes sejam ZERO porque o usuário não usou 16 letras. Se ele usar apenas 8 letras e, PIOR, usar apenas números, um teste de 00000000 até 99999999 terá resultado!
O que se faz neste caso, como o gnupg, por exemplo.
Se usa a senha que o usuário digitou, que se chama de frase de passagem, se gera um hash dela e usa o hash como chave.
Exemplo: vou cifrar meu HD com AES. O programa pede uma frase de passagem (sem limite de letras).
Eu digito:
"Ape,Nas989 para nao esquecer$#"
O programa computa md5(frase):
echo -ne "Ape,Nas989 para nao esquecer$#"|md5sum
Que em hexa da bfb7a0cb7bb67ed6c5a2d0bf253a499b
Se usa isto como chave!
Quando o usuário digitar a frase de passagem, se repete o processo!
É uma solução super eficiente para não limitar as possíveis chaves.
[23] Comentário enviado por elgio em 27/02/2009 - 16:40h
Complementando minha resposta anterior.
NÃO IMPORTA A FORÇA DO ALGORITMO!
Se você determinar que serão aceitas como chave apenas letras [A-Za-z] ou número [0-9] e obrigar o usuário a colocar 8 letras como chave, o força bruta poderá ser concluido em 62^8 (62 elevado na oito), pois cada caracter dos oito pode assumir um valor dentre 62 (26 A-Z, 26 a-z e 10 0-9). Ai se está restringindo os possíveis valores de chave (sendo que sem esta restrição cada caractere poderia ser um valor dentre 256 e eu PRECISARIA TER 16 caracteres).
Este é o equívoco que muitos fazem!
Se o cenário for este, tem um total de
echo "62 ^ 8"|bc
218.340.105.584.896 possibilidades.
E será este mesmo número mesmo que eu use o AES de 256 bits!
Para usar a força do algoritmo é preciso libertar-se desta restrição, o que as vezes é difícil ou impraticável (conseguiria eu exigir que um usuário colocasse como senha uma frase de passagem grande, sem ser dicionário, misturando letras, números e simbolos para poder usar no MD5? Nada, se não cuidar o cara vai digitar a placa do carro, nascimento da filha, aniversário de casamento... ops, esta ultima não pois teria que anotar para lembrar a senha!
[24] Comentário enviado por stremer em 27/02/2009 - 18:57h
Entendi Elgio... Muito boa a explicação...
Já era mais ou menos o que eu imaginava...
Eu costumo utilizar AES-128 bits... e a chave geralmente é feita usando o base64 de uma senha grande aleatória.
Poderia ser também o hash... (ja utilizei o md5 também)
e nesse caso acho que por força bruto fica meio impossivel alguem descobrir os dados de um arquivo criptografado... isso sem considerarmos as variaveis que você citou!
Deixa eu só ver então se entendi bem esse lance do WEP... o cara então não usa caracteres especiais, somente letras e números... ou seja, seria como se a chave tivesse menos bits, pois algumas combinações teriam menos possibilidades... como você falou no exemplo do 62^8... ai nesse caso juntando as técnicas de força bruta com criptoanalise, poderia quebrar rapidinho... (que é mais ou menos o que o aircrack-ng faz né?)...
se eles ao invés de terem gerado a chave baseado na senha, mas gerado um hash... já mudaria a figura?? É isso mesmo???
[25] Comentário enviado por elgio em 27/02/2009 - 19:02h
Não stremer!
A pisada na bola no padrão WEP foi muito mais grave, tanto que WEP de 64bits ou 128bits dá na mesma.
Explico com mais calma depois (estou entrando em aula agora), mas, basicamente, eles detonaram o WEP quando definiram um VI (vetor de inicialização) de apenas 24 bits. Em tese se teria 2^24 possibilidades, mas isto somado a outros equívocos detonou ainda mais o método de sorte que programas como aircrack quebram hoje em pouco tempo.
Depois explico pois o assunto é muito interessante!
[]'s
[26] Comentário enviado por elgio em 28/02/2009 - 11:12h
Oi stremer.
Segue a explicação, EXTENSA, sobre os problemas do WEP.
De inicio divulgo uma palestra minha que trata de criptografia. Se alguém ficou curioso sobre como funciona o RSA e algoritmos de fluxo a palestra trata disto. Pode ser baixada em http://www.inf.ufrgs.br/~tpbiazus/ (Conceitos básicos de Criptografia e protocolo SSL, Pelotas, 23/Agosto/2008).
Sobre o WEP:
A padrão WEP é baseado no algoritmo simétrico de fluxo RC4. Pode ser de 64bits ou de 128bits.
O RC4 é uma cifra que usa unicamente XOR, o que permite uma cifragem bit a bit. Interessante pois não é necessário esperar o acúmulo de um bloco inteiro para cifrar. Cifras baseadas em XOR são seguras desde que não haja repetição de chave, ou seja, se eu cifrar via XOR um texto "ABCDE" com a chave "XYKZU" eu não posso usar a chave "XYKZU" para cifrar outra mensagem, pois se um atacante tiver as duas mensagens e souber que elas foram cifradas com a mesma chave pode fazer criptoanálise. Isto significa que para que o XOR pudesse ser usado com segurança a chave deve ser tão grande quanto a mensagem.
RC4 resolve este problema construindo um gerador de bits pseudo-aleatórios. Uma máquina que fica "guspindo" bits que não formam uma dízima periódica, ou seja, ela não gera bits como estes "01100 01100 01100 ...", pois isto seria repetição de chave, mas sim algo como "01100 01011 10110 10001...". Estes bits são udados para cifrar por XOR a mensagem.
Fato é que esta máquina guspidora de bits precisa ser inicializada com um valor e se duas máquinas forem inicializadas com o mesmo valor elas estarão sincronizadas e irão gerar os mesmos bits. Desta forma basta que o remetente e o destinatário ajustem suas máquinas RC4 com o mesmo número inicial e elas estarão sincronizadas. Ora, este número passa a ser o segredo que ambos compartilham.
Pode-se usar um valor de 64 bits ou de 128 bits para inicializar o RC4. Em tese, mesmo que se use o de 64 bits, ainda assim 2^64 é muito e inquebrável por força bruta o que garante uma boa segurança ao RC4.
Agora vamos a implementação do RC4 no WEP.
Consideramos chave de 64 bits. A princípio o emprego poderia ser assim:
- cadastro na minha base wireless uma chave de 64 bits, exemplo: 20 F2 45 00 15 78 AB C6
- divulgo esta chave aos meus clientes wireless.
- Cliente e AP inicializam suas máquinas RC4 com esta chave e a comunicação ocorre.
Porém este algoritmo acima tem um inconveniente: um cliente wireless poderia ler os dados de outro cliente wireless pois todos usam a mesma chave! Além de que haveria colisão, ou seja, um cliente usaria os bits do RC4 para cifrar seus dados, outro cliente usaria os mesmos bits o que seria repetição de chave XOR possibilitanto criptoanálise.
Para (tentar) evitar este problema, a chave RC4 é dividida em duas partes:
- 40 bits FIXOS
- 24 bits de VI (Vetor de inicialização)
Então eu cadastro na AP e nos clientes apenas 40 bits de chave: 20 F2 45 00 15
Clientes e AP tem esta chave cadastrada, mas os outros 24 bits são aleatórios.
Veja que se os 24 bits forem sempre os mesmos haverá colisão, logo espera-se que os clientes usem sempre valores inéditos em suas comunicações e ai começam os problemas!
Primeiro problema porque a cada novo frame um novo VI é escolhido e quem escolhe é o cliente. Considerando que um frame pode ter até 1500 octetos. Como existem apenas 2^24 possíveis VIs um único clientes consegue enviar 24Gbytes sem precisar repetir. OK, isto seria suficiente, pois se considerar um rede de 11Mbps uma máquina poderia transmitir por 290 minutos sem repetir VI.
Mas em uma rede existem muitas outras máquinas que juntas podem gerar colisão muito rapidamente. Além disto teve o fato da negligência de alguns fabricantes de rede que ao terem que escolher o VI simplesmente começam em 00 00 00 e vão incrementando a cada novo frame, ou seja, Vis previsíveis.
Também tem a perda de sincronismo que força AP e clientes a trocarem novamente os seus Vi's.
Juntando tudo isto, tornou-se possível construir ferramentas que realizam criptoanálise analisando as colisões. Para tal a ferramenta precisa de mensagens que sejam colisões e elas existirão. As primeiras ferramentas precisavam de horas de tráfego intenso para poder descobrir a chave. As novas jogam lixo no sinal, forçando alguns sincronismos e literalmente fabricando colisões. Isto aliado as colas torna a quebra do WEP muito fácil (colas pois em um cabeçalho ethernet e mesmo IP tem muitas informações previsíveis, como número MAC, numero IP, etc, que podem ser usadas).
E não adianta usar o WEP de 128 bits, pois neste padrão a chave é de 102 e o VI igualmente de míseros 24 bits. A corda arrebenta no lado mais fraco e pode colocar quantos bits quiser, mas se mantiver 24 bits de VI a força será medida por ele.
O padrão WEP2 mudou apenas isto: Vi passou a ser de 48 bits o que já dá uma boa garantia.
Em http://www.inf.ufrgs.br/~tpbiazus/ (Conceitos básicos de Criptografia e protocolo SSL, Pelotas, 23/Agosto/2008) tem os slides de uma palestra minha sobre criptografia onde descrevo os algoritmos de fluxo (slides 17 e 18). Esta mesma apresentação pode sanar a curiosidade sobre o algoritmo RSA.
[28] Comentário enviado por elgio em 28/02/2009 - 12:49h
WPA?
Pois é.
Não falo porque ainda não tive tempo de estudá-lo completamente.
Mas adianto que existem DIVERSOS modos de autenticação neste padrão.
Um deles é o mesmo WEP, da mesma forma, porém com VI de 48 bits
[29] Comentário enviado por andre.vmatos em 28/02/2009 - 17:10h
Rsrsrs, tem razão, Professor. Esqueci de excluir da lista as palavras que continham outros "a"s além dos já indicados. Porém, o dicionário do BrOffice, para quem o conhece de perto, é repletos de acentos, e as linhas não terminam onde termina as palavras, sendo que cada linha apresenta vários sufixos, referentes ao seu uso no BrOffice (não podendo, portanto, usar o seu grep com indicação de fim de linha ($) no final do comando). Outra coisa, eu sabia que a palavra era programação, porém, quis adicionar um pouco de emoção à brincadeira. Novamente, parabéns pelo artigo. T+
[31] Comentário enviado por carlaliliane em 06/03/2009 - 11:41h
Parabéns Elgio! Artigo nota 10. E concordo com o conrad0, na facul todos professores deveriam ser bons assim.
Valeu por compartilhar um pouco do teu vasto conhecimento. BJs
[34] Comentário enviado por adrianoturbo em 02/05/2009 - 14:07h
Excelente artigo professor Elgio.
Uma coisa que ainda não conseguir encontrar foi sobre as técnicas de segurança: cifração(confusão) ,permutação e transposição(difusão) ,com os tipos de segurança :fisica,
lógica e externalidade.
Parabéns pelo artigo.
[49] Comentário enviado por arthurmatiello em 01/04/2021 - 10:35h
Que didatica sensacional.
Estou estudando criptografia para tirar a certificação LPIC-3 e com a sua didatica tudo fica mais facil, mesmo sendo um artigo de 2009.
Parabéns.