Interested Article - 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 выбирает ключ , подходящий для пришедшей подписи с сервера S .
  4. C выбирает другую случайную 256-битную строку, отличающуюся от предыдущей строки клиента и сервера. Клиент собирает набор из трех случайных строк, чисел n , p и q , шифрует его с помощью ключа по алгоритму RSA и отправляет на сервер S.
  5. S отвечает с параметрами g , p , протокола Диффи-Хеллмана , зашифрованными алгоритмом AES-256 в режиме IGE , используя временный ключ и Salt , получаемую из новой строки клиента и сервера.
  6. C выбирает закрытый ключ b , вычисляет открытый ключ и общий открытый ключ . Затем (в зашифрованном виде) отправляется на сервер S .

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

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

  1. A соединяется с сервером, чтобы получить параметры для протокола Диффи-Хеллмана — простое p и генератор g . A также получает для генерации секретного ключа a .
  2. A вычисляет открытый ключ и отправляет его пользователю B .
  3. B получает запрос на создание чата и подтверждает его инициализацию только на одном из его авторизованных устройств. Он подключается к серверу для получения последних параметров протокола Диффи-Хэлмана и генерирует свой закрытый ключ b .
  4. B вычисляет открытый ключ и отправляет его A .
  5. Оба пользователя генерируют общий открытый ключ . На этом обмен секретными ключами между пользователями окончен .

Примечания

  • Секретный ключ a генерируется по правилу: , где 2048 бит, сгенерированные генератором случайных чисел на устройстве клиента, — 2048 бит сгенерированные сервером для того, чтобы в случае ненадежного генератора у пользователя усилить стойкость ключа a .
  • Оба клиента проверяют, что сервер прислал им безопасное простое число p (такое что также является простым), число и генерирует циклическую подгруппу по простому основанию . Параметры 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 ( с увеличением длины сообщения )

К сформированному шифротексту , который дешифруется в сообщение , добавляется ещё один блок длиной 128 бит, то есть принимаемый шифротекст . В итоге преобразованное сообщение расшифровывается в виде , в котором , причем длина больше длины блока. Так как длина не проверяется, дешифрование сообщения пройдет успешно .

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

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

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

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

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

Название Язык(и) Исходный код Описание
@mtproto/core JavaScript Telegram API (MTProto) client library for browser
PHP Async PHP client/server API for the telegram MTProto protocol
Telethon Python Pure Python 3 MTProto API Telegram client library, for bots too!
pyrogram Python Telegram MTProto API Client Library and Framework for Python
grammers Rust A set of Rust libraries to interact with Telegram’s API
TLSharp C# 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 Cross-platform library for building Telegram clients. It can be easily used from almost any programming language
MTProto Go Full-native implementation of MTProto protocol on Golang!

Примечания

  1. .
  2. .
  3. , с. 32.
  4. , с. 32—34.
  5. , с. 34—36.
  6. , с. 35.
  7. , с. 37—41.
  8. , с. 41—43.
  9. , с. 51.
  10. , с. 51—52.
  11. , с. 47.
  12. , с. 48.
  13. , с. 49.
  14. , с. 50.

Литература

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

Ссылки

Источник —

Same as MTProto