MTProto

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

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

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

Создание сессий

Регистрация устройства

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

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

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

Создание секретного чата между двумя пользователями

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

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

Примечания

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

Шифрование сообщений

Состав пакета для шифрования

Length	Header	Random bits		Layer	seq_in	seq_out	Header	Random id	TTL	Message			Header	Padding
32 bit	32 bit	128 bit		32 bit	32 bit	32 bit	32 bit	64 bit	32 bit	Произвольная длина			32 bit	0-96 bit
Блок 1			Блок 2			Блок 3			Блок 4		Блоки	Блок N

• 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. В случае коллизии открытый ключ будет сгенерирован снова

Расшифрование сообщений

Структура зашифрованного сообщения

auth_key_id	msg key	Encrypted Data
64 бит	128 бит	N * 128 бит

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

Атаки на протокол

Зеркальная атака и атака повтором

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

Timing-атака

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

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

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

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

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

Криптоанализ

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

Атака #1 (с увеличением длины сообщения)

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

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

Атака #2 (с изменением последнего зашифрованного блока)

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

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

Библиотеки для языков программирования

Название	Язык(и)	Исходный код	Описание
@mtproto/core	JavaScript	https://github.com/alik0211/mtproto-core	Telegram API (MTProto) client library for browser
MadelineProto	PHP	https://github.com/danog/MadelineProto	Async PHP client/server API for the telegram MTProto protocol
Telethon	Python	https://github.com/LonamiWebs/Telethon	Pure Python 3 MTProto API Telegram client library, for bots too!
pyrogram	Python	https://github.com/pyrogram/pyrogram	Telegram MTProto API Client Library and Framework for Python
grammers	Rust	https://github.com/Lonami/grammers	A set of Rust libraries to interact with Telegram’s API
TLSharp	C#	https://github.com/sochix/TLSharp	Telegram client library implemented in C#
TDLib	Python, JavaScript, Go, Java, Kotlin, C#, C++, Swift, Objective-C, Dart, Delphi, Rust, Erlang, PHP, Lua, Ruby, Clojure, Emacs Lisp, D, Elixir, 1С, C, FPC	https://github.com/tdlib/td	Cross-platform library for building Telegram clients. It can be easily used from almost any programming language
MTProto	Go	https://github.com/xelaj/mtproto	Full-native implementation of MTProto protocol on Golang!

Литература

• 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