Mailinglisten-Archive |
-----Ursprüngliche Nachricht-----
Von: Iván Arce <core.lists.bugtraq_(at)_CORE-SDI.COM>
An: <BUGTRAQ_(at)_SECURITYFOCUS.COM>
Gesendet: Dienstag, 24. Oktober 2000 00:09
Betreff: [CORE SDI ADVISORY] MySQL weak authentication
> 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_(at)_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_(at)_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_(at)_core-sdi.com
>
>
---
*** Weitere Infos zur Mailingliste und MySQL unter http://www.4t2.com/mysql
php::bar PHP Wiki - Listenarchive