Так ли плох DES, как это пытаются показать?

Тема в разделе "WASM.CRYPTO", создана пользователем v_mirgorodsky, 24 май 2008.

  1. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Интерес у меня чисто академический. В моей работе отсутсвует необходимость применения стойких криптоалгоритмов, но интересно было бы немного глубже разобраться в предмете.

    Длинна ключа DES составляет всего 56 бит, что дает нам много миллиардов возможных комбинаций. Теперь представим, что стоит задача вскрыть некий зашифрованный текст, объемом несколько килобайт. Ну пусть это будет простой текстовый файл. Представления о его содержании мы не имеем никакого, знаем, что это русский язык, чего-нибудь типа Windows-1251 кодировка. Пусть эту операцию необходимо выполнить за 2 месяца. Несложный подсчет говорит, что для полного перебора всех комбинаций за это время надо перебирать по 130 миллионов комбинаций в секунду. Но одного декодирования мало - надо еще автоматически с той же скоростью проверять является ли текст искомым сообщением, или нет. В описанном случае это решается сравнительно просто - все символы сообщения должны лежать в определенных пределах, но ведь для проверки гипотезы надо раскодировать хотя бы несколько строк текста :-\

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

    Таким образом для взлома нашего текстового сообщения необходимо потратить ~100K$ и два месяца времени. И это в простейшем случае. А если сообщение является чисто бинарным и для понимания его целостности необходимо расшифровать его текст полностью? А если мы просто используем двойной DES? Или тройной? В случае двойного или тройного DES задача прямого перебора уже не решается принципиально на сегодняшнем уровне развития техники и математики, поскольку колличество комбинаций просто огромно.

    Где же ошибка в рассуждениях? Почему весь народ при виде DES плюется и кричит о ненадежности шифрования?
     
  2. Jupiter

    Jupiter Jupiter

    Публикаций:
    0
    Регистрация:
    12 авг 2004
    Сообщения:
    530
    Адрес:
    Russia
    если для вскрытия защиты нужно сделать два шага, а не покрыть два световых года, то наивно полагать, что подобная защита надёжна на основании того, что кому-то лень сделать эти два шага.
    если подразумевать, что у атакующей стороны достаточно ресурсов (бюджет в миллионы долларов) - то каков смысл в "шифровании на день"?
    хотя ты же не защищаешь секреты на миллиарды долларов... инсайдеров у тебя в которе нет...
    тут уже другая зависимость ;) классическая зависимость стойкости от температуры )))
     
  3. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    v_mirgorodsky
    Значительно дешевле и значительно быстрее, см. например http://www.copacobana.org/. Была также построена машина, перебирающая меньше, чем за сутки.

    Double-DES ничем не отличается от одинарной, читай про meet-in-the-middle атаку. Tripple-DES считается на сегодняшний день стойкой и широко применяется.
     
  4. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Собсно, аналог такой машины использовать для брут-форса я и имел ввиду. Однако же, они никак не затрагивают критерии правильности раскодирования информации. Одно дело перемолотить много миллиардов комбинаций, а другое дело определить, что на неком шаге был получен правильный ответ. Написание реальной функции проверки правильного ответа в реальной жизни увеличит время перебора в сотни раз.
     
  5. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Если я правильно понял, то A = DES(DES(DATA, KEY1), KEY2) = DES(DATA, KEY3)? Иначе meet-in-the-middle заканчивается полным перебором всех 2^112 комбинаций.
     
  6. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    v_mirgorodsky
    Если кодировать (практически) случайную информацию, то может быть. Иначе сравни время на проверку десятка знаков с временем перебора.

    Нет конечно. Иначе не имело бы смысла зашифровывать несколько раз с помощью DES и Triple-DES была бы эквивалентна одинарной. Вот описание принципа: Meet-in-the-middle attack
     
  7. v_mirgorodsky

    v_mirgorodsky New Member

    Публикаций:
    0
    Регистрация:
    7 авг 2006
    Сообщения:
    53
    Stiver
    Спасибо за ликбез ;) Одно могу сказать однозначно - http://www.copacobana.org/ не годится для реализации Meet-in-the-middle attack, поскольку просто не имеет необходимых ресурсов оперативной памяти ;)

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

    n0hack New Member

    Публикаций:
    0
    Регистрация:
    3 июн 2008
    Сообщения:
    71
    >> Где же ошибка в рассуждениях? Почему весь народ при виде DES плюется и кричит о ненадежности шифрования?

    Главным образом из-за дилны ключа. Если не ошибаюсь, где-то в 96'м этот шифр взломали перебором ключей с помощью распределенной сети за двое суток или около того. После чего правительство США и решило организовать конкурс AES.

    Кроме того, шифр медленный (по сравнению с прочими) и трудно реализуется программными средствами (опять таки по сравнению с прочими).

    Советую посмотреть в сторону IDEA или ГОСТ.