информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыСтрашный баг в WindowsПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Microsoft обещает радикально усилить... 
 Ядро Linux избавляется от российских... 
 20 лет Ubuntu 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
хе.. 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. не то что бы мне это очень надо, просто пива не с кем попить..
1  |  2 >>  »  




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach