En criptografía, el problema de los criptógrafos de comedor estudia cómo realizar un cálculo seguro de múltiples partes de la función booleana-OR. David Chaum propuso este problema por primera vez a principios de la década de 1980 y lo usó como un ejemplo ilustrativo para demostrar que era posible enviar mensajes anónimos con imposibilidad de rastrear el remitente y el destinatario incondicionalmente. Las redes de comunicación anónimas basadas en este problema a menudo se denominan redes DC (donde DC significa "criptógrafos de comedor"). [1]
A pesar de la palabra cenar , el problema de los criptógrafos de comedor no está relacionado con el problema de los filósofos de comedor .
Descripción
Tres criptógrafos se reúnen alrededor de una mesa para cenar. El camarero les informa que la comida ha sido pagada por alguien, que podría ser uno de los criptógrafos o la Agencia de Seguridad Nacional (NSA). Los criptógrafos respetan el derecho de los demás a realizar un pago anónimo, pero quieren saber si la NSA pagó. Entonces deciden ejecutar un protocolo de dos etapas.
En la primera etapa, cada dos criptógrafos establecen un secreto compartido de un bit, digamos lanzando una moneda detrás de un menú para que solo dos criptógrafos vean el resultado de cada dos criptógrafos. Supongamos, por ejemplo, que después del lanzamiento de la moneda, el criptógrafo A y B comparten un bit secreto, A y C comparten , y B y C comparten .
En la segunda etapa, cada criptógrafo anuncia públicamente un bit, que es:
- si no pagaron por la comida, el OR exclusivo (XOR) de los dos bits compartidos que tienen con sus dos vecinos,
- si pagaron por la comida, lo contrario de ese XOR.
Suponiendo que ninguno de los criptógrafos pagó, entonces A anuncia , B anuncia y C anuncia . Por otro lado, si A pagó, anuncia.
Los tres anuncios públicos combinados revelan la respuesta a su pregunta. Uno simplemente calcula el XOR de los tres bits anunciados. Si el resultado es 0, implica que ninguno de los criptógrafos pagó (por lo que la NSA debe haber pagado la factura). De lo contrario, uno de los criptógrafos pagó, pero su identidad sigue siendo desconocida para los demás criptógrafos.
David Chaum acuñó el término red de criptógrafos de comedor , o DC-net, para este protocolo.
Limitaciones
El protocolo DC-net es simple y elegante. Tiene varias limitaciones, sin embargo, algunas soluciones se han explorado en la investigación de seguimiento (consulte la sección de Referencias a continuación).
- Colisión
- Si dos criptógrafos pagaron por la cena, sus mensajes se cancelarán entre sí y el resultado final de XOR será . Esto se llama colisión y permite que solo un participante transmita a la vez utilizando este protocolo. En un caso más general, una colisión ocurre siempre que un número par de participantes envíe mensajes.
- Ruptura
- Cualquier criptógrafo malintencionado que no quiera que el grupo se comunique con éxito puede bloquear el protocolo para que el resultado XOR final sea inútil, simplemente enviando bits aleatorios en lugar del resultado correcto del XOR. Este problema se produce porque el protocolo original se diseñó sin utilizar ninguna tecnología de clave pública y carece de mecanismos fiables para comprobar si los participantes siguen honestamente el protocolo. [2]
- Complejidad
- El protocolo requiere claves secretas compartidas por pares entre los participantes, lo que puede ser problemático si hay muchos participantes. Además, aunque el protocolo DC-net es "incondicionalmente seguro", en realidad depende de la suposición de que ya existen canales "incondicionalmente seguros" entre pares de participantes, lo que no es fácil de lograr en la práctica.
Un algoritmo de red de veto anónimo relacionado calcula el OR lógico de las entradas de varios usuarios, en lugar de un XOR lógico como en las redes de CC, que puede ser útil en aplicaciones para las que una operación de combinación de OR lógico es naturalmente adecuada.
Historia
David Chaum pensó por primera vez en este problema a principios de la década de 1980. La primera publicación que describe las ideas básicas subyacentes es la suya. [3] La versión de la revista apareció en el primer número de la revista Journal of Cryptology. [4]
Generalizaciones
Las redes de CC se generalizan fácilmente para permitir transmisiones de más de un bit por ronda, para grupos de más de tres participantes y para "alfabetos" arbitrarios distintos de los dígitos binarios 0 y 1, como se describe a continuación.
Transmisiones de mensajes más largos
Para permitir que un remitente anónimo transmita más de un bit de información por ronda de redes de CC, el grupo de criptógrafos puede simplemente repetir el protocolo tantas veces como desee para crear un número deseado de bits de ancho de banda de transmisión. Estas repeticiones no necesitan realizarse en serie. En los sistemas prácticos de DC-net, es típico que las parejas de participantes acuerden por adelantado un único secreto "maestro" compartido, utilizando el intercambio de claves Diffie-Hellman, por ejemplo. Luego, cada participante alimenta localmente este secreto maestro compartido en un generador de números pseudoaleatorios , con el fin de producir tantos "lanzamientos de moneda" compartidos como desee para permitir que un remitente anónimo transmita múltiples bits de información.
Tamaños de grupos más grandes
El protocolo se puede generalizar a un grupo de participantes, cada uno con una clave secreta compartida en común con los demás participantes. En cada ronda del protocolo, si un participante quiere transmitir un mensaje imposible de rastrear al grupo, invierten su parte anunciada públicamente. Los participantes se pueden visualizar como un gráfico completamente conectado con los vértices que representan a los participantes y los bordes que representan sus claves secretas compartidas.
Gráficos de intercambio de secretos dispersos
El protocolo puede ejecutarse con gráficos de intercambio de secretos menos que conectados, lo que puede mejorar el rendimiento y la escalabilidad de las implementaciones prácticas de DC-net, con el riesgo potencial de reducir el anonimato si los participantes coludidos pueden dividir el gráfico de intercambio de secretos en componentes conectados separados. Por ejemplo, una generalización intuitivamente atractiva pero menos segura paraparticipantes que utilizan una topología de anillo , donde cada criptógrafo sentado alrededor de una mesa comparte un secreto solo con el criptógrafo a su derecha e izquierda inmediatas, y no con todos los demás criptógrafos. Esta topología es atractiva porque cada criptógrafo necesita coordinar dos lanzamientos de moneda por ronda, en lugar de. Sin embargo, si Adam y Charlie son en realidad agentes de la NSA sentados inmediatamente a la izquierda y a la derecha de Bob, una víctima inocente, y si Adam y Charlie se confabulan en secreto para revelar sus secretos el uno al otro, entonces pueden determinar con certeza si Bob fue o no. el remitente de 1 bit en una ejecución DC-net, independientemente de cuántos participantes haya en total. Esto se debe a que los participantes en connivencia, Adam y Charlie, "dividen" efectivamente el gráfico de intercambio secreto en dos componentes separados y desconectados, uno que contiene solo a Bob y el otro que contiene a todos los demás participantes honestos.
Otra topología de red de CC compartida secreta de compromiso, empleada en el sistema Dissent para la escalabilidad, [5] puede describirse como una topología de cliente / servidor o de usuario / fideicomisario . En esta variante, asumimos que hay dos tipos de participantes que desempeñan roles diferentes: un número potencialmente grande n de usuarios que desean el anonimato y un número mucho menorde fideicomisarios cuya función es ayudar a los usuarios a obtener ese anonimato. En esta topología, cada uno de los los usuarios comparten un secreto con cada uno de los fideicomisarios, pero los usuarios no comparten secretos directamente con otros usuarios, y los fideicomisarios no comparten secretos directamente con otros fideicomisarios, lo que resulta en una matriz de intercambio secreto. Si el número de fideicomisarioses pequeño, entonces cada usuario necesita administrar solo algunos secretos compartidos, mejorando la eficiencia para los usuarios de la misma manera que lo hace la topología de anillo. Sin embargo, siempre que al menos un fideicomisario se comporte con honestidad y no filtre sus secretos ni se confabulara con otros participantes, ese fideicomisario honesto forma un "centro" que conecta a todos los usuarios honestos en un único componente completamente conectado, independientemente de cuál o cómo muchos otros usuarios y / o fideicomisarios pueden estar conspirando deshonestamente. Los usuarios no necesitan saber o adivinar qué fideicomisario es honesto; su seguridad depende únicamente de la existencia de al menos un fideicomisario honesto y no coludido.
Alfabetos alternativos y operadores de combinación
Aunque el protocolo simple DC-nets usa dígitos binarios como su alfabeto de transmisión y usa el operador XOR para combinar textos cifrados, el protocolo básico se generaliza a cualquier alfabeto y operador de combinación adecuado para el cifrado de almohadilla de una sola vez . Esta flexibilidad surge naturalmente del hecho de que los secretos compartidos entre los muchos pares de participantes son, en efecto, meras almohadillas de una sola vez combinadas simétricamente dentro de una sola ronda DC-net.
Una opción alternativa útil de operador de combinación y alfabeto de redes de CC es usar un grupo finito adecuado para la criptografía de clave pública como el alfabeto, como un grupo de Schnorr o una curva elíptica, y usar el operador de grupo asociado como la combinación de redes de CC. operador. Tal elección de alfabeto y operador hace posible que los clientes utilicen técnicas de prueba de conocimiento cero para probar las propiedades de corrección de los textos cifrados de red de CC que producen, como que el participante no está "bloqueando" el canal de transmisión, sin comprometer la anonimato ofrecido por DC-net. Esta técnica fue sugerida por primera vez por Golle y Juels, [6] desarrollada posteriormente por Franck, [7] y luego implementada en Verdict , una implementación criptográficamente verificable del sistema Dissent . [8]
Manejar o evitar colisiones
La medida originalmente sugerida por David Chaum para evitar colisiones es retransmitir el mensaje una vez que se detecta una colisión, pero el documento no explica exactamente cómo organizar la retransmisión.
La disensión evita la posibilidad de colisiones involuntarias mediante el uso de una mezcla verificable para establecer un programa de transmisión de redes de CC, de modo que cada participante sepa exactamente qué bits del programa corresponden a su propia ranura de transmisión, pero no sabe quién es el propietario de otras ranuras de transmisión. [9]
Contrarrestar los ataques disruptivos
Herbivore divide una gran red de anonimato en grupos DC-net más pequeños, lo que permite a los participantes evadir los intentos de interrupción dejando un grupo interrumpido y uniéndose a otro grupo, hasta que el participante encuentra un grupo libre de disruptores. [10] Este enfoque de evasión introduce el riesgo de que un adversario que posea muchos nodos pueda interrumpir selectivamente solo los grupos que el adversario no ha comprometido por completo , "conduciendo" a los participantes hacia grupos que pueden ser funcionales precisamente porque están completamente comprometidos. [11]
Dissent implementa varios esquemas para contrarrestar la disrupción. El protocolo original [9] utilizaba un shuffle criptográfico verificable para formar un programa de transmisión DC-net y distribuir "asignaciones de transmisión", permitiendo verificar la exactitud de los textos cifrados DC-net subsiguientes con una simple verificación de hash criptográfica . Sin embargo, esta técnica requería un nuevo verificable antes de cada ronda de DC-nets, lo que conducía a altas latencias. Un esquema posterior, más eficiente, permite que una serie de rondas de DC-net continúen sin intervenir barajas en ausencia de interrupción, pero en respuesta a un evento de interrupción utiliza una mezcla para distribuir acusaciones anónimas que permiten a una víctima de interrupción exponer y probar la identidad de el perpetrador. [5] Finalmente, las versiones más recientes admiten redes de CC totalmente verificables, a un costo sustancial en eficiencia de cálculo debido al uso de criptografía de clave pública en la red de CC, así como un modo híbrido que usa CC eficiente basado en XOR. redes en el caso normal y redes de CD verificables solo en caso de interrupción, para distribuir las acusaciones más rápidamente de lo que es factible usando barajas verificables. [8]
Referencias
- ^ Chaum DL (1988). "El problema de los criptógrafos de comedor: imposibilidad de rastrear el remitente y el destinatario incondicional". J Cryptol . 1 (1): 65–75.
- ^ Caballeros y bribones .
- ^ David Chaum (1985). "Seguridad sin identificación: sistemas de transacciones para hacer obsoleto al hermano mayor" (PDF) . Comunicaciones de la ACM . 28 (10): 1030-1044. CiteSeerX 10.1.1.319.3690 . doi : 10.1145 / 4372.4373 . S2CID 15340054 .
- ^ David Chaum (1988). "El problema de los criptógrafos de comedor: remitente incondicional y no rastreabilidad del destinatario" . Revista de criptología . 1 (1): 65–75. CiteSeerX 10.1.1.127.4293 . doi : 10.1007 / BF00206326 . S2CID 2664614 .
- ^ a b David Isaac Wolinsky; Henry Corrigan-Gibbs; Bryan Ford; Aaron Johnson (8 al 10 de octubre de 2012). Disentir en números: hacer una fuerte escala de anonimato . X Simposio USENIX sobre Diseño e Implementación de Sistemas Operativos (OSDI). Hollywood, CA, Estados Unidos.
- ^ Philippe Golle; Ari Juels (2 al 6 de mayo de 2004). Criptógrafos gastronómicos revisados (PDF) . Eurocrypt 2004. Interlaken, Suiza.
- ^ Franck, Christian (2008). Nuevas direcciones para criptógrafos gastronómicos (PDF) (tesis de maestría).
- ^ a b Henry Corrigan-Gibbs; David Isaac Wolinsky; Bryan Ford (14 al 16 de agosto de 2013). Mensajería anónima responsable proactivamente en veredicto . 22º Simposio de Seguridad de USENIX. Washington, DC, Estados Unidos.
- ^ a b Henry Corrigan-Gibbs; Bryan Ford (octubre de 2010). Disentir: Anonimato de grupo responsable . 17ª Conferencia de la ACM sobre seguridad informática y de las comunicaciones (CCS). Chicago, IL, Estados Unidos. Archivado desde el original el 29 de noviembre de 2012 . Consultado el 9 de septiembre de 2012 .
- ^ Emin Gün Sirer; Sharad Goel; Mark Robson; Doğan Engin (19 al 22 de septiembre de 2004). Eludir a los carnívoros: compartir archivos con un fuerte anonimato (PDF) . Taller europeo ACM SIGOPS. Lovaina, Bélgica.
- ^ Nikita Borisov; George Danezis; Prateek Mittal; Parisa Tabriz (octubre de 2007). ¿Denegación de servicio o denegación de seguridad? Cómo los ataques a la confiabilidad pueden comprometer el anonimato (PDF) . Conferencia ACM sobre Seguridad Informática y Comunicaciones (CCS). Alexandria, VA, Estados Unidos.