Problems with the password hashing algorithm used in Apache Derby



Important note: Derby 10.6.1.0 (released 19-May-2010) addresses the problem described bellow. CVE-2009-4269 was assigned to this vulnerability.



Apache Derby is an open source relational database implemented in Java and available under the Apache License, Version 2.0. Derby is based on the JDBC, and SQL standards. Derby provides an embedded JDBC driver that can be used in any Java-based solution. Derby also supports the client/server mode with the Derby Network Client JDBC driver and Derby Network Server.

The password hash generation algorithm used in Derby to store passwords in the database has weaknesses. This article gives a detailed description of the security-related problems caused by the transformation used before generating the SHA-1 hash from passwords. It is easy to find two passwords with the same password hash (collision). The used transformation significantly reduces the computational complexity of cracking passwords. The resource requirements for successful on-line password cracking attacks can easily be satisfied by a low-end PC.

The source code of Derby is available for download at "http://db.apache.org/derby/derby_downloads.html". The password hash generation algorithm is implemented in [source_path]/java/engine/org/apache/derby/impl/jdbc/authentication/AuthenticationServiceBase.java in the encryptPassword() method. The method generates an SHA-1 hash from the given password after calling the toHexByte() method from [source_path]/java/engine/org/apache/derby/iapi/util/StringUtil.java, which performs the transformation described bellow. The password hash will be the concatenation of constant hexadecimal bytes (always "0x3b60") and the SHA-1 hash.

The toHexByte function divides every byte of the password string (ASCII code of the given character) into two half bytes (one half byte is based on the higher 4 bits, the other uses the lower 4 bits). For example the ASCII code of 'a' is 0x61, the two half bytes will be 0x6 and 0x1, the function will store those in two bytes (the high part will be stored first): 0x01, 0x06. The function performs this to each byte of the original password and stores the resulting two bytes consecutively in a way that the higher part of the actual character overwrites the lower part of the previous one, the final position in the resulting byte array is increased only by one(!) for every new character. The toHexByte function allocates two times the length of the original password for the result bytes. The remaining bytes are set to zero.

An example for generating the hash (password is "Test12"):
char[0]: T
050400000000000000000000
char[1]: e
050605000000000000000000
char[2]: s
050607030000000000000000
char[3]: t
050607070400000000000000
char[4]: 1
050607070301000000000000
char[5]: 2
050607070303020000000000
bytePasswd: 050607070303020000000000
encryptVal: eda923065a6c95b860d646ebf12d896fa5add7bc
Return value: 3b60eda923065a6c95b860d646ebf12d896fa5add7bc

As the algorithm considers only the upper 4 bits for the characters of passwords (except the last one), the resulting hash will be the same if the ASCII code for the characters differs only in the lower 4 bits. For example the resulting hash for all the passwords in the following list: "APASS", "BPASS", "CPASS", ... "NPASS", "OPASS" will be the same. The hash for "PPASS" will be a different one. The hash for password "PPASS" will be the same as for "QPASS", .. "YPASS", "ZPASS". If we consider more character positions, the hash for password "Test12" will be the same as for any password matching "[Q-Z][a-p][q-z][q-z][0-9]2". As we can see, finding collisions is easy.

Examples of passwords and their hashes:
Password: Hash
APASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
BPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
CPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
DPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
EPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
FPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
GPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
HPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
IPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
JPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
KPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
LPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
MPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
NPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
OPASS: 3b60cb484c002b5f9ee655da908c7dc2871fb76f9587
PPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
QPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
RPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
SPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
TPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
UPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
VPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
WPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
XPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
YPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b
ZPASS: 3b6053c259320da5fdec1ba26ef6d28c9a693006c50b

As the lower half bytes are overwritten (except for the last character in the original password), the possible number of resulting password hashes for password length n is 16^(n+1). This value is 16^8=4294967296 for passwords of length 7. This number is smaller if we consider only passwords containing printable special characters, letters and numbers. The ASCII values for those are between 0x20 and 0x7E. The possible values for the higher half bytes are: 0x2,0x3,0x4,0x5,0x6,0x7 which makes only 6 possibilities. The possible number of resulting password hashes for passwords of length 7 is 6^7*16=4478976. This is a very low number for off-line brute forcing, it can be checked in less than a second on a commodity PC.

The following comparison shows the result of the applied transformation regarding the on-line and off-line password cracking complexity for 8 character long passwords. Possible number of 8 character long passwords containing upper case letters (26 possible values), lower case letters (26 possible values) and numbers (10 possible values) is 62^8=218340105584896. Using Derby password hashing, the possible number of hashes generated from 8 character long passwords (using the same character set) is 6^8*16=26873856. The complexity of cracking is reduced by a factor of (62^8)/(6^8*16)=8124628. This means that a cracker needs to try 8124628 times less possible values for 8 character long passwords due to the transformation implemented in the toHexByte() method.


APPENDIX: The source code of encryptPassword and toHexByte functions

protected String encryptPassword(String plainTxtUserPassword)
{
if (plainTxtUserPassword == null)
return null;

MessageDigest algorithm = null;
try
{
algorithm = MessageDigest.getInstance("SHA-1");
} catch (NoSuchAlgorithmException nsae)
{
// Ignore as we checked already during service boot-up
}

algorithm.reset();
byte[] bytePasswd = null;
bytePasswd = StringUtil.toHexByte(
plainTxtUserPassword,0,plainTxtUserPassword.length());
algorithm.update(bytePasswd);
byte[] encryptVal = algorithm.digest();
String hexString = ID_PATTERN_NEW_SCHEME +
StringUtil.toHexString(encryptVal,0,encryptVal.length);
return (hexString);

}

public static byte[] toHexByte(String str, int offset, int length)
{
byte[] data = new byte[(length - offset) * 2];
int end = offset+length;

for (int i = offset; i < end; i++)
{
char ch = str.charAt(i);
int high_nibble = (ch & 0xf0) >>> 4;
int low_nibble = (ch & 0x0f);
data[i] = (byte)high_nibble;
data[i+1] = (byte)low_nibble;
}
return data;
}