the root of all mistake: the overgeneralization

Yes, it's me again with this DSA-1571 exploitation issue. The discovery, explanation and exploitation of the bug is now part of my final coursework for my postgraduate degree career. So, yes... sorry.

Some weeks ago I started suspecting about the attack to PFS in SSL with EDH. The key point is: the key space is dependent of the PRNG state. The bug affects the initialization of the PRNG, but the random string has not a pattern by it self. If you ask for many random numbers to the PRNG, you gonna get numbers that differ among them, since they are the output of a hash function of them self. So each random number depends on, besides the PID, the state of the PRNG pool in the moment (in other words, amount of bytes that you already pull from the PRNG pool before)

The explained attack was based in a fixed list of private exponents (which are selected randomly during the DHE handshake), presupposing that all the application call RAND_bytes() the same number of times before get it. To make the list of exponent I ran the openssl s_client with all the possible PIDs, hoping that all the applications behaves the same way.

After more tests I notice that that was an overgeneralization. The proof is in the pudding: wget and cURL, two simple CLI file retrievers, gets different exponent between them, even running with the same PID.

I was working on this when I accidentally found a really nice Eric Rescorla's post which is deeply related with this. The post goes further and analyzes the interaction between how Apache forks off and how it generates SSL handshakes.

So, I made lists of secret exponents for wget, curl, openssl s_client and openssl s_server with a modification version of libssl (appling this messy patch) and running scripts like this:

for i in $(seq $((2**15)));
do
  export MAGICPID=$i;
  LD_LIBRARY_PATH="openssl.broken/" LD_PRELOAD="./getpid.so" \
     wget --no-check-certificate https://localhost/ -q  -O /dev/null ;
  echo $i ;
done

As you can see, I used the HD Moore's GetPID faker shared library and a normal local Apache with mod_ssl. The broken libssl (which is in .openssl.broken/) store up in /tmp/data.key a csv with command name, PID and all the DH components (g, x, y and p).

But this way is farly unconfortable for others SSL deamon servers. Have you got any better idea?

in the process of moving

Digamos que este post solo tiene sentido si es visto desde mi antiguo gestor de blog. De todas formas decidí portarlo aquí por razones históricas.

Desde ya hace tiempo que tenía intensiones de irme de LiveJournal. No es que funcione mal. Es que simplemente tiene cosas que no me cuadran. Me la paso adaptándome a lo que puede darme (como el caso de hack para el bloguear en planet.debian.org) y tiene limitaciones de diseño. La publicidad que empezó a surgir a la derecha de la pantalla es la gota que derramó el vaso. No es solo antiestética, sino que si decido tener publicidad es porque espero cobrar por ella.

Dado que RaqLink puede proveerme un hosting gratuito y que otros amigos han ofrecido espacio y ancho de banda, decidí mudarme y tener mi propio Blog que dependa de mi mismo.

Así fue como me decidí por WordPress. Es lindo, sencillo y flexible. Por otro lado, dudo de su seguridad. Y este último punto no es menor. Veremos que tal anda durante los próximos meses. Si da mucho problema... volará por otra opción. Escucho opciones.

Una cosa es segura. No más LiveJournal. Este blog (es decir, lbello.livejournal.com) deja de existir como tal. Puedes acceder al nuevo en www.lucianobello.com.ar. Todos los post antiguos está migrados. Incluso los comentarios. En la pasada se han perdido los tags y el threading de los comentarios. Los primeros irán emergiendo con el correr del tiempo y de mi ratos libros. El segundo está definitivamente perdido. Aunque los nuevos comentarios si pueden anidarse, los viejos han quedado planos.

Asimov, Leibniz, pi, python, floats y evadirse de la realidad

La matemática tiene cosas sorprendentemente lindas. Y una de las que siempre me gustó de forma especial es la formula de Leibniz para el cálculo de π. También conocida como la serie de Gregory-Leibniz es una simpática manera de expresar el más famoso de los números irracionales:

O para aquellos no gustan de las notación sigma-grande:

Como verán, se trata de una serie sumamente simple y elegante. Y como suele ocurrir con estas cosas, aparecen en la vida de uno en momentos extraños, casi que al rescate.

Anoche me hallé frente a la biblioteca buscando nada en espacial. Necesitaba despejar la cabeza, olvidarme de los asuntos terrenales asociados con las complejas interacciones y relaciones humanas.

Fue en esa circunstancia que me encuentro con De los números y su historia de Isaac Asimov (que puede ser descargado desde aquí). Mientras lo hojeaba vi la formula de Leibniz, promediando el capítulo 6 e inmediatamente atrajo mi atención.

Después de expresar la serie, Asimov explica:

<<Ustedes podrán condenar mi falta de perseverancia, pero los invito a calcular la serie de Leibniz simplemente hasta donde la hemos escrito más arriba, es decir hasta 4/15. Incluso pueden enviarme una postal para darme el resultado. Si al terminar se sienten desilusionados al descubrir que su respuesta no está tan cerca de π como lo está el valor 355/113, no se den por vencidos. Sigan sumando términos. Sumen 4/17 al resultado anterior, luego resten 4/19, después sumen 4/21 y resten 4/23, etcétera. Pueden seguir hasta donde lo deseen, y si alguno de ustedes descubre cuántos términos se requieren para mejorar el valor 355/113, escríbanme unas líneas y no dejen de decírmelo. >>
En efecto, la fracción 355/113 parece ser la forma que mejor balancea precisión y simpleza a la hora de arrimarse a π desde lo números racionales, quedando a solo 2.66764189 × 10-7 de distancia. Mucha gente también utiliza la relación 22/7, aunque con menor precisión.

El desafío propuesto parecía interesante. Resultaba una entretenida oportunidad de jugar con floats en python, que siempre a resultado ser bastante tricky (además de ser un excusa para despejar la cabeza).

Empecé por escribir una versión relativamente obvia de la solución, que me dijo que al llegar al cociente 7497257 (n=3748629 en la sumatoria de Leibniz) el valor de la sumatoria estaría en 3.14159292035, quedando a 2.66764081935 x 10-7 de π. Dado que los decimales (floats, representaciones de punto flotante) en Python no se comportan de forma intuitiva, decidí hacer una segunda versión.

En esta versión traté de mudarme al predecible mundo de los enteros. Y obtuve valores levemente distintos. En el cociente 7497247 (n=3748624) se obtiene la primera aproximación mejor que 355/113, que es 3.141592386825... (a 2.66764162 x 10-7 de π)

Tampoco estoy seguro de que la segunda solución sea la correcta. Me pregunto cual será el promedio de valores en las postales que la viuda Asimov seguramente guarda en una caja de zapatos.

El hecho es que fue entretenido intentarlo y tal vez continúe con la experiencia la próxima vez que quiera desconectarme del mundo. Después de todo, como dijo el mismo Asimov: “Los hombres que se acostumbran a preocuparse por las necesidades de unas máquinas, se vuelven insensibles respecto a las necesidades de los hombres”, y hay veces que volverse insensible se ve, erróneamente, como una propuesta seductora. Hay gente que ahoga penas en alcohol, mucho más sano es ahogarlas matemáticas...

BTW, ya que tenía los datos armé un plot de los primeros 1000 valores de la serie para mostrar de forma gráfica la convergencia.

Ahora es momento de volver a la realidad, que buena o mala, irracional o racional (seguro que real al menos), inexacta o precisa, después de este recreo metal ya no se ve tan mal :-)

UPDATE: Sat, 20 Sep 2008 22:18:18 -0300: La solución estaba realmente cerca (en mi misma ciudad) y se llama Facundo, quien dejó un comentario. Bah.. se llama decimal, pero existe gracias a Facundo :). La biblioteca decimal permite manejar de forma exacta una cantidad arbitraria de decimales. La respuesta correcta es........ (redoblantes de suspenso) con n=(7497259+1)/2! aproxima a Π en 3.141592386825668744985771256 a solo 2.66764125 × 10-7 del número irracional. El nuevo script.. aquí.

Gracias Facundo, gracias decimal, gracias Asimov, gracias Leibniz....