Curso: (62612) Dise˜no de aplicaciones seguras Fernando Tricas Garc´ıa Departamento de Inform´ atica e Ingenier´ıa de Sistemas Universidad de Zaragoza http://webdiis.unizar.es/~ftricas/ http://moodle.unizar.es/ [email protected]

Tema VII: Aleatoriedad y determinismo Fernando Tricas Garc´ıa Departamento de Inform´ atica e Ingenier´ıa de Sistemas Universidad de Zaragoza http://webdiis.unizar.es/~ftricas/ http://moodle.unizar.es/ [email protected]

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

2

Aleatoriedad y determinismo

La aleatoriedad se utiliza para que determinadas componentes del sistema no sean predecibles: I Identificadores, fundamentalmente I I I

I

En URLs En gesti´ on de sesiones ...

Y claves

Hace falta: I

Longitud adecuada

I

Con suficiente impredecibilidad

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

3

Aleatoriedad y determinismo

I

Mal uso de los sistemas de generaci´ on de n´ umeros aleatorios: problema de seguridad

I

random() y similares no ofrecen n´ umeros verdaderamente aleatorios (PRNG)

I

Los ataques son dif´ıciles, pero no tanto como solemos creer

I

Los computadores son especialmente ‘malos’ para estas cosas

I

Vamos a discutir el uso de n´ umeros seudo-aleatorios de forma adecuada

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

4

Generadores de n´umeros pseudo...

I

Los computadores son completamente deterministas

I

Se utilizan algoritmos generadores (pseudo random number generators – PRNG) A partir de una semilla (un n´ umero inicial) se calculan los siguientes. I I

I

Si las semillas se pueden adivinar, los n´ umeros tambi´en Hay que tratar de tener semillas imposibles de calcular o de predecir A veces es u ´til que esto sea as´ı (depuraci´ on, simulaci´on, ...)

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

5

Generadores ...

I

Siempre que sea posible, semillas generadas ‘m´as aleatoriamente’

I

Si la semilla tiene n bits ‘buenos’, el ataque necesitar´a 2n operaciones

I

Hace falta conocer el algoritmo, no siempre es as´ı, pero la experiencia demuestra una y otra vez, que es mejor suponer que se conoce (recordar: defensa en profundidad)

I

Se trata de suposiciones parecidas a las que hacen los cript´ografos. (se consideran as´ı)

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

6

Dos tipos de algoritmos

I

Estad´ısticos. 1. Est´an pensados pasar los tests de aleatoriedad estad´ıstica, lo que no significa que sean impredecibles (s´ olo que se distribuyen razonablemente). 2. Un objetivo importante es la reproducibilidad, con una semilla al principio

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

7

Algoritmos criptogr´aficos

I

Criptogr´aficos I

I I

Necesitamos m´as: que sean seguros criptogr´aficamente (los estad´ısticos son de uso frecuente) Su seguridad depende de la entrop´ıa de la semilla random(), rand(), drand48(), lrand48(), mrand48() no son criptogr´aficos I

java.util.Random tampoco.

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

8

Ejemplos

El m´as frecuente, generador lineal basado en congruencias Xn+1 = (aXn + b)mod c Valores adecuados de a, b, y c proporcionan buenos resultados para aplicaciones estad´ısticas

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

9

M´as detallado long long RandSeed = #### ; unsigned long Random ( l o n g max ) { long long x ; doubl e i; unsigned long final ; x = 0xffffffff ; x += 1 ; RandSeed ∗= ( ( l o n g l o n g ) 1 3 4 7 7 5 8 1 3 ) ; RandSeed += 1 ; RandSeed = RandSeed % x ; i = ( ( d o u b l e ) RandSeed ) / ( double ) 0 x f f f f f f f f ; f i n a l = ( l o n g ) ( max ∗ i ) ; return ( unsigned long ) f i n a l ; } 62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

10

Generadores basados en congruencias

I

Generan un n´ umero entre 0 y 1, o un entero equiprobable

I

Son muy f´aciles de atacar, porque la mayor´ıa usan valores de 32 bits

I

Observando los n´ umeros generados, se puede adivinar la semilla (s´olo hay 4.294.867.295 posibilidades)

I

Aumentando el n´ umero de bits no mejora, porque tambi´en hay otros ataques posibles

I

¡Usar uno criptogr´afico!

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

11

Blum-Blum-Shub I

M´etodo criptogr´afico, basado en la dificultad de factorizar primos grandes

I

No muy pr´actico Importante porque se basa en principios matem´aticos simples

I

1. Dos n´ umeros primos grandes p y q (p mod 4 = 3, q mod 4 = 3) Secretos. 2. N = p x q es el n´ umero de Blum 3. Elegir una semilla aleatoria s (entre 1 y N, que no sea p ni q) 4. x0 = s 2 mod N 2 5. xi = xi−1 mod N 6. bi = xi mod 2 El bit menos significativo de xi se usa como bit aleatorio.

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

12

Ataques

I

Criptoan´alisis

I

Conocimiento que se pueda tener sobre el estado interno del PRNG

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

13

¿D´onde conseguir entrop´ıa?

I

La semilla es muy importante I I

I

No se puede incluir en el c´ odigo, ni pedir que alguien la teclee No usar direcciones de red, nombres de m´aquinas, de gente, de la madre ... El reloj tampoco es una buena fuente: en la mayor´ıa de los casos, 32 bits, pero muchas veces, ni siquiera eso.

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

14

¿D´onde conseguir entrop´ıa?: hw

I

La mejor soluci´on es el ‘hardware’ espec´ıfico

I

No siempre es factible Ejemplos:

I

I I

I

Medir el ruido t´ermico en un diodo semiconductor Contador Geiger que emite un pulso cada vez que se detecta una bajada de radioactividad, el intervalo temporal es aleatorio

Conviene procesar despu´es (y vigilar).

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

15

¿D´onde conseguir entrop´ıa?: sw I I I

Casi siempre se usan de este tipo Se supone que la m´aquina no ha sido comprometida Se buscan fuentes de aleatoriedad: I I

Muestreo del teclado o del rat´ on Por ejemplo: ‘mueva el rat´ on, o teclee un texto’ Visto en http://ubuntuforums.org/showthread.php?t=1975929

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

16

¿D´onde conseguir entrop´ıa?

I

Cuidado con el rat´ on: la informaci´ on viaja por la red y es visible para las aplicaciones

I

Cuidado con el teclado: auto-repetici´ on Tiempo para la finalizaci´ on de alguna tarea

I

1. Tiempo tardarmos en conseguir tiempo de procesador un determinado n´ umero de veces. 2. Tiempo que se tarda en lanzar un hilo que no hace nada, ... VI I

Variaciones entre el reloj y la generaci´ on de interrupciones

I

Tr´afico de la red, tiempo de b´ usqueda en el disco (cuidado con este)

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

17

¿D´onde conseguir entrop´ıa?

I

Es dif´ıcil saber c´omo de buenos son los datos que se consiguen as´ı I

I

Se puede tratar de medir, ejecutando repetidamente, y observando qu´e bits cambian con una probabilidad similar

Muchas de estas t´ecnicas son susceptibles de recibir ataques, si alguien tiene acceso a la m´aquina

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

18

Algunos (malos) ejemplos

Navegador Netscape En 1996 demostraron un fallo, al elegir una mala semilla (f´acilmente predecible) para usar con el SSL. Utilizaban la hora del sistema (en sistemas de tipo Unix con una precisi´on de milisegundos pero en otros s´ olo de 1/60 segundo o menos: 60 × 60 × 60 = 216000 valores posibles) Ian Goldberg and David Wagner, ‘Randomness and the Netscape Browser’ http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

19

Algunos (malos) ejemplos

Debian, openSSH En mayo de 2008, un problema en Debian por un generador aleatorio predecible: S´ olo 215 (32767) claves posibles. El desarrollador coment´ o parte del c´ odigo (que no comprend´ıa bien) porque pens´o que era innecesario al ser se˜ nalado como tal (‘using uninitialized data’) por una herramienta de ayuda (‘Valgrind’). http://www.debian.org/security/2008/dsa-1571 http://etbe.coker.com.au/2008/05/18/debian-ssh-problems/ http://blog.drinsama.de/erich/en/linux/2008051401-debian-openssl-desaster.html

62612 Dise˜ no de aplicaciones seguras. Fernando Tricas Garc´ıa.

20

Algunos (malos) ejemplos Ruby, openSSH (Nov. 2011) ext/openssl/ossl pkey rsa.c (rsa generate): [SECURITY] Set RSA exponent value correctly. Awful bug. This bug caused exponent of generated key to be always ’1’. By default, and regardless of e given as a parameter. !!! Keys generated by this code (trunk after 2011-09-01) must be re-generated !!! (ruby 1 9 3 is safe)

Mal: f o r ( i = 0 ; i < ( i n t ) s i z e o f ( ex p ) ; ++i ) {

Bien (* 8) : f o r ( i = 0 ; i < ( i n t ) s i z e o f ( ex p ) ∗ 8 ; ++i ) { i f ( ex p & ( 1