[Fwd: [CORE SDI ADVISORY] MySQL weak authentication]

I am forwarding this not to belittle MySQL, but to hopefully help in the
development of our own encryption protocol for secure password
authentication over the network.

The point being is that if we offer the protocol to do it, we had better
ensure its security, or someone WILL find the hole.  Hopefully it will
be people who want to help security and not exploit it.

--
Lamar Owen
WGCR Internet Radio
1 Peter 4:11

-------- Original Message --------
Subject: [CORE SDI ADVISORY] MySQL weak authentication
Date: Mon, 23 Oct 2000 19:09:24 -0300
From: Iván Arce <core.lists.bugtraq@CORE-SDI.COM>
Reply-To: Iván Arce <core.lists.bugtraq@CORE-SDI.COM>
Organization: Core-SDI, Buenos Aires, Argentina
To: BUGTRAQ@SECURITYFOCUS.COM
                                        CORE SDI                                  http://www.core-sdi.com
                  Vulnerability Report for MySQL Authentication
Vulnerability


Date Published: 2000-10-23

Advisory ID: CORE-20001023

Bugtraq ID: 1826

CVE CAN: Not currently assigned.

Title: MySQL Authentication Vulnerability

Class: Design Error

Remotely Exploitable: Yes

Locally Exploitable: No


Vulnerability Description:
The "MySQL Database Engine" uses an authentication scheme designedto prevent the flow of plaintext passwords over the
networkandthe storage of them in plaintext. For that purpose a challenge-responsemechanism for authentication has been
implementedon all versionsof MySQL. Slight variations are to be found between version 3.20and 3.21 and above.
 
Regrettably, this authentication mechanism is not cryptographicallystrong. Specifically, each time a user executes this
mechanism,informationallowing an attacker to recover this user's password isleaked. Using an attack of our design,
describedin the "Technicaldetails" section of this advisory,  an eavesdropper is able to recoverthe user's password
afterwitnessing only a few executions of thisprotocol, and thence is able to authenticate to the database
engineimpersonatinga valid user.
 

Vulnerable Packages/Systems: All versions of MySQL

Solution/Vendor Information/Workaround:
The vendor is aware of the problems described and suggestsencrypting the traffic between client and server to
preventexploitation.Forfurther details refer to:
 

http://www.mysql.com/documentation/mysql/commented/manual.php?section=Securi
ty
Plans to implement a stronger authentication mechanism are beingdiscussed for future versions of MySQL.
Additionally, advisories and information on security issuesin MySQL can be obtained from:
       http://www.securityfocus.com/bid/1147       http://www.securityfocus.com/bid/975
http://www.securityfocus.com/bid/926

Vendor notified on: October 19th, 2000

Credits:
These vulnerabilities were found and researched by Ariel "Wata"Waissbein, Emiliano Kargieman, Carlos Sarraute, Gerardo
RicharteandAgustin "Kato" Azubel of CORE SDI, Buenos Aires, Argentina.
 
This advisory was drafted with the help of the SecurityFocus.comVulnerability Help Team. For more information or
assistancedraftingadvisories please mail vulnhelp@securityfocus.com.
 

Technical Description - Exploit/Concept Code:
1. The challenge/response mechanism
The challenge-response mechanism devised in MySQL does the following:From mysql-3.22.32/sql/password.c:


/***********************************************************************The main idea is that no passwords are sent
betweenclient & server onconnection and that no passwords are saved in mysql in a decodableform.
 
MySQL provides users with two primitives used for authentication: ahash function and a (supposedly) random generator.
Onconnection a
 
randomstring is generated by the server and sent to the client. The client,using as input the hash value of the random
stringhe has received andthe hash value of his password, calculates a new string using therandom generator
primitive.This'check' string is sent to the server, where it is compared with astring generated from the stored
hash_valueof the password and therandom string.
 
The password is saved (in user.password) by using the PASSWORD()function in mysql.
 Example:   update user set password=PASSWORD("hello") where user="test" This saves a hashed number as a string in the
passwordfield.
 
**********************************************************************/
To accomplish that purpose several functions and data structures are implemented:
 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)   Initializes the
PRNG,used by versions 3.21 and up
 
  static void old_randominit(struct rand_struct *rand_st,ulong seed1)   Initializes the PRNG, used by versions up to
3.20
 double rnd(struct rand_struct *rand_st)   Provides a random floating point (double) number taken from   the PRNG
between0 and rand_st->max_value
 
 void hash_password(ulong *result, const char *password)   Calculates a hash of a password string and stores it   in
'result'.
 void make_scrambled_password(char *to,const char *password)   Hashes and stores the password in a readable form in
'to'
 char *scramble(char *to,const char *message,const char *password,              my_bool old_ver)   Genererate a new
messagebased on message and password   The same thing is done in client and server and the results are   checked.
 
 my_bool check_scramble(const char *scrambled, const char *message,                      ulong *hash_pass, my_bool
old_ver)  Checks if the string generated by the hashed password and the   message sent matches the string received from
theother endpoint.   This is the check for the challenge-response mechanism.
 
 The MySQL engine initializes the PRNG upon startup of the server as follows:
 mysql-3.22.32/sql/mysqld.cc:main() randominit(&sql_rand,(ulong) start_time,(ulong) start_time/2);   Where start_time
isobtained using the seconds since 0:00 Jan 1,   1970 UTC using time(3) when the server starts. Our first observation
isthat the PRNG is seeded with an easily guessable value. Though,   this observation has no direct implications in the
vulnerabilitywe   present.
 
 Upon connection to the server from a client a new thread is created to handle it and a random string is calculate and
storedin per connection structure, this is done in 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 */   ... The challenge/response exchange is performed and checked in
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);  }   Here the random string has been sent (along with other server    data) and the
responsehas been read.   The authentication checks are then perfomed    ...    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() in mysql-3.22.32/sql/sql_acl.cc does the permission    checks for the username and host the
connectioncomes from and    calls the check_scramble function described above to verify the    valid reponse to the
challengesent. If the response is checked    valid we say this (challenge and response) test was passed.
 
2. The problem: Cryptographically weak authentication scheme

 The hash function provided by MySQL outputs eight-bytes strings (64 bits), whereas the random number generator outputs
five-bytesstrings (40 bits). Notice that as for the authentication mechanism described above, to impersonate a user
onlythe hash value of this user's password is needed, e.g. not the actual password.
 
 We now describe why the hash value of the password can be efficiently calculated using only a few executions of the
challenge-and-response mechanism for the same user. In particular, we introduce a weakness of this authentication
scheme,and deduce that an attack more efficient than brute-force attack can be carried out.
 
 Firstly we describe how the MySQL random generator (PRNG) works. Then we proceed to analyse this scheme's security.
Thealgorithm for making these calculations will be briefly described in the following section.
 
 Let n := 2^{30}-1 (here n is the max_value used in randominit() and old_randoninit() respectively). Fix a user U. And
initiatea challenge and response. That is, suppose the server has sent a challenge to the user U. The hash value of
thisuser's password is 8 bytes long. Denote by P1 the first (leftmost) 4 bytes of this hash value and by P2 the last 4
bytes(rightmost). Likewise, let C1 denote the first 4 bytes of the challenge's hash value and C2 the last 4. Then, the
randomgenerator works as follows:
 
 -calculate the values seed1 := P1^C1 and seed2 := P2^C2 (here ^ denotes the bitwise exclusive or (XOR) function)
 -calculate recursively for 1 =< i =< 8
   seed1 = seed1+(3*seed2)         modulo (n)   seed2 = seed1+seed2+33          modulo (n)   r[i] =
floor((seed1/n)*31)+64
 -calculate form the preceding values
   seed1 = seed1+(3*seed2)         modulo (n)   seed2 = seed1+seed2+33          modulo (n)   r[9] =
floor((seed1/n)*31)
 -output the checksum value  S=(r[1]^r[9] || r[2]^r[9] || ... || r[7]^r[9] || r[8]^r[9])
 It is this checksum that is sent, by U, to the server. The server, who has in store the hash value of U's password,
recalculatesthe checksum by this same process and succintly verifies the authenticity of the value it has received.
Howeverit is a small collection of these checksums that allows any attacker to obtain P1 and P2 (the hash value of the
user'spassword). Hence, it is therefore possible to impersonate any user with only the information that travels on the
wirebetween server and client (user).
 
 The reason why the process of producing the checksum out of the hash values of both the password and the challenge is
insecureis that this process can be efficently reversed due to it's rich arithmetic properties. More specifically,
considerthe random generator described above as a mapping 'f' that takes as input the two values X and Y and produces
thechecksum value f(X,Y)=S (e.g., in our case X:=P1^C1 and Y:=P2^C2). Then we can efficiently calculate all of the
valuesX',Y' which map to the same checksum value than X,Y, i.e. if f(X,Y)=S, then we calculate the set of all the
valuesX',Y' such that f(X',Y')=S. This set is of negligible size in comparison to the 2^64 points set of all the
possiblepasswords' hashes in which it is contained. Furthermore, given a collection of challenges and responses made
betweenthe same user and the server, it is possible to efficiently calculate the set of all (hash values of) passwords
passingthe given tests.
 

3. The attack

 We now give a brief description of the attack we propose. This description shall enable readers to verify our
assertionthat the MySQL authentication scheme leaks information. This attack has been implemented on Squeak Smalltalk
andis now perfectly running. A complete description of the attack-algorithm lies beyond the scope of this text and will
bethe matter of future work.
 
 The attack we designed is mainly divided into two stages. In these two stages we respectively use one of our two
algorithmictools:
 
 Procedure 1 is an algorithmic process which has as input a checksum S and the corresponding hash value of the
challengeC1||C2, and outputs a set consisting of all the pairs X,Y mapping through the random generator to the checksum
S,i.e. in symbols {(X,Y): f(X,Y)=S} (here of course we have 0 <=X,Y< 2^{32}).
 
 In our attack Procedure 1 is used to cut down the number of possible hashed passwords from the brute-force value 2^64
toa much smaller cardinality of 2^20. This set is highly efficiently described, e.g. less than 1Kb memory. For this
smallerset, it is feasible to eliminate the invalid (hashed) passwords using further challenges and responses by our
Procedure2.
 
 Procedure 2 is an algorithmic process having as input a set SET of possible (hashed) passwords, and a new pair
(S,C1||C2)of checksum and challenge, and producing as output the subset of SET of all the passwords passing this new
test.
 The way in which Procedure 2 is used in our algorithm should now be clear. We first use Procedure 1 to reduce the set
ofpasswords to the announced set consisting of 2^{20} points, using as input only two challenge and responses for the
sameuser. This set contains all the passwords passing this two tests. Suppose now that the attacker has in his
possessiona new pair (S,C1||C2) of challenge and response, then he can use Procedure 2 to produce the smaller set of
allthe passwords passing the first three tests (the ones corresponding to the three pairs of challenge and response he
hasused). Notice that this process can be repeated for every new pair of challenge and response the attacker gets. With
eachapplication of this process the set of possible passwords becomes smaller. Furthermore, the cardinality of these
setsis not only decresing but eventually becomes 1. In that case the one element remaining is the (hashed) password.
 

4. Statistics and Conclusions
 In the examples we tested, about 300 possible passwords were left with the use of only 10 pairs of challenge and
response.Notice that in a plain brute-force attack about 2^{64}-300=18,446,744,073,709,551,316 would remain as possible
passwords.It took about 100 pairs of challenge and response to cut the 300 set two a set containing two possible
passwords(i.e., a fake password and the password indeed). Finally it took about 300 pairs of challenge and response to
getthe password.
 
 We therefore are able to make a variety of attacks depending on the amount of pairs of challenge and response we get
fromthe user we want to impersonate. The two extreme cases being very few pairs of challenge and response from the same
user,and a lot of pairs of challenge and response. The second attack, that of many pairs of challenge and response
captured,is straight-forward: Apply the algorithm described above until the password is found. The first case, that of
onlya few pairs of challenge and response captured, is as well easy to carry out: simply apply the algorithm we
describedwith all the pairs of challenge and response captured, then use any possible password in the set produced by
theapplication of the algorithm for authenticating yourself as a user (some of these fake passwords will still pass
manytests!).
 


DISCLAIMER:
 The contents of this advisory are copyright (c) 2000 CORE SDI S.A. and may be distributed freely provided that no fee
ischarged for this distribution and proper credit is given.
 

$Id: MySQLauth-advisory.txt,v 1.11 2000/10/23 21:30:57 iarce Exp $

---

"Understanding. A cerebral secretion that enables one having it to knowa house from a horse by the roof on the
house,It'snature and laws have been exhaustively expounded by Locke,who rode a house, and Kant, who lived in a horse."
-Ambrose Bierce
 


==================[ CORE Seguridad de la Informacion S.A. ]=========
Iván Arce
Presidente
PGP Fingerprint: C7A8 ED85 8D7B 9ADC 6836  B25D 207B E78E 2AD1 F65A
email   : iarce@core-sdi.com
http://www.core-sdi.com
Florida 141 2do cuerpo Piso 7
C1005AAG Buenos Aires, Argentina.
Tel/Fax : +(54-11) 4331-5402
=====================================================================


--- For a personal reply use iarce@core-sdi.com