Capítulo VI (Final!). Este capítulo fue escrito mientras se escuchaba: The Beatles (2009 Remastered discography).
Buenas! Hoy les traigo la última entrega del taller de Criptografía Asimétrica. La idea es que cuando todos ya estén listos, nos pongamos a crear un algoritmo nuevo. Avisen entonces cuando ya estén, asi podemos ponernos.
Esta entrega va a ser distinta de las demás, estuve trabajando en un código que hace diversos testeos en generadores pseudoaleatorios, con el fin de encontrar fallas en los mismos. Para que un PRNG sea seguro para ser usado en criptografía, debe cumplir con las siguientes normas:
- Tener períodos largos.
- La salida debe tener una distribución uniforme.
- Los espacios entre ciertos valores, no corresponden a los de una distribución aleatoria.
- No debe haber correlación entre los valores sucesivos de la salida.
El programa que creé, prueba todas menos la última, que como vamos a ver más adelante, es una de las más importantes.
NOTA: El programa crea un par de gráficos que muestran la distribución de frecuencias y otro que muestra la distribución de las diferencias. Para esto, van a necesitar un programa llamado Graph. Lo pueden bajar de aquí. Es freeware, asi que no van a tener problemas.
El código está adjuntado al post, es demasiado grande para pegarlo y realmente no confío en rapidshare y similares.
El código utiliza el PRNG que utiliza c++, que es el clásico generador lineal congruencial con distintos parámetros según el compilador. Pero se puede utilizar cualquier prng con solo codearlo en el programa.
Como entrada, el código pide un tamaño de la muestra, que luego va a ser multiplicado por 256, para que sea posible que haya al menos uno de cada uno de los 256 posibles caracteres. Utiliza memoria dinámica para guardar los valores, es claro que tiene un límite este número, si lo exceden, no va a poder asignarlo y a pesar de que tiene un chequeo, probablemente crashee.
Como salida, da algunos datos estadísticos y luego hace unas pruebas aprobadas por el FIPS140-1 para probar aleatoriedad de la muestra. Vamos a verlos uno por uno. Al final de cada medida estadística puse el valor buscado en un PRNG ideal, debemos acercarnos lo más posible a este valor.
Defino antes de empezar un par de conceptos:
Función de distribución: Muestra cuantas veces aparecen cada uno de los valores en un gráfico.
Función de distribución uniforme: Función ideal en la cual todos los valores aparecen la misma cantidad de veces, un PRNG debe aproximarse lo más posible a dicha distribución.
Tamaño de la muestra (n): 256 * x. Siendo "x" el tamaño que el usuario elija. Si esta excede "4000", se toman solo los primeros 4000 * 256 datos. Esto es por el teorema central del límite que dice que si se toman muestras suficientemente grandes, las medidas estadísticas van a ser idénticas con un márgen de error despreciable en comparación con las medidas de la muestra total. Es más que nada para agilizar los cálculos.
Mean, Media o promedio (Xm): Media aritmética estándar. Xm = Sum(xi) / n. Sumatoria de todos los valores dividido la cantidad de valores. Valor buscado = 127,5 (255/2).
Mode, Moda o Modo (Mo): Valor modal, es decir el más repetido de todos. Puede existir más de uno, pero solo se muestra el primero que se encuentra. Valor buscado = No definida, es decir, que no haya un valor que salga más que otros.
Anti-Mode o Anti-Moda (aMo): Probablemente tenga otro nombre que desconozco, pero representa el valor menos repetido en la muestra. Valor buscado = No definida, es decir, que no haya un valor que salga menos que otros.
Standard deviation, desviación estandar o desviación típica(Sx): Es una medida de dispersión que indica que tan distribuidos están los valores a lo largo de los rangos, en este caso, 0-255. Sx = sqrt(Sum((xi - Xm)^2) / n) = sqrt(Sum(xi^2)/n - Xm^2). Valor buscado = 73.9.
Assimetry coefficient o coeficiente de asimetría (As): Determina que tan simétrica es la distribución, si hay valores que se repiten más que otros, va a afectar la simetría. Sin embargo, si el/los valores que se repiten, lo hacen de la misma manera que x+Xm mod 256 siendo "x" el valor, entonces no va a afectar la simetría. El lado que cause la asimetría, es decir, que tenga mayor frecuencia, se denomina "sesgo". Si As > 0, entonces el sesgo está hacia la derecha, si As < 0, el sesgo estará hacia la izquierda. Si As = 0, la distribución será perfectamente simétrica. As = Sum((xi - Xm)^3) / n / Sx^3. Valor buscado = 0, es decir que sea simétrica.
Aquí vemos que el sesgo está hacia la derecha, con un As > 0.
Kurtosis o curtosis (Ks): Determina que tan distantes están distribuidos los valores al rededor de la media. Las distribuciones definidas teóricas, como por ejemplo la Normal, la de Gauss, la de Poisson, la uniforme, etc. Tienen una curtosis esperada.
Ks = Sum((xi - Xm)^4) / n / Sx^4 - 3.
D: Distribución de Laplace. Ks = 3.
S: Distribución secante hiperbólica. Ks = 2
L: Distribución logística. Ks = 1.2
N: Distribución normal. Ks = 0
C: Distribución coseno aumentada. Ks = −0.593762.
W: Distribución de Wagner. Ks = -1.
U: Distribución uniforme. Ks = -1.2.
Valor buscado = -1.2, es decir, uniforme.
Entropy o entropía (Ep): Busca la uniformidad en la muestra, se centra en la repetición de cada uno de los caracteres posibles. Ep = Sum(-fr(i) * log2(fr(i))). Donde fr(i) son las frecuencias relativas, es decir, las veces que se repite "i" sobre "n". Valor buscado = 8.
Deciles D(x): Un decil representa el valor que acumula el x*10% (siendo 0 < x < 10) de la muestra. Es decir, si tenemos un gráfico de una distribución, dividimos verticalmente el gráfico en 10 partes iguales, el valor del eje "x" en donde cae la primera división, es el primer decil, el valor del eje "x" en donde cae la segunda división, es el segundo decil y así sucesivamente. Para calcular, se deben ir sumando las frecuencias de cada uno de los valores, hasta que la siguiente suma supere n/10*x, llamamos entonces el valor de ese valor "i", a la suma de frecuencias la llamamos F(n-1) y la fórmula es: D(x) = i + (x/10 * n - F(n-1)) / f(i).
Valor buscado = x * 25.5.
Buscando estas fallas, el programa busca en la muestra completa primero por una cuestion de eficiencia si hay dos valores consecutivos iguales a los primeros dos valores de la muestra, si estos coinciden, prueba entonces los siguientes 10 valores (esto es modificable cambiando el define PERIOD_SAMPLE) si estos coinciden, comienza a probar toda la muestra. Si la muestra no es lo suficientemente grande como para tener dos períodos completos, entonces da un mensaje de "repetición de período" probable, si puede completar la prueba, entonces da un mensaje de "repetición de período" conclusivo. Por último muestra el tamaño del período en potencias de 2. Valor buscado >= 2^32 (4 Gbytes).
Monobit test (stream y block): Consiste en medir cuantos "1" y cuantos "0" hay en una muestra y sacar una razón. El test se puede aplicar tanto con streams, es decir con el total de la muestra, o con bloques de distintos tamaños, en el programa de 8192 a 16 bits y luego se promedian las razones. En definitiva, se trata de ver si hay uniformidad entre 1s y 0s como habría en una muestra realmente aleatoria. Valores buscados [0.966557 ; 1.035840] para todas las razones. Es posible que para los tests de bloques más pequeños falle el test, es decir que en alguno de los bloques, no haya ni "1" ni "0", esto significa que hay al menos una sucesion de dos o cuatro "255" o "0" y deben ser ignorados, solo en las distribuciones más perfectas esto no ocurre. Si ya falla la de 64 bits, va a fallar luego el "long run test".
Poker test: Analiza de a nibbles (grupo de 4 bits) como si fuesen manos de poker, buscando fallas en la aleatoriedad. Se busca la frecuencia de cada uno de los nibbles (es decir de 0000 a 1111) y luego se aplica esta fórmula: Pt = (16/5000) * SUM(f(i)^2) - 5000.
Valor buscado: 1.03 <= Pt <= 57.4.
Runs test: Analiza cuantas sucesiones de los mismos bits repetidos, ya sean "0" o "1", hay en una muestra. Se deben contar la cantidad de repeticiones de x bits por separado para los "1" y para los "0".
Las repeticiones de más de 6 bits, se cuentan como si fuesen de 6. Piensen que "1" significa que no se repite ni una vez, es decir que si el bit analizado es "0" el siguiente es "1" y viceversa.
Valores buscados:
1 2,267 - 2,733
2 1,079 - 1,421
3 502 - 748
4 223 - 402
5 90 - 223
6+ 90 - 223
Long runs test: Este test es facil y se puede incorporar en el anterior, en definitiva, falla si se encuentra algun bit que se repita más de 33 veces ya sea 0 o 1.
Correlación entre valores sucesivos.
Esto significa que se pueda encontrar una relación entre cada uno de los valores, que permita, teniendo uno de los valores, calcular el siguiente de manera feasible y en tiempo polinómico o cuasi polinómico. El programa no incluye testeos para buscar correlación, entonces puede no detectar ciertos PRNG que en teoría parecen perfectos, pero en la realidad contienen graves fallas.
Prueben por ejemplo modificar el PRNG del programa por lo siguiente:
Este "PRNG" tiene un período de 2^32 y medidas estadísticas cuasi perfectas.
Sin embargo, la sucesión de valores es perfectamente predecible, ya que lo único que hace es sumarle "1" al valor anterior. Los dos "if" sirven para evitar que tenga período corto.
El generador lineal congruencial tiene el mismo problema ya que los parámetros que se utilizan para calcular el siguiente valor, están hardcodeados y varían sólo un poco, con conseguir pocos valores, se podría conseguir rápidamente el siguiente valor de la secuencia. Esto sumado a su período corto, hacen a éste PRNG como potencialmente inseguro.
Fuentes:
http://en.wikipedia.org/wiki/Linear_congruential_generator
http://www.csm.ornl.gov/~dunigan/fips140.txt
http://en.wikipedia.org/wiki/Mersenne_twister
Este es el fin del capítulo VI y el fin de la parte teórica del taller de criptografía asimétrica. Posteen todas las dudas que tengan y cuando estén listos, empezamos a crear.
Un abrazo
APOKLIPTICO
El código bájenlo por acá http://web.i.elhacker.net/archivos/StatisticalAnalysis.rar (Gracias Novlucker!)
Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
Buenas! Hoy les traigo la última entrega del taller de Criptografía Asimétrica. La idea es que cuando todos ya estén listos, nos pongamos a crear un algoritmo nuevo. Avisen entonces cuando ya estén, asi podemos ponernos.
Esta entrega va a ser distinta de las demás, estuve trabajando en un código que hace diversos testeos en generadores pseudoaleatorios, con el fin de encontrar fallas en los mismos. Para que un PRNG sea seguro para ser usado en criptografía, debe cumplir con las siguientes normas:
- Tener períodos largos.
- La salida debe tener una distribución uniforme.
- Los espacios entre ciertos valores, no corresponden a los de una distribución aleatoria.
- No debe haber correlación entre los valores sucesivos de la salida.
El programa que creé, prueba todas menos la última, que como vamos a ver más adelante, es una de las más importantes.
NOTA: El programa crea un par de gráficos que muestran la distribución de frecuencias y otro que muestra la distribución de las diferencias. Para esto, van a necesitar un programa llamado Graph. Lo pueden bajar de aquí. Es freeware, asi que no van a tener problemas.
El código está adjuntado al post, es demasiado grande para pegarlo y realmente no confío en rapidshare y similares.
El código utiliza el PRNG que utiliza c++, que es el clásico generador lineal congruencial con distintos parámetros según el compilador. Pero se puede utilizar cualquier prng con solo codearlo en el programa.
Como entrada, el código pide un tamaño de la muestra, que luego va a ser multiplicado por 256, para que sea posible que haya al menos uno de cada uno de los 256 posibles caracteres. Utiliza memoria dinámica para guardar los valores, es claro que tiene un límite este número, si lo exceden, no va a poder asignarlo y a pesar de que tiene un chequeo, probablemente crashee.
Como salida, da algunos datos estadísticos y luego hace unas pruebas aprobadas por el FIPS140-1 para probar aleatoriedad de la muestra. Vamos a verlos uno por uno. Al final de cada medida estadística puse el valor buscado en un PRNG ideal, debemos acercarnos lo más posible a este valor.
Defino antes de empezar un par de conceptos:
Función de distribución: Muestra cuantas veces aparecen cada uno de los valores en un gráfico.
Función de distribución uniforme: Función ideal en la cual todos los valores aparecen la misma cantidad de veces, un PRNG debe aproximarse lo más posible a dicha distribución.
Medidas estadísticas
Tamaño de la muestra (n): 256 * x. Siendo "x" el tamaño que el usuario elija. Si esta excede "4000", se toman solo los primeros 4000 * 256 datos. Esto es por el teorema central del límite que dice que si se toman muestras suficientemente grandes, las medidas estadísticas van a ser idénticas con un márgen de error despreciable en comparación con las medidas de la muestra total. Es más que nada para agilizar los cálculos.
Mean, Media o promedio (Xm): Media aritmética estándar. Xm = Sum(xi) / n. Sumatoria de todos los valores dividido la cantidad de valores. Valor buscado = 127,5 (255/2).
Mode, Moda o Modo (Mo): Valor modal, es decir el más repetido de todos. Puede existir más de uno, pero solo se muestra el primero que se encuentra. Valor buscado = No definida, es decir, que no haya un valor que salga más que otros.
Anti-Mode o Anti-Moda (aMo): Probablemente tenga otro nombre que desconozco, pero representa el valor menos repetido en la muestra. Valor buscado = No definida, es decir, que no haya un valor que salga menos que otros.
Standard deviation, desviación estandar o desviación típica(Sx): Es una medida de dispersión que indica que tan distribuidos están los valores a lo largo de los rangos, en este caso, 0-255. Sx = sqrt(Sum((xi - Xm)^2) / n) = sqrt(Sum(xi^2)/n - Xm^2). Valor buscado = 73.9.
Assimetry coefficient o coeficiente de asimetría (As): Determina que tan simétrica es la distribución, si hay valores que se repiten más que otros, va a afectar la simetría. Sin embargo, si el/los valores que se repiten, lo hacen de la misma manera que x+Xm mod 256 siendo "x" el valor, entonces no va a afectar la simetría. El lado que cause la asimetría, es decir, que tenga mayor frecuencia, se denomina "sesgo". Si As > 0, entonces el sesgo está hacia la derecha, si As < 0, el sesgo estará hacia la izquierda. Si As = 0, la distribución será perfectamente simétrica. As = Sum((xi - Xm)^3) / n / Sx^3. Valor buscado = 0, es decir que sea simétrica.
Aquí vemos que el sesgo está hacia la derecha, con un As > 0.
Kurtosis o curtosis (Ks): Determina que tan distantes están distribuidos los valores al rededor de la media. Las distribuciones definidas teóricas, como por ejemplo la Normal, la de Gauss, la de Poisson, la uniforme, etc. Tienen una curtosis esperada.
Ks = Sum((xi - Xm)^4) / n / Sx^4 - 3.
D: Distribución de Laplace. Ks = 3.
S: Distribución secante hiperbólica. Ks = 2
L: Distribución logística. Ks = 1.2
N: Distribución normal. Ks = 0
C: Distribución coseno aumentada. Ks = −0.593762.
W: Distribución de Wagner. Ks = -1.
U: Distribución uniforme. Ks = -1.2.
Valor buscado = -1.2, es decir, uniforme.
Entropy o entropía (Ep): Busca la uniformidad en la muestra, se centra en la repetición de cada uno de los caracteres posibles. Ep = Sum(-fr(i) * log2(fr(i))). Donde fr(i) son las frecuencias relativas, es decir, las veces que se repite "i" sobre "n". Valor buscado = 8.
Deciles D(x): Un decil representa el valor que acumula el x*10% (siendo 0 < x < 10) de la muestra. Es decir, si tenemos un gráfico de una distribución, dividimos verticalmente el gráfico en 10 partes iguales, el valor del eje "x" en donde cae la primera división, es el primer decil, el valor del eje "x" en donde cae la segunda división, es el segundo decil y así sucesivamente. Para calcular, se deben ir sumando las frecuencias de cada uno de los valores, hasta que la siguiente suma supere n/10*x, llamamos entonces el valor de ese valor "i", a la suma de frecuencias la llamamos F(n-1) y la fórmula es: D(x) = i + (x/10 * n - F(n-1)) / f(i).
Valor buscado = x * 25.5.
Periodo corto.
Uno de los tests necesarios para un PRNG, es probar que no tenga un período muy corto. Todos los PRNG tienen un período, es decir, un momento en el cual vuelve a empezar la sucesión de dígitos aleatorios. Esto puede ser problemático para un algoritmo criptográfico, ya que si se consigue una parte del PRNG, se puede asumir que va a ser exactamente igual una vez que se reinicie el período. Sin embargo, los buenos PRNG, tienen períodos muy largos, por ejemplo el Mersenne Twister tiene un período de 2^19337 -1, suficiente para cualquier cifrado. Sin embargo, el PRNG que viene por defecto en C++ (linear congruential generator) tiene un período de 2^24 es decir = 16777216 o 16 Mbytes. Si uno usase eso como keystream para cifrar un archivo utilizando xor cuyo tamaño es mayor a 16 Mbytes, con conseguir parte del plaintext, se podrían descifrar otras partes del archivo.Buscando estas fallas, el programa busca en la muestra completa primero por una cuestion de eficiencia si hay dos valores consecutivos iguales a los primeros dos valores de la muestra, si estos coinciden, prueba entonces los siguientes 10 valores (esto es modificable cambiando el define PERIOD_SAMPLE) si estos coinciden, comienza a probar toda la muestra. Si la muestra no es lo suficientemente grande como para tener dos períodos completos, entonces da un mensaje de "repetición de período" probable, si puede completar la prueba, entonces da un mensaje de "repetición de período" conclusivo. Por último muestra el tamaño del período en potencias de 2. Valor buscado >= 2^32 (4 Gbytes).
Pruebas de aleatoriedad FIPS140-1.
Estas pruebas son las estándares creadas por el FIPS, con el fin de determinar si una muestra es lo suficientemente aleatoria. Consiste en cuatro tests: Monobit test (stream y block), poker test, runs test y long run test. Todos estos tests se deben hacer con una muestra de 20000 bits o 2500 bytes. Sin embargo, en el programa utilizo para el monobit test una muestra de 500 bytes aleatoria escojida aleatoriamente, para los demás tests, se utilizan muestras aleatorias de 2500 bytes.Monobit test (stream y block): Consiste en medir cuantos "1" y cuantos "0" hay en una muestra y sacar una razón. El test se puede aplicar tanto con streams, es decir con el total de la muestra, o con bloques de distintos tamaños, en el programa de 8192 a 16 bits y luego se promedian las razones. En definitiva, se trata de ver si hay uniformidad entre 1s y 0s como habría en una muestra realmente aleatoria. Valores buscados [0.966557 ; 1.035840] para todas las razones. Es posible que para los tests de bloques más pequeños falle el test, es decir que en alguno de los bloques, no haya ni "1" ni "0", esto significa que hay al menos una sucesion de dos o cuatro "255" o "0" y deben ser ignorados, solo en las distribuciones más perfectas esto no ocurre. Si ya falla la de 64 bits, va a fallar luego el "long run test".
Poker test: Analiza de a nibbles (grupo de 4 bits) como si fuesen manos de poker, buscando fallas en la aleatoriedad. Se busca la frecuencia de cada uno de los nibbles (es decir de 0000 a 1111) y luego se aplica esta fórmula: Pt = (16/5000) * SUM(f(i)^2) - 5000.
Valor buscado: 1.03 <= Pt <= 57.4.
Runs test: Analiza cuantas sucesiones de los mismos bits repetidos, ya sean "0" o "1", hay en una muestra. Se deben contar la cantidad de repeticiones de x bits por separado para los "1" y para los "0".
Las repeticiones de más de 6 bits, se cuentan como si fuesen de 6. Piensen que "1" significa que no se repite ni una vez, es decir que si el bit analizado es "0" el siguiente es "1" y viceversa.
Valores buscados:
1 2,267 - 2,733
2 1,079 - 1,421
3 502 - 748
4 223 - 402
5 90 - 223
6+ 90 - 223
Long runs test: Este test es facil y se puede incorporar en el anterior, en definitiva, falla si se encuentra algun bit que se repita más de 33 veces ya sea 0 o 1.
Correlación entre valores sucesivos.
Esto significa que se pueda encontrar una relación entre cada uno de los valores, que permita, teniendo uno de los valores, calcular el siguiente de manera feasible y en tiempo polinómico o cuasi polinómico. El programa no incluye testeos para buscar correlación, entonces puede no detectar ciertos PRNG que en teoría parecen perfectos, pero en la realidad contienen graves fallas.
Prueben por ejemplo modificar el PRNG del programa por lo siguiente:
Código (cpp) [Seleccionar]
unsigned long long val = 0;
unsigned long long rnd()
{
val++;
if(val%255 == 0) val++;
if(val%65024 == 0) val++;
return val;
}Este "PRNG" tiene un período de 2^32 y medidas estadísticas cuasi perfectas.
Sin embargo, la sucesión de valores es perfectamente predecible, ya que lo único que hace es sumarle "1" al valor anterior. Los dos "if" sirven para evitar que tenga período corto.
El generador lineal congruencial tiene el mismo problema ya que los parámetros que se utilizan para calcular el siguiente valor, están hardcodeados y varían sólo un poco, con conseguir pocos valores, se podría conseguir rápidamente el siguiente valor de la secuencia. Esto sumado a su período corto, hacen a éste PRNG como potencialmente inseguro.
Fuentes:
http://en.wikipedia.org/wiki/Linear_congruential_generator
http://www.csm.ornl.gov/~dunigan/fips140.txt
http://en.wikipedia.org/wiki/Mersenne_twister
Este es el fin del capítulo VI y el fin de la parte teórica del taller de criptografía asimétrica. Posteen todas las dudas que tengan y cuando estén listos, empezamos a crear.
Un abrazo
APOKLIPTICO
El código bájenlo por acá http://web.i.elhacker.net/archivos/StatisticalAnalysis.rar (Gracias Novlucker!)
Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.