Анализ
С алгоритмической точки зрения при вскрытии современного шифра со случайным ключом существуют два принципиально различных направления атаки: поиск и использование некоторых уязвимостей алгоритма, и перебор ключей.
Поиск уязвимостей - долгая и кропотливая аналитическая работа, позволяющая делать выводы об исходных данных на основе шифрованных данных и знания алгоритма (криптосистемы).
Перебор ключей - (второе название «силовая атака», brute force - BF) стандартный способ подбора пароля, заключающийся в генерации очередного значения, шифровании его и сравнении полученного результата с имеющимся хешем. Основную роль в переборе ключей играют вычислительные мощности злоумышленника, таким образом, это универсальный способ для взлома различных шифров, поскольку этот способ не зависит от внутреннего устройства шифра.
Ввиду больших затрат времени и вычислительных средств, к перебору прибегают в том случае, когда остальными методами решить проблему не получается. И даже в случае перебора все равно, пытаются максимально сузить перебираемое множество за счет анализа особенностей конкретного алгоритма.
В дальнейшем будем предполагать, что злоумышленник знает логин пользователя, хеш H и ключ шифрования K.
Если бы криптосистема в Oracle строилась на однократном шифровании, при котором H=DES(X,K), то при известных H и K она бы мгновенно теряла стойкость, поскольку X=DES-1(H,K), и все параметры правой части известны.
В Oracle ситуация сложнее, и при наших допущениях если требуется вычислить пароль Х, то уравнение будет выглядеть так:
Х = DES-1 (H, K ) (3)
Заметим, что для обратной операции требуется промежуточный ключ K . Т.е., чтобы вычислить значение Х, в данном уравнении недостает значения K =DES(Х, K), которое является промежуточным ключом и не хранится нигде. А вычислить DES(Х, K) нет возможности, потому что X есть ЛогинПароль и пароль, по условиям задачи неизвестен.
Написанное выше означает, что, даже зная ключ шифрования K, можно только вычислить всевозможные значения DES(ЛогинПароль,K) для всевозможных значений пароля, а затем найти в этом множестве подходящее значение. А сделать это можно путем перебора всех возможных паролей, т.е. фактически только путем силовой атаки!
Вот в чем основной фокус криптографической конструкции в Oracle: для вычисления секретного пароля Х необходимо вначале вычислить промежуточный ключ DES(ЛогинПароль,K) для всевозможных значений пароля. Иными словами, теоретическая сложность взлома этой криптосистемы при отсутствии реальных уязвимостей, приближается к сложности силовой атаки на этот шифр.
Такая криптографическая конструкция - удачный пример однонаправленной функции, для которой неизвестна обратная. В итоге остается только перебирать вероятные пароли, сравнивая получившийся результат с образцом.
Однако говорить о том, что криптосистема Oracle является идеальной криптосистемой, еще рано. Для того чтобы быть уверенными в ее идеальности, следует исследовать ее особенности на предмет выявления закономерностей, позволяющих понизить ее криптостойкость. С точки зрения криптографии, использованная в Oracle конструкция имеет два потенциально интересных направления анализа (атаки):
- Изучение свойств промежуточного ключа. Несмотря на то, что DES достаточно хороший алгоритм, можно ожидать, что подмножество порожденных значений K' будет небольшим, а также будет обладать специальными свойствами. В результате, из 264 теоретически возможных значений K', в действительности может реализоваться только малая часть. Из значений K' вместе со значением Х можно составить базу данных, чтобы в дальнейшем K' брать из БД и подавать на вход второго узла DES.
- Потенциально интересной будет атака с накоплением DES(X,K) с одной стороны, и DES-1(H,Y) с другой, где Y - некоторое случайное значение (вероятное значение промежуточного ключа). В этом случае возможно как распараллелить эту атаку, так и понизить ее сложность.
