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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
кажестя никто особо не парился почитать.. 17.12.01 11:00  Число просмотров: 2242
Автор: zelych Статус: Member
<"чистая" ссылка>
очень извиняюсь, но там небольшая ошибочка закралась..

> d = (d<<1) | ((a&1) ^ ~(c&1));
должно быть

d = (d<<1) | ((a&1)^(~(c&1)&1);
или, что то же самое:
d = (d<<1) | ((a&1)^(c&1)^1);

а то там и ломать особо нечего ( (d == -1) | (d == -2) )..

вообщем ящик пива ждёт вас в холодильнике..
<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-2020 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach