Самое простое объяснение принципа работы современных алгоритмов симметричного шифрования +21



(Нашёл в твиттере тред с очень крутым объяснением работы симметричных шифров. Его написал Colm MacCarthaigh один из основных контрибьюторов Apache. Я спросил разрешение Колма на перевод, он любезно согласился).


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


Итак, симметричное шифрование — это именно то, что мы используем в большинстве случаев, когда хотим зашифровать кучу данных. Ваш браузер отправляет и получает данные, используя симметричное шифрование. Если вы шифруете файлы или диск, в этом случае тоже работает симметричное шифрование. iMessage, Signal, WhatsApp — все они используют симметричное шифрование для безопасности вашей переписки.


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


Вот простой пример. Допустим, у меня есть строка "Ovaltine" и я хочу её зашифровать. Я мог бы воспользоваться rot13 — очень простым олдскульным шифром Цезаря, который делает хоровод из букв, где a и z держатся за ручки, и заменяет каждую букву другой буквой алфавита, которая находится от заменяемой буквы на расстоянии 13 символов. Таким образом "O" превращается в "B", а "v" становится "i", в итоге "Ovaltine" превращается в "Binygvar". Конечно, это не очень безопасно. Это наивный пример, который очень легко взломать, так как атакующий может выяснить, какая буква встречается чаще всего (обычно в оригинальном тексте это "e") и найти оставшиеся буквы подобным образом.


Сейчас вы можете представить, что должны существовать более хитрые способы "перемешивания" букв. Например, некая сложная схема, в которой "a" переходит в "p", но при повторном шифровании — в "f". Может даже иногда эта схема начинает шифровать "a" двумя буквами, например "jd" или в что-нибудь другое. Таким образом эта усложнённая схема может зашифровать "Ovaltine" в строку "FGyswDmweeRq" (заметьте, что она стала длиннее). В прошлом появлялись алгоритмы шифрования, которые работали подобным образом, но это совсем не так, как работает современное шифрование.


Вместо "перемешивания" букв современное шифрование берёт вашу секретную строку и хитро комбинирует её со случайными данными. Это похоже на rot13 только в двух моментах: шифрование и расшифровка по сути одна и та же операция, и всё происходит "на месте". Действительно, вы заметили что rot13 является одновременно алгоритмом шифрования и расшифровки? rot13(Ovaltine) -> Binygvar, rot13(Binygvar) -> Ovaltine. Я считаю, что это очень красивая симметрия в симметричном шифровании. Но всё же вернёмся к нашей теме. Хитрость заключается в том, что мы используем побитовую операцию XOR. В криптографии, формальной логике и коде программ XOR может обозначаться по разному, но я буду использовать такую нотацию, с которой вы вероятнее всего знакомы. Она выглядит вот так: ^.


XOR — это сокращение от "exclusive OR" (исключающее ИЛИ). Это оператор (или функция, если вам так удобнее думать), которая принимает два аргумента и возвращает результат. A ^ B = C. Этот оператор называется "побитовым", так как применяется к соответствующим друг другу битам. Если A и B байты, то мы можем считать, что A ^ B = C по сути 8 разных операций, которые происходят одновременно. ^ сравнивает первый бит A и первый бит B, а затем помещает результат в первый бит C. Он повторяет тоже самое ещё 7 раз для оставшихся бит. Правила простые: если бит из A "1" ИЛИ бит из B "1", тогда мы устанавливаем соответствующий бит C в "1", но только в том случае, когда "A" и "B" одновременно не являются "1". Это и есть исключающая часть. Вот олдскульная таблица истинности:


A|B|C
0|0|0
1|0|1
0|1|1
1|1|0

Самая клёвое в XOR то, что он похож на rot13. Мы можем использовать его для шифрования и расшифровки. Покажу это на простом примере. Давайте представим, что мы хотим зашифровать обычное число "3" и что наш ключ шифрования другое число "7". Таким образом 3 ^ 7 = 4. То есть результат шифрования — "4". Давайте теперь расшифруем число. Я просто сделаю тоже самое снова: 4 ^ 7 = 3. Возьмите любое число, которое вам нравится или любые данные, и это всегда будет работать — XOR всегда сможет расшифровать себя.


Бит за битом — вот как мы в действительности шифруем и расшифровываем данные, нет никакого перемешивания, только XOR-инг. Трудная часть — поиск данных, к которым мы можем применить XOR. Один из подходов заключается в том, чтобы взять большой кусок секретных данных, лежащих под рукой, и использовать его в качестве второго аргумента XOR. При этом все участники процесса передачи зашифрованных данных должны использовать один и тот же набор секретных данных для шифрования и расшифровки. И это будет работать. Правда есть несколько проблем.


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


Вторая проблема. Вам нельзя переиспользовать секретные данные, так как паттерны проявятся снова. Таким образом вы как-то должны предоставлять большие куски секретных данных для всех, кто в них нуждается как в шифре Вернама (One-time pad). Это слишком трудно.


В современном шифровании мы "генерируем" нужные нам секретные данные из маленьких ключей. Эти ключи гораздо проще таскать с собой и защищать. Вот чем в действительности являются алгоритмы симметричного шифрования — схемами для детерминированной генерации случайных данных из ключа. Часть про "детерминированность" очень важна: два человека с одним и тем же ключом должны генерировать абсолютно один и тот же набор данных, иначе они не смогут понять друг друга. Вероятно, вы слышали про такие алгоритмы: AES, 3DES, DES, RC4, ChaCha20. Все они делают это.


Оказывается, что математическая задача генерации случайного потока данных (в котором нет паттернов в любом предсказуемом виде) с помощью ключа очень сложна. Из этого списка сегодня считаются безопасными только AES и ChaCha20. Другие алгоритмы были взломаны: люди смогли предсказывать их. Причём AES имеет немного запятнанную репутацию, потому что криптографы говорят следующее:


AES — основной и наиболее проанализированный алгоритм шифрования. Абсолютно золотой стандарт! :dark_sunglasses:

Но при этом добавляют:


Реализации AES в программном обеспечении (не в аппаратном) или небезопасны, или медленны, а иногда и не безопасны, и медленны. Он не был разработан с учётом того, что его взлом можно осуществить с помощью анализа кэша. :facepalm:

Не пугайтесь слишком сильно, если это вам непонятно. Главная мысль заключается в следующем: AES шикарен с точки зрения математики, но очень сложен в программной реализации. Но не надо беспокоиться — у нас почти всегда есть поддержка AES на уровне аппаратного обеспечения (список всех процессоров с аппаратной поддержкой AES можно посмотреть тут https://en.wikipedia.org/wiki/AES_instruction_set, — прим. переводчика).


Как бы то ни было, продолжаем… Как эти алгоритмы работают в действительности? Каким образом мы можем взять ключ и безопасно сгенерировать случайный поток данных? Я буду тут немного упрощать и начну с блоков.


Эти алгоритмы получают на вход три параметра и на выходе отдают зашифрованный текст. Входные параметры — ключ, шифруемый текст и… сюрприз — что-то странное под названием "вектор инициализации" (initialization vector, IV).


AES(key, IV, plaintext) -> encrypted_data.

Ключ и IV комбинируются между собой, чтобы создать набор "стартовых условий" для алгоритма; это подобно начальной перестановке или перемешиванию плиток в игре Скрэббл. Одинаковая комбинация ключа и IV всегда будет создавать одинаковый набор стартовых условий. Спрашиваете, почему нам вообще тогда понадобился IV? Нам нужен IV, чтобы мы могли шифровать множество сообщений, используя одинаковый ключ. Без IV, каждый генерируемый поток данных был бы одинаков, и это плохо. Это бы нарушило одно из правил, про которое мы говорили ранее: мы не можем переиспользовать одни и те же данные при шифровании. Таким образом нам нужен IV для перемешивания результата. Но в отличии от ключа IV может быть публичным.


Итак, когда вы шифруете сообщение и отправляете его кому-нибудь, вы также можете добавить: "Эй, а вот IV, который я использовал". При этом всё ещё критично, чтобы мы не переиспользовали комбинацию ключа и IV, потому что они дали бы нам повторяющиеся случайные данные. Для достижения этого условия есть два пути: 1) IV это некий счётчик, который мы увеличиваем с каждым новым сообщением. 2) IV генерируется случайно, при этом у него достаточно большое значение, поэтому нам не надо сильно беспокоиться о коллизиях. Как бы то ни было, я упомянул, что я буду говорить о блоках.


Ключи и IV "смешиваются" или комбинируются таким образом, чтобы создать набор стартовых условий… эти условия на самом деле являются начальным "блоком" случайных данных. Длина этого блока для AES128 128 бит, для AES256 — 256 бит, для ChaCha20 — 512 бит. И вот тут проявляется настоящая магия и индивидуальность конкретного алгоритма шифрования. В действительности их суть заключается в том, каким образом генерируется последовательность блоков и как каждый блок связан со своими соседями. Отношения между этими блоками остаются предсказуемы даже для тех, у кого нет ключа.


Я не буду глубоко погружаться в то, как именно работают эти алгоритмы, но если вы хотите узнать больше, я советую вам начать изучение этой темы с линейного конгруэнтного метода (linear congruential generators, LCG). LCG представляет собой функцию, которая создаёт "циклические" блоки данных в случайном и неповторяющемся виде. Затем взгляните на cеть Фе?йстеля (Feistel networks) — следующий уровень развития LCG. Затем разберитесь с S-Boxes, а потом посмотрите на то как Salsa20 создаёт чередование в алгоритме ChaCha20. Всё это гораздо доступнее, чем вы можете подумать!


Итак, мы теперь знаем, как случайный поток данных может быть скомбинирован с текстом, чтобы его зашифровать и расшифровать, и мы уже немного в теме того, как эти случайные потоки данных создаются. Разве это не всё, что нам надо? Для шифрования диска, это, действительно, почти всё. Мы можем шифровать каждый блок или сектор хранилища с использованием одного ключа и IV, который может быть получен из "позиции" на диске. Таким образом мы можем всегда расшифровать любой блок данных в любом месте на диске, до тех пор пока у нас есть ключ. Но тут есть одна проблемка… кто-нибудь может испортить наши зашифрованные данные. Если я изменю значение любого байта, даже если у меня не будет ключа, то в итоге мы не сможем расшифровать блок. И нет защиты против вмешательства такого вида. В случае отправки сообщений и данных по сети, это становится ещё критичнее. Мы не хотим, чтобы кто-нибудь мог испортить наши передаваемые данные. Таким образом нам надо добавить проверку целостности! Есть несколько схем, для того чтобы это сделать.


HMAC, GCM и Poly1305 — наиболее распространённые современные схемы для проверки целостности. Эти алгоритмы по большому счёту работают так: им на вход подаются данные и другой ключ (так называемый ключ целостности). После вычислений они выдают на выходе MAC (message authentication code) или тэг, который в свою очередь просто другой кусочек данных, выступающий подписью.


Таким образом для шифрования и защиты наша схема может выглядеть так:


AES(key, IV, "Ovaltine") -> encrypted_output
HMAC(key, encrypted_output) -> MAC

и затем по проводам мы отправляем:


IV | encrypted_output | MAC

Для расшифровки мы проверяем MAC, генерируя его снова и сравнивая результат с полученным MAC, а затем расшифровываем данные. Есть внутренние различия в том, как HMAC, GCM и Poly1305 генерируют эти подписи, но вам не надо об этом беспокоиться. На сегодняшний день эту комбинацию операций обычно оборачивают в функцию с именем "AEAD" (Authenticated Encryption with Additional Data). Под капотом она делает всё то, про что я говорил ранее:


AEAD(key, IV, plaintext, additional_data) -> IV_encrypted_data_MAC

Штука под названием "additional_data" — всего лишь данные, с помощью которых вы можете убедиться в том, что эти данные есть у отправляющей стороны, хотя они и не были им отправлены. Это как мета-данные, с помощью которых устанавливаются права доступа. Часто это поле оставляют пустым.


Но тем не менее вы можете поиметь проблемы с AEAD, если будете использовать один и тот же IV. Это плохо! Есть попытки для улучшения этой ситуации: мой коллега, которого зовут Шай, работает над клёвой схемой SIV, добавляющей уровень защиты от этой проблемы. Но если вы используете уникальный IV, современное шифрование очень безопасно. То есть вы можете опубликовать зашифрованный текст в Нью-Йорк Таймс, и никто не сможет его взломать. Шифр будет оставаться неприступен, даже если "некоторая" часть текста будет известна. Например, в интернет-протоколах большое количество текста известно. HTTP-сервера всегда отвечают одинаково и первые байты всегда известны. Но этот факт совсем не имеет значения — он не поможет атакующему узнать ни кусочка оставшихся данных… Мы прошли долгий путь со времён Второй мировой войны.


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


image


Давайте сначала разберёмся с длиной. Очевидно, что длина — это не скрытая характеристика. И это нормально, если вы пытаетесь защитить свой пароль или номер кредитной карты где-то в середине сообщения. Не очень то и большая проблема. Но это означает, что потенциально любой человек может определить тип контента, который вы отправляете. Простой пример: если вы отправляете gif с помощью мессенджера и если размер этого изображения уникален, атакующий, перехватывающий ваши данные, может предположить какая именно гифка была только что отправлена. Есть более хитрые версии этой атаки для Google Maps, Netflix, Wikipedia и т.п. Для защиты от этой атаки можно "добивать" отправляемые сообщения дополнительными байтами, таким образом, чтобы все отправляемые сообщения были одинаковой длины несмотря ни на что. Шифрование, которое используется в военных сетях, всегда "добивает" трафик дополнительными данными, то есть для перехватчика он всегда выглядит одинаковым! Ещё одна проблема, связанная с длиной, заключается в том, что если вы используете сжатие и даёте атакующему возможность изменять любую часть контента на странице, которую видит пользователь, то это даёт возможность атакующему разузнать даже самые маленькие секреты. Поищите атаку под названием "CRIME". Она шикарна и страшна.


Я ещё говорил о том, что другая проблема — тайминг. Очевидно, что время отправки каждого сообщения открытая информация. Это может быть проблемой? Может! Например, если вы отправляете сообщение на каждое нажатие клавиши, тогда тривиально выяснить, что именно печатается с помощью анализа времени. Круто! Другой пример — VOIP. Если ваше приложение для звонков отправляет данные только тогда, когда люди говорят, но не во время молчания, этого достаточно для того, чтобы восстановить 70% английской речи. Всего лишь из тишины. Страшно клёво.


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


Как бы то ни было, это тот уровень объяснения, на котором я хочу сейчас остановиться, но мы рассмотрели самое необходимое, что надо знать. Если вы дочитали до этого момента — спасибо! Сейчас у вас должно быть большее понимание того, что происходит при шифровании и чего следует остерегаться.


Не стесняйтесь задавать вопросы


Перевод публикуется под лицензией CC BY-NC-SA 4.0

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (18):

  1. mmMike
    /#19886784

    Из этого списка сегодня считаются безопасными только AES и ChaCha20. Другие алгоритмы были взломаны: люди смогли предсказывать их

    Что правда что ли? И 3des?! (Double des)
    Как народ то не боится карточками расплачиваться…
    И вообще попытка рассказать все на уровне "детского сада" как то вызывает раздражение. Ощущение что автор снисходительно снизосходит…
    Да лучше стандарты почитать!

    • Myshov
      /#19886806

      > Что правда что ли? И 3des?! (Double des)

      Да, вот тут можно почитать подробнее sweet32.info

      > И вообще попытка рассказать все на уровне «детского сада» как то вызывает раздражение.

      Я думаю, что это, наоборт, преимущество. Человек простым языком объяснил сложные вещи. Такие статьи вдохновляют на изучение чего-то нового.

      • StJimmy
        /#19886888

        Sweet32 не является атакой на конкретный алгоритм, это атака на режим CBC для всех блочных шифров с размером блока 64-бит (при условии, что на одном ключе шифруется достаточно большое количество данных).
        К слову в статье сказано, что все алгоритмы работают по схеме XOR с открытым текстом, но это актуально только для потоковых шифров, блочные шифры работают по такой схеме только в некоторых режимах.
        Ну и

        Длина этого блока для AES128 128 бит, для AES256 — 256 бит, для ChaCha20 — 512 бит

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

        • Myshov
          /#19886894

          > это конечно провал.

          Если тут какая-то ошибка (я её не вижу), напишите об этом в твиттер автору (https://twitter.com/colmmacc/status/1101578627592839168).

          • StJimmy
            /#19886958

            Размер блока для алгоритма AES всегда 128 бит и не зависит от длины ключа (который как раз 128, 192 или 256).
            Для потокового шифра ChaCha20 говорить про размер блока, наверное, не совсем корректно, правильнее было бы говорить о размере состояния шифра.

        • Myshov
          /#19886904

          > Sweet32 не является атакой на конкретный алгоритм

          Но при этом с помощью него был взломан 3DES, так что ссылка правильная.

          • StJimmy
            /#19886960

            Думаю корректнее было бы сказать, что была взломана система шифрования, использующая алгоритм 3DES в режиме CBC (а также любой другой шифр с 64-битным блоком). Сам по себе алгоритм никто не взламывал.

        • Mingun
          /#19887042

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

      • jok40
        /#19886980 / +2

        Человек простым языком объяснил сложные вещи.
        Говоря откровенно, не таким уж и простым языком. Вот пример из статьи:
        Правила простые: если бит из A «1» ИЛИ бит из B «1», тогда мы устанавливаем соответствующий бит C в «1», но только в том случае, когда «A» и «B» одновременно не являются «1».
        Ну и как Вам — простой язык?
        А теперь то же самое действительно простым языком:

        «Если биты A и B — разные, то A^B=1. Если же одинаковые, то A^B=0.»

        • Myshov
          /#19888060

          > Ну и как Вам — простой язык?
          > А теперь то же самое действительно простым языком:
          > «Если биты A и B — разные, то A^B=1. Если же одинаковые, то A^B=0.»

          Для меня лично и ваш вариант понятен, и вариант автора. Но из описания автора сразу становится ясно, почему эта операция носит название «исключающее или».

      • mmMike
        /#19890454

        Да, вот тут можно почитать подробнее sweet32.info
        Уязвимость алгоритма и уязвимость схемы его применения это разные вещи.
        Впрочем, мегя опередили и это прокомментировали

  2. Myshov
    /#19886892

    Удалено. Промахнулся комментарием.

  3. petropavel
    /#19887610 / +2

    Если ваше приложение для звонков отправляет данные только тогда, когда люди говорят, но не во время молчания, этого достаточно для того, чтобы восстановить 70% английской речи. Всего лишь из тишины. Страшно клёво.


    Не поверил. Посмотрел оригинал. Там тоже кто-то не поверил, попросил пруфы. Получил в ответ такую ссылку: www.iis.sinica.edu.tw/~swc/pub/skype_voice_activity_detection.html

    Я почитал, там пытаются находить тишину в трафике скайпа. И с 70-90% точностью им удаётся отлавливать участки тишины, несмотря на шифрование. Про восстановление речи там говорится ну просто совсем. Использования каких-то особеностей именно английской речи, по сравнению с любыми другими, тоже не было. Можно расходиться, сенсации не было.

  4. vburmistrov
    /#19888618

    Причём AES имеет немного запятнанную репутацию, потому что криптографы говорят следующее:


    Кто-то редактировал наш сегмент ru.wikipedia.org/wiki/Triple_DES и сообщил следующее:

    Тем не менее, 3DES понемногу выходит из употребления: на смену ему приходит новый алгоритмом AES Rijndael. Rijndael, реализованный программно, работает в шесть раз быстрее. Поэтому 3DES больше подходит для аппаратных реализаций. Многие системы безопасности продолжают поддерживать как 3DES, так и AES, по умолчанию используя AES. Хотя 3DES может поддерживаться для обратной совместимости, он больше не рекомендован к использованию.


    Все же, что сейчас предпочтительнее в разработке применять?

    • Scratch
      /#19889248

      Писал видимо кто-то из прошлого века, потому что 3des уже давно все забыли. Применять стоит алгоритмы на базе AES или той же ChaCha, зависит от задачи. Посмотрите на библиотеку libsodium

      • mmMike
        /#19890446

        На 3des автоизационные криптограммы по чиповым картам и шифрлвание pin блоков для online pin. И это останется так еще много лет.
        А применять нужно то что требуется для конкретной задачи. Где то и гост нужно (и сертифицированное по)

  5. saipr
    /#19889766 / +1

    Я мог бы воспользоваться rot13 — очень простым олдскульным шифром Цезаря

    Мы в школе еще шифровали на карандаше (где-то читал, что в Греции или Спарте использовали этот метод). На карандаш или какой-то n-гранник накручивается спиралью тонкая полоска бумаги, а потом в строчку на одной из граней вдоль карандаша пишется текст. На других ребрах пишется абракадабра. Потом, когда полоску снимем с карандаша, то получится шифровка. Прочитать можно, если снова накрутить полоску на аналогичный карандаш. Кстати, тоже симметричное шифрование.


    Ну и поскольку это русский хабр следует упомянуть российские алгоритмы симметричного шифрования, а именно ГОСТ 28147-89, Кузнечик и Магму.

  6. vlad9486
    /#19896214

    Но не надо беспокоиться — у нас почти всегда есть поддержка AES на уровне аппаратного обеспечения
    Всегда удивлялся. Кто этому верит? А что если в процессоре стоит бекдор и если записать в пару регистров магические числа, то с каких-то других регистров можно прочитать последние использованные ключи? Шифруешь такой сообщение, а рядом програмка с парой строк ассемблера сливает твои ключи куда надо.

    Вот буквально:

    movl $0xdeadbeef, %r11
    movq %r12, (key)
    movq %r13, (key + 8)

    Вместо 0xdeadbeef подставить секрет известный человеку, который заказал бекдор.