Consideremos un escenario en el que es necesario garantizar la seguridad de un almacén bancario. Se considera absolutamente impenetrable sin la clave que se te entrega desde el primer día de trabajo. Tu objetivo es conservar la clave de manera segura.

Supongamos que decidiste mantener la clave contigo en todo momento, permitiendo el acceso al almacén según sea necesario. Pero rápidamente te darás cuenta de que esta solución no se escala bien en la práctica, porque cada vez para abrir el almacén se requiere tu presencia física. ¿Y qué pasa con aquellas vacaciones que te prometieron? Además, hay una pregunta aún más inquietante: ¿qué pasaría si pierdes la única clave?

Pensando en las vacaciones, decidiste hacer una copia de la clave y confiarla a otro empleado. Sin embargo, entiendes que eso tampoco es ideal. Al duplicar el número de claves, también duplicaste las oportunidades de robo de la clave.

Desesperado, destruyes el duplicado y decides dividir la clave original en dos. Ahora, piensas, dos personas de confianza con fragmentos de la clave deben estar físicamente presentes para reunir la clave y abrir el almacén. Esto significa que el ladrón necesita robar ambos fragmentos, lo cual es el doble de difícil que robar una sola clave. Sin embargo, pronto te das cuenta de que este esquema no es mucho mejor que tener un solo clave, porque si alguien pierde la mitad de la clave, la clave completa no puede ser recuperada.

El problema se puede resolver con una serie de claves y cerraduras adicionales, pero con este enfoque se requerirán rápidamente muchas claves y cerraduras. Decides que en el esquema ideal, la clave debe dividirse para que la seguridad no dependa completamente de una sola persona. También concluyes que debe existir un umbral de cantidad de fragmentos, de modo que, al perder un fragmento (o si alguien se va de vacaciones), la clave completa permanezca funcional.

Cómo dividir un secreto

Este tipo de esquema de gestión de claves fue pensado por Adi Shamir en 1979, cuando publicó su trabajo "Cómo dividir un secreto". En el artículo se explica brevemente la llamada esquema umbral para la efectiva división de un valor secreto (por ejemplo, una clave criptográfica) en partes. Luego, cuando y solo cuando al menos de partes están reunidas, se puede recuperar fácilmente el secreto. .

Desde una perspectiva de seguridad, una propiedad importante de este esquema es que un atacante no debe aprender nada en absoluto si no tiene al menos fragmentos. Incluso la posesión de fragmentos no debe proporcionar ninguna información. Llamamos a esta propiedad seguridad semántica.

Interpolación polinómica

El esquema de umbral de Shamir se basa en la concepción de interpolación polinómica. Si no estás familiarizado con este concepto, en realidad es bastante simple. En general, si alguna vez has trazado puntos en un gráfico y luego los has conectado con líneas o curvas, ¡ya has utilizado este concepto!

A través de dos puntos, se puede trazar un número ilimitado de polinomios de grado 2. Para elegir uno de ellos de manera única, se necesita un tercer punto. Ilustración: Wikipedia

Consideremos un polinomio de grado uno, . Si deseas graficar esta función, ¿cuántos puntos necesitas? Bueno, sabemos que es una función lineal que forma una línea y, por lo tanto, se necesitan al menos dos puntos. Luego consideremos una función polinómica de grado dos, . Esta es una función cuadrática, por lo que se requieren al menos tres puntos para graficarla. ¿Qué hay de un polinomio de grado tres? Al menos cuatro puntos. Y así sucesivamente.

Lo realmente asombroso de esta propiedad es que, dado el grado de una función polinómica y al menos puntos, podemos derivar puntos adicionales para esta función polinómica. A esta extrapolación de esos puntos adicionales la llamamos interpolación polinómica.

Composición de secretos

Es posible que ya hayas comprendido que aquí entra en juego el ingenioso esquema de Shamir. Supongamos que nuestro secreto — es . Podemos convertir en un punto en un gráfico y crear una función polinómica de grado , que satisfaga este punto. Recordemos que será nuestro umbral de fragmentos requeridos, por lo que si establecemos el umbral en tres fragmentos, debemos elegir una función polinómica de grado dos.

Nuestro polinomio tendrá la forma , donde y — números enteros positivos seleccionados al azar. Simplemente estamos construyendo un polinomio de grado , donde el coeficiente libre  es nuestro secreto , y cada uno de los siguientes los miembros tienen un coeficiente positivo elegido al azar. Si regresamos al ejemplo inicial y suponemos que , entonces obtendremos una función .

En este punto, podemos generar fragmentos conectando números enteros únicos en , donde (porque ese es nuestro secreto). En este ejemplo, queremos distribuir cuatro fragmentos con un umbral de tres, así que generamos puntos al azar y enviamos un punto a cada una de las cuatro personas de confianza, los custodios de la clave. También les informamos que , ya que se considera información pública y es necesaria para la recuperación .

Recuperación del secreto

Ya hemos discutido el concepto de interpolación polinómica y cómo se basa en el esquema de umbral de Shamir . Cuando cualquiera de las tres de las cuatro personas de confianza quiere recuperar , solo necesitan interpolar con sus puntos únicos. Para ello, pueden definir sus puntos y calcular el polinomio de interpolación de Lagrange usando la siguiente fórmula. Si la programación te resulta más comprensible que las matemáticas, pi es esencialmente un operador para, que multiplica todos los resultados, y la sigma es para, que suma todo.

Al podemos resolver esto de la siguiente manera y devolver nuestra función polinómica original:

Dado que sabemos que , la recuperación se realiza simplemente:

Uso de la aritmética entera insegura

Aunque hemos aplicado con éxito la idea principal de Shamir , aún tenemos un problema que hemos ignorado hasta este momento. Nuestra función polinómica utiliza aritmética entera insegura. Ten en cuenta que por cada punto adicional que el atacante obtiene en el gráfico de nuestra función, quedan menos posibilidades para otros puntos. Puedes verlo tú mismo al graficar con un aumento en el número de puntos para la función polinómica usando aritmética entera. Esto es contraproducente para nuestro objetivo de seguridad, porque un atacante no debería aprender absolutamente nada, hasta que tenga al menos fragmentos.

Para demostrar cuán débil es el esquema de aritmética entera, consideremos un escenario en el que un atacante obtuvo dos puntos y conoce la información pública, que . De esta información, puede deducir , igual a dos, y conectar en la fórmula los valores conocidos y .

Luego, el atacante puede encontrar , al calcular :

Dado que hemos definido como números enteros positivos seleccionados al azar, hay un número limitado de posibles . Con esta información, el atacante puede deducir , ya que cualquier cosa mayor que 5 hará negativo. Esto resulta ser cierto, ya que hemos definido

Luego, el atacante puede calcular los posibles valores , reemplazando en :

Con un conjunto limitado de opciones para se hace evidente lo fácil que es adivinar y verificar valores . Aquí hay solo cinco opciones.

La solución al problema de la aritmética entera insegura

Para mitigar esta vulnerabilidad, Shamir sugiere utilizar aritmética modular, reemplazando en , donde y — el conjunto de todos los números primos.

Recordemos rápidamente cómo funciona la aritmética modular. Un reloj con manecillas es un concepto familiar. Utiliza un reloj que es . Una vez que la manecilla de la hora pasa por el doce, vuelve al uno. Una propiedad interesante de este sistema es que, simplemente mirando el reloj, no podemos deducir cuántas vueltas ha dado la manecilla. Sin embargo, si sabemos que la manecilla ha pasado por el 12 cuatro veces, podemos determinar completamente cuántas horas han pasado usando una simple fórmula , donde  — este es nuestro divisor (aquí ),  — es el cociente (cuántas veces el divisor cabe exactamente en el número original, aquí ), y  — es el residuo que típicamente devuelve la operación de módulo (aquí ). Conocer todos estos valores nos permite resolver la ecuación para , pero si omitimos el cociente, nunca podremos recuperar el valor original.

Se puede demostrar cómo esto mejora la seguridad de nuestro esquema aplicando el esquema a nuestro ejemplo anterior y utilizando . Nuestra nueva función polinómica , y los nuevos puntos . Ahora, los guardianes de la clave pueden nuevamente usar la interpolación polinómica para recuperar nuestra función, solo que esta vez las operaciones de suma y multiplicación deben acompañarse de reducción módulo (p.ej. ).

Usando este nuevo ejemplo, supongamos que el atacante conocía dos de estos nuevos puntos, , y la información pública . Esta vez, el atacante, basándose en toda la información que tiene, deduce las siguientes funciones, donde  — el conjunto de todos los números enteros positivos, y representa el coeficiente del módulo .

Ahora, nuestro agresor vuelve a encontrar , calculando :

Luego, vuelve a intentar deducir , reemplazando en :

Esta vez tiene un problema serio. En la fórmula faltan valores , y . Dado que hay una cantidad infinita de combinaciones de estas variables, no puede obtener más información.

Consideraciones de seguridad

El esquema de distribución secreta de Shamir ofrece seguridad desde el punto de vista de la teoría de la información. Eso significa que las matemáticas son resistentes incluso ante un atacante con potencia computacional ilimitada. Sin embargo, el esquema aún presenta varios problemas conocidos.

Por ejemplo, el esquema de Shamir no genera fragmentos verificables, es decir, las personas pueden presentar fragmentos falsificados y obstaculizar la recuperación del secreto correcto. Un guardián hostil de fragmentos con suficiente información incluso puede generar otro fragmento, alterando a su conveniencia. Este problema se resuelve con esquemas de distribución secreta verificables, como el esquema de Feldman.

Otro problema es que la longitud de cualquier fragmento es igual a la longitud del secreto correspondiente, por lo que es fácil determinar la longitud del secreto. Este problema se soluciona mediante una rellenado del secreto con números arbitrarios hasta una longitud fija.

Finalmente, es importante señalar que nuestras preocupaciones sobre la seguridad pueden ir más allá del propio esquema. En aplicaciones criptográficas reales, a menudo existe la amenaza de ataques a través de canales colaterales, donde los atacantes intentan extraer información útil del tiempo de ejecución de la aplicación, la memoria caché, fallas, etc. Si esto es preocupante, se deben considerar cuidadosamente medidas de seguridad durante el desarrollo, como funciones y búsqueda con un tiempo de ejecución constante, evitar el almacenamiento en memoria en disco y pensar en una serie de otras cosas que van más allá de este artículo.

Demo

En esta página hay una demostración interactiva del esquema de distribución de secretos de Shamir. La demostración se realiza sobre la base de la biblioteca ssss-js, que en sí misma es un puerto de JavaScript de un programa popular ssssTenga en cuenta que el cálculo de valores grandes , y puede tardar un tiempo.

Fuente: habr.com