Algoritmo de transformação criptográfica de acordo com GOST 28147 89. Padrão de criptografia de dados domésticos

Algoritmo de criptografia GOST 28147-89. Método de substituição simples. - Arquivo WASM.RU

“Enquanto você estiver vivo, não morra, dê uma olhada neste mundo.
Muitos aqui têm uma alma morta - eles estão mortos por dentro.
Mas eles andam e riem, sem saber que não são,
Não apresse a hora da sua morte ”, ela me disse.
Aria, "High Up There"
2.1 Redes Feistel.
2.2 Bloquear cifra GOST 28147-89

3.1 Informação chave
3.2 A principal etapa da transformação criptográfica
3.3 Ciclos básicos:“ 32-Z” , “ 32-R” .

4.1 Implementação da etapa principal da transformação criptográfica
4.2 Aumentando a velocidade do algoritmo
5. Requisitos de informação chave
6. Lista de literatura usada
7. Agradecimentos.

Introdução.

Este documento é minha tentativa de descrever um método para simplesmente substituir o algoritmo de criptografia GOST 28147-89 com a linguagem mais simples, mas, no entanto, tecnicamente competente. Depois de ler os seis primeiros pontos, o leitor dará sua opinião sobre como o fiz.

Para que o meu trabalho seja mais proveitoso, recomendo que se arme com as obras dos autores indicados na lista da literatura utilizada. Também é recomendado que uma calculadora tenha uma função para calcular a operação. XOR Desde a a leitura do artigo pressupõe que o leitor pretendia estudar esse algoritmo de criptografia. Embora também seja adequado como uma referência, escrevi este artigo precisamente como um treinamento.

Informações preliminares sobre cifras de bloco.

Antes de começarmos a examinar o algoritmo, precisamos nos familiarizar com a história da criação desse tipo de cifras. O algoritmo pertence à categoria das cifras de bloco, em que a arquitetura da informação é dividida em um número finito de blocos, sendo que o último naturalmente pode não estar completo. O processo de criptografia ocorre em blocos completos, que formam a cifra. O bloco final, se estiver incompleto, é complementado com algo (direi sobre as nuances de completá-lo abaixo) e é criptografado da mesma forma que os blocos completos. Por cifra, quero dizer o resultado da função de criptografia atuando em uma certa quantidade de dados que o usuário enviou para criptografia. Em outras palavras, uma cifra é o resultado final da criptografia.

A história do desenvolvimento das cifras de bloco está associada ao início dos anos 70, quando a IBM, percebendo a necessidade de proteger a informação na transmissão de dados por canais de comunicação de computador, embarcou em seu próprio programa de pesquisa voltado para a proteção de informação em redes eletrônicas, incluindo criptografia.

Um grupo de pesquisadores - desenvolvedores da IBM, que começou a pesquisar sistemas de criptografia com um esquema de uso de chave simétrica, foi liderado pelo Dr. Horst Feistel.

2.1 Redes Feistel

A arquitetura do novo método de criptografia proposto por Feistel na literatura clássica é chamada de "A Arquitetura Feistel", mas atualmente na literatura Russa e estrangeira é usado um termo mais estabelecido - "Rede de Feistel" ou Rede de Feistel. Posteriormente, a cifra "Lúcifer" foi construída sobre essa arquitetura - que mais tarde foi publicada e causou uma nova onda de interesse na criptografia em geral.

A ideia da arquitetura de "rede Feistel" é a seguinte: o fluxo de entrada de informações é dividido em blocos de n bits de tamanho, onde n é um número par. Cada bloco é dividido em duas partes - L e R, então essas partes são alimentadas em uma cifra de bloco iterativa, na qual o resultado do j-ésimo estágio é determinado pelo resultado do estágio j-1 anterior! Isso pode ser ilustrado por um exemplo:

Arroz. 1

Onde, a função A é a ação principal da cifra de bloco. Pode ser uma ação simples, como uma operação XOR, ou pode ter uma forma mais complexa como uma sequência de uma série de ações simples - adição de módulo, deslocamento para a esquerda, substituição de elemento, etc., tomadas em conjunto, essas ações simples formam o chamado - a etapa principal da transformação de criptografia.

Deve-se notar que os elementos-chave do funcionamento da função são o fornecimento de elementos-chave e a operação XOR, e pelo quão bem pensado o trabalho dessas operações, fala-se da força criptográfica da cifra como um todo.

Para que a ideia de redes Feistel seja finalmente clara, considere o caso mais simples mostrado em arroz. 1, onde na função A - haverá operações “mod 2” (“xor”), mas este mais simples um caso, em uma situação mais grave, por exemplo, ocultando informações de importância nacional, a função A pode ser mais complexa (pelo que vi, a função A é realmente muito complexa):

Dados iniciais:

L = 1110b, R = 0101, K = 1111b

Pegue uma cifra

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

L = 0101b, R = 1010b

Vamos explicar nossas ações:

1. Esta operação é um mod adicional 2 4. Na prática, tal operação é reduzida à simples adição, onde devemos somar dois números e ignorar a transferência para o 5º dígito. Visto que, se colocarmos os expoentes acima dos dígitos da representação binária de um número, haverá um expoente quatro acima do quinto dígito, vamos dar uma olhada na figura abaixo, que mostra as ações de nossa operação:

Arroz. 2

Aqui apontei para os expoentes com uma seta, como você pode ver, o resultado deveria ter sido 10100, mas como a transferência é ignorada durante a operação do mod 2 4, obtemos 0100.

2. Esta operação na literatura é chamada de mod 2, em linguagem assembly é implementada pelo comando XOR... Mas seu nome mais correto é mod 2 1. Sem esta operação única, dificilmente é possível construir um algoritmo de criptografia rápido e facilmente implementável e, ao mesmo tempo, que ainda seja criptograficamente forte. A singularidade dessa operação reside no fato de que ela mesma é o oposto! Por exemplo, se o número A é XORed com o número B, como resultado obteremos B, no futuro é suficiente reXOR os números B e C entre si para obter o valor anterior de A!

Nessa operação, temos 1010 com os números 1110 e 0100, para voltar 1110, basta re-XOR os números 0100 e 1010! Mais detalhes sobre essa operação podem ser encontrados no artigo, que acompanha o site. www.wasm.ru, « Um guia básico paraCRC_ algoritmos de detecção de erros»O autor que Ross N. Williams... Há um ponto neste trabalho - “ 5. Aritmética binária sem hifenização" É neste artigo que a operação é descrita. xor! Exclamo porque neste artigo esta operação está tão programada que o leitor não só compreende como funciona esta operação, como até a inicia. veja, ouça e sinta!

3. Esta ação é necessária para que os valores iniciais possam ser obtidos da criptografia durante a descriptografia.

2.2 Bloquear cifra GOST 28147-89

O algoritmo de criptografia GOST 28147-89 pertence à categoria de cifras de bloco operando de acordo com a arquitetura de redes Feistel balanceadas, onde duas partes do bloco de informações selecionado são de tamanho igual. O algoritmo foi desenvolvido nas profundezas do oitavo departamento da KGB, agora transformado em FAPSI e foi consagrado como o padrão de criptografia da Federação Russa em 1989 sob a URSS.

Para que esse método do algoritmo funcione, é necessário dividir as informações em blocos de 64 bits. Gere ou insira no sistema de criptografia as seguintes informações de chave: chave e tabela de substituição. A escolha da chave e da tabela de substituição para criptografia deve ser levada muito a sério, porque esta é a base da segurança de suas informações. Sobre quais requisitos são impostos à chave e a tabela de substituições, consulte o item “Requisitos para informações da chave”.

Ao considerar o método, não vamos nos concentrar nisso, porque Este artigo, como eu disse acima, foi escrito com o objetivo de ensinar ao leitor como criptografar dados usando o método de substituição simples desse algoritmo de criptografia, mas com certeza iremos tocar nesse assunto no final do artigo.

Mínimo teórico.

3.1 Informações-chave

Como eu disse acima, os seguintes estão ativamente envolvidos na criptografia de dados:

3.1.1. Uma chave é uma sequência de oito elementos de 32 bits cada. A seguir, denotaremos pelo símbolo K, e os elementos que o constituem são k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Tabela de substituição - uma matriz de oito linhas e dezesseis colunas, doravante - Hij. Cada elemento na interseção da linha ie da coluna j ocupa 4 bits.

3.2 Etapa básica da transformação criptográfica

A etapa principal do processo de criptografia é - a etapa principal da transformação de criptografia. Isso nada mais é do que uma ação para criptografar dados de acordo com um determinado algoritmo, apenas os desenvolvedores introduziram o nome muito complicado.

Antes de começar a criptografar, o bloco é dividido em duas partes L e R, de 32 bits cada. O elemento-chave é selecionado e somente então essas duas partes do bloco, o elemento-chave, a tabela de substituição, são alimentados na função da etapa principal, o resultado da etapa principal é uma iteração do ciclo básico, que será discutido em o próximo parágrafo. A etapa principal consiste no seguinte:

A parte adicional do bloco R é somada ao elemento chave K mod 2 32. Descrevi uma operação semelhante acima, aqui a mesma coisa apenas o expoente não é "4", mas "32" - o resultado dessa operação será denotado Smod no futuro.

Divida o resultado Smod obtido anteriormente em elementos de quatro bits s7, s6, s5, s4, s3, s2, s1, s0 e alimente-o para a função de substituição. A substituição é a seguinte: o elemento Smod - si é selecionado, começamos do início com o elemento mais baixo, e substituímos com o valor da tabela de substituições por i - a linha e coluna apontadas pelo valor do elemento s eu. Passamos ao elemento s i +1 e procedemos da mesma maneira e continuamos até alterar o valor do último elemento Smod - o resultado desta operação será denotado como Ssimple.

Nesta operação, deslocamos o valor Ssimple ciclicamente para a esquerda em 11 bits e obtemos Srol.

Selecionamos a segunda parte do bloco L e adicionamos mod 2 com Srol, como resultado temos Sxor.

Nesse estágio, a parte do bloco L passa a ser igual ao valor da parte R, e a parte R, por sua vez, é inicializada com o resultado de Sxor, e com isso a função da etapa principal é concluída!

3.3 Ciclos básicos: "32-З", "32-Р".

Para criptografar as informações, é necessário dividi-las em blocos de 64 bits, é claro que o último bloco pode ter menos de 64 bits. Esse fato é o calcanhar de Aquiles desse método de "substituição fácil". Visto que sua adição a 64 bits é uma tarefa muito importante para aumentar a força criptográfica do código cifrado e para este local sensível, se estiver presente no array de informações, mas pode não existir (por exemplo, um arquivo de 512 bytes! ), Deve-se tratar com grande responsabilidade!

Depois de dividir as informações em blocos, você deve dividir a chave em elementos:

K = k1, k2, k3, k4, k5, k6, k7, k8

A própria criptografia consiste no uso dos chamados ciclos básicos. Que, por sua vez, incluem o enésimo número de etapas básicas da cripto-transformação.

Os ciclos básicos são rotulados, como dizer: n - m. Onde n é o número de etapas básicas da criptotransformação no ciclo de base e m é o "tipo" do ciclo de base, ou seja, do que estamos falando, sobre criptografia "Z" ou criptografia "R" de dados.

O ciclo básico de criptografia 32-З consiste em 32 etapas básicas de cripto-transformação. Um bloco N e um elemento da chave K são alimentados na função que implementa as ações da etapa, e a primeira etapa ocorre com k1, a segunda sobre o resultado obtido com o elemento k2, etc. de acordo com o seguinte esquema:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

O processo de descriptografia para 32-P ocorre de maneira semelhante, mas os elementos-chave são fornecidos na ordem inversa:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Prática.

4.1 Implementação da etapa principal da transformação criptográfica

Depois de nos familiarizarmos com a teoria de como criptografar informações, era hora de ver como a criptografia ocorre na prática.

Dados iniciais:

Pegue um bloco de informação N = 0102030405060708h, aqui as partes L e R são iguais:

L = 01020304h, R = 05060708h, vamos pegar a chave:

K = ‘ as28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(são códigos ASCII, para visualizar a representação hexadecimal, você pode abrir este arquivo no modo de visualização no Total Commander pressionando a tecla F3"E então a chave" 3 "). Nesta chave, os valores dos elementos serão:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Veja também a seguinte tabela de substituição:

Arroz. 3

Aqui, as linhas são numeradas de 0 a 7, as colunas de 0 a F.

Um aviso: Todas as informações, incluindo a chave com a tabela de substituição, são tomadas como exemplo para considerar o algoritmo!

Utilizando os "Dados iniciais", é necessário obter o resultado da ação da etapa principal da transformação criptográfica.

1. Selecione a parte R = 05060708h e o elemento-chave k1 = 'as28', na forma hexadecimal o elemento-chave terá a seguinte aparência: 61733238h. Agora fazemos a operação de soma mod 2 32:

Arroz. 4

Como você pode ver na figura, não tivemos uma transferência em 33 bits marcada em vermelho e com o expoente “ 32 " E se tivéssemos outros valores de R e do elemento-chave, isso poderia muito bem ter acontecido, e então o teríamos ignorado e, posteriormente, usado apenas os bits marcados em amarelo.

Eu realizo esta operação com o comando assembler adicionar:

; eax = R, ebx = 'as28'

O resultado desta operação Smod = 66793940h

2. Agora, a operação mais complicada, mas se você olhar de perto, não é mais tão terrível quanto parece à primeira vista. Vamos imaginar o Smod da seguinte maneira:

Arroz. 5

Tentei visualizar os elementos Smod na figura, mas explicarei de qualquer maneira:

s0 = 0, s1 = 4, s2 = 9, etc.

Agora, começando com o elemento mais baixo s0, fazemos a substituição. Lembrando o parágrafo “ 3.2 Etapa básica da transformação criptográfica»I - linha, s i - coluna, procure o valor na linha zero e coluna zero:

Fig. 6

Portanto, o valor atual de Smod não é 6679394 0 h, e 6679394 5 h.

Prosseguimos para substituir s1, ou seja, quatro. Usando a primeira linha e a quarta coluna (s1 = 4!). Nós olhamos para a foto:

Arroz. 7

Agora já o valor do Smod, não 667939 4 5h, 667939 2 5h Presumo que agora o algoritmo de substituição está claro para o leitor, e posso dizer que após o resultado final do Ssimple terá o seguinte valor - 11e10325h.

Falarei sobre como isso é mais fácil de implementar na forma de comandos assembler posteriormente no próximo parágrafo, depois de falar sobre a tabela estendida.

Devemos deslocar o valor Ssimple resultante 11 bits para a esquerda.

Arroz. oito

Como você pode ver, esta ação é bastante simples e é implementada por um comando da linguagem assembly - rol e o resultado dessa operação Srol é 0819288Fh.

4. Agora, a parte L de nosso bloco de informações deve ser submetida a XOR com o valor Srol. Pego uma calculadora de w2k sp4 e obtenho Sxor = 091b2b8bh.

5. Esta ação é final e nós simplesmente atribuímos, limpamos R, o valor da parte L e inicializamos a parte L com o valor Sxor.

Resultado final:

L = 091b2b8bh, R = 01020304h

4.2 Aumentando a velocidade do algoritmo

Agora vamos falar sobre como otimizar o algoritmo para velocidade. No processo de implementação de um projeto, deve-se levar em conta que um programa que trabalha mais com registros do que com memória funciona mais rápido, e aqui esse julgamento também é muito importante, pois sobre um bloco de informações até 32 ações de criptografia!

Quando implementei o algoritmo de criptografia em meu programa, fiz o seguinte:

1. Parte selecionada do bloco L para o registrador eax, e R para edx.

2. No registro esi, inicializado com o endereço da chave estendida, mais sobre isso a seguir.

3. No registro ebx atribuído o valor do endereço da tabela estendida de substituições, mais sobre isso abaixo

4. Transferiu a informação dos itens 1, 2, 3 para a função do ciclo básico 32 - З ou 32 - Р, dependendo da situação.

Se você olhar o diagrama de fluxo dos elementos-chave no parágrafo " Ciclos básicos: "32-З", "32-Р"", Então nossa chave para o ciclo básico 32 - 3 pode ser representada da seguinte forma:

K 32-Z =

‘As28’, ‘zw37’, ‘q839’, ‘7342’, ‘ui23’, ‘8e2t’, ‘wqm2’, ‘ewp1’,

‘As28’, ‘zw37’, ‘q839’, ‘7342’, ‘ui23’, ‘8e2t’, ‘wqm2’, ‘ewp1’,

‘Ewp1’, ‘wqm2’, ‘8e2t’, ‘ui23’, ‘7342’, ‘q839’, ‘zw37’, ‘as28’

Aqueles. desde o início, existem k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ','zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t ’,‘wqm2 ','ewp1 ' esta sequência é repetida três vezes. Em seguida, os elementos vão na ordem inversa, ou seja: k8, k7, k6, k5, k4, k3, k2, k1 - ‘Ewp1’, ‘wqm2’, ‘8e2t’, ‘ui23’, ‘7342’, ‘q839’, ‘zw37’, ‘as28’.

Organizei os elementos na matriz com antecedência na ordem em que deveriam ser alimentados em 32 - Z. Assim, aumentei a memória necessária em regime turnkey, mas me salvei de alguns processos de pensamento de que não precisava e aumentei a velocidade do algoritmo, pois reduzindo o tempo de acesso à memória! Aqui, descrevi apenas a chave para 32 - З, para o ciclo 32 - Р, fiz o mesmo, mas usando um esquema diferente de fornecimento de elementos, que também descrevi no parágrafo " Ciclos básicos: “32-Z”, “32-P».

Agora é a hora de descrever a implementação da função de substituição, como prometi acima. Não consegui descrever antes, porque isso requer a introdução de um novo conceito - uma tabela de substituição estendida. Eu não posso te explicar o que é. Em vez disso, vou mostrar a você, e você mesmo formula para si mesmo, o que é - uma extensa tabela de substituições?

Portanto, para entender o que é uma tabela de substituição estendida, precisamos de uma tabela de substituição, por exemplo, pegarei aquela mostrada na Fig. 3

Por exemplo, precisávamos substituir o número 66793940h. Vou apresentá-lo da seguinte forma:

Arroz. nove

Agora, se pegarmos os elementos s1, s0, ou seja, byte menos significativo, o resultado da função de substituição será 25h! Depois de ler o artigo de Andrey Vinokurov, que citei no parágrafo " Lista de literatura usada", Você realmente descobre que, se pegar duas linhas, pode obter um array, o que lhe permite encontrar rapidamente os elementos de substituição usando o comando assembler xlat. Eles dizem que é possível de outra forma mais rápida, mas Andrey Vinokurov passou cerca de quatro anos pesquisando algoritmos rápidos para a implementação do GOST! Não acho que você deva reinventar a roda quando você já tem uma.

Então, sobre a matriz:

Vamos pegar as duas primeiras linhas zero e a primeira, criar um array de 256 bytes. Agora observamos uma peculiaridade: se for necessário transformar 00h, o resultado será 75h (com base na Fig. 3) - colocamos esse valor no array no deslocamento 00h. Pegamos o valor 01h, o resultado da função de substituição 79h, colocamos no array no deslocamento 01 e assim por diante até 0FFh, o que nos dará 0FCh, que colocaremos no array no deslocamento 0FFh. Portanto, obtivemos uma tabela de substituição estendida para o primeiro grupo de linhas: a primeira e zero. Mas ainda há três grupos: segunda página 2, página 3, terceira página 4, página 5, quarta página 6, página 7. Lidamos com esses três grupos da mesma maneira que com o primeiro. O resultado é uma tabela de substituição estendida!

Agora podemos implementar um algoritmo que fará a substituição. Para fazer isso, pegamos os códigos-fonte que Andrei Vinokurov postou em sua página, consulte " Bibliografia».

lea ebx, extended_table_simple

mov eax, [coloque o número a ser substituído]

adicione ebx, 100h; pule para os próximos dois nós

sub ebx, 300h; de modo que no futuro ebx aponta para a mesa

Agora, mais um recurso, com as ações anteriores não apenas substituímos, mas também deslocamos o número em 8 bits para a esquerda! Só temos que deslocar o número mais 3 bits para a esquerda:

e obtemos o resultado da operação rol eax, 11!

Não posso acrescentar mais nada sobre otimização, a única coisa que posso enfatizar é o que disse acima - use registradores com mais frequência do que acesso à memória. Acho que essas palavras são apenas para iniciantes, experientes e sem minhas palavras entendem perfeitamente.

Requisitos para informações importantes.

Conforme afirmado no artigo de Andrey Vinokurov, a chave é selecionada de acordo com dois critérios:

O critério para a distribuição equiprovável de bits entre os valores 1 e 0. Normalmente, o critério para a distribuição equiprovável de bits é o critério de Pearson ("qui-quadrado").

Isso significa uma chave, em princípio, qualquer número pode. Ou seja, quando o próximo bit da chave é formado, a probabilidade de sua inicialização por um ou zero é 50/50!

Observe que a chave consiste em oito elementos, cada um com 32 bits, portanto, há apenas 32 * 8 = 256 bits na chave e o número de chaves possíveis é 2 256! Isso não te impressiona?

Critério de série.

Se olharmos para a nossa chave, que dei no parágrafo " 4.1 Implementação da etapa principal da transformação criptográfica», Então você notará que a seguinte notação é válida:

Arroz. dez

Em uma frase, o valor de k 1 não deve ser repetido nem em k 2, nem em qualquer outro elemento da chave.

Ou seja, a chave que escolhemos como a consideração do algoritmo de criptografia atende totalmente aos dois critérios acima.

Agora sobre a escolha da tabela de substituições:

Agora vamos falar sobre como escolher a mesa de substituição certa. O principal requisito para a seleção de tabelas de substituição é o fenômeno de “não repetibilidade” dos elementos, cada um com 4 bits de tamanho. Como você viu acima, cada linha da tabela de substituição consiste nos valores 0h, 1h, 2h, 3h,…, 0fh. Portanto, o principal requisito é que cada linha contenha os valores 0h, 1h, 2h, ..., 0fh e cada um desses valores em uma cópia. Por exemplo, a sequência:

1 2 3 4 5 6 7 8 9 A B C D E F

Ele atende totalmente a esse requisito, mas ainda assim! Não é recomendado selecionar tal sequência como string. Visto que se você alimentar um valor para a entrada de uma função que depende de tal string, você obterá o mesmo valor na saída! Não acredita em mim? Em seguida, pegue o número 332DA43Fh e oito dessas linhas como uma tabela de substituição. Realize a operação de substituição e garanto que a saída será o número 332DA43Fh! Ou seja, o mesmo que você submeteu ao input da operação! E isso não é um sinal de boa forma na criptografia, certo?

Este era um requisito, o próximo critério diz que - cada bit do bloco de saída deve ser estatisticamente independente de cada bit do bloco de entrada!

Como parece mais simples? E aqui está como, por exemplo, escolhemos do número acima o elemento s0 = 0Fh, 01111b. A probabilidade de substituirmos agora o primeiro bit por um ou zero é 0,5! A probabilidade de substituir o segundo, terceiro e quarto bits, cada bit, consideramos separadamente, por uns ou zeros também é 0, 5. Ao escolher s1 = 0Eh, a probabilidade de sermos um bit zero, e este é "0" , será substituído por um zero ou um também igual a - 0,5! Assim, de acordo com este critério, não há regularidade entre a substituição de bits zero dos elementos s0, s1! Sim, você pode substituir uns, mas também pode substituir zeros.

Para avaliar a tabela por este critério, você pode construir uma tabela de coeficientes de correlação calculados pela fórmula:

Se p = 1, então o valor do bit j na saída é igual ao valor do bit i na entrada para quaisquer combinações de bits na entrada;

Se p = -1, então o valor do bit j na saída é sempre o inverso do bit i de entrada;

Se p = 0, então o bit de saída j com igual probabilidade assume os valores 0 e 1 para qualquer valor fixo do bit de entrada i.

Vamos dar um exemplo de linha:

Vamos dividi-lo em "componentes":

Vamos calcular um coeficiente de acordo com a fórmula acima. Para facilitar a compreensão de como isso é feito, explicarei com mais detalhes:

Pegamos o 0º bit do 0º número (0) na entrada e o 0º bit do 0º número na saída (1), realizamos a operação 0 XOR 1 = 1.

Pegamos o 0º bit do 1º número (1) na entrada e o 0º bit do 1º número na saída (1) realizamos a operação 1 XOR 1 = 0.

Pegamos o 0º bit do 2º número (0) na entrada e o 0º bit do 2º número na saída (0) realizamos a operação 0 XOR 0 = 0.

Pegamos o 0º bit do 3º número (1) na entrada e o 0º bit do 3º número na saída (1) realizamos a operação 1 XOR 1 = 0.

Realizando sucessivamente operações XOR nesta sequência, contamos o número de todos os valores diferentes de zero, obtemos o valor 6. Portanto, P 00 = 1- (6/2 4-1) = 0,25. Assim, descobriu-se que o valor do bit 0 na saída é igual ao valor do bit 0 na entrada em 4 casos de 16;

Tabela de probabilidades final:

Como pode ser visto na tabela de coeficientes de correlação, o bit 3 na entrada é invertido em relação ao bit 0 na saída em 14 casos de 16, o que é 87,5% .Isso não é mais aceitável para sistemas de criptografia normais. Vamos dar outro exemplo para uma mudança:

A tabela de coeficientes será a seguinte (para quem não tem preguiça de recalcular)

Bem, nesta tabela, as coisas são ainda piores - os bits 1 e 2 do grupo permanecem inalterados! O criptanalista tem onde se virar Levando em consideração todos esses requisitos, uma busca simples ("frontal") foi encontrada nas tabelas de permutação correspondentes à teoria indicada (hoje - 1276 combinações). Aqui estão algumas delas:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Lista da literatura utilizada.

Artigo de Andrey Vinokurov:

Algoritmo de criptografia GOST 28147-89, seu uso e implementação

para computadores da plataforma Intel x86.

Existem também os códigos-fonte para a implementação do algoritmo de criptografia.

Artigo de Horst Feistel:

Criptografia e segurança informática.

(pode ser encontrado no mesmo endereço do artigo anterior)

Ross N. Williams:

Um guia elementar para algoritmos de detecção de erro CRC
Postado no site www.wasm.ru.

Agradecimentos.

Gostaria de expressar minha gratidão a todos os visitantes do fórum www.wasm.ru. Mas eu gostaria de agradecer especialmente a ChS, que atualmente é conhecido como SteelRat, ele me ajudou a entender coisas que eu provavelmente nunca teria entendido, bem como me ajudou a escrever o parágrafo: “ Requisitos de informação chave”, A parte principal deste parágrafo foi escrita por ele. Também sou profundamente grato ao funcionário do KSTU que recebeu seu nome UM. Tupolev Anikin Igor Vyacheslavovich e seria um pecado não mencionar Chris Kaspersky pelo fato de que ele é e Volodya / wasm.ru por suas instruções. Ah, e eu herdei dele. Também quero observar Sega-Zero / Callipso, mas isso trouxe um pouco de selva matemática à minha mente.

Isso é, talvez, tudo o que eu gostaria de dizer a você.

Eu ficaria muito grato por qualquer crítica ou pergunta relacionada a este artigo ou apenas conselho. Meus detalhes de contato: [email protegido], ICQ - 337310594.

Atenciosamente, Evil`s Interrupt.

P.S .: Com este artigo, não tentei superar ninguém. Foi escrito com a intenção de facilitar o estudo do GOST, e se você tiver dificuldades, isso não significa que eu seja culpado disso. Seja razoável e tenha paciência, tudo de bom para você!

“Enquanto você estiver vivo, não morra, dê uma olhada neste mundo.
Muitos aqui têm uma alma morta - eles estão mortos por dentro.
Mas eles andam e riem, sem saber que não são,
Não apresse a hora da sua morte ”, ela me disse.

Aria, "High Up There"

Introdução

Informações preliminares sobre cifras de bloco

2.1 Redes Feistel.
2.2 Bloquear cifra GOST 28147-89

Mínimo teórico

3.1 Informação chave
3.2 A principal etapa da transformação criptográfica

3.3 Ciclos básicos:“ 32-Z” , “ 32-R” .

Prática

4.1 Implementação da etapa principal da transformação criptográfica
4.2 Aumentando a velocidade do algoritmo
5.
6. Lista de literatura usada
7. Agradecimentos.

Introdução.

Este documento é minha tentativa de descrever um método para simplesmente substituir o algoritmo de criptografia GOST 28147-89 com a linguagem mais simples, mas, no entanto, tecnicamente competente. Depois de ler os seis primeiros pontos, o leitor dará sua opinião sobre como o fiz.

Para que o meu trabalho seja mais proveitoso, recomendo que se arme com as obras dos autores indicados na lista da literatura utilizada. Também é recomendado que uma calculadora tenha uma função para calcular a operação. XOR Desde a a leitura do artigo pressupõe que o leitor pretendia estudar esse algoritmo de criptografia. Embora também seja adequado como uma referência, escrevi este artigo precisamente como um treinamento.

Informações preliminares sobre cifras de bloco.

Antes de começarmos a examinar o algoritmo, precisamos nos familiarizar com a história da criação desse tipo de cifras. O algoritmo pertence à categoria das cifras de bloco, em que a arquitetura da informação é dividida em um número finito de blocos, sendo que o último naturalmente pode não estar completo. O processo de criptografia ocorre em blocos completos, que formam a cifra. O bloco final, se estiver incompleto, é complementado com algo (direi sobre as nuances de completá-lo abaixo) e é criptografado da mesma forma que os blocos completos. Por cifra, quero dizer o resultado da função de criptografia atuando em uma certa quantidade de dados que o usuário enviou para criptografia. Em outras palavras, uma cifra é o resultado final da criptografia.

A história do desenvolvimento das cifras de bloco está associada ao início dos anos 70, quando a IBM, percebendo a necessidade de proteger a informação na transmissão de dados por canais de comunicação de computador, embarcou em seu próprio programa de pesquisa voltado para a proteção de informação em redes eletrônicas, incluindo criptografia.

Um grupo de pesquisadores - desenvolvedores da IBM, que começou a pesquisar sistemas de criptografia com um esquema de uso de chave simétrica, foi liderado pelo Dr. Horst Feistel.

2.1 Redes Feistel

A arquitetura do novo método de criptografia proposto por Feistel na literatura clássica foi denominada “The Feistel Architecture”, mas atualmente na literatura russa e estrangeira é utilizado um termo mais estabelecido - “Feistel's network” ou Feistel`s NetWork. Posteriormente, a cifra "Lúcifer" foi construída sobre essa arquitetura - que mais tarde foi publicada e causou uma nova onda de interesse na criptografia em geral.

A ideia da arquitetura de "rede Feistel" é a seguinte: o fluxo de entrada de informações é dividido em blocos de n bits de tamanho, onde n é um número par. Cada bloco é dividido em duas partes - L e R, então essas partes são alimentadas em uma cifra de bloco iterativa, na qual o resultado do j-ésimo estágio é determinado pelo resultado do estágio j-1 anterior! Isso pode ser ilustrado por um exemplo:

Arroz. 1

Onde, a função A é a ação principal da cifra de bloco. Pode ser uma ação simples, como uma operação XOR, ou pode ter uma forma mais complexa como uma sequência de uma série de ações simples - adição de módulo, deslocamento para a esquerda, substituição de elemento, etc., tomadas em conjunto, essas ações simples formam o chamado - a etapa principal da transformação de criptografia.

Deve-se notar que os elementos-chave do funcionamento da função são o fornecimento de elementos-chave e a operação XOR, e pelo quão bem pensado o trabalho dessas operações, fala-se da força criptográfica da cifra como um todo.

Para que a ideia de redes Feistel seja finalmente clara, considere o caso mais simples mostrado em arroz. 1, onde na função A - haverá operações “mod 2” (“xor”), mas este mais simples um caso, em uma situação mais grave, por exemplo, ocultando informações de importância nacional, a função A pode ser mais complexa (pelo que vi, a função A é realmente muito complexa):

Dados iniciais:

L = 1110b, R = 0101, K = 1111b

Pegue uma cifra

(R + K) mod 2 4 = Smod, Smod = 0100b
(Smod + L) mod 2 = Sxor, Sxor = 1010b
L = R, R = Sxor

L = 0101b, R = 1010b

Vamos explicar nossas ações:

Esta operação é mod 2 4 adição. Na prática, tal operação é reduzida à simples adição, onde devemos somar dois números e ignorar a transferência para o 5º dígito. Visto que, se colocarmos os expoentes acima dos dígitos da representação binária de um número, haverá um expoente quatro acima do quinto dígito, vamos dar uma olhada na figura abaixo, que mostra as ações de nossa operação:

Arroz. 2

Aqui apontei para os expoentes com uma seta, como você pode ver, o resultado deveria ter sido 10100, mas como a transferência é ignorada durante a operação do mod 2 4, obtemos 0100.

Esta operação na literatura é chamada de mod 2, em assembly é implementada pelo comando XOR... Mas seu nome mais correto é mod 2 1. Sem esta operação única, dificilmente é possível construir um algoritmo de criptografia rápido e facilmente implementável e, ao mesmo tempo, que ainda seja criptograficamente forte. A singularidade dessa operação reside no fato de que ela mesma é o oposto! Por exemplo, se o número A é XORed com o número B, como resultado obteremos B, no futuro é suficiente reXOR os números B e C entre si para obter o valor anterior de A!

Nessa operação, temos 1010 com os números 1110 e 0100, para voltar 1110, basta re-XOR os números 0100 e 1010! Mais detalhes sobre essa operação podem ser encontrados no artigo, que acompanha o site. www.wasm.ru, « Um guia básico paraCRC_ algoritmos de detecção de erros»O autor que Ross N. Williams... Há um ponto neste trabalho - “ 5. Aritmética binária sem hifenização" É neste artigo que a operação é descrita. xor! Exclamo porque neste artigo esta operação está tão programada que o leitor não só compreende como funciona esta operação, como até a inicia. veja, ouça e sinta!

Esta ação é necessária para que durante a descriptografia, os valores iniciais possam ser obtidos da cifra.

2.2 Bloquear cifra GOST 28147-89

O algoritmo de criptografia GOST 28147-89 pertence à categoria de cifras de bloco operando de acordo com a arquitetura de redes Feistel balanceadas, onde duas partes do bloco de informações selecionado são de tamanho igual. O algoritmo foi desenvolvido nas profundezas do oitavo departamento da KGB, agora transformado em FAPSI e foi consagrado como o padrão de criptografia da Federação Russa em 1989 sob a URSS.

Para que esse método do algoritmo funcione, é necessário dividir as informações em blocos de 64 bits. Gere ou insira no sistema de criptografia as seguintes informações de chave: chave e tabela de substituição. A escolha da chave e da tabela de substituição para criptografia deve ser levada muito a sério, porque esta é a base da segurança de suas informações. Sobre quais requisitos são impostos à chave e a tabela de substituições, consulte o item “Requisitos para informações da chave”.

Ao considerar o método, não vamos nos concentrar nisso, porque Este artigo, como eu disse acima, foi escrito com o objetivo de ensinar ao leitor como criptografar dados usando o método de substituição simples desse algoritmo de criptografia, mas com certeza iremos tocar nesse assunto no final do artigo.

Mínimo teórico.

3.1 Informações-chave

Como eu disse acima, os seguintes estão ativamente envolvidos na criptografia de dados:

3.1.1. Uma chave é uma sequência de oito elementos de 32 bits cada. A seguir, denotaremos pelo símbolo K, e os elementos que o constituem são k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Tabela de substituição - uma matriz de oito linhas e dezesseis colunas, doravante - Hij. Cada elemento na interseção da linha ie da coluna j ocupa 4 bits.

A etapa principal do processo de criptografia é - a etapa principal da transformação de criptografia. Isso nada mais é do que uma ação para criptografar dados de acordo com um determinado algoritmo, apenas os desenvolvedores introduziram o nome que era muito complicado :).

Antes de começar a criptografar, o bloco é dividido em duas partes L e R, de 32 bits cada. O elemento-chave é selecionado e somente então essas duas partes do bloco, o elemento-chave, a tabela de substituição, são alimentados na função da etapa principal, o resultado da etapa principal é uma iteração do ciclo básico, que será discutido em o próximo parágrafo. A etapa principal consiste no seguinte:

A parte adicional do bloco R é somada ao elemento chave K mod 2 32. Descrevi uma operação semelhante acima, aqui a mesma coisa apenas o expoente não é "4", mas "32" - o resultado dessa operação será denotado Smod no futuro.
Divida o resultado Smod obtido anteriormente em elementos de quatro bits s7, s6, s5, s4, s3, s2, s1, s0 e alimente-o para a função de substituição. A substituição é a seguinte: o elemento Smod - si é selecionado, desde o início começamos com o elemento mais baixo, e substituímos com o valor da tabela de substituições por i - a linha e coluna apontadas pelo valor do elemento s i. Passamos ao elemento s i +1 e procedemos da mesma maneira e continuamos até alterar o valor do último elemento Smod - o resultado desta operação será denotado como Ssimple.
Nesta operação, deslocamos o valor Ssimple ciclicamente para a esquerda em 11 bits e obtemos Srol.
Selecionamos a segunda parte do bloco L e adicionamos mod 2 com Srol, como resultado temos Sxor.
Neste estágio, a parte do bloco L torna-se igual ao valor da parte R, e a parte R, por sua vez, é inicializada com o resultado Sxor, e com isso a função da etapa principal é concluída!

3.3 Ciclos básicos: "32-З", "32-Р".

Para criptografar as informações, é necessário dividi-las em blocos de 64 bits, é claro que o último bloco pode ter menos de 64 bits. Esse fato é o calcanhar de Aquiles desse método de "substituição fácil". Visto que sua adição a 64 bits é uma tarefa muito importante para aumentar a força criptográfica do código cifrado e para este local sensível, se estiver presente no array de informações, mas pode não existir (por exemplo, um arquivo de 512 bytes! ), Deve-se tratar com grande responsabilidade!

Depois de dividir as informações em blocos, você deve dividir a chave em elementos:

K = k1, k2, k3, k4, k5, k6, k7, k8

A própria criptografia consiste no uso dos chamados ciclos básicos. Que, por sua vez, incluem o enésimo número de etapas básicas da cripto-transformação.

Os ciclos básicos são rotulados, como dizer: n - m. Onde n é o número de etapas básicas da criptotransformação no ciclo de base e m é o "tipo" do ciclo de base, ou seja, do que estamos falando, sobre criptografia "Z" ou criptografia "R" de dados.

O ciclo básico de criptografia 32-З consiste em 32 etapas básicas de cripto-transformação. Um bloco N e um elemento da chave K são alimentados na função que implementa as ações da etapa, e a primeira etapa ocorre com k1, a segunda sobre o resultado obtido com o elemento k2, etc. de acordo com o seguinte esquema:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

O processo de descriptografia para 32-P ocorre de maneira semelhante, mas os elementos-chave são fornecidos na ordem inversa:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Prática.

Depois de nos familiarizarmos com a teoria de como criptografar informações, era hora de ver como a criptografia ocorre na prática.

Dados iniciais:

Pegue um bloco de informação N = 0102030405060708h, aqui as partes L e R são iguais:

L = 01020304h, R = 05060708h, vamos pegar a chave:

K = ‘ as28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(são códigos ASCII, para visualizar a representação hexadecimal, você pode abrir este arquivo no modo de visualização no Total Commander pressionando a tecla F3"E então a chave" 3 "). Nesta chave, os valores dos elementos serão:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Veja também a seguinte tabela de substituição:

Arroz. 3

Aqui, as linhas são numeradas de 0 a 7, as colunas de 0 a F.

Um aviso: Todas as informações, incluindo a chave com a tabela de substituição, são tomadas como exemplo para considerar o algoritmo!

Utilizando os "Dados iniciais", é necessário obter o resultado da ação da etapa principal da transformação criptográfica.

Selecionamos a parte R = 05060708h e o elemento-chave k1 = 'as28', na forma hexadecimal o elemento-chave terá a seguinte aparência: 61733238h. Agora fazemos a operação de soma mod 2 32:

Arroz. 4

Como você pode ver na figura, não tivemos uma transferência em 33 bits marcada em vermelho e com o expoente “ 32 " E se tivéssemos outros valores de R e do elemento-chave, isso poderia muito bem ter acontecido, e então o teríamos ignorado e, posteriormente, usado apenas os bits marcados em amarelo.

Eu realizo esta operação com o comando assembler adicionar:

; eax = R, ebx = 'as28'

O resultado desta operação Smod = 66793940h

Agora, a operação mais complicada, mas se você olhar de perto, não é mais tão terrível quanto parece à primeira vista. Vamos imaginar o Smod da seguinte maneira:

FIGURA NÃO SALVA

Arroz. 5

Tentei visualizar os elementos Smod na figura, mas explicarei de qualquer maneira:

s0 = 0, s1 = 4, s2 = 9, etc.

Agora, começando com o elemento mais baixo s0, fazemos a substituição. Lembrando o parágrafo “ 3.2 Etapa básica da transformação criptográfica»I - linha, s i - coluna, procure o valor na linha zero e coluna zero:

Fig. 6

Portanto, o valor atual de Smod não é 6679394 0 h, e 6679394 5 h.

Prosseguimos para substituir s1, ou seja, quatro. Usando a primeira linha e a quarta coluna (s1 = 4!). Nós olhamos para a foto:

Arroz. 7

Agora já o valor do Smod, não 667939 4 5h, 667939 2 5h Presumo que agora o algoritmo de substituição está claro para o leitor, e posso dizer que após o resultado final do Ssimple terá o seguinte valor - 11e10325h.

Falarei sobre como isso é mais fácil de implementar na forma de comandos assembler posteriormente no próximo parágrafo, depois de falar sobre a tabela estendida.

Devemos deslocar o valor Ssimple resultante 11 bits para a esquerda.

Arroz. oito

Como você pode ver, esta ação é bastante simples e é implementada por um comando da linguagem assembly - rol e o resultado dessa operação Srol é 0819288Fh.

Agora, continua sendo a parte L de nosso bloco de informações a ser XORed com o valor Srol. Pego uma calculadora de w2k sp4 e obtenho Sxor = 091b2b8bh.
Esta ação é final e simplesmente atribuímos, limpamos R, o valor da parte L e inicializamos a parte L com o valor Sxor.

Resultado final:

L = 091b2b8bh, R = 01020304h

4.2 Aumentando a velocidade do algoritmo

Agora vamos falar sobre como otimizar o algoritmo para velocidade. No processo de implementação de um projeto, deve-se levar em conta que um programa que trabalha mais com registros do que com memória funciona mais rápido, e aqui esse julgamento também é muito importante, pois sobre um bloco de informações até 32 ações de criptografia!

Quando implementei o algoritmo de criptografia em meu programa, fiz o seguinte:

Parte selecionada do bloco L para o registrador eax, e R para edx.
No registro esi, inicializado com o endereço da chave estendida, mais sobre isso a seguir.
No registro ebx atribuiu-se o valor do endereço da tabela estendida de substituições, mais sobre isso abaixo
Transferiu a informação dos itens 1, 2, 3 para a função do ciclo básico 32 - З ou 32 - Р, dependendo da situação.

Se você olhar o diagrama de fluxo dos elementos-chave no parágrafo " Ciclos básicos: "32-З", "32-Р"", Então nossa chave para o ciclo básico 32 - 3 pode ser representada da seguinte forma:

K 32-Z =

‘As28’, ‘zw37’, ‘q839’, ‘7342’, ‘ui23’, ‘8e2t’, ‘wqm2’, ‘ewp1’,

‘Ewp1’, ‘wqm2’, ‘8e2t’, ‘ui23’, ‘7342’, ‘q839’, ‘zw37’, ‘as28’

Aqueles. desde o início, existem k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ','zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t ’,‘wqm2 ','ewp1 ' esta sequência é repetida três vezes. Em seguida, os elementos vão na ordem inversa, ou seja: k8, k7, k6, k5, k4, k3, k2, k1 - ‘Ewp1’, ‘wqm2’, ‘8e2t’, ‘ui23’, ‘7342’, ‘q839’, ‘zw37’, ‘as28’.

Organizei os elementos na matriz com antecedência na ordem em que deveriam ser alimentados em 32 - Z. Assim, aumentei a memória necessária em regime turnkey, mas me salvei de alguns processos de pensamento de que não precisava e aumentei a velocidade do algoritmo, pois reduzindo o tempo de acesso à memória! Aqui, descrevi apenas a chave para 32 - З, para o ciclo 32 - Р, fiz o mesmo, mas usando um esquema diferente de fornecimento de elementos, que também descrevi no parágrafo " Ciclos básicos: “32-Z”, “32-P».

Agora é a hora de descrever a implementação da função de substituição, como prometi acima. Não consegui descrever antes, porque isso requer a introdução de um novo conceito - uma tabela de substituição estendida. Eu não posso te explicar o que é. Em vez disso, vou mostrar a você, e você mesmo formula para si mesmo, o que é - uma extensa tabela de substituições?

Portanto, para entender o que é uma tabela de substituição estendida, precisamos de uma tabela de substituição, por exemplo, pegarei aquela mostrada na Fig. 3

Por exemplo, precisávamos substituir o número 66793940h. Vou apresentá-lo da seguinte forma:

FIGURA NÃO SALVA

Arroz. nove

Agora, se pegarmos os elementos s1, s0, ou seja, byte menos significativo, o resultado da função de substituição será 25h! Depois de ler o artigo de Andrey Vinokurov, que citei no parágrafo " Lista de literatura usada", Você realmente descobre que, se pegar duas linhas, pode obter um array, o que lhe permite encontrar rapidamente os elementos de substituição usando o comando assembler xlat. Eles dizem que é possível de outra forma mais rápida, mas Andrey Vinokurov passou cerca de quatro anos pesquisando algoritmos rápidos para a implementação do GOST! Não acho que você deva reinventar a roda quando você já tem uma.

Então, sobre a matriz:

Vamos pegar as duas primeiras linhas zero e a primeira, criar um array de 256 bytes. Agora observamos uma peculiaridade: se for necessário transformar 00h, o resultado será 75h (com base na Fig. 3) - colocamos esse valor no array no deslocamento 00h. Pegamos o valor 01h, o resultado da função de substituição 79h, colocamos no array no deslocamento 01 e assim por diante até 0FFh, o que nos dará 0FCh, que colocaremos no array no deslocamento 0FFh. Portanto, obtivemos uma tabela de substituição estendida para o primeiro grupo de linhas: a primeira e zero. Mas ainda há três grupos: segunda página 2, página 3, terceira página 4, página 5, quarta página 6, página 7. Lidamos com esses três grupos da mesma maneira que com o primeiro. O resultado é uma tabela de substituição estendida!

Agora podemos implementar um algoritmo que fará a substituição. Para fazer isso, pegamos os códigos-fonte que Andrei Vinokurov postou em sua página, consulte " Bibliografia».

lea ebx, extended_table_simple

mov eax, [coloque o número a ser substituído]

adicione ebx, 100h; pule para os próximos dois nós

sub ebx, 300h; de modo que no futuro ebx aponta para a mesa

Agora, mais um recurso, com as ações anteriores não apenas substituímos, mas também deslocamos o número em 8 bits para a esquerda! Só temos que deslocar o número mais 3 bits para a esquerda:

e obtemos o resultado da operação rol eax, 11!

Não posso acrescentar mais nada sobre otimização, a única coisa que posso enfatizar é o que disse acima - use registradores com mais frequência do que acesso à memória. Acho que essas palavras são apenas para iniciantes, experientes e sem as minhas palavras entendem isso perfeitamente :).

Requisitos para informações importantes.

Conforme afirmado no artigo de Andrey Vinokurov, a chave é selecionada de acordo com dois critérios:

- um critério para distribuição equiprovável de bits entre os valores 1 e 0. Normalmente, o critério para distribuição equiprovável de bits é o critério de Pearson ("qui-quadrado").

Isso significa uma chave, em princípio, qualquer número pode. Ou seja, quando o próximo bit da chave é formado, a probabilidade de sua inicialização por um ou zero é 50/50!

Observe que a chave consiste em oito elementos, cada um com 32 bits, portanto, há apenas 32 * 8 = 256 bits na chave e o número de chaves possíveis é 2 256! Isso não te impressiona? 🙂

- critério de série.

Se olharmos para a nossa chave, que dei no parágrafo " 4.1 Implementação da etapa principal da transformação criptográfica», Então você notará que a seguinte notação é válida:

Arroz. dez

Em uma frase, o valor de k 1 não deve ser repetido nem em k 2, nem em qualquer outro elemento da chave.

Ou seja, a chave que escolhemos como a consideração do algoritmo de criptografia atende totalmente aos dois critérios acima.

Agora sobre a escolha da tabela de substituições:

Agora vamos falar sobre como escolher a mesa de substituição certa. O principal requisito para a seleção de tabelas de substituição é o fenômeno de “não repetibilidade” dos elementos, cada um com 4 bits de tamanho. Como você viu acima, cada linha da tabela de substituição consiste nos valores 0h, 1h, 2h, 3h,…, 0fh. Portanto, o principal requisito é que cada linha contenha os valores 0h, 1h, 2h, ..., 0fh e cada um desses valores em uma cópia. Por exemplo, a sequência:

1 2 3 4 5 6 7 8 9 A B C D E F

Ele atende totalmente a esse requisito, mas ainda assim! Não é recomendado selecionar tal sequência como string. Visto que se você alimentar um valor para a entrada de uma função que depende de tal string, você obterá o mesmo valor na saída! Não acredita em mim? Em seguida, pegue o número 332DA43Fh e oito dessas linhas como uma tabela de substituição. Realize a operação de substituição e garanto que a saída será o número 332DA43Fh! Ou seja, o mesmo que você submeteu ao input da operação! E isso não é um sinal de boa forma na criptografia, certo? 🙂

Este era um requisito, o próximo critério diz que - cada bit do bloco de saída deve ser estatisticamente independente de cada bit do bloco de entrada!

Como parece mais simples? E aqui está como, por exemplo, escolhemos do número acima o elemento s0 = 0Fh, 01111b. A probabilidade de substituirmos agora o primeiro bit por um ou zero é 0,5! A probabilidade de substituir o segundo, terceiro e quarto bits, cada bit, consideramos separadamente, por uns ou zeros também é 0, 5. Ao escolher s1 = 0Eh, a probabilidade de sermos um bit zero, e este é "0" , será substituído por um zero ou um também igual a - 0,5! Assim, de acordo com este critério, não há regularidade entre a substituição de bits zero dos elementos s0, s1! Sim, você pode substituir uns, mas também pode substituir zeros. 🙂

Para avaliar a tabela por este critério, você pode construir uma tabela de coeficientes de correlação calculados pela fórmula:

- se p = 1, então o valor do bit j na saída é igual ao valor do bit i na entrada para quaisquer combinações de bits na entrada;

- se p = -1, então o valor do bit j na saída é sempre o inverso do bit i de entrada;

- se p = 0, então o bit de saída j com igual probabilidade assume os valores 0 e 1 para qualquer valor fixo do bit de entrada i.

Vamos dar um exemplo de linha:

D	B	4	1	3	F	5	9	0	UMA	E	7	6	8	2	C

Vamos dividi-lo em "componentes":

Vamos calcular um coeficiente de acordo com a fórmula acima. Para facilitar a compreensão de como isso é feito, explicarei com mais detalhes:

- tomamos o 0º bit do 0º número (0) na entrada e o 0º bit do 0º número na saída (1) realizamos a operação 0 XOR 1 = 1.

- tomamos o 0º bit do 1º número (1) na entrada e o 0º bit do 1º número na saída (1) realizamos a operação 1 XOR 1 = 0.

- tomamos o 0º bit do 2º número (0) na entrada e o 0º bit do 2º número na saída (0) realizamos a operação 0 XOR 0 = 0.

- tomamos o 0º bit do 3º número (1) na entrada e o 0º bit do 3º número na saída (1) realizamos a operação 1 XOR 1 = 0.

Realizando sucessivamente operações XOR nesta sequência, contamos o número de todos os valores diferentes de zero, obtemos o valor 6. Portanto, P 00 = 1- (6/2 4-1) = 0,25. Assim, descobriu-se que o valor do bit 0 na saída é igual ao valor do bit 0 na entrada em 4 casos de 16;

Tabela de probabilidades final:

A tabela de coeficientes será a seguinte (para quem não tem preguiça de recalcular)

	Entrada
Saída		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Bem, nesta tabela, as coisas são ainda piores - os bits 1 e 2 do grupo permanecem inalterados! O criptanalista tem a quem recorrer 🙂 Levando em consideração todos esses requisitos, uma simples pesquisa ("frontal") encontrou tabelas de permutação correspondentes à teoria indicada (hoje - 1276 combinações). Aqui estão algumas delas:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Lista da literatura utilizada.

Artigo de Andrey Vinokurov:

Algoritmo de criptografia GOST 28147-89, seu uso e implementação

para computadores da plataforma Intel x86.

(pode ser encontrado em: http://www.enlight.ru/crypto/frame.htm).

Existem também os códigos-fonte para a implementação do algoritmo de criptografia.

Artigo de Horst Feistel:

Criptografia e segurança informática.

(pode ser encontrado no mesmo endereço do artigo anterior)

Ross N. Williams:

Um guia elementar para algoritmos de detecção de erro CRC

Postado no site www.wasm.ru.

Agradecimentos.

Gostaria de expressar minha gratidão a todos os visitantes do fórum www.wasm.ru. Mas eu gostaria de agradecer especialmente a ChS, que atualmente é conhecido como SteelRat, ele me ajudou a entender coisas que eu provavelmente nunca teria entendido, bem como me ajudou a escrever o parágrafo: “ Requisitos de informação chave”, A parte principal deste parágrafo foi escrita por ele. Também sou profundamente grato ao funcionário do KSTU que recebeu seu nome UM. Tupolev Anikin Igor Vyacheslavovich e seria um pecado não mencionar Chris Kaspersky pelo fato de que ele é e Volodya / wasm.ru por suas instruções. Ah, e eu herdei dele :). Também quero observar Sega-Zero / Callipso, mas isso trouxe um pouco de selva matemática à minha mente.

Isso é, talvez, tudo o que eu gostaria de dizer a você.

Eu ficaria muito grato por qualquer crítica ou pergunta relacionada a este artigo ou apenas conselho. Meus detalhes de contato: [email protegido], ICQ - 337310594.

Atenciosamente, Evil`s Interrupt.

P.S .: Com este artigo, não tentei superar ninguém. Foi escrito com a intenção de facilitar o estudo do GOST, e se você tiver dificuldades, isso não significa que eu seja culpado disso. Seja razoável e tenha paciência, tudo de bom para você!

Este algoritmo é obrigatório para uso como algoritmo de criptografia em organizações governamentais da Federação Russa e em várias organizações comerciais.

Descrição do algoritmo

O diagrama do algoritmo é mostrado na Fig. 3.1. Como você pode ver, o esquema desse algoritmo é bastante simples, o que simplifica de forma inequívoca sua implementação de software ou hardware.

O algoritmo GOST 28147-89 criptografa as informações em blocos de 64 bits, que são divididos em dois sub-blocos de 32 bits (N1 e N2). O sub-bloco N1 é processado de uma determinada maneira, após a qual seu valor é adicionado

com o valor do sub-bloco N2 (a adição é realizada no módulo 2), então os sub-blocos são trocados. Essa transformação é realizada por um determinado número de rodadas: 16 ou 32, dependendo do modo de operação do algoritmo (descrito abaixo). Em cada rodada, as seguintes operações são realizadas:

1. Sobreposição de chave. O conteúdo do sub-bloco / VI é adicionado módulo 2 32 com parte da tecla Kx.

A chave de criptografia do algoritmo GOST 28147-89 tem uma dimensão de 256 bits, e Kx é sua parte de 32 bits, ou seja, a chave de criptografia de 256 bits é representada como uma concatenação de subchaves de 32 bits (Fig. 3.2) :

SH ATI, AG2, YU, AG4, K5, KB, K7.

No processo de criptografia, uma dessas subchaves é usada, dependendo do número da rodada e do modo de operação do algoritmo.

Arroz. 3.1. Esquema de algoritmo GOST 28147-

Arroz. 3.2. Chave de criptografia de algoritmo GOST 28147-89

2. Substituição tabular. Após a imposição da chave, o sub-bloco / VI é dividido em 8 partes de 4 bits, sendo o valor de cada um deles substituído individualmente de acordo com a tabela de substituição para esta parte do sub-bloco. As caixas de substituição (S-boxes) são frequentemente usadas em algoritmos de criptografia modernos, portanto, vale a pena considerá-las com mais detalhes.

A substituição tabular é usada desta forma: um bloco de dados de uma certa dimensão (neste caso, 4 bits) é alimentado à entrada, cuja representação numérica determina o número do valor de saída. Por exemplo, temos uma S-box com o seguinte formato:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Deixe um bloco de 4 bits "0100" entrar na entrada, ou seja, o valor 4. Conforme a tabela, o valor da saída será 15, ou seja. "1111" (0 é substituído por 4, 1 é substituído por 11, o valor de 2 não muda, etc.).

Como você pode ver, o esquema do algoritmo é muito simples, o que significa que a maior carga de criptografia de dados recai sobre as tabelas de substituição. Infelizmente, o algoritmo tem a propriedade de existirem tabelas de substituição “fracas”, em que o algoritmo pode ser divulgado por métodos criptanalíticos. Os fracos incluem, por exemplo, uma tabela em que a saída é igual à entrada:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Deslocamento à esquerda cíclico bit a bit em 11 bits.

Modos de operação do algoritmo

O algoritmo GOST 28147-89 tem 4 modos de operação:

□ modo de substituição simples;

□ modo gama;

Modo P gama com feedback;

□ modo de produção de simuladores.

Esses modos são um pouco diferentes dos geralmente aceitos (descritos na Seção 1.4), portanto, vale a pena considerá-los com mais detalhes.

Esses modos têm finalidades diferentes, mas usam a mesma transformação de criptografia descrita acima.

Modo de substituição fácil

No modo de substituição simples, as 32 rodadas descritas acima são executadas simplesmente para criptografar cada bloco de informações de 64 bits. As subchaves de 32 bits são usadas na seguinte sequência:

□ KO, Kl, K2, KZ, K4, K5, Kb, AG7, KO, ATI, etc. - nas rodadas 1 a 24;

□ K1, Kb, K5, K4, KZ, K2, K \, KO - em rodadas do 25º ao 32º.

A descriptografia no modo de substituição simples é realizada exatamente da mesma maneira, mas com uma sequência ligeiramente diferente de subchaves:

□ KO, K \, K2, KZ, K4, K5, Kb, KP - em rodadas de 1 a 8;

□ KP, Kb, K5, K4, KZ, K2, K \, KO, K1, Kb, etc. - em rodadas de 9 a 32.

Semelhante ao modo ECB padrão, devido à criptografia separada dos blocos, o modo de substituição simples é fortemente desencorajado para criptografar os próprios dados; ele só deve ser usado para criptografar outras chaves de criptografia em esquemas de várias chaves.

Modo gama

No modo gama (Fig. 3.3), cada bloco de texto simples é adicionado bit a bit ao módulo 2 com um bloco gama cifrado de 64 bits. O gama de uma cifra é uma sequência especial gerada usando as transformações descritas acima, da seguinte maneira:

1. Nos registros N1 e N2 seu preenchimento inicial é escrito - um valor de 64 bits, denominado "synchro-burst" (synchro-burst, na prática, é um análogo do vetor de inicialização nos modos CBC, CFB e OFB).

2. A criptografia do conteúdo dos registros / VI e N2 (neste caso - mensagens de sincronização) é realizada no modo de substituição simples.

3. O conteúdo de N1 é adicionado módulo (2 32 - 1) com a constante CI = 2 24 + 2 16 + 2 8 + 4, o resultado da adição é escrito no registrador / VI.

4. O conteúdo de N2 é adicionado módulo 2 com a constante C2 = 2 24 + 2 16 + 2 8 +1, o resultado da adição é escrito no registrador N2.

5. O conteúdo dos registros / VI e N2 são emitidos como um bloco gama de cifra de 64 bits (ou seja, neste caso / VI e N2 formam o primeiro bloco gama).

6. Se o próximo bloco de gama for necessário (ou seja, você precisa continuar com a criptografia ou descriptografia), volte para a etapa 2.

Para a descriptografia, o gama é gerado de maneira semelhante e, em seguida, a operação XOR é novamente aplicada ao texto cifrado e aos bits gama.

Para gerar a mesma gama de cifras, o usuário que descriptografa o criptograma deve ter a mesma chave e o mesmo valor de sincronização que foram usados para criptografar as informações. Caso contrário, não será possível obter o texto original do criptografado.

Na maioria das implementações do algoritmo GOST 28147-89, a mensagem de sincronização não é um elemento secreto, no entanto, a mensagem de sincronização pode ser tão secreta quanto a chave de criptografia. Nesse caso, podemos supor que o comprimento efetivo da chave do algoritmo (256 bits) é aumentado por mais 64 bits da mensagem de sincronização, que pode ser considerada como um elemento chave adicional.

Modo gama com feedback

No modo gama com realimentação, como o preenchimento dos registros / VI e L / 2, a partir do 2º bloco, não é utilizado o bloco gama anterior, mas o resultado da criptografia do bloco anterior de texto simples (Fig. 3.4) . O primeiro bloco neste modo é gerado de forma completamente semelhante ao anterior.

Arroz. 3.4. Geração de cifra gama no modo gama com feedback

Modo de produção de um simulador

Um prefixo é uma soma de verificação criptográfica calculada usando uma chave de criptografia para verificar a integridade das mensagens. Para calculá-lo, existe um modo especial do algoritmo GOST 28147-89.

A geração de um simulador é realizada da seguinte forma:

1. O primeiro bloco de informações de 64 bits, para o qual o prefixo é calculado, é escrito nos registros N1 e N2 e criptografado no modo reduzido de substituição simples, no qual os primeiros 16 ciclos de 32 são executados.

2. O resultado obtido é somado ao módulo 2 com o próximo bloco de informações, armazenando o resultado em N1 e N2.

3. M e N2 são criptografados novamente no modo reduzido de substituição simples, e assim por diante até o último bloco de informações.

Um imitador é o conteúdo resultante de 64 bits dos registradores N1 e N2, ou parte dele. O prefixo de 32 bits mais comumente usado é usado, ou seja, metade do conteúdo do registro. Isso é suficiente, uma vez que, como qualquer soma de verificação, o simulador é projetado principalmente para proteger contra distorção acidental de informações. Para proteger contra modificação deliberada de dados, outros métodos criptográficos são usados - em primeiro lugar, uma assinatura digital eletrônica (consulte a seção 1.1).

O imitador é usado da seguinte forma:

1. Ao criptografar qualquer informação, um prefixo de texto simples é calculado e enviado junto com o texto cifrado.

2. Após a descriptografia, o prefixo é calculado novamente e comparado com o enviado.

3. Se os prefixos calculados e enviados não corresponderem - o texto cifrado foi distorcido durante a transmissão ou chaves incorretas foram usadas durante a descriptografia.

O prefixo é especialmente útil para verificar a descriptografia correta das informações de chave ao usar esquemas de várias chaves.

Um imitador é algum análogo do código de autenticação de mensagem MAC calculado no modo CBC; a diferença é que a mensagem de sincronização não é usada no cálculo do prefixo, enquanto o vetor de inicialização é usado no cálculo do MAC.

Força criptográfica do algoritmo

Em 1994, a descrição do algoritmo GOST 28147-89 foi traduzida para o inglês e publicada; foi depois disso que os resultados de sua análise, realizada por especialistas estrangeiros, começaram a aparecer; no entanto, por um período de tempo considerável, nenhum ataque foi considerado viável.

□ grande comprimento de chave - 256 bits; junto com a mensagem de sincronização secreta, o comprimento efetivo da chave é aumentado para 320 bits;

□ 32 rodadas de transformações; após 8 rodadas, o efeito total de dispersão dos dados de entrada é alcançado: uma mudança em um bit do bloco de texto simples afetará todos os bits do bloco de texto cifrado, e vice-versa, ou seja, há uma margem de segurança múltipla.

Considere os resultados da criptanálise do algoritmo GOST 28147-89.

Análise de tabelas de substituição

Como as tabelas de substituição não são fornecidas na norma, vários trabalhos (por exemplo, c) sugerem que uma "organização competente" pode produzir tabelas de substituição "boas" e "ruins". No entanto, o famoso especialista Bruce Schneier chama essas suposições de "rumores". É claro que a força criptográfica do algoritmo depende muito das propriedades das tabelas de substituição usadas; consequentemente, existem tabelas de substituição fracas (ver um exemplo acima), cujo uso pode simplificar o ataque ao algoritmo. No entanto, a possibilidade de usar diferentes tabelas de substituição parece uma ideia muito válida, em favor da qual dois fatos da história do padrão de criptografia DES podem ser citados (ver seção 3.15 para detalhes):

□ ataques usando criptoanálise linear e diferencial do algoritmo DES usam recursos específicos de tabelas de substituição; ao usar outras tabelas, a criptoanálise terá que recomeçar;

□ foram feitas tentativas para fortalecer o DES contra a criptoanálise linear e diferencial usando tabelas de substituição mais robustas; tais tabelas, de fato mais robustas, foram propostas, por exemplo, no algoritmo 5 DES; mas, infelizmente, era impossível substituir DES por s 5 DES, uma vez que as tabelas de substituição são rigidamente definidas no padrão, respectivamente, a implementação do algoritmo provavelmente não suporta a capacidade de alterar tabelas para outras.

Em uma série de trabalhos (por exemplo, e) é erroneamente concluído que as tabelas secretas de substituições do algoritmo GOST 28147-89 podem fazer parte da chave e aumentar seu comprimento efetivo (que é insignificante, uma vez que o algoritmo tem uma chave grande de 256 bits). No entanto, o trabalho provou que as tabelas de substituição secreta podem ser calculadas usando o seguinte ataque, que pode ser aplicado na prática:

1. Coloca-se a chave zero e realiza-se a busca pelo “vetor zero”, ou seja, os valores z = / (0), onde / () é a função de rodada do algoritmo. Este estágio leva cerca de 2 operações de criptografia.

2. Usando o vetor zero, os valores das tabelas de substituição são calculados, o que leva no máximo 2 11 operações.

Modificações de algoritmo e sua análise

O trabalho realizou uma criptanálise de modificações do algoritmo GOST 28147-89:

□ o algoritmo GOST-H, no qual, em relação ao algoritmo original, a ordem de uso das subchaves é alterada, ou seja, nas rodadas 25 a 32, as subchaves são usadas em ordem direta, ou seja, da mesma forma que em as rodadas anteriores do algoritmo;

□ Algoritmo GOST® de 20 rodadas, que usa XOR para aplicar a chave em vez da adição do módulo 32.

Com base nos resultados da análise, concluiu-se que GOST-H e GOST © são mais fracos do que o algoritmo GOST 28147-89 original, uma vez que ambos têm classes de chaves fracas. Deve-se notar que na parte da criptoanálise GOST ©, o trabalho repete palavra por palavra a seção dedicada à criptoanálise do algoritmo GOST 28147-89, publicado em 2000 por um trabalho bem conhecido (sem quaisquer referências ao original) . Isso lança dúvidas sobre o profissionalismo dos autores da obra e do restante de seus resultados.

Uma modificação muito interessante do algoritmo é proposta no trabalho: as tabelas S \ ... Ss devem ser diferentes; em cada rodada do algoritmo, eles devem ser reorganizados de acordo com uma determinada lei. Essa permutação pode ser dependente da chave de criptografia ou pode ser secreta (ou seja, pode ser parte da chave de criptografia maior do que a chave original de 256 bits). Ambas as opções, de acordo com seus autores, aumentam significativamente a resistência do algoritmo contra a criptoanálise linear e diferencial.

E mais uma modificação relacionada às tabelas de substituição é dada no trabalho, que analisa um dos possíveis métodos de cálculo das tabelas de substituição a partir da chave de criptografia. Os autores do trabalho concluíram que tal dependência enfraquece o algoritmo, pois leva à presença de chaves fracas e a algumas vulnerabilidades potenciais do algoritmo.

Análise de algoritmo de rodada completa

Há ataques no GOST 28147-89 completo sem nenhuma modificação. Uma das primeiras obras públicas em que foi realizada a análise do algoritmo - um trabalho bem conhecido - é dedicada a ataques que exploram as fraquezas do procedimento de expansão de chave de uma série de algoritmos de criptografia conhecidos. Em particular, o algoritmo full-round GOST 28147-89 pode ser quebrado usando criptoanálise diferencial em chaves vinculadas, mas somente se tabelas de substituição fracas forem usadas. A variante de 24 rodadas do algoritmo (que não possui as primeiras 8 rodadas) é aberta da mesma maneira para quaisquer tabelas de substituição, mas tabelas de substituição fortes (por exemplo, mostradas em c) tornam esse ataque completamente impraticável.

Os cientistas domésticos A.G. Rostovtsev e E.B. Makhovenko em 2001, em seu trabalho, propuseram um método fundamentalmente novo de criptoanálise (de acordo com os autores, muito mais eficaz do que a criptoanálise linear e diferencial), formando uma função objetivo a partir de um texto simples conhecido correspondente ao texto cifrado e ao desejado valor-chave e encontrando seu extremo correspondente ao valor-chave verdadeiro. Eles também encontraram uma grande classe de chaves fracas do algoritmo GOST 28147-89, que tornam possível quebrar o algoritmo usando apenas 4 textos simples selecionados e os textos cifrados correspondentes com uma complexidade bastante baixa. A criptoanálise do algoritmo é continuada no trabalho.

Em 2004, um grupo de especialistas da Coréia propôs um ataque com o qual, por meio da criptoanálise diferencial de chaves vinculadas, é possível obter, com 91,7% de probabilidade, 12 bits da chave secreta. O ataque requer 2 35 textos simples selecionados e 2 36 operações de criptografia. Como você pode ver, este ataque é praticamente inútil para um ataque real ao algoritmo.

Algoritmo GOST 28147-89 e cifra "Magma" (GOST R 34.12-2015)

Esquema geral do algoritmo. O algoritmo descrito por GOST 28147-89 “Sistemas de processamento de informações. Proteção criptográfica. Algoritmo de Transformação Criptográfica ", é um padrão nacional para criptografia simétrica (antes de 1º de janeiro de 2016) e é obrigatório para implementação em ferramentas de proteção de informações criptográficas certificadas usadas em sistemas de informação estaduais e, em alguns casos, em sistemas comerciais. A certificação dos meios de proteção criptográfica das informações é necessária para proteger as informações que constituem um segredo de estado da Federação Russa, e as informações, cuja confidencialidade deve ser garantida de acordo com a legislação em vigor. Também na Federação Russa, o uso do algoritmo GOST 28147-89 é recomendado para a proteção de sistemas de informações bancárias.

O algoritmo GOST 28147-89 (Fig. 2.21) é baseado no esquema Feistel e criptografa as informações em blocos de 64 bits, que são divididos em dois sub-blocos de 32 bits (I, e R). Sub-bloco R,é processado pela função de transformação round, após o qual seu valor é adicionado ao valor do subbloco Lj, então os subblocos são trocados. O algoritmo tem 16 ou 32 rodadas, dependendo do modo de criptografia (cálculo da inserção de imitação ou outros modos de criptografia).

Arroz. 2,21.

Em cada rodada do algoritmo, as seguintes transformações são realizadas.

1. Sobreposição de chave. Conteúdo de sub-bloco R i adicionado módulo 2 32 com chave redonda K. Kjé a parte de 32 bits da chave original usada como rodada. O algoritmo GOST 28147-89 ns usa um procedimento de expansão de chave, a chave de criptografia de 256 bits original é representada como uma concatenação (concatenação) de oito subchaves de 32 bits (Fig. 2.22): K 0, K (, K t K, K A, K 5, K 6, K 7.

O processo de criptografia usa uma dessas subchaves PARA

Da 1ª à 24ª rodada - em sequência direta:

Do 25º ao 32º turno - na ordem inversa:

Arroz. 2,22. A estrutura da chave de criptografia do algoritmo GOST 28147-89

2. Substituição tabular. Depois que a chave foi aplicada, o sub-bloco R ié dividido em oito partes, mas 4 bits, o valor de cada um dos quais é substituído individualmente de acordo com sua tabela de substituição (S-box). Um total de oito caixas S são usadas - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. Cada S-box do algoritmo GOST 28147-89 é um vetor (array unidimensional) com ^ elementos numerados de 0 a 15. Os valores da S-box são números de 4 bits; inteiros de 0 a 15.

Um elemento é obtido da tabela S-box, cujo número de sequência coincide com o valor que veio para a entrada de substituição.

Exemplo 2.6.

Deixe haver um bloco S com a seguinte forma:

Seja o valor 0100 2 = 4 dado à entrada desta caixa S. A saída da caixa S será o 4º elemento da tabela de substituição, ou seja. 15 = 1111 2 (os elementos são numerados a partir de zero).

as pessoas de substituição não são definidas pelo padrão, como é feito, por exemplo, na cifra DES. Os valores mutáveis das tabelas de substituição complicam significativamente a criptoanálise do algoritmo. Ao mesmo tempo, a robustez do algoritmo depende significativamente de sua escolha correta.

Infelizmente, o algoritmo GOST 28147-89 tem tabelas de substituição “fracas”, ao usar as quais o algoritmo pode ser facilmente revelado por métodos criptanalíticos. Entre os "fracos" está, por exemplo, uma tabela trivial de substituições, na qual a entrada é igual à saída (Tabela 2.16).

Tabela 2.16

Um exemplo de um S-box fraco

Acredita-se que os valores específicos das tabelas de substituição devem ser mantidos em segredo e são um elemento-chave de longo prazo, ou seja, são válidos por um período muito mais longo do que as chaves individuais. No entanto, os valores secretos das tabelas de substituição não fazem parte da chave e não podem aumentar seu comprimento efetivo.

Na verdade, as tabelas de substituição secreta podem ser calculadas usando o seguinte ataque, que pode ser aplicado na prática:

uma chave zero é definida e uma pesquisa por um "vetor zero" é executada, isto é. significado z = F ( 0), onde F - função de transformação redonda do algoritmo. Isso requer cerca de 2 32 operações de criptografia de teste;
usando o vetor zero, os valores das tabelas de substituição são calculados, o que leva no máximo 2 11 operações.

No entanto, mesmo se a confidencialidade das tabelas de substituição for violada, a força da cifra permanece extremamente alta e não cai abaixo do limite permitido.

Também é assumido que as tabelas de substituição são comuns para todos os nós de criptografia no mesmo sistema de proteção criptográfica.

Melhorar a estrutura das S-box é um dos problemas mais intensamente pesquisados no campo das cifras de blocos simétricos. Basicamente, é necessário que quaisquer alterações nas entradas das caixas S se espalhem para aleatória aparentemente mudando a saída. Por outro lado, quanto maiores as S-boxes, mais resistente o algoritmo é aos métodos de criptanálise linear e diferencial. Por outro lado, uma grande mesa de reposição é mais difícil de projetar.

Em algoritmos modernos, as S-boxes são geralmente um vetor (matriz unidimensional) contendo 2 "t- elementos de bits. A entrada do bloco define o número do elemento, cujo valor serve como a saída do bloco S.

Vários critérios foram propostos para o projeto de S-box. A tabela de substituição deve satisfazer:

critério estrito de avalanche;
critério de independência de bit;
requisito de não linearidade dos valores de entrada.

Para cumprir o último requisito, foi proposto especificar uma combinação linear eu bits ( i = 1, ..., T) valores da tabela de substituição funções dobradas(eng, dobrado - desviando, neste caso - de funções lineares). As funções dobradas formam uma classe especial de funções booleanas caracterizada pela mais alta classe de não linearidade e conformidade com o critério estrito de avalanche.

Em alguns trabalhos, para S-box, é proposto verificar a implementação do efeito avalanche garantido de ordem y - quando um bit de entrada muda, pelo menos os bits de saída da S-box mudam. A propriedade de efeito avalanche garantido da ordem de y de 2 a 5 fornece características de difusão suficientemente boas de S-box para qualquer algoritmo de criptografia.

Ao projetar tabelas de substituição suficientemente grandes, as seguintes abordagens podem ser usadas:

seleção aleatória (para pequenas caixas S, pode levar à criação de tabelas de substituição fracas);
seleção aleatória seguida de verificação do cumprimento de vários critérios e rejeição de caixas S fracas;
seleção manual (muito trabalhosa para grandes blocos S);
abordagem matemática, por exemplo, geração usando funções dobradas (esta abordagem é aplicada no algoritmo CAST).

O seguinte procedimento para projetar blocos S individuais do algoritmo GOST 28147-89 pode ser proposto:

cada S-box pode ser descrita por quatro funções lógicas, cada uma das funções deve ter quatro argumentos lógicos;
essas funções precisam ser complexas o suficiente. Este requisito de complexidade não pode ser expresso formalmente, no entanto, como uma condição necessária, pode ser exigido que as funções lógicas correspondentes, escritas na forma mínima (ou seja, com o comprimento de expressão mínimo possível) usando operações lógicas básicas, não sejam menores que um certo valor exigido;
funções individuais, mesmo usadas em diferentes tabelas de substituição, devem ser suficientemente diferentes umas das outras.

Em 2011, um novo ataque “reunião reflexiva no meio” foi proposto, o que reduz ligeiramente a resistência do GOST 28147-89 (de 2256 para 2225). O melhor resultado da criptanálise do algoritmo em 2012 reduz sua força para 2.192, exigindo um tamanho de texto cifrado relativamente grande e um volume de dados pré-formados. Apesar dos ataques propostos, o GOST 28147-89 permanece praticamente estável no nível atual de desenvolvimento de tecnologia de computador.

Código "Magma" (GOST R 34.12-2015). O padrão GOST 28147-89 está em vigor na Rússia há mais de 25 anos. Durante esse tempo, ele mostrou durabilidade suficiente e boa eficiência de implementações de software e hardware, incluindo aquelas em dispositivos de poucos recursos. Embora ataques criptanalíticos tenham sido propostos para reduzir as estimativas de sua resistência (o melhor é para 2.192), eles estão longe de serem viáveis. Portanto, foi decidido incluir o algoritmo GOST 28147-89 no padrão de criptografia simétrica recém-desenvolvido.

Na loja de 2015, foram adotados dois novos padrões criptográficos nacionais: GOST R 34.12-2015 “Tecnologia da informação. Proteção de informações criptográficas. Block ciphers "e GOST R 34.13-2015" Tecnologia da informação. Proteção de informações criptográficas. Modos de operação das cifras de bloco ", que entram em vigor em 1º de janeiro de 2016.

O padrão GOST R 34.12-2015 contém uma descrição de duas cifras de bloco com um comprimento de bloco de 128 e 64 bits. A cifra GOST 28147-89 com blocos de substituição não lineares fixos está incluída no novo GOST R 34.12-2015 como uma cifra de 64 bits chamada "Magma".

Abaixo estão os blocos de substituição fixados no padrão:

O conjunto de S-box fornecido na norma fornece as melhores características que determinam a resistência do criptoalgoritmo à criptoanálise diferencial e linear.

De acordo com o comitê técnico de padronização "Proteção criptográfica de informações" (TC 26), a fixação de blocos de substituição não linear tornará o algoritmo GOST 28147-89 mais unificado e ajudará a eliminar o uso de blocos de substituição não linear "fracos". Além disso, a fixação no padrão de todos os parâmetros de longo prazo da cifra atende à prática internacional aceita. A nova norma GOST R 34.12-2015 está terminológica e conceitualmente ligada às normas internacionais ISO / IEC 10116 “Tecnologia da informação. Métodos de segurança. Modos de operação para "cifras de bloco de bits" (ISO / IEC 10116: 2006 Tecnologia da informação - Técnicas de segurança - Modos de operação para uma cifra de bloco de n bits) e a série ISO / IEC 18033 "Tecnologia da informação. Métodos e meios para garantir a segurança. Algoritmos de criptografia ": ISO / IEC 18033-1: 2005" Parte 1. Geral "(ISO / IEC 18033-1: 2005 Tecnologia da informação - Técnicas de segurança - Algoritmos de criptografia - Parte 1: Geral) e ISO / IEC 18033-3: 2010 "Parte 3. Cifras de bloco" (ISO / IEC 18033-3: 2010 (Tecnologia da informação - Técnicas de segurança - Algoritmos de criptografia - Parte 3: Cifras de bloco)).

O padrão GOST P 34.12-2015 também inclui uma nova cifra de bloco ("Grasshopper") com um tamanho de bloco de 128 bits. Espera-se que essa cifra seja robusta contra todos os ataques de cifra de bloco conhecidos hoje.

Os modos de operação das cifras de bloco (substituição simples, gama, gama com feedback de saída, gama com feedback de texto cifrado, substituição simples com engajamento e o desenvolvimento de uma inserção de imitação) estão incluídos em um padrão separado GOST R 34.13-2015, que corresponde a a prática internacional aceita. Esses modos são aplicáveis à cifra Magma e à nova cifra Grasshopper.

O deslocamento circular à esquerda de 11 bits é executado. A descriptografia é realizada de acordo com o mesmo esquema, mas com um cronograma de uso de chave diferente: da 1ª à 8ª rodada de descriptografia - na ordem direta: da 9ª à 32ª rodada de descriptografia - na ordem inversa: Em comparação com o A cifra DES em GOST 28147-89 tem as seguintes vantagens: uma chave significativamente mais longa (256 bits contra 56 para a cifra DES), um ataque em que a enumeração de força bruta do conjunto de chaves parece impossível no momento; um cronograma simples para usar a chave, o que simplifica a implementação do algoritmo e aumenta a velocidade dos cálculos. Projeto de blocos S GOST 28147-89. É óbvio que o esquema do algoritmo GOST 28147-89 é muito simples. Isso significa que a maior carga de criptografia recai sobre as tabelas de substituição. Valores de tabulação
Algoritmos de criptografia Panasepko S.P.: um livro de referência especial. SPb.: BHV-Peter-burg, 2009.
Kara O. Ataques de reflexão em cifras de produto. URL: http://eprint.iacr.org/2007/043.pdf
Padrão de criptografia russo: força reduzida. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
Achekseev E. K., Smyshlyaev S. V. GOST 28147-89: "Não se apresse para enterrá-lo."

O conhecido pesquisador, o fundador da criptoanálise algébrica, Nicolas Courtois, afirma que a cifra de bloco GOST, que se tornaria um padrão internacional em um futuro próximo, está na verdade quebrada e aguarda muitas publicações no futuro que devem desenvolver suas ideias sobre a instabilidade deste algoritmo.

A seguir, breves trechos dessa obra, que pode ser considerada um ataque alarmista em meio à padronização internacional (o autor era conhecido por exageros semelhantes em relação ao AES, mas seu trabalho teve grande influência teórica na criptanálise, mas teve não levou a ataques práticos à própria AES). Mas, talvez, este seja também um alerta real sobre o início da fase da "aeronave mergulhando em uma pirueta", que pode terminar com o colapso do padrão nacional de criptografia, como foi o caso do algoritmo de hashing SHA-1 e o algoritmo de hashing MD5 de fato.

O GOST 28147-89 foi padronizado em 1989 e se tornou o padrão oficial para a proteção de informações confidenciais pela primeira vez, mas a especificação da cifra permaneceu fechada. Em 1994, o padrão foi desclassificado, publicado e traduzido para o inglês. Por analogia com o AES (e ao contrário do DES), GOST tem permissão para proteger informações classificadas sem restrições, de acordo com a forma como é especificado no padrão russo. Este. GOST não é um análogo do DES, mas um concorrente do 3-DES com três chaves independentes ou AES-256. Obviamente, GOST é uma cifra bastante séria que atende aos critérios militares, criada com a expectativa das aplicações mais sérias. Pelo menos dois conjuntos de GOST S-box foram identificados com base em aplicativos usados por bancos russos. Esses bancos precisam conduzir comunicações secretas com centenas de agências e proteger bilhões de dólares contra roubo fraudulento.

GOST é uma cifra de bloco com uma estrutura Feistel simples, com um tamanho de bloco de 64 bits, uma chave de 256 bits e 32 rodadas. Cada rodada contém um módulo 2 ^ 32 de adição de chave, um conjunto de oito S-boxes de 4 bits e um deslocamento cíclico simples de 11 bits. Uma característica do GOST é a capacidade de armazenar blocos S em segredo, que pode ser representado como uma segunda chave que aumenta o material da chave efetiva para 610 bits. Um conjunto de S-boxes foi publicado em 1994 como parte da especificação da função hash GOST-R 34.11-94 e, como escreveu Schneier, foi usado pelo Banco Central da Federação Russa. Também está incluído no RFC4357 na parte "id-GostR3411-94-CryptoProParamSet". Havia um bug no código-fonte no final do livro de Schneier (na ordem S-box). A implementação de referência mais precisa de origem russa nativa agora pode ser encontrada na biblioteca OpenSSL. Se caixas S secretas são usadas em algum lugar, então elas podem ser extraídas de implementações de software e de microcircuitos, de fato, os trabalhos correspondentes foram publicados.

GOST é um concorrente sério

Além do tamanho de chave muito grande, o GOST tem um custo de execução significativamente menor em comparação com AES e outros sistemas de criptografia semelhantes. Na verdade, custa muito menos do que o AES, que requer quatro vezes mais portas lógicas de hardware para o nível de segurança reivindicado, muito mais baixo.

Não é surpreendente que GOST tenha se tornado um padrão da Internet, em particular, ele está incluído em muitas bibliotecas de criptografia, como OpenSSL e Crypto ++, e está se tornando mais popular fora de seu país de origem. Em 2010, o GOST foi declarado para padronização ISO como um padrão de criptografia mundial. Um número extremamente pequeno de algoritmos foi capaz de se tornar padrões internacionais. ISO / IEC 18033-3: 2010 descreve os seguintes algoritmos: quatro cifras de 64 bits - TDEA, MISTY1, CAST-128, HIGHT - e três cifras de 128 bits - AES, Camellia, SEED. Propõe-se que GOST seja adicionado ao mesmo padrão ISO / IEC 18033-3.

Pela primeira vez na história da padronização industrial, estamos lidando com um algoritmo tão competitivo em termos de otimização entre custo e nível de segurança. GOST tem 20 anos de esforços de criptoanálise e até recentemente sua segurança de nível militar não foi questionada.

Como o autor soube recentemente por correspondência privada, a maioria dos países se opôs a GOST na votação da ISO em Cingapura, mas os resultados dessa votação ainda serão considerados na reunião plenária da ISO SC27, então GOST ainda está em processo de padronização no momento de publicação deste trabalho.

Opiniões de especialistas sobre GOST

Nada das informações disponíveis e literatura sobre GOST dá motivos para acreditar que a cifra pode ser insegura. Pelo contrário, o grande tamanho da chave e o grande número de rodadas tornam o GOST, à primeira vista, adequado para décadas de uso.

Qualquer pessoa familiarizada com a Lei de Moore sabe que, em teoria, as chaves de 256 bits permanecerão seguras por pelo menos 200 anos. GOST foi extensivamente estudado pelos principais especialistas no campo da criptografia, conhecidos no campo da análise de cifra de bloco, como Schneier, Biryukov, Dankelman, Wagner, muitos cientistas australianos, japoneses e russos, especialistas em criptografia da ISO e todos os pesquisadores expressou que tudo parece assim que ele pode ou deveria estar seguro. Embora a opinião tenha chegado a um amplo entendimento de que a estrutura do próprio GOST é extremamente fraca, por exemplo, em comparação com DES, em particular, a difusão não é tão boa, no entanto, isso sempre foi devido ao fato de que isso deveria ser compensado por um grande número de rodadas (32), bem como uma não linearidade e difusão adicionais fornecidas pela adição de módulo.

Biryukov e Wagner escreveram: "O grande número de rodadas (32) e a bem estudada construção Feistel, combinada com sucessivas permutações de Shannon, fornecem uma base sólida para a segurança GOST." Na mesma obra, lemos: "após um considerável investimento de tempo e esforço, nenhum progresso foi feito na criptoanálise do padrão na literatura aberta." Portanto, não houve ataques significativos que permitiriam a descriptografia ou recuperação de chave em um cenário realista onde GOST é usado na criptografia com muitas chaves aleatórias diferentes. Em contraste, existem muitos trabalhos conhecidos sobre ataques a chaves fracas em GOST, ataques com chaves associadas, ataques à recuperação de S-boxes secretas. Na Crypto 2008, foi apresentado um hacking de uma função hash baseada nesta cifra. Em todos os ataques, o invasor tem um nível de liberdade significativamente maior do que o normalmente permitido. Em aplicações tradicionais de criptografia usando chaves selecionadas aleatoriamente, nenhum ataque criptográfico sério contra GOST foi encontrado até agora, o que em 2010 foi expresso pela frase final: "apesar dos esforços significativos dos criptoanalistas nos últimos 20 anos, o GOST ainda não foi cracked "(Axel Poschmann, San Ling e Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, pp. 219-233, 2010).

Análise linear e diferencial GOST

No conhecido livro de Schneier, lemos: "Contra a criptoanálise diferencial e linear, o GOST é provavelmente mais robusto do que o DES." A principal avaliação de segurança do GOST foi feita em 2000 por Gabidulin et al. Seus resultados são muito impressionantes: com um nível de segurança de 2 ^ 256 definido, cinco rodadas são suficientes para proteger o GOST da criptoanálise linear. Além disso, mesmo ao substituir S-boxes por outras idênticas e a única operação de cifra não linear - mod de adição 2 ^ 32 - a cifra ainda é resistente à criptoanálise linear após 6 rodadas de 32. A criptoanálise diferencial GOST parece relativamente mais fácil e atrai mais atenção. Para um nível de segurança de 2 ^ 128, os pesquisadores (Vitaly V. Shorin, Vadim V. Jelezniakov e Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint submetido a Elsevier Preprint, 4 de abril de 2001) assumiu durabilidade suficiente em 7 rodadas . De acordo com eles, quebrar GOST em mais de cinco rodadas é "extremamente difícil". Além disso, dois pesquisadores japoneses mostraram que um ataque diferencial avançado clássico com uma característica diferencial tem uma probabilidade extremamente baixa de passar por um grande número de rodadas. Com base no fato de estudar uma característica diferencial iterativa suficientemente "boa" para um número limitado de rodadas (que por si só tem uma probabilidade de passar não melhor do que 2-11,4 por rodada), o valor do conjunto de chaves adequadas é menos da metade . Para um GOST de rodada completa, tal ataque com uma única característica funcionará apenas com uma parte insignificante das chaves da ordem de 2-62 (e mesmo nesta pequena parte terá uma probabilidade de passar não mais do que 2-360 )

Ataques mais sofisticados envolvem múltiplos diferenciais que seguem certos padrões, como o uso de S-boxes individuais que possuem diferenciais zero enquanto outros bits possuem diferenciais diferentes de zero. Estamos falando sobre discriminar ataques com base nas propriedades de difusão pobres de GOST. O melhor desses ataques funciona contra 17 rodadas de GOST, depende da chave e tem um discriminador extremamente fraco de dados aleatórios na própria saída, para que possa de alguma forma ser usado para obter informações sobre a chave.

Escorregar e desviar ataques

Segundo Biryukov e Wagner, a estrutura GOST, que inclui a ordem inversa das subchaves nas últimas rodadas, o torna resistente a ataques deslizantes (os chamados "ataques deslizantes"). No entanto, devido à presença de uma grande auto-similaridade na cifra, isso permite ataques de inversão de chave em combinações de pontos fixos e propriedades de "reflexão" (os chamados "ataques reflexivos") para certas chaves fracas. A complexidade desse ataque é 2 ^ 192 e 2 ^ 32 textos simples correspondentes.

Últimos resultados

Novos ataques também usam reflexão e, na verdade, quebraram o GOST, que foi apresentado na conferência FSE 2011. Esses ataques também foram descobertos de forma independente pelo autor deste artigo. O ataque requer 2 ^ 132 bytes de memória, o que é realmente pior do que ataques mais lentos com menos requisitos de memória.

Muitos novos ataques de auto-similaridade funcionam contra todas as chaves GOST e permitem quebrar um GOST completo com uma chave de 256 bits, e não apenas para chaves fracas, como era antes. Todos esses ataques requerem muito menos memória e são significativamente mais rápidos.

Esses novos ataques podem ser vistos como exemplos de um novo paradigma geral para criptanálise de cifras de bloco denominado "redução de complexidade algébrica", que generaliza esses ataques para muitos casos particulares de ataques com pontos fixos, slides, involuções e ciclos conhecidos. É importante que entre a família de todos esses ataques existam aqueles que permitem a criptoanálise de GOST sem quaisquer reflexos e sem quaisquer pontos simétricos que apareçam no decorrer dos cálculos. Um exemplo é um ataque de hacking GOST simples sem reflexo neste trabalho.

Criptoanálise algébrica e ataques de baixa complexidade de dados em cifras de rodadas reduzidas

Ataques algébricos em cifras de bloco e fluxo podem ser representados como um problema de resolução de um grande sistema de equações algébricas booleanas que seguem a geometria e a estrutura de um esquema criptográfico particular. A própria ideia remonta a Shannon. Na prática, ele foi apresentado para o DES (apresentado pela primeira vez pelo autor deste trabalho) como um método de codificação formal e pode quebrar 6 rodadas em apenas um texto simples conhecido. A manipulação de equações é baseada em algoritmos XL, bases de Gröbner, método ElimLin, solvers SAT.

Na prática, ataques algébricos foram implementados contra um número muito pequeno de rodadas de cifras de bloco, mas já levaram à quebra de cifras de fluxo, e também houve sucessos na quebra de cifras ultraleves para micro-equipamentos. Devido às dificuldades no tamanho da memória e nas estimativas de custo computacional, eles são combinados com outros ataques.

Como hackear GOST?

Um ataque algébrico em um GOST completo é apresentado em mais detalhes nesta publicação. Em um trabalho anterior, o autor já esboçou 20 ataques algébricos em GOST e espera um grande número deles em um futuro próximo. O ataque proposto neste trabalho não é o melhor deles, mas abre um caminho fácil (pelo menos para o entendimento dos criptógrafos) para desenvolvimentos subsequentes para criar uma metodologia específica para crackear GOST.

O resultado prático ainda é modesto: 2 ^ 64 texto simples conhecido e 2 ^ 64 de memória para armazenar pares de texto simples / texto cifrado tornam possível quebrar o GOST 2 ^ 8 mais rápido do que a simples força bruta. Mas em termos de criptoanálise, isso torna a declaração de que "GOST foi hackeado" é completamente justo.

conclusões

O GOST foi projetado para fornecer um nível militar de segurança por 200 anos. A maioria dos principais especialistas que estudaram o GOST concordaram que "apesar dos esforços criptanalíticos significativos ao longo de 20 anos, o GOST ainda não foi quebrado". Em 2010, GOST foi promovido a ISO 18033 como o padrão de criptografia global.

A fundação das idéias sobre criptoanálise algébrica data de mais de 60 anos. Mas apenas nos últimos 10 anos foram desenvolvidas ferramentas de software eficazes para a solução (parcial) de muitos problemas NP-completos. Uma série de cifras de fluxo foram quebradas. Apenas uma cifra de bloco foi quebrada por este método - o próprio KeeLoq fraco. Neste trabalho, o autor quebra uma cifra GOST importante e realmente usada. Ele observa que esta é a primeira vez na história que uma cifra de estado padronizada foi quebrada por criptoanálise algébrica.

Um simples ataque "MITM com reflexão" em GOST já foi apresentado na conferência FSE 2011. No trabalho discutido neste artigo, outro ataque é apresentado apenas para ilustrar o fato de quantos ataques em GOST já apareceram agora, muitos dos quais são mais rápidos e um ataque algébrico requer muito menos memória e abre um espaço quase inesgotável de possibilidades para o adversário atacar a cifra de diferentes maneiras. Também neste artigo, é mostrado que não há necessidade de usar a propriedade de reflexão para hackear.

O autor afirma que é óbvio que o GOST tem falhas graves e agora não fornece o nível de durabilidade exigido pela ISO. Muitos ataques a GOST são apresentados no quadro da confirmação do paradigma de redução da complexidade algébrica.

Por fim, o pesquisador destaca principalmente alguns fatos que ainda não estão disponíveis ao leitor, mas são conhecidos pelo pesquisador, que são importantes no decorrer do processo de padronização ISO. Este ataque não é apenas um ataque de "certificação" no GOST, que é mais rápido do que o ataque de força bruta de força bruta. Na verdade, padronizar GOST agora seria extremamente perigoso e irresponsável. Isso ocorre porque alguns dos ataques são práticos. Na prática, algumas chaves GOST podem até mesmo ser descriptografadas, sejam elas chaves fracas ou chaves de aplicativos privados reais de GOST. No trabalho anterior, o autor dá uma consideração detalhada dos casos de possibilidade de ataques práticos. Significativamente, "esta é a primeira vez na história que uma cifra de bloco padronizada séria projetada para proteger segredos de nível militar e projetada para proteger segredos de estado para governos, grandes bancos e outras organizações foi comprometida por um ataque matemático."