Detalhes

Categoria: Criptoanálise

Atualização: Domingo, 14 Junho 2009 16:54

Autor: vovó Vicki

Acessos: 14376

O texto de Bruce Schneier, publicado em 15 de Outubro de 1999 na newsletter mensal CRYPTO-GRAM, dá uma idéia clara da estrutura, da segurança e dos problemas relacionados a sistemas de criptografia baseados em algoritmos simétricos.

A newsletter é grátis e traz resumos, análises, insights e comentários sobre segurança de dados e criptografia. Os textos são em Inglês. Para assinar a newsletter basta acessar o site da Counterpane ou enviar uma mensagem em branco para O endereço de e-mail address está sendo protegido de spambots. Você precisa ativar o JavaScript enabled para vê-lo.

Fiz a tradução do artigo à minha moda e sem a devida autorização do autor. Espero que o guru carequinha não queira me processar. O título "O seguro morreu de bits" foi idéia minha

O tamanho da chave e a segurança

Bruce Schneier

Apesar do que todos queiram te contar, o comprimento de uma chave criptográfica praticamente não tem nada a ver com a segurança. Uma chave curta significa segurança ruim, porém uma chave longa não necessariamente significa uma boa segurança.

A fechadura da porta da frente da sua casa tem uma série de pinos. Cada um destes pinos possui múltiplas posições possíveis. Quando alguém põe a chave na fechadura, cada um dos pinos é movido para uma posição específica. Se as posições ditadas pela chave são as que a fechadura precisa para ser aberta, ela abre. De outra forma, não.

A maioria das fechadura tem cinco pinos, cada um dos quais pode estar em uma de dez posições diferentes. Isto significa que existem 100.000 chaves possíveis. Um ladrão, com um molho de chaves muito grande, pode experimentar cada uma das chaves, uma após a outra, e eventualmente encontrar uma que funcione. É melhor que ele tenha muita paciência porque, mesmo que ele possa experimentar uma chave a cada cinco segundos, vai precisar de cerca de 69 horas para achar a chave certa - e isto não inclui as idas ao banheiro ou os intervalos para um lanche.

Um belo dia um vendedor bate à sua porta e oferece uma fechadura nova. A fechadura que ele oferece possui seis pinos com doze posições cada. Um ladrão, diz ele, vai precisar de 259 dias ininterruptos de tentativas com chaves diferentes antes que consiga abrir a sua porta. Você se sente mais seguro com esta nova fechadura?

Provavelmente não. De qualquer maneira, nenhum ladrão ficaria na frente da sua casa por 69 horas. É mais provável que ele use uma micha, que arrebente a porta, quebre uma janela ou que apenas se esconda atrás de uma árvore até que você apareça na calçada da frente. Uma fechadura com um número maior de pinos e posições não vai aumentar a segurança da sua casa porque o tipo específico de ataque que ela dificulta - tentar cada uma das chaves prováveis - não é bem o que te preocupa. Se o número de pinos for suficiente para tornar este ataque impraticável, você não tem que se preocupar com ele.

A mesma coisa é válida para chaves criptográficas. Se forem suficientemente longas, não há motivos para se preocupar, e o comprimento que é "suficientemente longo" é mais complicado do que um simples número - depende da aplicação e da quantidade de entropia das chaves.

Começando do início

Vamos começar pelo início. Uma chave criptográfica é um valor secreto que modifica um algoritmo de encriptação. Se Alice e Bob compartilham uma chave, eles podem usar o algoritmo para se comunicarem com segurança. Se Eva, uma bisbilhoteira, não conhece a chave, ela não consegue ler as mensagens de Alice ou de Bob. Ela é forçada a tentar "quebrar" o algoritmo, isto é, tentar descobrir a chave apenas através do texto cifrado.

Uma coisa óbvia que ela pode fazer é tentar cada uma das chaves possíveis, como o ladrão hipotético citado no início. Se a chave tiver o comprimento de n bits, então existem 2ⁿ chaves possíveis. Desta forma, se a chave tiver 40 bits de comprimento, existem aproximadamente um trilhão de chaves possíveis. Isto seria uma tremenda duma chatice para o ladrão, porém computadores são perfeitos para tarefas horrivelmente chatas. Na média, um computador precisa testar cerca da metade das chaves possíveis antes de achar a correta, de forma que uma máquina capaz de testar um bilhão de chaves por segundo levaria 18 minutos para achar a chave de 40 bits correta. A máquina Deep Crack, "quebradora" do DES, testou 90 bilhões de chaves por segundo e podia encontrar, em média, uma chave DES de 56 bits em 4 dias e meio. O projeto de pesquisa de chaves através da Internet distribuída, o distributed.net (o qual incluía a Deep Crack), conseguia testar 250 bilhões de chaves por segundo quando estava nos picos de atividade.

Tudo isto está em escala linear. Em 1996, um grupo de criptógrafos (inclusive eu) estavam pesquisando as várias tecnologias que poderiam ser usadas para construir máquinas de criptoanálise pela força bruta e recomendaram uma chave de, no mínimo, 90 bits para garantir a segurança até 2016. O Triple-DES tem uma chave de 112 bits e a maioria dos algoritmos modernos têm chaves de pelo menos 128 bits. Mesmo uma máquina um bilhão de vezes mais rápida que a Deep Crack levaria 10¹⁵ anos para testar todas as 2¹¹² chaves e recuperar o texto claro. Mesmo considerando que a lei de Moore continue válida pelas próximas centenas de anos, isto será seguro por um longo período.

Então, porque se preocupar? Porque não usar simplesmente chaves de zilhões de bits e ficarmos seguros pelo resto dos tempos? Para responder esta pergunta, preciso explicar o que é entropia.

A Entropia

A entropia é a medida da incerteza. Quanto mais incerta for alguma coisa, maior é a entropia desta coisa. Por exemplo, se escolhermos uma pessoa ao acaso, de uma população geral, ela será do sexo masculino ou do sexo feminino - a variável "sexo" possui um bit de entropia. Se uma pessoa ao acaso prefere um dos quatro Beatles, e cada um deles é igualmente preferido, isto corresponde a dois bits de entropia. O sexo de alguém que esteja participando de uma competição de natação masculina não tem entropia, pois todos são do sexo masculino. A entropia da preferência por um dos Beatles num fã-clube de John Lennon é muito menor do que dois bits porque é muito mais provável que uma pessoa ao acaso prefira o John. Quanto maior for a certeza numa variável, menor será a entropia.

O mesmo é válido para chaves criptográficas. O simples fato de que um algoritmo aceita um chave de 128 bits não significa que ele possua 128 bits de entropia na sua chave. Ou, mais exatamente, a melhor maneira de quebrar uma dada implementação de um algoritmo de encriptação de 128 bits pode não ser experimentar cada uma das chaves prováveis.

Preocupações

A primeira preocupação é com a qualidade do algoritmo de encriptação. Todos os cálculos citados levam em consideração que os algoritmos usam as chaves que recebem e as usam com perfeição. Se existirem falhas no algoritmo, isto reduz a entropia das chaves. Por exemplo, o algoritmo A5/l, usado nos telefones celulares GSM da Europa, tem uma chave de 64 bits, mas o tempo para quebrá-lo é o mesmo necessário para quebrar uma chave de 40 bits pela força bruta. Isto significa que, mesmo que se tenha fornecido ao algoritmo uma chave de 64 bits de entropia, ele usa apenas 40 bits de entropia na chave. Num caso como este, também é possível usar um algoritmo que use efetivamente uma chave de 40 bits.

O mesmo problema está atrasando a implantação do algoritmo AES. O governo dos EUA quer substituir o DES (que tem uma chave de 56 bits) por um novo algoritmo que aceite chaves de até 256 bits. A esta altura há cinco semifinalistas, mas será que qualquer um deles fornece a entropia de 256 bits que alega possuir? Este também é o motivo pelo qual fica difícil levar a sério os anunciantes de produtos com chaves de mil bits - eles não entendem como funcionam as chaves e a entropia.

A segunda preocupação é com a origem das chaves. Todos os cálculos de comprimento de chave que acabei de fazer consideram que cada chave tenha o máximo de entropia quando ela é gerada. Em outras palavras, considerei que cada chave é igualmente provável. Isto simplesmente não corresponde à realidade.

Muitas chaves são geradas a partir de senhas ou frases-senha. Um sistema que aceita senhas de 10 caracteres ASCII pode necessitar de 80 bits para representá-los, porém possui muito menos do que 80 bits de entropia. Caracteres ASCII estendidos nem vão aparecer e senhas que são palavras reais (ou próximas de palavras reais) são muito mais prováveis do que strings de caracteres randômicos. Tenho visto que a entropia estimada do Inglês padrão é de 1,3 bits por caracter; as senhas, provavelmente, têm menos de 4 bits de entropia por caracter. Isto significa que uma frase-senha é algo como uma chave de 32 bits e que, se você quiser uma chave de 128 bits, vai precisar de uma frase-senha em Inglês que tenha 98 caracteres.

Como você pode perceber, um motor para quebrar senhas através da força bruta não vai testar pela ordem cada uma das chaves possíveis. Vai testar primeiro as mais prováveis e depois testar as restantes de acordo com um critério semelhante. Vai testar as senhas mais comuns, do tipo "password" e "1234", depois o dicionário de Inglês inteiro e finalmente maiúsculas e números extras variados, e assim por diante. L0phtcrack é um programa de quebra de senhas que faz isto; num Pentium Pro 200 ele pode comparar um arquivo de 200 senhas com um dicionário de 8 Megabytes de senhas comuns em menos de um minuto. Testar todo o espaço do alfabeto de 26 caracteres leva 26 horas e o espaço alfanumérico de 36 caracteres leva cerca de 250 horas.

A Segurança

É por isso que é hilário quando companhias como a Microsoft coletam encriptações de 128 bits e depois baseiam a chave na senha (isto caracteriza muito bem toda a segurança do Windows NT). Os algoritmos que eles usam até podem aceitar uma chave de 128 bits, mas a entropia de uma senha está longe, muito longe disso. Na verdade, não importa o quanto a criptografia seja boa ou qual seja o comprimento da chave - senhas fracas irão quebrar este sistema.

Alguns lidaram com este problema exigindo senhas cada vez mais fortes, mas isto também não é efetivo. Nas últimas décadas, a lei de Moore tornou possível usar a força bruta em chaves cada vez maiores e com mais entropia. Ao mesmo tempo, existe um máximo de entropia que o usuário comum de computadores (ou mesmo o usuário acima da média) queira lembrar. Você não pode esperar que ele guarde na memória uma string de 32 caracteres hexadecimais randômicos, mas é isso que precisa acontecer se ele tiver que decorar uma chave de 128 bits. Estes dois números chegaram no limite. Quebradores de senhas, agora, podem quebrar qualquer coisa que possivelmente seja razoável esperar que um usuário memorize. O usuário vai reclamar que as senhas boas são difíceis de guardar, mas é justamente por isso que são consideradas boas.

Mas as chaves geradas randomicamente também não são necessariamente as melhores porque dependem de um programa gerador de números randômicos que produza chaves com um máximo de entropia. Foi exatamente uma falha no gerador de números randômicos o que quebrou a encriptação do Netscape versão 1.1. Apesar do gerador de números randômicos ter sido usado para gerar chaves de 128 bits, a entropia máxima estava ao redor de 20 bits. Desta forma, o algoritmo não era melhor do que um que gerasse uma chave de 20 bits.

As soluções existem, porém requerem renúncias da engenharia. A biometria pode gerar senhas melhores, mas não porque contenham mais entropia. Por exemplo, uma impressão digital (meu palpite é de que seja equivalente a uma chave de cerca de 60 bits) é melhor porque não existe algo como uma impressão digital ruim da forma como existe uma senha ruim. Smart cards oferecem um jeito conveniente de transportar uma chave de alta entropia, porém possuem as restrições associadas a um dispositivo físico. E, para alguns sistemas de comunicação, protocolos de chave pública podem gerar segredos de alta entropia usando apenas informação pública. A verificação on-line de senhas, que previne os ataques de dicionário off-line, também funciona em algumas circunstâncias.

Senhas são um grande negócio. Vejo sistemas PKI complexos onde a chave privada é protegida por uma senha. Praticamente todos os produtos de encriptação em HD baseiam sua segurança numa chave a ser lembrada pelo usuário. Praticamente toda a segurança do Windows NT entra em colapso porque foi construída sobre senhas que precisam ser lembradas pelo usuário. Até a PGP se abre se o usuário escolher uma frase-senha ruim. Não interessa quais sejam os algoritmos ou de que tamanho sejam as chaves que usem - segredos que precisam ser lembrados por usuários não são seguros.

Observações sobre algoritmos de chave pública

Este texto fala sobre algoritmos simétricos (cifras de bloco e de fluxo), os quais usam strings com um número arbitrário de bits como chaves. Os sistemas de chave pública com chaves matemáticas, como o produto de dois números primos grandes, são diferentes. Ainda existem ataques pela força bruta contra sistemas de chave pública, porém eles envolvem a solução de problemas matemáticos como a fatoração. O grupo que acabou de fatorar uma chave RSA de 512 bits disse que o cálculo representou cerca de 2% do esforço na procura de uma chave de 56 bits. Estimativas para a futura segurança das chaves RSA são muito mais difíceis de se estabelecer porque é preciso considerar os avanços na matemática de fatoração, assim como os avanços na velocidade e na conectividade na rede de computadores.

Estimativas conservadoras indicam que chaves de 1024 bits são boas o suficiente para mais alguns poucos anos e que, chaves de 2048 bits, deveriam ser boas o suficiente para os próximos dez anos (aproximadamente). Mas, uma vez que ninguém nem mesmo sabe se a fatoração é "difícil", certamente é possível que um matemático brilhante possa aparecer e tornar estes tamanhos de chave inseguros.

As chaves RSA, é claro, têm entropia demais para se memorizar. Ou elas são encriptadas com uma frase-senha e armazenadas no HD, ou são armazenadas em um token como um smart card. Algumas vezes são até mesmo deixadas abertas.

Fonte

Texto de Bruce Schneier publicado em 15.10.99 no CRYPTO-GRAM.