Шо там по MTProto в Telegram-то?

Для полного понимания происходящего неплохо было бы быть знакомым с основами криптографии, с принципом работы хеш функций (в данной статье SHA-1, SHA-256), а также с такими протоколами как RSA, AES и  Diffie-Hellman (приведены ссылки для более подробного ознакомления).

Рассматриваем тележку, так сказать.Рассматриваем тележку, так сказать.

Оглавление

Предисловие

Здравствуйте, дорогие хабровчане! Я здесь новенький, поэтому не кидайтесь там палками, помидорами и всем прочим (хотя, кидайтесь, мб, полезнее будет). Как один из всадников ноябрь-декабрьского криптографического апокалипсиса, я пришел вам поведать о протоколе, что используется как в секретной переписке с мамой о покупке продуктов, так и в не очень доброжелательных целях.

21 год на дворе. В чем там сейчас чатятся зуммеры, бумеры, думеры, миллениалы и вот эти все касты? Тележка, конечно, тележка. Каждый из нас хочет, чтобы его самые сокровенные секреты, будь то причудливые мемы, переписки со странными субъектами, да и что уж таить, подписки на аниме-каналы, оставались секретами до конца. Но VK же, вроде, удовлетворяет всем нуждам и потребностям, удобно и доступно. Соглашусь, мы в СНГ выросли уже на этой социальной сети, и она нам как родная (а ее, как и тележку, основал Пашенька). Но на данный момент она переживает не лучшие времена, пытаясь подражать всему и вся, добавляя никому ненужный функционал, а также заполняя ленту невероятным количеством рекламы (на каждые 6 постов, 1 рекламный — ужас). Также, бог весть, что там за защита у VK.

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

High-level описание

А дела в алгоритме обстоят довольно запутанно с первого взгляда. Разработчики тележки, самые что ни на есть храбрецы: взять уже готовые протоколы, по типу Signal — не, скучно; создать свой протокол, используя всевозможные известные алгоритмы с добавлением кучи своих фишек и фокусов, чтобы все было еще секретнее и сложнее — прекрасное решение. Так и появился MTProto.

Начать, пожалуй, нужно с описания работы в целом. MTProto — клиент-серверный набор протоколов, служащий для доступа к серверу из клиентского приложения через незащищенное соединение. Этот набор можно разделить на 3 основные части:

Общая схема работы MTProto 2.0.Общая схема работы MTProto 2.0.

  • 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.

Терминология

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

Итак, дамы и господа, наша сегодняшняя терминология:

  1. Authorization key (AK, auth_key) — 2048-битный ключ, который создается на этапе пользовательской регистрации по средством алгоритма Diffie-Hellman, а доступ к нему имеет только клиент и сервер. Более того, утверждается, что ключ шифруется на сервере, а ключ к ключу отправляется на другой сервер. Таким образом, получение доступа лишь к одному серверу — недостаточно для взлома.

  2. RSA: sk^i— 2048-битный закрытый ключ RSA, pk^i— 2048-битный открытый ключ, используемые на этапе регистрации и генерации ключа авторизации.

  3. Key identifier (auth_key _id) — 64 младших бита хеша (SHA-1) auth_key, которые используются для идентификации конкретного ключа, используемого для шифрования сообщения.

  4. Session_id — случайное 64-битное число, генерируемое клиентом с целью различить отдельные сеансы одного пользователя (на телефоне, на ПК несколько окон).

  5. Server salt — случайное 64-битное число, меняющееся каждые 30 минут (отдельно для каждой сессии) по запросу сервера. Сообщения должны приниматься лишь с новой солью (: D), но старые валидны в течение 1800 секунд. Требуется для защиты от атак повторного воспроизведения.

  6. Message identifier (msg_id) — 64-битное число, используемое для однозначной идентификации сообщения в сеансе. Идентификаторы сообщений сервера и клиента должны монотонно увеличиваться (в пределах одного сеанса), и указывать приблизительный момент создания сообщения.

  7. Internal header — 16-байтовый заголовок, добавляемый перед сообщением и содержащий server salt и session_id.

  8. Padding (12–1024 бит) — добавление ничего не значащих данных к информации, нацеленное на повышение криптостойкости.

  9. Message key (msg_key) — средние 128 бит хеша (SHA-256) сообщения, которое надо зашифровать (учитывает при расчёте internal header и padding).

  10. External header — 24-байтовый заголовок, добавляемый перед зашифрованным сообщением и содержащий auth_key_id и msg_key.

  11. Key derivative function (KDF) — функция, формирующая один или несколько секретных ключей на основе секретного значения с помощью псевдослучайной функции (используется SHA-256).

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

Клиент-серверное шифрование

Давайте-ка взглянем на схему этого криптографического чуда:

Алгоритм шифрования для обычных сообщений.Алгоритм шифрования для обычных сообщений.

Выглядит не так уж и сложно. Ну что тут: обычный Diffie-Hellman, SHA-256, AES — да и все, делов-то. Но давайте все же немного приоткроем завесу тайны и попробуем разобраться что да как.

В общих словах работа алгоритма такова:

  1. Собирается пакет для шифрования, состоящий из server salt, session_id, самого сообщения (в него включены время, длина и порядковый номер, которые проверяются на стороне получателя) и padding.

  2. Далее, находится msg_key, 128 средних бита хеша (SHA-256) от сообщения с добавлением 32-байтового фрагмента auth_key.

  3. Auth_key в комбинации с ново найденным msg_key определяет при помощи KDF 256-битный aes_key и 256-битный начальный вектор aes_iv.

  4. Далее найденные значения aes_key и aes_iv используются в алгоритме AES IGE для шифрования сообщения.

  5. В самом конце собирается пакет, состоящий из external header, а также зашифрованного сообщения.

Создание auth_key

Начнем с самой важной состовляющей, а в то же время с самой замороченной и интересной, с создания auth_key. В основном здесь используется RSA, SHA-1, AES и Diffie-Hellman, а также добавлены некоторые тонкости для еще большей надежности и секретности. Привожу схему (не пугайтесь):

Схема получения AK.Схема получения AK.

Поехали по порядку:

  1. C: генерирует случайное 128-битное число n_c(идентифицирует C в рамках этого процесса) и отправляет его.

  2. S: генерирует свое случайное 128-битное числоn_s(далее n_c, n_sвключены во все сообщения как в зашифрованном виде, так и в обычном), создает N = ml(N\leq2^{63}-1)натуральное число, являющееся произведением простых чисел mиl. После, отправляет n_c, n_s, fp^1, ..., fp^d, где fp^i— отпечаток RSA ключа равный 64 нижним битам хеша (SHA-1) известных pk^i(публичный ключ RSA). В свою очередь S хранит sk^1, ..., sk^d(закрытые ключи RSA) для дешифровки.

  3. C: раскладывает на простые множители N(реализовано для защиты от DoS атак), выбирает публичный ключ pk^i, отвечающий одному из отпечатков fp^i, генерирует еще одно случайное 256-битное число n_k, которое вместе с n_sиспользуется для получения эфемерного ключа kи начального вектора iv для последующей шифровки сообщения с помощью AES IGE. Посылает n_c, n_s, m, l, fp^i, \begin{Bmatrix}SHA1(M_c^1), M_c^1\end{Bmatrix}_{pk^i}, где M_c^1 = N, m, l, n_c, n_s, n_k, а также введено обозначение \begin{Bmatrix} \end{Bmatrix}_{x} — шифрование с применением x.

  4. S: выбирает параметры p, gдля алгоритма Diffie-Hellman, рассчитывает g_a = g^a mod p для случайного 2048-битового числа a, вычисляет (k, iv) = kdf(n_s, n_k). Посылает n_c, n_s, \begin{Bmatrix} SHA1(M_s), (M_s) \end{Bmatrix}_{(k, iv)}, где M_s = n_c, n_s, g, p, g_a, time(time— серверное время).

  5. C: вычисляет (k, iv) = kdf(n_s, n_k), рассчитывает g_b = g^b mod pдля случайного 2048-битового числа b, проводит советующие проверки для g, p, g_a, g_b(об этом чуть дальше), получает auth_key: AK = g_a^b mod p. Посылает n_c, n_s, retry, g_b, \begin{Bmatrix} SHA1(M_c^2), (M_c^2) \end{Bmatrix}_{(k, iv)}, где M_c ^2 = n_c, n_s, retry, g_b;
    retry = 0, если это первая попытка посылки данного сообщения, retry = hash, если S позже запросит для повторного согласования auth_key в том же сеансе путем генерации нового b(такая ситуация может возникнуть при проверке уникальности, выполненной в конце).

  6. S: получает auth_key: AK = g_b^a mod p, затем удостоверяется что, полуенный ключ уникальный, сравнивая его хеш с хешами других auth_keys. Если хеш уникален, то S отправляет подтверждение n_c, n_s, hash(n_k), в противном случае S отправляет сообщение об ошибке и процесс возвращается к стадии 4.

В течение работы этого алгоритма необходимо делать следующие проверки:

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

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

Немного про AES IGE

Вы могли заметить, как при создании auth_key, так и в основном алгоритме MTProto учавствует некое шифрование AES IGE. Это всеми любимое AES шифрование, работающее в Infinite Garble Extension режиме. Пару слов про данный режим:

Схема AES IGE.Схема AES IGE.

IGE режим задается следующим цепным равенством:

c_i = f_K(m_i \oplus c_{i-1})\oplus m_{i-1},

где c_i— блок шифротекста, m_i— блок сообщения, которое необходимо закодировать, f_K— обозначение манипуляций, производимых над блоком сообщения сксоренным с блоком шифротекста предыдущей итерации во время выполнения блочного шифрование (в нашем случае AES) с ключом K, i— индекс, пробегающий от 1 до n(количество текстовых блоков, на которое разбито сообщение). Для запуска сего механизма требуется начальные значения c_oи m_0, которые могут быть получены из начального вектора iv.

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

Наберитесь сил, осталось совсем немного.Наберитесь сил, осталось совсем немного.

Секретные чаты и сквозное шифрование

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

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

Схема шифрования почти идентична с предыдущей:

Алгоритм шифрования для секретных сообщений.Алгоритм шифрования для секретных сообщений.

Опять же, в общих словах, по очереди происходит 2 идентичных шифрования с разными ключами SK и AK. Нам требуется добыть SK да так, чтобы никто и никогда не знал его. В этом нам опять же поможет всеми любимый алгоритм DH.

Схема получения SK перед вами (довольно знакомая, не правда ли):

Схема получения SK.Схема получения SK.

Кратко о процессе:

  1. A: получает параметры g, pот S, генерирует id(для определения текущей сессии), рассчитывает g_a = g^amod p.Отправляет \begin{Bmatrix} id, Q_{AB}, g_a \end{Bmatrix}_{K_{AS}}, где Q_{AB}— запрос на инициализацию секретного чата от клиента A клиенту B.

  2. B: при согласии на инициализацию секретного чата, получает параметры g, pот S, рассчитываетg_b = g^b mod p,а также SK = g_a^b mod pи его 64-битный хеш (SHA1). Отправляет \begin{Bmatrix} id, g_a, SHA1(SK) \end{Bmatrix}_{K_{BS}}.

  3. A:   рассчитывает SK = g_b^a mod pи сверяет хеш (для удостоверения правильной работы клиентского приложения).

Собственно все. Теперь сообщение сначала шифруется с использованием ключа SK и алгоритма, расписанного выше, а потом результат проходит второй круг шифрования с использованием AK и отправляется через сервер другому клиенту.

Rekeying (смена ключа шифрования)

Посидели разработчики тележки, посмотрели на все, что они наворотили, почесали репу, да решили, что как-то это все не слишком секретно, ненадежно. А вдруг кто-то получит секретный ключ и сможет расшифровать сообщения. Недолго думая, они взяли да реализовали алгоритм смены ключей. По их задумке секретные ключи, используемые в сквозном шифровании, сменяются каждые 100 сообщений или же каждую неделю. Старые ключи должны быть уничтожены и более не использоваться. Думаю, в третий раз разъяснение алгоритма DH — это уже перебор, поэтому просто приведу схему:

Схема смены ключа шифрованияСхема смены ключа шифрования

На данном этапе, разработчики почувствовали себя в безопасности и решили остановиться.

Заключение

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

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

Надеюсь, мне удалось донести основы того, как функционирует MTProto и стало немного яснее, как устроено шифрование в мессенджерах (устройство \pmобщее). А вам спасибо за ваше внимание и приглашаю в комментарии для дальнейшего обсуждения. Буду рад, если кто-то укажет неточности, ежели таковые запреметит.

P.S. И помните, когда вы отправляете одну единственную скобку, реагируя на какую-то новость, вы заставляете ваш бедный телефон и сервера тележки вкалывать, чтобы это все было секретно.

Довольный, наверное понял, как работает MTProto.Довольный, наверное понял, как работает MTProto.

Литература и ссылки на почитать

К сожалению или к счастью, все на английском.

© Habrahabr.ru