Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Вот такая вот задачка. 18.04.03 15:32
Автор: Alexander N. Brandt Статус: Незарегистрированный пользователь
|
Здравствуйте...
В криптографии я, прямо скажем, не силён, но вот жизнь поставила перед необходимостью решить следующую задачку. :)
Имеется некий "чёрный ящик", на вход которого подаётся последовательность байт (от 1 до 30), на выходе получаем последовательность той же длинны, полученную из входной по некоторому алгоритму. Необходимо выяснить этот алгоритм, имея таблицу входных и выходных значений, с тем, чтобы построить модель "чёрного ящика".
Решаема ли описанная задача в принципе, и если да, то какие методы решения могут предложить уважаемые гуру?
Заранее благодарен всем ответившим...
|
|
Вот такая вот задачка. 23.04.03 19:23
Автор: tdes <jin> Статус: Member
|
|
а я бы предложил решать следующим образом - в матлабе построить нейронную сетку, например для начала, из перцептронов, составить {X}, {Y} и тренировать сетку, чтоб она, либо в идеале всегда находила по заданному х - y, либо увеличить число попаданий до максимума. Можно пробовать разные конфигурации, поиграть с количеством слоев ... Если алгоритм не сложный, это, имхо, самый быстрый путь ( самому не надо думать много :)))
|
| |
Вот такая вот задачка. 24.04.03 11:24
Автор: Alexander N. Brandt Статус: Незарегистрированный пользователь
|
> разные конфигурации, поиграть с количеством слоев ... Если
> алгоритм не сложный, это, имхо, самый быстрый путь ( самому
> не надо думать много :)))
Час от часу не легче... :)
Где найти информацию по нейронным сетям вообще, и по построению их
в матлабе в частности? Понятно, что универсальный ответ - в интернете,
но наверняка вам известны ссылки где это всё описано подробно,
без лишней "воды".
Позволит ли построение и тренировка нейросети получить в конечном итоге алгоритм вида:
1. Ксорим X c числом N1
2. Полученное значение сдвигаем вправо на 4 бита
3. Ксорим с N2 = Y
или всё сведётся к необходимости построения нейронной сети в программе,
имитирующей работу ч.я?
|
| | |
Вот такая вот задачка. 04.05.03 01:52
Автор: zelych Статус: Member
|
>
> > разные конфигурации, поиграть с количеством слоев ...
> Если
> > алгоритм не сложный, это, имхо, самый быстрый путь (
> самому
> > не надо думать много :)))
как мне кажется, у нийронных сетей и криптоалгоритмов задачи прямо противоположные.. нейросети обычно занимаются классификацией объектов (т.е. пытаются найти какие-то закономерности), а криптоалгоритмы - совсем наоборот - пытаются всякие закономерности изничтожить..
к тому же для моделирования придётся сделать сеть с кучей слоёв, а потом ещё пол-года её обучать..
> Час от часу не легче... :)
> Где найти информацию по нейронным сетям вообще, и по
> построению их
> в матлабе в частности? Понятно, что универсальный ответ - в
> интернете,
> но наверняка вам известны ссылки где это всё описано
> подробно,
> без лишней "воды".
на matlab.ru кажется много всего было (или ссылки были), только там зарегистрироваться надо.
|
| | | |
Вот такая вот задачка. 09.05.03 00:36
Автор: tdes <jin> Статус: Member
|
> как мне кажется, у нийронных сетей и криптоалгоритмов
> задачи прямо противоположные.. нейросети обычно занимаются
> классификацией объектов (т.е. пытаются найти какие-то
> закономерности), а криптоалгоритмы - совсем наоборот -
> пытаются всякие закономерности изничтожить..
> к тому же для моделирования придётся сделать сеть с кучей
> слоёв, а потом ещё пол-года её обучать..
неправда ваша, если знать что функции составляющие крипто-алгоритм достаточно просты, то нейронную сеть определяющую их построить достаточно просто, хороший пример есть в “Нейронные сети. Матлаб” Потемкин
|
|
О криптоанализе 19.04.03 22:43
Автор: Кремлёв Статус: Незарегистрированный пользователь
|
Здраствуйте уважаемые господа. Позвольте представить вам мои рассуждения по этому вопросу.
Для начала классифицируем возможные атаки на ч.я.
Условимся X - входная последовательность Y - выходная последовательность
1. С известным X и Y. Тяжко :)
2. С выбором X. Необходим доступ к ч.я. Формируем такие X которые могут помочь нам раскрыть алгоритм к примеру из одних нулей (единиц), из нулей и одной единицы и т.д. Обязательно послать два одинаковых блока X и сравнить выходные блоки Y если они одинаковы это упрощает дело т.к.
можно составить список вероятных сообщений преобразовать их, а затем работать с полученными результатами, можно вообще составить список всех возможных сообщений. Если такая ситуация наблюдается, т.е. совпадение Y при одинаковых X, вероятно использование блочного шифра в режиме простой замены, также при этом длина X=Y. Если длина совпадает, а содержимое нет то возможен режим гаммирования, при этом можно попытаться определить период гаммы используемого датчика псевдослуч. чисел (ПСЧ), можно подавать последовательно блоки допустим из одних единиц пока не наступит повторение и тогда вероятно период будет найден, хотя здесь всё не так просто, в литературе описаны различные способы. Можно сделать которые предположения о алгоритме, замеряя время обработки X, при этом составить зависимость времени обработки от состава X, известно, что ассиметричные шифры работают дольше чем симметричные, т.е. можно сделать гипотезы о типе алгоритма.
3. С выбором Y. Это тогда, когда ч.я. работает и в обратном направлении.
Теперь несколько мыслей о возможных вариантах действия.
Проводить подобный анализ имеет смысл, если есть вероятность, что алгоритм слабый, иначе в одиночку это неподсильная задача. Можно попытаться подавать на вход непотребные данные, прерывать
работу ч.я. в самый неподходящий момент и получить с этого какие нибудь данные о алгоритме.
Необходимо выяснить как организована работа с ключевой информацией, есть ли вообще ключ.
Надо определить место и назначение ч.я. его роль в системе, возможно это вовсе не криптопреобразование, а какой нибудь преобразователь инф. в известный связной код. Также важно сравнить длину блоков X и Y если длина Y>X или длина вых. массива данных > вх. массива то возможно добавляются некоторые случайные данные, имитозащита, метки времени, ч.я. может иметь некоторые доп. входы для синхронизации получения времени и т.д. В общем необходимо собрать как можно больше информации и использовать её для определения структуры ч.я. Если ящик программа можно посмотреть на дизассемблере. Главное помнить, что можно найти и альтернативный верный алгоритм, м.б. даже более простой.
P.S.
Прошу строго не судить всё выше сказанное, возможно где-то и накосячил, конструктивная критика только приветствуется.
P.P.S.
Информацию по данным вопросам можно найти: "www.algolist.manual.ru" и
"www.ssl.stu.neva.ru/psw/crypto.html"
|
| |
О криптоанализе 24.04.03 11:16
Автор: Alexander N. Brandt Статус: Незарегистрированный пользователь
|
> Здраствуйте уважаемые господа. Позвольте представить вам
> мои рассуждения по этому вопросу.
> Для начала классифицируем возможные атаки на ч.я.
> Условимся X - входная последовательность Y - выходная
> последовательность
>
> 2. С выбором X. Необходим доступ к ч.я. Формируем такие X
> которые могут помочь нам раскрыть алгоритм к примеру из
> одних нулей (единиц), из нулей и одной единицы и т.д.
Вообщем, вот этот способ как раз подходит.
Но всё на самом деле не так сложно, как вы описываете. Никакого гаммирования, привязки ко времени,
и прочих "весёлостей" там нет - одному данному входному X соответствует одно
(всегда одно и то же для данного Х) выходное значение Y такой же длинны, хотя для разных входных
X может быть одно и то же Y, как показано ниже.
Значения на вход можем подавать какие угодно, непосредственно дизассемблировать внутренний
алгоритм ч.я. не представляется возможным.
Заложить в модель заранее вычисленные таблицы для всех возможных входных Х при максимальной
длинне Х = 30 байт - тоже не самое правильное решение.
Эксперименты с ч.я. дают возможность предполагать, что алгоритм этот несложен, и оперирует
с 32-х разрядными числами, т.е. Х разбивается на блоки по 4 байта, значение младших (слева
направо) 4-х байт влияет на значение следующего блока, но от него не зависит.
Чтобы немного пояснить вышесказанное, приведу таблицу соответствий Х => Y:
00 73
0000 0A4A
000000 1290DA
00000000 48CBFA64
0000000000 48CBFA6403 --> 4 первых байта остались такими же.
000000000000 48CBFA644BB8
ну и так далее.
01 FC
02 4D
11 74
12 2C
73 8E
Вот ещё интересные ответы:
E2 58
OE 59
17 20
B0 20
52 83
D2 83
40 FF
FF BA
DE DE !!! и такое вот бывает.
OD 45
D0 47
Если приведённое выше несколько прояснило ситуацию, то вопрос, в принципе, остаётся прежним -
каким образом можно вычислить алгоритм, по которому для заданных Х формируются Y.
Что-то мне подсказывает, что там всё одними сдвигами/ксорками обходится.
Если у кого появились идеи по этому поводу - просьба поделиться... :)
> Теперь несколько мыслей о возможных вариантах действия.
> Проводить подобный анализ имеет смысл, если есть
> вероятность, что алгоритм слабый, иначе в одиночку это
> неподсильная задача. Можно попытаться подавать на вход
Как оценить вероятность того, что алгоритм слабый?
За ссылки - спасибо большое, только, как я понял из беглого ознакомления, в большинстве
источников исходят из того, что алгоритм заранее известен.
|
| | |
О криптоанализе 20.05.03 21:26
Автор: Крипт Статус: Незарегистрированный пользователь
|
> и оперирует
> с 32-х разрядными числами, т.е. Х разбивается на блоки по 4
> байта, значение младших (слева
> направо) 4-х байт влияет на значение следующего блока, но
> от него не зависит.
Господи, надо же, человек сам дал ответ и просит еще чего-то
Составь память 2^31, на основе которой можно построить некоторую функцию - вот тебе и ответ на все моделирование автомата.
Данная модель тебе достаточна для дешифрования любой послед - это точно :)))))
|
| | |
О криптоанализе 25.04.03 12:33
Автор: NickP Статус: Незарегистрированный пользователь
|
> Эксперименты с ч.я. дают возможность предполагать, что
> алгоритм этот несложен, и оперирует
> с 32-х разрядными числами, т.е. Х разбивается на блоки по 4
> байта, значение младших (слева
> направо) 4-х байт влияет на значение следующего блока, но
> от него не зависит.
Если алгоритм работает с 32-х разраядными числами, то возможно, что и более короткие последовательности он дополняет до 32-х бит, а разультат обрезает до длинны входной последовательности.
Попробуй поперебирать числа с фиксированными 3-мя байтами изменяя только 4-й и посмотреть не выдастся ли ответ у которого 3 байта будут совпадать с ответом если на вход подать толко эти три байта.
|
| | |
О криптоанализе 25.04.03 02:43
Автор: Кремлёв Статус: Незарегистрированный пользователь
|
Привет всем, это опять я.
Приведённые пояснения, признаюсь довольно сильно сбили с толку.
Хотелось бы узнать существует ли, обратное преобразование
(м.б. расшифрование) и чем оно осуществляется? Если ч.я. работает и в обратную сторону то, что будет в данном случае, например дано соответствие:
X Y
17h 20h
B0h 20h
что будет на X если подать 20h на Y несколько раз(если возможно)?
Позвольте представить на ваш суд следующие рассуждения.
В примерах есть соответствие разным X, одинаковых Y, в
криптосистемах такое встречается, но при этом, длина X и Y
различается, т.е. в X встраиваются метки опознавания или Y состоит
из нескольких частей позволяющих определить X.
Можно сделать вывод, что возможно совпадение X для одного Y, есть следствие некорректных входных данных, т.к. криптопреобразование д.б. однозначным.
Вероятно преобразование осуществляется над блоками длиной в 4 байта, следовательно есть вероятность того,что допустимым с точки зрения, логики ч.я., является входая последовательность X длиной кратной 4 байтам, иные же последовательности преобразуются неверно (неоднозначно). В примерах совпадения приводятся для последовательностей длиной меньше 4 байт.
В примере есть соответствия для X состоящих из нулей, видно, что для X длиннее 4 байт, первые 4 байта сохраняются. Посмотреть будет ли, та же ситуация для последовательности из единиц, и для любой другой последовательности. Если исходить из того, что корректный ввод кратен 4 байтам, надо посмотреть соответствие для 8 байт заполненных 0, назовём эту последовательность Х1 а её соответствие Y1. Если последующие 4 байта отличаются от первых 4 байт Y1, следовательно они как то зависят от предыдущих, допустим XOR, тогда просто подаём на вход ч.я. X2 длиной 4 байта состоящую из первых 4 байт Y1 и они должны совпадать со вторыми 4 байтами Y2 т.к. XOR выполняется с 0, но всё это в случае зависимости XOR.
Можно составлять соответствия для X которые отличаются друг от друга на заданную величину, например изменять один бит, или ставить его на разные позиции. Возможно удобнее всё это анализировать в двоичном представлении. Если предположить, что используется XOR и сдвиги то есть вероятность, что всё это повторяется в течении нескольких раундов. Если XOR, то с каким значением, константа, ключ, функция от входа, предыдущий блок, что-то ещё. Чем больше раундов тем м.б. сложнее восстановить алгоритм, ключ может разбиваться на раундовые т.е. иметь в каждом раунде своё значение. Если есть раунды то имея соответствия можно судить лишь о некотором сложном алгоритме эквивалентном многократно повторяющемуся простому алгоритму.
Если предположить, что используется XOR и сдвиги, то как этот процесс атоматизировать, есть одна идея возьмём последовательность 4 байта допустим из нулей и напишем программу которая будет суммировать её со всеми возможными значениями длиной 4 байта и для каждого из этих значений осуществлять все возможные сдвиги всего (2^32)*32=137438953472 вариантов, сравнивать с верным результатом и запоминать пары значений где будет совпадение, в случае нескольких раундов придётся всё усложнить. Далее будет необходим анализ значений с которыми производится XOR, совпадают ли они для разных X и т.д.
И наконец самое главное, точно ли, Ч.Я. это преобразование с целью защитить информацию (шифр), может быть это нечто совершенно другое?
Если шифр, то д.б. однозначное преобразование.
Важно выяснить структуру входной последовательности, длину, наличие каких то, меток, повторений, возможно ч.я. не определяет, что ему подана неверная информация, хотя и такие данные должны помочь выяснить его структуру.
Степень крутизны алгоритма в ч.я., возможно определить из условий где он применяется, если для защиты гос. тайны то дело дрянь :-), а также зная квалификацию разработчиков.
Ещё раз хочется отметить, что наобум очень сложно будет, что либо, проанализировать, нужна хоть какая то информация о назначении ч.я.
P.S.
Всё вышесказанное может быть неправдой (без моего злого умысла ;-)
Критика только приветствуется.
P.P.S.
Стоит ли игра свеч?
|
| | |
О криптоанализе 24.04.03 12:10
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> (всегда одно и то же для данного Х) выходное значение Y
> такой же длинны, хотя для разных входных
> X может быть одно и то же Y, как показано ниже.
Это уж точно не шифровальная машинка :)
> Заложить в модель заранее вычисленные таблицы для всех
> возможных входных Х при максимальной
> длинне Х = 30 байт - тоже не самое правильное решение.
Убедитесь, что размер блок действительно 32 бит серией тестов - возмите несколько 32бит последовательностей, объедините несколько из них, прогоните через ч.я., сравните 32битные последовательности разных тестов. Для 32бит и табличку не сложно составить (это действительно не 30 байт). Это как максимум. Короткий алгоритм найти (если он по предположению не сложный) постараться можно, только данных надо побольше, чем приведено ниже.
> Эксперименты с ч.я. дают возможность предполагать, что
> алгоритм этот несложен, и оперирует
> с 32-х разрядными числами, т.е. Х разбивается на блоки по 4
> байта, значение младших (слева
> направо) 4-х байт влияет на значение следующего блока, но
> от него не зависит.
> Чтобы немного пояснить вышесказанное, приведу таблицу
> соответствий Х => Y:
>
> 00 73
> 0000 0A4A
> 000000 1290DA
> 00000000 48CBFA64
> 0000000000 48CBFA6403 --> 4 первых байта
> остались такими же.
> 000000000000 48CBFA644BB8
> ну и так далее.
>
> 01 FC
> 02 4D
> 11 74
> 12 2C
> 73 8E
>
> Вот ещё интересные ответы:
> E2 58
> OE 59
>
> 17 20
> B0 20
>
> 52 83
> D2 83
>
> 40 FF
> FF BA
>
> DE DE !!! и такое вот бывает.
>
> OD 45
> D0 47
>
> Если приведённое выше несколько прояснило ситуацию, то
> вопрос, в принципе, остаётся прежним -
> каким образом можно вычислить алгоритм, по которому для
> заданных Х формируются Y.
Устно - тяжело. Програмку надо написать, которая из элементарных функций, комбинируя их, создает алгоритмы, их прогоняет на тестовых данных и сравнивает результаты.
> Что-то мне подсказывает, что там всё одними
> сдвигами/ксорками обходится.
>
> Как оценить вероятность того, что алгоритм слабый?
>
> За ссылки - спасибо большое, только, как я понял из беглого
> ознакомления, в большинстве
> источников исходят из того, что алгоритм заранее известен.
>
|
|
Вот такая вот задачка. 19.04.03 19:44
Автор: Pit Статус: Незарегистрированный пользователь
|
> Здравствуйте...
> В криптографии я, прямо скажем, не силён, но вот жизнь
> поставила перед необходимостью решить следующую задачку. :)
> Имеется некий "чёрный ящик", на вход которого подаётся
> последовательность байт (от 1 до 30), на выходе получаем
> последовательность той же длинны, полученную из входной по
> некоторому алгоритму. Необходимо выяснить этот алгоритм,
> имея таблицу входных и выходных значений, с тем, чтобы
> построить модель "чёрного ящика".
>
> Решаема ли описанная задача в принципе, и если да, то какие
> методы решения могут предложить уважаемые гуру?
>
> Заранее благодарен всем ответившим...
Знаешь, всё зависит от сложности структуры этого ящика., и от того набора входных данных которые у нас есть. Имея достаточно больщой набор тестовых данных можнонайти алгоритм или похожий алгоритм справедливый для этих наборов данных. Всё это не так просто. Советую разобраться с теор вером (теория вероятности) без неё здесь никак. Это была теоритическая часть. С другой стороны если этот ящик можно разобрать (дизасемблировать) можешь посмотреть, что тварится с той входной информацией, может сработать.
|
|
Вот такая вот задачка. 18.04.03 19:06
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Здравствуйте...
> В криптографии я, прямо скажем, не силён, но вот жизнь
> поставила перед необходимостью решить следующую задачку. :)
> Имеется некий "чёрный ящик", на вход которого подаётся
> последовательность байт (от 1 до 30), на выходе получаем
> последовательность той же длинны, полученную из входной по
> некоторому алгоритму. Необходимо выяснить этот алгоритм,
> имея таблицу входных и выходных значений, с тем, чтобы
> построить модель "чёрного ящика".
>
> Решаема ли описанная задача в принципе, и если да, то какие
> методы решения могут предложить уважаемые гуру?
>
> Заранее благодарен всем ответившим...
Алгоритм ч.я. можно придумать, только если будет таблица соответствия входных данных и выходных для всего множества входных данных. Причем это соответствие (таблица) и будет одним из бесконечного множества алгоритмов. Если хоть для одного из исходных данных не будет соответствия выходных данных, то можно придумать приблизительный алгоритм, но ни кто не гарантирует, что для этих недостающих данных ч.я. и наш алгоритм даст один и тот же результат. Касаемо криптографии, если нет неопределенности - т.е. любому из множества исходных данных соответствует один и только один шифр и наоборот, то можно восстановить, если не хватает только этого одного соответствия.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
