Contraseña de error tolerante de la prueba

2

Quiero usar gpg con una contraseña simétrica para cifrar un mensaje. Cómo hacer esto se explica aquí en el foro, pero también en internet. Soy consciente de que una clave simétrica tiene el problema general del intercambio de claves. Una posible solución es hacer un cuestionario. La idea es tomar 20 preguntas de una prueba de examen, que se pueden responder con a, b, c o d. Y esta será la contraseña para cifrar el mensaje. La entropía de la contraseña es 4 ^ 20, que es lo suficientemente alta como para un pequeño examen divertido.

El problema es que el software PGP necesita una contraseña 100% correcta. Pero en realidad ningún alumno podrá responder todas las preguntas correctamente. Lo que necesito es algo que sea un poco tolerante a errores. ¿Cuál es el algoritmo para generar una contraseña, que también es correcto si solo el 90% de las preguntas son contestadas correctamente? ¿Se puede hacer esto con algún tipo de función hash o sal?

La idea desde una perspectiva educativa es que los estudiantes asisten primero a un cuestionario y, si lo han hecho bien, pueden leer el mensaje secreto que contiene la música. Solo el alumno que tuvo éxito puede escuchar la canción.

    
pregunta Manuel Rodriguez 26.04.2018 - 17:03
fuente

2 respuestas

3

Una forma en que puedes hacer esto es con el intercambio secreto de Shamir . Los datos de su canción tendrán un prefijo con un valor que se sabe que es bueno (por ejemplo, "RIGHTKEY") y luego se cifrarán con un cifrado simétrico como AES-CTR-128, y el secreto compartido S sería la clave AES convertida en un entero de 128 bits.

Usando Shamir, generarías tus 20 puntos en la curva, cada uno en la forma [x, f (x)] . Asigne cada punto a una pregunta, agregando el valor correcto de la respuesta (mapeando a, b, c, d a 1,2,3,4) a la parte f (x) , de manera que obtenga puntos en la forma [x, f (x) + q] donde q es el índice de respuesta correcta 1, 2, 3 o 4. Si un estudiante tuviera que mirar En el código fuente de la página, solo verían un punto [x, y] y no sabrían cuál es el valor de f (x) o q es.

Al enviar la hoja de respuestas completa, revisa cada respuesta y resta el índice de la respuesta dada de la segunda parte del punto. Si la respuesta es correcta, su valor se habrá restado al valor original de f (x) . Si suficientes de sus respuestas son correctas, tendrán suficientes puntos [x, f (x)] para descifrar el secreto. Como algunas de sus respuestas pueden estar equivocadas, no puedes usar todos los puntos. En su lugar, recorre cada posible combinación de respuestas k e intenta calcular el secreto compartido, luego usa el secreto resultante para descifrar los primeros 8 bytes de la canción cifrada y ver si los datos son "RIGHTKEY" . Si es así, sabes que tienes la clave correcta. Si no, pasa a la siguiente iteración y vuelve a intentarlo. Para un valor de k = 16 con 20 preguntas, solo necesita hacer 4845 intentos como máximo; para respuestas correctas suficientes, esto será mucho más rápido ya que es probable que encuentre una combinación correcta al principio del proceso de descifrado.

Contra un enfoque ingenuo de fuerza bruta, el sistema tiene un límite de seguridad de 4 k para un umbral de k respuestas correctas. La principal debilidad es que si un examinador está absolutamente seguro de algunas respuestas pero no conoce otras, puede usar las que sabe que son correctas para reducir significativamente el espacio de fuerza bruta. Sin embargo, en última instancia, este es un problema inherente para cualquier método de validación del lado del cliente que utiliza umbrales. La única forma de evitar esto es tener el examen validado en el lado del servidor contra un conjunto de respuestas conocidas.

    
respondido por el Polynomial 26.04.2018 - 17:53
fuente
0

La solución más fácil que viene a la mente es usar un código de corrección de errores como parte de la prueba. Una variante conocida es los códigos de Hamming. Usaría Hamming (20,15) para eso.

Una opción alternativa que podría ser más intuitiva para la implementación manual por parte de los estudiantes es un código rectangular . Puede organizar las 20 preguntas en una cuadrícula de 5x4 algo impropia para el cheque, o extender la prueba a 24 preguntas para una cuadrícula de 5x5-1 adecuada.

En ambos casos, algunas preguntas se vuelven esencialmente opcionales si era perfecto en los "bits de datos". No puedo sugerir una forma simple y escalable de evitar eso (para garantizar que 1 y solo 1 error sea corregible), aparte de usar un programa de verificación de caja negra, aunque eso no significa que no exista uno.

    
respondido por el Therac 26.04.2018 - 17:37
fuente

Lea otras preguntas en las etiquetas