03 ago 2023
14:00 Defesa de Mestrado Auditório do IC3
Tema
Estudo de Difusão e Matrizes MDS em Cifras de Bloco Simétricas
Aluno
Ana Clara Zoppi Serpa
Orientador / Docente
Ricardo Dahab - Coorientador: Jorge Nakahara Junior
Breve resumo
Este trabalho estuda a propriedade de difusão completa em cifras de bloco simétricas, com atenção especial para a história do uso de matrizes MDS ao longo dos anos, fornecendo um catálogo de ~200 matrizes MDS presentes na literatura e seus respectivos custos computacionais (número de xtime e xor necessários para multiplicação de matrizes). Também investigamos a construção de matrizes MDS por meio de algoritmos genéticos.
A difusão completa é fundamental para a segurança contra criptoanálise diferencial e linear. Como componentes matemáticos que ajudam a garantir que a difusão completa seja alcançada em poucas iterações da função de rodada de uma cifra, as matrizes MDS são altamente relevantes para o design moderno de cifras de bloco. No entanto, existem muitos desafios em relação à construção de matrizes MDS, por exemplo, encontrar matrizes que sejam MDS (e, portanto, adequadamente seguras para uso em cifras) enquanto apresentem baixo custo computacional, levando a implementações rápidas de software ou hardware. Há algumas estratégias para a geração de matrizes MDS, como a construção de tipos específicos de matrizes (por exemplo, Cauchy, Vandermonde, Hadamard, circulante) que diminuam o número de escolhas de elementos necessárias (por exemplo, algumas dessas construções exigem que apenas os n elementos do primeira linha sejam escolhidos, pois os restantes são derivados da primeira linha, em vez de todos os n^2 elementos de uma matriz n x n completa). No entanto, a construção de matrizes MDS com algoritmos genéticos ainda não foi explorada. Escolhemos investigar o uso de algoritmos genéticos não apenas pela novidade da abordagem, mas também por sua aplicabilidade em problemas de otimização, e modelamos a construção de matrizes MDS como um problema de otimização onde desejamos otimizar o custo computacional.
Iniciamos nosso trabalho com estudos preliminares sobre difusão, comparando como a difusão completa é alcançada por duas cifras clássicas, DES e AES. Mostramos uma análise detalhada de como a difusão é alcançada em cada rodada. Para o DES, nossa análise modela os bits de estado do DES como nós em um grafo. Até onde sabemos, não houve análise de difusão DES modelando-o como um grafo, portanto, esta forma de análise de difusão também é uma nova contribuição de nosso trabalho. Acreditamos que poderia ser aplicada para estudar difusão em outras cifras e também em funções hash. Após a análise de difusão, nos aprofundamos na criptoanálise diferencial e linear, explicando a relação entre a propriedade de difusão e a segurança contra esses dois ataques clássicos. Em seguida, apresentamos nosso catálogo de matrizes MDS, que contém o custo de cada matriz encontrada em nossa revisão da literatura, juntamente com o custo de sua inversa para o corpo finito escolhido. Um catálogo completo contendo todas essas matrizes e seus custos também é novidade até onde sabemos e pode ser uma contribuição significativa para a comunidade de pesquisa em criptologia, especialmente criptologistas em busca de matrizes para usar em seus projetos de algoritmos. Por fim, explicamos como modelar a construção de matrizes MDS na configuração de algoritmos genéticos e apresentamos resultados de nossos esforços em busca de matrizes MDS com algoritmos genéticos, apresentando-os como uma possível nova estratégia para o problema de construção de matrizes MDS.
Banca examinadora
Titulares:
| Ricardo Dahab | IC/UNICAMP |
| Daniel Panario | Carleton University |
| Marcos Antonio Simplicio Junior | PCS/USP |
| Thaís Bardini Idalino | INE/UFSC |
Suplentes:
| Fábio Luiz Usberti | IC/UNICAMP |
| Routo Terada | IME/USP |