Este algoritmo único que utiliza Python y el Esquema de Shamir protege tu contraseña maestra de los hackers y contra tu propio olvido.
Muchos de nosotros usamos administradores de contraseñas para almacenar de forma segura nuestras muchas contraseñas únicas.
Una parte crítica de un administrador de contraseñas es la contraseña maestra. Esta contraseña protege a todas las demás, y de esa manera, es un riesgo.
Cualquiera que la tenga puede fingir ser tú … ¡en cualquier lugar! Naturalmente, mantienes tu contraseña maestra difícil de adivinar, la guardas en la memoria y haces todas las otras cosas que se supone que debes hacer.
Pero, ¿y si pasa algo y la olvidas? Tal vez te tomaste unas vacaciones en una hermosa isla lejana sin tecnología durante un mes. Después de jugar diariamente en el agua y comer piñas, no puedes recordar tu contraseña.
¡¿Tal vez era “las piernas largas corren rápido”? ¿O fue algo así como “las cucharas afiladas te permiten comer rápido”? Definitivamente fue inteligente cuando la pensaste.
Por supuesto, nunca le dijiste a una sola alma tu contraseña. Por qué, esta es literalmente la primera regla de administración de contraseñas. ¿Qué podrías haber hecho diferente?
Debes conocer Shamir’s Secret Sharing, un algoritmo que permite a los usuarios dividir un secreto en partes. Estas partes solo se pueden usar en combinación con las otras piezas.
Echemos un vistazo al esquema de Shamir en acción a través de una historia de tiempos antiguos y tiempos modernos.
Esta historia asume cierto conocimiento del cifrado. Puedes repasarlo con esta introducción a la criptografía y la infraestructura de clave pública.
Una historia de secretos en la antigüedad
En un antiguo reino, sucedió que el rey tenía un secreto. Un terrible secreto:
def int_from_bytes(s):
acc = 0
for b in s:
acc = acc * 256
acc += b
return acc
secret = int_from_bytes(«terrible secret».encode(«utf-8»))
Tan terrible que el rey no podía confiarlo a ninguno de sus descendientes. Tenía cinco de ellos, pero sabía que habría peligros en el camino por delante.
El rey sabía que sus hijos necesitarían el secreto para proteger el reino después de su muerte. Empero no podía soportar la idea de que el secreto se conociera durante dos décadas, mientras todavía lo lloraban.
Entonces usó magia poderosa para dividir el secreto en cinco fragmentos. Sabía que era posible que uno o dos niños no respetaran sus deseos, pero no creía que tres de ellos pudieran:
from mod import Mod
from os import urandom
El rey estaba bien versado en las artes mágicas de campos finitos y aleatoriedad. Como un rey sabio, usó Python para dividir el secreto.
Lo primero que hizo fue elegir un primo grande, el 13º número primo de Mersenne (2**521 – 1). Este ordenó que se escribiera en letras de 10 pies de alto, forjadas en oro, sobre el palacio:
P = 2**521 - 1
Esto no era parte del secreto: eran datos públicos.
El rey sabía que, si P es primo, los módulos de números P forman un campo matemático: se pueden sumar, multiplicar, restar y dividir siempre que el divisor no sea cero.
Como rey ocupado, utilizó el paquete PyPI mod, que implementa la aritmética de módulo.
Se aseguró de que su terrible secreto fuera menor que P:
secret < P
TRUE
Y lo convirtió a su módulo mod P:
secret = mod.Mod(secret, P)
Para permitir que tres descendientes reconstruyan el secreto, el rey tuvo que generar dos partes más para mezclar:
polynomial = [secret]
for i in range(2):
polynomial.append(Mod(int_from_bytes(urandom(16)), P))
len(polynomial)
Evaluación
Luego, el rey necesitaba evaluar este polinomio en puntos aleatorios. Evaluar un polinomio es calcular polynomial[0] + polynomial[1]*x + polynomial[2]*x**2 …
Si bien existen módulos de terceros para evaluar polinomios, no funcionan con campos finitos. El rey necesitaba escribir el código de evaluación él mismo:
def evaluate(coefficients, x):
acc = 0
power = 1
for c in coefficients:
acc += c * power
power *= x
return acc
Luego, el rey evaluó el polinomio en cinco puntos diferentes, para dar una pieza a cada descendiente:
shards = {}
for i in range(5):
x = Mod(int_from_bytes(urandom(16)), P)
y = evaluate(polynomial, x)
shards[i] = (x, y)
Lamentablemente, como temía el rey, no todos sus descendientes eran honestos y verdaderos. Dos de ellos, poco después de su muerte, trataron de descubrir el terrible secreto de las partes que tenían. Intentaron como pudieron, no tuvieron éxito. Sin embargo, cuando los demás aprendieron esto, los exiliaron del reino para siempre:
del shards[2]
del shards[3]
Veinte años después, como había decretado el rey, el hermano mayor y los otros dos se unieron para descubrir el terrible secreto de su padre. Juntaron sus fragmentos:
retrieved = list(shards.values())
Durante 40 días y 40 noches, lucharon por encontrar el secreto del rey. No fue tarea fácil ante ellos. Como el rey, conocían a Python, pero ninguno era tan sabio como él.
Finalmente, la respuesta les llegó.
El código de recuperación se basa en un concepto llamado interpolación lagrange. Evalúa un polinomio 0 basado en sus valores n en otros lugares, donde n es el grado del polinomio.
La forma en que funciona es que se puede encontrar de forma explícita una fórmula para un polinomio que es 1 en t[0] y 0 en t[i] para i diferentes a 0. Dado que evaluar un polinomio es una función lineal, evalúa cada uno de estos polinomios. Además, interpola los resultados de las evaluaciones con los valores que tiene el polinomio:
from functools import reduce
from operator import mul
def retrieve_original(secrets):
x_s = [s[0] for s in secrets]
acc = Mod(0, P)
for i in range(len(secrets)):
others = list(x_s)
cur = others.pop(i)
factor = Mod(1, P)
for el in others:
factor *= el * (el - cur).inverse()
acc += factor * secrets[i][1]
return acc
Resultado
No es sorprendente que les haya tomado 40 días y 40 noches, ¡este código es bastante complicado! Pero lo ejecutaron sobre los fragmentos sobrevivientes, esperando con la respiración contenida:
retrieved_secret = retrieve_original(retrieved)
¿Los hijos obtuvieron el secreto correcto?
retrieved_secret == secret
TRUE
¡La belleza de la magia de las matemáticas es que siempre funciona de manera confiable! Los hijos, ahora mayores y capaces de comprender las elecciones de su padre, usaron el terrible secreto para defender el reino. El reino prosperó y creció.
Una historia moderna del intercambio secreto de Shamir
En los tiempos modernos, muchos de nosotros también estamos cargados con un terrible secreto: la contraseña maestra de nuestro administrador de contraseñas.
Pocas personas tienen una persona en la que puedan confiar completamente con sus secretos más profundos y oscuros. No obstante, muchos pueden encontrar un grupo de cinco donde es poco probable que tres rompan su confianza juntos.
Afortunadamente, en estos tiempos modernos, no necesitamos dividir nuestros secretos nosotros mismos, como lo hizo el rey. A través de la tecnología moderna de código abierto, podemos utilizar el software que existe.
Digamos que tienes cinco personas en las que confías, no del todo, sino bastante: tu mejor amigo, tu cónyuge, tu madre, un colega cercano y tu abogado.
Puedes instalar y ejecutar el programa ssss para dividir la clave:
$ echo 'long legs travel fast' | ssss-split -t 3 -n 5
Generating shares using a (3,5) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: Using a 168 bit security level.
1-797842b76d80771f04972feb31c66f3927e7183609
2-947925f2fbc23dc9bca950ef613da7a4e42dc1c296
3-14647bdfc4e6596e0dbb0aa6ab839b195c9d15906d
4-97c77a805cd3d3a30bff7841f3158ea841cd41a611
5-17da24ad63f7b704baed220839abb215f97d95f4f8
Ah, una fuerte, poderosa, contraseña maestra: long legs travel fast. Nunca se puede confiar a una sola alma, pero puedes enviar los cinco fragmentos a tus cinco guardianes.
- Envías 1 a tu mejor amigo, F.
- Envías 2 a tu cónyuge, S.
- Envías 3 a tu mamá, M.
- Envías 4 a tu colega, C.
- Envías 5 a tu abogado, L.
Ahora, digamos que te vas de vacaciones en familia. Durante un mes, te diviertes en las cálidas arenas de la playa. Mientras juegas, no tocas ningún dispositivo electrónico. Muy pronto, tu poderosa contraseña maestra se olvida.
Tu amada esposa y tu querida madre estaban contigo de vacaciones. Mantuvieron sus fragmentos seguros en su administrador de contraseñas, y han olvidado sus contraseñas.
Esto está bien.
Solución
Te pones en contacto con tu mejor amigo, F, que te da 1-797842b76d80771f04972feb31c66f3927e7183609. Tu colega, que cubrió todos tus turnos, se alegra de tenerte de vuelta y te da 4-97c77a805cd3d3a30bff7841f3158ea841cd41a611. Tu abogado te cobra $ 150 por hora, ingresa a tu administrador de contraseñas y desentierra 5-17da24ad63f7b704baed220839abb215f97d95f4f8.
Con esas tres piezas, ejecutas:
$ ssss-combine -t 3
Enter 3 shares separated by newlines:
Share [1/3]: 1-797842b76d80771f04972feb31c66f3927e7183609
Share [2/3]: 4-97c77a805cd3d3a30bff7841f3158ea841cd41a611
Share [3/3]: 5-17da24ad63f7b704baed220839abb215f97d95f4f8
Resulting secret: long legs travel fast
Y así, con la tecnología de código abierto, ¡tú también puedes vivir como un rey!
Comparte de forma segura por tu seguridad
La administración de contraseñas es una habilidad esencial para la vida en línea de hoy. Puedes crear una contraseña compleja, por supuesto, pero no te detengas allí.
Puedes usar el práctico algoritmo de secreto compartido de Shamir para compartirlo de manera segura con otros.