El intercambio de secretos (también llamado división de secretos ) se refiere a métodos para distribuir un secreto entre un grupo de participantes, a cada uno de los cuales se le asigna una parte del secreto. El secreto sólo puede reconstruirse cuando se combina un número suficiente, posiblemente de diferentes tipos, de acciones; las acciones individuales no sirven de nada por sí mismas.
En un tipo de esquema de compartición de secretos no es uno de concesionarios y n jugadores . El crupier les da una parte del secreto a los jugadores, pero solo cuando se cumplan las condiciones específicas, los jugadores podrán reconstruir el secreto a partir de sus acciones. 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 puedan reconstruir juntos el secreto, pero ningún grupo de menos de t jugadores puede. Tal sistema 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.
Importancia
Los esquemas de intercambio secreto son ideales para almacenar información que es muy sensible e 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 encriptación 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 al almacenar múltiples copias reduce la confidencialidad al crear vectores de ataque adicionales; hay más oportunidades para que una copia caiga en las manos equivocadas. Los esquemas de intercambio secreto abordan este problema y permiten alcanzar niveles arbitrariamente altos de confidencialidad y confiabilidad.
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 compartición secreta de umbral. Luego, la clave se reconstruye cuando es necesario. También se ha sugerido el uso compartido secreto para redes de sensores donde los enlaces pueden ser interceptados enviando los datos en acciones, lo que dificulta la tarea del fisgón. La seguridad en tales entornos puede aumentar mediante el cambio continuo de la forma en que se construyen las acciones.
Compartir secretos "seguros" versus "inseguros"
Un esquema de intercambio seguro de 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 recursos compartidos "pa ––––––", "––ss ––––", "–––– wo––", y "–––––– rd". Una persona con 0 acciones solo sabe que la contraseña consta de ocho letras y, por lo tanto, tendría que adivinar la contraseña de 26 8 = 208 mil millones de combinaciones posibles. Una persona con una acción, sin embargo, tendría que adivinar solo las seis letras, de 26 6 = 308 millones de combinaciones, y así sucesivamente a medida que más personas coluden. 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, considerar el esquema de compartición de secretos, donde X es el secreto para ser compartida, P i son públicas de cifrado asimétricos llaves 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 externa 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 puede alcanzar completamente la X secreta sin primero tener que descifrar un blob cifrado con clave pública para el que 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.
Limitaciones
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 mientras mantienen la seguridad suficiente para ser considerados tan seguros como otras primitivas criptográficas comunes. Por ejemplo, podrían permitir que los secretos estén protegidos por recursos compartidos con 128 bits de entropía cada uno, ya que cada recurso compartido se consideraría suficiente para bloquear a cualquier adversario actual imaginable, requiriendo un ataque de fuerza bruta de tamaño promedio de 2127 .
En común a todos los esquemas de intercambio de secretos incondicionalmente seguros, existen limitaciones:
- Cada parte del secreto debe ser al menos tan grande como el propio secreto. Este resultado se basa en la teoría de la información , pero puede entenderse intuitivamente. Dadas las acciones t - 1 , no se puede determinar ningún tipo de información sobre el secreto. Por lo tanto, la acción final debe contener tanta información como el secreto en sí. A veces hay una solución para esta limitación comprimiendo primero el secreto antes de compartirlo, pero esto a menudo no es posible porque muchos secretos (claves, por ejemplo) parecen datos aleatorios de alta calidad y, por lo tanto, son difíciles de comprimir.
- Todos los esquemas de intercambio secreto utilizan bits aleatorios . Para distribuir un secreto de un bit entre el umbral t personas, son necesarios t - 1 bits aleatorios. Para distribuir un secreto de longitud arbitraria b bits, es necesaria una entropía de ( t - 1) × b bits.
Compartir secretos triviales
t = 1
t = 1 compartir secretos es trivial. El secreto simplemente se puede distribuir a todos los n participantes.
t = n
Hay varios ( t , n ) esquemas de intercambio de secretos para t = n , cuando todos los recursos compartidos son necesarios para recuperar el secreto:
- Codifique el secreto como un número binario s de longitud arbitraria . Dé a cada jugador i (excepto uno) un número aleatorio p i con la misma longitud que s . Dale al último jugador el resultado de ( s XOR p 1 XOR p 2 XOR ... XOR p n −1 ) donde XOR es exclusivo a nivel de bits o . El secreto es el XOR bit a bit de todos los números de los jugadores ( p ).
- Además, (1) se puede realizar utilizando cualquier operador lineal en cualquier campo . Por ejemplo, aquí hay una alternativa que es funcionalmente equivalente a (1). Seleccionemos enteros de 32 bits con semántica de desbordamiento bien definida (es decir, se conserva la respuesta correcta, módulo 2 32 ). Primero, s se puede dividir en un vector de M enteros de 32 bits llamado v secreto . Entonces ( n - 1) jugadores reciben cada uno un vector de M números enteros aleatorios, y el jugador i recibe v i . El jugador restante recibe v n = ( v secreto - v 1 - v 2 - ... - v n −1 ). El vector secreto se puede recuperar sumando todos los vectores del jugador.
1 < t < n , y, de manera más general, cualquier subconjunto deseado de {1,2, ..., n}
La dificultad radica en crear esquemas que aún sean seguros, pero que no requieran todos los n recursos compartidos. Por ejemplo, imagine que a la Junta Directiva de una empresa le gustaría proteger su fórmula secreta. El presidente de la compañía debería poder acceder a la fórmula cuando sea necesario, pero en caso de emergencia, cualquiera de los 12 miembros de la junta podría desbloquear la fórmula secreta juntos. Esto se puede lograr mediante un esquema de intercambio secreto con t = 3 yn = 15, donde se entregan 3 acciones al presidente y 1 a cada miembro de la junta.
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 de dos de los tres jugadores Alice, Bob y Carol, crear tres () diferente acciones secretas para s , dando los tres conjuntos de dos acciones a Alice y Bob, Alice y Carol, y Bob y Carol.
Compartir secretos de forma eficiente
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 esquemas que se crearán y que cada jugador mantendrá 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.
El esquema de Shamir
En este esquema, cualquier t de n acciones se puede utilizar 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 seleccionados al azar. A continuación, busque n puntos en la curva y dé 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) ésimo grado, siendo el primer coeficiente el secreto.
El esquema de Blakley
Dos rectas no paralelas en el mismo plano se cruzan 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 no paralelos ( n - 1) dimensionales se cruza en un punto específico. El secreto puede codificarse como cualquier coordenada única del punto de intersección. Si el secreto está codificado usando todas las coordenadas, incluso si son aleatorias, entonces un informante (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 avión. Si una persona con información privilegiada puede obtener más conocimiento sobre el secreto que una persona de afuera, entonces el sistema ya no tiene seguridad teórica de la información . Si solo se usa 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). A cada jugador se le da 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 en tres dimensiones: cada acción es un plano , y el secreto es el punto en el que se cruzan tres acciones. Dos acciones son insuficientes para determinar el secreto, aunque proporcionan suficiente información para reducirlo a la línea donde ambos planos se cruzan. |
El esquema de Blakley es menos eficiente en el espacio que el de Shamir; mientras que las acciones de Shamir son cada una tan grandes como el secreto original, las acciones de Blakley son t veces más grandes, donde t es el número umbral de jugadores. El esquema de Blakley se puede ajustar agregando restricciones sobre qué aviones se pueden usar como acciones. El esquema resultante es equivalente al sistema polinomial de Shamir.
Usando el teorema del resto chino
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 de intercambio secreto que hacen uso del teorema del resto chino , los esquemas de Mignotte y Asmuth-Bloom. Son esquemas de intercambio secreto de umbral, en los que las acciones se generan mediante el módulo de reducción de los enteros, y el secreto se recupera esencialmente resolviendo el sistema de congruencias usando el teorema chino del resto .
Intercambio de secretos proactivo
Si los jugadores almacenan sus recursos compartidos en servidores informáticos inseguros, un atacante podría entrar y robar los recursos compartidos. Si no es práctico cambiar el secreto, se pueden renovar las acciones no comprometidas (estilo Shamir). 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 iguales. Luego, cada jugador agrega las coordenadas y antiguas y nuevas entre sí y mantiene el resultado como la nueva coordenada y del secreto.
Todos los recursos compartidos no actualizados que acumuló el atacante se vuelven inútiles. Un atacante solo puede recuperar el secreto si puede encontrar suficientes recursos compartidos no actualizados para alcanzar el umbral. Esta situación no debería suceder porque los jugadores eliminaron sus acciones anteriores. 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 estar atento a los jugadores que mantienen acciones vencidas.
Compartición secreta verificable
Un jugador puede mentir sobre su propia participación 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. Tales esquemas no se pueden calcular de manera convencional; los jugadores deben sumar y multiplicar números colectivamente sin que ningún individuo sepa qué se está sumando y multiplicando exactamente. Tal Rabin y Michael Ben-Or idearon un sistema de computación multipartita (MPC) que permite a los jugadores detectar 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.
Uso compartido de secretos computacionalmente seguro
La desventaja de los esquemas de intercambio de secretos incondicionalmente seguros es que el almacenamiento y la transmisión de los recursos compartidos requiere 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, 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 secreto, renunciando al requisito de seguridad incondicional.
Una de estas técnicas, conocida como intercambio secreto abreviado , [3] combina el algoritmo de dispersión de información de Rabin [4] (IDA) con el intercambio secreto de Shamir. Los datos se cifran primero 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 secreto, pero a diferencia de los esquemas de intercambio secreto, el tamaño de los datos resultantes aumenta 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 a los datos. El paso final en el intercambio secreto abreviado es utilizar el intercambio secreto de Shamir para producir acciones de la clave simétrica generada aleatoriamente (que suele ser del orden de 16 a 32 bytes) y luego dar una acción y un fragmento a cada accionista.
Un enfoque relacionado, conocido como AONT-RS, [5] aplica una transformación de todo o nada a los datos como un paso previo al procesamiento de un IDA. La transformación de todo o nada garantiza que cualquier número de acciones por debajo del umbral es insuficiente para descifrar los datos.
Uso compartido de secretos (por lotes) de múltiples secretos y de uso eficiente del espacio
Un esquema de intercambio de secretos k de n información teóricamente seguro genera n acciones, cada una 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 múltiples secretos diseñado por Matthew K. Franklin y Moti Yung , [6] múltiples puntos de los secretos del host polinomial; El método resultó útil en numerosas aplicaciones, desde la codificación hasta los cálculos de múltiples partes. En el uso compartido de secretos con eficiencia espacial, ideado por Abhishek Parakh y Subhash Kak , cada parte es aproximadamente la fracción (k-1) del tamaño del secreto. [7]
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. [8] Más adelante se señalaron algunas vulnerabilidades de los esquemas relacionados con el uso compartido de secretos eficientes en el espacio . [9] Muestran que un esquema basado en el método de interpolación no puede usarse para implementar un esquema ( k , n ) cuando los k secretos que se distribuirán se generan inherentemente a partir de un polinomio de grado menor que k - 1 , y el esquema no funciona si todos los secretos que se van a compartir son los mismos, etc. [10]
Otros usos y aplicaciones
Un esquema de intercambio de secretos puede proteger un secreto en varios servidores y seguir siendo recuperable a pesar de los fallos de varios servidores. El distribuidor puede actuar como varios participantes distintos, distribuyendo las acciones entre los participantes. Cada recurso compartido puede almacenarse en un servidor diferente, pero el distribuidor puede recuperar el secreto incluso si varios servidores se averían, siempre que puedan recuperar al menos t recursos compartidos; sin embargo, los crackers que ingresen a un servidor 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 en la Universidad de Washington , donde se usa 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 de la red deben ser accesibles; el principio de este proyecto en particular es que la cantidad de nodos de intercambio de secretos en la red disminuirá de forma natural con el tiempo, lo que provocará que el secreto finalmente desaparezca . Sin embargo, la red es vulnerable a un ataque de Sybil , lo que hace que Vanish se sienta inseguro. [11]
Cualquier accionista que alguna vez 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 ha visto. Este es uno de los principales enigmas de la gestión de derechos digitales .
Un distribuidor 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 recursos compartidos para recuperar el secreto, una tarea que es más difícil que interceptar un solo archivo, especialmente si los recursos compartidos se envían utilizando diferentes medios (por ejemplo, algunos a través de Internet , otros en CD ).
Para secretos grandes, puede ser más eficiente cifrar el secreto y luego distribuir la clave mediante el uso compartido de secretos.
El intercambio secreto es una primitiva importante en varios protocolos para el cálculo seguro entre varias partes . El intercambio secreto también se puede utilizar para la autenticación de usuarios en un sistema. [12]
Ver también
- Estructura de acceso
- Tolerancia a fallas bizantinas
- Código de borrado : cuando los datos que se van a reconstruir no son secretos
- Uso compartido de secretos homomórficos : un protocolo de votación descentralizado simplista.
- Matriz ortogonal : se utiliza para construir algunos esquemas de umbral.
- Compartición secreta usando el teorema del resto chino
- Cálculo multiparte seguro
- Compartir el secreto de Shamir
- Criptografía visual
Referencias
- ^ Shamir, Adi (1 de noviembre de 1979). "Cómo compartir un secreto" (PDF) . Comunicaciones de la ACM . 22 (11): 612–613. doi : 10.1145 / 359168.359176 . S2CID 16321225 . Archivado (PDF) desde el original el 10 de agosto de 2017.
- ^ Blakley, GR (1979). "Protección de claves criptográficas" (PDF) . Gestión del conocimiento de requisitos, Taller internacional sobre (AFIPS) . 48 : 313–317. doi : 10.1109 / AFIPS.1979.98 . S2CID 38199738 . Archivado desde el original (PDF) el 28 de junio de 2018.
- ^ Krawczyk, Hugo (1993). Intercambio secreto reducido (PDF) . CRYPTO '93.
- ^ Rabin, Michael O. (1989). "Dispersión eficiente de información para seguridad, balanceo de carga y tolerancia a fallas". Revista de la ACM . 36 (2): 335–348. CiteSeerX 10.1.1.116.8657 . doi : 10.1145 / 62044.62050 . S2CID 13166422 .
- ^ Resch, Jason; Plank, James (15 de febrero de 2011). AONT-RS: Combinación de seguridad y rendimiento en sistemas de almacenamiento dispersos (PDF) . Usenix FAST'11 .
- ^ Franklin, Matthew; Yung, Moti (4 de mayo de 1992). "Complejidad de la comunicación de la computación segura (resumen extendido)" . STOC '92 Actas del Vigésimo Cuarto Simposio Anual ACM sobre Teoría de la Computación . Stoc '92: 699–710. doi : 10.1145 / 129712.129780 . ISBN 0897915119. S2CID 7486402 .(también disponible en [1] )
- ^ Parakh, Abhishek; Kak, Subhash (enero de 2011). "Uso compartido de secretos con uso eficiente del espacio para la seguridad implícita de los datos". Ciencias de la información . 181 (2): 335–341. doi : 10.1016 / j.ins.2010.09.013 .
- ^ Parakh, Abhishek; Kak, Subhash (septiembre de 2009). "Almacenamiento de datos online mediante seguridad implícita". Ciencias de la información . 179 (19): 3323–3331. doi : 10.1016 / j.ins.2009.05.013 .
- ^ Sahasranand, KR; Nagaraj, N .; Rajan, S. (2010). "Cómo no compartir una serie de secretos". Revista Internacional de Ciencias de la Computación y Seguridad de la Información . 8 : 234-237. arXiv : 1001.1877 . Código Bibliográfico : 2010arXiv1001.1877S .
- ^ Liu, Yanhong; Zhang, Futai; Zhang, Jie (febrero de 2016). "Ataques a algunos esquemas de intercambio de múltiples secretos verificables y dos esquemas mejorados". Ciencias de la información . 329 : 524–539. doi : 10.1016 / j.ins.2015.09.040 .
- ^ "Unvanish: reconstruir datos autodestructivos" . Archivado desde el original el 20 de marzo de 2012.
- ^ Gupta, Kishor Datta, et al. "Uso compartido secreto de Shamir para la autenticación sin reconstruir la contraseña". 2020 Décimo Taller y Conferencia Anual de Computación y Comunicación (CCWC). IEEE, 2020.
enlaces externos
- Ubuntu Manpage: gfshare - explicación de Shamir Secret Sharing en GF (2 8 )
- Descripción de los esquemas de Shamir y Blakley
- Patente para el uso de intercambio secreto para recuperar PGP (¿y otras frases de paso?) Patente de EE. UU. 6,662,299
- Una bibliografía sobre esquemas de intercambio de secretos
- Sistemas de firma de código que utilizan Shared Secret en Wayback Machine (archivado el 14 de febrero de 2008)
- Beimel, Amos (2011). "Esquemas de intercambio de secretos: una encuesta" (PDF) .