MTProto

MTProto — криптографический протокол, используемый в системе обмена сообщениями Telegram для шифрования сообщений и обмена данных. Протокол был разработан Николаем Дуровым и другими программистами Telegram.

В основе протокола лежит оригинальная комбинация симметричного алгоритма шифрования AES (в режиме IGE), протокола Диффи-Хеллмана для обмена 2048-битными RSA-ключами между двумя устройствами и ряда хеш-функций. Протокол допускает использование шифрования end-to-end с опциональной сверкой ключей^[1][2].

Также на основе протокола был создан MTProxy.

При первом запуске приложения пользователь вводит номер своего телефона, на который приходит пятизначный код его подтверждения^[3].

После ввода кода приложение запускает протокол авторизации^[4]:

1. Клиент С отправляет запрос на сервер S со строкой, составленной из случайной 128-битной последовательности.
2. S отправляет в ответ другую случайную 128-битную последовательность, число n (64-битное) и цифровую подпись публичного ключа RSA (получаемую из младших 64 бит SHA1-хэша публичного ключа сервера).
3. C раскладывает n на два простых числа p и q так, что p < q, и это служит проверкой работы. У клиента есть набор публичных ключей сервера, хранящийся на устройстве. Из него C выбирает ключ ${\displaystyle server_{pk}}$, подходящий для пришедшей подписи с сервера S.
4. C выбирает другую случайную 256-битную строку, отличающуюся от предыдущей строки клиента и сервера. Клиент собирает набор из трех случайных строк, чисел n, p и q, шифрует его с помощью ключа ${\displaystyle server_{pk}}$ по алгоритму RSA и отправляет на сервер S.
5. S отвечает с параметрами g, p, ${\displaystyle g_{a}}$протокола Диффи-Хеллмана, зашифрованными алгоритмом AES-256 в режиме IGE, используя временный ключ и Salt, получаемую из новой строки клиента и сервера.
6. C выбирает закрытый ключ b, вычисляет открытый ключ ${\displaystyle g_{b}=g^{b}{\bmod {p}}}$ и общий открытый ключ ${\displaystyle K=(g_{a})^{b}{\bmod {p}}}$. Затем ${\displaystyle g_{b}}$ (в зашифрованном виде) отправляется на сервер S^[4].

Пользователи A и B хотят инициализировать секретный чат^[5]:

1. A соединяется с сервером, чтобы получить параметры для протокола Диффи-Хеллмана — простое p и генератор g. A также получает ${\displaystyle r_{server}}$ для генерации секретного ключа a.
2. A вычисляет открытый ключ ${\displaystyle g_{a}=g^{a}{\bmod {p}}}$ и отправляет его пользователю B.
3. B получает запрос на создание чата и подтверждает его инициализацию только на одном из его авторизованных устройств. Он подключается к серверу для получения последних параметров протокола Диффи-Хэлмана и генерирует свой закрытый ключ b.
4. B вычисляет открытый ключ ${\displaystyle g_{b}=g^{b}{\bmod {p}}}$ и отправляет его A.
5. Оба пользователя генерируют общий открытый ключ ${\displaystyle K=(g_{a})^{b}{\bmod {p}}=(g_{b})^{a}{\bmod {p}}}$. На этом обмен секретными ключами между пользователями окончен^[5].

• Секретный ключ a генерируется по правилу: ${\displaystyle a=r_{client}\oplus r_{server}}$, где ${\displaystyle r_{client}}$ 2048 бит, сгенерированные генератором случайных чисел на устройстве клиента, ${\displaystyle r_{server}}$ — 2048 бит сгенерированные сервером для того, чтобы в случае ненадежного генератора у пользователя усилить стойкость ключа a.
• Оба клиента проверяют, что сервер прислал им безопасное простое число p (такое что ${\displaystyle q={p-1 \over 2}}$ также является простым), число ${\displaystyle g\in \{2,3,4,5,6,7\}}$ и генерирует циклическую подгруппу по простому основанию ${\displaystyle {p-1 \over 2}}$. Параметры p и q, получаемые от сервера, фиксированы и могут меняться только между версиями приложения^[6].

• Length — длина пакета без учёта padding
• Header — каждый пакет состоит из трех заголовков, содержащих информацию о версии протокола, типе приложенных медиафайлов
• Random bits — 120 бит, сгенерированных клиентом, и 8 бит определяют длину поля в байтах. Используется как Salt для шифрования
• Layer — обозначает версию протокола
• seq_in — количество отправленных сообщений к создателю чата
• seq_out — количество отправленных сообщений от создателя чата
• Random id — произвольное число, сгенерированное отправляющим клиентом, отправляется как текст
• TTL — число секунд, в течение которых получатель сможет видеть сообщение перед его удалением
• Message — сообщение, введенное пользователем (произвольной длины)
• Padding — добавляется непосредственно перед шифрованием

• auth_key — открытый ключ шифрования, полученный при создании чата
• Payload — пакет для шифрования (из предыдущего пункта)
• msg_key — младшие 128 бит SHA1-хэша шифруемого пакета. Используется для проверки корректности при расшифровании
• Padding — 0—96 бит, добавленных для того, чтобы размер блока для шифрования был равен 128 битам
• AES key и IV — параметры для шифрования алгоритмом AES в режиме IGE. Получены с помощью KDF
• KDF (key derivation function) — функция формирования AES key и IV на основе msg_key и auth_key
• auth_key_id — младшие 64 бит SHA1-хэша открытого ключа K. В случае коллизии открытый ключ будет сгенерирован снова^[7]

1. Клиент получает зашифрованное сообщение, проверяет подлинность auth_key_id — вычисляет младшие 64 бит SHA1-хеша открытого ключа K. В случае совпадения значений продолжается расшифровка сообщения
2. С помощью key derivation function формируются AES key и IV
3. Далее происходит поблочное дешифрование данных с помощью алгоритма AES-IGE. В итоге получаем пакет, который должен совпадать с пакетом отправителя.
4. Сравниваем младшие 128 бит SHA1-хэша расшифрованного пакета с пришедшим msg_key. В итоге получаем расшифрованное сообщение^[8].

До 16-й версии протокола клиенты были вынуждены доверять серверу сохранять порядковые номера сообщений, а сами сообщения не обладали подобным механизмом. Но это означало, что сервер злоумышленника имел полный контроль над потоком сообщений. Сервер не имел возможности читать передаваемую информацию, но мог удерживать сообщения, менять их порядок, отправлять их снова. В случае, если хотя бы один из клиентов использует протокол версии 16 и ниже, чат является незащищенным от такого типа атак^[9].

Данный вид атаки использует временной интервал между отправкой сообщения и приемом ответа об ошибке. Большинство пользователей Telegram использует его на мобильных устройствах со слабым сигналом, по этой причине проверка подлинности сообщений замедляется (время, за которое процессор обработает информацию, много меньше времени её получения)^[9].

В Telegram проверки проходят в следующем порядке:

1. Полученный auth_key_id сравнивается с хранящимся на устройстве.
2. После дешифрования длина полученного сообщения должна быть больше 0 и меньше количества полученных байт.
3. Вычисляется msg_key и сравнивается с полученным.
4. Проверяются порядковые номера сообщений с локальным счетчиком.

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

Для осуществления атаки необходимо отправить сообщение в секретном чате, но зашифрованный пакет заменить на случайную последовательность. В результате проверок получатель не подтверждает получения сообщения и в окне отправителя данное сообщение навсегда останется непрочитанным^[10].

По данным публикаций, протокол не имеет ни authenticated encryption (AE), ни indistinguishability under chosen-ciphertext attack (INDCCA)^[1][2].

К сформированному шифротексту ${\displaystyle C=\{tags,y_{1},y_{2},...,y_{l}\}}$, который дешифруется в сообщение ${\displaystyle X=\{tags,message,padding\}}$, добавляется ещё один блок длиной 128 бит, то есть принимаемый шифротекст ${\displaystyle C'=\{tags,y_{1},y_{2},...,y_{l},r\}}$. В итоге преобразованное сообщение расшифровывается в виде ${\displaystyle X'=\{tags,message,padding'\}}$, в котором ${\displaystyle padding'=\{padding,padding^{*}\}}$, причем длина ${\displaystyle padding'}$ больше длины блока. Так как длина ${\displaystyle padding}$ не проверяется, дешифрование сообщения пройдет успешно^[1][11].

Для предотвращения данного типа атаки необходимо лишь проверять длину блока padding, в случае превышения допустимого размера необходимо прекращать дешифрование сообщения^[1][12].

В сформированном шифротексте ${\displaystyle C=\{tags,y_{1},y_{2},...,y_{l}\}}$, который дешифруется в сообщение ${\displaystyle X=\{tags,message,padding\}}$, изменяется последний блок длиной 128 бит, то есть принимаемый шифротекст ${\displaystyle C'=\{tags,y_{1},y_{2},...,y_{l-1},r\}}$. В итоге преобразованное сообщение расшифровывается в виде ${\displaystyle X'=\{tags,message',padding'\}}$, причем длина ${\displaystyle padding'}$ равна длине ${\displaystyle padding\ (p)}$. С вероятностью ${\displaystyle 2^{P-B}}$ дешифрованное сообщение совпадает с оригинальным, но так как максимальная длина добавочного блока ${\displaystyle padding}$ составляет 96 бит, то вероятность составляет ${\displaystyle 2^{-32}}$, таким образом данный вид атаки получается намного более сложным, чем ожидалось^[1][13].

Чтобы предотвратить данный тип атаки, необходимо добавить тег проверки padding в заголовки отправляемого сообщения, но исправления в протоколе не позволят пользователям с новым протоколом обмениваться сообщениями с пользователями, у которых остался старый^[1][14].

• Jakob Bjerre Jakobsen. On the CCA (in)Security of MTProto. — 2016. — ISBN 978-1-4503-4564-4.
• A practical cryptanalysis of the Telegram messaging protocol  (неопр.). Дата обращения: 24 февраля 2017. Архивировано из оригинала 14 января 2016 года.

• https://core.telegram.org/mtproto
• https://web.archive.org/web/20161129083141/https://unhandledexpression.com/2013/12/17/telegram-stand-back-we-know-maths/
• https://www.incibe.es/extfrontinteco/img/File/intecocert/EstudiosInformes/INT_Telegram_EN.pdf

Для улучшения этой статьи желательно: Проставить сноски, внести более точные указания на источники. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.