Alongamento de chave

Em criptografia, alongamento de chave (do inglês, key stretching), refere-se às técnicas usadas para fazer chaves inseguras, tipicamente uma senha ou algo semelhante, mais seguras contra contra ataque de força bruta ao aumentar o tempo que leva-se para testar cada possibilidade de chave. Senhas criadas por humanos costumam ser pequenas e previsíveis o suficiente para permitir a quebra de senha (do inglês, password cracking). Alongamento de chave torna este ataque mais difícil.

Alongamento de chave algumas vezes são referenciadas como "fortalecimento de chave (do inglês, key strengthening)", embora este último termo se refira à outra técnica com significantes diferenças nas propriedades de segurança e performance. (Veja sessão 6 do ^[1] para uma comparação).

As técnicas de alongamento de chave geralmente funcionam da seguinte forma: a chave inicial serve de entrada para um algoritmo que tem como saída uma uma chave reforçada. A chave reforçada deverá ter tamanho o suficiente para tornar impossível de ser quebrada através da força bruta (pelo menos 128 bits por exemplo). Este algoritmo em sua forma geral deve ser capaz de ser seguro de maneira que não seja possível descobrir outra maneira de calcular a chave reforçada em menos tempo (menos trabalho de processador) que ele próprio.

O processo de alongamento de chave deixa o ataque com duas opções: ou ele tenta todas as possíveis combinações de chaves reforçadas (o que é impossível se a chave reforçada for grande o suficiente), ou então ele tenta todas as combinações da chave inicial. Neste último caso, se a chave inicial for uma senha, então o atacante poderá tentar usar primeiro o ataque de dicionário, e caso não for bem sucedido, tentar todas as combinações de caracteres para a senha. O alongamento de senha não evita este caso, mas faz o atacante perder muito mais tempo em cada tentativa.

Se o atacante usa a mesma classe de hardware que o usuário, cada tentativa irá tomar o mesmo período de tempo de processo que o usuário ao entrar com sua senha (por exemplo, um segundo). Mesmo se um atacante tiver maiores recursos computacionais que o usuário, o alongamento de chave ainda irá atrasar o atacante, isto porque o usuário apenas computa a função de alongamento de chave uma vez, ao entrar com sua senha, enquanto que o atacante terá que fazer esta computação para cada palpite do seu ataque (de dicionário ou força bruta).

Existem muitas formas de fazer o alongamento de chave. Uma função de hash criptográfica ou um bloco de cifra podem ser repetidamente aplicados em um looping. Em aplicações onde a chave é usada para uma cifragem, o esquema de chaves (do inglês, key schedule ou key set-up) em uma cifra de modo que leve um segundo para ser executada.

Uma técnica relacionada, a adição de sal (criptografia), que protege contra ataques de balanceamento de tempo-memória (do inglês, time-memory tradoff), é usado frequentemente combinado com o alongamento de chave.

Alongamento de chave baseado em hash

Muitas bibliotecas provém funções que executam o alongamento de chave como parte de sua funcionalidade. Veja crypt(3) como exemplo. Note que PBKDF2 é para gerar uma chave de cifragem a partir de uma senha, e não necessariamente uma senha autenticada. PBKDF2 pode ser usada para ambos se o número de bits da saída for menor ou igual ao algoritmo interno de hashing no PBKDF2, que usualmente é o SHA-1 (160 bits), ou é usado como uma chave de cifragem para cifrar dados estáticos.

Resistência e tempo

Para estes exemplos assuma que o mais lento computador pessoal usados atualmente (2011) pode fazer acerca de 65000 SHA-1 hashes em um segundo usando um código compilado. Então um programa que usa alongamento de chaves pode usar 65000 rodadas de hash e o tempo de espera do usuário não passará de muito mais que um segundo.

Testar uma senha tipicamente requer uma operação de hash. Mas se o alongamento de chave é usado, o atacante terá de computar uma chave reforçada para cada chave que que ele testar. Isto significa que são 65000 computações de hash por teste, aproximadamente ${\displaystyle 2^{16}}$, o que significa que uma chave reforçada vale um adicional de 16 bits de resistência na chave (veja entropia da informação).

A comumente aceita Lei de Moore implica que a velocidade dos computadores dobram aproximadamente a cada um ano e meio. Assumindo isto, um bit a mais de resistência na chave é alcançado através da força bruta a cada 1.5 anos. Isto implica que 16 bits extras de resistência vale aproximadamente (16x1.5) 24 anos de atraso na quebra, mas isto também significa que o número de rodadas de alongamentos que um sistema usa deva ser dobrada aproximadamente a cada 1.5 anos para manter o mesmo nível de segurança. (Como a maioria das chaves são mais seguras que o necessário, sistemas que precisam de uma consistência determinística na geração de chaves provavelmente não atualizar o número de iterações usadas no alongamento de chaves. Nestes casos, o designer deve considerar o quão longo deseja-se que o sistema de derivação de chaves permaneça inalterado e escolher um número de hashes apropriado para o tempo de vida útil do sistema).

Funções de hash limitadas pela CPU podem ser vulneráveis a ataques implementados em hardware. Estas implementações de SHA-1 usam apenas 5000 gates e 400 ciclos de clock^[2]. Com FPGAs com vários milhões de gates custando menos de $100^[3], um atacante pode construir um completo hardware de looping desenrolado (do inglês, unrolled) por cerca de $5000. Este design, setado em 100 MHz de clock, pode testar cerca de 300.000 chaves por segundo. O atacante é livre para escolher uma boa relação de preço e custo. Por exemplo, um design de 150.000 chaves por segundo custará $2500. Isto não valerá muita coisa já que o alongamento de chave ainda retardará o atacante mesmo nesta situação; um design de $5000 atacando diretamente um hash SHA-1 a uma taxa de 300.000 chaves por segundo irá apenas produzir chaves reforçadas a uma taxa de (300.000/(${\displaystyle 2^{16}}$)) 4.6 chaves por segundo.

Para defender contra abordagens de hardware, funções criptográficas limitantes pela memóriatambém têm sido propostas. Estes acessos a uma grande quantidade de memória ocorrem de maneira imprevisível, tornando os cachesineficazes. Uma vez que acessar grandes quantidades de memória com uma baixa latência é caro, isto pode dissuadir significantemente um atacante.

Existe uma fraqueza conhecida em algoritmos de alongamento de chave baseadas em hash que usam uma função de hash interativa. Este ataque é conhecido como ataque de estado transferível. O ataque envolve a transferência de estados anteriores dos hashes iterados diretamente para os métodos de transformação da próxima interação. Este ataque pode diminuir o tempo de alongar a chave em 80%-90% do tempo original de alongamento^[4]. Ele foi implementado em SHA256^[5].

História

O primeiro uso deliberado de funções de derivação de chaves lentas aconteceu em "CRYPT", descrito por Robert Morris em 1978 para encriptar senhas do Unix^[6]. Este programa usava 25 iterações, um sal de 12 bits e uma variante de DES como uma sub-função (DES em si foi evitado como uma forma de evitar ataques ao hardware padrão do DES). Senhas foram limitadas ao máximo de oito caracteres ASCII. Enquanto isto era visto como um grande avanço na época, CRYPTO agora é considerado inadequado. A quantidade de iterações, projetados para a era PDP-11, é muito baixa, 12 bits de sal é um inconveniente, mas não para ataques de dicionário, e o limite de 8 caracteres evita o uso senhas mais resistentes.

Funções de derivação de chaves baseadas em senhas modernas, como o PBKDF2, usa hash criptográfico, como MD5 e SHA-1, um sal longo (exemplo: 64 bits) e uma alta quantidade de iterações (geralmente 1000 ou mais).

Em 2008, um algoritmo de fortalecimento de chave de memória intensiva scrypt, foi introduzido com a intenção de limitar o uso de hardwares customizáveis altamente paralelos para aumentar a velocidade de teste da chave^[7][8].

Alguns sistemas que usam alongamento de chave

• Some but not all disk encryption software
• Apache .htpasswd "APR1" and OpenSSL "passwd" use 1000 rounds of MD5 key stretching.
• KeePass e KeePassX, gerenciadores de senha de código aberto.
• Password Safe open-source password manager.
• PGP, GPG encryption software.
• Wi-Fi Protected Access (WPA and WPA2) wireless encryption protocol in personal mode.

Ver também

• Funções de derivação de chave - costuma usar alongamento de chave
• PBKDF2, bcrypt, scrypt - usam largamente algoritmos de alongamento
• Hashcash - Um método relacionado.
• Hash encadeado (do inglês, hashchain).

Referências

1. «Schneier on Security: Low-Entropy Keys». www.schneier.com. Consultado em 9 de agosto de 2015 
2. «events.iaik.tugraz.at/RFIDSec08/Papers/Publication/04%20-%20ONeill%20-%20Low%20Cost%20SHA-1%20-%20Slides.pdf» (PDF) 
3. «New 90nm Xilinx Spartan-3 FPGAs Reshape Semiconductor Landscape (0333) : Xilinx Press Releases». www.xilinx.com. Consultado em 9 de agosto de 2015. Arquivado do original em 16 de julho de 2011 
4. «firebwall.com/research/TransferableStateAttackonIteratedHashingFunctions.pdf» (PDF). Consultado em 9 de agosto de 2015. Arquivado do original (PDF) em 6 de setembro de 2013 
5. «bwall/SafeCracker». GitHub. Consultado em 9 de agosto de 2015 
6. «Computing and Software Principles Research». ect.bell-labs.com. Consultado em 9 de agosto de 2015 
7. «www.tarsnap.com/scrypt/scrypt.pdf» (PDF) 
8. «BSDCan2009: scrypt: A new key derivation function». www.bsdcan.org. Consultado em 9 de agosto de 2015 

Ligações externas

• PHP implementation to get a strong hash from a weak password