Создание ключа авторизации

При описании формата запросов используется двоичная сериализация данных и язык TL. Все большие числа передаются как строки (string), содержащие нужную последовательность байтов в порядке big-endian. Хэш-функции вроде SHA1 возвращают строки (из 20 байтов), которые также могут быть проинтерпретированы как big-endian числа. Маленькие числа (int, long, int128, int256) обычно little-endian; однако если они представляют собой часть SHA1, то байты не переставляются. Таким образом, если long _x_ есть младшие 64 бита от SHA1 от строки s, то берутся последние 8 байтов 20-байтной строки SHA1(**s**), и интерпретируются как 64-битное целое.

Последовательность действий

Прежде чем отсылать незашифрованные сообщения (в данном случае — необходимые для создания авторизационного ключа), клиент должен пройти «(p,q)-авторизацию» следующим образом:

Вычисление nonce

Клиент шлёт серверу запрос:

req_pq#60469778
    nonce:int128
= ResPQ

Значение nonce выбирается клиентом произвольно (случайное число); оно идентифицирует клиента в рамках данного обмена. После этого шага оно известно всем.

Ответ сервера

Сервер отправляет ответ в виде:

resPQ#05162463
    nonce:int128
    server_nonce:int128
    pq:string
    server_public_key_fingerprints:Vector long
= ResPQ

Здесь «строка» pq представляет собой запись натурального числа (в двоичной системе в формате big-endian). Это число является произведением двух различных нечетных простых чисел. Обычно pq не превосходит 2^63-1. Значение server_nonce выбирается сервером произвольно; после этого шага оно известно всем.

server_public_key_fingerprints — это список отпечатков публичных RSA-ключей (младшие 64 бита SHA1 (server_public_key); при этом публичный ключ представляется как голый тип rsa_public_key n:string e:string = RSAPublicKey (bare type; подробней про типы см. в статье «сериализация бинарных данных»), где, как обычно, n и е — числа в формате big-endian, сериализованные как строки байтов, после чего и вычисляется SHA1), принимаемых сервером.

Отметим, что все последующие сообщения содержат пару (nonce, server_nonce) и в открытой, и в зашифрованной части, что позволяет использовать ее для идентификации «временной сессии» (одного запуска обсуждаемого протокола создания ключей). Злоумышленник не в состоянии создать параллельную сессию с сервером с такими же параметрами и переиспользовать зашифрованные клиентом или сервером части их сообщений в своих целях в параллельной сессии, поскольку для новой «временной сессии» сервером будет выбран другой server_nonce.

Доказательство выполнения работы

Клиент раскладывает число pq на простые множители p < q. Теперь начинается раунд обмена ключей по Диффи—Хелману:

Отправка серверу и аутентификация

Клиент отправляет запрос:

req_DH_params#d712e4be
    nonce:int128
    server_nonce:int128
    p:string
    q:string
    public_key_fingerprint:long
    encrypted_data:string
= Server_DH_Params

Здесь encrypted_data получается следующим образом:

  • new_nonce := еще одно (хорошее) случайное число, сгенерированное клиентом; после этого запроса оно известно клиенту и серверу;
  • data := сериализация следующего:
    p_q_inner_data#83c95aec
        pq:string
        p:string
        q:string
        nonce:int128
        server_nonce:int128
        new_nonce:int256
    = P_Q_inner_data

    или этого

    p_q_inner_data_temp#3c6a84d4
        pq:string
        p:string
        q:string
        nonce:int128
        server_nonce:int128
        new_nonce:int256
        expires_in:int
    = P_Q_inner_data;
  • data_with_hash := SHA1(данных) + (данные) + (любые рандомные байты); длина этого должна равняться 255 байтам;
  • encrypted_data := RSA (data_with_hash, server_public_key); — 255-байтное длинное число (big-endian) возводится в нужную степень по нужному модулю, результат записывается как 256-байтное число.

Кто-то может перехватить этот запрос и послать вместо него свой, самостоятельно разложив pq на множители вместо клиента. Единственное поле, которое имеет смысл при этом изменить — это new_nonce, который злоумышленнику как раз придется генерировать заново (поскольку он не в состоянии расшифровать зашифрованные данные, отправленные клиентом). Поскольку все последующие сообщения зашифрованы с помощью new_nonce или содержат new_nonce_hash, они не будут обработаны клиентом (злоумышленник не сможет сделать вид, что их сгенерировал сервер, поскольку в них не будет new_nonce). Поэтому результатом такого перехвата будет только то, что злоумышленник вместо клиента завершит протокол создания авторизационного ключа и создаст новый ключ (не имеющий никакого отношения к клиенту); однако он мог бы и так добиться того же эффекта, просто инициировав создание нового ключа от своего имени.

Альтернативная форма внутренних данных (p_q_inner_data_temp) используется для создания временных ключей, которые сохраняются только в RAM сервера и стираются не более чем через expires_in секунд. Сервер свободно может стереть эту копию раньше. Во всех остальных отношениях протокол генерации временных ключей такой же. После того как временный ключ создан, клиент обычно привязывает его к основному ключу авторизации посредством метода auth.bindTempAuthKey и использует его для всех коммуникаций клиент-сервер до того как его срок истечёт; затем генерируется новый временный ключ. Таким образом в коммуникации клиент-сервер достигается Perfect Forward Secrecy.

Сервер отвечает двумя способами:

server_DH_params_fail#79cb045d
    nonce:int128
    server_nonce:int128
    new_nonce_hash:int128
= Server_DH_Params
server_DH_params_ok#d0e8075c
    nonce:int128
    server_nonce:int128
    encrypted_answer:string
= Server_DH_Params

Здесь encrypted_answer получается таким образом:

  • new_nonce_hash := 128 бит нижнего порядка SHA1 (new_nonce);
  • answer := serialization
    server_DH_inner_data#b5890dba
        nonce:int128
        server_nonce:int128
        g:int
        dh_prime:string
        g_a:string
        server_time:int
    = Server_DH_inner_data
  • answer_with_hash := SHA1(ответ) + ответ + (0-15 рандомных байт); длина должна делиться на 16;
  • tmp_aes_key := SHA1(new_nonce + server_nonce) + substr (SHA1(server_nonce + new_nonce), 0, 12);
  • tmp_aes_iv := substr (SHA1(server_nonce + new_nonce), 12, 8) + SHA1(new_nonce + new_nonce) + substr (new_nonce, 0, 4);
  • encrypted_answer := AES256_ige_encrypt (answer_with_hash, tmp_aes_key, tmp_aes_iv); здесь tmp_aes_key — это 256-битный ключ, tmp_aes_iv — это 256-битный вектор инициализации. Так же и во всех других инстанциях, которые используют шифрование AES, зашифрованные данные подбиваются рандомными байтами до длины, делимой на 16, сразу перед шифрованием.

После этого шага new_nonce всё ещё известно только клиенту и серверу. Клиент уверен, что ответил именно сервер и что ответ сгенерирован специально в ответ на запрос клиента req_DH_params, поскольку данные ответа шифруются с использованием new_nonce.

От клиента ожидается проверка того, является ли p = dh_prime верным 2048-битным простым числом (имеется в виду, что и p и (p-1)/2 являются простыми числами, и что 2^2047 < p < 2^2048), и что g генерирует циклическую подгруппу простого порядка (p-1)/2, т. е. является квадратичным вычетом mod p. Поскольку g всегда равняется 2, 3, 4, 5, 6 или 7, это легко делается с помощью квадратичного закона взаимности; получается простое условие на p mod 4g — именно, p mod 8 = 7 для g = 2; p mod 3 = 2 для g = 3; нет дополнительного условия для g = 4; p mod 5 = 1 или 4 для g = 5; p mod 24 = 19 или 23 для g = 6; и p mod 7 = 3, 5 или 6 для g = 7. После того как g и p проверены клиентом, имеет смысл кэшировать результат, чтобы в будущем не повторять длинные вычисления.

Если верификация занимает слишком много времени (в случае использования более старых мобильных девайсов), она может вначале запустить только 15 итераций Миллера-Рабина для верификации первичности /принадлежности к простым числам p и (p — 1)/2 с вероятностью ошибки не превышающей одну миллиардную, и сделать больше итераций позднее в фоновом режиме.

Другой оптимизацией может быть встраивание в код приложения клиента маленькую таблицу с некоторыми «хорошими» парами (g,p) (или просто известные верные простые числа p, поскольку g легко проверяется во время выполнения), проверяемую во время фазы генерации кода, чтобы избежать выполнения такой верификации во время выполнения. Сервер изменяет эти значения редко, таким образом обычно требуется подставить в такую таблицу текущее значение dh_prime сервера. Например, текущее значение dh_prime равняется (в порядке байт big-endian):

C7 1C AE B9 C6 B1 C9 04 8E 6C 52 2F 70 F1 3F 73 98 0D 40 23 8E 3E 21 C1 49 34 D0 37 56 3D 93 0F 
48 19 8A 0A A7 C1 40 58 22 94 93 D2 25 30 F4 DB FA 33 6F 6E 0A C9 25 13 95 43 AE D4 4C CE 7C 37 
20 FD 51 F6 94 58 70 5A C6 8C D4 FE 6B 6B 13 AB DC 97 46 51 29 69 32 84 54 F1 8F AF 8C 59 5F 64 
24 77 FE 96 BB 2A 94 1D 5B CD 1D 4A C8 CC 49 88 07 08 FA 9B 37 8E 3C 4F 3A 90 60 BE E6 7C F9 A4 
A4 A6 95 81 10 51 90 7E 16 27 53 B5 6B 0F 6B 41 0D BA 74 D8 A8 4B 2A 14 B3 14 4E 0E F1 28 47 54 
FD 17 ED 95 0D 59 65 B4 B9 DD 46 58 2D B1 17 8D 16 9C 6B C4 65 B0 D6 FF 9C A3 92 8F EF 5B 9A E4 
E4 18 FC 15 E8 3E BE A0 F8 7F A9 FF 5E ED 70 05 0D ED 28 49 F4 7B F9 59 D9 56 85 0C E9 29 85 1F 
0D 81 15 F6 35 B1 05 EE 2E 4E 15 D0 4B 24 54 BF 6F 4F AD F0 34 B1 04 03 11 9C D8 E3 B9 2F CC 5B

Генерация ключа

Клиент вычисляет рандомное 2048-битное число b (используя достаточное количество энтропии) и посылает серверу запрос:

set_client_DH_params#f5045f1f
    nonce:int128
    server_nonce:int128
    encrypted_data:string
= Set_client_DH_params_answer

Здесь encrypted_data получается таким образом:

  • pow(g, b) mod dh_prime;
  • data := serialization
    client_DH_inner_data#6643b654
        nonce:int128
        server_nonce:int128
        retry_id:long
        g_b:string
    = Client_DH_Inner_Data;
  • data_with_hash := SHA1 (данных) + данные + (0-15 рандомных байт), длина должна делиться на 16;
  • encrypted_data := AES256_ige_encrypt (data_with_hash, tmp_aes_key, tmp_aes_iv);

Поле retry_id равняется нулю во время первой попытки; или равняется auth_key_aux_hash от предыдущей зафейленной попытки (см. пункт 9).

Вычисление auth_key

Соответственно, auth_key равняется pow(g, {ab}) mod dh_prime; на сервере оно вычисляется как pow(g_b, a) mod dh_prime, а на клиенте как (g_a)^b mod dh_prime.

Вычисление auth_key_hash

auth_key_hash вычисляется := 64 бита нижнего порядка SHA1 (auth_key). Сервер проверяет, если ли уже другой ключ с таким же auth_key_hash и отвечает одним из следующих способов.

Завершение обмена ключами

Сервер отвечает одним из трёх способов:

dh_gen_ok#3bcbf734
    nonce:int128
    server_nonce:int128
    new_nonce_hash1:int128
= Set_client_DH_params_answer
dh_gen_retry#46dc1fb9
    nonce:int128
    server_nonce:int128
    new_nonce_hash2:int128
= Set_client_DH_params_answer
dh_gen_fail#a69dae02
    nonce:int128
    server_nonce:int128
    new_nonce_hash3:int128
= Set_client_DH_params_answer
  • new_nonce_hash1, new_nonce_hash2, и new_nonce_hash3 вычисляются как 128 бит нижнего порядка SHA1 строки байтов, полученной из строки new_nonce добавлением одного байта со значением 1, 2 или 3, с последующими другими 8 байтами с auth_key_aux_hash. Разные значения необходимы, чтобы помешать нарушителю изменить ответ сервера dh_gen_ok на dh_gen_retry.
  • auth_key_aux_hash это 64 бита высшего порядка SHA1(auth_key). Его нельзя путать с auth_key_hash.

В другом случае, клиент обращается к пункту 6) генерируя новое b.

В первом случае, клиент и сервер реализуют auth_key, после чего они забывают все остальные временные данные, и клиент создаёт другую зашифрованную сессию используя auth_key. В то же самое время server_salt вначале устанавливается как substr(new_nonce, 0, 8) XOR substr(server_nonce, 0, 8). При необходимости клиент сохраняет разницу между server_time полученным в пункте 5) и своим местным временем, чтобы иметь хорошую приблизительную точность к времени сервера, которая нужна для генерации правильных идентификаторов сообщения.

ВАЖНО: Помимо условий простого числа Диффи-Хеллмана dh_prime и генератора g, обе стороны должны проверить что g, g_a и g_b больше 1 и меньше чем dh_prime − 1. Мы рекомендуем также проверять, что g_a и g_b находятся между 2^{2048-64} и dh_prime − 2^{2048-64}.

Обработка ошибок

В том случае, если клиент не получает никакого ответа от сервера на свой запрос в течение какого-то времени, он может просто повторить запрос. Если сервер уже отправлял ответ на этот запрос (ровно на этот запрос, а не на такой же — все параметры при повторе должны принимать то же значение), но он не дошел до клиента, сервер просто повторит тот же ответ. Сервер помнит ответ до 10 минут после момента получения запроса 1). Если же сервер уже забыл ответ или необходимые временные данные, клиенту придется начать все с самого начала.

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

Пример использования

Пример полного списка запросов, необходимый для генерации ключа авторизации, показан на отдельной странице: «создание ключа авторизации — примеры».