Asegurar una predicción sobre un evento futuro

12

Quiero hacer una predicción sobre un evento futuro, pero solo revelar esa predicción después de que ocurra el evento, a menos que el conocimiento de mi predicción afecte el resultado.

Por ejemplo, supongamos que Alice predice que Bob beberá el vaso de leche derramado el 24 de abril a las 9:17 AM. Ella escribe en un archivo de texto:

Bob spills his glass of milk on April 24th at 9:17 AM.

Alice no quiere que Bob conozca los detalles específicos de la predicción antes del evento, de lo contrario, Bob podría evitar la leche ese día para evitar el resultado de la predicción de Alice. Sin embargo, si Alice solo revela la predicción después de el evento, Bob puede afirmar que Alice inventó la predicción después de que el evento ya haya ocurrido.

Naturalmente, Alicia debe proporcionar una verificación de la autenticidad de su predicción a Bob antes del evento, una verificación que no revela los detalles de la predicción hasta después del evento, pero que confirma que la predicción se realizó antes del evento .

He encontrado dos métodos de verificación posibles:

  1. Encriptación
    • Alice aplica un algoritmo de cifrado de clave simétrica (como AES) en el archivo de texto
    • Alice le proporciona a Bob el archivo cifrado
    • Después de que ocurra el evento, Alice le proporciona a Bob la contraseña secreta
    • Bob descifra el archivo cifrado y lee la predicción
  2. Hashing
    • Alice aplica un algoritmo de hash (como SHA-256) en el archivo de texto
    • Alice le proporciona a Bob el hash computado
    • Después de que ocurra el evento, Alice le proporciona a Bob el archivo de texto original
    • Bob aplica el mismo algoritmo de hash en el archivo de texto y verifica el hash

¿Cuál es el método de verificación más seguro (es decir, que teóricamente sería más difícil para Bob superar y, por lo tanto, descubrir la predicción antes de que ocurra el evento)?

¿Cuál es el método de verificación más práctico (por ejemplo, los hashes ocupan un espacio significativamente más pequeño que un archivo cifrado)?

    
pregunta Vilhelm Gray 30.01.2014 - 17:46
fuente

1 respuesta

12

Encriptación no ofrece la funcionalidad que busca; Al menos no directamente. Como caso extremo, considere Pad de una sola vez : la clave es tanto como los datos a cifrar y el cifrado. se realiza con un XOR bit a bit: dada la clave K y el texto simple P , el texto cifrado es C = P XOR K . Supongamos que utilizó OTP para su cifrado; usted predijo P y publicó la versión encriptada C . Más tarde, la predicción resultó ser errónea; Bob no derrama leche sino vino (a las 9:17 AM, ¡qué vergüenza!). Ahora desea aparecer como si lo hubiera predicho correctamente todo el tiempo; por lo tanto, usted quiere que el texto cifrado C se descifre como P ', no P (tenga en cuenta que P' tiene la misma longitud que P ). Esto es fácil: calcula la clave K '= C XOR P' y publica K ' como la clave que usaste. Puede verificar que C es de hecho el resultado del cifrado de P ' por K' .

Entonces, con OTP, puede falsificar a posteriori el mensaje inicial. Esta es la característica que hace de la OTP un sistema de cifrado teóricamente irrompible: cada texto posible es posible (con la misma probabilidad) para un texto cifrado dado.

Por lo tanto, si usa otro sistema de encriptación (por ejemplo, algunos AES), puede proporcionar el tipo de compromiso que busca solo por ser imperfecto como Un sistema de cifrado. Esto no parece ser una buena base para la seguridad: debe ser bueno, pero no demasiado bueno.

Hashing es un candidato mucho mejor. Hash la predicción P en H = SHA-256 ( P ), luego publique el valor hash. Más adelante, revele P : todos pueden hacer un hash del P y ver si coincide con el valor hash previamente publicado H . Esto es seguro siempre y cuando la función hash sea resistente a colisiones, es decir, siempre que no pueda crear dos predicciones P y P ' que tengan el mismo valor (porque de lo contrario puede elegir revelar el que sucedió).

Como nota al margen, la publicación puede tomar varias formas. Considere timestamping de confianza : este es un método público para los compromisos. La Time Stamping Authority (TSA) recibe un valor de hash, lo encapsula en una estructura que también contiene la fecha y la hora actuales (como la conoce la TSA) y firma la estructura. En efecto, la TSA, por su firma, dice (de manera verificable): "ese valor hash H se publicó en la fecha T o antes, porque lo vi en fecha T ". En un mundo no informático, este trabajo se realiza con un sobre de Soleau .

El valor de hash tiene un inconveniente: potencialmente permite que alguien intente forzar la predicción con fuerza bruta. Dado el valor de hash H , se podrían probar las posibles predicciones de P y agruparlas todas hasta encontrar una coincidencia, reconstruyendo así la predicción antes de revelarla. Por ejemplo, uno podría saber que usted predice el derrame de alguna bebida en alguna fecha y prueba todas las combinaciones de bebidas y dátiles. Dado que el hashing puede proceder a una velocidad de miles de millones de mensajes por segundo (con una buena GPU), algunas predicciones estructuradas estarían en riesgo de revelación temprana. Para evitar este ataque, agregue un relleno aleatorio al final:

Bob spills his glass of milk on April 24th at 9:17 AM, and
here is random padding:sef9yb94bo3qr7yqwnc67sb32

Asegúrese de usar nuevos caracteres aleatorios cada vez que haga una predicción (¡no los reutilice!). Tenga en cuenta que se puede crear un ejemplo artificial de una función hash que sea "segura" en el sentido de que no permite que se calculen las colisiones, pero aún falla al ocultar el valor de predicción; Sin embargo, este sería un ejemplo artificial. Con SHA-256, el relleno aleatorio hará el trabajo, siempre que agregues suficientes (un carácter al azar agregará 5 o 6 bits de entropía; a los 80 bits, los enemigos son derrotados por completo, por lo que 16 caracteres son suficientes). Un inconveniente del método es que tiene que mantener la cadena de entrada completa, es decir, la predicción padded , con los caracteres aleatorios; esto puede ser problemático si tiene la intención de mantenerlo en su cabeza.

    
respondido por el Tom Leek 30.01.2014 - 19:10
fuente

Lea otras preguntas en las etiquetas