27 janvier 2008
MySQL AES_ENCRYPT error rate on erroneous encryption/decryption key
As stated on MySQL documentation:
"If AES_DECRYPT() detects
invalid data or incorrect padding, it returns
NULL. However, it is possible for AES_DECRYPT() to return a
non-NULL value (possibly garbage) if the
input data or the key is invalid."
In fact if the wrongly decrypted last char is 0F (hexa), all 15 previous characters will be considered as valid, so error is approximately 1/256 (0.4%). There's other cases but they are statistically not signifiants.
On a 1Million user base, AES_DECRYPT() will send back results (invalid) for approximately 4000 accounts, when the encryption/decryption key is erroneous.
26 janvier 2008
MySQL AES_ENCRYPT flaws
MySQL integrate a AES_ENCRYPT function, that should encrypt (128bits encryption) a string with a key. A reversible encryption.
The company that actually hire me use the AES_ENCRYPT function to encrypt user passwords.
There's 3 problems in the way it is done by the company:
- There's no need to reversible encryption, a simple SHA-1 fingerprint should be enough (will be subject to dictionary attack if not properly salted, globally + individually!)
- The encryption KEY is common to all the user base (NO SALT), rapidly growing (10K+ each day!), leading to possible search of the encryption key knowing only one account on a test server. So any developer could know any user password and use it's account if it see an encrypted Password ;-)
- Encryption key is in pur ascii, so it's only 112 bits encryption (16 characters x 7bits) instead 128bits Key
And now there's the MySQL part of the bad job, to weaken the encrypted content...
The AES encryption encrypt content using 16-bytes blocks (128bits).
When you encrypt a password (15 chars or less, usually 6-8 chars) with AES_ENCRYPT() on MySQL, MySQL create a block that contain the password followed by it's length repeated on each following Byte.
So a 'toto' password will be transformed to:
74 6F 74 6F 04 04 04 04 04 04 04 04 04 04 04 04
Yes you read it: even if you didn't know the length (given it's on the 6-8 char web account password), the last 8 chars contains less than 2 real bits of informations (6, 7 or 8, encoded and repeated), leading to attack on the AES itself, for example to try to reveal the encryption key!
There's no need to add the length on each remaining byte of the message, once is enough (at the end of the block naturally), and all remaining space should have been filled with truely random information, as they will be discarded on the AES_DECRYPT() function!
Sorry MySQL, but another time, you made it wrong from start!
Worse, as many DB use the AES_ENCRYPT() function, and they could be used to do COMPARE on SELECT(), this wrong behaviour could not be changed without breaking compatibility with installed user-base!
Please! Consider security seriously next time!
02 novembre 2006
Why brute-force alone is impractical
Actually, mysql offers the ability to store nearly 4 611 686 018 427 387 904 differents footprints, 4 x 10^18. Or 4 billions of billions.
That much keys could not be totally parsed in a lifetime, even if we parse 1 billion key/second. John-the-ripper parse around 10-20 millions key per second on a monocore Pentium4, that lead us to 5 millenium. Remind me of 42 (The hitchhiker's guide to the galaxy).
In the other hand, if you forge passwords, you will end up with as much as 10^16 possibilities for 8 characters passwords, or 10^18 possibilities for 9 characters. Even 10^16 possibilities will take John more than 10 years of tries on our monocore Pentium4.
| password-len | number of password | time @ 10million key/s |
|---|---|---|
| 1 char | 94 | 0s |
| 2 chars | 9 x 10^3 | 0s |
| 3 chars | 831 x 10^3 | 0s |
| 4 chars | 78 x 10 ^6 | 8 s |
| 5 chars | 7 x 10^9 | 12 mn |
| 6 chars | 690 x 10^9 | 19 hours |
| 7 chars | 65 x 10^12 | 2+ months |
| 8 chars | 6 x 10^15 | 19 years |
| 9 chars | 573 x 10^15 | 2 milleniums |
This is the table that show time needed for full-scan depending on the password length. I take the assumption that nobody will use accents, but that we could find non-alphanumerical characters (ASCII ranging from 33 to 126 = 94 characters). I remove space because MySQL do,and 127 because it's backspace and impractical to enter and manage on the different mysql clients (as for accents or ascii>128 characters).
This is for the old-password system, given that the cracker has read access to 16-chars hexadecimal password footprint (mysql.user). But seems that too much people are alway using it!
MySQL's Sergei answer
This is the official answer of Sergei Golubchik, Senior Software Developer
Yes, it's a known issue, the weakness of our old (pre-4.1) password
hashing was one of the main reasons for changing it.
See e.g. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2000-0981
I don't think many people use old passwords nowadays, because new scheme
is the default since 2003.
There's plenty of cases where you have to resort to the old security scheme, with MySQL 4.1 or MySQL 5:
- For PHP4 or PHP3 compatibility
- For PHP5 to enable use of mysql_ functions (that everyone seems to use at this day!)
- Default MySQL5 Ubuntu installation use old-password scheme
- Default MAMP MySQL5 installation use old-password scheme
- I only see ONE new-password, even at my work (a 1 million+ member dating website) we use old for these reasons (php4, php5 and so on)
Answer is politically correct, but in the real-world, you will mainly find old-password footprints in each and every web-related MySQL installation or end-user installation.
EACH AND EVERY INTERNET HOSTING SERVICE HAS TO USE WEAK OLD-PASSWORD for compatibility purpose.
01 novembre 2006
MySQL AB is in touch
I contact MySQL AB concerning the weaknesses I found in the hash function, to determinate the threat level, and later how they could protect mysql and ensure better mysql security
How Mysql store passwords
MySQL store encrypted passwords, using an hash function. We could say that he store password footprint instead real password.
You could find them doing (in mysql client)
use mysql
select Password from user;
You'll see 16 hexadecimal digits (0..9 & a..f), each one representing 64bits theorically and 62bits really (We'll see that later).
To store a password, MySQL encrypt it using the hash function, and store the generated footprint.
When a client program or an user send a password, MySQL encrypt it using the same hash function and compares the newly generated footprint to the stored one.
(This point is really important, when you consider you only have 62bits for the footprint)
The hash function is not bivalent, a password generate one and only one footprint, but a footprint could lead to many passwords (or even none!). It will be very important on the last part, when we will be able to evaluate more than 100 billions footprints per seconds using a monocore Pentium4.
Hash function doesnt allow us to regenerate the password from the footprint, or generate another password having the same footprint. This is the theory, but in practice the hash function will help us discriminate password substrings that could not lead to the right footprint, as this function was not conceived to obfuscate passwords.
Our task will consist in many steps, 4 main steps, all relying on the hash function algorithm, which is the locker, our passwords being the key. To find the key giving it's footprint, we have to understand the locker...
This is for the old-password system, given that the cracker has read access to 16-chars hexadecimal password footprint (mysql.user). But seems that too much people are alway using it!
30 octobre 2006
Mysql Hacking & Chess game
I want to use mysql accounts without knowing their passwords, only the password footprint on the mysql.user tatble. I tried John-the-ripper 1.7.2 with a MySQL patch. He found instantaneously Serguei Pl. account (with a '123456' password! lol! 'was on a 1 million subscriber web site, and the account is named by it's firstname and without ip limitation!), and in one hour the account serguei created for me (with a 'mysql' database select right! lol!). And then 3 days later a test account (with a password besginning with 'test' and full privileges! lol!).
Albeit Serguei Pl. is totally incompetent speaking security (this guy even pretend it's safe to store credit-card informations in the company's server! you see it's password and account?!?), we have a good SysAdmin, Daniel that is competent and responsible : he conly choose random password with 8 or 9 characters (including lowercase, uppercase, digits, and special characters!).
John only enable to attack user-choosen password, with efficiency, but offers no quick solution for random passwords. Trying 10^7 password by second typically on my Pentium4 computer, using John, it could take centuries to break daniel's passwords!
I look at mysql code, at John's patched code, and I found interesting patterns in the hash function. This is more a hash-table hashing function than a password encryption function. Good news!
Next entries will gives you informations about this hash-function features and weaknesses (yes there's many!), and how to crack a fully random 8-characters mysql password within a day, using regular monocore computer. That include:
- Using game-theory algorithms (and the search extension that avoid combinatory explosion)
- Evaluate a position or data-pattern (seems like Chess-game! Russian will love that!)
- Speed-up sequential searches
- Select potentially good searches
- Using multiple account to unlock faster
- And finish with a nice assembly code touch (x86 and/or PowerPC) to reach warp-7 !
Chess-game developper, and notably the On-line chess-game for the International Grand Master Joël Lautier's TV-show, I found a way to use these technologies (mainly combinatory explosion avoiding).
The result? Crack yourself a mysql random 8-character password with a monocore PC in a day, or an 9 characters password within week (with a fast PC! lol!). Seems impossible? We'll see!
This is for the old-password system, given that the cracker has read access to 16-chars hexadecimal password footprint (mysql.user). But seems that too much people are alway using it!