Loading
Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of Cryptography Prof. Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bangalore Lecture – 54 Schnorr Signature Scheme y TLS o SSL (Consulte el tiempo de la diapositiva: 00:33) Hola a todos. Bienvenidos a esta conferencia. El plan para esta conferencia es el siguiente y esta conferencia vamos a discutir una transformación o heurística muy poderosa, a la que llamamos como heurística de Fiat-Shamir. Lo que nos permite obtener esquemas de firma digital de cualquier esquema de identificación segura y luego veremos cómo aplicar esta transformación a ningún esquema de firma para obtener un esquema de firma digital basado en la suposición discreta de las anotaciones. Por último, veremos una visión general del protocolo TLS y SSL. (Consulte la hora de la diapositiva: 01:00)Así que, comencemos nuestra discusión con la transformación de Fiat-Shamir. Por lo tanto, lo que hace Fiat-Shamir heurística o transformación es, toma cualquier esquema de identificación interactiva de 3 rondas, que tiene estructura de compromiso, desafío, respuesta. Y la transformación convierte ese protocolo interactivo en un protocolo no interactivo. No interactivo en el sentido de que solo tendrá una ronda de interacción desde el probador hasta el verificador y utilizando ese protocolo no interactivo básicamente, terminamos consiguiendo un esquema de firma de 1 ronda. La idea detrás de esta transformación es que, si tienes un esquema de identificación y si quieres sacar un esquema de firma de eso, entonces para firmar el mensaje usando la clave de firma, el firmante tiene que actuar como prover y tiene que ejecutar todo el protocolo del esquema de identificación en su mente. Según las reglas de esta transformación, venga con toda la transcripción en un solo disparo y dárselo al verificador. Esto significa que, en el protocolo interactivo de tres rondas que existía para el sistema de identificación, el verificador habría elegido el reto. Pero lo que estamos diciendo aquí es que después de hacer esta transformación, incluso el desafío también será escogido por el propio prover. Tiene que desempeñar el papel del prover, así como el verificador simultáneamente. Por lo tanto, es posible que se esté preguntando que si a prover se le da la provisión para escoger el desafío en nombre del verificador, el prover malicioso o el prover trampa puede engañar. Puede que no escoja un desafío uniformemente aleatorio. Resulta que la transformación de Fiat-Shamir es tan inteligente que termina incluso forzando al prover de trampas a elegir desafíos uniformemente aleatorios. Así que, aquí es como hacemos la conversión de protocolo interactivo de 3 vueltas en 1 ronda de protocolo interactivo. Por lo tanto, se nos da un esquema de identificación de 3 rondas Gen, 1, 2,. Usándolo, queremos obtener 1-round signature scheme sign = (Gen, Sign, Vrfy). Como parte de esta transformación, asumimos que tenemos la descripción pública de algunas entradas de longitud arbitraria de correlación de funciones hash a los elementos del espacio de desafío del esquema de identificación subyacente. Por lo tanto, el algoritmo de generación de claves de este esquema de firma, será el mismo que el algoritmo de generación de claves de su esquema de identificación. Ahora el algoritmo de firma es el siguiente. Imagine, hay un firmante que tiene la clave de firma sk, y tiene un mensaje en el que quiere generar su firma. Por lo tanto, como he dicho antes, tiene que desempeñar el papel del prover, así como el verificador del propio esquema de identificación. Por lo tanto, ejecuta el algoritmo P1 en la clave de firma para obtener el compromiso I y una información de estado, y ahora tiene que seleccionar la aleatoriedad de desafío r en nombre del propio verificador. Por lo tanto, lo ideal es que elija la aleatoriedad del retador r uniformemente al azar del espacio de desafío, pero ahora vamos a diseñar un esquema de firma. Por lo tanto, el mensaje también debe entrar en la imagen mientras se recoge la aleatoriedad r o el retador r. Por lo tanto, para escoger el desafío. Entonces, la idea aquí es básicamente, el desafío r va a estar de alguna manera asociado con el mensaje, que el remitente quiere firmar aquí. Y si asumimos o si modelizamos la función hash subyacente como un oráculo aleatorio aquí, resulta que el valor r, que el firmante va a obtener al generar r según este método, será de hecho un valor uniformemente aleatorio del espacio de desafío del esquema de identificación subyacente. Una vez que se genera el r, el firmante tiene que generar la parte de respuesta, es decir, ejecutando el algoritmo P2, y finalmente la firma es (r, s). Por lo tanto, ahora para enviar un mensaje firmado al verificador, sólo enviará un mensaje junto con la firma (r, s). Y la forma en que el verificador verifica la firma es, ejecuta el algoritmo de verificación del esquema de identificación subyacente, pero hay una diferencia. En el esquema de identificación original, el verificador estaba verificando si la salida del algoritmo de verificación con la clave de verificación y la parte (r, s) de la transcripción da la parte I de la transcripción o no. Aquí, por otro lado, la parte s del algoritmo de verificación del esquema de firma, el verificador va a ejecutar el algoritmo de verificación del esquema de identificación subyacente, pero no compara la salida de la función V con el componente I , porque no conoce el componente I tal cual. Si ve la estructura de este esquema de firma, el I no lo proporciona el firmante al verificador, mientras que en el esquema de identificación, el verificador ya habría obtenido un I y por eso podría comparar la salida de la función V con el compromiso I dado por el prover. Por lo tanto, en el algoritmo de verificación del esquema de firma, I se calcula desde cero por el verificador ejecutando la función V e idealmente este I debería ser el mismo I, que un probador legítimo en el esquema de identificación habría comprometido con un verificador honesto. Ahora, para verificar la firma de lo que es el verificador, ahora tiene el valor I , ahora tiene el valor m y comprueba. Luego acepta la firma, de lo contrario, rechaza la firma. Idealmente, si de hecho el firmante y el firmante son honestos, entonces el I generado ejecutando la función de verificación o la función V en la clave de verificación r y s habría dado un I, de tal forma que debería ser igual a r. Por lo tanto, la declaración del teorema que podemos probar aquí es que si usted está en el modelo de oráculo aleatorio, y si este esquema de identificación pi es un esquema de identificación seguro, entonces el esquema de la firma que hemos generado aquí de hecho es un esquema de firma segura. La prueba está ligeramente involucrada, y tenemos que entrar en los tecnicismos del modelo random-oracle. Por lo tanto, me estoy saltando la prueba formal completa, sólo veremos una visión general de la prueba, usted puede ver la prueba formal completa en el libro de Katz y Lindell. La idea aquí es que si ves la distribución de r que el firmante ha generado en el algoritmo de firma, su distribución es exactamente la misma que habría sido en una ejecución real del esquema de identificación, siempre que estés en el modelo random-oracle. Eso significa, incluso el firmante es corrupto, no tiene control sobre la aleatoriedad r porque va a ser un valor aleatorio uniforme, porque va a ser una salida del oráculo aleatorio. La forma en que hemos diseñado el esquema de firma, en el algoritmo de firma, la aleatoriedad r, o el reto r, que el firmante está generando, es básicamente una función tanto del compromiso I como del mensaje en el que quiere generar la firma. Así que, si tenemos un adversario que quiere forjar una firma en nombre del firmante sin saber realmente la clave de la firma sk, entonces básicamente lo que el forger tiene que hacer es sin conocer la clave de firma sk, tiene que llegar con alguna información de I y de estado y tiene que llegar con algún desafío r, al consultar el oráculo aleatorio, y tiene que llegar con alguna respuesta s, de tal manera que en general es una transcripción de aceptación, a saber (I, r, s) es una transcripción de aceptación y no sólo esa salida del azar-oracle en el compromiso I y el mensaje es igual a r. Todo esto tiene que ver sin saber realmente la clave de la firma. Si existe un adversario que de hecho puede hacer eso con una probabilidad significativa, entonces intuitivamente significa que tiene un adversario que puede incluso forjar o que puede romper la seguridad de este esquema de identificación subyacente, es decir, incluso sin saber la clave de la firma o la clave secreta, sk, ese adversario podría llegar con una transcripción legítima de aceptación en nombre del prover y convencer al verificador y conseguir que se acepte. Pero eso va en contra del supuesto de que el esquema de identificación subyacente es un esquema de identificación seguro. Así que esa es una idea intuitiva detrás de esta transformación Fiat-Shamir. No voy a entrar en los detalles formales completos. (Consulte la hora de la diapositiva: 10:20)Ahora, veamos cómo podemos aplicar la transformación Fiat-Shamir en el esquema de identificación debido a Schnorr y, como resultado, obtenemos un esquema de firma, que denominamos Schnorr Signature Scheme. Subrayo que esta transformación de Fiat-Shamir es una transformación genérica. Puede aplicarse en cualquier esquema de identificación, en cualquier esquema de identificación de tres rondas, para obtener un esquema de firma de 1 ronda. Aquí lo estamos aplicando en el marco del Esquema de Identificación de Schnorr. Por lo tanto, recordemos que en el Schnorr Identification Scheme, la clave secreta:, y el esquema de identificación es el siguiente: el probador en el esquema de identificación quiere saber, por lo que demostrar que se compromete, mediante el envío de gk. El verificador lanza una combinación lineal aleatoria r y el prover tiene que presentar una respuesta s. A saber, una combinación lineal (mod y el verificador verifica el − = o no. Si aplica la heurística Fiat-Shamir en el esquema de identificación, el algoritmo de generación de claves del esquema de firma será el siguiente: la clave de verificación donde la clave de firma correspondiente:. Junto con eso, habrá una descripción públicamente conocida de una función hash de la función de hash ⇒ Z, porque el espacio de desafío aquí no es nada más que Z. El algoritmo de firma será el siguiente: imagine que hay un firmante con un para firmar un mensaje m. Primero calcula el compromiso al escoger un valor elegido al azar, y luego escoge el reto en nombre del verificador llamando, calcula el mod de respuesta, y la firma es (r, s, m). Para verificar la firma, el verificador tiene que generar el compromiso de −, y lo que salga, que se trate como el compromiso del firmante para el esquema de identificación de Schnorr subyacente. Entonces el verificador genera el desafío que este compromiso calculado y el mensaje que el firmante está enviando habría producido, por lo que el verificador llama al azar-oracle Output 1, iff, que el firmante está afirmando ser parte de la firma. De acuerdo con la seguridad de la heurística de Fiat-Shamir, este esquema de firma de 1 ronda es de hecho un esquema de firma de seguridad en el modelo de oráculo aleatorio. Por lo tanto, ahora tenemos un esquema de firma candidato basado en la suposición discreta del registro. Resultó que Schnorr patentó esta idea. Por lo tanto, básicamente patentó su esquema de identificación de tres rondas, por lo que como resultado el esquema de firmas que sale al aplicar la transformación Fiat-Shamir también es considerado como patentado, por lo que no podemos utilizarlo en el dominio público. Así que lo que hizo NIST es, desarrolló una variación del esquema de Identificación de Schnorr y al aplicar la transformación Fiat-Shamir en esa variante, obtuvo un esquema de firma basado en la suposición discreta del registro, que llamamos como DSA, Digital Signature Algorithm. Es un estándar bien conocido que utilizamos en la práctica y el grupo subyacente que utilizamos en este algoritmo DSA es el grupo basado en el punto de curvas elípticas modulo prime, entonces la instanciación de la DSA se llama ECDSA, Elliptic Curve Digital Signature Algorithm y se trata de un algoritmo de firma digital muy popular utilizado en varias aplicaciones del mundo real. (Consulte la hora de la diapositiva: 14:48) Por lo tanto, ahora más o menos llegamos al final de la discusión sobre la criptografía de clave pública. Hemos visto una instanciación del esquema de cifrado, firmas digitales y demás. Durante la primera mitad del curso, hemos discutido rigurosamente sobre el cifrado de claves simétricas. Por lo tanto, ahora veremos cómo combinar varios primitivos criptográficos en ambos mundos, nos encontramos con un verdadero protocolo de comunicación segura mundial. Así que lo que voy a discutir es una visión general de muy alto nivel del protocolo SSL, que en realidad es el sucesor del protocolo TLS y esto es sólo una visión general de muy alto nivel. No debemos tratar la discusión como una implementación real del SSL para los detalles exactos bajo un análisis completo del protocolo SSL. Debe consultar cualquier texto estándar en la seguridad de la red. Por lo tanto, aquí es como funciona el protocolo SSL. Así que, imagine que tiene un ordenador y en su navegador, escriba https seguido de xyz.com, por ejemplo google.com. Así que tan pronto como escriba https, el s aquí indica que realmente desea iniciar una sesión de comunicación segura con el servidor llamado mail.google.com. Y tan pronto como escribe esto en realidad el protocolo SSL comienza a ejecutar, y como parte de este protocolo SSL, hay dos subprotocolos, que se ejecutan. Hay un protocolo de reconocimiento donde se produce alguna interacción entre el cliente, que el navegador en este caso y el servidor que es google.com en este caso. En cuanto al protocolo de reconocimiento si todo va bien, entonces se establece una clave entre el servidor y el cliente. Por lo tanto, para empezar con el cliente, y el servidor no tenía información previa compartida, pero tan pronto como el protocolo de reconocimiento se ejecuta y se realiza el intercambio de claves autenticadas entre el servidor y el cliente. Si el protocolo de reconocimiento es satisfactorio, la clave se establecerá correctamente entre el servidor y el cliente. Ahora, una vez establecida la clave, el segundo subprotocolo que se inicia ejecutando es el protocolo de capa de registro. Este protocolo de capa de registro lo que hace es que hace la comunicación privada autenticada entre el servidor y el cliente utilizando las claves que se han establecido durante el protocolo de reconocimiento. En términos de primitivas criptográficas para hacer el intercambio de claves autenticado, el protocolo de reconocimiento utiliza criptografía de clave pública mientras que una vez establecida la clave para hacer la comunicación real entre el servidor y el cliente, el protocolo de capa de registro utiliza las primitivas de clave privada. Ahora usted puede ver cómo exactamente los diversos primitivos criptográficos se combinan para hacer o resolver todo el problema de la comunicación segura aquí. Así que ahora vamos un poco más profundo en los detalles del protocolo de apretón de manos y el protocolo de la capa de registro. Por lo tanto, recuerde que el objetivo del protocolo de reconocimiento es realizar un intercambio de claves autenticado entre el cliente y el servidor. Imagine que el servidor tiene su propia clave pública y una clave de descifrado para un mecanismo de encapsulación de claves seguras de CCA e imagina que tenemos varias autoridades de certificación disponibles en el mercado que tienen su propia clave de firma y clave de verificación.En este ejemplo, estoy suponiendo que hay cuatro autorizaciones de certificado, y supongo que la clave de verificación de las autorizaciones de certificados ya están preconfiguradas en el navegador, que es utilizado por el cliente. Por lo tanto, si quieres puedes ir a la configuración del navegador que estás utilizando y puedes ver la clave de verificación de las conocidas autoridades certificadora, que ya están incrustadas en tus navegadores. También asumo aquí que el servidor en este caso tiene un certificado emitido por las autoridades de segundo certificado que certifican su clave de cifrado o la clave pública y que dicho certificado está disponible con el servidor. Por lo tanto, tan pronto como el protocolo de apretón de manos comienza a ejecutarse entre el cliente y el servidor, el primer mensaje va del cliente al servidor, donde básicamente el cliente envía las ciphersuites soportadas, a saber, qué versión de la función hash que soporta, qué versión de los cifrados de bloque que soporta, qué versión del generador de pseudorandom que soporta, y así sucesivamente y junto con que el cliente envía el valor nonce elegido al azar. En respuesta, el servidor elige una nonce aleatoria, y envía las suites de cifrado que soporta, a saber, su versión de función hash, su versión de ciphers de bloques, generadores de pseudorandom y así sucesivamente. Y junto con que el servidor envía la clave pública de su mecanismo de encapsulación clave, y para convencer de que de hecho esta clave pública pertenece al llamado servidor, el remitente envía el certificado que podría haber obtenido de una de estas autoridades de certificación. En este ejemplo, es la segunda autoridad certificadora. Por lo tanto, básicamente la idea aquí es que tanto el cliente como el servidor están tratando de ponerse de acuerdo sobre la versión de ciphersuites que van a utilizar para el resto de la comunicación, y junto con que el servidor está enviando su clave de cifrado o la clave pública y demostrar que de hecho la clave pública pertenece al servidor mediante el envío del certificado correspondiente. Ahora, lo que hace el cliente es, comprueba o verifica el certificado. Para verificar el certificado, utiliza la clave de verificación de la entidad emisora de certificados que ha emitido ese certificado en el servidor y, en este caso, el certificado ha sido emitido por la segunda autoridad certificadora. Se utilizará la clave de verificación de la segunda autoridad certificadora y si sólo se verifica satisfactoriamente el certificado, la comunicación continuará, de lo contrario el cliente terminará anormalmente la sesión. Ahora, es posible que el certificado sea emitido por una entidad emisora de certificados cuya clave de verificación no esté incluida en el navegador del cliente. En ese caso, esta verificación no tendrá salida. Como resultado, el navegador lanzará un mensaje de aviso al usuario o al cliente, a saber, diciendo que, “ no puedo identificar, o no puedo reconocer la validez del certificado ”. Este es un mensaje de error común, que a menudo nos encontramos cuando tratamos de hacer una comunicación SSL con un servidor, cuyo certificado no puede ser reconocido por nuestro navegador. Recibimos el mensaje de advertencia de que usted puede proceder a su propio riesgo. Es por ello que siempre se recomienda actualizar las versiones de tu navegador porque cada vez que se te ocurre con tu nueva versión de tu navegador, la clave de verificación de las nuevas autoridades certificadora se embeben en las nuevas versiones y de ahí que no obtendrás este tipo de mensaje de error. En este ejemplo, asumo que la clave de verificación de la entidad emisora de certificados está disponible con el cliente y el certificado se verifica correctamente. Una vez que se realiza la verificación del certificado, ahora lo que hace el cliente es que ejecuta el algoritmo de encapsulación del mecanismo de encapsulación de claves subyacente utilizando la clave pública proporcionada por el servidor. Como resultado, se producirá una clave secreta, que denoté como pmk. La encapsulación de este pmk no es más que clave premaestra. Por lo tanto, este algoritmo de encapsulación generará una clave premaestra y su encapsulación c. La encapsulación c se enviará al servidor y lo que el cliente va a hacer es que va a ejecutar una función de derivación de claves en las entradas Nc y Ns, es decir, las dos no-ces, que son seleccionadas por el cliente y el servidor respectivamente, la clave premaestra y la salida se consideran como una clave maestra. Por otra parte, cualquier comunicación ha sucedido entre el cliente y el servidor hasta ahora, incluyendo esta encapsulación c, que se llame como transcripción. Todo este cliente de transcripción se autentica utilizando un código de autenticación de mensajes y utilizando la clave maestra como clave, y el código correspondiente se envía al servidor. Por lo tanto, ese es un mensaje ahora del lado del cliente. Lo que hace el servidor es, toma la encapsulación c y ejecuta el algoritmo de descapitalización en esta encapsulación c para obtener la misma clave premaestra pmk. Una vez que obtiene la clave premaestra, ejecuta la función de derivación de claves en los dos valores de nonce y la clave premaestra para obtener la clave maestra.Por lo tanto, ahora, según nuestra suposición, tanto el cliente como el servidor habrían acordado las versiones de la función de derivación de claves que van a utilizar porque es la parte de las suites de cifrado soportadas. Asegura que tanto el cliente como el servidor utilizan la misma versión de la función de derivación de claves y la misma versión del mecanismo de encapsulación de claves. Ahora, el servidor también realiza el paso siguiente. Por lo tanto, ahora ha visto la autenticación de toda la transcripción que el cliente le ha enviado, por lo que verifica la etiqueta en la transcripción que el cliente le está enviando y aborta si falla la verificación de la etiqueta. Mientras que si la verificación de la etiqueta es exitosa, hace lo siguiente: ejecuta un generador de pseudorandom en la llave maestra y deriva cuatro teclas, que son denotadas por kc, kc ’, ks, ks ’. Además, cualquiera que sea la transcripción que el servidor ha visto hasta ahora, lo llamamos transcripción ’ y esto incluye todo lo que el cliente le ha enviado seguido por la autenticación de la transcripción que el cliente ha enviado al servidor. Todo esto lo llamo como transcripción ’ y esta transcripción ’ ahora es autenticada por el servidor utilizando la clave maestra mk y la etiqueta se envía al cliente. Lo que el cliente va a hacer es realizar una verificación en la transcripción ’ utilizando la clave maestra. Si la verificación falla, termina anormalmente, de lo contrario también ejecuta el mismo generador de pseudorandom, que fue ejecutado por el servidor en la clave maestra mk, y deriva las mismas cuatro claves, que el servidor ha generado. Esto completa el protocolo de reconocimiento. Ahora, se puede ver en todo este protocolo de apretón de manos, utilizamos la primitiva clave pública a saber, el mecanismo de encapsulación clave, y junto con eso estamos utilizando la función de derivación de claves y un generador de pseudorandom. Hasta el final del protocolo de reconocimiento, no se han producido las cifraciones reales de los mensajes, que el cliente desea comunicar al servidor. Hasta ahora, sólo ha ocurrido el intercambio de claves y el intercambio de claves sólo invoca el mecanismo de encapsulación clave junto con la función de derivación de claves y el generador de pseudorandom. Ahora, suponiendo que el protocolo de reconocimiento se ejecuta correctamente, tanto el servidor como el cliente tienen ahora dos pares de claves. Siempre que al servidor le gustaría comunicar algo al cliente, ejecuta un esquema de cifrado autenticado utilizando el par de claves ks y ks ’ y podemos utilizar cualquier esquema de cifrado autenticado aquí, digamos el obtenido mediante el uso del cifrado y, a continuación, autenticar el mecanismo. En respuesta cada vez que el cliente desea comunicar algo al servidor, utiliza el otro par de claves, a saber, la clave kc, y la clave kc ‘.Puede recordar que en el enfoque genérico que habíamos visto para construir el esquema de cifrado autenticado, hacemos hincapié en que debe haber una clave independiente para crear una instancia del esquema de cifrado seguro de CPA que está ahí dentro del esquema de cifrado autenticado y debe haber una clave independiente para crear una instancia del componente MAC, que está ahí en el esquema de cifrado autenticado y por eso hay un par de claves, que se utiliza en el esquema de cifrado autenticado. Tenemos un par de claves dedicadas cada vez que el servidor quiere comunicarse con el cliente, y tenemos una clave dedicada cada vez que el cliente quiere comunicarse con el servidor. Ahora puede ver que para hacer la comunicación real entre el cliente y el servidor, estamos utilizando un proceso de cifrado de claves completamente simétrico. (Consulte el tiempo de la diapositiva: 27:45) Para resumir, debemos dar las gracias definitivamente a estos dos geniales personas Diffie y Hellman que pensaron en resolver el problema clave del acuerdo, mientras que el remitente y el receptor que están conectados por un canal seguro a la comunicación pública y todavía pueden llegar a ponerse de acuerdo sobre una clave privada aleatoria común conocida sólo para el remitente y el receptor. Es solo por su visión y debido al trabajo pionero, surgió todo el área de criptografía de clave pública y es así como podríamos pensar en hacer una comunicación segura con cualquier persona desconocida con la que nunca nos hayamos encontrado, con la que nunca hemos compartido ningún tipo de información secreta y podemos hacer convenientemente la comunicación segura con esas personas desconocidas. Por lo tanto, definitivamente debemos agradecer a estas dos personas debido al impacto del trabajo que lo que han hecho, se les concede el premio Turing muy recientemente. Eso es todo para esta conferencia. Así que sólo para resumir en esta conferencia, hemos visto, hemos discutido en un nivel muy alto que tenemos Fiat-Shamir heurística y cómo podemos aplicarlo para convertir cualquier esquema de identificación de tres rondas en un esquema de firma. Lo aplicamos concretamente para el esquema de identificación de Schnorr para obtener el esquema de la firma Schnorr y discutimos una visión general de muy alto nivel del protocolo SSL y un protocolo TLS. Así que, más o menos termina nuestra discusión sobre el problema de la comunicación segura. Ahora, cómo se sabe cómo hacer la comunicación segura entre dos entidades a través de un canal público donde el remitente y el receptor pueden no tener ninguna información precompartida. Para las conferencias restantes, veremos cómo podemos utilizar primitivas criptográficas para diseñar protocolos interactivos donde