Salsa20

Salsa20 é uma cifra de fluxo que foi submetida ao eSTREAM por Daniel J. Bernstein. Ela é construída através de uma função pseudorrandômica baseada na adição de 32-bits, adição bit a bit (XOR) e operações de rotação, que mapeia uma chave de 256 bits, um nonce de 64 bits e uma posição de fluxo de 64 bits em uma saída de 512 bits (existe ainda uma versão de 128 bits). Esse funcionamento dá ao Salsa20 uma vantagem incomum que permite ao usuário realizar buscas de maneira eficiente em qualquer parte do fluxo de saída. Desta forma, ela fornece uma velocidade de cerca de 4-14 ciclos por byte em software em processadores de arquitetura x86 bem como uma razoável performance de hardware. O Salsa20 por sua vez não é patenteado e Bernstein tem escrito diversas implementações de domínio público para as arquiteturas mais comuns.

Estrutura

Internamente, o algoritmo de cifragem utiliza a adição bit a bit (XOR), adição 32-bits mod 2^32 e uma distância constante de operações de rotação em um estado interno de palavras de 32-bits. A escolha destas operações evita a possibilidade de ataques de tempo em implementações de software.

O estado inicial é formado por 8 palavras-chave, sendo estas: 2 palavras de posição de fluxo, 2 palavras de nonce e 4 palavras constantes. Como resultado de 20 rodadas de mistura, são produzidas 16 palavras da saída da cifra de fluxo.

Cada rodada de mistura consiste de 4 operações de quarto-de-rodada, realizadas nas colunas ou nas linhas do estado de 16 palavras, dispostas em uma matriz 4x4. A cada duas rodadas o padrão é repetido. O pseudocódigo para as rodadas é o seguinte: ⊞ é a adição modulo 2^32, <<<< é a operação de rotação à esquerda, ^ é o XOR e x ^= y é abreviação para x = x ^ y.

x[ 4] ^= (x[ 0] ⊞ x[12])<<<7;    x[ 9] ^= (x[ 5] ⊞ x[ 1])<<<7;
x[14] ^= (x[10] ⊞ x[ 6])<<<7;    x[ 3] ^= (x[15] ⊞ x[11])<<<7;
x[ 8] ^= (x[ 4] ⊞ x[ 0])<<<9;    x[13] ^= (x[ 9] ⊞ x[ 5])<<<9;
x[ 2] ^= (x[14] ⊞ x[10])<<<9;    x[ 7] ^= (x[ 3] ⊞ x[15])<<<9;
x[12] ^= (x[ 8] ⊞ x[ 4])<<<13;   x[ 1] ^= (x[13] ⊞ x[ 9])<<<13;
x[ 6] ^= (x[ 2] ⊞ x[14])<<<13;   x[11] ^= (x[ 7] ⊞ x[ 3])<<<13;
x[ 0] ^= (x[12] ⊞ x[ 8])<<<18;   x[ 5] ^= (x[ 1] ⊞ x[13])<<<18;
x[10] ^= (x[ 6] ⊞ x[ 2])<<<18;   x[15] ^= (x[11] ⊞ x[ 7])<<<18;

x[ 1] ^= (x[ 0] ⊞ x[ 3])<<<7;    x[ 6] ^= (x[ 5] ⊞ x[ 3])<<<7;
x[11] ^= (x[10] ⊞ x[ 9])<<<7;    x[12] ^= (x[15] ⊞ x[14])<<<7;
x[ 2] ^= (x[ 1] ⊞ x[ 0])<<<9;    x[ 7] ^= (x[ 6] ⊞ x[ 5])<<<9;
x[ 8] ^= (x[11] ⊞ x[10])<<<9;    x[13] ^= (x[12] ⊞ x[15])<<<9;
x[ 3] ^= (x[ 2] ⊞ x[ 1])<<<13;   x[ 4] ^= (x[ 7] ⊞ x[ 6])<<<13;
x[ 9] ^= (x[ 8] ⊞ x[11])<<<13;   x[14] ^= (x[13] ⊞ x[12])<<<13;
x[ 0] ^= (x[ 3] ⊞ x[ 2])<<<18;   x[ 5] ^= (x[ 4] ⊞ x[ 7])<<<18;
x[10] ^= (x[ 9] ⊞ x[ 8])<<<18;   x[15] ^= (x[14] ⊞ x[13])<<<18;

Estas operações pode ser realizadas de forma bastante eficiente utilizando o conjuntos de instruções SSE2 x86.

O Salsa20 realiza 20 rodadas de mistura em suas entradas. Todavia, já foram introduzidas variantes com 8 e 12 rodadas, são respectivamente o Salsa20/8 e Salsa20/12. Estas variações foram criadas para complementar o Salsa20 (e não para substituí-lo) e obter melhores benchmarks do que o já competitivo Salsa20.

Criptoanálise

Em 2005, Paul Crowley reportou um ataque contra o Salsa20/5 com um tempo de complexidade estimado em 2^165 e ganhou um prêmio de US$1000,00 de Bernstein por ser a "mais interessante criptoanálise realizada no Salsa20". Este e todos os ataques subsequentes ao Salsa20 são baseados em criptoanálise diferencial truncada. Em 2006, Fischer, Meier, Berbain, Biasse, e Robshaw reportaram um ataque no Salsa20/6 com tempo de complexidade estimado em 2^177 e um ataque de chave relacionada no Salsa20/7 com tempo de complexidade estimado em 2^217.

Em 2007, Yukiyasu Tsunoo et. al. anunciaram uma criptoanálise no Salsa20 que "quebra" 8 das 20 rodadas a fim de obter a chave secreta de 256-bits em 2^255 operações usando 2^11.37 pares de chaves de fluxo. No entanto, este ataque não parece ser comparável ao ataque de força bruta.

A partir de 2008, Aumasson, Fischer, Khazaei, Meier, and Rechberge reportaram um ataque cryptoanalítico contra o Salsa20/7 com tempo de complexidade de 2^153 e reportaram o primeiro ataque contra o Salsa20/8 com um tempo de complexidade estimado em 2^251. Este ataque usa de um novo conceito de probabilidade de chaves de bits neutros para a detecção de diferenciais truncados. O ataque pode ser adaptado para "quebrar" o Salsa20 com chave de 128-bits. Não existem ataques publicados contra o Salsa20/12 ou o completo Salsa20/20.

Variante ChaCha

Em 2008, Bernstein publicou a semelhante família de cifras "ChaCha" cujo intuito é aumentar a difusão por rodada e alcançar o mesmo, ou maior desempenho. O artigo publicado por Aumasson e al. também prevê ataques no ChaCha alcançando uma rodada a menos: ChaCha6 com complexidade 2^140 e ChaCha7 com complexidade 2^231.

O ChaCha a primitiva básica de rodada do Salsa20 R(a,b,c,k)

b ⊕= (a ⊞ c) <<< k;

Com a computação modificada, temos:

b ⊞= c;
a ⊕= b;
a <<<= k;

Os valores de rotação também são atualizados. Um quarto round completo torna-se:

a ⊞= b; d ⊕= a; d <<<= 16;
c ⊞= d; b ⊕= c; b <<<= 12;
a ⊞= b; d ⊕= a; d <<<= 8;
c ⊞= d; b ⊕= c; b <<<= 7;

Além de ser mais eficiente em máquinas de 2 instruções (como x86), este atualiza cada palavra duas vezes por quarto de rodada.

O fato de duas das rotações serem múltiplos de 8 permite algumas otimizações. Adicionalmente, a formatação de entrada é rearranjada para suportar uma implementação eficiente de SSE descoberta para o Salsa20. Ao invés de alternar as rodadas das colunas através das linhas, elas são realizadas das colunas junto as diagonais.

ChaCha é a base da função de hash BLAKE, finalista na competição de funções de hash do NIST.