MySQL weak authentication vulnerability ------------------------------------------------------------------------ SUMMARY The MySQL Database Engine uses an authentication scheme designed to prevent the flow of plaintext passwords over the network and their storage in plaintext form. 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. By using an attack that is 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 hence is able to authenticate with the database engine impersonating a valid user. DETAILS 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=Security> http://www.mysql.com/documentation/mysql/commented/manual.php?section=Security Plans to implement a stronger authentication mechanism are being discussed for future versions of MySQL. 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 will 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 will introduce a weakness of this authentication scheme, and deduce that an attack more efficient than brute-force attack can be carried out. First, we will describe how the MySQL random generator (PRNG) works. Then we will proceed to analyze 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]) This checksum 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 succinctly 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 efficiently reversed due to its 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 will 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 that was 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 these 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 decreasing but eventually becomes 1. In that case, the one element remaining is the (hashed) password. 4. Statistics and Conclusions In the examples that were 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 are therefore able to make a variety of attacks depending on the amount of pairs of challenge and response we can collect from the user we want to impersonate. ADDITIONAL INFORMATION 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. -- Eko Sulistiono MIKRODATA & AntiVirus Media Web: http://www.mikrodata.co.id/ WAP: http://www.mikrodata.co.id/wap/index.wml This message contains no viruses. Guaranteed by AVP. ------------------------------------------------------------------------ Forum Komunikasi Penulis-Pembaca MIKRODATA (FKPPM) Informasi : http:[EMAIL PROTECTED] Arsip : http://www.mail-archive.com/forum%40mikrodata.co.id/ WAP : http://mikrodata.co.id/wap/index.wml Milis ini menjadi kontribusi beberapa rubrik yang diasuh tim MIKRODATA. Termasuk rubrik-rubrik yang ada di media lain. Memakai, Menyebarluaskan, dan Memperbanyak software bajakan adalah tindakan kriminal. Please check with the latest AVP update before you ask about virus: ftp://mikrodata.co.id/avirus_&_security/AntiViral_Toolkit_Pro/avp30.zip
