Um conceito de função hash para ambientes paralelos

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