Crypton

Crypton é um algoritmo de cifra de bloco que representa um candidato para o Advanced Encryption Standard (AES). É um sucessor da cifra Square , uma cifra de bloco criada por Vincent Rijmen e Joan Daemen, que teve sua primeira publicação em 1997. A estrutura de Square é uma rede de substituição permutação com 8 etapas, operando com blocos de 128 bits e usando uma chave também de 128 bits . Os criadores de Square também foram responsáveis pela criação do algoritmo Rijndael que seria considerado o novo padrão AES.

O algoritmo foi desenvolvido por Chae Hoon Lim em 1998 que na época era diretor de pesquisa no centro de Criptografia e Segurança de Rede da Future Systems Inc. Desde de 2002 trabalha como professor-assistente no departamento de engenharia para internet na Universidade de Sejong (Koréia do Sul).

A estrutura de Crypton é similar a de Square, também processa seus blocos de dados em uma matriz 4x4 byte. No entanto, Crypton se difere de Square em sua permutação de bits e a forma como seus S-boxes são construídos, componentes que são parte essencial no design das cifras de bloco. Chae Hoon Lim resolveu utilizar a estrutura de Square, considerando sua eficiência em processadores modernos que fazem uso de cada vez mais paralelismo.

Uma desvantagem dessa estrutura é que mais registros são necessários para lidar com variáveis intermediárias. A permutação de bits $\pi$ tem uma ordem de difusão de 4, enquanto a multiplicação da matriz MDS em Square tem a ordem de difusão de 5. No entanto, sua permutação de bits é bem simples e eficiente (é implementada utilizando apenas XOR's) e, já que sua involução, isto é, $\pi =\pi ^{-1}$, o processo de criptografia e descriptografia pode ser idêntico. Existem várias opções para um vetor máscara M para $\pi$ .

Atualmente não existem nenhuma patente para o Algoritmo Crypton, sendo considerado de domínio público.

Princípios do Crypton

O intuito do projeto principal era:

• Criar uma cifra simples de ser implementada e usada;
• Utilizar conceitos na época de criptografias avançada (as S-boxes);
• Criar uma linguagem que poderia ser usada como gerador de números aleatórios e Stream Cipher.
• Criar um candidato para o Advanced Encryption Standard (AES).

Estrutura de funcionamento

Como foi já foi dito, a estrutura de Crypton é semelhante a de Square, também processa seus blocos de dados em uma matriz 4x4 byte. A rodada de transformação do Crypton funciona em 4 etapas paralelas, são elas: substituição de byte, permutação de byte, transposição de byte e adição da chave. Essas etapas são realizadas 12 vezes, isto é, 12 rodadas, e em cada roda uma subchave é gerada a partir da chave do usuário.

O processo de criptografia e descriptografia pode ser idêntico, exceto que subchaves diferentes são aplicada.

Na Figura 1, podemos ver como é a estrutura de fucionamento de Crypton.

Figura 1: Estrutura de funcionamento do Crypton.

Funcionamento do algoritmo

Crypton criptografa blocos de 128 bits com uma chave de até 256 bits, utilizando 12 rodadas (r) para o processo de criptografia. O algoritmo consiste da função de criptografia em si e um keyschedule que deriva (r + 1) subchaves de 128 bits da chave e função de criptografia. A função de encriptação consiste de r rodadas rodeadas por uma transformação dos valores de entrada (definidos por um XOR entre o texto base e a primeira subchave) e uma transformação de valores na saída (definida como um modelo fixo 2 de mapeamento linear).

Vamos representar um bloco A de 128 bits por:

$A={\begin{pmatrix}a_{0,3}&a_{0,2}&a_{0,1}&a_{0,0}\\a_{1,3}&a_{1,2}&a_{1,1}&a_{1,0}\\a_{2,3}&a_{2,2}&a_{2,1}&a_{2,0}\\a_{3,3}&a_{3,2}&a_{3,1}&a_{3,0}\\\end{pmatrix}}{\begin{matrix}A[0]\\A[1]\\A[2]\\A[3]\\\end{matrix}}$

Onde cada $a_{i,j}$ é um byte.

Uma rodada consiste em uma substituição de bytes $\gamma$ seguida por uma permutação de bits , uma transposição de bites $\tau$ e a adição de uma subchave $\sigma$. $\gamma$ ($\gamma _{o}$ para rodadas ímpares e $\gamma _{e}$ para rodadas pares) usa duas S-boxes $S_{0}$ e $S_{1}$. Só será preciso descrever $\gamma _{o}$ visto que para se obter o $\gamma _{e}$ é necessário apenas trocar $S_{0}$ e $S_{1}$.

${\begin{pmatrix}b_{0,3}&b_{0,2}&b_{0,1}&b_{0,0}\\b_{1,3}&b_{1,2}&b_{1,1}&b_{1,0}\\b_{2,3}&b_{2,2}&b_{2,1}&b_{2,0}\\b_{3,3}&b_{3,2}&b_{3,1}&b_{3,0}\end{pmatrix}}{\overleftarrow {\gamma _{o}}}$ ${\begin{pmatrix}S_{1}(a_{0,3})&S_{0}(a_{0,2})&S_{1}(a_{0,1})&S_{0}(a_{0,0})\\S_{0}(a_{1,3})&S_{1}(a_{1,2})&S_{0}(a_{1,1})&S_{1}(a_{1,0})\\S_{1}(a_{2,3})&S_{0}(a_{2,2})&S_{1}(a_{2,1})&S_{0}(a_{2,0})\\S_{0}(a_{3,3})&S_{1}(a_{3,2})&S_{0}(a_{3,1})&S_{1}(a_{3,0})\\\end{pmatrix}}$

$\pi$($\pi _{o}$ para rodadas ímpares, $\pi _{e}$ para rodadas pares) é uma permutação de bits. Só é necessário descrever os efeitos de $\pi _{o}$ para rodadas pares visto que, os efeitos de $\pi _{e}$ são similares. $\pi _{o}$ é dado por:

$T=A[0]\oplus A[1]\oplus A[2]\oplus A[3],$

$B[0]\leftarrow (A[0]\wedge MI_{0})\oplus (A[1]\wedge MI_{1})\oplus (A[2]\wedge MI_{2})\oplus (A[3]\wedge MI_{3})\oplus T,$

$B[1]\leftarrow (A[0]\wedge MI_{1})\oplus (A[1]\wedge MI_{2})\oplus (A[2]\wedge MI_{3})\oplus (A[3]\wedge MI_{0})\oplus T,$

$B[2]\leftarrow (A[0]\wedge MI_{2})\oplus (A[1]\wedge MI_{3})\oplus (A[2]\wedge MI_{0})\oplus (A[3]\wedge MI_{1})\oplus T,$

$B[3]\leftarrow (A[0]\wedge MI_{3})\oplus (A[1]\wedge MI_{0})\oplus (A[2]\wedge MI_{1})\oplus (A[3]\wedge MI_{2})\oplus T,$

Onde: $MI_{0}=0xc0300c03$ $MI_{1}=0x03c0300c$ $MI_{2}=0x0c03c030$ $MI_{3}=0x300c03c0$

Nós podemos notar que se omitirmos a adição com T, $\pi$ resultará em permutações de 4 palavras de 2 bits em cada uma das 16 colunas de palavras de 2 bis na matriz A.

A transposição $\tau$ apenas consiste em trocar todos os pares de bytes $a_{i,j}$ e $a_{j,i}$ na matriz A e a adição da chave $\sigma _{k}$ consiste apenas de XOR entre A e uma subchave de 128 bits K.

${\begin{matrix}A[0]\\A[1]\\A[2]\\A[3]\\\end{matrix}}{\begin{pmatrix}a_{0,3}&a_{0,2}&a_{0,1}&a_{0,0}\\a_{1,3}&a_{1,2}&a_{1,1}&a_{1,0}\\a_{2,3}&a_{2,2}&a_{2,1}&a_{2,0}\\a_{3,3}&a_{3,2}&a_{3,1}&a_{3,0}\\\end{pmatrix}}{\overrightarrow {\tau }}$ ${\begin{matrix}B[0]\\B[1]\\B[2]\\B[3]\\\end{matrix}}{\begin{pmatrix}a_{3,0}&a_{2,0}&a_{1,0}&a_{0,0}\\a_{3,1}&a_{2,1}&a_{1,1}&a_{0,1}\\a_{3,2}&a_{2,2}&a_{1,2}&a_{0,2}\\a_{3,3}&a_{2,3}&a_{1,3}&a_{0,3}\\\end{pmatrix}}$

$B[0]\leftarrow A[0]\oplus K[0],$

$B[1]\leftarrow A[1]\oplus K[1],$

$B[2]\leftarrow A[2]\oplus K[2],$

$B[3]\leftarrow A[3]\oplus K[3],$

Criptoanálise

A seguir serão apresentados dois ataques ao Crypton.

Truncated Differential Attacks on 8-Round Crypton

Ataques em um Crypton de 7 e 8 rounds, com a primeira adição da subchave $\sigma _{K0}$ e a transformação final $\phi _{e}$. Vai ser apresentado primeiramente o algoritmo para atacar o Crypton de 7 rounds e depois o algoritmo usando diferentes tabelas de distribuição para as S-boxes. Usando o segundo algoritmo podemos atacar a cifra Crypton até 8 de seus 12 rounds.

O algoritmo para o ataque do Crypton de 7 rounds é realizado da seguinte maneira:

1. Prepare $2^{65}$ conjuntos de $2^{32}$ $P_{i}^{j}$, j = 0, ..., $2^{65}-1$, i = 0, ..., $2^{32}-1$ que tenham todos os possíveis valores em bytes (1, 2),(1, 0),(3, 2) e (3, 0) e são constantes em outros bytes. Criptografe os conjuntos para ter $2^{65}$ conjuntos de $2^{32}$ textos cifrados $C_{i}^{j}$.
2. Descriptografe os $2^{65}$ conjuntos de $C_{i}^{j}$ através de $\pi _{o}^{-1}\circ \pi _{e}^{-1}\circ \tau ^{-1}(=\pi _{o}^{-1}\circ \tau ^{-1}\circ \tau ^{-1}pi_{e}^{-1}\circ \tau ^{-1}pi_{e}^{-1}\circ \tau ^{-1})$, e então subtraia os conjuntos de $2^{65}$ para conseguir $C_{i}^{j*}$ (cada $C_{i}^{j*}$ representa 128 bits depois da adição da chave $\sigma _{K_{eq}^{7}}$ no sétimo round).
3. Inicialize um vetor de $2^{128}$ contadores correspondentes a possíveis subchaves para $(K_{1,2}^{0},K_{1,0}^{0},K_{3,2}^{0},K_{3,0}^{0},K_{eq,0,2}^{6},K_{eq,0,0}^{6},K_{eq,2,2}^{6},K_{eq,2,0}^{6},K_{eq,0,3}^{7},K_{eq,0,2}^{7},K_{eq,0,1}^{7},K_{eq,0,0}^{7},K_{eq,2,3}^{7},K_{eq,2,2}^{7},K_{eq,2,1}^{7},K_{eq,2,0}^{7}).$.
4. Para cada subchave de 32 bits de valor $K^{0}$ faça o seguinte:
   1. Parcialmente criptografe $P_{i}^{j}$ através das 4 S-boxes ativas no round 1, e subtraia o valor que obtemos em $P_{i}^{j*}$ (cada $P_{i}^{j*}$ representa dados de 128 bits depois da parte não linear $\gamma _{o}$ no round 1), e classificar cada conjunto de bytes (1,2), (1,0), (3,2) e (3,0) e escolher o pares do texto $(P_{i1}^{j},P_{i2}^{j})$, tal que, a diferença entre $P_{i1}^{j}$ e $P_{i2}^{j}$ são de $(cc_{x},cc_{x})$ de Tipo d.
   2. Verifique se $C_{i1}^{j*}$ e $C_{i2}^{j*}$ tem diferença zero nas linhas 1 e 3.
   3. Para cada subchave de 64 bits de valor $K_{eq}^{7}$ faça o seguinte:
      1. Parcialmente descriptografe os pares $(C_{i1}^{j*},C_{i2}^{j*})$ através $\pi _{e}^{-1}\circ \tau ^{-1}\circ \gamma _{o}^{-1}\circ \sigma _{K_{eq}^{7}}^{-1}$ nos 8 bytes ativos, e subtraia o valor que obtemos em $C_{i}^{j**}\$(cada\$C_{i}^{j**}$ representa dados de 128 bits depois da parte de adicionar a chave $\sigma _{K_{eq}^{6}}$ no round 6).
      2. Verifique que $C_{i1}^{j**}$ e $C_{i2}^{j**}$ tem diferença 0 no bytes (1,2), (1,0), (3,2) e (3,0).
      3. Para cada subchave de 32 bits de valor $K_{eq}^{6}$, parcialmente descriptografe os pares $(C_{i1}^{j**},C_{i2}^{j**})$ através $\gamma _{e}^{-1}$ nas 4 S-boxes ativas, e verifique que a diferença entre decriptar dois textos é de $(\delta _{i},\delta _{j})$ de Tipo b onde $(\delta _{1},\delta _{2})(\in D_{1}xD_{1}ouD_{2}xD_{2})$. Se assim for, aumentar o contador correspondente por 1.
5. Cheque todos os contadores, e saída de subchaves em que seu valor seja maior ou igual a 6.

A complexidade das informações é $2^{97}$ textos-base escolhidos. Devido ao tamanho e quantidade dos textos escolhidos e os $2^{128}$ contadores para subchaves, o algoritmo parece requerer um número de bytes maior de memória. No entanto, se lidarmos com o algoritmo delicadamente, a quantidade de memória necessária pode ser reduzida para $2^{39}(=2^{32}\ast 2\ast 16)$ bytes. A chance de sucesso dessa técnica é de $0.75(\approx 0.75\ast (\Sigma _{i=0}^{5}(_{2^{96}}C_{i}\ast (2^{-119.2})^{i}\ast (1-2^{-119.2})^{2^{96-i}}))^{2^{128}})$.

Agora descrevemos o segundo algoritmo para atacar o Crypton de 7 rounds, é importante primeiro adicionar o passo de pré-computação:

Prepara tabelas de distribuição de diferenças para as 4 S-boxes e armazena os possíveis pares de suas entradas em uma tabela já processada, denominada tabela A, e prepara outra grande tabela especial de processamento, denominada Tabela B, associada com as diferenças de entrada e saída de $\gamma$ nos rounds 6 e 7. Para criar a tabela B primeiro processamos $2^{32}$ (valor de entrada e saída) pares de $\tau \circ \pi _{e}$ onde os valores de entrada de $\tau \circ \pi _{e}$ tem todos os valores possíveis em bytes (0,2), (0,0), (2,2) e (2,0) e são zero em outros bytes. (Note que os valores de entrada de $\tau \circ \pi _{e}$ representam as diferenças de saída de $\gamma _{e}$ no round 6, e os valores de saída de $\tau \circ \pi _{e}$ representam as diferenças de entrada de $\gamma _{0}$ no round 7). A tabela B consiste de um vetor $2^{32}x2^{64}$ em que suas linhas correspondem a (valor de entrada, valor de saída) pares de $\tau \circ \pi _{e}$ no round 6, e as colunas correspondem a possíveis diferenças de saída de $\gamma _{0}$ no round 7 (ou seja, as colunas correspondem a todos as possíveis diferenças na linha 0 e 2) Se uma entrada do vetor de $2^{32}x2^{64}$ for designada por um (I,O) par de $\tau \circ \pi _{e}$ e a diferença de saída $\Delta$ de $\gamma _{0}$ no round 7, nós armazenamos nessa entrada todos os possíveis pares que satisfazem $(\delta _{1},\delta _{2}){\overrightarrow {\gamma _{e}}}I$ na tabela A onde $(\delta _{1},\delta _{2})(\in D_{1}xD_{1}ouD_{2}xD_{2})$ representa qualquer diferença do tipo B, junto com todos os possíveis pares que satisfazem: $O{\overrightarrow {\gamma _{e}}}\Delta$ na tabela A.

1. Realize os passos 1,2 e 3 do primeiro algoritmo.
2. De cada conjunto, geramos $2^{63}$ pares $(C_{i1}^{j*},C_{i2}^{j*})$ e verifique que $C_{i1}^{j*}$ e $C_{i2}^{j*}$ tem diferença 0 nas linhas 1 e 3.
3. Para cada par de texto base $(P_{i1}^{j},P_{i2}^{j})$ relacionados a $(C_{i1}^{j*},C_{i2}^{j*})$ que passaram no teste acima faça o seguinte:
   1. Obtenha o valor da subchave $K^{0}$ de 32 bits usando a tabela A.
   2. Para cada par $(C_{i1}^{j*},C_{i2}^{j*})$, e para cada $\tau \circ \pi _{e}$ faça o seguinte:
      1. Obtenha os valores da subchave $K_{eq}^{7}$ de 64 bits usando a tabela B.
      2. Usando a subchave $K_{eq}^{7}$ de 64 bits obtida, parcialmente descriptografe $(C_{i1}^{j*},C_{i2}^{j*})$ através de $\pi _{e}^{-1}\circ \tau ^{-1}\circ \gamma _{o}^{-1}\circ \sigma _{K_{eq}^{7}}^{-1}$ nos 16 bytes ativos, e obtenha os valores da subchave $K_{eq}^{6}$ de 32 bits usando os dois textos descriptados e a tabela B. Aumente o número de contadores relacionados a chave obtida por 1.
4. Cheque todos os contadores, e saída de subchaves em que seu valor seja maior ou igual a 6.

Esse método foi definido como 99\% eficaz em criptografias de até 8 rounds, no entanto é interessante constar que o recomendado para o Crypton é 12 rounds. O que tornaria essa técnica ineficaz em altos níveis de rounds de criptografia.

Stochastic Attack Using Differential Properties

Esse é um ataque em uma cifra de Crypton completa em 8 rounds.

Apresentamos aqui um ataque em uma cifra encriptada com 6 rounds. Usando leis Heuristicas, podemos calcular as probabilidades das maiores diferenças em vários rounds. Em particular obtemos a seguinte figura para os 6 rounds internos de Crypton: se a diferença de entrada é (18, 18) par dos valores de $\Delta _{1}$, a probabilidade que a saída $(\delta _{1},\delta _{2})$ pareie com $(\delta _{1},\delta _{2})\in D_{1}xD_{1}$ é $2^{-120.72}$. Da mesma forma, se a entrada é o (128, 128) par de valores $D_{2}$ a probabilidade que o valor de saída seja um $(\delta _{1},\delta _{2})$ par dos valores de $D_{2}$ é $2^{-112.62}$.

Esse resultado interno calculado com 6 rounds pode ser um usado em um ataque a uma cifra de 8 rounds. Devido a adição tardia da chave $\sigma$ no primeiro round interno, podemos controlar diferenças na saída da primeira ocorrência de $\gamma$ , e assim o primeiro round pode ser tratado como apenas uma "permutação inicial" sem chave. Um ataque 1R permite também ganhar o último round. Logo podemos explorar as propriedades dos 6 últimos rounds e escolher um ataque via plaintext para obter informações sobre a última chave do round 8.

Para obter pares eficientes dos textos-base cuja diferença $\Delta _{2}=(128,128)$ é igual à primeira ocorrência de $\gamma$, agrupamos os textos-base em estruturas. Dois elementos de 128 bits pertencem a mesma estrutura se e somente se, suas imagens de $\gamma$ forem iguais exceto por alguns dos 16 bits de $\Delta _{2}$. Cada estrutura tem $2^{16}$ elementos. Sabemos disso, se dois textos-base X e X' pertecem a mesma estrutura, com probabilidade $2^{-112.62}$, as estradas correspondentes para o oitavo round são da forma de $Y$ e $Y\oplus \Delta _{2}$. Apenas consideramos aqueles pares $(X,X')$ como o texto cifrado $C\oplus C'$ e checando se $Y\oplus Y'$ tem a forma correta. Alguns pares são "falsos alarmes" passando pela condição de filtro mas não pertencendo em nenhum conjunto. Uma vez selecionados os 'bons" pares, nós testamos os possíveis valores da chave que vai ser usada no final do oitavo round. O valor candidato que aparecer em maior quantidade é quase sempre o correto. Obtemos 4 bytes de informação em $K_{8}$.

Podemos passar pela última transformação $\phi _{e}$ porque ela não muda o valor de saída do oitavo round. Levando em consideração a primeira adição de uma chave $\sigma _{0}$ apenas aumenta o número de falsos alarmes. O número de textos bases para cifras é $N=2^{112.62}$. Mas nós precisamos ter uma segurança contra falsos alarmes. Definimos que tirar $N=2^{114.62}$ é o suficiente. Então podemos obter 32 bits de informação da $K_{8}$ cifrando $N=2^{114.62}$ pares $X$ e $X\oplus \Delta$ na versão completa de Crypton com 8 rounds. A complexidade desse ataque é $N=2^{114.62}$ encriptações e $2^{96}$ computações adicionais.

Esse ataque é mais rápido do que busca exaustiva e ataques diferenciais. De fato, pode mostrar que a probabilidade da melhor caracteristica de um ataque de 8 rounds é $2^{-120}$.

Na Prática

Nesta seção será apresentado o uso atual do algoritmo de Crypton na prática.

Implementando Crypton em máquinas Little Endian

Já que a especificação original descreve Cryptonde acordo com a convenção de máquinas Little Endian, nós primeiros revisamos uma implementação baseada na convenção nas Little Endian, e usamos de referência para a implementação em uma máquina Big Endian.

Em máquinas Little Endian, uma mensagem de 16 bytes é mapeada como dado interno. A primeira palavra de 4 bits é ordenada por convenção Little Endian e colocada na primeira linha de uma matriz 4 x 4 e a próxima palavra de 4 bytes na segunda linha e assim por diante. Note que isso é equivalente a converter uma string de 16 bytes em um vetor de 4 palavras de 4 bytes.

O texto-base que é representado por uma matriz 4 x 4 é agora sujeito a uma encriptação como nas definições da documentação do Crypton. Depois que a encriptação está completa, a cifra internamente representada como uma matriz 4X4 deve ser transformada novamente em uma mensagem de saída de 16 bytes, pelo processo reverso de encriptação. Nessa especificação Little Endian, o byte do topo a direita serve como a origem da matriz 4 x 4 em termos de ordem.

Crytpon aceita uma chave de 32 bytes. Esses bytes da chaves são mapeados em matrizes de 4 x 4 bytes, uma com bytes pares e outra com ímpares. Essas duas matrizes de chaves de usuários estão sujeitos a expansão de chave (que consiste em preencher os espaços vazios das chaves com 0's) para produzir duas matrizes de chaves expandidas. Então chaves são geradas suscetivamente atualizando a estruturação das chaves.

Implementando Crypton em máquinas Big Endian

Na convenção Big Endian, a ordem dos bytes, quando lendo uma palavra de 4 bytes da memória como um inteiro não definido, é exatamente o reverso da Little Endian. A reorganização dos bytes consume ciclos não negligenciais em implementação de software. Logo seria interessante para um algoritmo permitir reestruturação dos processos lógicos internos para evitar esse problema. Isso é possível em Crypton, já que ele possui essencialmente, porque ele processa a mensagem de entrada byte por byte. Para isso, no entanto, nós temos que rearranjar o processamento interno dos componentes para que o os dados de saída sejam os mesmos que antes.

Nesse ambiente, uma mensagem de entrada de 16 bytes é mapeada em uma matriz interna de 4 x 4 palavras de 4 bytes. Nesse caso o byte do topo esquerdo está servindo como o byte de origem da matriz 4 x 4 em termos de ordem., o que difere o Big Endian do Little Endian, isto é, a diferença do Big Endian e o Little Endian é a ordem dos byte numa palavra de 4 bytes. Depois de completa o processo de criptografia/descriptografia, a matriz 4 x 4 deve ser transformada de volta em uma mensagem de 16 bytes usando o processo reverso de transformação.

Para obter o mesmo resultado na criptografia/descriptografia como em uma convenção Little Endian, é necessário ajustar as operações básicas $(\gamma ,\pi$ e $\tau )$ de uma forma que cada byte esteja sujeito as mesmas operações que uma convenção Little Endian.

A chave interna do processo também deve estar sujeita a mudança de acordo com a ordem de bytes Big Endian. Note que a chave também tem componentes de uma transformação de round. Para garantir o mesmo processamento interno em cada byte como em uma máquina Little Endian, é necessário rearranjar a chave de usuário e produzir rounds de chave na ordem de bytes do Big Endian.