Post-quantum cryptography acceleration for next generation computers

Abstract

(English) The security of modern cryptographic schemes relies upon mathematical problems that are assumed to be hard to solve, like the Rivest-Shamir-Adleman (RSA) problem or the discrete logarithm problem over elliptic curves. Using the existing “classical” computers, all known algorithms attempting to solve these problems, would require such a big amount of computational time that will actually make the intercepted data useless by the time the attack finishes. Around 1997, Shor and Grover independently developed efficient quantum-computer algorithms that can give unprecedented speedup on certain mathematical problems. It then became evident that the advent of a large scale quantum computer can jeopardize secure communications. Nevertheless, it is still not clear whether there will exist large scale quantum computers able to break the current public key cryptographic standards. As a preemptive act, the National Institute of Standards and Technology (NIST) announced in 2015 its plans for transitioning to Post-Quantum (PQ) cryptographic algorithmic standards. The widespread adoption of the current standards , calls for further research on the efficiency and security of the PQ standards implementation on modern computing systems. This thesis intends to bridge the gap between the PQ cryptosystems’secure specification and their respectively secure and efficient implementation in advanced computing architectures.We specifically choose the PQ cryptosystem of Classic McEliece (CM), merely due to its long-standing security. CM has withstood attacks with minor modifications since its inception in 1978 and is currently a finalist of the NIST contest and has already been integrated in commercial products like VPN networks. This thesis comprises four main contributions. In the first one we present a hardware/software (HW/SW) co-design acceleration of the CM cryptosystem. The second contribution is geared towards the design and integration of custom designed and monolithic CM accelerators in a RISC-V based SoC. The third contribution strives to further optimize the performance of CM in hardware by introducing an advanced design of a monolithic accelerator for the encryption part of the CM cryptosystem. The final contribution of this thesis is moving away from a monolithic hardware accelerator and investigates the impact of vectorization by an SIMD unit on the CM application. With this thesis, we conclude a study conveyed on the CM cryptosystem, concerning its efficient hardware implementation on modern computing infrastructures. Nevertheless, there are numerous future research directions that could build on the knowledge gained as well as the hardware infrastructure designed in the context of this thesis. As such, we consider the secure implementation and side-channel mitigation on the CM hardware accelerators themselves and the performance evaluation of lightweight hardware implementations of CM.

(Català) (Català) La seguretat dels esquemes criptogràfics moderns es basa en problemes matemàtics que se suposa que són difícils de resoldre, com el problema de Rivest-Shamir-Adleman (RSA) o el problema del logaritme discret sobre corbes el•líptiques. L’ús dels ordinadors "clàssics" existents, tots els algorismes coneguts que intenten resoldre aquests problemes, requeriria una quantitat tan gran de temps de càlcul que en realitat farà que les dades interceptades siguin inútils quan finalitzi l’atac. Al voltant de 1997, Shor i Grover van desenvolupar de manera independent algorismes d’ordinador quàntic eficients que poden donar una velocitat sense precedents en determinats problemes matemàtics. Aleshores es va fer evident que l’arribada d’un ordinador quàntic a gran escala pot posar en perill les comunicacions segures. No obstant això, encara no està clar si existiran ordinadors quàntics a gran escala capaços de trencar els estàndards criptogràfics de clau pública actuals. Com a acte preventiu, l’Institut Nacional d’Estàndards i Tecnologia (NIST) va anunciar el 2015 els seus plans per a la transició als estàndards algorítmics criptogràfics Post-Quantum (PQ). L’adopció generalitzada dels estàndards actuals requereix més investigacions sobre l’eficiència i la seguretat de la implementació dels estàndards PQ en sistemes informàtics moderns. Aquesta tesi pretén salvar la bretxa entre l’especificació segura dels criptosistemes PQ i la seva implementació, respectivament, segura i eficient en arquitectures informàtiques avançades. Escollim específicament el criptosistema PQ de Classic McEliece (CM), només per la seva seguretat de llarga data. CM ha suportat atacs amb petites modificacions des dels seus inicis l’any 1978 i actualment és finalista del concurs NIST i ja s’ha integrat en productes comercials com les xarxes VPN. Aquesta tesi consta de quatre contribucions principals. En el primer presentem una acceleració de codisseny de maquinari/programari (HW/SW) del criptosistema CM. La segona contribució està orientada al disseny i la integració d’acceleradors CM monolítics i dissenyats a mida en un SoC basat en RISC-V. La tercera contribució s’esforça per optimitzar encara més el rendiment de CM al maquinari mitjançant la introducció d’un disseny avançat d’un accelerador monolític per a la part de xifratge del sistema criptogràfic CM. La contribució final d’aquesta tesi és allunyar-se d’un accelerador de maquinari monolític i investigar l’impacte de la vectorització per part d’una unitat SIMD en l’aplicació CM. Amb aquesta tesi, concloem un estudi vehiculat sobre el criptosistema CM, sobre la seva implementació eficient de maquinari en infraestructures informàtiques modernes. No obstant això, hi ha nombroses direccions futures de recerca que podrien basar-se en els coneixements adquirits així com en la infraestructura de maquinari dissenyada en el context d’aquesta tesi. Com a tal, considerem la implementació segura i la mitigació del canal lateral als propis acceleradors de maquinari CM i l’avaluació del rendiment de les implementacions de maquinari lleugeres de CM.

(Español) (Español) La seguridad de los esquemas criptográficos modernos depende de problemas matemáticos que se supone son difíciles de resolver, como el problema de Rivest-Shamir-Adleman (RSA) o el problema de logaritmos discretos sobre curvas elípticas. El uso de las computadoras "clásicas" existentes, todos los algoritmos conocidos que intentan resolver estos problemas, requeriría una cantidad tan grande de tiempo de cálculo que, de hecho, hará que los datos interceptados sean inútiles cuando finalice el ataque. Alrededor de 1997, Shor y Grover desarrollaron de forma independiente algoritmos eficientes para computadoras cuánticas que pueden dar una velocidad sin precedentes en ciertos problemas matemáticos. Entonces se hizo evidente que la llegada de una computadora cuántica a gran escala puede poner en peligro las comunicaciones seguras. Sin embargo, todavía no está claro si existirán ordenadores cuánticos a gran escala capaces de romper los actuales estándares criptográficos de clave pública. Como acto preventivo, el Instituto Nacional de Estándares y Tecnología (NIST) anunció en 2015 sus planes para la transición a estándares algorítmicos criptográficos poscuánticos (PQ). La adopción generalizada de los estándares actuales exige más investigaciones sobre la eficiencia y seguridad de la implementación de los estándares PQ en los sistemas informáticos modernos. Esta tesis pretende cerrar la brecha entre la especificación segura de los criptosistemas PQ y su implementación respectivamente segura y eficiente en arquitecturas informáticas avanzadas. Elegimos específicamente el criptosistema PQ de Classic McEliece (CM), simplemente debido a su seguridad de larga data. CM ha resistido ataques con modificaciones menores desde sus inicios en 1978 y actualmente es finalista del concurso NIST y ya se ha integrado en productos comerciales como redes VPN. Esta tesis comprende cuatro contribuciones principales. En el primero presentamos un codiseño hardware/software (HW/SW) de aceleración del criptosistema CM. La segunda contribución está orientada al diseño e integración de aceleradores CM monolíticos y diseñados a medida en un SoC basado en RISC-V. La tercera contribución se esfuerza por optimizar aún más el rendimiento de CM en hardware mediante la introducción de un diseño avanzado de un acelerador monolítico para la parte de cifrado del criptosistema CM. La contribución final de esta tesis se aleja de un acelerador de hardware monolítico e investiga el impacto de la vectorización por una unidad SIMD en la aplicación CM. Con esta tesis, concluimos un estudio realizado sobre el criptosistema CM, en relación con su implementación eficiente de hardware en infraestructuras informáticas modernas. Sin embargo, existen numerosas direcciones de investigación futuras que podrían aprovechar los conocimientos adquiridos, así como la infraestructura de hardware diseñada en el contexto de esta tesis. Como tal, consideramos la implementación segura y la mitigación de canales laterales en los propios aceleradores de hardware CM y la evaluación del rendimiento de implementaciones de hardware liviano de CM.