O SEGURO MORREU DE BITS
Bruce Schneier
Este 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 computadores 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 crypto-gram-subscribe@chaparraltree.com
A tradução do artigo foi feita pela vovó Vicki da Aldeia Numaboa, sem a devida autorização expressa do autor. Espero que o guru carequinha não queira me processar ;-) O título "O seguro morreu de bits" é da Aldeia.
TAMANHO DE CHAVE E SEGURANÇA
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 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 intervalos para 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 maior número 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 2n 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 tremendamente chatas. Na média, um computador precisa testar cerca da metade das chaves possíveis antes de achar a correta, de forma que um computador 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; ela 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), estava testando 250 bilhões de chaves por segundo quando nos picos de atividade.
Tudo isto está em escala linear. Em 1996, um grupo de criptógrafos (eu incluído) estavam pesquisando as várias tecnologias que poderiam ser usadas para construir máquinas de criptaná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 1015 anos para testar todas as 2112 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; 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. Somente porque um algoritmo aceita um chave de 128 bits, isto não significa que ele possui 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 acima levaram em consideração que os algoritmos usaram as chaves que receberam e as usaram com perfeição. Se existirem falhas no algoritmo, isto reduz a entropia das chaves. Por exemplo, o algoritmo A5/l, usado nos telefones celulares da GSM européia, tem uma chave de 64 bits, mas pode ser quebrado no mesmo tempo em que se quebra 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. Neste caso, também seria possível usar um algoritmo que usasse efetivamente uma chave de 40 bits.
Este é o problema porque o processo AES está demorando tanto. O governo dos EUA quer substituit 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 para o padrão, mas será que qualquer um deles fornece a entropia de 256 bits que alegam possuir? Isto é também porque fica difícil levar a sério produtos que anunciam 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 é gerada. Em outras palavras, considerei que cada chave é igualmente provável. Isto simplesmente não corresponde à verdade.
Muitas chaves são geradas à 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 extendidos nem vão aparecer e senhas que são palavras reais (ou próximas a 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 tenham menos de 4 bits de entropia por caracter. Isto significa que uma frase-senha seja algo como uma chave de 32 bits e que, se você quiser uma chave de 128 bits, então vai precisar de uma frase-senha em Inglês de 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 descreve 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 disso, muito longe. 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 é mais 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 de cabeça 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. Boas senhas são difíceis de guardar, vai reclamar o usuário, mas é justamente por isso que são consideradas boas.
Chaves geradas randomicamente não necessariamente são melhores porque agora o gerador de números randômicos precisa produzir chaves com um máximo de entropia. Uma falha no gerador de números randômicos foi 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 biométrica pode gerar senhas melhores, 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) - mas 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 nada mais do que informação pública. A verificação on-line de senhas, que previne os ataques de dicionário off-line, também funcionam em algumas circunstâncias.
Este é 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 a serem lembradas pelo usuário. Até a PGP se abre se o usuário escolher uma frase-senha ruim. Não interessa o que sejam os algoritmos ou de que tamanho sejam as chaves que usem; segredos a serem 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, os quais têm 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 de uma procura de uma chave de 56 bits. Estimativas para a futura segurança das chaves RSA são muito mais difíceis porque é preciso considerar os avanços na matemática de fatoração assim como os avanços na velocidade e na conectividade em rede dos 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 aproximadamente os próximos dez anos. 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 mesmo 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 para CRYPTO-GRAM.
