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

11 апр. 2012 г.

Косяки MongoDB


Перечислю косяки MongoDB, которые попадаются при работе с ней. Список пополняется.

  • При локе базы, любая работа с монго подвешивает mongo shell (Bug: SERVER-4243)
  • Index entries have a limitation on their maximum size (the sum of the values), currently approximately 800 bytes. (Bug: SERVER-3372)
  • The maximum size of a collection name is 128 characters (including the name of the db and indexes). It is probably best to keep it under 80/90 chars.[link]
  • MongoDB limits the data size of individual BSON objects/documents. At the time of this writing the limit is 16MB.[link]
  • A Year with MongoDB :
  • Non-counting B-Trees 
  • Poor Memory Management 
  • Uncompressed field names 
  • Global write lock 
  • Safe off by default 
  • Offline table compaction 
  • Secondaries do not keep hot data in RAM


    22 июн. 2010 г.

    Быстрый доступ к памяти во Flash используя особенности Alchemy.

    В конце 2008 с выходом Alchemy toolkit от Adobe, Nicolas Cannasse рассказал в своём блоге о Virtual Memory API который он добавил в haXe. Его дополнение к API основывалось на дополнительных возможностях Flash Player 10+ по работе с памятью.

    Flash Player имеет ряд Fast memory op codes(pdf с презентацией) которые используются только компилятором Alchemy, другие компиляторы от Adobe этого не делают. Nicolas сделал возможным использовать эту особенность в своём компиляторе haXe, что позволило иметь очень быстрый доступ к памяти.

    Стоит отметить, что AS3 API имеет доступ к этой быстрой памяти через Application.domainMemory:ByteArray, но используя это API никакого прироста скорости не получается, реализация этого API подкачала.

    Так же, Nicolas сделал возможным используя haXe создавать библиотеки .swc которые можно подключать к обычным Flash/Flex проектам.

    Michael Baczynski используя эти возможности haXe, создал библиотеку Data Structures (de.polygonal.ds.*) по работе с быстрой памятью.

    Более подробнее о библиотеке и тестах скорости работы с ней можно посмотреть у Michael-a в его заметке MemoryManager revisited.

    BlooDHounD тоже использовал эти особенности haXe и создал замену части функционала as3corelib, в своей библиотеке о которой можно почитать в заметке "Тяжёлые алгоритмы на стероидах (MD5, Base64, CRC32, JPEG, PNG)"

    2 июн. 2010 г.

    Анализ аудитории ВКонтакте (01.06.10) #3

    Небольшой анализ аудитории #3.

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

    http://www.you-ra.info/vkstats/

    p.s. если интересны другие графики, которые можно построить по данным uid/sex/timezone/has_mobile/rate , то спрашивайте, построю.

    p.s.s. рассмотрено 85.281.877 анкет

    29 мар. 2010 г.

    Selectel сервер - наблюдение за железом(полезные советы).

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

    Речь пойдёт о Селектеловском выделенном сервере:
    Intel Core 2 Duo E8400 3.0 GHz / 6Gb DDRIII / 2 x 500Gb SATA

    Подобное будет работать и для остальных, с небольшими изменениями.

    1. Установка ОС и внешняя консоль(IP-KVM)

    Если по каким либо причинам, вы решили поставить ОС сами, это возможно удалённо.

    У серверов есть IP-KVM доступный по ссылке:
    https://support.selectel.ru/servers/console.php

    IP-KVM представляет собой java приложение, которое отображает то, что вы увидели бы, подключив монитор/клавиатуру/мышь к серверу непосредственно.

    т.е. если у вас "поломалась" ОС, это отличный способ узнать, что вообще произошло и попытаться починить.

    Помимо прочего, вы можете подключить удалённо любой .iso образ и поставить ОС сами.(в самой ОС этот .iso образ будет доступен как cdrom и usb device)

    Удалённо имеется ввиду с вашего компьютера, по-этому если есть желание поставить ОС, то рекомендую использовать разные netinstall iso образы, не превышающие 200мб.

    Что бы выбрать устройство для загрузки образа(cdrom а не винчестер), при загрузке сервера нажмите F11 и выберите нужную опцию(предварительно нужно "вставить" .iso образ в виртуальный cdrom нажав на иконку дискетки в углу приложения).

    Так же можно с образа протестировать память(RAM), например при помощи http://www.memtest86.com/ .

    2. Мониторинг состояния винчестера.

    Для мониторинга состояния винчестера используется S.M.A.R.T.

    Под Linux/Debian:
    smartctl - для ручного мониторинга.
    smartd - для автоматического(настраиваемого в /etc/smartd.conf)

    В моём случае smartd настроен примерно на следующее:
    /dev/sda -a -d sat -o on -S on -s (S/../.././04|L/../../6/05) -m root -M exec /usr/share/smartmontools/smartd-runner

    (тоже самое и для /dev/sdb)

    т.е. демон каждый день в 4 утра запускает быстрый тест работы винчестера и раз в неделю в 5 утра - длинный.

    Если результат плохой, то письмо придёт к пользователю root.
    (учитывая /etc/aliases, то к пользователю user)

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

    3. Мониторинг сенсоров(под Linux/Debian).

    Как оказалось, материнская плата на этом сервере X7SBT.
    http://www.supermicro.com/products/motherboard/Xeon3000/X48/X7SBT.cfm

    Популярный пакет lm-sensors в моём случае не заработал. Почитав сайт разработчиков, увидел, что для работы Winbond 83627DHG chip, который находится на этой motherboard, необходимо перебирать kernel с несколькими заплатками,
    чего мне не хотелось делать.

    Однако, на сайте supermicro(выше ссылка), предлагалась утилита Supero Doctor II под Linux.

    Скачивается она с их ftp:
    ftp://ftp.supermicro.com/utility/Supero_Doctor_II/Linux/Release/

    Устанавливается при помощи ./quickinstall (запуск в директории распакованного архива).

    После установки работает утилита sdt, которая отображает:

    Fan1 Fan Speed
    Fan2 Fan Speed
    Fan3 Fan Speed
    CPU Core Voltage
    DIMM Voltage
    +12V Voltage
    +3.3V Voltage
    +5V Voltage
    System Temperature
    CPU Temperature
    Chassis Intrusion
    Power Supply Failure

    или передавая данные используя SNMP при помощи sd_extension .

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

    Прежде чем задавать вопросы или ругаться:
    a)Не имею отношения к компании Selectel
    б)Не отвечаю за любые неприятности, которые вы можете получить после использования советов.
    в)Могу помочь в настройке сервера, консультациях по настройке, тестированию, администрированию и т.п., но только на взаимовыгодных условиях.

    4 мар. 2010 г.

    Анализ аудитории ВКонтакте (01.03.10) #2

    Небольшой анализ аудитории #2.

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

    http://www.you-ra.info/vkstats/

    p.s. если интересны другие графики, которые можно построить по данным uid/sex/timezone/has_mobile/rate , то спрашивайте, построю.

    p.s.s. рассмотрено 72.352.719 анкет