Generadores pseudo-aleatorios | Instanciaciones prácticas | Alison
Loading
Apuntes
Study Reminders
Support
Text Version

Instanciación práctica de los PRG

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 de CryptographyProf. Dr. Ashish Choudhury (ex) Fundación Infosys Fundación de Desarrollo Career ProfessorIndian Institute of Technology-BangaloreLecture-12Practical Instanciations of PRGHello everyone, welcome to conferencia 11. (Consulte Slide Time: 00 30) El plan para esta conferencia es el siguiente. En esta conferencia vamos a discutir acerca de las instanciaciones prácticas de los generadores pseudo-aleatorios, a saber, veremos la construcción basada en el registro de cambios de retroalimentación lineal y RC4 y discutiremos acerca de los desarrollos recientes en el área de instanciaciones prácticas de generador pseudo-aleatorio. La razón por la que llamamos a estas instanciaciones como prácticas es que son super-rápidos, en comparación con las construcciones provablemente seguras de generadores pseudo-aleatorios que habíamos discutido en la última conferencia basada en una función de una manera y una forma de permutación. Sin embargo, desafortunadamente, para estas instanciaciones prácticas de generadores pseudo-aleatorios, no tenemos ninguna prueba matemática de que son realmente pseudo generadores aleatorios. Eso significa que no tenemos la declaración del teorema, lo que demuestra que hey no hay polinomio tiempo distinguido que puede distinguir la salida de este generador de números al azar de la salida de un verdadero generador de números al azar. Es sólo porque desde la construcción de estas instanciaciones prácticas de PRG no hemos encontrado ningún ataque adecuado o cualquier distinción adecuada, creemos que estas construcciones son seguras, mientras que para las construcciones provablemente seguras basadas en la función de una manera y el predicado hardcore que hemos discutido en la última conferencia, tenemos una prueba matemática que De hecho, son seguros en el sentido de que no existe un polinomio de tiempo de distinción para distinguir la salida de esos algoritmos de la salida del correspondiente generador de números aleatorios verdadero. Así que en la práctica, donde quiera que tenga una construcción criptográfica en la que desea crear una instancia de un generador pseudo-aleatorio, realmente vamos para estas instanciaciones prácticas. (Consulte el tiempo de la diapositiva: 02 :08) Así que en todas las instanciaciones prácticas de generadores pseudo-aleatorios, podemos seguir la siguiente abstracción. Imagine que se le da un generador pseudo-aleatorio, que expande una entrada de l-bits a una salida de? -bits. Podemos suponer que el generador pseudo-aleatorio consiste en un par de algoritmos, a saber, un algoritmo de inicialización y el algoritmo GetNextBit. Y lo que básicamente estos algoritmos hacen son los siguientes. Por lo tanto, el algoritmo de Init es en realidad el algoritmo de inicialización que establece el estado inicial de su algoritmo y es una función determinista. ¿Y toma la semilla para el algoritmo? como entrada y junto con un vector de inicialización opcional, por lo que este vector de inicialización es opcional. No es necesario que cada instanciación práctica del generador pseudo-aleatorio tome este vector de inicialización, depende de la construcción.Sin embargo, ¿si el?? se da como una entrada, se conoce públicamente, y se basa en la semilla y??, el algoritmo de inicialización produce un estado inicial del algoritmo que denotamos por? ?0. Ahora, el algoritmo GetNextBit hace lo siguiente. Toma el estado actual de su algoritmo o el PRG, que denotan por? ??, y actualiza el estado a? ?? + 1 y junto con que produce el siguiente bit de salida de su algoritmo?, right.So, si usted quiere generar una secuencia de bits, lo que hacemos es que hacemos el algoritmo de inicialización, obtener el estado inicial??? y decir si usted está interesado en obtener una salida de grandes? -bits, básicamente invocamos este algoritmo GetNextBit? número de veces en secuencia y en cada invocación el estado se actualiza y los bits de salida se mantienen en generar uno por uno. Así que esa es la abstracción que podemos utilizar para abstraer cualquier instrumentación práctica del pseudo generador aleatorio. (Consulte el Tiempo de la diapositiva: 04 :03) Así que veamos, una popularmente utilizada instanciación práctica del generador pseudo-aleatorio, que usamos en el hardware. Y esto se llama registro de cambio de retroalimentación lineal o LFSR. Así que, históricamente, se usó como PRG. Y es muy rápido cuando se implementa en hardware. Sin embargo, no se recomienda ser utilizado para aplicaciones críticas, porque es muy fácil para un adversario recuperar la llave entera por sólo ver pocos bits de salida de la LFSR.So, una LFSR de grado? ¿consisten básicamente en? registros denoted by? 0to?? − 1. ¿Y junto con eso, tendrá? feedback coeficientes? 0to?? − 1, donde los coeficientes serán valores booleanos. Así, por ejemplo, aquí tenemos un LFSR de grado 4 que consta de 4 registros, y los coeficientes de retroalimentación son 0, 1, 0, 1. Por lo tanto, cómo funciona una LFSR. Por lo que se considera el estado de un LFSR, el estado no es más que los valores de bits que se almacenan en el registro individual. Por lo tanto, si tomamos este ejemplo en particular, entonces el estado de la LFSR no es más que una serie de 4 bits, a saber, los 4 bits almacenados en los registros? 3,? 2,? 1 y? 0 y la actualización del estado sucede de la siguiente manera: después de cada ciclo de reloj, el bit que está presente en? 0se va a producir como el bit de salida y el contenido de todos los registros se desplaza a la derecha. Como resultado de eso, ¿qué va a pasar es que la corriente? 1 se convertirá en la siguiente? 0. La actual? 2 se convertirá en la siguiente? 1 y así sucesivamente. ¿Y como resultado? 3 quedará vacío. Y el valor actualizado del último registro, en este caso? 3, se determinará tomando un XOR de los subconjuntos de los bits del estado actual. Y los subconjuntos de los registros cuya XOR tomamos está realmente determinado por el coeficiente de retroalimentación. Así que de nuevo en este ejemplo, ya que los coeficientes de retroalimentación son 0, 1, 0, 1, eso significa, después de cada ciclo de reloj una vez que hacemos el cambio correcto aquí, el valor de? 3, no es nada, sino el XOR de la corriente? 2, y el actual? 0. Si usted toma el XOR que será el valor que será alimentado como el nuevo valor de? 3. Es por ello que el nombre de cambio de opinión lineal de registro. En cada ciclo de reloj, cambiamos el contenido de todos los registros por una posición y es por eso que el registro de turnos. Y la retroalimentación lineal, porque tenemos un bucle de retroalimentación que determina el valor del contenido de?? − 1, en el siguiente ciclo del reloj. Y esta función de retroalimentación es una función lineal del conjunto actual de registros. Es por eso que el nombre del registro de cambio de opinión lineal. (Consultar tiempo de la diapositiva: 06 :54) Así, por ejemplo, si toma este LFSR de grado 4, y supongamos que el estado inicial es 0011, después del primer reloj, todo será cambiado por una posición, y como resultado, el bit 1 va a ser el primer bit de salida y la retroalimentación que va a entrar en el LFSR para la siguiente iteración será 1, es decir, el XOR del bit 0 y 1 porque sus coeficientes de retroalimentación son 0, 1, 0, 1 y como resultado el siguiente estado de la LFSR será 1001.Nuevamente después del siguiente ciclo de reloj, el valor de bit 1 será desechado la salida de prueba; esa será la segunda el bit de salida de su LFSR y la retroalimentación que va a ser será 1 y como resultado su estado será actualizado a 1100 y así sucesivamente. Entonces, así es como una LFSR de grado? (Tiempo de Slide: 07:49) Ahora vamos a discutir si este LFSR es seguro o no, eso significa que podemos considerar que este LFSR es un pseudo generador aleatorio. Y el requisito de un generador pseudo-aleatorio es que si alguien le da la muestra de un LFSR, donde no se le da el estado inicial del algoritmo porque si se le da el estado inicial de la LFSR entonces usted puede realmente calcular todos los bits de salida de LFSR. Por lo tanto, imagina que no se le da el estado de entrada de la LFSR y junto con eso imagina que no se le dan los coeficientes de retroalimentación también pero se le da el grado de la LFSR, que significa, usted sabe el número de registros que se utilizan en la LFSR. Entonces es posible que el atacante calcule o prediga el resultado de LFSR. Resulta que si tenemos un LFSR de grado?, entonces puede tener como mucho 2? − 1 estados no cero. ¿Y por qué estamos interesados en estados que no son cero? Porque una vez que LFSR ocupa el estado, donde el contenido de todos los registros es 0, entonces después de eso no importa cuántas veces o cuánto ciclo de reloj operamos la LFSR.todos los estados posteriores serán 0. Eso significa que una vez que alcancemos un estado totalmente cero, deberíamos dejar de generar las salidas de LFSR. Así que el caso interesante es cuando realmente nos enfocamos en los estados no-cero de LFSR. Definimos LFSR como una longitud máxima LFSR, si la secuencia de salida se repite después de exactamente 2? − 1number of non-zero states. Y curiosamente, resulta que no importa con qué estado de entrada se inicia, si usted comienza con cualquier estado inicial no cero, entonces siempre es posible establecer los coeficientes de retroalimentación de tal manera que su LFSR realmente se convierte en una longitud máxima LFSR.Eso significa comenzar con ese estado inicial no cero, usted puede pasar por todos los 2? − 1 non-zerostates y, a continuación, sólo se repetirá la secuencia. Así que imagínate por el momento que tienes una longitud máxima LFSR. Intuitivamente, usted podría sentir que todas las series de? -bit se van a producir con igual frecuencia, entonces eso significa que su LFSR es un PRG seguro porque si el estado de salida se va a repetir después de 2? − 1 number of states, that means for an atacante, it has to wait for 2? − 1 número de estados, que es una cantidad exponencial de cantidad. Y por lo tanto no puede distinguir la salida de la LFSR de la salida de un generador de números aleatorios verdadero. Esa podría ser su intuición subyacente basada en la cual usted puede declarar su LFSR para ser seguro. Pero resulta que ese no es el caso. Para un LFSR de grado?, sólo observando el número polinomio de bits de salida, (Consulte el tiempo de la diapositiva: 10 :26) un adversario puede recuperar la llave entera y una vez que recupera la llave entera, puede predecir todos los bits de salida futuros del derecho LFSR. Entonces imagínate que te dan un LFSR de grado?, donde no conoces los coeficientes de retroalimentación y no conoces los estados iniciales de LFSR e imagina que el adversario ha observado los primeros 2? Bits de salida del LFSR que denotan por? 1, …,? ?.Y el estado inicial no cero del LFSR se denota mediante la notación (?? − 1 (0), …,? 0 (0)). Así que en esta notación, en el superíndice, estoy poniendo 0 en el paréntesis que denota el estado número 0 de LFSR, a saber, el estado inicial, y que también es desconocido para el atacante, el atacante ha visto sólo el primer 2? bits de salida. También asumimos que el adversario no es consciente de los coeficientes de retroalimentación; desde el punto de vista del adversario, podría ser cualquier subconjunto del? registros que realmente están recibiendo XORed para decidir la retroalimentación. Así que los coeficientes desconocidos?? − 1to? 0 son, por lo tanto, el atacante. Resulta que el adversario conoce la relación que el estado inicial de la LFSR no es más que el primero? bits de salida que ha visto porque si usted ve la operación de la LFSR, después de cada ciclo de reloj, el contenido de? 0está saliendo realmente como la salida y después de cada ciclo de reloj, el nuevo contenido de? 0es en realidad el contenido anterior de? 1, que a su vez es en realidad el anterior? 2 y así sucesivamente. Eso significa que el adversario sabe que el primero? los bits de salida de su LFSR no son nada, sino su estado inicial. Así que esa es la primera pieza de información que ahora está disponible para el adversario, que ahora es una cantidad significativa de información para el adversario. Y resulta que los siguientes bits de salida, a saber?? + 1to? 2?, en realidad da un sistema de ecuaciones lineales en las incógnitas en los coeficientes de retroalimentación al adversario. Es decir, el adversario sabe que el? + 1 ?h bit output?? + 1is nothing, but? 0?1 spile ?1?2 &help… ¿Qué??? − 1 ??. De la misma manera, el bit de salida de 2 ??h satisface la relación? 2? =? 0??waters ?1?? + 1, … ¿Desea? − 1 ?2? − 1. ¿Entonces el adversario consigue un sistema de? ¿ecuaciones independientes? variables. Y al resolverlos, puede recuperar por completo los coeficientes de retroalimentación. Así que ahora tanto las llaves como los coeficientes de retroalimentación son conocidos por el adversario.Y por lo tanto puede determinar completamente todas las salidas posteriores de su LFSR. Eso significa sólo observando 2? bits de salida del LFSR, el adversario puede romper completamente esta LFSR. Y por lo tanto, de ninguna manera, en realidad es un pseudo generador aleatorio. (Consultar Tiempo de Slide: 13 :27) Así que un método que se utiliza para preservar la seguridad de la LFSR es añadir algún tipo de linealidad. Si usted ve el ataque, o la estrategia, que es utilizado por el atacante aquí es para explorar el sistema de la ecuación lineal, o es decir, el atacante utiliza el hecho de que la retroalimentación es en realidad una función lineal del subconjunto del registro. Así que una manera de sortear esto es añadir algún tipo de linealidad no? en el registro de cambio de opinión. Y hay varias maneras de introducir la no linealidad en la construcción del registro de cambio de retroalimentación lineal. El primer método para agregar la no linealidad es hacer que su propia retroalimentación sea no lineal. A saber, lo que suponemos aquí es que el contenido del? ?hregister en el ciclo del reloj? + 1 será el contenido del? + 1 ?hregistrarse en el ciclo del reloj?, eso significa que todo sigue siendo cambiado por una posición después de cada ciclo de reloj. Pero el contenido del último registro es ahora una función no lineal de los registros actuales. Entonces, en la construcción anterior en la LFSR, ¿la función? era en realidad una función lineal. Pero la propuesta aquí es que en lugar de asegurar que la retroalimentación es una función lineal, la retroalimentación ahora va a ser una función no lineal del conjunto de bits que están ahí en el registro actual. Por lo tanto, esa es una forma de agregar la no linealidad que se sigue en las construcciones modernas de generadores pseudo aleatorios basados en registros de cambio de retroalimentación. La otra manera de agregar la no linealidad es agregar la no linealidad en la salida en sí. Así que hasta ahora estamos discutiendo el caso donde la salida es en realidad el contenido de la corriente? 0, donde? 0es el valor de? 1en el ciclo de reloj anterior y así sucesivamente y cada ciclo de reloj todo se cambia por una posición. Pero podría tener otra manera de determinar la salida, donde la salida es en realidad una función no lineal. Y hay 2 maneras de determinar los generadores de combinación no lineal. La variante uno es la siguiente: todavía utilizamos el LFSR único, donde todo se cambia por una posición y tenemos una retroalimentación lineal. Pero en lugar de asegurarse de que? 0es el bit de salida, el bit de salida resulta ser una función no lineal de los registros actuales. Y la variante dos es, en lugar de usar una LFSR, ahora tendremos varias LFSR, preferiblemente de diferentes grados. Y el bit de salida global del LFSR combado será una función no lineal complicada de la salida de los LFSRs individuales. Así que es la segunda variant.Así que, eso significa añadir no linealidad que tiene 2 opciones, la no linealidad en la retroalimentación y la no linealidad en la salida, donde la no linealidad en la salida se puede lograr de 2 maneras. Basta con utilizar 1 LFSR, siendo la salida una función no lineal complicada y la opción dos es utilizar varios LFSR, siendo la salida una función no lineal complicada de la salida de los LFSRs individuales. (Consultar Tiempo de Slide: 16 :31) Y resulta que las construcciones modernas de PRG basadas en LFSR utilizan de hecho estos principios. Así que aquí está una construcción candidata basada en LFSR, que se llama Trivium. Y es una instanciación muy popular de pseudo generador aleatorio. Si ves pictorialmente, en realidad es una combinación de 3 registros de turnos de retroalimentación. Así que usted tiene el primer LFSR que consta de 93 registros, que denotamos como el registro de cambio de opinión A. Entonces usted tiene el siguiente LFSR, que denotineas B que consta de 84 registros. Y luego tenemos los siguientes registros de turno de retroalimentación C, que consta de 111 registros. Ahora, la razón por la que está usando 93, 84, 111 no son claramente conocidos; son el principio de diseño utilizado por los diseñadores del trivium. Sin embargo, hay algunos principios bien conocidos que se utilizan para seleccionar el valor de FSR A, FSR B, FSR C así. Pero de lo contrario en general no hay directrices fijas que se utilizan para seleccionar el tamaño de FSR A, FSR B, FSR C para ser así. Y ahora, verá que cada FSR tiene una salida individual. Por lo tanto, si considero la salida de FSR A, por lo tanto, es básicamente el XOR del registro más a la derecha, en este caso, el 93º registro y otro registro de la misma FSR. Así que esta es la primera diferencia en la construcción de Trivium en comparación con la LFSR.En la LFSR regular, la salida 93, el contenido del registro número 93 será considerado como el bit de salida después de cada ciclo de reloj. Pero ahora después de cada ciclo de reloj, es el XOR del registro número 93 y un registro de 66 ?en el FSR A, que será considerado como la salida de la FSR A después de los ciclos de reloj individuales. Y lo mismo sostiene para el FSR B, así como el FSR C. Esa es la primera manera de agregar la no linealidad aquí. Y la salida general de la FSR es básicamente el XOR de la salida de la FSR A, FSR B, FSR C. Así que esa es la segunda manera de agregar la no linealidad aquí. En cuanto a la retroalimentación se considera aquí, si se ve por ejemplo, el FSR A aquí, ¿ahora qué va como el feedback? Así que la retroalimentación no es más que básicamente una función de uno de los registros en la misma FSR y un subconjunto de registros de la FSR por encima de él. Así que lo que quiero decir “ por encima de ello ” aquí es lo siguiente: como dije la secuencia de los primeros 93 registros es el FSR A y el siguiente registro de 84 es FSR B y el siguiente registro 1011 es FSR C. Se puede imaginar esta construcción como algún tipo de construcción circular, donde por encima de la FSR A, tenemos la FSR C, por encima de la FSR B tenemos la FSR A y por encima de la FSR C tenemos la FSR B. Eso es lo que quiero decir por “ arriba ” en este contexto. Y la retroalimentación de la FSR A es básicamente una XOR de uno de los registros de la FSR A, junto con algunos de los registros de la FSR C. De la misma manera, la retroalimentación de la FSR B es una XOR de algunos de los registro de la FSR B junto con algunos de los registros en la FSR A, y de la misma manera la retroalimentación para el FSR C es una XOR de algunos de los registros de la FSR C junto con algunos de los registros en la FSR B. Así es como estamos introduciendo la no linealidad. Entonces, la idea aquí es haciendo esta construcción complicada, estamos realmente eliminando completamente la linealidad que estaba presente en la construcción original de la LFSR. Y así es como está diseñado el Trivium. Y esto se considera un PRG seguro porque, después del desarrollo de esta construcción, no hemos conseguido ningún ataque práctico. Eso significa que no se ha reportado ningún algoritmo de tiempo polinómico, que en realidad puede predecir el resultado del trivium si no se conoce el estado inicial del trivium. Por lo tanto, no voy a entrar en los detalles completos de la construcción, qué principios de diseño se utilizan, por qué los 3 FSRs utilizados, sus grados se construyen como este y así sucesivamente. Si quieres saber más sobre los detalles de tales construcciones puedes referirnos a cualquiera de las referencias que estamos siguiendo en este curso. (Consultar Tiempo de Slide: 20 :56) Ahora consideraremos otra instanciación popular de pseudo generador aleatorio, es decir, RC4 que es súper rápido cuando se implementa en software. Y a pesar de que fue muy popular tillalgunos años atrás, recientemente se han reportado varias vulnerabilidades. Y por eso ya no se recomienda su uso para fines críticos. De hecho, se utilizó como uno de los estándares en WEP.Y después de que se reportaran vulnerabilidades en RC4 ya no se usa en la norma. Por lo tanto, recuerde que cualquier instanciación práctica de un generador pseudo aleatorio consta de 2 algoritmos, a saber, un algoritmo de inicialización y un algoritmo de actualización de estado. Y en el algoritmo de inicialización, el estado se inicializa y dentro del algoritmo de actualización de estado, se actualiza el estado y se generan los bits de salida siguientes. Por lo tanto, en lo que respecta al estado en RC4, el estado consiste básicamente en una matriz, que consta de 256 bytes. Y a lo largo del algoritmo, se garantizará que estos 256 bytes en realidad consisten en una permutación del conjunto 0 a 255. Esto significa que cada uno de los valores de 0 a 255 se producirá como uno de los bytes entre estos 256 bytes. Y por eso es una permutación del set 0 a 255.Ahora el algoritmo de inicialización para este RC4 es el siguiente. El algoritmo de inicialización crea una permutación pseudoaleatoria dependiente de clave del conjunto 0 a 255. ¿Y junto con eso, inicializar punteros 2index? y? en el rango de 0 a 255. Esa es la forma en que se produce la inicialización para RC4, vamos a entrar en los detalles de la inicialización muy pronto. Y una vez que se ha realizado la inicialización, en el algoritmo de actualización de estado en cada iteración los bytes del?, que son en realidad una permutación pseudoaleatoria dependiente clave del conjunto 0 a 255 se barajan alrededor, y después de barajar uno de los bytes es la salida, es decir, la forma en que se actualiza el estado. (Consulte Tiempo de diapositiva: 23 :02) Así que ahora vamos a entrar en los detalles del algoritmo de inicialización. Por lo tanto, la clave o la semilla para el algoritmo RC4algorithm es básicamente una clave de 16 bytes, que va a ser una clave aleatoria de 16 bytes. Así que denotamos itby? 0to? 15. Y la salida va a ser una pseudo permutación aleatoria del conjunto 0 a 255. Entonces, ¿esa será la matriz?. ¿Así que inicializamos la matriz? consta de valores de 0 a 255 en sequence.Namely, el primer byte se establece en 0. El siguiente byte se establece en 1 y se dice que el último byte es el valor 255. Esta es una permutación de identidad. Y ahora tenemos que algunos cómo reorganizar el contenido de la matriz? basado en el valor de la matriz de claves?. Eso significa que dependiendo del contenido de los bytes clave, tenemos que barajar el contenido de la matriz?, asegurando que después de barajar, el modificado? sigue representando una permutación del conjunto 0 a 255.Así que para hacerlo, en realidad repetimos los valores de la clave y nos aseguramos de que la matriz de claves se convierte en tamaño 255. Y esto se hace realizando la operación,? [?] =? [? mod 16], eso significa que tomamos los primeros 16 bytes, y lo repetimos una y otra vez, para asegurar que ahora tenemos una matriz de claves expandida de tamaño 256. Esa es la forma en que hacemos la expansión clave. ¿Y entonces establecemos el puntero de índice inicial? para ser 0. ¿Y una vez el puntero? se establece en 0, para las siguientes 256 iteraciones, hacemos lo siguiente. Hacemos el barajado y para hacer el barajado, en realidad cambiamos el valor de? Como esto: ¿nos ponemos? a ser la suma de la corriente? y el contenido actual del byte? ?h de? y el byte de clave? ?h. A saber,? =? +? [?] +? [?]. Y una vez que tenemos el índice actualizado?, intercambiamos el contenido de? [?] y? [?]. Así es como hacemos el cambio. Entonces, intuitivamente lo que se puede imaginar aquí es que en cada iteración, el índice? se incrementa en 1. ¿Y en cada iteración el índice? se baraja aleatoriamente, dependiendo del byte de las teclas. ¿Y una vez el puntero? se actualiza, vamos a esa ubicación en la matriz? .Y cambiar el contenido? [?] con el contenido de esa ubicación. Así es como realmente generamos una permutación pseudo-aleatoria dependiente de la clave de?. ¿Por qué se trata de una permutación pseudoaleatoria dependiente de clave? es porque en cada iteración, el valor de? depende del contenido de la matriz de claves. Ese ’ s cómo la permutación resultante es una permutación dependiente de la clave. (Consulte Tiempo de Slide: 26 :01) Ahora una vez que el estado se ha inicializado, vamos al algoritmo de actualización y salida del estado. Por lo tanto, en el algoritmo de actualización de estado, en cada invocación, el contenido actual del? se barajará alrededor y uno de los bytes va a ser la salida. Por lo tanto, la forma en que se genera es la siguiente. ¿Imagina que tenemos la corriente? ¿y la corriente?, ¿qué hacemos es que incrementamos el valor de?. ¿Y entonces decidimos al azar el valor de?, dependiendo del contenido actual de? como sigue: Entonces, ¿el valor de? se actualiza de forma pseudo-aleatoria estableciendo:? ¿(?) +? [?]) mod 256. Eso significa que cualquiera sea el índice actual de?, a eso agregamos el valor de byte que se almacena en el? ?hlocation de la matriz?, y para asegurar que hacemos el wraparound, todas las operaciones se hacen modulares 256. Por lo tanto, al hacer esta operación actualizamos el valor del contador de índices? de una manera pseudo? aleatoria. Y entonces lo que hacemos es, intercambiamos el contenido de? ?hlocation de array? y? ?hubicación de la matriz?. Así es como hacemos realmente la actualización del estado. Para determinar la salida, lo que hacemos es determinar un nuevo índice?, que no es otra cosa que la suma de los contenidos del? ?hlocation de la matriz? y el? ?hlocation de la matriz? .Es decir,? (? [?] +? [?]) mod 256 Y vamos a esa ubicación, que es el? ?hlocation y lo que sea el valor de byte que se almacena allí, que es el valor de byte que vamos a la salida. (Consulte el apartado Tiempo de la diapositiva: 27 :46) Así que ahora vamos a discutir sobre la seguridad del algoritmo RC4. Así que si ves el pseudocódigo del algoritmo de actualización y algoritmo de inicialización del estado, puedes ver que no estamos haciendo ninguna operación complicada. Por eso este algoritmo es súper rápido cuando lo implementas en software. Y por eso fue muy popular. Entonces la gente empezó a reportar vulnerabilidades en la seguridad de RC4. Por lo tanto, queremos analizar aquí si de hecho RC4 es un candidato pseudo-aleatorio generador de números o no. Por lo tanto, si recuerda, en cada modificación de la actualización de estado, RC4 produce un byte. Por lo tanto, tenemos que comparar el algoritmo del generador de bytes RC4 con un verdadero algoritmo de generador de bytes aleatorios. Un verdadero algoritmo de generador de bytes aleatorios producirá cualquier byte en el conjunto de 0 a 255, de forma uniforme al azar. Y el resultado esperado de RC4 es que en cada invocación del algoritmo de actualización de estado, el byte de salida podría ser casi como un valor aleatorio uniforme del conjunto de 0 a 255. Resulta que en una de las obras anteriores, Mantín y Shamir mostraron que incluso si asumimos que la inicialización del algoritmo de la RC4 es una inicialización uniforme (eso significa que no depende del algoritmo clave), si empezamos a ejecutar el algoritmo de actualización de estado, entonces el segundo byte de salida de RC4 es más probable que sea 0 que significa, la probabilidad de que el segundo byte de salida de RC4is 0 sea 2256, en comparación con 1256. Y esto se puede demostrar formalmente. Por lo tanto, si quieres ver los detalles formales exactos de que cómo se deriva exactamente esta probabilidad puedes referirnos a una de las referencias que estamos siguiendo. Por lo tanto, suponiendo que este es el caso, aquí hay un RC4distinguisher muy simple que puede distinguir aparte un byte de ejemplo generado por el generador de bytes RC4, de una muestra que es generada por un generador de bytes realmente aleatorio. Así que imagine que el distinguidor se le da una muestra?, y tiene que determinar si es producido por el generador de bytes RC4 o por un generador de bytes aleatorios. Así que lo que hace el distinguidor, ya que sabe el resultado de Mantín y Shamir, sólo comprueba el segundo byte de?, y luego si el segundo byte de? resulta ser 0, entonces etiqueta que la muestra? es generado por el generador de bytes RC4. De lo contrario, etiqueta la muestra? para ser generado por una salida realmente aleatoria. Ahora vamos a calcular la ventaja distintiva del distinguido que hemos diseñado. Si de hecho la muestra? que es una secuencia de bytes es generada por el RC4 por el generador se le da al distinguidor entonces la probabilidad de que de hecho el segundo byte es 0 es 2256. Por lo tanto, la probabilidad de que nuestro distinguido cuando se le da una muestra aleatoria generada por el generador de bytes RC4 la etiqueta como el resultado de RC4 es 2256. Mientras que si la secuencia de bytes es generada por un generador de bytes realmente aleatorio se le da al distinguidor, que la probabilidad de que su segundo byte es 0 es en realidad de 1 sobre 256. Eso significa en ese caso sólo, con esa gran probabilidad sólo, nuestro distinguidor terminará etiquetando una verdadera secuencia aleatoria de bytes para ser un resultado de un RC4. Entonces, ¿cuál es la ventaja distintiva del atacante en este caso? Pues bien, la diferencia absoluta es 1256, lo cual es una probabilidad significativa. Eso significa que ya no podemos afirmar que la secuencia de bytes generados por el generador de bytes RC4 está cerca de la secuencia de bytes, que un generador de bytes realmente aleatorio habría producido y es por eso que este RC4 ya no es considerado como seguro. Para concluir, en esta conferencia hemos visto en un nivel muy alto algunas de las instanciaciones prácticas de pseudo generador aleatorio. Entonces hemos visto una construcción basada en hardware, a la que llamamos como el registro de cambio de retroalimentación lineal. El registro de cambio de opinión lineal original ya no se utiliza en la forma que se propuso, ya que al observar el número polinómico de salidas, un adversario puede averiguar todo el estado, así como los coeficientes de retroalimentación y por lo tanto obtener puede predecir todos los bits de salida subsiguientes de LFSR. Entonces es por eso que las instanciaciones modernas de generadores pseudo-aleatorios basados en el registro de cambio de retroalimentación introducen algún tipo de no linealidad que puede ser hecho por varias maneras, tales como la no linealidad en la forma de coeficientes de retroalimentación no lineales, bits de salida no lineal y así sucesivamente. También discutimos una construcción llamada Trivium, basada en ese principio, y una segunda construcción que vimos es la construcción de software que puede ser implementada en software y es super? rápido, es decir RC4. Desafortunadamente, también vimos algunas de las vulnerabilidades que se han reportado en RC4 debido a las cuales ya no se recomienda su uso.

Notification
You have received a new notification
Click here to view them all