Mostrar código-fonte de CAST-256

{{Wikificação|data=junho de 2016}}
'''Cast''' (Carlisle Adams and Stafford Tavares) é uma família de cifra de blocos. Nessa família se encontra a cifras de blocos individuais conhecidas como, CAST-64, CAST-128 (ou CAST5) e CAST-128 (candidato ao AES). O [[algoritmo]] encontrado na família CAST é baseado no algoritmo DES (utlizada a rede de Feistel e é conhecido como rede de substituição-permutação). CAST usa S-caixas fixas, mas são consideravelmente maiores do que as utilizadas em DES. Essas S-caixas foram cuidadosamente projetadas para ser não-linear e resistente à criptoanálise.

A cifra '''CAST-256''' foi derivada da cifra CAST-128 que é um algoritmo de cifra de bloco, sendo criado em 1996 por Carlisle Adams e Stafford Tavares. O CAST-128 é um algoritmo de Feistel, com 12 a 16 iterações (rodadas) da etapa principal, tamanho de bloco de [[64 bits]] e chave de tamanho variável (40 a 128 bits, com acréscimos de 8 bits). Os 16 rounds de iteração são usados quando a chave tem comprimento maior que 80 bits. <ref name = "oliveira">{Ronielton Rezende Oliveira. Criptografia simétrica  e  assimétrica - Os  principais  algoritmos de cifragem. Segurança  Digital  [Revista  online],31:11{15, 2012}</ref>

O algoritmo AES (Advanced Encryption Standard) é o principal padrão de criptografia simétrica atual. <ref name="daemen">{Joan Daemen and Vincent Rijmen. The design of Rijndael: AES-the advanced encryption standard. Springer Science & Business Media, 2013.}</ref> Vários algoritmos participaram do processo para escolha do AES. <ref name="daemen">{Joan Daemen and Vincent Rijmen. The design of Rijndael: AES-the advanced encryption standard. Springer Science & Business Media, 2013.}</ref> Para candidatura ao AES surgiu a necessidade de aumentar o tamanho do bloco de cifragem. Blocos esses que passaram a ter 128 bits. A partir disso, deu-se inicio a cifra CAST-256.

A cifra '''CAST-256''' além de ter a característica de blocos maiores, agora com 128 bits, também possui chaves de 128, 192 ou 256 bits e 48 iterações (12 quad-rounds) e faz uso de uma rede de Feistel "generalizada".


== Princípios do CAST-256 ==

* Em 1988-1990 começou o processo de criação de design para cifras simétricas, dando inicio à funções booleanas, Caixas-S, funções de rodadas, rotinas de chaves.
* Em 1992-1993 o nome CAST foi introduzido à família e especificado diversos parametros, dando inicio a criação do CAST-1 e posteriormente o CAST-2.
* Em 1993-1995 ocorreu a modificação da rotina de chave e partir disto deu-se o CAST-3 com uma maior foco em função de rodada e no design das Caixas-S. A criação preliminar das boxes-S caracteriza a CAST-4 e quando o design das boxes-S foram finalizadas criou-se a CAST-5 conhecida como CAST-128. 
* Em 1997 foi publicada a cifra CAST-128 (RFC 2144).
* Em 1998 deu inicio a expansão da CAST-128 para a CAST-256 que foi submetida como candidato à cifra de bloco AES (Advanced Encryption Standard.

==Estrutura de funcionamento==

A cifra CAST-256 faz uso de rede de Feistel, sendo o algoritmo desta rede baseado em:

* Seja <math>F</math> a função que será computada a cada rodada e seja <math>k_{0}, k_{1}, ..., k_{n}</math> as subchaves utilizadas nas rodadas <math>0, 1, ..., n</math> respectivamente. Então a operação básica realizada para encriptar o bloco de entrada é a seguinte:
** Divida o bloco de entrada em duas metades (esquerdo e direito) que são processadas independentemente e para cada rodada <math>i = 0, 1, ..., n</math> compute:
:::<math> Esquerda_{i+1} = Direita_{i}</math>

:::<math> Direita_{i+1} = Esquerda_{i} \oplus F(Direita_{i}, k_{i})</math>

* A operação em cada rodada <math>i = n, n-1, ..., 0</math> utilizada para a decriptação do texto cifrado <math>(Esquerda_{i+1}, Direita_{i+1})</math> é:

::<math>Direita_{i} = Esquerda_{i+1}</math>

::<math>Esquerda_{i} = Direita_{i+1} \oplus F(Esquerda_{i+1}, k_{i})</math>

* Ao final das operações, obtem-se o texto em claro novamente. 

==Funcionamento do algoritmo== 

Na Figura 1 conseguimos ver como é a estrutura de funcionamento da cifra CAST-256 que é bastante parecida com a de Feistel e se dá da seguinte maneira:

[[Ficheiro:Cast-256.png|miniaturadaimagem|direita|Figura 1: CAST-256]]

Dado um bloco de entrada de 128-bits, divida-o em quatro blocos de 32-bits, denotado por <math>\beta = (A, B, C, D)</math>. Seja o quad-round definido pelas seguintes operações de encriptação: <math>\beta \leftarrow Q_{i}(\beta)</math>.<ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref> 

::<math>C = C \oplus f_{1}(D, k_{r0}(i), k_{m0}(i))</math>

::<math>B = B \oplus f_{2}(C, k_{r1}(i), k_{m1}(i))</math>

::<math>A = A \oplus f_{3}(B, k_{r2}(i), k_{m2}(i))</math>

::<math>D = D \oplus f_{1}(A, k_{r3}(i), k_{m3}(i))</math>

quando <math>k_{rj}(i)</math> e <math>k_{mj}(i)</math> são gerados pelo algoritmo de geração de chave do CAST-256 (mais detalhes sobre o algoritmo de geração de chaves e sobre as funçoes <math>f_{1}, f_{2}, f_{3}</math> em <ref name="carlisle">Carlisle Adams and Jeff Gilchrist. The cast-256 encryption algorithm. Technical report, 1999.</ref>

O processo de decriptação se dá da seguinte maneira <math>\beta \leftarrow \overline{Q_{i}}(\beta)</math>.<ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref>

::<math>C = C \oplus f_{1}(D, k_{r0}(i), k_{m0}(i))</math>

::<math>B = B \oplus f_{2}(C, k_{r1}(i), k_{m1}(i))</math>

::<math>A = A \oplus f_{3}(B, k_{r2}(i), k_{m2}(i))</math>

::<math>D = D \oplus f_{1}(A, k_{r3}(i), k_{m3}(i))</math>

== Descrição do algoritmo CAST-256 ==

Seja <math>\beta</math> = 128-bits de bloco de entrada (texto em claro), temos o seguinte código de encriptação que corresponde ao esquema dito na seção anterior.

<syntaxhighlight lang="C">
for(i = 0; i < 6; i++)
    Beta <- Q[i](Beta) 
for (i = 6; i < 12; i++) 
    Beta <- Q_barra[i](Beta)
</syntaxhighlight>


A saída desse algoritmo é o bloco de entrada cifrado <math>\beta</math> de 128-bits.

A cifra CAST-256 faz uso de uma chave primária k de 256-bits. Considerando que a descriptografia é idêntica a criptografia, exceto que o conjunto de entradas das chaves <math>k_{r}(i), k_{m}(i)</math> na quad-round são derivadas de k e são usada em ordem inversa <ref name="sicast">SICAST. Cast-256 algorithm specification.</ref>, como se segue:

<syntaxhighlight lang="C">
for (i = 0; i < 12; i++)
{
    k_{rnovo}(i) = k_{r}(11-i)
    k_{mnovo}(i) = k_{m}(11-i)
}
</syntaxhighlight>

A rotina de geração de chaves do CAST-256 é dada pelo seguinte algoritmo <ref name="sicast">SICAST. Cast-256 algorithm specification.</ref>:

''Inicialização''

::<math>c_{m} = 2^{30} \sqrt{2} = 5A827999_{16}</math>

::<math>m_{m} = 2^{30} \sqrt{3} = 6ED9EBA1_{16}</math>

::<math>c_{r} = 19</math>

::<math>m_{r} = 17</math>

<syntaxhighlight lang="C">
for (i = 0; i < 24; i++){
    for(j = 0; j < 8; j++){
        tmj(i) = cm
        cm = (cm + mm) mod 2 ^ 32
        trj(i) = cr
        cr = (cr + mr) mod 32
    }
}
</syntaxhighlight>

''Rotina da chave''

<math>\kappa</math> = ABCDEFGH = chave primaria de 256 bits, K.

<syntaxhighlight lang="C">
for (i = 0; i < 12; i++){
    kappa <- omega(2i)(K)
    kappa <- omega(2i+)(K)
    kr(i) <- kappa
    km(i) <- kappa
}
</syntaxhighlight>

Detalhes sobre a especificação da função omega em <ref name="sicast">SICAST. Cast-256 algorithm specification.</ref>.

Nota:

:<math>(|K| = 128) -> (E = F = G = H = 0)</math>

:<math>(|K| = 160) -> (F = G = H = 0)</math>

:<math>(|K| = 192) -> (G = H = 0)</math>

:<math>(|K| = 224) -> (H = 0)</math>

== Criptoanálise ==

A ferramenta fundamental de um ataque linear é um diferenciador linear que consiste uma equação linear envolvendo pedaços de texto simples, texto cifrado e chave, segurando com probabilidade não uniforme. Essa discrepância entre a probabilidade de uma relação linear de uma cifra e  de um comportamento aleatório é chamado de viés. Normalmente, as relações lineares são derivados para cada componente individual em uma cifra. Além disso, as relações lineares são combinadas, levando a aproximações lineares de estruturas maiores, até alcançar múltiplas rodadas. Intuitivamente, aproximações lineares são realizadas de preferência sobre os componentes não lineares, tais como, as S-boxes. Seja a S-box S: <math>\mathbb{Z}_{2}^{n}\rightarrow \mathbb{Z}_{2}^{m}</math>, e duas cadeias de bits, <math>\Gamma X \in \mathbb{Z}_{n}^{2}</math> e <math>\Gamma Y \in \mathbb{Z}_{n}^{2}</math>, conhecido como máscaras de bits. A equação linear envolvendo os bits de entrada de <math>S</math>, designada por <math>\Gamma X</math>, e seus bits de saída designados por, <math>\Gamma Y</math> é <math>X \ast \Gamma X \oplus S[X] \ast \Gamma Y = 0</math>. A probabilidade para que essa relação seja verdadeira é <ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref>

::<math>P_{\Gamma X , \Gamma Y} = \frac{\#{X \in \mathbb{Z}_{2}^{n}|X . \Gamma X = S[X] . \Gamma Y}}{\#{X \in \mathbb{Z}_{2}^{n}}}</math>

Se <math>\Gamma X = \Gamma Y = 0</math>, então a máscara de bits é chamado trivial; caso contrário, ele é chamado de não-trivial. A tendência desta relação linear é <math>|P_{\Gamma X, \Gamma Y} - \frac{1}{2}|</math>. Uma lista exaustiva contendo todas as entradas e saídas de máscaras de bits de uma S-box S é chamada Tabela aproximação linear (LAT) de <math>S</math>. O LAT permite identificar os mais promissores (não-trivial) relações lineares para S, nomeadamente aqueles com maior viés. <ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref>  

O viés da combinação de duas aproximações lineares é derivado usando de Matsui Empilhar-Up Lema. A Zero-Up Lema assume que todas as subchaves das rodadas são independentes, a fim de calcular o viés combinado das relações lineares independentes. As subchaves das rodadas em CAST, porém, não são independentes, mas gerado através de um algoritmo de chave programação. No entanto, assumimos a aproximação é razoavelmente boa, como já foi assumido em ataques lineares anteriores sobre a cifra DES. <ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref>

Mas, não se pode combinar um número arbitrário de relações lineares. Uma restrição óbvia é a de limitar o esforço de ataque para menos do que a de uma pesquisa exaustiva chave. O tamanho da chave para CAST-128 é de pelo menos 40 bits, e para CAST-256, pelo menos 128 bits. Além disso, tanto para CAST-128 e CAST-256, nós olhamos para os ataques que não exigem mais texto do que o livro de códigos completa <math>(2^{64} e 2^{128}</math>, blocos de texto, respectivamente). Caso contrário, um invasor pode recolher o livro de códigos e usá-lo para decifrar (e forjar) criptogramas sem conhecer a chave (e enquanto a chave não é alterado) <ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref>

As mesmas S-caixas de CAST-128 também são usadas em CAST-256. Da mesma forma, os mesmos três tipos de funções das rodadas de CAST-128 são aplicadas em grupos de quatro rodadas chamados quadrounds. 
Assim, usamos em CAST-256 as mesmas máscaras de bits usados em nossa análise da CAST-128. É interessante observar que <ref name="cmadams">S.E. Tavares M. Wiener C.M. Adams, H.M. Heys. An analysis of the cast-256 cipher. </ref> já previu aproximações lineares com mascára de saída diferente de zero. Mas, os autores <ref name="cmadams">S.E. Tavares M. Wiener C.M. Adams, H.M. Heys. An analysis of the cast-256 cipher. </ref> não discutiram mais este assunto.  <ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref>

As primeiras relações lineares que temos para CAST-256 são 4-rodadas iterativa (Figura 2), que significa um quad-round. Apenas uma (de quatro) rodada é ativa e todas as quatro funções <math>f_{i}</math> desta rodada estão ativas. <ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref>

[[Ficheiro:Quadround.png|miniaturadaimagem|Figura 2 : Um quad-round iterativo de relações lineares para CAST-256]]
Calculamos o viés para a aproximação linear com máscaras <math>(00_{x}, 00000001_{x})</math>, para cada um das quatro caixas <math>S_{1}</math> até <math>S_{4}</math>. O viés é exatamente <math>2^{-5}</math> para todos eles. <ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref>

Poderíamos ter construído as relações lineares alternativas iterativas, com bits de ordem superior definidos como <math>00000002_{x}</math> ou <math>00000003_{x}</math>. Para máscara de bit <math>00000002_{x}</math> todos as S-caixas presente no viés <math>2^{-5}</math>, e por <math>00000003_{x}</math> o viés são <math>2^{-6}, 2^{-5}, 2^{-6}</math> e <math>2^{-7}</math> para as S-boxes <math>S_{1}</math> à <math>S_{4}</math>, respectivamente. Estas máscaras levam a uma diminuição de <math>2^{-3}</math> no viés combinado devido ao carry e devido ao empréstimo de bits nas operações em modulo de adição e subtração nas funções das rodadas. Por exemplo, para uma rodada completa, usando a máscara <math>00000002_{x}</math>, o viés torna-se <math>2^{4} * 2^{-5} * 2^{-5} * 2^{-5} * 2^{-5} * 2^{-3} = 2^{-19}</math>. O fator <math>2^{-3}</math> é, devido à aproximação do módulo da subtração e adição com a máscara <math>00000002_{x}</math>. Assim, temos não nenhuma vantagem significativa no uso dessas máscaras de bits alternativas em vez de <math>00000001_{x}</math>. <ref name="jrlinear">Jorge Nakahara Jr and Mads Rasmussen. Linear analysis of reduced-round cast-128 and cast-256.</ref>


A relação linear na Figura 2 pode ser usado para distinguir um número de rodadas quad-rounds da CAST-256 a partir de uma permutação aleatória (com o mesmo tamanho de bloco). Pode-se derivar uma relação linear, tais como <math>(D \oplus H) * 00000001_{x} = 0</math>, onde (A, B, C, D) indica um bloco de texto simples, e (E, F, G, H) indica um bloco de texto cifrado após uma série de quad-rodadas.

==Na Prática==

Diversas ferramentas comerciais fazem uso da cifragem de dados:

* TrueCrypt
* CryptoExpert 2004 Lite
* E4M Disk Encryption

O PGP (Pretty Good Privacy) tem como algoritmo default CAST-128.


{{referências}}

[[Categoria:Algoritmos de criptografia]]