Juego para aprender acerca de los ataques XSS

Juego XSS

Página de presentación

XSS son las iniciales de Cross-Site Scripting. Se trata de una vulnerabilidad que puede tener una aplicación web y que explotada permite a un atacante inyectar código del lado cliente, generalmente Javascript, en la misma. Con ese código el atacante pretende conseguir varios objetivos ilícitos. El más peligroso de ellos sería hacerse con la sesión del usuario en el sitio.

Esto sólo es posible si la aplicación no transforma adecuadamente los datos que los usuarios pueden introducir o no los sanea antes de volverlos a mostrar. El programador debe decidirse por una de las dos opciones en función del tipo de datos que espera, pues según qué datos podrían verse alterados si se sanea la entrada.

Que una aplicación tenga en un punto, o en varios, esta vulnerabilidad pues ser debido a razones como:

  • El programador no sabe proteger su aplicación de estos ataques.
  • Fecha de entrega del producto demasiado ajustada o cambios de última hora.
  • Cambios sobre cambios que agotan la energía del programador.

Sobre aspectos como los factores humanos o funcionamiento de la empresa poco puede hacer el programador pero sobre el primer punto llega Google al rescate. Esta empresa ha sacado un juego, más orientado a desarrolladores que a crackers, para que aprendan acerca de las diferentes técnicas que los malos tienen a su disposición. El juego se presenta en forma de niveles y es bastante instructivo. Aquí tienes el enlace si quieres jugar.

Esto no es por amor al arte. Los de Mountain View pagarán hasta 7500$ a quien encuentre y reporte una vulnerabilidad de este tipo en cualquier aplicación de Google.

Un algoritmo de generación de números pseudoaleatorios

En la nota a pie del artículo La privacidad no existe citaba un artículo de la Wikipedia acerca de cómo generar números aleatorios mediante software. En esta entrada voy a poner un ejemplo sencillo desarrollado en Python. Obviamente Python tiene sus propias funciones para ello, pero nada nos impide desarrollar nuestra propia función.

En primer lugar veamos la teoría que hay detrás. Estos algoritmos lo que realmente generan son números pseudoaleatorios porque usan procedimientos sistemáticos. El método más empleado es el de congruencia lineal. Se eligen cuatro números enteros: un módulo m, un multiplicador a, el incremento c y la semilla x0 Estos números deben ser números enteros positivos mayores de 0. El artículo de la Wikipedia también impone que  a, c y x0 deben ser menores que m pero no encuentro ninguna razón para ello. De hecho, al final el artículo entra en contradicción al afirmar que el estándar POSIX para C define a = 1103515245 y m = 32768 Con lo que a > m

Una semilla válida la podemos obtener del reloj interno de la CPU: el RTC. En el ejemplo usaré el método time() de la librería time. Éste nos da el tiempo que ha pasado desde el tiempo Unix: el 1 de Enero de 1970. Como se puede ver, devuelve un número en coma flotante:

>>> time.time()
1487416084.126488

Como necesitamos un entero lo convertimos, el número de segundos será suficiente para el ejemplo.

Siguiendo con la teoría, la semilla nos dará el primer número aleatorio y este mismo número será la semilla para el siguiente. Partiendo de una semilla inicial xn sería:

xn+1 = (axn + c) mod m

Como a, c y m usaré los valores del estándar Posix para C. Este programa genera 10 números aleatorios:

import time

xn = int(time.time()) #Semilla

for i in range(10):
    xn1 = (1103515245 * xn + 12345) % 32768
    print(xn1)
    xn = xn1

Si lo ejecuto este es el resultado:

13566
9311
7852
10101
8970
10107
31128
17905
26070
16471

Lo ejecuto otra vez lo más rápidamente posible:

875
16072
23393
9862
27463
32628
19613
9490
29923
7904

Como vemos hay bastante aleatoriedad. Suficiente para videojuegos y modelos de simulación. Aunque entre ambas ejecuciones sólo pase un segundo los resultados no tienen nada que ver. Si necesitamos diferentes ejecuciones en menos de un segundo podríamos crear un entero fruto de la concatenación de la parte entera y la parte decimal del número que devuelve time()

Llegará un momento en que el resultado obtenido coincida con alguno de los resultados ya obtenidos. Cuando eso pase sabremos que la serie ha acabado y a continuación se repetirán los mismos números. Veámoslo usando unos valores más pequeños: m = 7, a = 5, c = 3 y x0 = 2:

x1 = 5x0 + 3 = 5*2 + 3 = 13 mod 7 = 6
x2 = 5x1 + 3 = 5*6 + 3 = 33 mod 7 = 5
x3 = 5x2 + 3 = 5*5 + 3 = 28 mod 7 = 0
x4 = 5x3 + 3 = 5*0 + 3 = 3 mod 7 = 3
x5 = 5x4 + 3 = 5*3 + 3 = 18 mod 7 = 4
x6 = 5x5 + 3 = 5*4 + 3 = 23 mod 7 = 2
x7 = 5x6 + 3 = 5*2 + 3 = 13 mod 7 = 6

Por lo tanto la serie que se repetirá ad infinitum es: 6, 5, 0, 3, 4, 2, …

De hecho, podríamos decir que la serie empieza por el 2, pues ya x6 = x0. Ahí tenemos la primera coincidencia, antes de llegar a x7 En el algoritmo en Python no se muestra x0 para no tener el primer número pseudoaleatorio de la serie demasiado parecido en diferentes ejecuciones.

En el mejor de los casos posibles el número de elementos de la serie será igual a m. Una mala elección de los valores iniciales m, c y x0 conduciría a una serie muy corta. Según el teorema de Hull-Dobell un generador congruencial tiene una secuencia completa (el número de elementos es igual a m) si y solo si:

  1. m y c son primos entre si.
  2. a -1 es divisible por todos los factores primos de m.
  3. Si 4 divide a m, entonces 4 divide a a – 1.

Además, los algoritmos más eficientes escogerán como m una potencia de 2, pues la operación módulo podrá ser calculada simplemente truncando los 32 o 64 bits más a la derecha.

El estándar POSIX para C ha escogido cuidadosamente los valores cumpliendo con las condiciones del teorema de Hull-Dobell. Veamos:

  1. 1103515245 y 32768 son primos entre si.
  2. El único factor primo de 32768 es 2: 32768 = 215 y 1103515244 | 2 Además es eficiente al ser potencia de 2.
  3. Se cumple tanto 32768 | 4 como 1103515244 | 4

Por lo tanto el algoritmo anterior debería dar una serie 32768 números únicos. Veamos si es cierto con una sencilla modificación del programa anterior que irá añadiendo números a la tupla hasta que se produzca la primera repetición:

import time

xn = int(time.time())
total = []
repeated = False

while (not repeated):
    xn1 = (1103515245 * xn + 12345) % 32768
    xn = xn1
    repeated = xn1 in total
    if (not repeated):
        total.append(xn1)
    
print(total)
print(len(total))

No voy a mostrar la tupla resultante por ser demasiado larga, será bastante con ver el número de elementos que la componen (segundo print):

32768

El número de elementos de la tupla resultante siempre será el mismo por más veces que lo ejecutemos.

Si necesitamos números aleatorios entre 0 y 1 haríamos xn / m :

xn = int(time.time())

for i in range(10):
    xn1 = ((1103515245 * xn + 12345) % 32768) / 32768.00
    print(xn1)
    xn = xn1

Los dos decimales .00 añadidos a c son un “truco” para que Python imprima el resultado xn con decimales: le estamos diciendo al intérprete que queremos un float como resultado de la división. Este es uno de los resultados que da su ejecución:

0.654296875
0.87919062376
0.538866591363
0.578234577039
0.358640995601
0.190647192963
0.728419539036
0.0794397516329
0.638488339469
0.501262168

La operación módulo en teoría de números y cómo la implementan diferentes lenguajes

En informática, la operación módulo, dados dos números, D el dividendo y d el divisor, nos da el resto r de la división entera de D por d, siendo d≠0 y |r|<|d|. Aunque no parece gran cosa, aun menos teniendo en cuenta que hace décadas que las CPUs incorporan coprocesadores matemáticos capaces de hacer a gran velocidad operaciones aparentemente más relevantes como raíces o logaritmos, la realidad es que es una operación fundamental en informática. Desde la generación de tablas de hash y números aleatorios hasta la criptografía y la generación de checksums. Incluso ciertas operaciones aritméticas y lógicas, a nivel interno el ordenador las resuelve con aritmética modular, por ejemplo XOR es el resultado del módulo 2 (10 en binario) de la suma de dos bits.

Veamos como Python resuelve esta operación. Abrimos la consola de Python y mediante el operador % le pedimos el módulo con D=27 y d=13:

>>> 27%13
 1

Así es: 27 = 13 * 2 + 1

Lo mismo nos devuelve PHP:

echo 27%13;
1

Nada nuevo bajo el sol, matemáticas básicas. Probemos esto ahora:

>>> -27%13
12

Así es: -27 = 13 * (-3) + 12

Cambiando los signos de D y d:

>>> 27%-13
-12

¡¿Comorll?!?

El resultado esperado es 1:

27 = -13 * (-2) + 1

¿Por qué da -12? ¿Y PHP qué opina de todo esto?

echo 27%-13;
1

Buen chico. ¿Será que un lenguaje tan usado y prestigioso como Python no sabe dividir? ¿Por qué entonces lo escogen en tantas facultades de todo el mundo para la enseñanza? La NASA también lo usa, ¿han escogido un lenguaje que no sabe ni calcular el resto de una división entera?

Siguiendo con PHP:

echo -27%13;
-1

Habíamos visto antes que el resultado era 12 ¿PHP anda también perdido? La definición de la Wikipedia tampoco ayuda a esclarecer que está pasando. En mi opinión, esa definición es inexacta pues dice que la operación módulo calcula el resto de la división euclídea y en la división euclídea se impone la condición r ≥ 0 Cuando no se impone esa condición, y no lo hice en la definición de la operación módulo que di al iniciar esta entrada, las divisiones tendrán dos cocientes y dos residuos posibles: por defecto y por exceso. Mientras que con r ≥ 0 sólo habrá un resultado posible. Si hay un cociente q habrá otro cociente q’ cuyo valor será q + 1 y cada cociente tendrá su respectivo residuo r y r’ Con D=-27 y d=13 tendremos q=-3 y r=12 por un lado y por otro q=-2 y r=-1

-27 = 13 * (-3) + 12

-27 = 13 * (-2) + (-1)

Por lo tanto ambos lenguajes están calculando correctamente. En teoría de números siempre se escoge r ≥ 0 y algunos lenguajes, como Pascal, Scheme o Stata así lo hacen también, para estos lenguajes sí aplica la definición de la Wikipedia, pero la mayoría y los más usados van a escoger la división por exceso o por defecto. Algunos, como PHP, C o C++ escogerán siempre para el resto el signo del dividendo D mientras que otros como Python o Mathematica el del divisor d. Aparentemente para conseguir esta igualdad de signo, usarán la división por exceso o por defecto según sea necesario, aunque lo que realmente hacen es una operación más rápida. Los que usan el mismo signo que el dividendo van realmente rápido, truncan la división:

r = D – d * truncar(D / d)

La función truncar simplemente extermina todos los decimales, o dicho más fino: se redondea al número entero inmediato más cercano a 0. Esto es lo que hace PHP o C:

-1 = -27 – [13*truncar(-27 / 13)] = -27 – [13*truncar(-2.07…)] = -27 – [13*(-2)] = -27 – (-26)

Por otro lado, los que usan el signo del divisor d, usan la función floor (suelo). Esta función proporciona el número entero más pequeño inmediato o igual al número que se le pasa. De manera que por ejemplo Π quedaría en 3 y -Π en -4. Está función se expresa mediante ⌊⌋: floor(x) = ⌊x⌋

r = D – d * ⌊D / d⌋

Esto es lo que Python hace:

12 = -27 – 13[⌊-27 / 13⌋] = -27 – 13[⌊-2.07…⌋] = -27 -13[-3] = -27 + 39

Con la primera extrañeza que nos encontramos, cuando pusimos un divisor negativo, ahora sabemos qué hace Python:

-12 = 27 – (-13)*[⌊27 / -13⌋] = 27 – (-13)⌊-2.07…⌋ = 27 – (-13)*(-3) = 27 – 39

Lenguajes respetuosos con la teoría, como Pascal, hacen esto:

Si d > 0 => q = ⌊D / d⌋

Si d < 0 => q = ⌈D / d⌉

Es decir, si el divisor es negativo usan la función ceiling (techo) Dicha función da el número entero más grande inmediato o igual al número que se le pasa. De manera que Π quedaría en 4 y -Π en -3. Está función se expresa mediante ⌈⌉: ceiling(x) =⌈x⌉

Hay que tener en cuenta que no es esto lo que hacen los lenguajes que cogen el signo del divisor, es decir, no es lo mismo ⌊x⌋ que truncar(), no en el caso de números negativos. Volviendo al ejemplo D = 27 y d = -13 que en Python dio r = -12 mientras que PHP r = 1:

-12 ≠ 27 – (-13*⌈27 / -13⌉) = 27 – (-13*(-2)) = 27 – 26 = 1

Es lo que nos devolvió PHP, porque para números negativos truncar(x) equivale a ⌈x⌉ Para los positivos, en cambio, truncar(x) equivale a ⌊x⌋, por eso para D y d positivos todo lenguaje da el mismo r. Las diferencias surgen con los negativos. Veamos el caso en que ambos son negativos, D = -27 y d = -13. PHP usa truncar(), que en este caso sí equivale a ⌈⌉ :

-27 – (-13* truncar(-27 / -13) = -27 – (-13*truncar(2.07)) = -27 – (-13*2) = -27 + 26 = -1

>>> -27%-13
-1
echo -27%-13;
-1

Mientras que ⌊⌋, que ningún lenguaje la usa, daría:

-27 – (-13*⌊-27 / -13⌋) = -27 – (-13*(⌊2.07⌋) = -27 – (-13)*3 = -27 + 39 = 12

Como q = (D – r) / d Acaba resultando una ecuación sin solución entera:

(-27 – 12) / -13

Por lo tanto r ≠ 12

En la definición de división entera que di al principio introduje una “trampa” para que los resultados de PHP, Python o C fueran correctos: añadí la condición |r|<|d| En teoría de números, la división entera se define sólo para el conjunto de los naturales y la única condición es d ≠ 0 En cambio, para el conjunto de los números enteros (que incluye los naturales más los negativos), se usa la división euclídea, la cual añade la condición r ≥ 0 con el objetivo de obtener unos q y r únicos.

En mi opinión, la razón principal por la que algunos lenguajes usan la división entera también para números negativos es obtener un conjunto de r más amplio. Sin la condición r ≥ 0 se obtienen también r negativos. Con ello, por ejemplo, se consigue reducir el número de colisiones en una tabla de hash. Secundariamente, porque es más rápido el cálculo: truncar es más rápido que redondear. Sacrifican purismo matemático por fines prácticos. Además, el programador puede seguir obteniendo el resto de la división euclídea por otras vías. Puede programar su propia función con ceil() y floor(), o con floor() y truncate() si viene de microsegundos. También es más que probable que el lenguaje tenga una función para obtener dicho resto. Por ejemplo C tiene la función fmod en la librería math.h

La privacidad no existe

Cifrado

Cifrado con clave pública y clave privada

A finales del año pasado apareció en el blog de Chema Alonso un interesante artículo acerca de como la NSA podría haber “troyanizado” los números primos para descifrar las comunicaciones. La conclusión de dicho artículo es que la privacidad en Internet no existe. Nada queda oculto a quien dispone de los recursos suficientes. Aunque de criptografía sé muy poco, voy a intentar explicar lo que he entendido del artículo, añadiendo una introducción previa. Si me equivoco en algo agradecería que me lo hagáis saber en la zona de comentarios.

En primer lugar, cuando se habla de algoritmos de 1024 bits, estamos hablando de números que oscilan entre 1 (2^0) y 2^1024 (una cifra descomunal) En criptografía es fundamental poder escoger de la forma más aleatoria posible entre un conjunto de números primos cuanto más amplio mejor. Sabiendo los números primos que se hicieron servir, revertir el cifrado sería inmediato. Si se supiera que los números aleatorios entre los que el algoritmo escoge no son muchos, para descifrar el mensaje se debería aplicar fuerza bruta probando los posibles números. Si son pocos sería cuestión de minutos, o incluso segundos, si son muchos serían años con los mejores ordenadores actuales, incluso siglos, milenios… todo depende de la cantidad de números posibles. Entonces, ¿un algoritmo de 1024 bits de cuantos números posibles dispone para escoger aleatoriamente?

Según la función de Gauss para los números primos, la cantidad aproximada de números primos en un intervalo de 1 a m sería:

m / (ln(m))

Entonces en nuestro caso sería 2^1024 / ( ln(2^1024) ) y ese valor es enorme. Hay millones de números primos que se pueden representar con 1024 bits. Con tanta variedad, ningún ordenador actual, ni conjunto de ellos, podría romper el cifrado.

El algoritmo Diffie-Hellman, usado para el intercambio de claves en un canal no seguro, es de 1024 bits. Muchísimos servicios en Internet lo usan. Herramientas como por ejemplo SSH (y por lo tanto también SCP y SFTP) o los protocolos VPN, acrónimo para las redes privadas que funcionan a través de redes públicas.

El revuelo lo ha causado un estudio que concluye que las implementaciones del algoritmo son defectuosas y dejan sólo 68.000 números primos posibles. Según el mismo estudio, al reducirse de tal modo la cantidad posible de semillas, está dentro de la capacidad computacional de una organización como la NSA romper el cifrado casi en tiempo real, dice textualmente:

Our calculations suggest that it is plausibly within NSA’s resources to have performed number field sieve precomputa-tions for at least a small number of 1024-bit Diffie-Hellman groups. This would allow them to break any key exchanges made with those groups in close to real time.

 

Esto no acaba aquí. En criptografía, el algoritmo Dual Elliptic Curve Deterministic Random Bit Generator se considera óptimo para la generación aleatoria de números. Todo era perfecto hasta que salió un estudio de las universidades de Pennsylvania y Loraine (Francia) donde se afirma que una de las implementaciones más usadas de dicho algoritmo tiene saboteada la generación de números aleatorios:

 

The newspaper articles describe documents making specific reference to a backdoor in the Dual EC random number generator, which had been standardized by both NIST and ANSI. NIST responded by withdrawing its recommendation for the Dual EC DRBG, writing “This algorithm includes default elliptic curve points for three elliptic curves,the provenance of which were not described. Security researchers have highlighted the importance of generating these elliptic curve points in a trustworthyway. This issue was identified during the development process, and the concern was initially addressed by including specifications for generating different points than the default values that were provided. However, recent community commentary has called into question the trustworthiness of these default elliptic curve points” [38]. There is evidence that the ability to backdoor the Dual EC
algorithm has been exploited in the wild: Juniper Networks had implemented
Dual EC in NetScreen VPN routers, but had used it with custom-generated
parameters. In December 2015 Juniper published a security advisory [25] an-
nouncing that an attacker had made unauthorized modifications to the source
code for these products to substitute a different curve point in the Dual EC
implementation.

 

Con este sabotaje y hardware especializado es posible revertir el cifrado en algo menos que milenios como cabría esperar. 80 minutos son suficientes:

 

Both the Initialization and the Descent steps can be heavily parallelized.
The expected CPU-time for computing an individual logarithm is a few days
on a typical core, distributed more or less equally between the two steps. Using
parallelization, we managed to get a result in 80 minutes of wall-clock time:
the initialization took around 20 minutes parallelized across 500 cores, and the descent took 60 minutes parallelized across 352 cores. (We used 44 cores for each large special q to be descended.)

 

Las dudas razonables sobre la capacidad de la NSA pare descifrar comunicaciones  llevaron a los especialistas a preguntarse el cómo. En cierta manera, no poder explicar si es técnicamente posible era una muy buena defensa para la NSA. Ahora, y a pesar de mi gran desconocimiento sobre estos temas, me parece razonable afirmar que en Internet la privacidad no existe.  Muy recomendable leer el artículo de Chema Alonso. Espero que el mio sirva también como introducción a lo que ahí escribe pues da bastantes cosas por sabidas.

Nota:

Con el objetivo de hacer la lectura más amena he hablado de números aleatorios cuando realmente son pseudo-aleatorios. La Wikipedia contiene un artículo donde explica cómo funcionan las funciones de generación de números aleatorios de los lenguajes programación. Para entender mejor el artículo de la Wikipedia que explica su generación, hay que tener en cuenta que en matemáticas, se dice que dos números a y b son congruentes respecto al módulo m cuando al dividirlos ambos por este módulo producen el mismo resto. Me resulta curioso que algoritmos mucho más complejos para la generación aleatoria de números, usados en “grandes ligas” como la criptografía, sigan siendo pseudo-aleatorios. Por supuesto, implementados sin trampa, la aleatoriedad que consiguen es más que suficiente para lograr el objetivo de cifrar de forma segura.