Ataque de paridade na cifra de bloco
Meu mal-entendido é sobre o ataque de paridade mencionado em "Engenharia de criptografia por Ferguson, Schneier e Kohno".
A maioria das cifras de bloco modernas tem um tamanho de bloco de 128 bits, mas opera em palavras de 32 bits. Eles constroem a função de criptografia a partir de muitas operações de 32 bits. Esse método provou ser muito bem-sucedido, mas tem um efeito colateral. É bastante difícil construir uma permutação estranha a partir de pequenas operações; como resultado, virtualmente todas as cifras de bloco geram apenas permutações pares.
Ainda não entendi até que ponto um ataque de paridade será útil. Por que apenas cifras ideais têm permutações estranhas? Alguém pode formar um exemplo de por que permutações estranhas precisam de mais operações e por que é difícil perceber com o hardware atual sendo capaz de fazer apenas operações de 32 bits?
Eu não fiquei esperto com outro tópico neste fórum exatamente sobre essa questão.
Respostas
Ao lidar com uma cifra de bloco de tamanho de bloco grande, o texto aparece como uma citação na pergunta
A maioria das cifras de bloco modernas tem um tamanho de bloco de 128 bits, mas opera em palavras de 32 bits. Eles constroem a função de criptografia a partir de muitas operações de 32 bits. Esse método provou ser muito bem-sucedido, mas tem um efeito colateral. É bastante difícil construir uma permutação estranha a partir de pequenas operações; como resultado, virtualmente todas as cifras de bloco geram apenas permutações pares.
trata-se de um ataque meramente teórico. O livro é o capítulo 3 reconhece que:
Este ataque não tem nenhum significado prático.
Isso ocorre porque saber a paridade da permutação implementada por uma cifra de bloco ideal com um$b$- o bloco de bits e alguma chave fixa só ajudam os adversários depois de terem obtido $2^b-2$pares de texto simples / texto cifrado: os dois últimos pares de texto simples / texto cifrado são revelados por essa paridade. Antes desse limite, nada acionável vem desse bit de informação.
Por exemplo, com $b=3$, depois que um adversário obteve pares de texto simples / texto cifrado 0/ 1, 1/ 6, 2/ 5, 3/ 0, 4/ 2, 5/ 7, que podemos imaginar como
0 1 2 3 4 5 6 7
1 6 5 0 2 7 ? ?
e se a permutação é conhecida como par, então o adversário pode determinar¹ que os pares restantes são 6/ 3, 7/ 4( em vez de 6/ 4, 7/ 3). Mas antes que o adversário obtido o par 5/ 7, sabendo que a permutação foi mesmo era de nenhuma ajuda a prever se 5mapas para 3, 4ou 7.
Mesmo que uma cifra de bloco de 128 bits seja conhecida por implementar uma permutação uniforme para qualquer chave, isso não é um ponto fraco explorável. Ele permite construir uma distinção teórica de uma cifra ideal, mas somente depois de fazer tantas consultas ($2^{128}-1$) ao oráculo de criptografia ou descriptografia² que não conta como um ataque contra as definições de segurança usuais ou razoáveis.
O texto citado exagera um pouco a dificuldade de construir uma permutação estranha a partir de pequenas operações; veja estes comentários de poncho :
O truque padrão para cifras Feistel de blocos pequenos é usar adição modular, em vez de xor, em cada rodada; dessa forma, a rodada e, portanto, a permutação, tem 0,5 probabilidade de ser ímpar. (...) Se as duas metades do estado Feistel são$a, b$, então a atualização $a\gets a+F(k,b)$pode ser estranho; na verdade, será se um número ímpar de$F(k,b)$ os valores são ímpares (fixos $k$, sobre todos os valores possíveis de $b$)
¹ Prova: ir de 01234567a 16502734pode ser feito com um número par de permutações, por exemplo 01234567→ 10234567→ 16234507→ 16534207→ 16504237→ 16502437→ 16502734.
² O desafiante escolhe aleatoriamente uma cifra aleatória ideal ou até mesmo uma cifra aleatória, o distinguidor tenta adivinhar essa escolha. Precisa$2^{128}-1$consultas para determinar se a cifra é par ou ímpar, se ímpar resulta em 'ideal', caso contrário, emite 'par'. É bem-sucedido com probabilidade$3/4$.