Для полного понимания происходящего неплохо было бы быть знакомым с основами криптографии, с принципом работы хеш функций (в данной статье SHA-1, SHA-256), а также с такими протоколами как RSA, AES и Diffie-Hellman (приведены ссылки для более подробного ознакомления).
![Рассматриваем тележку, так сказать. Рассматриваем тележку, так сказать.](https://habrastorage.org/getpro/habr/upload_files/d61/89c/06e/d6189c06ead34e45b288bd777df56aec.png)
Оглавление
Предисловие
Здравствуйте, дорогие хабровчане! Я здесь новенький, поэтому не кидайтесь там палками, помидорами и всем прочим (хотя, кидайтесь, мб, полезнее будет). Как один из всадников ноябрь-декабрьского криптографического апокалипсиса, я пришел вам поведать о протоколе, что используется как в секретной переписке с мамой о покупке продуктов, так и в не очень доброжелательных целях.
21-й год на дворе. В чем там сейчас чатятся зумеры, бумеры, думеры, миллениалы и вот эти все касты? Тележка, конечно, тележка. Каждый из нас хочет, чтобы его самые сокровенные секреты, будь то причудливые мемы, переписки со странными субъектами, да и что уж таить, подписки на аниме-каналы, оставались секретами до конца. Но VK же, вроде, удовлетворяет всем нуждам и потребностям, удобно и доступно. Соглашусь, мы в СНГ выросли уже на этой социальной сети, и она нам как родная (а ее, как и тележку, основал Пашенька). Но на данный момент она переживает не лучшие времена, пытаясь подражать всему и вся, добавляя никому не нужный функционал, а также заполняя ленту невероятным количеством рекламы (на каждые 6 постов, 1 рекламный – ужас). Также, бог весть, что там за защита у VK.
В то же время тележка намного проще и чище в плане функционала и рекламы (пока что). Более того, Пашенька позиционирует свой чатек как несокрушимую и непоколебимую крепость в плане взлома, а сам алгоритм шифрования MTProto выставлен перед всеми на обозрение. Так давайте поговорим о внутреннем устройстве MTProto, разработанного собственноручно командой тележки, с точки зрения криптографии.
High-level описание
А дела в алгоритме обстоят довольно запутанно с первого взгляда. Разработчики тележки – самые что ни на есть храбрецы: взять уже готовые протоколы, по типу Signal – не, скучно; создать свой протокол, используя всевозможные известные алгоритмы с добавлением кучи своих фишек и фокусов, чтобы все было еще секретнее и сложнее – прекрасное решение. Так и появился MTProto.
Начать, пожалуй, нужно с описания работы в целом. MTProto – клиент-серверный набор протоколов, служащий для доступа к серверу из клиентского приложения через незащищенное соединение. Этот набор можно разделить на 3 основные части:
![Общая схема работы MTProto 2.0. Общая схема работы MTProto 2.0.](https://habrastorage.org/getpro/habr/upload_files/764/1ae/6b4/7641ae6b4cc7a5f4d192e1cccd52d932.png)
High-level API and Type language: отвечает как за API запросы и ответы, так и за сериализацию данных.
Cryptographic and authorization components: определяет, как приложение (клиент) авторизируется на сервере, а также шифрование сообщений перед отправкой на транспортный уровень.
Transport component: определяет, как клиент и сервер обмениваются сообщениями посредством таких транспортных протоколов, как UDP, TCP, HTTP(S), WebSocket и другие.
Итак, как я и сказал, мы остановимся на втором уровне, связанном с криптографией и авторизацией (C&A), и поглядим, как вся кухня устроена. В свою очередь данный уровень можно поделить на 3 модуля:
Authorization: этот модуль отвечает за первоначальную авторизацию клиента. Он работает во время первого запуска приложения, чтобы получить ключ авторизации.
Secret chat key exchange and rekeying: данный модуль отвечает за установку сессионного общего секретного ключа между клиентами, используемого в сквозном шифровании.
Message encryption: модуль-работяга, не покладая рук, шифрует наши сообщения симметричным шифром AES.
Терминология
Начать наше путешествие, думаю, стоит с описания всех фигурирующих величин и терминов. Для удобства в статье большинство из них будут написаны на забугорском языке (лучше выделяются, а также легче яндексятся).
Итак, дамы и господа, наша сегодняшняя терминология:
Authorization key (AK, auth_key) – 2048-битный ключ, который создается на этапе пользовательской регистрации посредством алгоритма Diffie-Hellman, а доступ к нему имеет только клиент и сервер. Более того, утверждается, что ключ шифруется на сервере, а ключ к ключу отправляется на другой сервер. Таким образом, получение доступа лишь к одному серверу – недостаточно для взлома.
RSA:
– 2048-битный закрытый ключ RSA,
– 2048-битный открытый ключ, используемые на этапе регистрации и генерации ключа авторизации.
Key identifier (auth_key _id) – 64 младших бита хеша (SHA-1) auth_key, которые используются для идентификации конкретного ключа, используемого для шифрования сообщения.
Session_id – случайное 64-битное число, генерируемое клиентом с целью различить отдельные сеансы одного пользователя (на телефоне, на ПК несколько окон).
Server salt – случайное 64-битное число, меняющееся каждые 30 минут (отдельно для каждой сессии) по запросу сервера. Сообщения должны приниматься лишь с новой солью ( :D ), но старые валидны в течение 1800 секунд. Требуется для защиты от атак повторного воспроизведения.
Message identifier (msg_id) – 64-битное число, используемое для однозначной идентификации сообщения в сеансе. Идентификаторы сообщений сервера и клиента должны монотонно увеличиваться (в пределах одного сеанса), и указывать приблизительный момент создания сообщения.
Internal header – 16-байтовый заголовок, добавляемый перед сообщением и содержащий server salt и session_id.
Padding (12-1024 бит) – добавление ничего не значащих данных к информации, нацеленное на повышение криптостойкости.
Message key (msg_key) – средние 128 бит хеша (SHA-256) сообщения, которое надо зашифровать (учитывает при расчёте internal header и padding).
External header – 24-байтовый заголовок, добавляемый перед зашифрованным сообщением и содержащий auth_key_id и msg_key.
Key derivative function (KDF) – функция, формирующая один или несколько секретных ключей на основе секретного значения с помощью псевдослучайной функции (используется SHA-256).
Фух, тяжело, понимаю, прямо как на матане, когда на тебя вываливают гору определений, но крепитесь. Не забудьте открыть в дополнительном окне этот список, чтобы подсмотреть, что за что отвечает (людям с телефона RIP – мотайте).
Клиент-серверное шифрование
Давайте-ка взглянем на схему этого криптографического чуда:
![Алгоритм шифрования для обычных сообщений. Алгоритм шифрования для обычных сообщений.](https://habrastorage.org/getpro/habr/upload_files/9da/451/b5f/9da451b5f40be17887bb29e335495684.png)
Выглядит не так уж и сложно. Ну что тут: обычный Diffie-Hellman, SHA-256, AES – да и все, делов-то. Но давайте все же немного приоткроем завесу тайны и попробуем разобраться, что да как.
В общих словах работа алгоритма такова:
Собирается пакет для шифрования, состоящий из server salt, session_id, самого сообщения (в него включены время, длина и порядковый номер, которые проверяются на стороне получателя) и padding.
Далее, находится msg_key, 128 средних бита хеша (SHA-256) от сообщения с добавлением 32-байтового фрагмента auth_key.
Auth_key в комбинации с новонайденным msg_key определяет при помощи KDF 256-битный aes_key и 256-битный начальный вектор aes_iv.
Далее найденные значения aes_key и aes_iv используются в алгоритме AES IGE для шифрования сообщения.
В самом конце собирается пакет, состоящий из external header, а также зашифрованного сообщения.
Создание auth_key
Начнем с самой важной состовляющей, а в то же время с самой замороченной и интересной, с создания auth_key. В основном здесь используется RSA, SHA-1, AES и Diffie-Hellman, а также добавлены некоторые тонкости для еще большей надежности и секретности. Привожу схему (не пугайтесь):
![Схема получения AK. Схема получения AK.](https://habrastorage.org/getpro/habr/upload_files/235/6b7/e60/2356b7e608751e68aa348c6d102df445.png)
Поехали по порядку:
C: генерирует случайное 128-битное число
(идентифицирует C в рамках этого процесса) и отправляет его.
S: генерирует свое случайное 128-битное число
(далее
включены во все сообщения как в зашифрованном виде, так и в обычном), создает
натуральное число, являющееся произведением простых чисел
и
. После, отправляет
, где
– отпечаток RSA ключа равный 64 нижним битам хеша (SHA-1) известных
(публичный ключ RSA). В свою очередь S хранит
(закрытые ключи RSA) для дешифровки.
C: раскладывает на простые множители
(реализовано для защиты от DoS атак), выбирает публичный ключ
, отвечающий одному из отпечатков
, генерирует еще одно случайное 256-битное число
, которое вместе с
используется для получения эфемерного ключа
и начального вектора
для последующей шифровки сообщения с помощью AES IGE. Посылает
, где
, а также введено обозначение
– шифрование с применением
.
S: выбирает параметры
для алгоритма Diffie-Hellman, рассчитывает
для случайного 2048-битового числа
, вычисляет
. Посылает
, где
(
- серверное время).
C: вычисляет
, рассчитывает
для случайного 2048-битового числа b, проводит советующие проверки для
(об этом чуть дальше), получает auth_key:
. Посылает
, где
, если это первая попытка посылки данного сообщения,
, если S позже запросит для повторного согласования auth_key в том же сеансе путем генерации нового
(такая ситуация может возникнуть при проверке уникальности, выполненной в конце).
S: получает auth_key:
, затем удостоверяется что, полуенный ключ уникальный, сравнивая его хеш с хешами других auth_keys. Если хеш уникален, то S отправляет подтверждение
, в противном случае S отправляет сообщение об ошибке и процесс возвращается к стадии 4.
В течение работы этого алгоритма необходимо делать следующие проверки:
C должен проверить:
и
являются простыми числами,
,
порождает циклическую подгруппу по простому основанию
.
C и S должны верифицировать, что
. Также телеграмм рекомендует, чтобы обе стороны проверяли следующее:
.
C и S должны проверять, что msg_key равен 128 средним битам хеша (SHA-256) расшифрованных данных с добавлением 32-байтового фрагмента auth_key и что msg_id четное для сообщений от C, и нечетное в противном случае.
У C и S должны быть сохранены идентификаторы msg_id последних N сообщений. Если сообщение приходит с идентификатором меньшим или равным тем, что хранятся – сообщение игнорируется. В противном случае новый msg_id сохраняется, и если требуется, самый старый затирается.
![Ну и каша, не правда ли (хотя здесь опущены многие технические фокусы). Ну и каша, не правда ли (хотя здесь опущены многие технические фокусы).](https://habrastorage.org/getpro/habr/upload_files/7ed/bf8/db5/7edbf8db565485a1c786ed92a5c6f3e6.png)
Так-так, самое мудреное и сложное позади, здесь можно выдохнуть. На самом деле это все не так сложно, если позалипать в схему и вчитаться в ход алгоритма.
Немного про AES IGE
Вы могли заметить, как при создании auth_key, так и в основном алгоритме MTProto участвует некое шифрование AES IGE. Это всеми любимое AES шифрование, работающее в Infinite Garble Extension режиме. Пару слов про данный режим:
![Схема AES IGE. Схема AES IGE.](https://habrastorage.org/getpro/habr/upload_files/95d/e05/2ff/95de052ffc78262b1e09f17191db20e2.png)
IGE режим задается следующим цепным равенством:
где – блок шифротекста,
– блок сообщения, которое необходимо закодировать,
– обозначение манипуляций, производимых над блоком сообщения сксоренным с блоком шифротекста предыдущей итерации во время выполнения блочного шифрования (в нашем случае AES) с ключом
,
– индекс, пробегающий от 1 до
(количество текстовых блоков, на которое разбито сообщение). Для запуска сего механизма требуются начальные значения
и
, которые могут быть получены из начального вектора
.
Получается, здесь разработчики не изобретали никаких велосипедов, а лишь повесили на руль звонок. Как они утверждают, их реализация IGE не сломанная и работает вполне прилично, а также тот факт, что ключ зависит от содержимого сообщения, сводит на нет блочно-адаптивные атаки.
![Наберитесь сил, осталось совсем немного. Наберитесь сил, осталось совсем немного.](https://habrastorage.org/getpro/habr/upload_files/5e8/dd1/925/5e8dd19254aa9972f2e145a11a6fe42b.png)
Секретные чаты и сквозное шифрование
Окей, вроде все секретно, все отлично. Но это все под защитой покуда у злоумышленника нет доступа до серверов тележки, так как на них хранится вся зашифрованная переписка вместе с ключами для того, чтобы иметь доступ в нескольких сессиях. Так-так, а вдруг я захочу обсудить с другом кто лучший из BTS, но не хотелось бы, чтобы это знали другие. В такой ситуации есть решение – секретные чаты. Давайте перейдем к рассмотрению сквозного шифрования в тележке.
Наше желание: только пользователи, которые инициируют общение, имеют доступ к переписке, и никто больше, при том только в одной сессии. Для этого нам требуется, чтобы у каждого пользователя были ключи, дающие возможность шифровки и дешифровки сообщений.
Схема шифрования почти идентична с предыдущей:
![Алгоритм шифрования для секретных сообщений. Алгоритм шифрования для секретных сообщений.](https://habrastorage.org/getpro/habr/upload_files/2de/bf5/71a/2debf571af97ec42f642716a941dbbe4.png)
Опять же, в общих словах, по очереди происходит 2 идентичных шифрования с разными ключами SK и AK. Нам требуется добыть SK да так, чтобы никто и никогда не знал его. В этом нам опять же поможет всеми любимый алгоритм DH.
Схема получения SK перед вами (довольно знакомая, не правда ли):
![Схема получения SK. Схема получения SK.](https://habrastorage.org/getpro/habr/upload_files/fb5/02f/a24/fb502fa24684cd7809f33f34f31360af.png)
Кратко о процессе:
A: получает параметры
от S, генерирует
(для определения текущей сессии), рассчитывает
Отправляет
, где
– запрос на инициализацию секретного чата от клиента A клиенту B.
B: при согласии на инициализацию секретного чата, получает параметры
от S, рассчитывает
а также
и его 64-битный хеш (SHA1). Отправляет
.
A: рассчитывает
и сверяет хеш (для удостоверения правильной работы клиентского приложения).
Собственно, все. Теперь сообщение сначала шифруется с использованием ключа SK и алгоритма, расписанного выше, а потом результат проходит второй круг шифрования с использованием AK и отправляется через сервер другому клиенту.
Rekeying (смена ключа шифрования)
Посидели разработчики тележки, посмотрели на все, что они наворотили, почесали репу, да решили, что как-то это все не слишком секретно, ненадежно. А вдруг кто-то получит секретный ключ и сможет расшифровать сообщения. Недолго думая, они взяли да реализовали алгоритм смены ключей. По их задумке секретные ключи, используемые в сквозном шифровании, сменяются каждые 100 сообщений или же каждую неделю. Старые ключи должны быть уничтожены и более не использоваться. Думаю, в третий раз разъяснение алгоритма DH – это уже перебор, поэтому просто приведу схему:
![Схема смены ключа шифрования Схема смены ключа шифрования](https://habrastorage.org/getpro/habr/upload_files/03f/019/0d2/03f0190d2e6805dc973eda644146a494.png)
На данном этапе разработчики почувствовали себя в безопасности и решили остановиться.
Заключение
Фух, смотрите, сколько Пашенька и его команда вложила души в секретность тележки, грех не пользоваться. Хотя, криптоаналитики и разработчики были в полном ужасе, увидав кашу из всех этих алгоритмов и своих тонкостей (в данной статье опущено множество технических подробностей, например, расчеты хэшей, а там все очень и очень запутанно).
Теперь запросы правительств о выдаче ключей шифрования звучат уж слишком смешно. Ну а нам, простым смертным, со спокойной душой можно пользоваться всеми нами любимой тележкой, покуда квантовые компьютеры не пришли и не раздали нам подзатыльники за наши математические фокусы.
Надеюсь, мне удалось донести основы того, как функционирует MTProto и стало немного яснее, как устроено шифрование в мессенджерах (устройство общее). А вам спасибо за ваше внимание и приглашаю в комментарии для дальнейшего обсуждения. Буду рад, если кто-то укажет неточности, ежели таковые заприметит.
P.S. И помните, когда вы отправляете одну-единственную скобку, реагируя на какую-то новость, вы заставляете ваш бедный телефон и сервера тележки вкалывать, чтобы это все было секретно.
![Довольный, наверное понял, как работает MTProto. Довольный, наверное понял, как работает MTProto.](https://habrastorage.org/getpro/habr/upload_files/d38/15b/54f/d3815b54fb5b97beb93fefd67b8b4f94.gif)
Литература и ссылки на почитать
К сожалению или к счастью, все на английском.
A practical cryptanalysis of the Telegram messaging protocol (тут про MTProto 1.0)
UPD: поправил немного про AES IGE.