Как можно сделать реверс-инжиниринг алгоритма?

Question

Мне интересно, как можно изменить алгоритм, например, для хранения логинов или пин-кодов.

Допустим, у меня есть количество данных, где:

7262627 -> ? -> 8172

5353773 -> ? -> 1132

и т.д.. Это всего лишь пример. Или произнесите шестнадцатеричную строку, преобразованную в другую.

&h8712 -> &h1283 или что-то в этом роде.

Как мне начать понимать, что это за алгоритм? С чего начать?

Не могли бы вы начать пробовать разные смены, xors и надеяться, что что-то выделяется? Я уверен, что есть лучший способ, так как это похоже на удар в темноте.

Возможно ли вообще реконструировать этот вид алгоритма?

Извините, если это глупый вопрос. Спасибо за вашу помощь / указатели.

Answer 1

Есть несколько вещей, которые люди пытаются:

• Получить исходный код или разобрать исполняемый файл.
• Угадайте, основываясь на хэш-функциях, которые используют другие люди.Например, хеш, состоящий из 32 шестнадцатеричных цифр, вполне может быть одним или несколькими повторениями MD5, и если вы можете получить одну пару входов / выходов, то это довольно легко подтвердить или опровергнуть (хотя см. «Соль» ниже).
• Статистический анализ большого числа пар входов и выходов, поиск любого вида паттернов или корреляций, и соотнесение этих корреляций со свойствами известных хеш-функций и / или возможных операций, которые разработчик системы может выполнитьбыло использовано.Это выходит за рамки одного метода и относится к области общего криптоанализа.
• Спросите автора.Безопасные системы обычно не полагаются на секретность алгоритмов хэширования, которые они используют (и, как правило, долго не остаются в безопасности).Примеры, которые вы приводите, довольно малы, и безопасное хеширование паролей всегда будет включать соль, чего, по-видимому, нет у вас.Таким образом, мы можем не говорить о системе, в которой автор уверен, что это сделает.

В случае хэша, в котором результат составляет всего 4 десятичных знака, вы можете атаковать его простопостроение таблицы каждого возможного 7-значного ввода вместе с его хэшированным значением.Затем вы можете перевернуть таблицу, и у вас будет (один-ко-многим) операция удаления хэширования.Вам никогда не нужно знать, как на самом деле вычисляется хеш.Как вы получаете пары ввода / вывода?Что ж, если сторонний разработчик может каким-то образом указать значение для хеширования и увидеть результат, то у вас есть то, что называется «выбранный открытый текст», и атака, основанная на этом, является «выбранной атакой открытого текста».Таким образом, хэш из 7 цифр -> 4 цифр был бы действительно очень слабым, если бы он использовался таким образом, который позволял выбранным атакам открытого текста генерировать много пар ввода / вывода.Я понимаю, что это всего лишь один пример, но это также всего лишь один из примеров техники, позволяющей обратить его вспять.

Обратите внимание, что обратный инжиниринг хеша и реверсирование его - это две разные вещи.Вы могли бы выяснить, что я использую SHA-256, но это не поможет вам обратить его вспять (то есть, учитывая вывод, определите входное значение).Никто не знает, как полностью обратить вспять SHA-256, хотя, конечно, всегда есть радужные таблицы (см. «Соль» выше) <conspiracy> По крайней мере, никто не признает, что они делают, так что это бесполезно для вас или меня. </conspiracy>

Answer 2

Возможно, вы не можете. Предположим, что функция преобразования известна, например,

function hash(text):
    return sha1("secret salt"+text)

Но «секретная соль» не известна и является криптографически сильной (очень большое случайное целое число). Вы никогда не сможете перебрать секретную соль даже из очень большого числа пар текстовых и криптекстовых текстов.

На самом деле, если бы точная используемая хеш-функция была известна как одна из двух одинаково сильных функций, вы никогда не могли бы даже догадываться, какая из них используется.

Answer 3

Уничтожение в темноте приведет вас к безумию.Есть некоторые алгоритмы, которые, учитывая текущее понимание, вы не могли бы надеяться на то, чтобы вывести внутреннюю работу между настоящим моментом и [предсказанным] концом вселенной, не зная точных деталей (потенциально включая личные ключи или внутренниегосударство).Конечно, некоторые из этих алгоритмов являются основой современной криптографии.

Если вы заранее знаете, что существует шаблон, который необходимо обнаружить, иногда есть способы приблизиться к этому.Например, если набор данных содержит несколько входных значений, которые отличаются на 1, сравните соответствующие выходные значения:

7262627 -> 8172
7262628 -> 819
7262629 -> 1732
...
7262631 -> 3558

Здесь довольно ясно (с учетом нескольких минут и калькулятора), что, когда вход увеличивается на 1выходной сигнал увеличивается на 913 по модулю 8266 (т. е. простой линейный конгруэнтный генератор ).

Дифференциальный криптоанализ - это относительно современная методика, используемая для анализа прочности криптографического блокашифры, опираясь на аналогичную, но более сложную идею о том, где известен алгоритм шифрования, но предполагается, что закрытый ключ не .Считаются входные блоки, отличающиеся друг от друга одним битом, и влияние этого бита отслеживается через шифр, чтобы определить, какова вероятность того, что каждый выходной бит "перевернется" в результате.

Другие способы решения этой проблемы заключаются в рассмотрении крайностей (максимальные, минимальные значения), распределения (что приводит к частотному анализу ), направления (всегда ли числа увеличиваются? Уменьшаются?) И (если это разрешено) рассмотрите контекст, в котором были найдены наборы данных.Например, некоторые типы PIN-кодов всегда содержат повторяющуюся цифру, чтобы их было легче запомнить (я не говорю, что PIN-код обязательно может быть выведен из всего остального - просто повторяющаяся цифра равна единице меньше цифр для беспокойства!).

Answer 4

Возможно ли вообще реверс-инжиниринг такого рода алгоритма?

Это возможно с ошибочным алгоритмом и достаточным количеством зашифрованных / незашифрованных пар, но хорошо разработанный алгоритм может вообще исключить такую ​​возможность.