Breaking Rainbow: Analisi di Attacchi alla Crittografia Multivariata

Abstract

Da qualche tempo, ormai, la crittografia è stata affidata ai matematici e agli informatici, ma, con l’evolversi dei mezzi a disposizione, la sfida si sta facendo sempre più ardua: è sempre più difficile mantenere un’informazione al sicuro, poiché, col passare degli anni, la potenza di calcolo dei computer moderni sta aumentando vertiginosamente. In particolare, l’introduzione dei computer quantistici ha messo in seria difficoltà molti dei sistemi crittografici di attuale utilizzo, come il celebre RSA. È necessario, quindi, lo sviluppo della cosiddetta post-quantum cryptography (PQC), cioè la ricerca di crittosistemi che siano in grado di resistere anche all’attacco di computer di ultimissima generazione e potenza di calcolo mai vista finora.

Lo scopo di questa tesi è quello di presentare alcune delle idee proposte per raggiungere questo obiettivo, e mostrare come non sia un traguardo così semplice: nel Capitolo 1, introdurremo una delle famiglie di crittosistemi PQC più importanti, la crittografia multivariata, descrivendone il meccanismo e le idee su cui si basa; nel capitolo successivo (Capitolo 2), verranno introdotti due schemi di firma di crittografia multivariata, Oil and Vinegar e Rainbow , con i loro vantaggi e i loro svantaggi; successivamente, nel Capitolo 3, vedremo come è possibile attaccare questi schemi, mostrando molteplici approcci che ne mettano in risalto le vulnerabilità (con un particolare focus sul nuovo punto di vista proposto per attaccarli), per poi arrivare all’attacco conclusivo a Rainbow, quello di Beullens, mostrato nel Capitolo 4, che lo metterà definitivamente in crisi.

For some time now, cryptography has been entrusted to mathematicians and computer scientists. However, with the evolution of available resources, the challenge is becoming increasingly daunting: it is increasingly difficult to keep information secure, as over the years, the computing power of modern computers is skyrocketing. In particular, the introduction of quantum computers has seriously challenged many of the currently used cryptographic systems, such as the well-known RSA. Therefore, the development of so-called post-quantum cryptography (PQC) is necessary, that is, the search for cryptosystems that can withstand even the attack of the latest generation computers with unprecedented computing power.

The purpose of this thesis is to present some of the ideas proposed to achieve this goal, and to show how it is not such a simple task: in Chapter 1, we will introduce one of the most important families of PQC cryptosystems, multivariate cryptography, describing its mechanism and the underlying ideas; in the next chapter (Chapter 2), two multivariate cryptography signature schemes, "Oil and Vinegar" and "Rainbow", will be introduced, along with their advantages and disadvantages; subsequently, in Chapter 3, we will see how these schemes can be attacked, showing multiple approaches that highlight their vulnerabilities (with a particular focus on the new perspective proposed for attacking them), leading to the conclusive attack on Rainbow, Beullens' attack, shown in Chapter 4, which will definitively put it in crisis.