Pregunta:
He construido un GPS basado en el microcontrolador AVR. El GPS se utiliza para registrar datos de vuelo para competiciones. El archivo de registro se actualiza 10 veces por segundo. Lo que me gustaría hacer es asociar una firma con este archivo para que cualquiera pueda confirmar que el archivo fue escrito por el GPS.
Esto sugiere que el GPS debería tener una clave privada de algún tipo internamente y que la verificación debería ocurrir a través de una clave pública. Sin embargo, hay un par de importantes limitaciones de hardware:
- El AVR es un procesador de 8 bits que funciona a 8 MHz. Puedo mantener un hash MD5 en ejecución del archivo, pero no hay suficiente tiempo entre las muestras para calcular, por ejemplo, una firma ECDSA.
- El hardware no sabe cuándo se apagará. Cuando el usuario apaga el interruptor, simplemente se apaga. Esto significa que no es posible realizar el hash/firma una vez justo antes del apagado. La firma tendría que actualizarse cada vez que se agrega una nueva fila al archivo de registro, es decir, 10 veces por segundo.
Algo así como un HMAC se ajustaría a las limitaciones del procesador, pero no a la necesidad de verificación pública. ¿Existe alguna variante de un HMAC que pueda calcularse con una clave privada y luego verificarse con una contraparte pública?
¡Gracias por tu ayuda!
Respuesta:
Los algoritmos de firma de la familia ECDSA son susceptibles de precálculos. De hecho, cuando desea firmar el mensaje m con ECDSA, el proceso es el siguiente:
-
Trabajamos en una curva (o un subgrupo de una curva) de orden $n$ (un entero primo). Se da un generador convencional $G$ (un punto de orden fijo $n$ ). La clave privada es $x$ (un módulo entero distinto de cero $n$ ) y la clave pública es el punto $Q = xG$ .
-
Genere (para cada firma) un nuevo entero aleatorio distinto de cero $k$ módulo $n$ . El número entero DEBE seleccionarse uniformemente en todo el rango (esto es importante).
-
Calcular el punto $kG$ , extraer su coordenada $X$ y reducirlo módulo $n$ ; esto produce la primera mitad de la firma, $r$ .
-
Mensaje hash $m$ y truncar/reducir el valor hash a un módulo entero $n$ (llamémoslo $h$ ).
-
Calcule la segunda mitad de la firma: $s = (h+xr)/k \pmod n$
El punto aquí es que la parte más costosa, que es el cálculo de $kG$ , en realidad no depende del mensaje que se va a firmar. Por lo tanto, se puede hacer por adelantado, antes de que se obtenga el mensaje $m$ . Una configuración de precomputación generaría previamente un montón de valores $k$ , con los valores correspondientes $r$ y $1/k \pmod n$ , reduciendo así la parte en línea de la firma a un par de multiplicaciones modulares y una adición modular. Esto, sin embargo, requiere los siguientes comentarios:
-
El proceso anterior requiere un $k$ aleatorio, producido con un generador aleatorio de calidad criptográfica. Esto es algo difícil de poner en práctica, especialmente en sistemas integrados. Dado que la falla en el uso de una buena aleatoriedad puede exponer la clave privada en sí misma (y tales errores han ocurrido en la práctica), se ha definido otro mecanismo para generar el valor de $k$ , denominado desaleatorización . En el caso de ECDSA, esto se describe en RFC 6979 . Sin embargo, aunque esto elimina la necesidad de una fuente aleatoria, hace que $k$ dependa del mensaje de entrada $m$ . Como tal, evita los cálculos previos.
-
ECDSA, tal como lo definen los estándares relevantes, opera en curvas "clásicas", que no son necesariamente las curvas más rápidas. Es posible que desee investigar EdDSA , y especialmente Ed25519 (aplicación de EdDSA a una curva específica de 255 bits). Esto se puede hacer, pero puede encontrarse con algunos problemas adicionales:
-
EdDSA se especifica como desaleatorizado, por lo que no hay cálculos previos. Sucede que el verificador de firmas no puede saber realmente si el firmante fue desrandomizado o no, por lo que podría "volver a aleatorizar" el algoritmo, lo cual es totalmente herético desde un punto de vista criptográfico y, por lo tanto, posible pero lleno de peligros.
-
El cálculo de la firma real utiliza una invocación de función hash, que se define como SHA-512. SHA-512 es razonablemente eficiente… en grandes escritorios y servidores, donde están disponibles registros de 64 bits. A su AVR de 8 bits no le gustará.
-
-
Los precálculos pueden ayudarlo solo si tiene tiempo para precalcular. El caso de uso típico para los cálculos previos es pagar un peaje en una autopista o puente: el dispositivo de firma en un automóvil tiene muy poco tiempo para calcular la firma real (la transacción debe completarse mientras el dispositivo inalámbrico está dentro del alcance del aparato de detección, y eso no dura porque el coche no frena), sino minutos si no horas para preparar la siguiente firma. En su caso, tiene un flujo de firmas largo y potencialmente ilimitado para calcular, por lo que no es obvio si tiene suficiente tiempo para hacer todos los cálculos previos.
Para dar algunas cifras, en este artículo se describe el récord actual de cálculos de curvas elípticas en procesadores AVR de 8 bits; calculan una multiplicación de puntos en Curve25519 en aproximadamente 14 millones de ciclos de reloj. Esto es sustancialmente más alto que su presupuesto (a 0,400 millones de ciclos por firma).
Aquí hay algunas ideas que pueden ayudar (o no):
-
Las curvas "modernas" como Curve25519 están diseñadas bajo la premisa esencial de que las multiplicaciones son rápidas. Esto es cierto para la CPU en los sistemas de servidor y de escritorio, y también en los teléfonos inteligentes. Pero no en AVR de 8 bits. Por lo tanto, no son necesariamente una buena opción en tu caso específico.
-
Supongo que el valor de sus firmas no es tan alto. Quiero decir, te preocupas por las falsificaciones, pero un registro falso no generará miles de millones de dólares para los atacantes. Como tal, probablemente podría tolerar un nivel de seguridad ligeramente más bajo. Una curva de aproximadamente 160 bits proporcionará un nivel de seguridad de alrededor de $2^{80}$ , que está más allá de los registros públicos actuales en la ruptura de curvas. Esto es tecnológicamente alcanzable, pero a un costo tremendo (estamos hablando de miles de millones de dólares aquí), por lo que es poco probable que se haga simplemente para hacer un registro de GPS falso (supongo que estás hablando de carreras de drones o algo similar).
-
En estas condiciones, diría que entre las curvas conocidas, la más rápida probablemente sea la K-163 , descrita en FIPS 186-4 . Esta curva tiene una estructura especial que permite cálculos más rápidos, siempre que aplique algunas matemáticas extrañas (el endomorfismo de Frobenius). Sin embargo, incluso con todo el poder del Frobenius, me temo que todavía no se ajustaría al costo por firma en 400k ciclos de reloj.
-
El usuario humano es humano; él no es tan rápido. Con eso, quiero decir que si bien no puede predecir cuándo el usuario accionará el interruptor, aún puede indicarle a dicho usuario que al accionar el interruptor puede perder, digamos, los últimos dos segundos de los registros de GPS. Por lo tanto, podría calcular una firma cada 2 segundos, en veinte líneas de registros de una sola vez, en lugar de hacer diez firmas por segundo. ¡Acabo de multiplicar su presupuesto de CPU por 20! Y ahora, ECDSA con K-163 puede convertirse en una solución realista.
-
Es posible que desee considerar conectar una CPU mejor. En un receptor GPS, lo más probable es que la parte de la radio use mucha más energía que la CPU, por lo que podría usar una CPU más robusta. El ARM Cortex-M0+ , con una frecuencia de reloj de 48 MHz, consumiría como máximo unos pocos milivatios (incluida la energía para un poco de RAM) y puede calcular una firma Ed25519 en menos de 200 ms.
Otra idea, completamente diferente, sería utilizar el esquema de firma de Lamport . Utiliza solo funciones hash y puede ser muy rápido. Su problema principal es que se trata de un esquema de firma de un solo uso : si firma dos mensajes distintos con la misma clave privada, entonces revela la clave privada y las falsificaciones se vuelven fáciles. No obstante, en tu caso concreto, podrías aplicarlo de la siguiente forma:
- Antes de un vuelo, el sistema GPS genera un nuevo par de claves pública/privada y exporta la clave pública.
- Durante el vuelo, el sistema calcula regularmente una nueva firma sobre la totalidad del archivo de registro y reemplaza la firma anterior. Así, solo guarda una única firma en su sistema de almacenamiento. Esto utiliza el hecho de que la clave privada se revela solo al mostrar dos firmas; Por lo tanto, los valores de firma que nunca se muestran no son un problema.
- La clave privada se mantiene solo en la RAM, por lo que desaparece cuando el sistema se apaga.
Para facilitar el uso, podría imaginar un sistema híbrido:
- El sistema tiene un par de claves "permanentes", para usar en ECDSA o Ed25519 o un sistema similar.
- Cuando arranca, genera un nuevo par de claves públicas/privadas de Lamport.
- La clave pública está firmada con la clave ECDSA/Ed25519/lo que sea; la clave pública de Lamport y la firma se almacenan en el encabezado del archivo de registro.
- La firma de Lamport en ejecución se calcula aproximadamente cada segundo, como se describió anteriormente.
- La clave privada de Lamport desaparece al apagar.
La combinación de todas las ideas anteriores me hace pensar que lo que está buscando es posible , pero ciertamente no es un lugar común. Usted se adentrará mucho en la criptografía arcana, y sabemos, por experiencia, que tales cosas son difíciles , en particular porque no hay una prueba de seguridad (puede probar la funcionalidad , pero no puede saber fácilmente si lo que produjo es seguro).
Entonces, es un proyecto divertido, pero no construyas un negocio sobre él.