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 designed
 to prevent the flow of plaintext passwords over the network and
 the storage of them in plaintext. For that purpose a challenge-response
 mechanism for authentication has been implemented on all versions
 of MySQL. Slight variations are to be found between version 3.20
 and 3.21 and above.

 Regrettably, this authentication mechanism is not cryptographically
 strong. Specifically, each time a user executes this mechanism,
 information allowing an attacker to recover this user's password is
 leaked. Using an attack of our design, described in the "Technical
 details" section of this advisory,  an eavesdropper is able to recover
 the user's password after witnessing only a few executions of this
 protocol, and thence is able to authenticate to the database engine
 impersonating a valid user.

Vulnerable Packages/Systems:
  All versions of MySQL

Solution/Vendor Information/Workaround:

 The vendor is aware of the problems described and suggests
 encrypting the traffic between client and server to prevent
 exploitation.
 For further details refer to:

http://www.mysql.com/documentation/mysql/commented/manual.php?section=Securi
ty

 Plans to implement a stronger authentication mechanism are being
 discussed for future versions of MySQL.

 Additionally, advisories and information on security issues
 in 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 Richarte and
 Agustin "Kato" Azubel of CORE SDI, Buenos Aires, Argentina.

 This advisory was drafted with the help of the SecurityFocus.com
 Vulnerability Help Team. For more information or assistance drafting
 advisories 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 between client & server on
 connection and that no passwords are saved in mysql in a decodable
 form.

 MySQL provides users with two primitives used for authentication: a
 hash function and a (supposedly) random generator. On connection a
random
 string is generated by the server and sent to the client. The client,
 using as input the hash value of the random string he has received and
 the hash value of his password, calculates a new string using the
 random generator primitive.
 This 'check' string is sent to the server, where it is compared with a
 string generated from the stored hash_value of the password and the
 random 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 password field.
 
**********************************************************************/

 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 between 0 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 message based 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 the other 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 is obtained using the seconds since 0:00 Jan 1,
    1970 UTC using time(3) when the server starts. Our first observation
    is that the PRNG is seeded with an easily guessable value. Though,
    this observation has no direct implications in the vulnerability we
    present.

  Upon connection to the server from a client a new thread is created to
  handle it and a random string is calculate and stored in 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 response has 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 connection comes from and
     calls the check_scramble function described above to verify the
     valid reponse to the challenge sent. 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-bytes
  strings (40 bits).
  Notice that as for the authentication mechanism described above, to
  impersonate a user only the 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. The algorithm 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 initiate a challenge
  and response. That is, suppose the server has sent a challenge to the
  user U. The hash value of this user'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 random
  generator 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, recalculates the checksum
  by this same process and succintly verifies the authenticity of the
  value it has received. However it is a small collection of these
  checksums that allows any attacker to obtain P1 and P2 (the hash value
  of the user's password). Hence, it is therefore possible to
  impersonate any user with only the information that travels on the
  wire between 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 insecure is that this
  process can be efficently reversed due to it's rich arithmetic
  properties.
  More specifically, consider the random generator described above as a
  mapping 'f' that takes as input the two values X and Y and produces
  the checksum 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 values X',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 values X',Y' such that f(X',Y')=S. This set is of
  negligible size in comparison to the 2^64 points set of all the
  possible passwords' hashes in which it is contained. Furthermore,
  given a collection of challenges and responses made between the same
  user and the server, it is possible to efficiently calculate the set
  of all (hash values of) passwords passing the given tests.


 3. The attack


  We now give a brief description of the attack we propose. This
  description shall enable readers to verify our assertion that the
  MySQL authentication scheme leaks information. This attack has been
  implemented on Squeak Smalltalk and is now perfectly running. A
  complete description of the attack-algorithm lies beyond the scope of
  this text and will be the 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 algorithmic tools:

  Procedure 1 is an algorithmic process which has as input a
  checksum S and the corresponding hash value of the challenge
  C1||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 to a much smaller
  cardinality of 2^20. This set is highly efficiently described, e.g.
  less than 1Kb memory.
  For this smaller set, it is feasible to eliminate the invalid (hashed)
  passwords using further challenges and responses by our Procedure 2.

  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 of passwords to the
  announced set consisting of 2^{20} points, using as input only two
  challenge and responses for the same user.
  This set contains all the passwords passing this two tests. Suppose
  now that the attacker has in his possession a new pair (S,C1||C2) of
  challenge and response, then he can use Procedure 2 to produce the
  smaller set of all the passwords passing the first three tests (the
  ones corresponding to the three pairs of challenge and response he has
  used). Notice that this process can be repeated for every new pair of
  challenge and response the attacker gets. With each application of
  this process the set of possible passwords becomes smaller.
  Furthermore, the cardinality of these sets is 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
  get the password.

  We therefore are able to make a variety of attacks depending on the
  amount of pairs of challenge and response we get from the 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 only a few pairs of challenge and response
  captured, is as well easy to carry out: simply apply the algorithm we
  described with all the pairs of challenge and response captured, then
  use any possible password in the set produced by the application of
  the algorithm for authenticating yourself as a user (some of these
  fake passwords will still pass many tests!).


DISCLAIMER:

  The contents of this advisory are copyright (c) 2000 CORE SDI S.A.
  and may be distributed freely provided that no fee is charged 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 know
 a house from a horse by the roof on the house,
 It's nature 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

Tue, 24 Oct 2000 10:25:14 -0400
Lamar Owen <lamar.owen@wgcr.org>
[Fwd: [CORE SDI ADVISORY] MySQL weak authentication]
On Tue, Oct 24, 2000 at 10:25:14AM -0400, Lamar Owen wrote:
> 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.

IMO, anything short of a full SSL wrapped connection is fairly
pointless.  What does it matter if the password is encrypted if
sensitive query data flows in the clear?
-- 
Bruce Guenter <bruceg@em.ca>                       http://em.ca/~bruceg/
Wed, 25 Oct 2000 10:27:15 -0600
Bruce Guenter <bruceg@em.ca>
Re: [Fwd: [CORE SDI ADVISORY] MySQL weak authentication]
Bruce Guenter wrote:
> On Tue, Oct 24, 2000 at 10:25:14AM -0400, Lamar Owen wrote:
> > 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.
 
> IMO, anything short of a full SSL wrapped connection is fairly
> pointless.  What does it matter if the password is encrypted if
> sensitive query data flows in the clear?

I tend to agree.  SSL is a fully worked out means of doing secure
connections.  It is portable, it is robust, and it is relatively secure.
--
Lamar Owen
WGCR Internet Radio
1 Peter 4:11

Wed, 25 Oct 2000 13:56:17 -0400
Lamar Owen <lamar.owen@wgcr.org>
Re: [Fwd: [CORE SDI ADVISORY] MySQL weak authentication]
On Tue, Oct 24, 2000 at 10:25:14AM -0400, Lamar Owen wrote:
> 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.

Better not try to create it ourselves ;)

http://srp.stanford.edu/

It has even RFC's assigned to it.  RFC2945, RFC2944
I put it into my TOLOOK list but have not found the time yet. :)

-- 
marko


Wed, 25 Oct 2000 23:27:25 +0200
Marko Kreen <marko@l-t.ee>
Re: [Fwd: [CORE SDI ADVISORY] MySQL weak authentication]
On Wed, Oct 25, 2000 at 10:27:15AM -0600, Bruce Guenter wrote:
> On Tue, Oct 24, 2000 at 10:25:14AM -0400, Lamar Owen wrote:
> > 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.
> 
> IMO, anything short of a full SSL wrapped connection is fairly
> pointless.  What does it matter if the password is encrypted if
> sensitive query data flows in the clear?

Passwords are sensitive too.  They are actually orthogonal,
for data security we need something like SSL, but for
authentication/password security we need some strong authentication
scheme anyway.


-- 
marko


Wed, 25 Oct 2000 23:37:13 +0200
Marko Kreen <marko@l-t.ee>
Re: [Fwd: [CORE SDI ADVISORY] MySQL weak authentication]