АлгоритмМД5

Black_sun
ищи у себя ошибку в программе. значение MD5 зависит от всех битов

 

1.Проверял? Проверь и дай плз пример где это не сработало. ОК?
2. я чуть ошибся

Код (Text):

1. 127
2. 126
3. 125
4. 124
5. 123
6. 122
7. 121
8.  
9. 119
10. 118
11. 117
12. 116
13. 115
14. 114
15. 113
16.  
17. 111
18. 110
19. 109
20. 108
21. 107
22. 106
23.  
24. 103
25. 102
26. 101
27. 100
28. 99
29.  
30. 97
31.  
32. 95
33. 94
34. 93
35. 92
36.  
37. 89
38.  
39. 87
40. 86
41. 85
42. 83
43. 82
44. 81
45.  
46. 79
47.  
48. 76
49.  
50. 74
51.  
52. 73
53.  
54. 71
55.  
56. 69
57. 68
58. 67
59.  
60. 62
61. 61
62.  
63. 59
64. 58
65. 57
66.  
67. 53
68.  
69. 51
70.  
71. 47
72. 46
73.  
74. 43
75.  
76. 41
77.  
78. 38
79. 37
80.  
81. 34
82.  
83. 31
84.  
85. 29
86.  
87. 23
88.  
89. 19
90.  
91. 17

3. А от куда тогда коллизии?
4. 2^(128-64)=2^64 чуть ошибся:
39614081257132168796771975168 было(до обнаружения ошибки)
18446744073709551616 стало

 

лучше ты приведи пример, где это сработало...

 

Код (Text):

1. 011100110001100011101111110001010111011011011000110000100100101101000111010101000000110101011010110011111101010110001110010110[b]1[/b]0
2. хэш=
3. 11100011011110110111100001101000011100111011101010000110110001110110010101001000110000001100101001100111011010000100111101010101
4.  
5. 011100110001100011101111110001010111011011011000110000100100101101000111010101000000110101011010110011111101010110001110010110[b]0[/b]0
6. хеш=
7. 11100011011110110111100001101000011100111011101010000110110001110110010101001000110000001100101001100111011010000100111101010101

 

2Black_sun

ни одного совпадения. Проверь свой код

Код (Text):

1. #include <stdio.h>
2. #include <windows.h>
3.  
4. #include "md5.h"
5.  
6. #define KBYTE   1024
7. #define MBYTE   KBYTE*1024
8.  
9. #define DATA_SIZE   10*MBYTE
10.  
11. BYTE Data[DATA_SIZE];
12.  
13. int main()
14. {
15.     MD5_CTX ctx1, ctx2;
16.     BYTE Powers[8] = {1, 2, 4, 8, 16, 32, 64, 128};
17.  
18.     ZeroMemory(Data, DATA_SIZE);
19.  
20.     for (int i=0; i<DATA_SIZE; i++)
21.     {
22.         for (int j=0; j<8; j++)
23.         {
24.             MD5Init(&ctx1);
25.             MD5Init(&ctx2);
26.            
27.             MD5Update(&ctx1, Data, DATA_SIZE);
28.             MD5Final(&ctx1);
29.            
30.             Data[i] |= Powers[j];
31.            
32.             MD5Update(&ctx2, Data, DATA_SIZE);
33.             MD5Final(&ctx2);
34.  
35.             Data[i] &= ~(Powers[j]);
36.            
37.             if (!memcmp(ctx1.digest, ctx2.digest, 16))
38.             {
39.                 printf("%d - matched\n", i*8 + j);
40.             }
41.         }
42.     }
43.    
44.     return 0;
45. }

 

Си это конечно же хорошо, но вот хотелось бы узнать что тут происходит. Разбирать чужую программу - дело неблагодарное и муторное.
Приведи пример хеш функции(пароль желательно в бинарном виде запиши напамять ).
А я тем времинем посмотрю что у меня не так.
http://passcracking.ru/index.php - еще один подборщик паролей, хороший но воосновном до 8-ми символов.

 

RTFM RFC1321

 

- я просто так сказал, на замеитку.) интерфейс более понятен, чем на других сайтах.

 

Создается массив размером 10 мбайт. Далее в цикле по всем битам массива рассчитываются два хеша - один для исходного массива, второй - для этого же массива с измененным одним битом. Если оба хеша совпадают, на консоль выводим номер бита (не оказывающего влияние на md5).
Как показывает программка, биты от 0 до 83886080 влияют на хеш.

стандартная реализация из RFC

 

Нашел ошибку, она- в формировании нового хеша (с измененным битом).

 

Обращаем МД5.
Как известно алгоритм данной функции является односторонним, но сейчас мы попробуем его братить, зная тоько что его длинна будет у нас 128 бит. Рассмотрим пошагово:
1. Разбиваем данную(т.е. сам хеш) нам строку по блокам 32 бита и находим переменные ABCD до того как к ним был добавленн значение буфера(проводится быстро и довольно понятно, может я как нибудь нитак выразился, если вам не понятно).
2. Конечные значения ABCD мы получили теперь начинаем путь назад
BCDA 9 21 64
b = c + ((b+ I(c,d,a) + X[9] + T[64]) <<< 21)
Неизвестно у нас только b(Х=0 т.к. длинна 128 бит).
Вичислить его достаточно просто
(b -с) <<< 11=((b+ I(c,d,a) + X[9] + T[64]))<<< (11+21=32=0)
(b -с) <<< 11=((b+ I(c,d,a) + X[9] + T[64]))
b=((b -с) <<< 11)- I(c,d,a) - X[9] - T[64]
b=((b -с) <<< 11)- I(c,d,a) - T[64]
а дальше у нас появляется камень предкновения:
CDAB 2 15 63
с = d+ ((c+ I(d,a,b) + X[2] + T[63]) <<< 15)
Тут у нас уже 2 переменные, а как известно такие уравнение имеет ооочень много решений, это видно из уравнения:
c=((c -d) <<< 17)- I(d,a,b) - T[63]- X[2] (1).
Для наглядности ((c -d) <<< 17)- I(d,a,b) - T[63]=const
c=const-X[2]
const-c=X[2] (2)
поэтому подним свои глаза в самый верх(в начало вычисления хеша: 1 раунд 3 операция):
CDAB 2 17 3
(заметте 17+15=32, так к слову)
с1 = d+ ((c+ I(d,a,b) + X[2] + T[3]) <<< 15)
Тут сложновато, но можно сказть даже наоборот,поэтому приведем к тому же виду
Получим:
c1-const2=X[2] (3)
(в конст2 вы наверное поняли что находится, и конечно нам его придется вычислять, но об этом чуть позже)
Теперь зная что х2:х2=1 найдем отношения уравнений 2 и 3:
(const-c):c1-const2=1
Частное решение которого является:
c=const2 (4)
c1=const
Следовательно Х[2]=const -const2
с=d+ ((c+ I(d,a,b) + ((c -d) <<< 17)- I(d,a,b) - T[63]+T[63]-const2)<<<15

 

Вот продолжение:

- из данного выражения следует что константа2 должна быть меньше константы1, но это необязательно так как отрицательных чисел в данном случае не существует. Так как консанту1 можно вычислить(напомню что она равна ((c -d) <<< 17)- I(d,a,b) - T[63]). То все дело встает за вычислением второй "константы":
const2=(d<<<17)+c+i(d,a,b)+T[3]
Х[2]=const -const2
Подставим в выражение значения констант:
Х[2]=(c' -d') <<< 17)- I'(d,a,b) - T[63]-(d<<<17)-c-i(d,a,b)-T[3]
как видно остается одна неизвестная, состоящая из 2х зависимых переменных, котрые мы вичисляем по циклу(какой цикл использовать это уже зависит от того какой входной поток мы хотим найти, к примеру по нахождении пароля используещго ассии(аски или ацки код) код понадобится ~2^40 операций+ советую ввести проверку полученного Х на коррректность, т.е. что бы значение каждого байта не превосходило 127 и было больше 32)
Найдя х2 и зная что "с" предыдущее равно константе 2 проверим справедливость равенства
с = d+ ((c+ I(d,a,b) + X[2] + T[63]) <<< 15), заранее вычислив х и с(хотя можно просто вычислить "с" обратив данную формулу и продолжать).
теперь все гораздо проще
[ABCD 4 6 61]
Х по условию равно"10000000000000000000000000000000"- в двоичном коде
Далее идут 4 операции [ABCD 8 6 57][DABC 15 10 58][CDAB 6 15 59][BCDA 13 21 60] - тут х=0
[BCDA 1 21 56] - помните мы уже вычислили х1
[CDAB 10 15 55] - х=0
DABC 3 10 54 - тут производим аналогичные вычисления(так как мы вычисляли х2, но тут уже все константы известны)
[BCDA 5 21 52] [ABCD 12 6 53] - так же х=0
CDAB 14 15 51 - по умолчанию 128 бит был у нас входной поток
DABC 7 10 50 - х=0
ABCD 0 6 49 - мы уже вычислили(точнее попытались предугодать) х0 уже в самом начале.