FROG
Em criptografia, Frog é um algoritmo simétrico de cifra de bloco desenvolvido na empresa TecApro International S.A no ano de 1998 por Dianelos Georgoudis, Damian Leroux, e Billy Simón Chaves. Esse algoritmo foi um dos concorrentes no concurso AES de 1998 e acabou não sendo o ganhador por ter sido descobertas falhas como um esquema de chave difícil e demorado, encriptação demorada e conjunto de chaves fracas. Os direitos autorais pertencem ao Dr Brian Gladman mas o código é aberto para qualquer pessoa poder visualizar e fazer estudos em cima dele.
O Frog tem em comum alguns algoritmos como: AES · Blowfish · DES (Internal Mechanics,Triple DES) · Serpent · Twofish. Fazendo simples comparações desse algoritmo com outros existentes, podemos ver que ele tem um dos mais lentos esquemas de chave entre os algoritmos AES, ficando apenas à frente do algoritmo MAGENTA. O Frog usa 128 S-box para encriptação enquanto MAGENTA usa 192 S-box. Também não é possível colocar o FROG dentro de um Smart Card porque seu esquema de chave precisa de mais de 2300 bytes de RAM, como acontece também com Hasty Pudding Cipher, enquanto outros como por exemplo Magenta são mais favoráveis de serem usados nisso.
Princípios do Algoritmo
[editar | editar código-fonte]A ideia básica por trás do design do Frog é ocultar todo o processo de transformar o texto em branco para texto cifrado em uma chave interna secreta. O objetivo é de bloquear qualquer atacante de saber sobre todo esse processo sendo ele público ou não, juntando ainda com a implementação de uma cifra que seja o mais simples possível de implementar(eficiência) e o mais complexa possível matematicamente(força). Os métodos de encriptação e desencriptação usados no Frog são simples. Toda a complexidade fica na chave secreta interna, que é desconhecida pelo atacante. Sendo fácil de implementar, o algoritmo na linguagem C tem em média 150 linhas de código, sendo que grande parte dele consiste em código da chave interna secreta e uma pequena parte da cifra interna mesmo.
Estrutura de Funcionamento
[editar | editar código-fonte]Na realidade, enquanto outras cifras de bloco utilizam a chave apenas como dado, esse algoritmo de encriptação opera como um tradutor que considera a chave secreta interna como um programa e o executa como se ele fosse séries de instruções primitivas. A chave interna é construída recursivamente e a estrutura escolhida ou é para obedecer requerimentos de design ou para acelerar o processo de difusão. Com isso, é criada uma chave interna simples(simpleKey) durante o setup da chave, no qual a quantidade necessária de cópias de chave de usuário foram apenas ligadas entre si. Esse é o jeito mais simples de criar essa chave. Uma tabela constante(randomSeed) é incluida no Frog, mas sua definição é baseada em dados aleatórios conhecidos que foram publicados nos últimos 40 anos(RAND tables) e portanto nenhuma trapdoor pode ser escondida nessa tabela. Além disso, os valores nessa tabela não afetam seriamente a força do algoritmo. Você pode preencher a tabela com qualquer valor aleatório e o resultado final do Frog vai funcionar bem. O propósito da tabela é de aumentar a flexibilidade do algoritmo porque ele pode ser usado como uma chave mestre. Frog funciona com qualquer tamanho de bloco entre 8 e 128 bytes e suporta chaves de tamanho entre 5 e 125 bytes.
Tabela de RandomSeed, começando pelo byte menos significativo
[editar | editar código-fonte]113, 21,232, 18,113, 92, 63,157,124,193,166,197,126, 56,229,229, 156,162, 54, 17,230, 89,189, 87,169, 0, 81,204, 8, 70,203,225, 160, 59,167,189,100,157, 84, 11, 7,130, 29, 51, 32, 45,135,237, 139, 33, 17,221, 24, 50, 89, 74, 21,205,191,242, 84, 53, 3,230, 231,118, 15, 15,107, 4, 21, 34, 3,156, 57, 66, 93,255,191, 3, 85,135,205,200,185,204, 52, 37, 35, 24, 68,185,201, 10,224,234, 7,120,201,115,216,103, 57,255, 93,110, 42,249, 68, 14, 29, 55, 128, 84, 37,152,221,137, 39, 11,252, 50,144, 35,178,190, 43,162, 103,249,109, 8,235, 33,158,111,252,205,169, 54, 10, 20,221,201, 178,224, 89,184,182, 65,201, 10, 60, 6,191,174, 79, 98, 26,160, 252, 51, 63, 79, 6,102,123,173, 49, 3,110,233, 90,158,228,210, 209,237, 30, 95, 28,179,204,220, 72,163, 77,166,192, 98,165, 25, 145,162, 91,212, 41,230,110, 6,107,187,127, 38, 82, 98, 30, 67, 225, 80,208,134, 60,250,153, 87,148, 60, 66,165, 72, 29,165, 82, 211,207, 0,177,206, 13, 6, 14, 92,248, 60,201,132, 95, 35,215, 118,177,121,180, 27, 83,131, 26, 39, 46, 12
Funcionamento do Algoritmo
[editar | editar código-fonte]
São feitas 8 iterações no processo de criptografar. Cada iteração usa um registro da chave interna(chamada internKey), que é uma estrutura de dados com 8 registros. Cada registro tem 3 campos: um array de 16 bytes(xorBu) que é usado em uma operação inicial de XOR com o bloco de bytes, um array de 256 bytes(substPermu) que representa uma tabela de substituição para valores de byte e um array de 16 bytes(bombPermu) onde cada um dos quais aponta para diferentes posições de byte dentro do bloco e portanto tem um valor entre 0 e 15.
Cada iteração cruza sequencialmente o bloco de 16 bytes(do byte menos significativo até o mais significativo) e executa 4 operações básicas em cada byte:
1 - XOR entre o próximo byte do bloco com o próximo byte do campo de xorBu
2 - Substituir o byte computado na operação 1 pelo byte na tabela de substituição(substPermu) indexado por ele
3 - Modificar o próximo byte no bloco por XOR com o byte computado na operação 2. Quando é alcançado o fim do bloco, então o byte menos significativo do bloco é considerado o próximo byte
4 - Usar o próximo byte do array bombPermu para definir uma posição no bloco. Modificar o byte nessa posição do bloco fazendo XOR com o byte computado na operação 2
Exemplo de encriptação
[editar | editar código-fonte]Todos os valores estão em hexadecimal começando com o byte menos significativo. Primeiro é definido um registro de chave interna com os seguintes valores, começando com o byte menos significativo indexado em zero:
xorBu: 05 f0 a3 ...
substPermu: a2 16 08 bb 03 f1 ...
bombPermu: 03 0f 00 ...
Vamos agora encriptar o texto em branco a seguir:
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0f
e mostrar os estágios intermediários do bloco após cada passo.
Processando o byte na posição 0:
1.: 05 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0f
2.: f1 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0f
3.: f1 f0 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0f
4.: f1 f0 02 f2 04 05 06 07 08 09 0a 0b 0c 0d 0f
Processando byte na posição 1:
1.: f1 00 02 f2 04 05 06 07 08 09 0a 0b 0c 0d 0f
2.: f1 a2 02 f2 04 05 06 07 08 09 0a 0b 0c 0d 0f
3.: f1 a2 a0 f2 04 05 06 07 08 09 0a 0b 0c 0d 0f
4.: f1 a2 a0 f2 04 05 06 07 08 09 0a 0b 0c 0d ad
Processando byte na posição 2:
1.: f1 a2 03 f2 04 05 06 07 08 09 0a 0b 0c 0d ad
2.: f1 a2 bb f2 04 05 06 07 08 09 0a 0b 0c 0d ad
3.: f1 a2 bb 49 04 05 06 07 08 09 0a 0b 0c 0d ad
4.: 4a a2 bb 49 04 05 06 07 08 09 0a 0b 0c 0d ad
e assim por diante. O processo é rápido e depois de apenas 3 iterações qualquer redundância estatística no texto em branco torna-se obscura. Foram escolhidas 8 iterações como base para o algoritmo Frog garantir que o texto cifrado gerado tenha propriedades aleatórias muito boas. Note que todos os passos no processo são simples operações que podem ser invertidas e com isso chega-se ao processo de desencriptação, conseguindo no fim recuperar o texto em branco. A chave interna usada na desencriptação é idêntica, exceto que todas as tabelas de substituição(campos substPermu) são substituídos pelo seu inverso.
Pseudo código Encriptação
[editar | editar código-fonte]FROG-encriptar(textoEmBranco, textoCifrado, internKey)
//converter texto em branco para texto cifrado
copiar textoEmBranco em textoCifrado
para cada 8 registros na internKey faça
começa
//xorBuf, substPermu, bombPermu indicam os campos do registro atual
para cada byte no textoCifrado faça[I \textless- 0 to blockSize-1]
começa
textoCifrado[I] <-- textoCifrado[I] XOR xorBu[I]
textoCifrado[I] <-- substPermu[textoCifrado[I]
se I < blockSize-1
então textoCifrado[I+1] <-- textoCifrado[I+1] XOR textoCifrado[I]
else textoCifrado[0] <-- textoCifrado[0] XOR textoCifrado[I]
K <-- bombPermu[I]
textoCifrado[K] <-- textoCifrado[K] XOR textoCifrado[I]
fim
fim
fim Procedimento
Setup da Chave Secreta
[editar | editar código-fonte]FROG computa a chave interna como uma função da chave de usuário. Cada iteração feita usa um registro que possui 16 bytes para o campo xorBuf, 256 bytes para o campo substPermu e 16 bytes para o campo bombPermu. Com isso, a chave interna possui 2,304 bytes. O setup da chave é um processo recursivo. Primeiro cria uma chave interna simples e então usa a encriptação FROG em modo CBC(Cipher Block Chaining) para produzir a chave interna definitiva.
Como é mostrado na figura, a chave é produzida por 2 algoritmos. O primeiro (função makeInternalKey) pega um array arbitrário de 2304 bytes e o transforma em uma chave interna válida e computa a permutação de arrays substPermu e bombPermu para cada um dos 8 registros. Para ser feito isso, é usada a segunda função makePermutation que pega um array arbitrário de N bytes e returna uma permutação com valores de 0 à N-1. Se a chave interna for usada para desencriptação, então o substPermu é invertido. O campo bombPermu é válidado depois para completar as condições necessárias descritas anteriormente.
O segundo algoritmo é a chave hash, que pega uma chave de tamanho entre 5 e 125 bytes e produz um long array de 2304 bytes (randomKey) sem perder nenhuma entropia e preenchendo-o com dados que parecem ser estatisticamente aleatórios. Esse procedimento é feito em 3 passos:
1 - O long array de 2304 bytes(simpleKey) é preenchido com dados que depende da chave do usuáriop e da constante interna(randomSeed) que é preenchida com 251 bytes aleatórios verdadeiros. A simpleKey é primeiramente preenchida com cópias da chave do usuário e então é feito sequencialmente XOR com cópias da randomSeed. Qualquer byte da direita é ignorado. O array resultante é então processado pela função makeInternalKey e transformado em uma chave interna FROG válida.
2 - Um IV(vetor de inicialização) é criado usando o byte menos significativo de 16 bytes da chave do usuário(se a chave tiver menos de 16 bytes, então o resto é preenchido com zeros). Então é feito um XOR do valor correspondente ao tamanho da chave do usuário em byte com o byte menos significativo do IV. Isso garante que diferentes tamanhos de chave do usuário sempre crie textos cifrados diferentes.
3 - A função de encriptação FROG é chamada para encriptar um array preenchido com zero de 2304 bytes no modo CBC(Cipher BLock Chaning) usando a chave interna criada no passo 1e o IV do passo 2. O resultado desse processo é um array(randomKey) com uma boa aleatoriedade estatística.
Então esse array é processado pela função makeInternalKey e transformado em uma chave interna válida. Isso completa a criação da chave interna que é usada então para encriptar ou desencriptar.
makePermutation é um algoritmo que pega um array de entrada de de bytes e retorna uma permutação de mesmo tamanho. Nesse contexto, permutação corresponde ao array de tamanho N que tem todos os valores entre 0 e N-1 com nenhuma repetição.Funciona da seguinte forma:
Um array "use" é inicializado sequencialmente com todos os valores entre 0 e N-1. A permutação é criada sequencialmente um byte de cada vez pegando bytes do array "use". Quando um byte é usado, ele é removido do "use" e o tamanho do array é decrementado em 1. Desse jeito é garantido que o mesmo valor nunca será usado em uma permutação. Os valores do vetor de entrada são usados para computar um index em um array "use". Quando estiver computando o i-ésimo elemento da permutação, esse index é computado adicionando o index anterior usado com o i-ésimo byte do array de entrada: index\_i = ( index\_(i-1) + input[i] ) mod (tamanho do array "use"). A operação de módulo é necessária para garantir que o index computado vai apontar para uma posição válida. Para primeira iteração, o index anterior é inicializado em 0.
Exemplo Permutação
[editar | editar código-fonte]Array de 8 elementos: 105,135,188,156,103,91,68,208
Na primeira iteração:
index = (0 + 105) mod 8 = 1. No array "use" "1", é indexado o 1 que se torna o primeiro elemento da permutação. Remove 1 do array "use"
Segunda iteração:
index = (1 + 135) mod 7 = 3. No array "use" "3", é indexado o 4 que se torna o segundo elemento da permutação. Remove o 4 do array "use" e assim sucessivamente...
Criptoanálise
[editar | editar código-fonte]A eficiência do algoritmo é de O(2^(N-1)) .
Foram achados vários modos que recuperam a chave secreta mais rápidos que usando força bruta.
Ataque de texto cifrado escolhido é esperado que exija 2^64 cifras de textos conhecidas em média. Esse tipo de ataque pode ser feito usando o modo CBC(Cipher Block Chaining) e ECB(Electronic CodeBlock). Conseguindo decifrar usando esse tipo de ataque, indica que o FROG tem um problema grande com chaves fracas.
Ataque de texto em branco escolhido usa D = 2^50, F = 2^-33 e C = 2\^{}58 e é esperado que o atacante recupere a chave depois de 2^83 operações.
Em sua desencriptação, tem um ataque de F= 2^-28.5, D = 2^37 e C = 2^43. Deste modo, um atacante consegue recuperar a chave depois de 2^65.5 operações.
Referências
[editar | editar código-fonte]- David Wagner, Niels Ferguson and Bruce Schneier, Cryptanalysis of FROG, in proceedings of the 2nd AES candidate conference, pp175–181, NIST, 1999 .
- Dianelos Georgoudis, Damian Leroux and Billy Simón Chaves, The FROG Encryption Algorithm, June 15, 1998 .