Reporte de Vulnerabilidad en la Autenticación de MySQL
Fecha de Publicacion: Septiembre 26, 2000
Advisory ID: CORE-092600
Bugtraq ID: 1826
CVE CAN: Ninguno asignado hasta el momento.
Titulo: Vulnerabilidad en la Autenticación de MySQL
Clase: Error de Diseño
Explotable Remotamente: Si
Explotable Localmente: Si
Descripcion de la Vulnerabilidad:
para prevenir el paso de passwords en plaintext por la red y a la
vez el almacenamiento de las mismas en ese formato. Para eso todas
las versiones MySQL cuentan con un mecanismo de challenge-and-response
(reto y contestación). Pequeñas variaciones de este mecanismo
pueden encontrarse en la versión 3.20, la 3.21 y las subsiguientes.
Lamentablemente este esquema de autenticación es criptografícamente
inseguro. Específicamente, cada vez que un usuario utiliza este esquema
pierde (ej: muestra) cierta información que puede ser utilizada por un
atacante para recuperar la clave de este usuario. Mediante un
procedimiento de nuestro diseño, que se describe en la sección
``Detalles
Técnicos", un atacante que esta ``escuchando'' en la red puede recuperar
la clave del usuario tan solo después de presenciar unas pocas
ejecuciones
de este esquema, y así autenticarse ante la base de datos personificando
a
un usuario valido.
Sistemas/Paquetes Vulnerables:
Todas las versiones de MySQL
Solucion/Informacion de Vendedores/Workaround:
El vendedor fue avisado de los problemas descriptos y sugiere encriptar
el
tráfico entre cliente y server para prevenir este ataque. Para acceder a
más
detalles se lo refiere a
http://www.mysql.com/documentation/mysql/commented/manual.php?section=Securi
ty
Se estan discutiendo planes para implementar una autenticación segura en
las
próximas versiones de MySQL. Advisories adicionales e información sobre
seguridad
en MySQL pueden encontrarse en:
http://www.securityfocus.com/bid/1147
http://www.securityfocus.com/bid/975
http://www.securityfocus.com/bid/926
Vendedor notificado en: 19 de Octubre de 2000
Creditos:
Estas vulnerabilidades fueron encontradas e investigadas por Ariel
"Wata" Waissbein,
Emiliano Kargieman, Carlos Sarraute, Gerardo Richarte y Agustin "Kato"
Azubel de CORE
SDI, Buenos Aires, Argentina.
Este advisory fue creado con la ayuda del SecurityFocus.com
Vulnerability Help Team.
Para mas información o asistencia en la creacion de advisories por favor
envie un mail a
[EMAIL PROTECTED]
Descripcion Tecnica - Exploit/Codigo de Prueba de Concepto:
1. El mecanismo de challenge-and-response:
Se describe el mecanismo de autenticación de MySQL directamente del
fichero
mysql-3.22.32/sql/password.c:
/***********************************************************************
La idea principal es que no se mandan claves entre cliente y server
durante la conección,
y que ninguna clave se guarda en el server en un formato del que pueda
ser decifrada.
MySQL provee a los usuarios de dos primitivas que son usadas para el
proceso de autenticación:
una función de hash y un generador de números (supuestamente)
pseudo-aleatorios. Al comienzo
de cada conección el server genera una tira de números aleatorios (con
un generador que solo
posee el server) que manda al cliente - este es el challenge o reto. El
cliente usa X-OR del
hash de esta tira con el valor del hash de su clave como entrada de la
función generadora de
números aleatorios. Este es el response (o la respuesta) al reto, que el
manda al server, donde
es comparado con el mismo valor que es generado en el server a partir
del hash de la clave del
cliente y el mismo challenge. La clave se guarda (en user.password)
usando la función PASSWORD()
de mysql.
Ejemplo:
update user set password=PASSWORD("hello") where user="test"
Esta instrucción guarda el numero hasheado como un string en el campo de
clave.
**********************************************************************/
Con ese propósito varias funciones y estructuras de datos se han
implementado:
mysql-3.22.32/include/mysql_com.h:
struct rand_struct {
unsigned long seed1,seed2,max_value;
double max_value_dbl;
};
mysql-3.22.32/sql/password.c:
void randominit(struct rand_struct *rand_st,ulong
seed1, ulong seed2)
Inicializa el PRNG, usado en la versión 3.21
y superiores.
static void old_randominit(struct rand_struct
*rand_st,ulong
seed1)
Inicializa el PRNG, usado en versiones
hasta 3.20.
double rnd(struct rand_struct *rand_st)
Provee de un número random de tipo punto
flotante (double)
entre 0 y rand_st->max_value tomado del PRNG.
void hash_password(ulong *result, const char
*password)
Calcula el hash de la clave y lo guarda en
'result'.
void make_scrambled_password(char *to,const char
*password)
Hashea y guarda la clave en 'to' en un
formato leible.
char *scramble(char *to,const char *message,const
char
*password, my_bool old_ver)
Genera un nuevo mensaje basado en el mensaje
y la clave
El mismo procedimiento se hace en el
servidor y el cliente
my_bool check_scramble(const char *scrambled, const
char
*message, ulong *hash_pass, my_bool old_ver)
Chequea si el string genereado por el
mensaje y el hash de la
clave es identico al string recibido en el
servidor
Este es el chequeo para el esquema de reto y respuesta.
La MySQL engine inicializa el generador de números
pseudo-aleatorios (PRNG)
al iniciar el server como sigue:
mysql-3.22.32/sql/mysqld.cc:main()
randominit(&sql_rand,(ulong) start_time,(ulong) start_time/2);
Donde start_time se obtiene usando la
cantidad de segundos desde
0:00 Enero 1, 1970 UTC usando time(3) cuando el server
inicia.
Nuestra primera observación es que el PRNG es
inicializado con una
semilla facil de adivinar. Sin embargo, esta
observación no tiene
relación directa con la vulnerabilidad que
se presenta en este advisory.
Al conectarse un cliente al server un nuevo hilo
(thread) es creado
para manejarla, y un número pseudo-aleatorio es
calculado por el
generador de números pseudo-aleatorios y ese número es
guardado por
estructura de conección. Este proceso se ejecuta en
mysql-3.22.32/sql/mysqld.cc:create_new_thread():
...
(thread_count-delayed_insert_threads > max_used_connections)
max_used_connections=thread_count-delayed_insert_threads;
thd->thread_id=thread_id++;
for (uint i=0; i < 8 ; i++) // Generate password
teststring
thd->scramble[i]= (char) (rnd(&sql_rand)*94+33);
thd->scramble[8]=0;
thd->rand=sql_rand;
threads.append(thd);
/* Start a new thread to handle connection */
...
El intercambio de reto/respuesta se ejecuta y es
chequeado en
mysql-3.22.32/sql/sql_parse.cc:check_connections():
....
memcpy(end,thd->scramble,SCRAMBLE_LENGTH+1);
end+=SCRAMBLE_LENGTH+1;
...
if (net_write_command(net,protocol_version, buff,
(uint)
(end-buff)) ||
(pkt_len=my_net_read(net)) == packet_error ||
pkt_len < 6)
{
inc_host_errors(&thd->remote.sin_addr);
return(ER_HANDSHAKE_ERROR);
}
Aquí el número pseudo-aleatorio ha sido mandado
(junto con
otra información del server) y la respuesta ha sido
leida.
El chequeo de autenticación se ejecuta.
...
char *passwd= strend((char*) net->read_pos+5)+1;
if (passwd[0] && strlen(passwd) != SCRAMBLE_LENGTH)
return ER_HANDSHAKE_ERROR;
thd->master_access=acl_getroot(thd->host, thd->ip,
thd->user, passwd, thd->scramble,
&thd->priv_user,
protocol_version == 9 ||
!(thd->client_capabilities &
CLIENT_LONG_PASSWORD));
thd->password=test(passwd[0]);
...
acl_getroot() en mysql-3.22.32/sql/sql_acl.cc chequea
los permisos para
el nombre de usuario y el host de donde se origina la
concección, y llama
la función check_scramble descripta arriba para verificar la
respuesta
válida al reto ya mandado. Si la respuesta es chequeada como
válida se
dice que el test (de reto y respuesta) ha sido pasado.
2. El problema: Esquema de Autenticación Cripográficamente Débil
La función de hash provista por MySQL tiene una salida de 8 octetos (64
bits) mientras
que el generador de números psedu-aleatorios tiene una salida de 5
octetos (40 bits).
Nótese que según el mecansimo de autenticación arriba descrpito para
personificar un
usuario ante la base de datos solo hace falta el hash de su clave, e.j.
y no la clave
misma. En lo que sigue se explica el motivo por el cual el hash de la
clave de un usuario
puede ser eficientemente calculada a partir de (mirar) unas pocas
ejecuciones del protocolo
de challenge and response entre el server y un mismo usuario. En
particular, introducimos
una debilidad en el esquema de autenticación y deducimos que un ataque
mucho más eficente que
el ataque de fuerza bruta (brute-force attack) es posible.
Primeramente se describe como funciona el generador de números
pseudo-aleatorios. Luego,
procedemos a analizar la seguridad que proporciona. El algoritmo para
hacer estos cálculos
será introducido en la siguiente sección.
Sea n := 2^{30}-1 (aca n es el valor max_value usado en randominit() y
old_randoninit()
respectivamente). Fijese un usuario U. E iniciese un esquema de
challenge and response.
Supongamos que el server ha mandado un reto (challenge) al usuario U.
Nótese que el hash
de la clave del usuario, y el hash de este reto son cada uno de 8
octetos. Denotese por
P1 los 4 primeros (más significativos) octetos del hash de la clave y
por P2 los últimos
4 octetos de este hash. Analogamente, sean C1 y C2 los primeros 4 y
últimos 4 octetos del
hash del challenge. Luego el (programa que interpreta al) generador de
números psuedo-
aleatorios hace los siguiente:
-calcula los valores seed1 := P1^C1 and seed2 := P2^C2
(aqui ^ denota la funcion XOR)
-calcula recursivamente para 1 =< i =< 8, i++
seed1 = seed1+(3*seed2) modulo (n)
seed2 = seed1+seed2+33 modulo (n)
r[i] = floor((seed1/n)*31)+64
(acá floor denota la función suelo floor(x)=max{n entero tq n=<x})
-calcual a partir de los valores precedentes
seed1 = seed1+(3*seed2) modulo (n)
seed2 = seed1+seed2+33 modulo (n)
r[9] = floor((seed1/n)*31)
-devuelve la respuesta
S=(r[1]^r[9] || r[2]^r[9] || ... || r[7]^r[9] || r[8]^r[9])
Es esta respuesta que manda el usuario U al server para autenticarse. El
server, que
tiene guardado el hash de la clave y el challenge repite este
procedimiento para
encontrar la misma respuesta, y autentica correctamente al usuario si
ambas respuestas
son identicas. Sin embargo, veremos que tan solo con un pequeño número
de estas
respuestas, y sus respectivos retos, le permiten a un atacante obtener
al hash de la
clave P1,P2. Luego, es posible por este medio personificar a cualquier
usuario con
la información que viaja por la red entre el server y el cliente
(usuario).
La razón por la cual el proceso de producir respuestas a partir del X-OR
de los hashes
de la calve y el reto -usando la función generadora de números
pseudo-aleatorios- es
que dicho proceso/función puede ser invertida eficentemente. Más
especificamente,
denote por f a la función que toma los valores X e Y como entrada y
devuelve el
valor S=f(X,Y) (e.g., en nuestro caso es X=P1^C1 e Y=P2^C2). Entonces,
mediante un
algoritmo eficiente, es posible recuperar todos los valores X',Y' que
devuelven la misma salida f(X',Y')=S que el par X,Y. Este conjunto es de
un tamanio negligible en
comparación con los 2^{64} valores de posibles hash de clave en el cual
esta contendio.
Aún más, dada una colección de retos y respuestas entre un mismo usuario
y el server,
es posible calcular eficientemente el conjunto de todos los hashes de
claves que pasan
los retos dados.
3. El ataque
En lo que sigue se da una breve descripción del ataque propuesto. Esta
descripción
permitirá a los lectores verificar el hecho de que el esquema de
autenticación de
MySQL que se describe arriba ``pierde" información. Este ataque ha sido
implementado
en Squeak Smalltalk y esta funcionando en este mismo momento. Una
descripción completa
del ataque va más allá de las miras de este advisory y aparecerá como un
white-paper
en el futuro.
El procedimiento que subyace al ataque esta divido en dos partes. En
estas partes se
usa respectivamente alguna de las siguientes herramientas algorítmicas:
El procedimiento 1 es la herramienta mediante la cual se calcula, a
partir de la respuesta
S y el correspondiente hash del reto C1||C2, el conjunto que consiste de
todos los pares
X,Y que van a parar a S via la función f, i.e. en símbolos {(X,Y):
f(X,Y)=S} (aquí por
supuesto es 0 <=X,Y< 2^{32}).
En el ataque, el procedimiento 1 es usado para reducir el número de
posibles hashes de clave
a 2^{33} del valor máximo 2^{64} correspondiente al ataque de fuerza
bruta. Este conjunto es
altamente eficientemente descripto, e.j. representado en menos de 1Kb de
memoria.
De este nuevo y más pequeño conjunto, es posible eliminar eficientemente
candidatos a hash de
clave usando nuevos pares de reto y respuesta mediante el Procedimiento
2. El Procedimiento
2 es la herramienta algorítmica mediante la cual, a partir de un
conjunto SET de candidatos
a hash de clave, y un nuevo par de reto y respuesta (S,C1||C2), se
cacula el subconjuto de
SET que pasa este nuevo (último) reto.
La manera en la cual el Procedimieto 2 se usa en el ataque debería estar
ya clara. Primeramente
se utiliza el Procedimiento 1 para reducir el conjunto de candidatos de
hash de clave del valor
2^{64} a 2^{33} usando tan solo un par de reto y respuesta para un mismo
usuario. El conjunto
resultante contiene todas los hash de claves que pasan estos dos tests.
Supongase ahora que
se tiene un nuevo par de reto y respuesta (S,C1||C2), entonces el
atacante puede utilizar el
Procedimiento 2 para producir el conjunto -más pequeño- de hash de
claves que pasan los tres
retos en cuestión (los dos correspondientes al Procedimiento 1, y el
último que corresponde al
Procedimiento 2). Cabe aclarar que el Procedimiento 2 puede ser
reaplicado por cada nuevo par
de reto y respuesta que es capturado. Con cada aplicación de este
porcedimiento el conjunto de
candidatos a hash de clave se hace cada vez más pequeño. Aún más, la
cardinalidad de estos
conjuntos de candidatos no es solo decreciente, sino que eventualmente
llega al valor 1. En
cuyo caso el elemento remanente es exactamente el hash de la clave.
4. Estadisticas y Conclusiones
En los ejemplos testeados, quedaron aproximadamente 300 cantidatos a
clave después de aplicar
nuestro ataque a 10 pares de reto y respuesta correspondientes a un
mismo usuario. Nótese que
un ataque de fuerza bruta hubieran quedado
2^{64}-300=18,446,744,073,709,551,316 candidatos a
clave. Tomo unos 100 pares de reto y respuesta en reducir esos 300
candidatos a clave a un conjunto de tan solo 2 candidatos (e.j., una
clave falsa y la verdadera).
Finalmente nos tomó unos 300 pares de clave y respuesta para encontrar
la verdadera clave.
De esta manera nos es posible hacer una amplia variedad de ataques
dependiedo de la cantidad
de pares de reto y respuesta que se poseen del usuario que se quiere
personificar. Los dos
casos extremos son cuando se tienen pocos pares de reto y respuesta, y
el caso en el que se
tiene una grán cantidad de tales pares. El segundo caso extremo, aquel
de muchos pares de
de reto y respuesta capturados, es directo: Aplíquese el algoritmo
arriba descripto hasta
obtener el hash de la clave. El primer caso extremo, aquel de unos pocos
pares de reto y
respuesta capturados, es también fácil de llevar a cabo: simplemente
aplíquese nuestro algoritmo
con todos los pares de reto y respuesta capturados, y luego usese
cualquiera de los candidatos
restantes para la autenticación (muchas de estos falsas claves aún pasan
varios nuevos tests!).
Informacion de Copyright:
~~~~~~~~~~~~~~~~~~~~~~~~~
El contenido de esta advertencia de seguridad es copyright (c) 2000 CORE
SDI S.A. y puede ser distribuida libremente si es que no se cobra ningun
tipo de arancel por su distribución y se mencione quien sostenta su
autoría.
==================[ CORE Seguridad de la Informacion S.A. ]=========
--
Sebastián D. Criado
