Справочник автора/Криптография

Материал из Posmotre.li
Перейти к: навигация, поиск
« Кто возьмёт в плен русского шифровальщика, либо захватит русскую шифровальную технику, будет награжден Железным крестом, отпуском на родину и обеспечен работой в Берлине, а после окончания войны — поместьем в Крыму »
— Приказ 1942 года

Здесь информация о криптографии и шифрах.

Что читать[править]

Я сошлюсь на две книги. Всего на две, неспециалисту этого должно хватить.

  • Дэвид Кан. Взломщики кодов.
  • Владимир Жельников. Криптография от папируса до компьютера.

А я добавлю:

Терминология[править]

В криптографию не входят, но близки к ней…

  • Код — правила, по которым информация преобразуется в другую форму. Кодами являются кодировки символов, сигналы бедствия, тарабарские фразы, которыми переговариваются охранники супермаркета…
  • Тайнопись aka стеганография — способ защитить от врага факт передачи информации. Невидимые чернила, встраивание в картинку тайных посланий…

Криптография занимается такими вещами.

  • Шифр — способ защитить от врага информацию, даже если факт её передачи раскроется.
  • Хэш-функция — функция, принимающая на входе послание произвольной длины и возвращающая число от 0 до N.
  • Криптостойкий генератор псевдослучайных чисел — генератор псевдослучайных чисел, для которого по имеющейся истории сложно предсказать дальнейшие числа. Может применяться, например, в азартных играх.
  • Имитовставка — «криптографически стойкая контрольная сумма», защищающая сообщение от намеренной подмены. Частным случаем имитовставки является электронная подпись.
  • Криптографический протокол — процедура обмена ключами и шифрованной информацией.
  • Ключ — секретная информация, позволяющая шифровать/расшифровывать сообщения, накладывать/проверять имитовставку.

Какие бывают шифры[править]

  • Поточные и блочные.
    • Поточный — работает по одному символу.
    • Блочный — всего лишь шифр простой замены. Однако замену эту делает не по одному символу, а блоками, например, по 8 или 16 штук.
  • С обратной связью и без. Обратная связь — это когда внутреннее состояние шифратора зависит от того, какие символы вы на него подали. Обратная связь мешает находить в шифротексте закономерности, однако сложнее для ручной работы: любая ошибка приведёт к тому, что остаток текста будет нечитаемым.
    • Блочные шифры обратной связи по определению не имеют. Значит, её приделывают искусственно (например, суммируют получившийся блок с предыдущим).
      • Существуют также «самокорректирующиеся» режимы шифрования, когда ошибка распространяется, например, на ошибочный блок и следующий за ним.
  • С перестановкой символов и без. Перестановка мало повышает криптостойкость и хороша лишь тем, что несложное устройство — картонка с вырезами — позволяет быстро переставлять символы при ручной шифровке. Естественно, с переходом на компьютер от перестановки отказались.
  • С элементами случайности и без. Случайность затрудняет анализ: сходные сообщения зашифруются совершенно по-разному. Если у шифра есть обратная связь, самый простой способ добавить случайности — начать послание с нескольких случайных символов.
  • Симметричные (одноключевые) и асимметричные (двухключевые). Двухключевой шифр имеет два разных ключа для зашифровки и расшифровки, это позволяет довольно интересные криптопротоколы (см. раздел о компьютерной криптографии). Ни один из существующих двухключевых шифров не пригоден для ручного исполнения, только компьютер.

Взлом шифров[править]

Атаки делятся на:

  • Атаки на основе шифротекста. У взломщика нет ничего, кроме шифровки.
  • Атаки с открытым текстом. Взламывая шифр Виженера, мы предполагаем, что где-то в шифровке есть «ХАЙЛЬ ГИТЛЕР». Если так оно и оказалось, а длина ключа не более 11, шифр взламывается. Несложная компьютерная программа за долю секунды приложит открытый текст ко всем позициям шифровки — человеку остаётся только увидеть (или не увидеть) осмысленный текст.
  • Атаки с подобранным открытым текстом. Интересно получается: шпион добирается до машины, вводит в неё «ААААААА» и прикарманивает выходную перфоленту.
  • Атаки с адаптивно подобранным открытым текстом. Это когда шифромашину «мучают» в лаборатории.
  • Атаки с подобранными ключами. Это если лаборатория позволяет менять ключи.
  • Атаки с анализом неполадок. Электронную шифромашину «истязают» помехами, и от помех она начинает портить шифровку. Сравнивая порченую шифровку с эталонной, можно выяснить ключ.
  • Подслушивание по сторонним каналам. Ультразвук от катушек на материнской плате (долго!), пульсации тока в цепях питания, время реакции машины…

Ну и нельзя сбрасывать со счетов банальные подслушивание, пытки («терморектальный криптоанализ») и подкуп.

Чем так важен криптопротокол?[править]

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

  • В компьютерной шифровке из-за дороговизны (а зачастую и отсутствия) надёжных каналов мы даже не уверены, что на другой стороне провода тот, за кого он себя выдаёт.
  • Если шифруются одинаковые сообщения, кое-какую информацию можно извлечь просто из факта, что шифровки одинаковы.
  • Можно стать «промежуточным звеном» (man in the middle — «человек посередине»), перешифровывающим сообщения.
  • Можно запомнить шифровку, а потом повторить её без изменений, даже не зная, что она означает.
  • Кусок открытого текста можно и угадать логически. В компьютерной шифровке технические байты, присущие форматам и протоколам более низкого уровня (например, шифруем JPEG или HTTP) — отличный открытый текст. В первом протоколе немецкой шифромашины «Энигма» один и тот же текст (разовый ключ) повторялся дважды, это упрощало взлом.
  • Информацию можно выудить даже из факта, что шифровка была (или не была) послана. Или вдруг в шифроканале началась бурная деятельность.

В общем, колхозный протокол может свести на нет всю прочность шифра.

Ручная криптография[править]

Раз шифровка выполняется руками и дешифровка руками, вокруг ручной криптографии можно раскрутить интересные детективные сюжеты. Пожалуй, самый интересный из них — несложный шифр и «ненастоящий сварщик» (вернее, криптоаналитик). Тогда читатель сможет ухватиться за мысль сыщика, проследить, как он находит улики и прикладывает их к шифротексту. А ещё ключом или контейнером для шифроблокнота может быть ничем не примечательный предмет. Хороший пример — «Пляшущие человечки»: узнав, что героиню зовут Илси (в оригинале Elsie), Шерлок устраивает атаку с открытым текстом и разрушает шифр.

Различные колёса, диски и таблицы, которые надо ставить в нужное положение вручную, также для простоты отнесём к ручной криптографии.

Скитала (античная шифровальная «машина»)[править]

В Спарте оборачивали узкий кожаный ремешок вокруг палки по спирали и писали текст. При разматывании получался набор букв, для прочтения требовалась такая же палка. Нашли и способ анализа: наматывали ремень на коническую палку и двигали туда-сюда, пока текст не начинал читаться.

Шифры простой замены[править]

Многие из вас с такими шифрами баловались в детстве. Умелый криптоаналитик может с одного взгляда увидеть и вскрыть шифр простой замены. А неумелый — проведёт частотный анализ. Автор этих строк участвовал в конкурсе «IT Starz 2013», одним из заданий которого было вскрыть такой шифр. Нашёл частоту каждой буквы, сопоставил их с реальными частотами букв в языке — оставалось немного подправить, и готово. Два часа программирование, десять минут дешифровка.

В числе шифров простой замены…

Литорея[править]

Шифр простой замены, приспособленный для проговаривания: например, заменяются только согласные буквы.

Шифр Цезаря[править]

Сдвиг алфавита на n символов. Например, на 3.

А → Г
Б → Д
В → Е
...
Ь → Я
Э → А
Ю → Б
Я → В

Квадрат Полибия[править]

Квадрат Полибия

Античная шифровальная таблица. Хоть и древнее шифра Цезаря, но, тем не менее, удобнее и нагляднее, хотя и работает по такому же принципу. В простейшем случае можно брать нижестояющую букву следующего ряда, но можно пропустить ряд, или брать букву по любому иному принципу.

Шифр Виженера[править]

Усовершенствованный шифр Цезаря. Буквам А…Я даём номера от 0 до 32. Положив, что 0 = 33, 1 = 34, 2 = 35 и т. д., получим…

А + А = 0 + 0 = 0 = A
А + Б = 0 + 1 = 1 = Б
А + В = В
...
А + Я = Я
Б + А = Б
Б + Б = В
...
Б + Ю = Я
Б + Я = А
...

Получается такая таблица сложения (для простоты выпишу только кусок).

АБВГДЕЁЖ...ЮЯ
БВГДЕЁЖЗ...ЯА
ВГДЕЁЖЗИ...АБ
ГДЕЁЖЗИЙ...БВ
ДЕЁЖЗИЙК...ВГ
ЕЁЖЗИЙКЛ...ГД
....

Придумаем какой-нибудь ключ (например, БЕГ). Открытый текст БАГДАД. Записываем одно под другим и воспользуемся таблицей.

   БАГДАД
  +БЕГБЕГ
   ------
   ВЕЁЕЕЖ

Получаем шифровку ВЕЁЕЕЖ. Шифр прост, но не поддавался взлому три века.

Колёса Джефферсона[править]

Современная реплика машины Джефферсона, частично разобранная. Вот такой «лоу-тек» взломали только в XX веке!

Того самого, основателя США. Стойкость близка к шифру Виженера.

Шифр Цезаря можно прокрутить такой машиной. Есть несколько алфавитных колёс, собранных в барабан. На колёсах набираем открытый текст, поворачиваем барабан в сборе на несколько делений — и читаем шифровку. Достаточно сделать колёса не в алфавитном порядке, а в секретном, для каждого колеса своём — имеем машину Джефферсона. Впоследствии колёса заменили на полоски с двойным алфавитом, это сделало машину компактнее.

Одноразовый шифроблокнот[править]

Советский шифроблокнот

Вот мы и пришли к широко известному, но переоцененному шифру. Таблица сложения как у Виженера. Однако ключ заведомо длиннее сообщения. Такой ключ уже не запомнишь; у разведчика он записан в специальный блокнот. Разведчик вырывает из блокнота лист, шифрует сообщение, лист уничтожает.

Шифроблокнот — единственный шифр, который не взламывается даже теоретически, независимо от того, сколько раскрыто пар «открытый текст — шифровка». Однако он чувствителен к любому нарушению процедуры. Если вместо случайных букв запишешь сгенерированные компьютером, это уже будет другой (и довольно непрочный) шифр. Даже неравномерное распределение букв ключа (например, если ключом будет какая-то книга, или источник случайности — машинистка, бьющая по клавишам) упрощает перебор. Если разведчик зашифрует два сообщения одной страницей, компьютеризованный враг также без проблем раскроет эту страницу.

Из-за ореола невзламываемости авторы любят совать шифроблокноты куда ни попадя. Это неверно: шифроблокнота должно хватить на всю миссию, да и шифр попроще можно прокрутить в голове — а блокнотом зашифровать только самые важные части наподобие фамилий и чисел. В компьютерной реализации — непонятно, как передавать ключ (а если ключ передавать под другим шифром — прочность такого протокола будет равняться прочности шифра) и как надёжно уничтожить использованные «страницы».

Книжный шифр[править]

Вариантов много: например, в книге находят слово, и передают страницу, строку и номер слова. По этой причине кодовой книгой часто является словарь: в нём есть почти все слова, которые могут понадобиться. Соответственно, ключ — конкретное издание книги. Кодовая книга — замечательный артефакт: детектив должен понять, что является кодовой книгой, и где её достать.

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

Способен ли ручной шифр противостоять компьютерному взлому?[править]

Этот вопрос ещё ждёт своего исследователя. Шифровальщик Брюс Шнайер придумал для писателя Нила Стивенсона шифр «Пасьянс» («шифровальная машина» — колода карт). Однако дальнейшие исследования нашли в «Пасьянсе» несколько уязвимостей.

А вот микросхемы низкой степени интеграции уже способны, неплохие шифры можно реализовать несколькими сотнями логических элементов; AES оценивается в несколько тысяч затворов.

Впрочем, существует древний и совсем не криптографический метод: неизвестный язык. Издавна язык, хоть и с русской грамматикой, но звучащий совсем не по-русски, употребляется маргинальными элементами наподобие офеней. Именно из-за языка сложна война с национальной преступностью. А если язык хоть немного зашифровать — без хорошего лингвиста не разберёшься. Во вторую мировую войну американцы наняли в шифровальщики индейцев навахо — переговоры на экзотическом языке немцы взломать так и не смогли. Русские партизаны с этой же целью использовали самый настоящий язык падонков, а в одном из рассказов о войне, написанных по воспоминаниям ветеранов, в качестве шифра для голосовых переговоров использовался казахский язык. На Тихом океане англичане посадили за радиостанции юных кадетов и приказали им общаться на том французском, которому их учили в школах. Понять их не смогли не только японские специалисты по английскому (которые и занимались радиоперехватом), но и спешно затребованные специалисты по французскому, в то время как сами они друг друга вполне понимали (на уровне «Вич воч? — Сыкс воч!»). Роберт Хайнлайн в повести «Бездна» упоминает speedtalk — искусственный язык скоростного общения. Внимание: сейчас, когда вокруг компьютеры, хоть какой-то шифр всё равно нужен, чтобы статистика букв была поломана. Кнорозов расшифровал язык майя вручную и без билингвы[1].

Ещё в телеграфную эпоху некий Керкгоффс вывел один из принципов военной связи: прочности шифровального ключа должно хватать, чтобы связь оставалась секретной[2], даже если в руки врага попадут остальные компоненты: криптопротокол, алгоритмы шифрования… Вот этому требованию и не отвечает неизвестный язык: если лингвист всё же найдётся, будет очень нехорошо. Шифровальный ключ сменить легко, остальное — крайне трудно.

Электромеханические шифровальные машины[править]

Целый период, грубо от конца Первой мировой войны до развала СССР, и для авторов не слишком благодатный: работа машины всё так же требует человеческого вмешательства, это исключает сложные криптопротоколы. А вот шифры стали намного прочнее, объём переписки увеличился. Чаще всего электромеханическая машина — макгаффин, за которым гоняется «наш» шпион. Дешифровка — дело сложное и скучное, военные шифры с переменным успехом долбают целые институты.

Неавтоматическая шифровальная машина работает так: задаём букву (поворачиваем ручку или жмём на клавиатуре) — на индикаторе шифрованная, задаём вторую — на индикаторе вторая. Автоматическая перфорирует телеграфную ленту или напрямую передаёт сообщение по телеграфному каналу.

Хотя электромеханические машины работали с начала XX века и до распада СССР, известными стали разве что немецкие «Энигма» и «Лоренц». Кстати, прото-ЭВМ были разработаны британцами именно для дешифровки этих машин.

«Игра в имитацию»[править]

Драматично показать расшифровку такой машины крайне сложно, и это видно в фильме «Игра в имитацию» — как раз про Тьюринга и его прото-ЭВМ «Бомба». Кульминация фильма — атака с открытым текстом. Да перепробовать распространённые открытые тексты — особенно такие очевидные, как «Хайль Гитлер» — это первое, что нужно сделать! Кстати, тьюринговская «бомба» работала именно так — перебирала варианты, пока не попадётся забитый в машину кусок открытого текста. И гений Тьюринга нужен был для того, чтобы уменьшить перебор! Маленький совет киношникам от постороннего: нашли бы менее очевидный открытый текст.

А что осталось в фильме за кадром…

  • проколы шифровальщиков (один, впрочем, был вскользь упомянут);
  • постепенное повышение сложности шифрования. На «польском этапе» разбора обходились специальными таблицами (в фильме тоже показанными); изменение криптопротокола и ещё один ротор перекрыли и этот путь;
  • польские механические «бомбочки», на основе которых и была сделана большая «бомба»;
  • эта атака — не окончательная расшифровка, а лишь попытка оправдаться перед правительственной комиссией: мы хоть время от времени, да расшифровываем. На следующий день, когда меняется ключ, всё придётся начинать сначала;
  • раз машина подставляет известные открытые тексты, их специально «выращивали» (да, это официальный термин) — устраивали провокации в конкретных секторах моря…

Компьютерная криптография[править]

(link)

Как работает RSA.

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

  • Пересылка стала настолько «дешёвой», что личная встреча — недопустимая роскошь. Потому надо убеждаться, что противная сторона — именно друг, а не враг под прикрытием.
  • Зато стал возможен «пинг-понг» сообщениями: попробовал бы ты послать что-то шифрованное с курьером и дождаться ответа… Появились сложные криптопротоколы, ставшие фактически шифровальным флеботинумом. Из распространённого: умеет шифровать, но не умеет расшифровывать? — двухключевая схема (RSA, Эль-Гамаль и другие). Прошивку можно модифицировать, но нельзя заменять на неофициальную? — тивоизация (электронная подпись плюс вшитый в устройство ключ проверки). Как наладить секретную связь, когда стороны не знают ключей друг друга? — протоколы Диффи-Хеллмана. Два компьютера, не доверяющие друг другу, сообща генерируют число, гарантированно случайное — протоколы «бросания монеты в колодец».
  • Сами по себе шифры практически не взламываются, так что нужен хороший обоснуй, почему тот или иной протокол — повторяю, не шифр, а протокол! — оказался «колхозным».

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

Симметричные и асимметричные шифры[править]

Ещё один прорыв в криптографии произошёл в 1970-е годы: появился первый двухключевой, или асимметричный шифр RSA. Основан он на том, что перемножить два длинных числа легко, а вот разложить произведение на простые множители — сложно.

В двухключевых шифрах, как следует из названия, два ключа: ключ шифрования и ключ расшифровки.[3] Умея шифровать, ты не сможешь расшифровывать, и наоборот. Проблема лишь в том, что асимметричные шифры в тысячи раз медленнее обычных — так что под асимметричным шифром часто хранят ключ к простому симметричному, которым и зашифровано сообщение.

Обычно один ключ (ключ шифрования) трубят на всю Ивановскую, второй (ключ расшифровки) хранят у себя.

Обычные шифры с одним ключом, в противовес, называют симметричными.

Абсолютно неуязвимыми считаются 4096-битный RSA (асимметричный) и 256-битный AES (симметричный), на практике не поддаются взлому даже 256 и 64 бита[4] — поэтому не стоит описывать шифр с ключом в десятки килобайт.

Почему ключи RSA такие длинные? А потому, что в BlowFish или AES подойдёт любой ключ (кроме горстки «слабых»), в RSA — лишь такие числа, которые будут произведением двух простых чисел.

Криптографическая хэш-функция[править]

Как сказано выше, хэш-функция из длинного сообщения строит свёртку фиксированной длины (число от 0 до N). Если хэш-функции от двух посланий не равны, послания гарантированно не совпадают. Если равны — вероятно, совпадают. Криптографическая хэш-функция должна обладать двумя свойствами: 1) Трудно обратить: для данного числа y трудно подобрать послание s, для которого h(s)=y. 2) Трудно найти коллизию: для тел p и q трудно подобрать суффиксы r и s, чтобы h(p+r) = h(q+s).

Что такое обратить — это понятно. Кто-то подготовил документ, нужно подготовить другой с заданным хэшем — и желательно с заданной осмысленной частью. Впрочем, хэш — штука блочная, и если дать полную свободу хотя бы на одном блоке (и достаточно вычислительной мощи), остальные блоки можно сделать любые наперёд заданные.

Сфабриковать коллизию — интереснее. Готовим два документа с одинаковой свёрткой и заданными осмысленными частями. В нужный момент один подменяем другим.

Наиболее известный криптографический хэш — MD5. Правда, на 2014 он частично скомпрометирован — коллизии фабрикуются даже на обычном ПК. Другими словами: если документ готовил друг, MD5 ещё держится. Если враг — нет.

Имитовставка[править]

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

Также распространены имитовставки на основе хэш-функции (HMAC), выглядят они так:

 HMAC = hash ( (key xor c1) . hash ( (key xor c2) . message ) )

(точка — склеивание байтовых строк, xor — операция «исключающее ИЛИ», c1 и c2 — константы, key — ключ, длина которого соответствует длине блока хэш-функции, message — сообщение.)

Имитовставки используют, если само сообщение несекретно, однако важно подтвердить подлинность (разведчик сообщает численность войск); либо когда транспортный слой умеет прочно шифровать, но никак не может проверить абонента (в HTTPS-службах). Однако тот, кто может проверять имитовставку, может её генерировать. От этого недостатка свободна…

Электронная подпись[править]

Асимметричные шифры позволяют сделать асимметричной и имитовставку. Здесь асимметричный шифр используется наоборот: ключ шифрования надёжно хранят, ключ расшифровки известен всем, кто будет сверять подпись.

Алгоритм тот же: для подписывания берут хэш-функцию и шифруют. Для сверки — расшифровывают и сверяют с настоящей хэш-функцией.

Часто для защиты от модификации прошивок их подписывают: исследовать и переделать можно, а вот прошить в устройство — фигвам! Особо смешно получается, когда даны исходники прошивки (лицензия на Linux требует это), а устройство требует подпись — такие запреты на модификацию называются «тивоизация», в честь медиаплеера TiVo.

Центр сертификации[править]

Как сказано выше, в двухключевой схеме один ключ хранят при себе, второй — доступен везде. Но тогда возникает вопрос: а где гарантия, что найденный ключ принадлежит именно Иванову, и что Петров не расшифрует информацию (а для маскировки перешлёт Иванову сообщение, закрытое правильным ключом)?

К подобной уловке (называется «человек посередине») уязвимы практически все криптопротоколы. Для защиты существует так называемый «центр сертификации»: некая сторона, которой все доверяют, а открытый ключ широко известен. Центр сертификации делает электронную подпись открытого ключа и сопроводительной информации: подпись сошлась — значит, ключ сертифицирован.

Аппаратные шифромодули[править]

Шифромодули бывают трёх типов.

  • Шифровальный сопроцессор. Наиболее простая штука, применяется в специализированных устройствах с закрытыми ОС: основной процессор слаб, а риск вредоносной программы минимален. Даёшь шифровку, даёшь ключ, он и молотит, освобождая время центрального процессора на нечто более ценное.
  • Шифромодуль с хранилищем ключей. Именно так работает обычная телефонная SIM’ка: ключ никогда не покидает шифромодуля, вредоносная программа может зашифровать-расшифровать, а вот украсть ключ — нет. А ещё так устроены электронные ключи защиты от копирования, продвинутые карты контроля доступа.
  • Модуль доверенных вычислений. Не просто хранит ключи, а допускает к шифровке только те программы, у которых есть сертификат. По поводу таких модулей идут большие дебаты: с одной стороны, сильно улучшают жизнь военным и корпоративным пользователям. С другой — мегакорпорация начинает контролировать компьютер, диктовать, какие программы можно запускать, а какие — нет, налаживать непреодолимую защиту от копирования. Так уж вышло, что основные производители компьютеров далеки от медиамагнатов: Intel фильмов не снимает, ASUS музыкантов не окучивает.[5] Так что им выгодно поддерживать «пиратство», и — по крайней мере пока — такие модули остаются на военных и корпоративных машинах. В общем, очередная идея для киберпанк-антиутопии.

Куда идёт криптография?[править]

Шифропанки против тотальной слежки
В якобы «свободной» Великобритании, сплошь утыканной видеокамерами для тотальной слежки, стойкая криптография является уголовным преступлением

Крайне маловероятно, что самые прочные из современных шифров будут вскрыты: энергии Солнца для полного перебора не хватит даже теоретически. Криптография работает над криптопротоколами с самыми необычными свойствами: например, одно и то же сообщение в зависимости от ключа может читаться двумя разными способами. Если вдруг припрут к стенке, можно дать жертвенный ключ — и враг увидит нечто безобидное. Или, например, пятерым членам банды даются ключи, а расшифровать что-либо смогут только трое сообща. Или двое генерируют общий ключ на одну сессию связи, но тот, кто прослушивает канал, этого ключа не увидит. Всё это уже существует.

Приведу пример жизненного криптопротокола, который отдалённо напоминает компьютерные. Собрались трое, надо выбрать, кто пойдёт за водкой. При этом даже при сговоре двоих третий должен быть уверен: если его случайное число правильное, всё будет честно. Для этого каждый бросает от одного до трёх пальцев (например, 1, 3 и 1). Считают до 1+3+1=5, начиная с кого-нибудь; тот, на ком счёт остановится, и идёт за водкой. Впрямую этот протокол на компьютер не переносится[6], однако принцип поняли.

Развитие тайнописи[править]

Тайнопись, она же стеганография — способ скрыть, что секретное сообщение вообще есть. Тайнопись может быть зашифрована, а может и нет.

Древние времена. Обрить посланнику голову, написать сообщение, подождать, пока волосы отрастут.

Древние времена. Невидимые чернила.

Древние времена. Маскировка сообщений под безобидное. Например, Дэвид Кан во «Взломщиках кодов» упоминает сообщение кукольника: «Сломанная кукла в юбке из гавайской травы будет полностью починена к первой неделе февраля» (имеется в виду срок ввода в строй крейсера «Гонолулу»). Учтите, авторы: в военное время запрещено посылать почтой всё, что может стать маскировкой: ноты, схемы вышивки и вязания, шахматные партии, списки чего-нибудь… Цензура бдит, и бдит не за пристойностью, а за шпионажем.[7]

Средние века. Наколы и прочие пометки в книгах.

Эпоха Просвещения. Двоичное кодирование букв особенностями почерка (соединены ли буквы, беглое или нет написание, и т. д.) Каждая буква алфавита кодируется пятью битами.

XX век. Микроточки — фотоснимки размером с типографскую точку, приклеенные к безобидному документу.

Компьютерное время. Информация, встроенная в видео-, звуковые и графические контейнеры наподобие AVI и JPEG.

Компьютерное время. «Жёлтые точки», которые наносит на распечатку любой цветной принтер. Точки кодируют серийный номер устройства, дату и время печати.

Компьютерное время. Нестандартные способы форматирования дисков (например, отформатировать HD-дискету на 80 дорожек, записать информацию в дорожки с нечётными номерами и переформатировать на 40 дорожек). Хранение информации в незадействованных полях файловой системы наподобие сбойных блоков или «хвостов» кластеров.

Компьютерное время. Антипиратские коды, начиная с несуществующей улицы в заштатной деревне и заканчивая точками на киноэкране. Для открытой информации такие коды раскрывают факт «пиратства», для закрытой — кто именно допустил утечку.

Меры против компьютерной тайнописи[править]

Предположим, мы пересылаем какое-то сообщение в безобидной картинке. Как спецслужба может раскрыть факт тайнописи? Вот несколько способов, от простых к сложным.

Найти пустой контейнер. Если картинка скачана из интернета, можно её найти и убедиться, что у тайнописи увеличенный размер при низком качестве.

Поиск «неладного» в контейнере. Чем больше процент полезного сигнала, тем больше следов оставляет тайнопись. Например, если картинки — фотографии с минимальной обработкой, исследование шумов может показать: матрица и дебайеризатор так не шумят.

И просто сопоставлением нескольких сообщений.

Найденную тайнопись придётся ещё расшифровать — но, когда сам факт известен, можно разогревать терморектальный криптоанализатор

Распространённые ошибки[править]

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

  • Основная стратегия шифрования — в том, чтобы при известном алгоритме нельзя было расшифровать сообщение, не зная секретного ключа, или поставить чужую электронную подпись под своими данными. Вопреки этому, встречается представление, будто секрет представляет именно способ шифрования. Это было бы неразумно по ряду причин: широко известный алгоритм может быть неоднократно и многими людьми проверен, в то время как тайный по ясной причине доступен только узкому кругу лиц и может содержать неизвестные уязвимости, которые в любой момент могут быть эксплуатированы; создать новый и хороший алгоритм шифрования — нетривиальная задача для специалистов, и даже когда он создан, должно пройти немало времени, прежде чем можно будет убедиться в его надежности.
    • Тем, кто всё ещё хочет придумать свой шифр: есть несколько удачных взломов самодельных шифров, на слуху DVD и HDCP (оба, что интересно, защита медиаконтента от копирования). Каждый свободный DVD-плеер ломает защиту: это делается за долю секунды, а хранить ключи запрещает DMCA, американский закон о цифровом копирайте.
  • В фильмах, где показывают хакеров, нередко эксплуатируется следующая картина мира: каждая организация или человек использует свой шифр, который хакер за определенное время может взломать, при этом чем серьезнее организация, тем больше уйдет время. На самом деле используется крохотная горстка различных общеизвестных алгоритмов, которые, как правило, никто еще не взломал и, вероятнее всего, не сможет это сделать (а если и сможет, то потратит на это годы сложнейших математических исследований). Нахождение уязвимостей в отдельных алгоритмах быстро становится известно, а, взломай кто-нибудь что-то из фундаментальных принципов шифрования, мир бы сильно изменился. В реальности хакеры существуют, но взламывают они не шифры, а дыры в системах безопасности, уводят пароли из записных книжек секретарш и данные cookies из браузеров на незащищенных машинах, перехватывают и анализуют поток между узлами сети и занимаются кучей разных вещей, совершенно не похожей на то, что показывают обычно в кино.
  • Еще один кинематографический штамп — подбор пароля по символам. Он тоже не имеет ничего общего с реальностью: хэш-функции устроены так, что самое небольшое изменение в аргументе сильно меняет результат, так что есть только один способ подобрать пароль: нужно угадать его точно (а для этого в случае более-менее длинного пароля потребуется невообразимо большое время). Понять, близок ли введенный пароль реальному, нельзя.
  • Приплетать шифроблокноты. Шифроблокнот — это надёжный обратный канал связи такой же пропускной способности и физический источник случайности. Если чего-то нет — это уже не шифроблокнот. Поэтому реально шифроблокноты пригодны для ручного шифрования и отдельных сверхсекретных каналов.
  • Ключи невообразимой длины. Вовсю работают симметричные шифры в 64 бита и асимметричные в 1024 бита, 256 и 4096 — достаточный запас, чтобы будущие слабости не бросили тень на шифр. Таких ключей может быть много (например, в сложных протоколах), но удлинять их до килобайт бессмысленно. Не забывайте: один бит — это вдвое!
  • Никто не скрывает полезную нагрузку (если, конечно, её длина может превысить один блок) под асимметричными шифрами — это расточительство по процессорной мощи. Под асимметричными шифрами хранят обычный симметричный ключ, которым и закрыто сообщение.

Ссылки[править]

Примечания[править]

  1. Розеттский камень, ставший ключом к египетским иероглифам, был на трёх языках.
  2. Первый принцип — достаточная прочность ключа. Второй принцип перед вами. Остальные четыре относятся к практичности: легко меняющийся ключ, сопрягается с телеграфом, управляется одним человеком, проста в использовании.
  3. Точнее, в RSA их три: произведение и два ключа. Одна сторона знает произведение и 1-й ключ, вторая — произведение и 2-й ключ. Оба ключа можно получить, разложив произведение на простые множители… но это адски трудно.
  4. Последний, правда, не AES (у него минимальный ключ 128 бит), а Blowfish — шифр с 64-битным ключом, широко применяемый и всё ещё не скомпрометированный.
  5. Разве что Microsoft идёт на поводу у медиамагнатов: в Windows, начиная с Vista, есть Protected Media Path, задолбавший любого электронщика, строящего нестандартные устройства, Windows 10 отсылает непонятно куда каталоги дисков… Ну и Apple сделала свой магазин контента (iTunes) — но сейчас (2014) её позиция «не быть вредными», противопоставить себя настоящим звукомагнатам.
  6. Время реакции человека намного больше, чем временнóе разрешение зрения. Потому легко увидеть, действовали напарники самостоятельно или отвечали на ваше число. С компьютерами всё наоборот: реагируют они за доли миллисекунды, а типичные сетевые пинги исчисляются десятками миллисекунд.
  7. О цензуре и способах её троллить можно прочитать: «Вы, конечно, шутите, мистер Фейнман».