Detalhes

Categoria: Criptoanálise

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

Autor: vovó Vicki

Acessos: 14373

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.