Security and Simulation in Modern Computer Hardware

Abstract

Nas últimas décadas muitos aspectos da nossa vida têm sido migrados para a Internet.Desde pagamentos online até saúde, comunicações privadas, ou monitorização de infraestrutura, são imensas as actividades de cariz sensível que não só são actualmente comuns na Internet, mas seria desastroso se não fossem adequadamente protegidas.Uma ferramenta fundamental para a protecção de dados é a criptografia. A criptografia oferece mecanismos para assegurar a confidencialidade e integridade dos dados, assim como para a sua autenticação e ainda outros usos mais avançados como provas de conhecimento zero.Mas para a criptografia ser útil tem de ser usável. Uma componente significativa da usabilidade é o desempenho: se a criptografia for lenta---ou tiver a percepção de ser lenta---isto irá impedir a sua adopção ou incentivar o uso de alternativas inseguras. Isto não é apenas uma preocupação teórica; existem muitos casos em que funções criptográficas inseguras continuaram a ser usadas devido ao custo imposto por transitar para alternativas seguras. Uma das razões para uma função criptográfica ser lenta é por não ser desenhada com o hardware em mente, hardware este que à medida que a lei de Moore caminha para o seu fim, se torna cada vez mais paralelo.O foco principal desta tese é o desenvolvimento de funções criptográficas rápidas que se adaptam ao hardware moderno---rápidas o suficiente de forma a que não haja razão para preferir soluções inseguras. A minha contribuição consiste principalmente em duas funções com aplicações diferentes.A primeira, BLAKE2, é uma função de dispersão desenhada para substituir funções mais antigas como a MD5 e SHA-1 que, apesar de terem sido quebradas há mais de uma década, continuam a ser utilizadas porque tipicamente também são as mais rápidas. A BLAKE2 deriva da função BLAKE, uma das finalistas da competição SHA-3 do NIST, é considerada ter uma grande margem de segurança e, simultaneamente, é mais rápida que a MD5 e a SHA-1. A BLAKE2 também suporta dispersão em árvore, o que torna possível aproveitar o paralelismo em maior escala dos processadores modernos.A segunda contribuição é a função de cifração autenticada NORX. Apesar de já existirem funções de cifração autenticada, como a AES-GCM ou a EAX, estas são baseadas da cifra de bloco AES. Apesar desta cifra ser unanimemente considerada segura, para ser tanto segura como rápida tem de ser implementada em hardware. Uma submissão para a competição CAESAR para novas funções de cifração autenticada, a NORX ambiciona eliminar este dilema por ser rápida, paralelizável, e fácil de implementar na maioria das plataformas. Em processadores sem aceleração de AES, como o ARM Cortex-A7, a NORX pode ser até três vezes mais rápida do que a AES-GCM.Como subproduto do desenvolvimento destas funções, também desenvolvemos o Tyche, um gerador de números aleatórios destinado a simulações paralelas de grande escala. Outro subproduto foi a nossa criptanálise da NORX, que também se tornou útil para a análise de outras funções como a McMambo e Wheesht, ambas submetidas para a CAESAR, assim como a função de cifração autenticada usada no padrão Open Smart Grid Protocol.

In the last few decades many aspects of our lives have been moved online. Banking and payments, health care, private messaging, or critical infrastructure monitoring are just a small subset of sensitive activities that are now commonplace on the Internet, and yet it would be catastrophic if they were not adequately secured.One core tool for securing both data at rest and communications is cryptography. Cryptography offers tools for preserving the confidentiality and integrity of data, as well as for authentication and other more advanced uses like zero-knowledge proofs.But for cryptography to be useful it needs to be usable. One significant component of usability is speed: if cryptography is---or is perceived to be---slow, this will slow down its adoption and incentivize poor alternatives to replace it. This is not theoretical; there are many such cases in the past where weak or ineffective cryptography was used because better options were deemed to incur too much overhead. One of the reasons that cryptographic functions can be slow is that they are not designed with the hardware in which they are going to run in mind. Hardware which, as Moore's law comes closer to its end, is becoming increasingly parallel.The main focus of this thesis is the development of fast cryptographic primitives that fit modern hardware---fast enough that there should be no reason to prefer weaker ones. Our main contribution consists of two primitives with different applications.The first one, BLAKE2, is a hash function designed to replace legacy hash functions such as MD5 and SHA-1 that, despite being long known to be broken, continue to be used due to their speed and availability. %Their putative replacements, SHA-2 and SHA-3, have shown to be slower on common hardware and thus have not fully succeeded in replacing them. BLAKE2 was derived from the original BLAKE, one of the NIST SHA-3 competition finalists, and is expected to have a large security margin while, at the same time, being faster than MD5 and SHA-1. BLAKE2 also supports tree hashing, making it possible to accelerate operations on parallel hardware at a coarse grained level as well.The second main contribution is NORX, an authenticated encryption primitive. While existing authenticated encryption primitives already existed, such as AES-GCM or EAX, they were based on the AES block cipher. The AES block cipher is widely believed to be secure. However, AES-based primitives suffer from a drawback: for AES to be both fast and secure it must be hardware accelerated. As one of the submissions to the CAESAR competition for new authenticated encryption designs, NORX aims to eliminate this kind of tradeoff: it is fast, parallelizable, and easy to implement in pretty much every platform. In chips without hardware AES acceleration, such as the ARM Cortex-A7, NORX can be up to three times faster than AES-GCM.As a byproduct of the development of the primitives above, we also developed Tyche, a small nonlinear pseudorandom generator targeted towards massively parallel simulations. Another byproduct of our research was the cryptanalysis not only of NORX, but also of other primitives such as the CAESAR candidates McMambo and Wheesht, as well as the authenticated encryption scheme found in the widespread Open Smart Grid Protocol standard.