MARS (criptografia)

O algoritmo MARS é uma cifra em blocos criada pela IBM, que foi submetido ao NIST para concorrer ao AES (Advanced Encryption Standard), sendo um dos 5 algoritmos a chegarem na rodada 2 do processo que continha 15 algoritmos em sua primeira rodada. Consiste de um algoritmo de encriptação de chave simétrica com blocos de 128 bits e uma chave variando de 128 até 448 bits, que alem de alta segurança apresenta códigos compactos. O MARS foi desenvolvido pela IBM, que tem seu direito de patente. Entre os membros do time de desenvolvimento, esta incluso Don Coppersmith, que participou da criação do Data Encryption Standard (DES) 20 anos antes. A IBM afirma que o MARS e mais seguro que o triplo DES, e mais rápido que o DES simples, e que também é aplicável em ambientes com recursos limitados como smartcards por ter código compacto. Além disso, afirmavam que o MARS implementava uma forma de comunicação segura em relação a possíveis avanços na matemática criptográfica.

Princípios do projeto

Tendo como um dos criadores um membro da equipe que desenvolveu o DES, o projeto do MARS teve como inspiração alcançar uma segurança maior que o triplo DES. O projeto foi também concebido com o intuito de resistir a avanços futuros em criptografia, objetivo que motivou a utilização de uma abordagem em camadas compartimentadas.

Estrutura de funcionamento

A estrutura do MARS consiste de um ”núcleo criptográfico”de transformações chaveado, que é cercado por duas camadas que provêm uma avalanche rápida de chave.

• A primeira fase provê mixagem rápida e avalanche de chave, para frustar ataques com texto plano escolhido, e para tornar mais difícil ”cortar”rodadas do núcleo criptográfico em ataques lineares e diferenciais;

• A segunda fase e o núcleo criptográfico do cifrador, consistindo de 16 rodadas de transformações chaveadas Feistel tipo 3. Para garantir que a encriptação e a decriptamento tenham a mesma resistência, as primeiras 8 rodadas s˜ao realizadas em ”modo para frente”enquanto as ultimas 8 rodadas são feitas em ”modo para trás”;

• A terceira fase novamente provê mixagem rápida e avalanche de chave, desta vez para proteger contra ataques de textos cifrados escolhidos;

Funcionamento do algoritmo

A rede Feistel tipo 3 utilizada nesta primeira fase pode ser vista na figura 1. Nesta fase, primeiramente é adicionada uma palavra chave a cada

Figura 1: Estrutura da fase de Mixagem para Frente

palavra de dados, e então são feitas 8 rodadas de mixagem Feistel tipo 3 não chaveadas, baseadas nas caixas S, combinadas com algumas operações de mixagem adicional. Em cada rodada é usada uma palavra de dados (chamada de ”source word”ou palavra origem) para modificar as outras três palavras (chamadas de ”target words”ou palavras alvo). Os quatro bytes da palavra origem são vistos como índices nas duas caixas S, S0 e S1 cada uma sendo constituída de 256 palavras de 32 bits, e então as correspondentes entradas da caixa S são utilizadas em operações XOR e de adição contra as outras três palavras de dados.

Se nos denotarmos os quatro bytes da palavra ”origem”como b1, b2,b3 e b4 (com b1 sendo o byte mais baixo e b4 sendo o byte mais alto), então usa-se b1 e b3 como índices da caixa S S0 e b2 e b4 com índices da caixa S S1. Primeiramente efetua-se a opera¸c˜ao XOR entre S0[b1] e a primeira palavra ”alvo”, e então adiciona-se S1[b2] á mesma palavra. Também adiciona-se S0[b3] ´a segunda palavra ”alvo”e faz-se um XOR entre S1[b4] e a terceira palavra ”alvo”. Finalmente, a palavra ”origem”´e rotacionada 24 posições para a direita. Na próxima rodada as quatro palavras são rotacionadas, de maneira que a atual primeira palavra ”alvo”torne-se a próxima palavra ”origem”, a atual segunda palavra ”alvo”torne-se a próxima primeira palavra ”alvo”, a corrente terceira palavra ”alvo”torne-se a próxima segunda palavra ”alvo”e a atual palavra ”origem”torne-se a próxima terceira palavra ”alvo”. Em adição, apos a primeira e a quinta rodadas a terceira palavra ”alvo”´e adicionada de volta a palavra ”origem”, e apos a segunda e a sexta rodadas a primeira palavra ”alvo”´e adicionada de volta a palavra ”origem”.

Na figura 2 podemos ver a estrutura da rede Feistel tipo 3 que constitui o núcleo criptográfico do MARS, consistindo de 16 rodadas. Em cada rodada é utilizada uma função E chaveada (E de Expansão) que é baseada em uma moderna combinação de multiplicações, rotações dependentes de dados e buscas nas Caixas S (Figura 3).

Figura 2: Rede Feistel tipo 3 de transformação chaveada principal

Para garantir que o cifrador tenha a mesma resistência a ataques com textos cifrados escolhidos bem como textos planos escolhidos, as três saídas da função E são usadas em diferente ordem nas primeiras oito rodadas e nas oito últimas rodadas. Nas primeiras oito rodadas (modo para frente) a primeira e a segunda saídas da função E são respectivamente somadas a primeira e segunda palavras ”alvo”, e é feita uma operação de ou-exclusivo entre a terceira saída e a terceira palavra ”alvo”. Nas ´ultimas oito rodadas (modo para trás) respectivamente adicionamos a primeira e a segunda saídas da função E a terceira e segunda palavras ”alvo”, e é executada uma operação de ou-exclusivo entre a terceira saída com a primeira palavra ”alvo”. A função E pega como entrada uma das palavras de dados e mais duas palavras chaves para produzir três palavras de saída. Nesta função são utilizadas variáveis temporárias, denotadas por L, M e R. A seguir essas três variáveis são também referenciadas como as três ”linhas”na função. Inicialmente, R ´e setada para conter o valor da palavra de origem rotacionada 13 posições para a esquerda, e M ´e setada para conter a soma da palavra de origem com a primeira palavra chave. Os nove menores bits de M são utilizados com um índice na caixa S de 512 entradas S (que é obtida pela concatenação de S0 e S1 da fase de mixagem) e L então conterá a entrada correspondente da caixa S.

Figura 3: Funçãao E de transformação chaveada principal

Em seguida a segunda palavra chave (restringida a um numero inteiro ímpar) é multiplicada com R e rotacionada em 5

(cinco) posições para a esquerda (de forma que os 5 maiores bits do produto venham a ser os 5 menores bits de R apos

a rotação). Então realiza-se um XOR de R em L, e considera-se os cinco menores bits de R como um montante de rotação

entre 0 e 31, e então rotacionamos M por este montante. Apos rotaciona-se R mais 5 posições para a esquerda e efetua-se

um XOR do resultado em L. Finalmente, novamente usa-se os cinco menores bits de R como o montante de rotação e

Figura 4: Estrutura da fase de Mixagem para Trás

rotacionamos L para a esquerda por este montante. A primeira saída da função E é L, a segunda é M e a terceira é R. A fase de mixagem para trás é o mesmo que a decriptacao da fase de mixagem para frente, exceto que as palavras de dados são processadas em ordem diferente. Tanto que se pegarmos a saída da fase de mixagem para frente não chaveada e a utilizarmos como entrada para a fase de mixagem para trás, em ordem inversa (ou seja, saída D[3] para a entrada D[0], saída D[2] para a entrada D[1], etc.) então essas fases irão cancelar-se mutuamente uma a outra. Essa fase é essencialmente o inverso da primeira fase, consistindo de 8 rodadas do mesmo tipo de mixagem Feistel tipo 3 (Figura 4) da primeira fase (mas em modo ”para trás”), seguida da subtração das palavras-chave das palavras de dados. Como na mixagem para frente, aqui também usa-se em cada rodada uma palavra ”origem”para modificar as outras três palavras ”alvo”. Os quatro bytes da palavra ”origem”são denotados como b1, b2, b3 e b4, como anteriormente. Usa-se b1, b3 como índices para a caixa S S1 e b2, b4 como índices para a caixa S S0. Faz-se um XOR de S1[b1] na primeira palavra ”alvo”, subtrai-se S0[b4] da segunda palavra de dados, subtrai-se S1[b3] da terceira palavra ”alvo”e então faz-se um XOR de S0[b2] também na terceira palavra ”alvo”. Finalmente, rotaciona-se a palavra ”origem”por 24 posições para a esquerda. Para a próxima rodada as quatro palavras são rotacionadas, de forma que a primeira palavra ”alvo”atual torne-se a próxima palavra ”origem”, a atual segunda palavra ”alvo”torne-se a próxima primeira palavra ”alvo”, a atual terceira palavra ”alvo”torne-se a próxima segunda palavra ”alvo”e a atual palavra ”origem”torne-se a próxima terceira palavra ”alvo”. Ainda, antes de quatro rodadas específicas subtrai-se uma das palavras ”alvo”da palavra ”origem”: antes da quarta e oitava rodadas subtrai-se a primeira palavra ”alvo”da palavra ”origem”e antes da terceira e sétima rodadas subtrai-se a terceira palavra ”alvo”da palavra ”origem”.

O procedimento de expansão de chave MARS expande a chave fornecida pelo usuário (4 a 14 palavras de 32 bits [BCD+99] - Nota:

em BCD+98 o comprimento da chave fornecida pelo usuário no procedimento de expansão poderia variar entre 4 e 39 palavras de 32 bits) para uma chave de 40 palavras utilizada tanto nas operações de encriptação como de decriptação. O procedimento de expansão de chave consiste de 3 passos. O primeiro passo é uma ”expansão linear”que expande a chave original fornecida pelo usuário em quarenta palavras de 32 bits usando uma transformação linear simples. O segundo passo é ”Mistura da Chave baseada na Caixa-S”que mistura a chave expandida usando sete rodadas de uma rede Feistel tipo 1 para destruir relações

lineares na chave. Então um passo de ”modificação por multiplicação da palavra-chave”examina as palavras-chave que são usadas na operação de encriptação/decriptação MARS para multiplicação e então modifica-as se necessário.

Criptoanálise

Nos consideraremos ataques ao MARS com um ”embrulho”completo, mas um ”núcleo criptográfico”reduzido. Estes ataques demonstram como isto é possível para montar ataques em um núcleo criptográfico, mesmo através de embrulho completo, embora contra um núcleo mais enfraquecido. Estes ataques penetraram o maior numero de rounds de cifra, pois eles focam nas rodadas de misturas relativamente fracas, ao invés de rodadas de núcleos mais fortes. Nossos ataques são ataques ”meet-in-themiddle”, requirindo enorme recurso de memoria para implementar. Considere MARS com mistura completa e camadas de clareamento, mas com o núcleo reduzido para três a frente e duas rodadas de núcleo para trás. Este é vulnerável a um meetin-the-middle ataque como a seguir:

• Solicitado oito pares de texto simples/texto cifrado

• Do lado do texto simples, suponha:

    a) Uma chave pré-branqueada de 128 bits;
    b) Uma chave da primeira rodada de 62 bits
    c) KA e nove bits menos significativos de K+ para a segunda rodada
    d) Isso resulta no conhecimento de A2 = D3 shift 13. Compute este valor para todos oito textos originais, e colocar o valor de 256 bits, resultando em uma lista ordenada.

• Do lado do texto cifrado, suponha:

    a) Uma chave pós-branqueada de 128 bits;
    b) Uma chave da ultima rodada de 62 bits;
    c) KA e nove bits menos significativos de K+ para a próxima apos a ultima rodada;
    d) Isso resulta no conhecimento de A2 = D3 shift 13. Calcular este valor para todos oito textos cifrados, e procurar a lista ordenada dos palpites de texto simples para um jogo sobre este valor de 256 bits Este ataque passa por 16 rodadas de mistura e 5 rodadas de núcleo. Os requisitos de memoria são totalmente irracional, na pr´atica, de modo que este ataque ´e puramente acadêmico