7 авг. 2013 г.

MTProto adventure step 2 - SHA-1 / RSA / Diffie Hellman Merkle / AES / IGE

Недавно ВКонтакте открыли свой новый протокол MTProto. Мне стало интересно изучить его особенности и реализовать работу с протоколом на Erlang/OTP.

Попутно я вникал в разные технологии о которых давно слышал, но не находил времени для ознакомления.

Постепенно буду выкладывать информацию, тем или иным образом связанную с MTProto, которая мне показалась интересной в процессе освоения нового протокола.

SHA-1

SHA-1 метод получения уникального отпечатка данных.
Сколько бы данных не загнали, на выходе получим 20 байтовый, уникальный
отпечаток. Подробнее с примерами можно почитать в описании SHA-1 на сайте
американского ГОСТ
http://www.itl.nist.gov/fipspubs/fip180-1.htm

RSA

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

Алгоритм следующий:
1.  Возьмём два простых числа p и q. Перемножим их и получим публичный ключ:
n=p*q
2.  Возьмём публичную экспоненту e, общепринято, что ей является e=65537
2.1 Число n и e известны всем.
3.  Найдём частную экспоненту d, такую, что d*e = 1 mod (p-1)*(q-1)
3.1 После чего, числа p и q нужно уничтожить, а d хранить в тайне.
4.  К удивлению обнаружим, что m^(e*d) = m mod n

Для шифрования в "c" сообщения "m", используем публичный ключ e: c=m^e mod n
Для расшифровки "с" обратно в "m", используем частный ключ d: m=c^d mod n

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

AES / IGE

 
Сама идея метода простая, шифрование данных по ключу(и векторам),
с последующей расшифровкой по тому же ключу.
Сам алгорим для меня тёмный ящик, могу лишь добавить, что в MTProto 
используется вместе с Infinite Garble Extension(IGE) режимом блочного шифра, 
основная особенность которого в том, что при сломанном зашифрованном сообщении
в какой-либо точке, после неё данные расшифровать будет невозможно.
Подробнее можно почитать в описании IGE:
http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ige/ige-spec.pdf
и в описании AES:
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf

Стоит отметить, что функция шифрования aes256 ige есть в OpenSSL, но обёртки
или реализации на языках отличных от c/c++ практически не встречаются.
В свою очередь, я добавлял необходимые функции в  crypto библиотеку, 
в Erlang/OTP, которая использует функцию aes_ige_encrypt из OpenSSL.

Diffie–Hellman–Merkle key exchange

Цель - получить такое число, которое будет известно только двум участникам,
даже если все сообщения будут перехватывать.

В общем виде схема выглядит так:
1. Сервер и Клиент загадывают(говорят открыто) общие числа p=23 and base g=5
2. Сервер выбирает своё секретное число a=6, 
и отправляет Клиенту g^a mod p = 8
3. Клиент выбирает число b=15, и отправляет Серверу B = g^b mod p = 19
4. Сервер вычисляет s = B^a mod p = 2
5. Клиент вычисляет s = A^b mod p = 2
6. Сервер и Клиент получили общее секретное число: s=2

(g^a)^b и (g^b)^a равны и соответственно равен остаток от деления на p

В случае получения секрета в MTProto, переменные меняют названия:
p = dh_prime
g = G


Сам процесс получения секрета в MTProto такой как ниже(опущена часть
шифрования и получения хэшей)

1. Client -> Server 
отправляем случайное число N(требуется для временной сессии)

2. Server -> Client 
присылает наше N, свое число S, число PQ и отпечаток публичного ключа RSA(FRSA)

2.1 проверяем по отпечатку, что ключ RSA у нас такой есть
2.2 раскладываем PQ на простые сомножители P < Q(защита от флуда, ведь чем
больше PQ, тем дольше будет поиск простых сомножителей)
2.3 придумываем ещё одно уникальное число NN

3. Client -> Server
отправляем N,S,P,Q,PQ,FRSA,NN

4. Server -> Client
получаем N,S,G,DH_prime,G_A,Server_time

4.1 выдумываем своё число B
4.2 считаетм (G^B) mod Dh_prime = G_B

5. Client -> Server
отправляем N,SN,G_B

6. Server -> Client
получаем ОК 
значит теперь у нас есть общий секрет:
(G_B^A) mod Dh_prime = secret
(G_A^B) mod Dh_prime = secret

Этот секрет у MTProto называется auth_key