Post Quantum Cryptography

July 16, 2024 - 9 mins read

Notas utilizadas para mi presentacion sobre criptografía post cuántica con la que me recibí de Ingeniero en Computación 🎓

Introducción/Contexto de PQC

La criptografía de llave pública depende de funciones matemáticas que son “fáciles de hacer y difíciles de deshacer” (to do and to undo). Las variantes más utilizadas hasta ahora son vulnerables al Algoritmo de Shor:

RSA: factorización de números primos
Diffie-Hellman: problema del logaritmo discreto

Si se puede resolver el problema matemático, se puede romper la criptografía.

Surgen como solución algortimos de criptografía “post-cuántica”, es decir que serían resisitibles a ataques cuánticos. IMPORTANTE: Estos no son algoritmos que trabajan bajo la mecánica cuántica (en computadoras cuánticas), sino que lo hacen bajo las computadoras clásicas y funcionarían como reemplazo en la infraestructura que se tiene funcionando hoy en día.

Estos algoritmos son principalmente basados en Lattices, una herramienta matemática ampliamente utilizada en este tipo de criptografía. Se diferencia desde el punto de vista matemático de los algoritmos de la criptografía actual, ya que estos están basados principalmente en la Teoría de Números.

Keys

Public Key cryptography relies on math functions that are easy to do and difficult to undo
- RSA: prime factorization
- Diffie-Hellman: discrete log problem
If you can solve the underlying problem, then you can break the crypthography.

Shors algotrithm

Problema hoy: se podrían obtener mensajes encriptados hoy y desencriptar en un futuro con computadoras cuánticas. PQC busca resolver esto.

PQC Crypthography: criptografía que es resistente a ataques con una computadora cuántica. Pero la criptografía funciona en una computadora normal.

≠ Quantum crypthography: Cryptography on a quantum computer

Quantum computers are not “supercomputers” they seem to be much better at doing specific tasks: like prime factorization.

We need to develop standards that are secure against both quantum and classical computers.

Supersingular Isogeny Key Exchange (SIKE)

Lattices based cryptography: array of dots

https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/

What’s the Rush?

Por ahora están lejos las computadoras cuánticas. Por qué apurarse?

Harvesting attacks: store today’s ciphertexts to break later
Rewrite history: forge signatures for old keys. Agarrar contratos viejos y firmarlos con llaves “falsificadas”. “El que controla la historia controla el futuro”. Modificaciones en la blockchain

El problema de poder cambiar o ver el pasado.

Lattices

2d lattice se crea a partir de dos vectores. Desde ahí se construye a partir de la superposición de vectores

../image

Los vectores azul y rojo son las bases del Lattice.

Dos pares de vectores bases del lattice pueden generar el mismo lattice

Historia

RSA/Diffie-Hellman - Basados en Teoría de números

Factorización de números primos
Ellpitic curve
Discrete log

Reemplazar esto con “lattice-based” problems. Es una rama distinta de las matemáticas. Problemas más difíciles.

¿Por qué?

Eficientes: linear, embarrassingly parallel operations
Resisten ataques quánticos (conjeturas de que nunca se podrán romper)
Security from mild worst-case assumptions: Es necesario que sea difícil que romper en el caso “promedio”, no simplemente en casos especiales, ya que las claves públicas y privadas se generan de forma aleatoria.
Dio soluciones al fully homomorphic Encryption (FME) problem.

Qué es una Lattice?

Intuitivamente: Una grid de puntos generado a partir de la suma de dos vectores base.

Dada una base> $B = {b_1,…,b_n}$ se genera el Lattice

$$ \cal L = \sum_{i=1}^n (\mathbb{Z} \cdot b_i) $$

La misma Lattice pueden tener distinta base

Problemas dificiles con Lattices

Encontrar la suma de vectores de la base que de el punto más cercano al origen dentro de un factor de aproximación gamma: $(Gap)SVP_{\gamma}, SIVP_{\gamma}$
Para $\gamma=poly(m)$, la solución requiere $2^{\Omega(n)}$ tiempo (y espacio)

Shortest vector problem

Pregunta “increíblemente difícil”: ¿qué combinación de vectores genera el punto más cercano al origen? (sin contar el origen). Esto es el shortest vector problem: SVP.

A mayores dimensiones se complejiza todavía más el SVP

Es similar al “closest vector problem”: qué combinación da el punto más cercano a un punto arbitrario.

Estos se conocen como “lattice-problems”. Son muy difíciles incluso para computadoras cuánticas, son la base matemática de PQC.

El problema es más difícil de resolver cuanto menos perpendiculares son los vectores (bad basis).

Alice usa una good basis (private system)

../image

Bob embeds a message on the lattice her lattice.

Introduction to Lattice-based crypto - Florida University

Contexto: Luego de 8 años quedaron 3 finalistas a ser estandarizados:

Key Encapsulation Mechanism (KEMs)
- CRYSTALS-Kyber: FIPS 203
Digital Signatures
- CRYSTALS-Dilithium: FIPS 204
- FALCON
- SPHINCS+: FIPS 205

../image

Lattice

Un Lattice es una combinación $\mathbb{Z}$ -lineal de $n$ vectores independientes $b_i \in \mathbb{Z}^n$

$$ \cal L = \sum_{i=1}^n (\mathbb{Z} \cdot b_i) $$

Se genera un espacio de puntos con coordenadas enteras.

Cuando las bases son ortogonales resolver CVP es muy fácil

Queremos encontrar el punto más cercano a $\begin{bmatrix} 27 \ 8 \end{bmatrix}$

$$ L = \{ z_1 \mathbf{b}_1 + z_2 \mathbf{b}_2 \} = \left\{ z_1 \begin{bmatrix} 37 \\ 41 \end{bmatrix} + z_2 \begin{bmatrix} 103 \\ 113 \end{bmatrix} \right\} $$$$ \begin{cases}37 z_1 - 103 z_2 = 27 \\41 z_1 + 113 z_2 = 8\end{cases}\Rightarrow\begin{cases}z_1 = -53.023 \\z_2 = 19.309\end{cases}\Rightarrow (z_1, z_2) = (-53, 19) z_1 \begin{bmatrix} 37 \\ 41 \end{bmatrix} + z_2 \begin{bmatrix} 103 \\ 113 \end{bmatrix} = -53 \begin{bmatrix} 37 \\ 41 \end{bmatrix} + 19 \begin{bmatrix} 103 \\ 113 \end{bmatrix} = \begin{bmatrix} -4 \\ -26 \end{bmatrix} $$

Learning With Errors (LWE)

Primero hablar acerca de que operamos con matrices, caso del learning without errors y qué pasaría en tal caso (el secreto no es secreto). Luego ingresar el tema del módulo

Idea intuitiva

without errors: alice tiene un vector secreto (private key) que hace que un sistema de ecuaciones (clave publica) sea verdadero. No es seguro

Incorporando errores: se le suma un “error” a cada resultado de la ecuación. Estos errores son parte del secreto. Tiene más ecuaciones que variables, sistema sobredeterminado.

LWE puede ser “reframed” como un lattice problem, por lo que se cree que es igual de difícil

The LWE problem was introduced by Oded Regev in 2005[3] (who won the 2018 Gödel Prize for this work); it is a generalization of the parity learning problem. Regev showed that the LWE problem is as hard to solve as several worst-case lattice problems.

Descripción presentación

../image

Descripción Peikert

Parametros:

Dimensión n
Módulo q=poly(n)
Distribución de error

$$ a_1 \leftarrow \mathbb{Z}_q^n, \quad b_1 = (s, a_1) + e_1 \in \mathbb{Z}_q \\a_2 \leftarrow \mathbb{Z}_q^n, \quad b_2 = (s, a_2) + e_2 \in \mathbb{Z}_q \\\vdots $$

Se crea una matriz A con los a sub i.

$$ (\ldots A \ldots), \quad (\ldots b^t \ldots) \quad \Rightarrow \quad s^t A + e^t $$

Variantes del problema

Búsqueda: Encontrar s
Decisión: Distinguir si se usa el sistema “ruidoso” o el “uniforme”

LWE es difícil

Se muestra con reducciones. Reducción es un método mediante el cual un problema se transforma en otro con el propósito de demostrar que el segundo es al menos tan difícil como el primero. (Esto es lo que muestra Oded Regev en el 2005)

$$ (n/\alpha)\text{-approx worst case lattice problems} \leq \text{search/decision - LWE} \leq \text{crypto} $$

Una reducción cuántica implica que la complejidad intrínseca del problema original (por ejemplo, un problema de retícula en el peor caso) se preserva o se traduce adecuadamente incluso cuando se aborda con herramientas cuánticas. Esto significa que aunque utilicemos computadoras cuánticas, que pueden ser exponencialmente más rápidas para ciertos cálculos, el problema reducido sigue siendo un desafío significativo.

Tipos de LWE que aumentan la eficiencia.

../image

Kyber usa MLWE puesto que con el parámetro k se pueden alcanzar niveles de seguridad mayores: 2,3,4. En RLWE habría que cambiar el tamaño de A (matriz de pol).

Estándares, uso comercial

Hay 4 algoritmos seleccionados para estandarizar, de los cuales 3 ya se tiene un estándar escrito: FIPS 203, FIPS, 204, FIPS 205. El draft (borrador) se publicó el 24 de agosto de 2023, y los comentarios en diciembre del mismo año. Se espera que para 2024 sean publicadas las versiones finales

../image

Demostración

Tutorial: https://developer.ibm.com/tutorials/set-up-a-quantum-safe-ssh-connection/

# updates
sudo apt update
sudo apt -y upgrade

# install dependencies
sudo apt -y install autoconf \
                    automake \
                    cmake \
                    gcc \
                    git \
                    libtool \
                    libssl-dev \
                    make \
                    ninja-build \
                    zlib1g-dev

# clone the repo
git clone --depth 1 https://github.com/open-quantum-safe/openssh.git
cd openssh

Los algoritmos PQC están implementados en una librería llamada liboqs. Es necesario hacer un build de la misma para luego hacer un build de este fork de OpenSSH.

# build/install liboqs
./oqs-scripts/clone_liboqs.sh
./oqs-scripts/build_liboqs.sh

# build openssh
sudo ./oqs-scripts/build_openssh.sh

Algoritmos soportados: https://github.com/open-quantum-safe/openssh#supported-algorithms El que nos interesa a nosotros es Kyber pues es el que va a estandarizar este año el NIST bajo el nombre FIPS-203.

Config OpenSSH

OpenSSH has been configured with the following options:
                     User binaries: /usr/local/bin
                   System binaries: /usr/local/sbin
               Configuration files: /usr/local/etc
                   Askpass program: /usr/local/libexec/ssh-askpass
                      Manual pages: /usr/local/share/man/manX
                          PID file: /var/run
  Privilege separation chroot path: /var/empty
            sshd default user PATH: /usr/bin:/bin:/usr/sbin:/sbin:/usr/local/bin
                    Manpage format: doc
                       PAM support: no
                   OSF SIA support: no
                 KerberosV support: no
                   SELinux support: no
                   libedit support: no
                   libldns support: no
  Solaris process contract support: no
           Solaris project support: no
         Solaris privilege support: no
       IP address in $DISPLAY hack: no
           Translate v4 in v6 hack: yes
                  BSD Auth support: no
              Random number source: OpenSSL internal ONLY
             Privsep sandbox style: seccomp_filter
                   PKCS#11 support: yes
                  U2F/FIDO support: yes

              Host: x86_64-pc-linux-gnu
          Compiler: cc
    Compiler flags: -g -O2 -pipe -Wno-error=format-truncation -Wall -Wextra -Wpointer-arith -Wuninitialized -Wsign-compare -Wformat-security -Wsizeof-pointer-memaccess -Wno-pointer-sign -Wno-unused-parameter -Wno-unused-result -Wimplicit-fallthrough -Wmisleading-indentation -fno-strict-aliasing -D_FORTIFY_SOURCE=2 -ftrapv -fzero-call-used-regs=all -ftrivial-auto-var-init=zero -fno-builtin-memset -fstack-protector-strong -fPIE
Preprocessor flags:  -D_XOPEN_SOURCE=600 -D_BSD_SOURCE -D_DEFAULT_SOURCE
      Linker flags:  -Wl,-z,relro -Wl,-z,now -Wl,-z,noexecstack -fstack-protector-strong -pie
         Libraries: -lcrypto -lz  -lcrypt

Recursos

Usos en la industria

Noticias post

9 de diciembre de 2024, Google lanza un nuevo chip cuántico

Google’s blog

Security Week: Google’s willow chip

Puntos a considerar

105 qubits
Los 105 qubits no son tan interesantes comparados con los 433 de IBM
Lo que sí es interesante es la capacidad de correción de errores

Karl Holmqvist, founder and CEO of Lastwall, explains the process. “What Google achieved with Willow involves something called random circuit sampling (RCS), which generates random quantum circuits specifically designed as a benchmark for quantum computers,” he told SecurityWeek.