хмм... но ведь брутфорс - это не киген... результат взлома крэкми - это киген... так что можно было и 2^32 использовать, ведь мат. теория та же...
snatch Можно и меньше. Число иттераций можно тоже меньше сделать. Думаю можно даже использовать вместо умножения сложение(Оно не так круто рассеивает биты.Кроме того, почти равно xorу). Это всего лишь теория. 96 бит я выбрал просто, чтобы брутафорц обламывался, да и крякми с паролем в 32 выглядит не серьезно. (На самом деле, пусть будет 32 бита, только без тупого брутофорца (умный можно ) volodya birthday-attack - это уже не брутфорс,что есть хорошо. Был бы рад вообще услышать мнения по линейному, и дифференциальному криптоанализу. Тока (вроде) birthday-attack это когда hash(a,k1)=hash(a,k2), а серийник проверяется hash(a,k)=b, т.е. коллизии тут не помогут IMHO. Можно, правда, надеятся что b лежит в цикле последовательности b[k]=hash(a,b[k-1]),b[0]=b, тогда ключ можно и за корень(2^96) найти... Вообще лучше забыть что hash это хеш, пусть это будет такой шифр . ЗЫ. Этот шифр был придуман, как очень простой, но лишеный явных недостатков, поэтому я смею надеятся на нетривиальный взлом. З.Ы.Ы.Кстати о тривиальных взломах: вот как искать ключ в крякми(консольная прога для VC6). Теперь понятно зачем нужен rol? 683994611__solve.rar
если a,b,c,K рассматривать как 96-ти элементные векторы над полем GF2(xor,and) то можно заметить следующее: 1) ror/rol эквивалентно умножению вектора на матрицу 2) xor - сложение векторов 3) с умножением похуже. результат можно записать как вектор полиномов не выше 96й степени от 96ти переменных вобщем весь алгоритм можно свести к решению определенной системы 96ти полиномиальных уравнений от 96ти переменных степени не выше 96й т.к. система определенная и мы знаем что существует единственное решение, то решить ее можно так что с криптографической точки зрения стойкость такого шифра стремиться к 0. опровергните меня если я не прав
да, и вдогонку если учвеличить разрядность ключа K (т.е. взять например массив K[j] и использовать разные элементы в каждой итерации), то шифр более менее становится похожим на стойкий, т.к. результирующая система получается недоопределенной. вот если бы еще и степень ее была пониже было бы вообще зашибись
вобщем весь алгоритм можно свести к решению определенной системы 96ти полиномиальных уравнений от 96ти переменных степени не выше 96й Это мне напоминает криптоанализ AES на страничке HFE
Relayer Решение системы 96ти полиномиальных уравнений от 96ти переменных степени не выше 96й? А как, интересно? Пример, для 2х иттерации и 5 битовых операций: пусть a=0; c=19; (1й бит - младший) после первой иттерации z=k представление умножения в виде вектора из полиномов: (r=x*19) r1=x1 r2=x1+x2 r3=x2+x3+x1*x2 r4=x3+x4+x1*x2+x2*x3+x1*x2*x3 r5=x1+x4+x5+x2*x3+x3*x4+x1*x2*x4+x2*x3*x4+x1*x2*x3*x4 x1=k5,x2=k1,x3=k2,x4=k3,x5=k4 (после циклического сдвига) подставляем в систему x-ы, получаем для b b1=r1+k1,b2=r2+k2,b3=r3+k3,... (+ это xor, * это and) Как решить то, зная b? Для 16 бит в системе, для старшего бита получается 2055 слогаемых при умножения на 19. Для 96бит и после всех иттераций можно получить систему, где для каждого бита получается полином с 2^95-ю слогаемыми(само собой я не проверял)... такие даже на бумажку не записать. З.Ы. Решение систем булевых функций в базисе and,xor NP-полная задача... Так, что, я готов и дальше защищать свой маленький шифр
не совсем. если система недоопределенная (т.е. кол-во уравнений меньше кол-ва переменных) - то таки да я вам скажу что она NP-полная. поэтому я и предложил увеличить разрядность K в два-три раза.
Relayer Ладно не буду спорить на счет NP полноты. Вообще, это не важно... Вот цифры длин полиномов: Шифр с 16 битам, 10 циклами, c=19,a=0. 32878 32771 32787 32910 32762 32801 32827 33028 32632 32601 32777 32756 327745 32743 32642 32506 (длинны полиномов, определяющих зависимость соответствующих выходных бит, от бит k) здесь длинна, это кол-во слогаемых. Сомневаюсь, что такую систему можно решить быстрее чем за 32000 шагов. И это только 16 бит, и 10 циклов... З.Ы. На счет увеличения разрядности K. Ну, этот шифр был изначально обречен быть взломаным...
уточним еще раз постановку задачи ? ты просишь known-plain text attack ? - сколько пар (a,b) знает потенциальный злоумышленник ? возможна ли chosen-plain text attack ? - (ты на первоначальном этапе создания регистрационного ключа не просишь "a" себе по почте прислать ?)
OLS Условия произвольные. Все возможно. Хотя предпологалось что пара (a,b) одна, и зашита в программе, но я уже не надеюсь, что с этим можно что-то сделать.
k1 = 012341256h k2 = 0FA4B5213h k3 = 01F6DD262h 1F6DD262FA4B521312341256 Check All ok Trivialno. S rol 1 eto sovsem nie trivialno.
2blood: Насчет двух разных линейных пространств ты совершенно прав. На практике у тебя получилось нечто наподобие TEA - до сих пор не приведено успешных атак на него. Единственное: TEA достигает заявленного эффекта стойкости за 310 простейших 32-битных операций (XOR, ADD), а ты за 576 умножений + 1728 простейших операций.
TEA mozhet i dostigayet, no etot algoritm nikogda nikakoi cryptostoikosti nie dostigayet, v oboih variantah. Etot algorithm soznatelno sdelan legko reversiruyemim. Tolko bi yego author ne dumal, chto on yedinstvenniy v mire "krutoi matematik", kotoriy mozhet takiye prostiye algoritmi reversit. Eto dazhe ne challenge.
Ну вот недавно же пробегала статейка (вот нашел - http://www.tcs.hut.fi/Publications/bibdb/HUT-TCS-A84.pdf), где показано, что операция сложения (читай, умножения) при большой разрядности стойка к линейному криптоанализу, если количество итераций взять достаточным. (ну и естественно, использовать какие-либо операции нелинейные относительно сложения). Там вроде в конце статьи даже challenge есть на минимальное число раундов для защиты от линейного криптоанализа при условии использования внутри раунда только сложения и аффинных преобразований. ?
Ruptor "Eto dazhe ne challenge." Спортивный интерес тут непричем. Хотелось поглядеть на связь разнородных операций. Задачку оформил, как реверсирование шифра. Надеялся, что кто нибудь взломает его,... (yedinstvenniy v mire "krutoi matematik", kotoriy mozhet takiye prostiye algoritmi reversit) ...я не могу. Может кто линк какой даст, где рассматривается связь например xor и add, был бы очень признателен? З.Ы. В аттаче еще один крякми с решением. Алгоритм здесь с rol-ом, но число циклов шифрования =10 868509328__crackme.rar
2blood: так ты линк финский на 1 пост выше все таки не прочитал ? там и описывается как раз стойкость связи xor и add
Eto resheniye k prediduschemu ili k etomu zhe samomu crackme? Kstati, vot slegka uskorenniy variant: Код (Text): static void blood96 (const unsigned long *k, unsigned long *y) { unsigned long a[2]; __asm { mov edi,k mov eax,x0 mov edx,x1 mov ecx,x2 mov esi,10 _loop: xor eax,dword ptr [edi] xor edx,dword ptr [edi+4] xor ecx,dword ptr [edi+8] shl eax,1 rcl edx,1 rcl ecx,1 adc eax,0 mov dword ptr [a],eax mov dword ptr [a+4],edx imul eax,c2 imul edx,c1 imul ecx,c0 add ecx,eax add ecx,edx mov eax,c1 mul dword ptr [a] mov ebx,eax add ecx,edx mov eax,c0 mul dword ptr [a+4] add ebx,eax adc ecx,edx mov eax,c0 mul dword ptr [a] add edx,ebx adc ecx,0 dec esi jnz _loop mov ebx,y mov dword ptr [ebx],eax mov dword ptr [ebx+4],edx mov dword ptr [ebx+8],ecx } }
OLS все таки не прочитал Вылетело из головы совсем... Да, похоже это как раз то, что я просил. Очень признателен. Ruptor Решение к этому же самому (к предыдущему я уже давал). Как я говорил, это не соревнование. (Хотя, кому нибудь, наверное, было бы интересно самому найти решение). vot slegka uskorenniy variant Да... раза в два, как минимум, укороченый. У меня всегда были проблемы с умножением
Ты приведи конкретный пример - тогда и поговорим. А лучше cgi/php сайт с возможностью зашифровать введенные данные, чтобы можно было chosen plaintext-аттаку применить...
