Sobre o código do GOST, Grasshopper, seu SBox e sementes perdidas

Olá% username%!



Recentemente, retornamos da conferência EuroCrypt 2019, onde conhecemos pessoas extremamente inteligentes e, ao mesmo tempo, aprendemos fatos novos e extremamente ofensivos sobre o GOST SBox.

Portanto, esta é a segunda abordagem do projétil. Corrigido e suplementado.

Desta vez, não haverá slides incompreensíveis em vermelho-azul, mas haverá documentos originais do comitê ISO com explicações dos autores do Grasshopper.

E até o desafio no final!

Vamos lá

Primeiro programa educacional. No artigo anterior, não foi, desta vez eu corrijo.

Ataque de texto simples escolhido (CPA)

Começamos com o modelo básico de ataque em cifras de bloco.

Nesse modelo, o invasor sabe tudo sobre o sistema de criptografia, exceto a chave de criptografia. Ele pode criar qualquer texto simples, obter os textos cifrados correspondentes e sua tarefa é calcular a chave, porque essa é a única variável.

A cifra de bloco nessa situação pode ser considerada como uma substituição pseudo-aleatória. Uma função que corresponde a um bloco de texto simples a um bloco de texto cifrado de forma que seja impossível determinar o relacionamento entre eles.

Uma cifra de bloco ideal pode ser imaginada como uma tabela grande, onde horizontalmente haverá todas as chaves possíveis de 000 ... 000 a 111 ... 111, verticalmente - todos os textos abertos possíveis também de 000 ... 000 a 111 ... 111 , e no local da interseção - textos cifrados gerados aleatoriamente que associariam exclusivamente um par de "texto-chave-plano". Criar uma tabela na vida real não é possível devido ao seu tamanho, por isso é emulada usando vários algoritmos de criptografia de bloco.

O ataque à cifra de bloco pode ser chamado de êxito se pudermos determinar a “aleatoriedade” com a qual o algoritmo seleciona textos cifrados que correspondem a textos simples. Essa aleatoriedade permite, nos piores casos, calcular a chave de criptografia.

(Não) linearidade

O processo de criptografia na cifra de bloco pode ser representado por uma fórmula simples
C = M x K
onde C é texto cifrado, M é texto simples, K é a chave de criptografia ex x é a cifra de bloco.

Essa fórmula é visualmente semelhante à fórmula escolar da equação linear y = kx + b, cujo gráfico é uma linha reta.

Qualquer linha reta pode ser restaurada em apenas dois pontos. E, ao mesmo tempo, realmente não queremos que, em dois pares de texto sem formatação - texto cifrado, você possa restaurar a chave de criptografia. Para isso, camadas especiais são adicionadas aos algoritmos de criptografia responsáveis ​​pela não linearidade. Essas camadas são projetadas para impedir a possibilidade de calcular o relacionamento entre texto simples, texto cifrado e chave.

Sua qualidade é crítica para a segurança do algoritmo.

O que é o SBox?

Esta é a mesma camada não linear. Uma função que, no caso do Grasshopper e de outras cifras, mapeia exclusivamente um byte para outro byte.

Muitas vezes, é definido por uma tabela de correspondência simples, por exemplo:



Porque, caso contrário, não pode ser descrito. À primeira vista.

Por que o SBox é importante?

Porque é a única função não linear em toda a cifra. Sem ele, quebrar uma cifra não será fácil, mas muito simples, apresentando-a como um sistema de equações lineares. Portanto, a função de substituição tem muita atenção. Existem até exercícios práticos para hackear o AES com o SBox linear.

Por que você não pode criar um SBox seguro?

O problema é que a criptografia não é uma ciência exata. O único algoritmo de criptografia comprovadamente forte é o uso único . Todo o resto são tentativas tímidas de se encaixar no leque de conhecimentos disponíveis, cujo conjunto não é tão grande.
Não sabemos ao certo se as curvas RSA ou AES ou elípticas são resistentes, mas sabemos que essas e essas coisas definitivamente não são possíveis . Tudo no meio é criatividade.

Daí a paranóia constante sobre as várias "constantes mágicas" e outros pontos que os autores dos algoritmos apresentam como seguros, mas não podem provar isso .

Como criar SBox?

As várias variantes do SBox são 256!, Que é aproximadamente 2 ¹⁶⁸⁴ . A escolha é grande e, ao longo dos anos de análise de criptografia, métricas e características foram desenvolvidas que o SBox deveria ter, resistente aos ataques conhecidos de hoje. Obviamente, os criadores das tabelas pensam nos próximos anos e tentam criar substituições que seriam resistentes até aos ataques inventados em 5 a 10 anos. Mas isso é mais da categoria de magia e xamanismo.

Existem duas abordagens fundamentalmente diferentes para criar o SBox.

O primeiro é uma pesquisa aleatória. Os desenvolvedores geram tabelas aleatórias, examinam suas características e filtram aquelas que não são adequadas. Isso continua até que os desenvolvedores estejam satisfeitos com o que encontraram.

No mundo civilizado, isso acontece, por exemplo, da seguinte maneira:

1. Algum valor inicial é obtido, por exemplo, uma citação de um livro ou dos primeiros dígitos do Pi
2. Executa um hash
3. O resultado do hash é usado como dados para formar o SBox.
4. Se o SBox não couber, pegue o hash atual e retorne à etapa 2

Portanto, qualquer pessoa pode reproduzir esse processo e garantir que sejam atendidos pelo menos os requisitos mínimos para a pesquisa pseudo-aleatória.

Você sabe para onde vão as sementes do principal algoritmo simétrico do país? Perdido ! Eu pensei que eles não os informaram especificamente, o segredo está lá ou algo assim, mas colegas russos do EuroCrypt disseram que durante o desenvolvimento do algoritmo em 2007, por algum motivo, ninguém pensou que seria necessário justificar o design da tabela de pesquisa, e os valores a partir dos quais surgiram foram eternos. perdido. A história é linda, só não esqueça que o algoritmo foi criado não na escola, mas nas entranhas do FSB.

A segunda maneira é criar você mesmo o SBox, guiado pelo aparato matemático disponível. Foi o que os autores da AES fizeram e se saíram muito bem. Se compararmos a não linearidade do SBox AES, SM4 (padrão chinês) e Grasshopper (ele usa o mesmo SBox que o hash Stribog), o resultado não será favorável a este último

Não linearidade do AES (min, max) = (112,0, 112,0)
Não linearidade SM4 (min, máx) = (112,0, 112,0)
Não linearidade de Streebog (min, max) = (102,0, 110,0)

O código de cálculo de não linearidade usa a Transformada de Walsh e está disponível aqui.

Documentos

Eu tenho dois documentos da ISO. No primeiro, os designers do Grasshopper explicam como eles criaram o SBox; em outro, o comitê discute seus argumentos.



do primeiro documento, estamos interessados ​​em duas citações:



e



Espero que o tópico “O próprio Leo Perrin tenha surgido com a ideia de que os autores pesquisaram o SBox aleatoriamente” agora esteja fechado.

Das explicações dos designers, segue-se que

1. Eles realmente procuraram o SBox de maneira pseudo-aleatória (considerando os critérios de segurança)
2. Nenhuma estrutura oculta foi supostamente colocada nela.

E neste lugar eles estragaram tudo.

O que é uma estrutura?

Uma estrutura aplicada a uma tabela de pesquisa é um algoritmo que descreve esta tabela.

O documento mencionou AES. Mas a tabela de pesquisa para o AES foi originalmente criada não por pesquisa aleatória, mas com a ajuda de várias técnicas matemáticas que nos permitiram descrever uma camada não-linear com várias fórmulas . Aliás, essa é a singularidade da AES.

Pelo contrário, se você estiver procurando SBox aleatoriamente, não deve haver estruturas nele e o problema com o Grasshopper SBox é que as palavras dos projetistas de algoritmos são muito diferentes dos fatos. Eu escrevi sobre a estrutura de um gafanhoto chamado TKLog em um artigo anterior , desta vez vamos falar sobre estruturas em geral.

Complexidade de Kolmogorov

Este é o resultado da pesquisa do último artigo de Leo Perrin sobre o Grasshopper.

O principal contra-argumento dos artigos sobre estruturas no Grasshopper SBox é que "em quase qualquer SBox você pode encontrar alguma estrutura, se quiser." E "mesmo que a probabilidade de encontrar a estrutura que Leo encontrou seja insignificante, se houvesse outro SBox, haveria outro, também com uma probabilidade insignificante".

Digamos que seja assim. Mas Como se viu, é possível derivar um certo "grau de estrutura" do SBox, que não depende da probabilidade de cair em uma ou outra estrutura.

Mas isso depende do tamanho do algoritmo necessário para gerar este SBox!

Isso é chamado de complexidade de Kolmogorov.

Se você imaginar o SBox como uma sequência de bytes, no caso de uma sequência aleatória, não deve haver um algoritmo que gere essa sequência e, ao mesmo tempo, seja menor que essa sequência.

Para um gafanhoto

Portanto, o tamanho do SBox é de 256 bytes. Aqui está uma versão legível do código de autoria de Leo Perrin, que implementa a tabela Grasshopper. Na entrada está o byte de origem, na saída está o byte correspondente do Grasshopper SBox. A principal condição para esse algoritmo é a proibição do uso de estruturas de linguagem ou plataforma que reduzam enganosamente o tamanho do programa. Por exemplo, se em algum lugar dentro da biblioteca padrão houver uma constante contendo metade do SBox, você não poderá usá-lo.

Desafio - escreva um programa que será menor que o SBox.

unsigned char p(unsigned char x){
    unsigned char
        s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
        k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};    
    if(x) {
        unsigned char l=1, a=2;
        while(a!=x) {
            a=(a<<1)^(a>>7)*29;
            l++;
        }
        if (l%17) return 252^k[l%17]^s[l/17];
        else return 252^k[l/17];
    }
    else return 252;
}

, SBox «» , , SBox. 416 , .

, :

p(x){
  unsigned char
      *t="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",
      a=2,l=0,b=17;
  while(x && (l++,a^x)) a=2*a^a/128*29;
  return l%b ? t[l%b]^t[b+l/b]^b : t[l/b]^188;
}

196 , 23% SBox. . , :

p(x){char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8";int l=256,b=17;while(--l*x^l)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

SBox :

int main() {
   for(int i = 0; i < 256; i++){
       if (i % 16 == 0){
           printf("\n");
       }
    printf("%d, ", (unsigned char)p(i));    
   }
}

, SBox .
153 . — ANSI, 7 , 8. 1071 ~134 . , .

, Cortex-M4 80 ( ).

, 64 .

, ?

, , .

, 4 Sbox, SBox , .

. , « » AES (60 , GolfScript), .

— . , — .

— SBox. , . , .

( ), , 4 , SBox. , — , . 4 , , , . , , , 11 , , . , side project ¯\_(ツ)_/¯.

ISO . . .

, , , SBox . . , , .

Curve25519 Daniel J. Bernstein Tanja Lange, ISO . , , , SBox. . .

, .

, . ISO, , EuroCrypt.

, ( SBox), RFC 7801, .

, SBox, (, ). , , , . V2 .

. , « , ».

, ? , AES - .

, , , , . .

Challenge!

SBox , , . , 256 . . . — , .

— 58 Stax. « » SBox.

.