Um conceito de função hash para ambientes paralelos

Igor G. F. de Almeida, Luiz F. dos S. Sousa, Igor Ruiz Gomes

Centro Universitário do Pará (CESUPA) – Área de Ciências Exatas e Tecnologia (ACET) Laboratório de

Computação Natural (LCN) – Grupo de Estudos Temáticos de Matemática Computacional (MatComp-

CESUPA) - 66.060- 230, Belém – Pará – Brasil

E-mail: {cmte.igor.almeida, fellipe.skool, ruiz.igor}@gmail.com

RESUMO

Em um mundo em que a computação tende a ser cada vez mais paralela, a criptografia

necessita de algoritmos que sejam capazes de executar nesses ambientes.

Primitivos criptográficos como cifras de bloco e funções hash podem ser particularmente

beneficiados por um ambiente onde o paralelismo é presente, desde que sejam desenhados para tirar proveito dos recursos disponíveis nas arquiteturas paralelas.

Como todo o algoritmo os requisitos para a paralelização de uma função criptográfica são de

não haver dependências de dados ou de instruções concorrentes, assim evitando uma corrida pelos recursos físicos ou inconsistência nos dados [3], o que em uma área que os dados são o

foco é fatal.

Uma vez atendidos esses requisitos é necessário dividir a carga de processamento entre

diversas linhas de execução ou threads. Normalmente os algoritmos criptográficos são compostos de algumas instruções repetidas diversas vezes ao longo de um conjunto de dados, o

que caracteriza esse ambiente como SIMD (Single Instruction, Multiple Data), arquitetura

muito utilizada nos supercomputadores vetoriais [3]. No caso específico das funções hash existem alguns sistemas que podem ser utilizados no

contexto paralelo sem grandes esforços como a árvore de Merkle, conceito desenvolvido para

facilitar a computação de algoritmos complexos que dependem de funções hash. Categoria em que a assinatura de Lamport encontra-se, em que vários valores hash devem ser calculados para

gerar uma chave pública que será usada para verificar a autenticidade de uma assinatura.

O algoritmo exemplo desse trabalho comporta-se de forma semelhante a uma SPN

(Substitution-Permutation Network) [2] muito utilizada em cifras de bloco em que diversas camadas que substituem os valores de entrada alternam-se entre outras camadas que permutam

os bits. Tal sistema tem se provado eficaz sendo amplamente utilizado em algoritmos

conhecidamente seguros com o Serpent e o Rjndael, sendo o último adotado como padrão criptográfico pelo governo americano [2].

Ele é composto de duas camadas em que funções menores são dispostas, a primeira camada

é a de compressão em que um bloco da mensagem é combinado com o estado interno do algoritmo utilizando funções de mão única.

A camada de compressão nesse caso é representada por quatro instâncias da função C que

deve ser uma função do tipo Merkle-Damgård. A utilização de uma função desse tipo deve-se

ao fato de que é provado que uma vez que a função de compressão interna seja resistente a

colisões própria função C também será resistente a colisões[1]. Assim tem-se sendo um F uma função de compressão resistente a colisões. Uma das fraquezas do sistema

Merkle-Damgård é que uma vez que adversário tem conhecimento do tamanho da mensagem, ele poderá fazer uso de diversas técnicas que irão gerar colisões para a mensagem original,

dessa forma quebrando o algoritmo.

Porém uma forma de contornar esses problemas é usando uma técnica conhecida como wide-

pipe hash em que é utilizado um estado de tamanho duas vezes maior que o tamanho do bloco da mensagem[1]. Dessa forma a entropia da função impede uma relação direta entre o tamanho

da mensagem e o valor final do hash.

A outra camada do algoritmo é a camada de difusão que como o nome sugere serve para atender o princípio da dispersão de Shannon, em que cada bit de saída deve depender de todos

os bits de entrada. Cada chamada a função D, que é uma função não-linear, é composta da

32

ISSN 1984-8218

combinação dos valores prévios da função C com o estado anterior do algoritmo, sendo essa

combinação feita com a operação ou-exclusivo(XOR). Esse valor obtido após a operação do

XOR é usado como entrada para a função D que em si é uma S-box, substituindo os valores de forma que não haja relação óbvia para um criptoanalista entre a entrada e a saída. Uma função D

eficiente nesse ambiente paralelo é a S-box do AES que substitui cada byte com seu inverso

multiplicativo em um corpo de Galois (corpo finito)[2]. Porém qualquer função que possa trabalhar com diversas partes dos dados simultaneamente será eficaz na execução do algoritmo.

Com a iteração do estado ao longo dos diversos blocos da mensagem qualquer pequena

mudança na entrada gera uma grande mudança na saída, caracterizando o efeito avalanche [2].

Como continuação do trabalho pretende-se demonstrar a eficiência dessa arquitetura em um ambiente de programação paralela.

Figura 1 – Diagrama de como as camadas se comunicam para atualizar o estado

interno da função

Palavras-chave: Criptografia, programação paralela, função hash

Referências

[1] S. Lucks, “Design Principles for Iterated Hash Functions”, Cryptology ePrint

Archive, 2004.

[2] C. Paar, J. Pelzl, “Understanding Cryptography”, Springer-Verlag, 2009. [3] A. Tanenbaum, “Distributed operating systems”, Prentice Hall, 2005.

33

ISSN 1984-8218