El intercambio de secretos (también llamado división de secretos ) se refiere a métodos para distribuir un secreto entre un grupo, de tal manera que ningún individuo tenga información inteligible sobre el secreto, pero cuando un número suficiente de individuos combina sus "participaciones", el secreto puede reconstruirse. Mientras que el intercambio de secretos inseguro permite a un atacante obtener más información con cada participación, el intercambio de secretos seguro es "todo o nada" (donde "todo" significa el número necesario de participaciones).
En un tipo de esquema de reparto de secretos hay un crupier y n jugadores . El crupier da una parte del secreto a los jugadores, pero solo cuando se cumplen condiciones específicas los jugadores podrán reconstruir el secreto a partir de sus partes. El crupier logra esto dando a cada jugador una parte de tal manera que cualquier grupo de t (para el umbral ) o más jugadores pueden reconstruir juntos el secreto pero ningún grupo de menos de t jugadores puede hacerlo. Un sistema de este tipo se llama esquema de umbral ( t , n ) (a veces se escribe como esquema de umbral ( n , t ) ).
El intercambio de secretos fue inventado independientemente por Adi Shamir [1] y George Blakley [2] en 1979.
Los esquemas de intercambio de secretos son ideales para almacenar información que es altamente sensible e importante. Algunos ejemplos incluyen: claves de cifrado , códigos de lanzamiento de misiles y cuentas bancarias numeradas . Cada una de estas piezas de información debe mantenerse altamente confidencial, ya que su exposición podría ser desastrosa; sin embargo, también es fundamental que no se pierdan. Los métodos tradicionales de cifrado no son adecuados para lograr simultáneamente altos niveles de confidencialidad y confiabilidad. Esto se debe a que al almacenar la clave de cifrado, uno debe elegir entre mantener una sola copia de la clave en una ubicación para el máximo secreto, o mantener múltiples copias de la clave en diferentes ubicaciones para una mayor confiabilidad. Aumentar la confiabilidad de la clave mediante el almacenamiento de múltiples copias reduce la confidencialidad al crear vectores de ataque adicionales; hay más oportunidades de que una copia caiga en las manos equivocadas. Los esquemas de intercambio de secretos abordan este problema y permiten lograr niveles arbitrariamente altos de confidencialidad y confiabilidad. [3]
El intercambio de secretos también permite que el distribuidor del secreto confíe en un grupo "en conjunto". Tradicionalmente, dar un secreto a un grupo para su custodia requería que el distribuidor confiara completamente en todos los miembros del grupo. Los esquemas de intercambio de secretos permiten al distribuidor almacenar de forma segura el secreto con el grupo incluso si no se puede confiar en todos los miembros todo el tiempo. Mientras el número de traidores nunca sea mayor que el número crítico necesario para reconstruir el secreto, el secreto está a salvo.
Los esquemas de compartición de secretos son importantes en los entornos de computación en la nube . Por lo tanto, una clave se puede distribuir entre muchos servidores mediante un mecanismo de compartición de secretos de umbral. Luego, la clave se reconstruye cuando es necesario.
También se ha sugerido [ ¿quién? ] compartir secretos para redes de sensores donde los enlaces son susceptibles de ser interceptados, enviando los datos en fragmentos que dificultan la tarea del espía. [ cita requerida ] La seguridad en tales entornos se puede hacer mayor cambiando continuamente [ ¿cómo? ] la forma en que se construyen los fragmentos. [ cita requerida ]
Un esquema seguro de intercambio de secretos distribuye las acciones de modo que cualquiera con menos de t acciones no tiene más información sobre el secreto que alguien con 0 acciones.
Consideremos, por ejemplo, el sistema de intercambio de secretos en el que la frase secreta "contraseña" se divide en las partes "pa––––––", "––ss––––", "––––wo––" y "––––––rd". Una persona con 0 partes sabe únicamente que la contraseña consta de ocho letras, y por lo tanto tendría que adivinarla entre 26 8 = 208 mil millones de combinaciones posibles. Sin embargo, una persona con una parte tendría que adivinar únicamente las seis letras, entre 26 6 = 308 millones de combinaciones, y así sucesivamente a medida que más personas se confabulan. En consecuencia, este sistema no es un sistema de intercambio de secretos "seguro", porque un jugador con menos de t partes de secreto puede reducir el problema de obtener el secreto interno sin necesidad de obtener primero todas las partes necesarias.
En contraste, considere el esquema de intercambio de secretos donde X es el secreto a compartir, P i son claves de cifrado asimétricas públicas y Q i sus claves privadas correspondientes. A cada jugador J se le proporciona { P 1 ( P 2 (...( P N ( X )))), Q j }. En este esquema, cualquier jugador con clave privada 1 puede eliminar la capa externa de cifrado, un jugador con claves 1 y 2 puede eliminar la primera y segunda capa, y así sucesivamente. Un jugador con menos de N claves nunca puede alcanzar completamente el secreto X sin necesitar primero descifrar un blob cifrado con clave pública para el cual no tiene la clave privada correspondiente, un problema que actualmente se cree que es computacionalmente inviable. Además, podemos ver que cualquier usuario con todas las N claves privadas puede descifrar todas las capas externas para obtener X , el secreto, y en consecuencia este sistema es un sistema seguro de distribución de secretos.
Se dice que varios esquemas de intercambio de secretos son seguros en términos de información y se puede demostrar que lo son, mientras que otros renuncian a esta seguridad incondicional para mejorar la eficiencia, manteniendo al mismo tiempo la seguridad suficiente para ser considerados tan seguros como otros primitivos criptográficos comunes. Por ejemplo, podrían permitir que los secretos se protejan mediante fragmentos con una entropía de 128 bits cada uno, ya que cada fragmento se consideraría suficiente para frustrar a cualquier adversario concebible en la actualidad, lo que requeriría un ataque de fuerza bruta de tamaño promedio de 2 127 .
En común con todos los esquemas de intercambio de secretos incondicionalmente seguros, existen limitaciones: [ cita requerida ]
Nota: n es el número total de 'jugadores' entre los que se distribuyen las acciones, y t es el número mínimo de jugadores necesario para revelar el secreto.
t = 1 compartir secretos es trivial. El secreto puede distribuirse simplemente entre todos los n participantes.
Existen varios esquemas de compartición de secretos ( t , n ) para t = n , cuando todas las acciones son necesarias para recuperar el secreto:
La dificultad [ aclaración necesaria ] radica en crear esquemas que sigan siendo seguros, pero que no requieran todas las n acciones.
Cuando la eficiencia del espacio no es una preocupación, se pueden usar esquemas triviales t = n para revelar un secreto a cualquier subconjunto deseado de jugadores simplemente aplicando el esquema para cada subconjunto. Por ejemplo, para revelar un secreto s a dos de los tres jugadores Alice, Bob y Carol, cree tres ( ) diferentes t = n = 2 partes del secreto para s , dando los tres conjuntos de dos partes a Alice y Bob, Alice y Carol, y Bob y Carol.
Por ejemplo, imaginemos que el consejo de administración de una empresa quisiera proteger su fórmula secreta. El presidente de la empresa debería poder acceder a la fórmula cuando fuera necesario, pero en caso de emergencia, cualquiera de los 3 miembros del consejo podrían desbloquear la fórmula secreta juntos. Una de las formas de lograrlo es mediante un esquema de intercambio de secretos con t = 3 y n = 15 , donde se dan 3 acciones al presidente y una acción a cada miembro del consejo.
El enfoque trivial se vuelve rápidamente impráctico a medida que aumenta el número de subconjuntos, por ejemplo, cuando se revela un secreto a 50 de 100 jugadores, lo que requeriría la creación de esquemas y que cada jugador mantenga conjuntos distintos de acciones para cada esquema. En el peor de los casos, el aumento es exponencial. Esto ha llevado a la búsqueda de esquemas que permitan compartir secretos de manera eficiente con un umbral de jugadores.
En este esquema, se pueden utilizar t de n acciones para recuperar el secreto. El sistema se basa en la idea de que se puede ajustar un polinomio único de grado t − 1 a cualquier conjunto de t puntos que se encuentren en el polinomio. Se necesitan dos puntos para definir una línea recta, tres puntos para definir completamente una cuadrática, cuatro puntos para definir una curva cúbica, y así sucesivamente. Es decir, se necesitan t puntos para definir un polinomio de grado t − 1. El método consiste en crear un polinomio de grado t − 1 con el secreto como primer coeficiente y los coeficientes restantes elegidos al azar. A continuación, se encuentran n puntos en la curva y se les da uno a cada uno de los jugadores. Cuando al menos t de los n jugadores revelan sus puntos, hay suficiente información para ajustarles un polinomio de grado ( t − 1) ésimo, siendo el primer coeficiente el secreto.
Dos líneas no paralelas en el mismo plano se intersecan exactamente en un punto. Tres planos no paralelos en el espacio se intersecan exactamente en un punto. De manera más general, cualesquiera n hiperplanos no paralelos de ( n − 1) dimensiones se intersecan en un punto específico. El secreto puede codificarse como cualquier coordenada única del punto de intersección. Si el secreto se codifica utilizando todas las coordenadas, incluso si son aleatorias, entonces un insider (alguien en posesión de uno o más de los ( n − 1) hiperplanos dimensionales ) obtiene información sobre el secreto ya que sabe que debe estar en su plano. Si un insider puede obtener más conocimiento sobre el secreto que un outsider, entonces el sistema ya no tiene seguridad teórica de la información . Si solo se utiliza una de las n coordenadas, entonces el insider no sabe más que un outsider (es decir, que el secreto debe estar en el eje x para un sistema bidimensional). Cada jugador recibe suficiente información para definir un hiperplano; El secreto se recupera calculando el punto de intersección de los planos y luego tomando una coordenada específica de esa intersección.
El esquema de Blakley es menos eficiente en cuanto a espacio que el de Shamir; mientras que las porciones de Shamir son tan grandes como el secreto original, las porciones de Blakley son t veces más grandes, donde t es el número límite de jugadores. El esquema de Blakley se puede ajustar añadiendo restricciones sobre qué aviones se pueden usar como porciones. El esquema resultante es equivalente al sistema polinomial de Shamir.
El teorema del resto chino también se puede utilizar en la compartición de secretos, ya que nos proporciona un método para determinar de forma única un número S módulo k muchos enteros coprimos por pares , dado que . Hay dos esquemas de compartición de secretos que hacen uso del teorema del resto chino, los esquemas de Mignotte y Asmuth-Bloom. Son esquemas de compartición de secretos de umbral, en los que las participaciones se generan por reducción módulo los enteros , y el secreto se recupera esencialmente resolviendo el sistema de congruencias utilizando el teorema del resto chino.
Si los jugadores almacenan sus acciones en servidores informáticos inseguros, un atacante podría entrar y robar las acciones. Si no es práctico cambiar el secreto, las acciones no comprometidas (al estilo Shamir) pueden renovarse. El crupier genera un nuevo polinomio aleatorio con término constante cero y calcula para cada jugador restante un nuevo par ordenado, donde las coordenadas x del par antiguo y el nuevo son las mismas. Luego, cada jugador suma las coordenadas y antiguas y nuevas entre sí y mantiene el resultado como la nueva coordenada y del secreto.
Todas las acciones no actualizadas que acumuló el atacante se vuelven inútiles. Un atacante solo puede recuperar el secreto si puede encontrar suficientes acciones no actualizadas para alcanzar el umbral. Esta situación no debería ocurrir porque los jugadores eliminaron sus acciones antiguas. Además, un atacante no puede recuperar ninguna información sobre el secreto original de los archivos de actualización porque solo contienen información aleatoria.
El distribuidor puede cambiar el número de umbral mientras distribuye actualizaciones, pero siempre debe permanecer atento a los jugadores que mantienen acciones vencidas.
Un jugador puede mentir sobre su propia parte para obtener acceso a las de otros jugadores. Un sistema de intercambio de secretos verificables (VSS, por sus siglas en inglés) permite a los jugadores estar seguros de que ningún otro jugador miente sobre el contenido de sus partes, hasta una probabilidad de error razonable. Estos sistemas no se pueden calcular de manera convencional; los jugadores deben sumar y multiplicar números colectivamente sin que ningún individuo sepa exactamente qué se está sumando y multiplicando. Tal Rabin y Michael Ben-Or idearon un sistema de computación multipartidaria (MPC, por sus siglas en inglés) que permite a los jugadores detectar la deshonestidad por parte del crupier o de hasta un tercio del número límite de jugadores, incluso si esos jugadores están coordinados por un atacante "adaptativo" que puede cambiar de estrategia en tiempo real dependiendo de la información que se haya revelado.
La desventaja de los esquemas de intercambio de secretos con seguridad incondicional es que el almacenamiento y la transmisión de las acciones requieren una cantidad de recursos de almacenamiento y ancho de banda equivalente al tamaño del secreto multiplicado por el número de acciones. Si el tamaño del secreto fuera significativo, digamos 1 GB, y el número de acciones fuera 10, entonces los accionistas deberían almacenar 10 GB de datos. Se han propuesto técnicas alternativas para aumentar en gran medida la eficiencia de los esquemas de intercambio de secretos, renunciando al requisito de seguridad incondicional.
Una de estas técnicas, conocida como el método de compartir secretos en forma abreviada [4], combina el algoritmo de dispersión de información de Rabin [5] (IDA) con el método de compartir secretos de Shamir. Primero, los datos se cifran con una clave generada aleatoriamente, utilizando un algoritmo de cifrado simétrico. A continuación, estos datos se dividen en N fragmentos utilizando el IDA de Rabin. Este IDA se configura con un umbral, de manera similar a los esquemas de compartir secretos, pero a diferencia de estos últimos, el tamaño de los datos resultantes crece en un factor de (número de fragmentos/umbral). Por ejemplo, si el umbral fuera 10 y el número de fragmentos producidos por el IDA fuera 15, el tamaño total de todos los fragmentos sería (15/10) o 1,5 veces el tamaño de la entrada original. En este caso, este esquema es 10 veces más eficiente que si el esquema de Shamir se hubiera aplicado directamente a los datos. El paso final para compartir secretos en pocas palabras es utilizar el método de compartir secretos Shamir para producir partes de la clave simétrica generada aleatoriamente (que normalmente es del orden de 16 a 32 bytes) y luego entregar una parte y un fragmento a cada accionista.
Un enfoque relacionado, conocido como AONT-RS, [6] aplica una transformación de todo o nada a los datos como paso de preprocesamiento de una IDA. La transformación de todo o nada garantiza que cualquier número de acciones menor que el umbral sea insuficiente para descifrar los datos.
Un esquema de intercambio de secretos k de n seguro desde el punto de vista de la información genera n porciones, cada una de un tamaño al menos igual al del secreto en sí, lo que lleva a que el almacenamiento total requerido sea al menos n veces mayor que el secreto. En el intercambio de múltiples secretos diseñado por Matthew K. Franklin y Moti Yung , [7] múltiples puntos de los secretos del host polinomial; el método se encontró útil en numerosas aplicaciones, desde codificación hasta cálculos multipartidistas . En el intercambio de secretos eficiente en el espacio, ideado por Abhishek Parakh y Subhash Kak , cada porción es aproximadamente el tamaño del secreto dividido por k − 1. [ 8]
Este esquema hace uso de la interpolación polinómica repetida y tiene aplicaciones potenciales en la dispersión segura de información en la Web y en redes de sensores . Este método se basa en la partición de datos que involucra las raíces de un polinomio en un campo finito. [9] Algunas vulnerabilidades de los esquemas de intercambio de secretos eficientes en el espacio relacionados se señalaron más adelante. [10] Muestran que un esquema basado en el método de interpolación no se puede utilizar para implementar un esquema ( k , n ) cuando los k secretos a distribuir se generan inherentemente a partir de un polinomio de grado menor que k − 1 , y el esquema no funciona si todos los secretos a compartir son los mismos, etc. [11]
Un esquema de intercambio de secretos puede proteger un secreto en varios servidores y seguir siendo recuperable a pesar de múltiples fallas de servidores. El distribuidor puede actuar como varios participantes distintos, distribuyendo las partes entre los participantes. Cada parte puede almacenarse en un servidor diferente, pero el distribuidor puede recuperar el secreto incluso si varios servidores fallan, siempre que pueda recuperar al menos t partes; sin embargo, los piratas informáticos que ingresen a un servidor seguirán sin conocer el secreto mientras haya menos de t partes almacenadas en cada servidor.
Este es uno de los conceptos principales detrás del proyecto informático Vanish de la Universidad de Washington , donde se utiliza una clave aleatoria para cifrar datos, y la clave se distribuye como un secreto a través de varios nodos en una red P2P . Para descifrar el mensaje, al menos t nodos en la red deben ser accesibles; el principio de este proyecto en particular es que la cantidad de nodos que comparten secretos en la red disminuirá naturalmente con el tiempo, por lo que el secreto eventualmente desaparecerá . Sin embargo, la red es vulnerable a un ataque Sybil , lo que hace que Vanish sea inseguro. [12]
Cualquier accionista que tenga información suficiente para descifrar el contenido en cualquier momento puede tomar y almacenar una copia de X. En consecuencia, aunque herramientas y técnicas como Vanish pueden hacer que los datos sean irrecuperables dentro de su propio sistema después de un tiempo, no es posible forzar la eliminación de los datos una vez que un usuario malintencionado los ha visto. Este es uno de los principales enigmas de la gestión de derechos digitales .
Un distribuidor podría enviar t shares, todos ellos necesarios para recuperar el secreto original, a un único destinatario. Un atacante tendría que interceptar todos los t shares para recuperar el secreto, una tarea que es más difícil que interceptar un único archivo, especialmente si los shares se envían utilizando diferentes medios (por ejemplo, algunos por Internet , otros por correo en CD ).
En el caso de secretos de gran tamaño, puede resultar más eficiente cifrar el secreto y luego distribuir la clave mediante el uso compartido de secretos.
El intercambio de secretos es una primitiva importante en varios protocolos para la computación segura entre múltiples partes . El intercambio de secretos también se puede utilizar para la autenticación de usuarios en un sistema. [13]
