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 combinan sus "acciones", el secreto puede ser reconstruido. Mientras que el intercambio inseguro de secretos permite a un atacante obtener más información con cada recurso compartido, el intercambio seguro de secretos es "todo o nada" (donde "todos" significa la cantidad necesaria de recursos compartidos).
En un tipo de esquema de intercambio secreto hay un crupier y n jugadores . El crupier entrega una parte del secreto a los jugadores, pero sólo cuando se cumplan condiciones específicas los jugadores podrán reconstruir el secreto a partir de sus partes. El crupier logra esto dándole a cada jugador una parte de tal manera que cualquier grupo de t (para el umbral ) o más jugadores puedan juntos reconstruir el secreto, pero ningún grupo de menos de t jugadores puede hacerlo. Un sistema de este tipo se denomina esquema de umbral ( t , n ) (a veces se escribe como esquema de umbral ( n , t ) ).
El intercambio secreto fue inventado de forma independiente por Adi Shamir [1] y George Blakley [2] en 1979.
Los esquemas de intercambio secreto son ideales para almacenar información que es muy sensible y muy importante. Los 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, se debe elegir entre mantener una única copia de la clave en una ubicación para lograr el máximo secreto o mantener varias 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 posibilidades de que una copia caiga en manos equivocadas. Los esquemas de intercambio de secretos abordan este problema y permiten alcanzar niveles arbitrariamente altos de confidencialidad y confiabilidad. [3]
Compartir secretos también permite al distribuidor del secreto confiar 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 para compartir 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 supere el número crítico necesario para reconstruir el secreto, el secreto está a salvo.
Los esquemas de intercambio secreto 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 intercambio de secretos de umbral. Luego, la clave se reconstruye cuando es necesario.
También se ha sugerido compartir secretos [ ¿quién? ] para redes de sensores donde los enlaces pueden ser intervenidos, enviando los datos en acciones, lo que dificulta la tarea del espía. [ cita necesaria ] La seguridad en tales entornos se puede mejorar mediante cambios continuos [ ¿cómo? ] de la forma en que se construyen las acciones. [ cita necesaria ]
Un esquema seguro para compartir secretos distribuye acciones de modo que cualquier persona con menos de t acciones no tenga más información sobre el secreto que alguien con 0 acciones.
Considere, por ejemplo, el esquema de intercambio secreto en el que la frase secreta "contraseña" se divide en los elementos compartidos "pa––––––", "––ss––––", "––––wo––", y "––––––rd". Una persona con 0 acciones sólo sabe que la contraseña consta de ocho letras y, por tanto, tendría que adivinar la contraseña entre 26 8 = 208 mil millones de combinaciones posibles. Sin embargo, una persona con una acción tendría que adivinar sólo las seis letras, de 26 6 = 308 millones de combinaciones, y así sucesivamente a medida que más personas se confabulan. En consecuencia, este sistema no es un esquema de intercambio de secretos "seguro", porque un jugador con menos de t acciones secretas puede reducir el problema de obtener el secreto interno sin necesidad de obtener primero todas las acciones necesarias.
Por el contrario, considere el esquema de intercambio de secretos donde X es el secreto a compartir, Pi son claves públicas de cifrado asimétricas y Q i sus correspondientes claves privadas. Cada jugador J cuenta con { P 1 ( P 2 (...( P N ( X )))), Q j }. En este esquema, cualquier jugador con la clave privada 1 puede eliminar la capa exterior de cifrado, un jugador con las claves 1 y 2 puede eliminar la primera y la segunda capa, y así sucesivamente. Un jugador con menos de N claves nunca podrá alcanzar completamente la X secreta sin necesidad de descifrar primero 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 de distribución de secretos seguro.
Se dice que varios esquemas de intercambio de secretos son teóricamente seguros y se puede demostrar que lo son, mientras que otros renuncian a esta seguridad incondicional para mejorar la eficiencia y, al mismo tiempo, mantienen suficiente seguridad para ser considerados tan seguros como otras primitivas criptográficas comunes. Por ejemplo, podrían permitir que los secretos se protejan mediante acciones con una entropía de 128 bits cada una, ya que cada acción se consideraría suficiente para bloquear a cualquier adversario concebible en la actualidad, lo que requeriría un ataque de fuerza bruta de tamaño promedio 2 127 .
Comunes a todos los esquemas de intercambio de secretos incondicionalmente seguros, existen limitaciones: [ cita necesaria ]
t = 1 compartir secretos es trivial. El secreto se puede distribuir simplemente a los n participantes.
Hay varios ( t , n ) esquemas para compartir secretos para t = n , cuando todas las acciones son necesarias para recuperar el secreto:
La dificultad [ se necesita aclaración ] radica en crear esquemas que aún sean seguros, pero que no requieran 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 secretos compartidos para s , dando los tres conjuntos de dos compartidos a Alice y Bob, Alice y Carol, 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 sea necesario, pero en caso de emergencia, 3 de los 12 miembros de la junta podrían desbloquear la fórmula secreta juntos. Una de las formas en que esto se puede lograr es mediante un esquema de intercambio de secretos con t = 3 y n = 15 , donde se entregan 3 acciones al presidente y una acción a cada miembro de la junta directiva.
El enfoque trivial rápidamente se vuelve poco prá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 que se crearan esquemas y que cada jugador mantuviera distintos conjuntos 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 puede utilizar cualquier 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, etc. 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. Luego encuentra n puntos en la curva y dale 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 ( t − 1) grado, siendo el primer coeficiente el secreto.
Dos rectas no paralelas en el mismo plano se cortan exactamente en un punto. Tres planos no paralelos en el espacio se cruzan exactamente en un punto. De manera más general, cualquier n hiperplanos dimensionales no paralelos ( n − 1 ) se cruzan en un punto específico. El secreto puede codificarse como cualquier coordenada única del punto de intersección. Si el secreto se codifica usando todas las coordenadas, incluso si son aleatorias, entonces un insider (alguien en posesión de uno o más de los hiperplanos ( n − 1) -dimensionales ) obtiene información sobre el secreto ya que sabe que debe estar en su avión. Si un interno puede obtener más conocimiento sobre el secreto que un externo, entonces el sistema ya no tiene seguridad teórica de la información . Si sólo se utiliza una de las n coordenadas, entonces el interno no sabe más que un externo (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 Blakeley ocupa menos espacio que el de Shamir; mientras que las acciones de Shamir son tan grandes como el secreto original, las acciones de Blakley son t veces mayores, donde t es el número umbral de jugadores. El plan de Blakley puede endurecerse añadiendo restricciones sobre qué aviones pueden utilizarse como acciones. El esquema resultante es equivalente al sistema polinomial de Shamir.
El teorema del resto chino también se puede utilizar en el intercambio secreto, 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 secretos de reparto que utilizan el teorema del resto chino: los esquemas de Mignotte y Asmuth-Bloom. Son esquemas de intercambio de secretos de umbral, en los que las acciones se generan mediante reducción en módulo de los números 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 resulta 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 de los pares antiguo y nuevo son las mismas. Luego, cada jugador suma las coordenadas y nuevas y antiguas 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 sólo puede recuperar el secreto si puede encontrar suficientes recursos compartidos no actualizados para alcanzar el umbral. Esta situación no debería ocurrir porque los jugadores eliminaron sus antiguas acciones. 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 crupier 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 otras acciones. Un esquema de intercambio secreto verificable (VSS) permite a los jugadores estar seguros de que ningún otro jugador miente sobre el contenido de sus acciones, hasta una probabilidad razonable de error. Estos esquemas no pueden calcularse 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 multipartita (MPC) que permite a los jugadores detectar la deshonestidad por parte del crupier o por parte de hasta un tercio del número umbral 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 incondicionalmente seguros es que el almacenamiento y la transmisión de los recursos compartidos requieren una cantidad de recursos de almacenamiento y ancho de banda equivalente al tamaño del secreto multiplicado por el número de recursos compartidos. Si el tamaño del secreto fuera significativo, digamos 1 GB, y el número de acciones fuera 10, entonces los accionistas deben 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 intercambio de secretos abreviado , [4] combina el algoritmo de dispersión de información de Rabin [5] (IDA) con el intercambio de secretos de Shamir. Los datos primero se cifran con una clave generada aleatoriamente, utilizando un algoritmo de cifrado simétrico. A continuación, estos datos se dividen en N partes utilizando el IDA de Rabin. Este IDA está configurado con un umbral, de manera similar a los esquemas de intercambio de secretos, pero a diferencia de los esquemas de intercambio de secretos, 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 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 sobre los datos. El último paso en el intercambio de secretos simplificado es utilizar el intercambio de secretos de Shamir para producir acciones de la clave simétrica generada aleatoriamente (que generalmente es del orden de 16 a 32 bytes) y luego entregar una acción y un fragmento a cada accionista.
Un enfoque relacionado, conocido como AONT-RS, [6] aplica una transformación todo o nada a los datos como paso previo al procesamiento de un IDA. La transformación Todo o nada garantiza que cualquier número de recursos compartidos inferiores al umbral sea insuficiente para descifrar los datos.
Un esquema de intercambio de secretos k de n , teóricamente seguro, genera n recursos compartidos, cada uno de un tamaño al menos igual al del secreto mismo, lo que lleva a que el almacenamiento total requerido sea al menos n veces mayor que el secreto. En el intercambio de secretos múltiples diseñado por Matthew K. Franklin y Moti Yung , [7] múltiples puntos de los secretos del host polinómico; El método resultó útil en numerosas aplicaciones, desde codificación hasta cálculos multipartitos. En el intercambio de secretos eficiente en el espacio, ideado por Abhishek Parakh y Subhash Kak , cada parte tiene aproximadamente el tamaño del secreto dividido por k − 1 . [8]
Este esquema hace uso de interpolación polinomial 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] Más adelante se señalaron algunas vulnerabilidades de los esquemas relacionados de intercambio de secretos eficientes en el espacio . [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 iguales, etc. [11]
Un esquema de intercambio de secretos puede proteger un secreto en varios servidores y seguir siendo recuperable a pesar de las fallas de varios servidores. El negociante podrá actuar como varios partícipes distintos, distribuyendo las acciones entre los partícipes. Cada acción puede almacenarse en un servidor diferente, pero el distribuidor puede recuperar el secreto incluso si varios servidores fallan, siempre que puedan recuperar al menos t acciones; sin embargo, los crackers que ingresan a un servidor aún no conocerán el secreto siempre que se almacenen menos de t recursos compartidos 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 entre varios nodos de una red P2P . Para descifrar el mensaje, al menos t nodos de la red deben ser accesibles; El principio de este proyecto en particular es que el número de nodos que comparten secretos en la red disminuirá naturalmente con el tiempo, lo que provocará que el secreto finalmente desaparezca . Sin embargo, la red es vulnerable a un ataque Sybil , lo que hace que Vanish sea inseguro. [12]
Cualquier accionista que tenga suficiente información 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. para forzar la eliminación de datos una vez que un usuario malintencionado los haya visto. Este es uno de los principales enigmas de la gestión de derechos digitales .
Un comerciante podría enviar t acciones, todas las cuales son necesarias para recuperar el secreto original, a un solo destinatario. Un atacante tendría que interceptar todos los archivos compartidos para recuperar el secreto, una tarea que es más difícil que interceptar un solo archivo, especialmente si los archivos compartidos se envían utilizando diferentes medios (por ejemplo, algunos a través de Internet , otros enviados por correo en CD ).
Para secretos grandes, puede ser más eficaz 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 multipartita segura . El uso compartido de secretos también se puede utilizar para la autenticación de usuarios en un sistema. [13]
{{cite journal}}: Citar diario requiere |journal=( ayuda )