Привет всем юзверям античатаЩас я раскажу об MD5 хешах Вступление: Данный алгоритм шифрования является алгоритмом вычисления "хэш" функции (message digest). В качестве входных данных он принимает сообщение произвольной длины, и вычисляет 128-битный хэш. Нахождение двух различных входных строк, которые производили бы одинаковый MD5 хэш, или нахождение исходной строки по существующему хэш, представляется почти невозмжным (точнее, этим можно заняться имея огромные вычислительные ресурсы, плюс достаточный запас времени). MD5 алгоритм используется в приложениях криптографии и электронно-цифровых подписей для генерации ключа шифрования. Далее под "словом" будет подразумеваться количество информации в 32 бита, а под "байтом" - 8 бит. Последовательность бит интерпретируется в естественной форме - как последовательность байт, где каждая группа из 8 бит является отдельным байтом, причём старший бит байта идет первым. Аналогично представляется последовательность байт, как последовательность слов, только младший байт идет первым. Предпологается, что в качестве входного потока имеется поток данных N бит. N - неотрицательное целое (возможно 0), не обязательно кратное 8. Для вычисления MD5 хэш функции, неоходимо выполнить следующие 5 шагов. Шаг первый: выравнивание потока. Входной поток выравнивается так, чтобы его длина стала сравнимой с 448 по модулю 512. Выравнивание происходит следующим образом: к потоку добавляется один бит '1', а затем биты '0' до тех пор, пока длина потока не будет сравнима с 448 по модулю 512. Выравнивание происходит всегда, даже если длина потока была уже сравнима с 448 по модулю 512. Таким образом к потоку добавляется минимум 1 бит, максимум - 512. Шаг второй: добавление длины. 64 битное представление длины входного потока добавляется к результату предидущего шага. Если длина потока превосходит 2^64, то добавляются младшие 64 бит. Эти биты добавляются как 2 32-битных слова, младшее слово добавляется первым. Таким образом на этом шаге длина потока становится кратной 512 битам или 16 32-битным словам. Далее будем рассматривать входной поток как массив M[0 ... N-1] слов длиной N. Шаг третий: инициализация MD буфера. Буфер из 4 слов {A, B, C, D} используется для вычисления хэш функции, который инициализируется в следующие значения: A = 0x67452301 B = 0xEFCDAB89 C = 0x98BADCFE D = 0x10325476 Шаг четвёртый: обработка потока блоками по 16 слов. Теперь определим четыре вспомогательные функции, каждая из которых принимает три параметра размеров в слово и производит результат - слово. F(x, y, z) = (x & y) | (~x & z) G(x, y, z) = (x & z) | (y & ~z) H(x, y, z) = x ^ y ^ z I(x, y, z) = y ^ (x | ~z) Напомню, что & - побитовое И, | - побитовое ИЛИ, ^ - побитовое исключающее ИЛИ, ~ - побитовое отрицание. Функция F для каждого бита дает следующий результат: если X, то Y, иначе Z. На этом шаге также используется таблица T[1..64], которая построена с помощью функции синуса: T<i> = int(4294967296 * abs(sin(i))), где int() - целая часть. Например: T[1] = int(4294967296 * abs(sin(i))) = int(3614090360,282...) = 3614090360. Также следует определить операцию x <<< y, как циклический сдвиг x влево на y бит. Теперь рассмотрим сам алгоритм вычисления MD5 хэш функции. // обработать входной поток блоками по 16 слов for i = 0 to N/16 - 1 do { // копировать блок i в X for j = 0 to 15 do X[j] = M[i * 16 + j] // Сохранить значения A, B, C, D AA = A BB = B CC = C DD = D // проход 1 // пусть [abcd k s i] обозначает операцию // a = b + ((a + F(b, c, d) + X[k] + T<i>) <<< s) // исполнить 16 следующих операций [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] // проход 2 // пусть [abcd k s i] обозначает операцию // a = b + ((a + G(b, c, d) + X[k] + T<i>) <<< s) // исполнить 16 следующих операций [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] // проход 3 // пусть [abcd k s i] обозначает операцию // a = b + ((a + H(b, c, d) + X[k] + T<i>) <<< s) // исполнить 16 следующих операций [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36] [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40] [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48] // проход 4 // пусть [abcd k s i] обозначает операцию // a = b + ((a + I(b, c, d) + X[k] + T<i>) <<< s) // исполнить 16 следующих операций [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52] [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56] [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60] [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64] A += AA B += BB C += CC D += DD } Шаг пятый: вывод MD5. Результат вычисления представлен четырьмя 32 битными словами - A, B, C, D (младшим записывается A, старшим - D). 128-битный MD5 хэш готов ! Примеры: "a" - cc175b9c0f1b6a831c399e269772661 "abc" - 90150983cd24fb0d6963f7d28e17f72 "abrakadabra" - bda3bfdfa868d04f403838f5776f25e "123456789012345678901234567890123456789012345678901234567890123456 78901234567890" - 57edf4a22be3c955ac49da2e217b67a Вот вроде и всё. (c) http://inattack.ru/
вот реализация md5 на жаба=скрипте, http://www.slil.ru/upload/23671134 юзается в вобле, чтобы не передавать пасс по сети в открытом виде)
Дополнение... Дополню немного подредактированным FAQ из PasswordsPRO. FAQ Q1: У меня есть хэш "XXXYYYZZZ". Какой у него тип (т.е. алгоритм хэширования)? A: 1) Ниже перечислены некоторые типы хэшей: если хэш начинается с сигнатуры "$1$", то обычно это MD5 (Unix) хэш. если хэш начинается с сигнатуры "$apr1$", то обычно это MD5 (APR) хэш. если хэш имеет длину 8 байт, то это может быть MySQL-хэш или любой более длинный хэш, "урезанный" до длины 8 байт - например, MD5-хэш. длину 16 байт обычно имеют следующие типы хэшей: -MD2, MD4, MD5, LM, NT и другие алгоритмы; -некоторые SALT'овые алгоритмы, например, md5(md5($pass).$salt); -некоторые составные алгоритмы, например, md5(md5($pass)) и др. если хэш имеет длину 20 байт, то это может быть SHA-1, MySQL5 и др. 2) Иногда хэш может быть в Base64-кодировке (а не в стандартном HEX-виде) и для более точного анализа его необходимо преобразовать в текстовый вид. Для этого также можно использовать вышеупомянутый сервис или соответствующий инструмент в программе. Q2: Если я могу быстро вычислить хэш от своего пароля, то почему я не могу быстро сделать обратную операцию - вычислить пароль на основе хэша? Любой алгоритм хэширования фактически представляет собой подсчет контрольной суммы от исходного текста. При этом используются необратимые математические операции над исходным сообщением, такие как AND и др. Например, даже если в выражении "X AND Y = Z" мы знаем Y и Z, то мы никогда не сможем по ним точно восстановить исходное значение X (максимум, что мы можем - это рассчитать область возможных значений X, удовлетворяющих данному равенству). Это одна из причин, почему обратное преобразование "хэш -> пароль" невозможно (теоретически, можно лишь рассчитать область возможных исходных паролей, но на практике это нереальная задача). Вторая же причина, почему невозможно абсолютно точно вычислить исходный пароль на основе хэша - это коллизии. Что такое коллизии? Так как область выходных значений (всевозможных хэшей) в любом алгоритме хэширования является величиной конечной и определяется размером хэша (к примеру, для алгоритма MD5 количество возможных хэшей составляет 2128 или 3.4*1038 вариантов), а количество входных значений (исходных сообщений) - величина бесконечная, то само собой существуют такие исходные сообщения, которым соответствует один и тот же хэш. Такие исходные сообщения и называются коллизиями. Что такое SALT и SALT-овые хэши? SALT (или так называемая "привязка") в основном используется для того. чтобы пользователи, использущие одинаковые пароли, имели различные хэши. Как правило, SALT - это строка из 4...8 случайных символов, которая дополнительно используется для хэширования паролей пользователей и сохраняется вместе с финальным хэшем (как, к примеру, сделано в MD5 (Unix)-хэшах) или же хранится отдельно от хэша. Почему у SALT'овых хэшей низкая скорость перебора? В крайне упрощенном виде перебор паролей к обычным (не-SALT'овым) хэшам происходит так - однократно подсчитывается хэш от текущего пароля, а затем хэш многократно сравнивается со всеми перебираемыми хэшами. При восстановлении же паролей к SALT'овым хэшам текущий пароль приходится хэшировать отдельно для каждого пользователя, т.к. у них разные SALT'ы. Само собой, скорость любой атаки при этом будет снижена пропорционально количеству пользователей. Почему у MD5 (Unix) и MD5 (APR) хэшей низкая скорость перебора? Это связано с тем, что помимо использования SALT'ов, эти хэши формируются в цикле на 1000 итераций, в каждой из которых вызывается от 2 до 4 обычных MD5-преобразований. В результате скорость атаки для таких хэшей в тысячи раз ниже по сравнению с обычными MD5-хэшами. Где используются хэши, имеющие в PasswordsPro суффикс PHP: ? [/COLOR] Суффикс [PHP] указывает на то, что эти алгоритмы по своему синтаксису соответствуют PHP-коду, в котором они обычно и применяются: - md5(md5($pass)) [PHP] - используется в форуме e107. - md5(md5($pass).$salt) [PHP] - используется в форуме vBulletin 3.x.x. - md5(md5($salt).md5($pass)) [PHP] - используется в форуме IPB 2.x.x. [COLOR=Yellow]Что такое "словари" и где их взять? [/COLOR] Словарь - это текстовый файл, в котором находятся возможные пароли пользователей (одна строка файла - один пароль). Это могут быть как часто употребляемые пароли ("admin", "master" и др.) так и пароли из нужного диапазона символов ("1111" - "9999"), которые можно сгенерировать внешней утилитой "Генератор словарей". про словари смотри ссылки: https://forum.antichat.ru/thread13640.html http://www.insidepro.com/rus/download.shtml
