Tamanho da chave

Em criptografia, tamanho da chave ou comprimento da chave é o tamanho medido em bits da chave usada em um algoritmo criptográfico (tal como uma cifra). O comprimento de chave de um algoritmo é distinto de sua segurança criptográfica, que é uma medida logarítmica do ataque computacional mais rápido conhecido sobre o algoritmo, também medido em bits. A segurança de um algoritmo não pode exceder o seu comprimento de chave (já que qualquer algoritmo pode ser quebrado pela força bruta), mas pode ser menor. Por exemplo, Triple DES tem um tamanho de chave de 168 bits, mas fornece, no máximo, 112 bits de segurança, já que um ataque de complexidade 2¹¹² é conhecido.  Esta propriedade do Triple DES não é uma fraqueza dado que 112 bits de segurança é suficiente para uma aplicação. A maioria dos algoritmos de chave simétrica de uso comum são projetados para ter segurança igual ao seu comprimento de chave. Nenhum algoritmo de chave assimétrica com essa propriedade é conhecido; criptografia de curvas elípticas chega mais próximo com uma segurança efetiva de, grosso modo, metade do seu comprimento de chave.

Significação

Chaves são usadas para controlar o funcionamento de uma cifra de modo que somente a chave correta pode converter o texto criptografado (cifrotexto) para o purotexto. Muitas cifras são na verdade baseadas em algoritmos conhecidos publicamente ou são de código aberto (open source), e por isso é apenas a dificuldade de obter a chave que determina a segurança do sistema, dado que não há ataque analítico (isto é, uma "fraqueza estrutural" nos algoritmos ou protocolos utilizados), e assumindo que a chave não está, de outra maneira, disponível (como através de roubo, extorsão, ou comprometimento de sistemas de computador). A noção amplamente aceita de que a segurança do sistema deve depender somente da chave foi explicitamente formulada por Auguste Kerckhoffs (nos anos 1880s) e Claude Shannon (nos anos 1940s); os enunciados são conhecidos como Princípio de Kerckhoffs e Máxima de Shannon respectivamente.

A chave deve ser grande o suficiente para que um ataque de força bruta (possível contra qualquer algoritmo de criptografia) seja inviável - ou seja, levaria muito tempo para executar. O trabalho de Shannon sobre information theory mostrou que para alcançar o chamado sigilo perfeito, o comprimento da chave deve ser pelo menos tão grande quanto a mensagem e a chave de ser utilizada apenas uma vez (esse algoritmo é chamado One-time pad). À luz disto, e da dificuldade prática de gerenciar tais chaves longas, a prática criptográfica moderna descartou a noção de sigilo perfeito como um requisito para a criptografia, e em vez disso se concentra em segurança computacional, em que os requisitos computacionais de quebrar um texto criptografado devem ser inviáveis para um atacante.

Os números preferidos (do inglês, preferred numbers) comumente utilizados como tamanhos de chave (em bits) são potências de dois, potencialmente multiplicado com um pequeno número inteiro ímpar.

Tamanho da chave e sistema de encriptação

Sistemas de encriptação são frequentemente agrupados em famílias. Famílias comuns incluem sistemas simétricos (por exemplo, AES) e sistemas assimétricos (por exemplo, RSA); eles podem, alternativamente, ser agrupados de acordo com o algoritmo central usado (por exemplo, criptografia de curvas elípticas).

Como cada uma destas é de um nível diferente de complexidade criptográfica, é usual ter diferentes tamanhos de chave para o mesmo nível de segurança, dependendo do algoritmo utilizado. Por exemplo, a segurança disponível com uma chave de 1024 bits utilizando o algoritmo assimétrico RSA é considerada aproximadamente igual em segurança a uma chave de 80 bits em um algoritmo simétrico (Fonte: RSA Security).

O verdadeiro grau de segurança atingido varia com o tempo, à medida que mais poder computacional e métodos analíticos matemáticos mais poderosos se tornam disponíveis. Por esta razão criptólogos tendem a olhar para os indicadores de que um algoritmo ou tamanho da chave revela sinais de vulnerabilidade potencial, para aí então mudar para tamanhos de chave mais longos ou algoritmos mais difíceis. Por exemplo, a partir de maio de 2007, um número inteiro de 1039 bits foi fatorado com o special number field sieve usando 400 computadores ao longo der 11 meses. O número fatorado era de uma forma especial; o special number field sieve não pode ser usado em chaves RSA. O cálculo é aproximadamente equivalente a quebrar uma chave RSA de 700 bits. No entanto, isso pode ser um avanço advertindo que 1024 bits RSA utilizado no comércio on-line seguro deve ser desaprovado, uma vez que eles podem tornar-se frágil num futuro próximo. O Professor de criptografia Arjen Lenstra observou que "Da última vez, levou nove anos para generalizar a partir de um número difícil-de-fatorar especial para um não especial, " e quando perguntado se as chaves RSA de 1024 bits estão mortas, disse: "A resposta a essa pergunta é um sim não-qualificado. "

Ataque de força bruta

Mesmo se uma cifra simétrica for atualmente inquebrável explorando as fraquezas estruturais em seu algoritmo, é possível percorrer todo o espaço de chaves no que é conhecido como um ataque de força bruta. Já que chaves simétricas mais longas requerem exponencialmente mais trabalho para busca de força bruta, uma chave simétrica suficientemente longa torna esta linha de ataque impraticável.

Com uma chave de n bits de comprimento, há 2ⁿ chaves possíveis. Este número cresce muito rapidamente quando n aumenta. O grande número de operações (2¹²⁸) necessárias para tentar todas as chaves de 128 bits possíveis é amplamente considerado fora de alcance para as técnicas de computação digital convencional para o futuro previsível. No entanto, especialistas antecipam tecnologias de computação alternativas que podem ter poder de processamento superior à atual tecnologia de computador. Se um computador quântico de tamanho adequado capaz de rodar o algoritmo de Grover torna-se disponível de forma confiável, reduziria a segurança de uma chave de 128 bits para uma chave de 64 bits, cerca de um equivalente ao DES. Esta é uma das razões pelas quais AES suporta um comprimento de chave de 256 bits. Veja a discussão sobre a relação entre comprimentos de chave e ataques de computação quântica na parte inferior desta página para obter mais informações.

Comprimentos de chaves de algoritmos simétricos

A política de exportação do Governo dos EUA sempre restringiu a 'força' da criptografia que pode ser enviado para fora do país. Por muitos anos o limite foi de 40 bits.  Hoje, um comprimento de chave de 40 bits oferece pouca proteção contra até mesmo um intruso casual com um único PC, uma consequência previsível e inevitável das restrições governamentais que limitam comprimento da chave. Em resposta, até o ano 2000, a maioria das principais restrições dos EUA sobre o uso de criptografia forte foram relaxadas. No entanto, nem todos os regulamentos foram removidos, e registro de criptografia com o U.S. Bureau of Industry and Security ainda é obrigado a exportar "produtos de criptografia de mercado de massa, software e componentes com criptografia superior a 64 bits" (75 FR 36494).

A cifra de Lucifer da IBM foi selecionada em 1974 como a base para o que viria a ser o Data Encryption Standard. O comprimento da chave de Lúcifer foi reduzido de 128-bits para 56 bits, o que a NSA e NIST argumentaram foi suficiente. A NSA tem grandes recursos de computação e um grande orçamento; alguns criptógrafos incluindo Whitfield Diffie e Martin Hellman reclamaram que isso fez a cifra tão fraca que os computadores da NSA seriam capazes de quebrar uma chave DES em um dia através da força bruta de computação paralela. A NSA contestou isso, reivindicando que a força bruta sobre o DES levaria algo como 91 anos.  No entanto, no final dos anos 90, tornou-se claro que o DES pode ser quebrado em um quadro de tempo de alguns dias com um hardware personalizado construído que poderia ser comprado por uma grande empresa ou governo. O livro Cracking DES (O'Reilly and Associates) narra a tentativa bem sucedida de quebrar o DES de 56 bits por um ataque de força bruta montada por um grupo cibernético de direitos civis com recursos limitados veja EFF DES cracker. 56 bits de comprimento é agora considerado insuficiente para algoritmos de chaves  simétricas e pode ter sido por algum tempo. Organizações mais capazes financeiramente e tecnicamente eram certamente capazes de fazer o mesmo muito antes do esforço descrito no livro. Distributed.net e seus voluntários quebrou uma chave RC5 de 64 bits em vários anos, usando cerca de setenta mil (principalmente caseiros) computadores.

O algotirmo da NSA, Skipjack, usado no programa Fortezza utiliza chaves de 80 bits.

DES foi substituído em muitas aplicações pelo Triple DES, que tem 112 bits de segurança com chaves de 128 bits.

O Advanced Encryption Standard, publicado em 2001, usa um tamanho de chave de (no mínimo) de 128 bits. Ele também pode usar chaves de até 256 bits (uma exigência de especificação para inscrições para o concurso AES (AES contest)). Muitos observadores acham realmente que 128 bits é suficiente para o futuro previsível para algoritmos simétricos de qualidade AES. O Governo dos EUA requer 192 ou 256-bit AES chaves para dados altamente confidenciais.

Em 2003,  o Instituto Nacional de Padrões e Tecnologia dos Estados Unidos, NIST (U.S. National Institute for Standards and Technology) propôs a eliminação progressiva de chaves de 80 bits até 2015. A partir de 2005, as chaves de 80 bits foram permitidas apenas até 2010.

Comprimentos de chave de algoritmos assimétricos

A eficácia dos criptossistemas de chave pública depende da intratabilidade (computacional e teórica) de certos problemas matemáticos tais como fatoração de números inteiros. Estes problemas são demorados para resolver, mas geralmente mais rápido do que tentar todas as chaves possíveis pela força bruta. Assim, as chaves de algoritmo assimétrico deve ser mais longo para resistência equivalente ao ataque do que chaves algoritmo simétrico. A partir de 2002, uma chave assimétrica de 1024 bits de comprimento foi geralmente considerada  o mínimo necessário para o algoritmo de encriptação RSA.

A partir de 2003, a RSA Security afirma que as chaves RSA de 1024 bits são equivalentes em força para chaves simétricas 80 bits, chaves RSA de 2048 bits para 112 bits chaves simétricas e chaves RSA 3072 bits para chaves simétricas de 128 bits. A RSA afirma que chaves de 1024 bits são suscetíveis a se tornarem quebráveis em algum momento entre 2006 e 2010 e que as chaves de 2048 bits são suficientes até 2030. Uma chave RSA de  3072 bits de comprimento deveria ser usada se a segurança for necessária para além de 2030. As orientações de gestão chave da NIST sugerem ainda que chaves RSA 15360 bits são equivalentes em força para chaves simétricas de 256 bits.

O algoritmo de Corpos Finitos de Diffie-Hellman tem aproximadamente a mesma força que a chave RSA para os mesmos tamanhos de chave. O fator de trabalho para quebrar Diffie-Hellman é baseado no problema do logaritmo discreto, que está relacionado com o problema da fatoração inteira no qual a força da RSA é baseada. Assim, uma chave Diffie-Hellman 3072-bit tem aproximadamente a mesma força que uma chave RSA de 3072 bits.

Um dos tipos de algoritmos assimétricos, criptografia de curvas elípticas, ou ECC (elliptic curve cryptography), parece ser segura com chaves mais curtas do que outros algoritmos de chaves assimétricas. Orientações NIST indicam que as chaves ECC deve ser duas vezes o comprimento de dosagem equivalente aos algoritmos de chave simétrica. Assim, por exemplo, uma chave de 224 bits ECC teria aproximadamente a mesma resistência que uma chave simétrica de 112 bits. Estas estimativas não assumem grandes avanços na resolução dos problemas matemáticos de base, nos quais está baseada a ECC. Uma mensagem criptografada com um algoritmo de chave elíptica que usa uma chave longa 109 bits foi quebrado pela força bruta.

A NSA especifica que "Criptografia de chave pública de curvas elípticas usando o módulo principal de curva elíptica de 256 bits, conforme especificado no FIPS 186-2 e-SHA-256, é apropriada para proteger informações classificadas até ao nível SECRETO.  O uso do módulo primordial de curva elíptica módulo de 384 bits e SHA-384 é necessária para a protecção da informação TOP SECRET. "

Efeito do ataque de computação quântica sobre a força da chave

Os dois mais conhecidos ataques de computação quântica são baseados no algoritmo de Shor e no algoritmo de Grover. Dos dois, Shor oferece um maior risco aos sistemas de segurança atuais.

Derivados do algoritmo de Shor são amplamente conjecturados como sendo eficazes contra todos os algoritmos de chave pública mais conhecidos, incluindo RSA, Diffie-Hellman e criptografia de curvas elípticas. De acordo com o professor Gilles Brassard, um expert em computação quântica: "O tempo necessário para fatorar um número inteiro RSA é da mesma ordem que o tempo necessário para usar o mesmo número inteiro como módulo para uma única encriptação RSA. Em outras palavras, não leva mais tempo para quebrar RSA em um computador quântico (até para uma constante multiplicativa) que para usar legitimamente em um computador clássico." O consenso geral é que esses algoritmos de chave pública são inseguros em qualquer tamanho da chave se grandes computadores quânticos suficientemente capazes de executar o algoritmo de Shor se tornam disponíveis. A implicação deste ataque é que todos os dados criptografados usando padrões atuais baseada em sistemas de segurança, como o SSL onipresente usado para proteger e-commerce e internet banking e SSH usadas para proteger o acesso a sistemas de computação sensíveis está em risco. Dados criptografados protegidos usando algoritmos de chave pública podem ser arquivados e podem ser quebrados em um momento posterior.

Cifras simétricas tradicionais  (tais como AES or Twofish) e funções hash resistentes à colisões (tais como SHA) são amplamente conjecturadas como oferecendo maior segurança contra ataques conhecidos de computação quântica. Eles são amplamente pensados mais vulneráveis ao algoritmo de Grover. Bennett, Bernstein, Brassard e Vazirani provaram em 1996 que uma busca de chave de força bruta em um computador quântico não pode ser mais rápido do que cerca de 2^n/2 invocações do algoritmo de criptografia subjacente, em comparação com cerca de 2ⁿ no caso clássico. Assim, na presença de grandes computadores quânticos uma chave de n bits pode proporcionar, pelo menos n/2 bits de segurança. Força bruta quântica é facilmente derrotada dobrando o comprimento da chave, que tem pouco custo computacional extra no uso comum. Isto implica que, pelo menos, uma chave simétrica de 160 bits é requerida para alcançar classificação de segurança de 80 bits contra um computador quântico.

Ver também

• Alongamento de chave

Referências

• Recommendation for Key Management — Part 1: general, NIST Special Publication 800-57. March, 2007
• Blaze, Matt; Diffie, Whitfield; Rivest, Ronald L.; et al. "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security". January, 1996
• Arjen K. Lenstra, Eric R. Verheul: Selecting Cryptographic Key Sizes. J. Cryptology 14(4): 255-293 (2001) — Citeseer link

Ligações externas

• www.keylength.com: An online keylength calculator
• Articles discussing the implications of quantum computing
• NIST crypto toolkit
• Burt Kaliski: TWIRL and RSA key sizes (May 2003)
• «Uma calculadora de tamanho de chaves» (em inglês)