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

31 июл. 2013 г.

MTProto adventure step 1 - asn.1

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

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

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

ASN.1 PER

Первое с чем я столкнулся при посещении официального сайта MTProto - http://dev.stel.com/ это публичный ключ RSA.

Что из себя представляет этот ключ и рассмотрено.


Сам ключ выглядит так:

-----BEGIN RSA PUBLIC KEY-----
MIIBCgKCAQEAwVACPi9w23mF3tBkdZz+zwrzKOaaQdr01vAbU4E1pvkfj4sqDsm6
lyDONS789sVoD/xCS9Y0hkkC3gtL1tSfTlgCMOOul9lcixlEKzwKENj1Yz/s7daS
an9tqw3bfUV/nqgbhGX81v/+7RFAEd+RwFnK7a+XYl9sluzHRyVVaTTveB2GazTw
Efzk2DWgkBluml8OREmvfraX3bkHZJTKX4EQSjBbbdJ2ZXIsRrYOXfaA+xayEGB+
8hdlLmAjbCVfaigxX0CDqWeR1yFL9kwd9P0NsZRPsmoqVwMbMu7mStFai6aIhc3n
Slv8kg9qv1m6XHVQY3PnEw+QQtqSIXklHwIDAQAB
-----END RSA PUBLIC KEY-----

Ключ закодирован в формате asn.1 PER и получить его содержимое, можно командой:

vk_rsa.pub (openssl asn1parse -in public.key )

Однако, я сделаю это руками.

Отбрасываем заголовки с "---" и декодируем данные base64.

base64 decode

После декодирование, получаем следующий набор байт.

00000000  30 82 01 0a 02 82 01 01  00 c1 50 02 3e 2f 70 db  |0.........P.>/p.|
00000010  79 85 de d0 64 75 9c fe  cf 0a f3 28 e6 9a 41 da  |y...du.....(..A.|
00000020  f4 d6 f0 1b 53 81 35 a6  f9 1f 8f 8b 2a 0e c9 ba  |....S.5.....*...|
00000030  97 20 ce 35 2e fc f6 c5  68 0f fc 42 4b d6 34 86  |. .5....h..BK.4.|
00000040  49 02 de 0b 4b d6 d4 9f  4e 58 02 30 e3 ae 97 d9  |I...K...NX.0....|
00000050  5c 8b 19 44 2b 3c 0a 10  d8 f5 63 3f ec ed d6 92  |\..D+<....c?....|
00000060  6a 7f 6d ab 0d db 7d 45  7f 9e a8 1b 84 65 fc d6  |j.m...}E.....e..|
00000070  ff fe ed 11 40 11 df 91  c0 59 ca ed af 97 62 5f  |....@....Y....b_|
00000080  6c 96 ec c7 47 25 55 69  34 ef 78 1d 86 6b 34 f0  |l...G%Ui4.x..k4.|
00000090  11 fc e4 d8 35 a0 90 19  6e 9a 5f 0e 44 49 af 7e  |....5...n._.DI.~|
000000a0  b6 97 dd b9 07 64 94 ca  5f 81 10 4a 30 5b 6d d2  |.....d.._..J0[m.|
000000b0  76 65 72 2c 46 b6 0e 5d  f6 80 fb 16 b2 10 60 7e  |ver,F..]......`~|
000000c0  f2 17 65 2e 60 23 6c 25  5f 6a 28 31 5f 40 83 a9  |..e.`#l%_j(1_@..|
000000d0  67 91 d7 21 4b f6 4c 1d  f4 fd 0d b1 94 4f b2 6a  |g..!K.L......O.j|
000000e0  2a 57 03 1b 32 ee e6 4a  d1 5a 8b a6 88 85 cd e7  |*W..2..J.Z......|
000000f0  4a 5b fc 92 0f 6a bf 59  ba 5c 75 50 63 73 e7 13  |J[...j.Y.\uPcs..|
00000100  0f 90 42 da 92 21 79 25  1f 02 03 01 00 01

asn.1 DER decode

Как следует из соответствующих стандартов, ключ сериализован asn.1 DER по следующей схеме:

RSA public key syntax
( http://tools.ietf.org/html/rfc3447#appendix-A )

      RSAPublicKey ::= SEQUENCE {
          modulus           INTEGER,  -- n
          publicExponent    INTEGER   -- e
      }

Каким образом asn.1 сериализует данные можно посмотреть на википедии, я лишь сделаю разбор. Если коротко, данные о структуре кодируются по схеме. Биты в байте используются для описания содержимого.

      
asn.1 DER decode

    Identifier octets

octet   hex     binary
0000    0x30    00110000
                ^^
                0(bit 8) 0(bit 7) - Class bit "Universal"

0001            00110000
                  ^
                1(bit 6) Content is "Constructed"

                00110000
                   ^^^^^
                16 (bit 5 .. bit 1) Universal Class Tag SEQUENCE and SEQUENCE OF

    Length

0002    0x82    10000010
                ^
                1(bit 8) Long form

                10000010
                 ^^^^^^^
                2(bit 1 .. bit 7) - length octets of Contents lengths

0002    0x01    00000001 
0003    0x0a    00001010

                266 Length of Contents octets

    Content octets

        Identifier octets

0004    0x02    10000010
                ^^
                Class bits "Context-specific"

                10000010
                  ^
                Content is "Primitive"

                10000010
                   ^^^^^
                02 Universal Class Tag "INTEGER"

        Length

0005    0x82    10000010
                ^
                1(bit 8) Long form

                10000010
                 ^^^^^^^
                2(bit 1 .. bit 7) - length octets of Contents lengths

0006    0x01    00000001
0007    0x01    00000001

                257(0x101) Length of Contents octets

        Content octets (modulus data)

0008    0x00    00000000
0009    0xc1    11000001
000a    0x50    01010000
........................
0107    0x25
0108    0x1f
        
        Identifier octets

0109    0x02    10000010
                ^^
                Class bits "Context-specific"

                10000010
                  ^
                Content is "Primitive"

                10000010
                   ^^^^^
                02 Universal Class Tag "INTEGER"

        Length

010a    0x03    00000011
                ^
                Short form

                00000011
                 ^^^^^^^
                3 - Length of Content octets

        Content octets (publicExponent data)

010b    0x01    00000001
010c    0x00    00000000
010d    0x01    00000001

Modulus и Exponent

В конечном счёте мы получили два числа.

Modulus:        0xC150023E2F70DB7985DED064759CFECF0AF328E69A41DAF4D6F01B538135
                  A6F91F8F8B2A0EC9BA9720CE352EFCF6C5680FFC424BD634864902DE0B4B
                  D6D49F4E580230E3AE97D95C8B19442B3C0A10D8F5633FECEDD6926A7F6D
                  AB0DDB7D457F9EA81B8465FCD6FFFEED114011DF91C059CAEDAF97625F6C
                  96ECC74725556934EF781D866B34F011FCE4D835A090196E9A5F0E4449AF
                  7EB697DDB9076494CA5F81104A305B6DD27665722C46B60E5DF680FB16B2
                  10607EF217652E60236C255F6A28315F4083A96791D7214BF64C1DF4FD0D
                  B1944FB26A2A57031B32EEE64AD15A8BA68885CDE74A5BFC920F6ABF59BA
                  5C75506373E7130F9042DA922179251F

publicExponent: 0x010001