Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | | | | |
хе.. 14.12.01 17:47 Число просмотров: 3404
Автор: zelych Статус: Member
|
|
|
|
<theory>
|
hash 13.12.01 13:29
Автор: nimrod Статус: Незарегистрированный пользователь
|
Вчера ковырял одну ламерскую программку и наткнулся вот на такую штуку
int fu(int x1,int x2)
{ int a,b,c,d,i,j=0;
do{ a=0;
b=x1&0x80000057;
for(i=0;i<0x20;i++) {if(b&1)a++; b>>=1;}
x1=(x1>>1)&0x7fffffff;
if(a&1)x1|=0x80000000;
a=0; c=x2&x1;
for(i=0;i<0x20;i++) {if(c&1)a++; c>>=1;}
d=(d<<1)a&1);
}while(++j!=0x20);
return d;
}
int hash(int *b)
{ int x,y,i=0;
x=b[0];
do{y=b[++i]; x=fu(x,y);}while(i!=0x100);
return x;
}
Что с этим можно сделать? Не пхоже что алгоритм стойкий.
Спасибо если кто ответит
|
|
hash 13.12.01 15:06
Автор: iddqd <Юрий> Статус: Member
|
> Вчера ковырял одну ламерскую программку и наткнулся вот на
> такую штуку
>
> int fu(int x1,int x2)
> { int a,b,c,d,i,j=0;
> do{ a=0;
> b=x1&0x80000057;
> for(i=0;i<0x20;i++) {if(b&1)a++;
> b>>=1;}
> x1=(x1>>1)&0x7fffffff;
> if(a&1)x1|=0x80000000;
> a=0; c=x2&x1;
> for(i=0;i<0x20;i++) {if(c&1)a++;
> c>>=1;}
> d=(d<<1)a&1);
> }while(++j!=0x20);
> return d;
> }
> int hash(int *b)
> { int x,y,i=0;
> x=b[0];
> do{y=b[++i]; x=fu(x,y);}while(i!=0x100);
> return x;
> }
>
> Что с этим можно сделать? Не пхоже что алгоритм стойкий.
> Спасибо если кто ответит
долго разбираться не стал, но, на первый взгляд, у нее будет очень много повторяющихся результатов, слишком уж много" и "&", а они необратимы. возможно, я ошибаюсь
попробуй просто в лоб. перебери пару десятков тысяч вариантов и посмотри, какой результат чаще всего повторяется и при каких значениях
|
| |
hash 13.12.01 16:59
Автор: nimrod Статус: Незарегистрированный пользователь
|
> долго разбираться не стал, но, на первый взгляд, у нее
> будет очень много повторяющихся результатов, слишком уж
> много" и "&", а они необратимы. возможно, я ошибаюсь
Не похоже, заполнял b[i]=(rand()<<16)|rand(), посчитал полторы тыщи хешей, количество нулей и единиц в каждом бите ОЧЕНЬ близко к половине
Единственное что заметил, если в b есть шесть или больше идущих подряд нулей - тогда хеш всегда равен нулю
> попробуй просто в лоб. перебери пару десятков тысяч
> вариантов и посмотри, какой результат чаще всего
> повторяется и при каких значениях
|
| | |
hash 13.12.01 17:24
Автор: iddqd <Юрий> Статус: Member
|
> Не похоже, заполнял b[i]=(rand()<<16)|rand(),
> посчитал полторы тыщи хешей, количество нулей и единиц в
> каждом бите ОЧЕНЬ близко к половине
> Единственное что заметил, если в b есть шесть или больше
> идущих подряд нулей - тогда хеш всегда равен нулю
ну это уже хорошо ;)
а если сделать по-другому: составить булеву матрицу, по которой идет хеширование и по-немногу изменять ее (достроив до квадратной), пока у нее определитель не станет ненулевой, т.е. когда ей можно найти обратную, а там, может быть, проще будет. по крайней мере, можно будет прикинуть (на глаз) как она перемешивает. а потом применить что-то вроде дифференциального криптоанализа, она же (эта матрица) получается перемножением нескольких простых матриц.
З.Ы. С криптоанализом знаком только поверхностно, а потому могу сильно ошибаться
|
| | | |
hash 13.12.01 17:42
Автор: nimrod Статус: Незарегистрированный пользователь
|
> > Не похоже, заполнял b[i]=(rand()<<16)|rand(),
> > посчитал полторы тыщи хешей, количество нулей и единиц
> в
> > каждом бите ОЧЕНЬ близко к половине
> > Единственное что заметил, если в b есть шесть или
> больше
> > идущих подряд нулей - тогда хеш всегда равен нулю
> ну это уже хорошо ;)
>
> а если сделать по-другому: составить булеву матрицу, по
> которой идет хеширование и по-немногу изменять ее (достроив
> до квадратной), пока у нее определитель не станет
> ненулевой, т.е. когда ей можно найти обратную, а там, может
> быть, проще будет. по крайней мере, можно будет прикинуть
> (на глаз) как она перемешивает. а потом применить что-то
> вроде дифференциального криптоанализа, она же (эта матрица)
> получается перемножением нескольких простых матриц.
>
> З.Ы. С криптоанализом знаком только поверхностно, а потому
> могу сильно ошибаться
Не особо понял что ты сказал, но если хешируемый блок изменить на один бит, то хеш в меняется на 13- 20 бит..
|
| | | | |
hash 13.12.01 17:59
Автор: iddqd <Юрий> Статус: Member
|
> Не особо понял что ты сказал, но если хешируемый блок
да я уже сам запутался %)
> изменить на один бит, то хеш в меняется на 13- 20 бит..
ну, вообще, так и должно быть
другое дело, по какому закону все это меняется, я же говорю: матрицу построй, вдруг она там из кучи диагоналий состоит
а вообще, лучше применить дифференциальный криптоанализ, IMHO
|
| | | | | |
hash 13.12.01 18:09
Автор: nimrod Статус: Незарегистрированный пользователь
|
> > Не особо понял что ты сказал, но если хешируемый блок
> да я уже сам запутался %)
> > изменить на один бит, то хеш в меняется на 13- 20
> бит..
> ну, вообще, так и должно быть
> другое дело, по какому закону все это меняется, я же
> говорю: матрицу построй, вдруг она там из кучи диагоналий
> состоит
> а вообще, лучше применить дифференциальный криптоанализ,
> IMHO
а если порусски?
я наверное не настолько умный, потому и обращаюсь к вам..
|
| | | | | | |
hash 13.12.01 18:33
Автор: iddqd <Юрий> Статус: Member
|
> а если порусски?
ну, постораюсь ;)
> я наверное не настолько умный, потому и обращаюсь к вам..
да я, собственно, тоже не настоко умный в этом деле ;)
короче, я бы сделал так:
составил вектор, где верхняя часть разрядов состоит из х1, а нижняя из х2 (или наоборот)
представил каждое действие, например "x1=(x1>>1)&0x7fffffff", как матрицу
из всех этих матриц, в соответствии с алгоритмом, составил одну большую, на которую умножается вектор, и возвел бы ее в 32-ю степеть
то, что из нее получится, а получится, соответствено, матрица, и нужно смотреть
или расковырять сам текст проги и подставить туда вместо каждого бита, какую-нибудь метку,
а все действия заменить на конкатенацию меток и самих действий("&"," и т.п.)
проще, говоря сделать из нее простенький компилятор матриц
можно попробовать нагенерить кучу хешей и по аргументам и результатам, решив систему уравнений сгенерить эту злосчастную матрицу
|
| | | | | | | |
hash 14.12.01 12:34
Автор: zelych Статус: Member
|
всё значительно проще..
если тебе надо поменять хешируемый блок и получить определённое значение хеша, тогда вот:
int hash(int *b)
{ int x,y,i=0;
x=b[0];
do{y=b[++i]; x=fu(x,y);}while(i!=0x100);
return x;
}
если поменять b[a] на b`[a], то поменяется x начиная с i-ой итерации, соответственно надо найти такое у, что fu( b`[a], y ) = fu( b[a], b[a+1] ) и поставить его вместо b[a+1]..
получается уравнение:
дано - x и fu( x, y )
найти - y
int fu(int x1,int x2)
{ int a,b,c,d,i,j=0;
do{ a=0;
b=x1&0x80000057;
for(i=0;i<0x20;i++) {if(b&1)a++; b>>=1;}
//
x1=(x1>>1)&0x7fffffff;
// не совсем понятно зачем нужно &0x7ffff
if(a&1)x1|=0x80000000;
/* а вообще очень смахивает на регистр сдвига с полиномом обратной связи 0x80000057 и начальным заполнением x1
однако это не важно
*/ a=0; c=x2&x1;
for(i=0;i<0x20;i++) {if(c&1)a++; c>>=1;}
// а вот здесь a&1 - это скалярное произведение x2 и x1
d=(d<<1)a&1);
}while(++j!=0x20);
return d;
}
что из этого следует:
d(32-i) = <x2, x1(i+1)>, для i=0..31.
d(i) - i-й бит из d;
<.,.> - скалярное произведение;
x1(i) - регистр сдвига сдвинутый i раз.
получается 32 уравнения и 32 неизвестных..
решается очень просто:
пишем матричное уравнение
(D) = (X2)(X1)
d - строка из 32-х элементов
x2 - столбец
x1 - матрица 32х32, в которой i-я строка равна x1(i+1)
решаем матричное уранение:
(X2) = (D)(X1`), где X1` - матрица обратная к X1..
вот и всё..
P.S. глядя на исходник подумалось: "а зачем вообще люди пробелы придумали?"
|
| | | | | | | | |
А может программку напишешь, ато я не совсем разобрался?. 14.12.01 16:20
Автор: nimrod Статус: Незарегистрированный пользователь
|
|
|
| | | | | | | | | |
если ты всё ещё не разобрался, и если оно тебе всё ещё надо, то попробую что-нибудь написать.. 19.12.01 11:10
Автор: zelych Статус: Member
|
|
|
| | | | | | | | | |
хе.. 14.12.01 17:47
Автор: zelych Статус: Member
|
|
|
| | | | | | | | |
hash 14.12.01 13:02
Автор: iddqd <Юрий> Статус: Member
|
> всё значительно проще..
> если тебе надо поменять хешируемый блок и получить
> определённое значение хеша, тогда вот:
>
> int hash(int *b)
> { int x,y,i=0;
> x=b[0];
> do{y=b[++i]; x=fu(x,y);}while(i!=0x100);
> return x;
> }
>
> если поменять b[a] на b`[a], то поменяется x начиная с i-ой
> итерации, соответственно надо найти такое у, что fu(
> b`[a], y ) = fu( b[a], b[a+1] ) и поставить его вместо
> b[a+1]..
> получается уравнение:
> дано - x и fu( x, y )
> найти - y
>
> int fu(int x1,int x2)
> { int a,b,c,d,i,j=0;
> do{ a=0;
> b=x1&0x80000057;
> for(i=0;i<0x20;i++) {if(b&1)a++;
> b>>=1;}
> //
> x1=(x1>>1)&0x7fffffff;
> // не совсем понятно зачем нужно &0x7ffff
> if(a&1)x1|=0x80000000;
> /* а вообще очень смахивает на регистр сдвига с полиномом
> обратной связи 0x80000057 и начальным заполнением x1
я тормоз %) это же он и есть (регистр сдвига)!!
до какого-то времени считался достаточно стойким алгоритмом
в принципе это уже можно считать ответом, если не учитывать 0x80000057 (непонятно какой у него период)
> однако это не важно
не, помоему это важно, изначально вопрос ставился о стойкости алгоритма
> */ a=0; c=x2&x1;
> for(i=0;i<0x20;i++) {if(c&1)a++;
> c>>=1;}
> // а вот здесь a&1 - это скалярное произведение x2 и x1
если я правильно понял, это умножение на строку матрицы, или я опять что-то перепутал?
> d=(d<<1)a&1);
> }while(++j!=0x20);
> return d;
> }
>
> что из этого следует:
>
> d(32-i) = <x2, x1(i+1)>, для i=0..31.
> d(i) - i-й бит из d;
> <.,.> - скалярное произведение;
> x1(i) - регистр сдвига сдвинутый i раз.
>
> получается 32 уравнения и 32 неизвестных..
>
> решается очень просто:
> пишем матричное уравнение
>
> (D) = (X2)(X1)
> d - строка из 32-х элементов
> x2 - столбец
> x1 - матрица 32х32, в которой i-я строка равна x1(i+1)
>
> решаем матричное уранение:
> (X2) = (D)(X1`), где X1` - матрица обратная к X1..
> вот и всё..
>
> P.S. глядя на исходник подумалось: "а зачем вообще люди
> пробелы придумали?"
да там, видимо, тег "pre" забыли поставить ;)
>
а вообще, классный ответ!!!! ;)
|
| | | | | | | | | |
Urix, a ты не автор статьи Гипотеза о стойкости RSA ? 14.12.01 18:54
Автор: Alban Статус: Незарегистрированный пользователь
|
Ну и как, ты разобрался со своими заблуждениями относительно RSA,
если это ты конечно? :)))
|
| | | | | | | | | | |
Urix, a ты не автор статьи Гипотеза о стойкости RSA ? 17.12.01 09:29
Автор: iddqd <Юрий> Статус: Member
|
> Ну и как, ты разобрался со своими заблуждениями
> относительно RSA,
> если это ты конечно? :)))
не, это не я ;) меня постоянно путают с тем URIX'ом ;))))
а по поводу недостаточной стойкости RSA у меня несколько другое мнение, видимо, тоже ошибочное ;)
|
| | | | | | | | | |
hash 14.12.01 13:21
Автор: zelych Статус: Member
|
[..skip..]
> > /* а вообще очень смахивает на регистр сдвига с
>> полиномом
> > обратной связи 0x80000057 и начальным заполнением x1
> я тормоз %) это же он и есть (регистр сдвига)!!
> до какого-то времени считался достаточно стойким алгоритмом
> в принципе это уже можно считать ответом, если не учитывать
> 0x80000057 (непонятно какой у него период)
а хрен его знает, но я думаю что не проблема найти примитивный полином, так что скорее всего период максимальный (2^32-1)..
> > однако это не важно
> не, помоему это важно, изначально вопрос ставился о
> стойкости алгоритма
ну дырка, как мне кажется, здесь не в этом, а в том, что вся матрица (X1) запросто генерируется при известном х1..
> > // а вот здесь a&1 - это скалярное произведение x2 и
> >x1
> если я правильно понял, это умножение на строку матрицы,
> или я опять что-то перепутал?
точно-точно, <X,Y> = X1Y1+X2Y2+...+XnYn
|
| | | | | | | | | | |
hash 14.12.01 13:37
Автор: iddqd <Юрий> Статус: Member
|
> [..skip..]
> > > /* а вообще очень смахивает на регистр сдвига с
> >> полиномом
> > > обратной связи 0x80000057 и начальным заполнением
> x1
> > я тормоз %) это же он и есть (регистр сдвига)!!
> > до какого-то времени считался достаточно стойким
> алгоритмом
> > в принципе это уже можно считать ответом, если не
> учитывать
> > 0x80000057 (непонятно какой у него период)
>
> а хрен его знает, но я думаю что не проблема найти
> примитивный полином, так что скорее всего период
> максимальный (2^32-1)..
>
> > > однако это не важно
> > не, помоему это важно, изначально вопрос ставился о
> > стойкости алгоритма
>
> ну дырка, как мне кажется, здесь не в этом, а в том, что
> вся матрица (X1) запросто генерируется при известном х1..
т.е., по идее, можно нагенерить кучу уникальных матриц, если они часто повторяются.
а повторяться они должны. по крайней мере можно взять тот факт, что при шести нулях подряд, хэш возвращает ноль
или смысл не в этом?
>
> > > // а вот здесь a&1 - это скалярное произведение
> x2 и
> > >x1
> > если я правильно понял, это умножение на строку
> матрицы,
> > или я опять что-то перепутал?
>
> точно-точно, <X,Y> = X1Y1+X2Y2+...+XnYn
|
| | | | | | | | | | | |
hash 14.12.01 13:54
Автор: zelych Статус: Member
|
> т.е., по идее, можно нагенерить кучу уникальных матриц,
> если они часто повторяются.
> а повторяться они должны. по крайней мере можно взять тот
> факт, что при шести нулях подряд, хэш возвращает ноль
> или смысл не в этом?
ну количество таких матриц (X1) равно 2^32 (т.к. существует прямое отображение x1 -> (X1) посредством регистра сдвига)..
а на самом деле, я хотел сказать, что если матрица (X1) не генерировалась так легко из х1, то получилась бы система с неизвестными переменными и коэффициентами при них..
тоесть сама схема изначально дырявая..
|
| | | | | | | | | | | | |
hash 14.12.01 15:41
Автор: iddqd <Юрий> Статус: Member
|
|
теперь вроде понял ;)
|
| | | | | | | | | | | | | |
2ALL: люди вопрос на ящик пива.. 14.12.01 19:23
Автор: zelych Статус: Member
|
собственно говоря, почти та же самая прога, только чуть-чуть по-другому:
int fu( int x1, int x2 )
{
int a, b, c, d, i, j=0;
int x1_, x2_;
x1_ = x1;
x2_ = x2;
do{
a = 0;
b = x1_&0x80000057;
for( i = 0; i < 32; i++ ) {
if( b&1 ) a++
b >>= 1;
}
x1_ = (x1_>>1) & 0x7fffffff;
if( a&1 ) x1_ |= 0x80000000;
a = 0;
b = x2_ & 0x80000057;
for( i = 0; i < 32; i++ ) {
if( b&1 ) a++
b >>= 1;
}
x2_ = (x2_>>1) & 0x7fffffff;
if( a&1 ) x2_ |= 0x80000000
a=0;
b = x1_ & x2;
for( i=0; i < 32; i++ ) {
if( b&1 ) a++;
b >>= 1;
}
c = 0;
b = x2_ & x1;
for( i=0; i < 32; i++ ) {
if( b&1 ) c++;
b >>= 1;
}
d = (d<<1) | ((a&1) ^ ~(c&1));
} while( ++j != 0x20 );
return d;
}
int hash(int *b)
{ int x,y,i=0;
x=b[0];
do{y=b[++i]; x=fu(x,y);}while(i!=0x100);
return x;
}
вообщем кто сломает тому ящик пива..
P.S. не то что бы мне это очень надо, просто пива не с кем попить..
|
|
|
подробно о проекте
Анализ криптографических сетевых...
