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