Alongamento de chave

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.

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].

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].

• 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.

• 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).