Cómo funciona el secreto compartido de Shamir

• El secreto compartido de Shamir divide un secreto en varias partes, y solo puede recuperarse cuando se reúne al menos el umbral requerido; con menos que eso no se revela ninguna información
• Es útil cuando es difícil confiarle todo el secreto a una sola persona y también se necesita poder recuperarlo aunque se pierdan algunas partes, como con la clave maestra de una empresa, la recuperación de una cuenta familiar o los respaldos de un equipo
• El modelo central oculta el secreto como el valor en el punto 0 de un polinomio, y entrega cada parte como un punto sobre la curva
• Para un umbral k se usa un polinomio de grado k - 1: dos partes corresponden a una recta, tres partes a una parábola y cuatro partes a una curva cúbica
• El Legacy Kit de Ente usa este método como una capa para evitar que una tarjeta se convierta en una clave de recuperación permanente y para permitir descartar las tarjetas emitidas

---

Cómo se divide un secreto con puntos y polinomios

• Es un método publicado por Adi Shamir en 1979, y su punto clave no es solo que sea “difícil de romper”, sino que si faltan suficientes partes, no se revela absolutamente ninguna información
• Dos puntos distintos determinan exactamente una sola recta, pero con un solo punto hay infinitas rectas que pasan por él, y cada una cruza el eje vertical en una posición diferente
• Si el secreto fuera el número 7, ese valor puede ocultarse en la posición donde la recta cruza el eje vertical
• La pendiente no es el secreto en sí, sino que actúa como aleatoriedad para ocultarlo
• Si a cada persona se le entrega un punto sobre la recta, con el punto de una sola persona siguen existiendo infinitas rectas posibles, todas compatibles con secretos distintos
• Al combinar dos puntos, la recta queda fijada, y se puede recuperar el secreto leyendo el valor que esa recta tiene en 0
• Esta estructura es un esquema de secreto compartido 2-de-n: se pueden crear tantos puntos como se quiera, pero cualquier par de puntos permite reconstruir la recta
• Cuando aumenta el umbral, se usan curvas de mayor grado
  • Una parábola solo queda determinada con tres puntos, así que si el secreto se oculta en la posición donde la parábola cruza el eje vertical, puede recuperarse con cualquier tres partes y no con dos
  • En general, para un umbral k se usa un polinomio de grado k - 1
  • 2 partes corresponden a una recta, 3 partes a una parábola y 4 partes a una curva cúbica
  • En la implementación real no se usa papel cuadriculado, sino aritmética de campos finitos, pero la estructura es la misma: el secreto es el valor en 0, coeficientes aleatorios lo ocultan y cada parte es un punto del polinomio
  • Lo importante es que, si faltan partes, no es simplemente que sea difícil calcular el secreto, sino que todos los secretos posibles siguen siendo igualmente posibles

Ente Legacy Kit y materiales de referencia

• Ente usa esta idea en Legacy Kit
• El objetivo no es solo dividir un secreto, sino permitir la recuperación sin que las partes divididas se conviertan en una clave de recuperación permanente
• Legacy Kit usa el método de Shamir como una capa dentro de un flujo más amplio
• La tarjeta no contiene la clave de recuperación en sí; en su lugar, primero reconstruye otro secreto de forma local y luego participa en una recuperación mediada por el servidor
• Gracias a esta estructura, las tarjetas emitidas pueden descartarse y una tarjeta perdida no se convierte en una carga permanente
• Materiales de referencia
  • “How to Share a Secret”, de Adi Shamir
  • “Sharing Secrets Among Friends”, de Bruce Schneier
  • La historia de PayPal de Max Levchin
  • Código fuente de Ente

[GN⁺]

Comentarios en Hacker News

• Escribí mi tesis de maestría sobre este tema. Hice una app que divide y guarda datos entre varios proveedores de almacenamiento comunes como Dropbox, Google Drive y OneDrive, y usé compartición de secretos para complementar el cifrado
  La ventaja era que los proveedores ya no podían leer los datos, además había redundancia adicional porque bastaba con que sobrevivieran 2 lugares, y a diferencia de otras apps de almacenamiento seguro donde todo se acaba si olvidas la contraseña maestra, aquí se podían usar los procedimientos normales de recuperación de cuenta

  • La idea suena bien; me pregunto si después se convirtió en un producto o en una app de código abierto

• Me pregunto si hay alguna forma de combinar múltiples pares clave/valor en un solo texto cifrado, sin simplemente concatenarlos ni hacer explotar el tamaño del resultado, de modo que todas las personas que metan información en este esquema almacenen el mismo bloque cifrado pero con sus propias claves puedan descifrar valores distintos
  Así la gente podría servir como respaldo mutuo y aun así tener negación plausible sobre lo que está almacenado

• En mi tesis de maestría apliqué compartición de secretos de Shamir a una red mesh. La idea era que, aunque un nodo de la malla fuera comprometido por un atacante y se recuperara el secreto de ese nodo, siguiera siendo imposible romper todo el cifrado

• Nuestro equipo usa esta técnica para distribuir la frase de acceso de un almacén de secretos secundario de una forma “democráticamente segura”. Ese almacén secundario contiene la forma de acceder al almacén de secretos principal
  https://packages.debian.org/trixie/ssss es una implementación decente y bastante intuitiva

• Shamir me salvó de verdad una vez. Tuve que restaurar con urgencia un respaldo casi olvidado, y pude reconstruir la contraseña aleatoria que se había usado entonces
  Menos mal que había repartido los fragmentos distribuidos entre familiares “por si acaso”

• La parte de “lo útil no es que con muy pocos fragmentos sea difícil calcular el secreto; es que con muy pocos fragmentos no hay absolutamente ninguna información sobre el secreto. Si falta un fragmento, todos los secretos posibles siguen siendo posibles” me recuerda al proceso de factorizar números con un cuerpo cuadrático o alguna variante
  Vas encontrando un sistema de congruencias mod n y al final calculas los factores primos, pero antes de reunir suficientes no se puede. Cada congruencia debe contener algo de información, así que siempre me he preguntado en qué espacio estamos reduciendo grados de libertad
  Aquí también, cada fragmento restringe el espacio de polinomios, pero no lo suficiente como para revelar el punto donde la clave cruza el eje

• Es una técnica realmente genial, e incluso podría enseñarse en secundaria como un ejemplo interesante de lo que un científico de la computación puede hacer con polinomios

  • Soy profesor de matemáticas de secundaria y de hecho se lo enseño así a mis alumnos
    Cuando vemos cómo reconstruir la ecuación de una función lineal, presento Shamir, y hago que los estudiantes elijan un PIN secreto como pendiente, creen dos puntos y se los repartan a otros dos alumnos. Esos dos luego tienen que juntarse para recuperar el PIN, y los estudiantes siempre se enganchan muchísimo

• Bruce Schneier explicó esto en el libro clásico Applied Cryptography, y HashiCorp Vault también tenía una implementación en Go. En la práctica, siempre me he preguntado de cuántos bits deberían ser los fragmentos distribuidos
  La respuesta que escuché en un grupo de noticias fue: “1 bit más que la longitud real de la clave”. Hoy me pregunto cómo afectará la amenaza de la computación cuántica a 1) la elección del tamaño de los fragmentos y 2) las ventajas y desventajas de la compartición de secretos en general

  • El esquema básico de Shamir es seguro a nivel de teoría de la información, así que no le afectan en absoluto las computadoras cuánticas
    Si creas fragmentos Shamir de umbral “10 de” para un secreto de 1 byte y das 9 de esos fragmentos de 1 byte, ninguna computadora del universo podrá averiguar el secreto. En implementaciones reales hay que agregar algunas bytes extra para verificación de integridad, como un código de autenticación de mensajes o una suma de verificación
  • Como a las computadoras normales no les gustan mucho los errores, la compartición de secretos suele hacerse en un cuerpo finito. El tamaño del fragmento es un punto (x, y): x puede ser pequeño y normalmente es algo como log n cuando hay n participantes, y y es un punto arbitrario dentro del cuerpo
    La compartición de secretos de Shamir es segura a nivel de teoría de la información, así que en un secreto k-out-of-n, si no reúnes k puntos, hasta un ataque de fuerza bruta deja a todos los secretos igual de plausibles. Por eso el tamaño en bits del cuerpo puede elegirse como se quiera, aunque obviamente debe ser mayor que el tamaño en bits del secreto. No puedes ocultar 100 bits en un cuerpo finito con solo 5 elementos
    Normalmente lo que hay que impedir es que el atacante haga fuerza bruta sobre el secreto en sí, porque aunque el esquema sea seguro a nivel de teoría de la información, el secreto normalmente no lo es. Por ejemplo, una semilla de wallet; por eso se añade aleatoriedad al secreto y se elige un cuerpo lo bastante grande para bloquear ese tipo de ataques
    Según el modelo de amenaza, un cuerpo de 80 bits o 128 bits suele ser suficientemente seguro, y el tamaño del fragmento termina siendo apenas un poco mayor que 80 o 128 bits. En cuanto a computación cuántica, como este esquema es seguro a nivel de teoría de la información, no puede existir un ataque
  • Según entiendo, HashiCorp todavía tiene la implementación para el proceso de seal/unseal de Vault. Claro, a menos que algo haya cambiado
  • El método de Shamir se basa en el teorema fundamental del álgebra. Para definir de forma única un polinomio de grado n, se necesitan n+1 puntos
    Así que, para crear una configuración n-of-k, construyes un polinomio p(x) de grado n-1 y tomas k puntos arbitrarios de ese polinomio. El i-ésimo fragmento es simplemente (xi, yi), así que la cantidad de bits la determina el cuerpo con el que se construye el polinomio
    El cuerpo tiene que ser lo bastante grande para contener todo el secreto y, como hay que guardar dos valores (x, y), el tamaño del fragmento es como mínimo el doble del tamaño del secreto. Aun así, hace falta una verificación de integridad para confirmar que el fragmento no se haya dañado
    Entiendo que la computación cuántica no cambia nada aquí. Con que falte un solo punto, el último punto puede hacer que el secreto sea cualquier cosa, y no hay manera de distinguirlo
  • El secreto completo no tiene por qué ser necesariamente un solo elemento del cuerpo subyacente. También puede ser una n-tupla de elementos más pequeños del cuerpo
    Si no esperas una cantidad absurda de fragmentos, GF(2^8) es una opción bastante natural, y así no hace falta lidiar con aritmética de enteros grandes

• La implementación de Ente está aquí: (https://2of3.ente.com/)

  • Es de lo que más me ha gustado de todo lo que he visto hasta ahora, y es muy amigable para el usuario. Aunque sí me gustaría que fuera un poco más configurable
    Idealmente, me gustaría poder crear configuraciones como 3 of 4: A B C D o 2 of 3: E F G y 1 of 1: H
    También estaría bien alguna forma de poner nombres a las tarjetas, para que quede claro exactamente qué se necesita al recuperar. Claro, la simplicidad del diseño actual también tiene su ventaja
  • También hay una implementación empaquetada en la mayoría de las distribuciones Linux: http://point-at-infinity.org/ssss
  • Hay varias versiones basadas en navegador, que pueden usarse en línea o descargarse para usarlas sin conexión
    https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

• Hace algunos años hice una pequeña herramienta que ejecuta la compartición de secretos de Shamir en el navegador. Si descargas la página, puede usarse completamente sin conexión
  https://simon-frey.com/s4/

  • Hace algunos años descargué esa página y la guardé en varias memorias USB, junto con una base de datos de KeePass y fragmentos de la contraseña
    Se las repartí a algunos familiares y les dije que, si yo moría, se las entregaran a mi esposa