PyDERASN: как я добавил big-data поддержку19.04.2020 23:48

Продолжаю прошлую статью о PyDERASN — свободном ASN.1 DER/CER/BER кодеке на Python. За прошедший год, с момента её написания, кроме всяких мелочей, небольших исправлений, ещё более строгой проверки данных (хотя и прежде он был уже самым строгим из известных мне свободных кодеков), в этой библиотеке появился функционал для работы с большими объёмами данных — не влезающих в оперативную память. Об этом и хочу рассказать в данной статье.

ASN.1 browser

Проблемы/задачи

  • Огромный CRL:
    Представим, что мы большой удостоверяющий центр (CA) и у нас десятки или сотни миллионов выпущенных X.509 сертификатов. И ещё больше отозванных, хранящихся в списке CRL (certificate revocation list). CRL файл CACert.org, занимающий 8.72 MiB, при декодировании PyDERASN-ом под Python 3.6 занимает в памяти более полугигабайта (под другими библиотеками типа asn1crypto и pyasn1 и того больше). А там ведь чуть больше 416 тыс. отозванных сертификатов. Нужна очень неплохая машина, чтобы хранить в памяти структуру на десятки или сотни миллионов сертификатов. Удручающий факт.
  • Огромный CMS:
    CMS (Cryptographic Message Syntax) это популярный стандарт для
    зашифрованных/подписанных/аутентифицированных документов. Например,
    SignedData структура внутри хранит подписанные данные, а в ней,
    как в матрёшке, может находится какой-нибудь EnvelopedData с
    зашифрованным содержимым.

    У заказчиков может возникнуть желание делать резервные копии баз данных и сразу их помещать в такой вот CMS. Да, CMS позволяет делать detached data, когда настоящие данные находятся где-то отдельно, но это не всегда удобно и всеми поддерживается. Для 10 GiB копии БД нужно 20 GiB памяти как минимум: для создания самой структуры с этим 10 GiB содержимым и для её закодированной формы. Прискорбно.

Тривиальные хаки

Какие ASN.1 объекты на практике могут быть ресурсоёмки, занимать много места в памяти? Только SEQUENCE OF/SET OF, содержащие многочисленные объекты (сотни тысяч в случае с CACert.org), и все виды *STRING-ов (как во втором проблематичном случае). Так как одной из добродетелей программиста является лень (по Ларри Уоллу), то будем стараться побороть проблемы ресурсоёмкости минимальным изменением в коде библиотеки.

*STRING объекты, с точки зрения кодека, почти не отличаются друг от друга и в библиотеке реализуются одним общим классом. Что из себя представляет кодирование в OCTET STRING в DER? 

return tag + len_encode(len(value)) + value

Очевидно, что value не обязан всё это время находится в оперативной памяти. От него требуется быть bytes-like объектом у которого можно узнать длину. memoryview удовлетворяет этим условиям. А ещё memoryview можно сделать от mmap на какой-нибудь временный файл, что уже сокращает потребности в 20 GiB памяти для 10 GiB CMS копии БД в два раза: достаточно указать в качестве значения OCTET STRING-а (или любых других *STRING-ов) подобный memoryview. Для его создания в PyDERASN есть вспомогательная функция: 

from pyderasn import file_mmaped
with open("dump.sql.zst", "rb") as fd:
    ... = OctetString(file_mmaped(fd))

Если мы хотим декодировать огромный объём данных, то memoryview можно использовать и для decode: 

from pyderasn import file_mmaped
with open("dump.sql.zst", "rb") as fd:
    obj = Schema.decode(file_mmaped(fd))

Проблему с *STRING считаем частично решённой. Возвращаемся к созданию огромного CRL. Что из себя представляет его структура? 

CertificateList SEQUENCE
. tbsCertList: TBSCertList SEQUENCE
. . version: Version INTEGER v2 (01) OPTIONAL
. . signature: AlgorithmIdentifier SEQUENCE
. . issuer: Name CHOICE rdnSequence
. . thisUpdate: Time CHOICE utcTime
. . nextUpdate: Time CHOICE utcTime OPTIONAL
. . revokedCertificates: RevokedCertificates SEQUENCE OF OPTIONAL
. . . 0: RevokedCertificate SEQUENCE
. . . . userCertificate: CertificateSerialNumber INTEGER 17 (11)
. . . . revocationDate: Time CHOICE utcTime UTCTime 2003-04-01T14:25:08
. . . 1: RevokedCertificate SEQUENCE
. . . . userCertificate: CertificateSerialNumber INTEGER 20 (14)
. . . . revocationDate: Time CHOICE utcTime UTCTime 2002-10-01T02:18:01

                                 [...]

. . . 415753: RevokedCertificate SEQUENCE
. . . . userCertificate: CertificateSerialNumber INTEGER 1341859 (14:79:A3)
. . . . revocationDate: Time CHOICE utcTime UTCTime 2020-02-08T06:51:56
. . . 415754: RevokedCertificate SEQUENCE
. . . . userCertificate: CertificateSerialNumber INTEGER 1341860 (14:79:A4)
. . . . revocationDate: Time CHOICE utcTime UTCTime 2020-02-08T06:53:01
. . . 415755: RevokedCertificate SEQUENCE
. . . . userCertificate: CertificateSerialNumber INTEGER 1341861 (14:79:A5)
. . . . revocationDate: Time CHOICE utcTime UTCTime 2020-02-08T07:25:06
. signatureAlgorithm: AlgorithmIdentifier SEQUENCE
. signatureValue: BIT STRING 4096 bits

Длинный список из небольших RevokedCertificate структур. В данном случае, содержащих всего-лишь серийный номер сертификата и время его отзыва. Что из себя представляет его DER кодирование? 

value = b"".join(revCert.encode() for revCert in revCerts)
return tag + len_encode(len(value)) + value

Просто конкатенация DER представлений каждого отдельного элемента этого списка. Нужно ли нам иметь заранее в памяти все эти сотни тысяч объектов, по ходу просто сериализующихся в 15 байт DER представления? Очевидно, что нет. Поэтому заменяем список объектов на итератор/генератор. Скорее всего, создание CRL будет происходить на основе данных из СУБД: 

def revCertsGenerator(...):
    for row in db.cursor:
        yield RevokedCertificate((
            ("userCertificate", CertificateSerialNumber(row.serial)),
            ("revocationDate", Time(("utcTime", UTCTime(row.revdate)))),
        ))

crl["tbsCertList"]["revokedCertificates"] = revCertsGenerator()

Теперь мы почти не потребляем памяти при создании такого CRL — нужно место только для работы с его DER представлением: в данном случае, речь о паре десятков мегабайт (в противовес полугигабайтному списку RevokedCertificate объектов). Но появляется отличие в поведении: проверка на размеры SEQUENCE OF/SET OF происходит только после исчерпания итератора, а не в момент присваивания значения.

Потоковое кодирование DER

Оно невозможно. Ведь это же DER — длины всех TLV (tag + length + value) элементов должны быть известны заранее!

Но этого бы так хотелось! Ведь нам всё равно ещё нужно 10 GiB памяти для хранения DER представления копии БД: raw = cms.encode ()! В идеале, хочется передать некий writer, куда бы записывалось сериализованное представление. Может быть, передавать файловый дескриптор, оставлять placeholder-ы в файле на месте длин и потом их заполнить, выполняя seek? К сожалению, длина длины (соответственно и placeholder) тоже заранее не известна.

PyDERASN получил возможность двухпроходного DER кодирования. В первом проходе собирается знание о длинах объектов, создавая временное состояние. Во втором происходит потоковое кодирование DER в некий writer, уже возможное из-за наличия знания о длинах. Реализация этого вышла простой, лишь немного добавляя двухпроходных методов к каждому из ASN.1 базовых типов. Так как обход объектов является строго детерминированным (D — distinguished!), то, для хранения необходимых длин, ведётся простой список, к которому, по мере прохождения всего дерева объектов, добавляются значения длин. У некоторых типов длина фиксирована. У некоторых она нужна только для сообщения вышестоящему контейнеру (SEQUENCE/SET, SEQUENCE OF/SET OF, EXPLICIT TAG). Например, состояние длин для списка из двух отозванных сертификатов выглядит так: 

revCert = RevokedCertificate((
    ("userCertificate", CertificateSerialNumber(123)),
    ("revocationDate", Time(("utcTime", UTCTime(datetime.utcnow())))),
))
revs = RevokedCertificates([revCert, revCert])

(42, [40, 18, 18])

В данном случае, нам нужно знать длину значения только для каждого из RevokedCertificate и всего списка в целом. Длина целых чисел и закодированного времени (в DER оно фиксированной длины) в состоянии не хранится за ненадобностью. В итоге, для нашего CACert.org CRL подобный список занимает чуть более 3.5 MiB, а для гигантского CMS, в котором почти весь вес приходится на одно единственное поле с копией БД, он занимает около 0.5 KiB.

Двухпроходное кодирование выполняется двумя вызовами: 

fulllen, state = obj.encode1st()
with open("result", "wb") as fd:
    obj.encode2nd(fd.write, iter(state))

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

Используя вспомогательную функцию encode2pass (obj) можно выполнить двухпроходное кодирование в память. Зачем? Оно может быть значительно более экономно по потреблению памяти, так как в нём не будет, в случае с CACert.org CRL, хранится 416k+ небольших бинарных строчек, объединяемых b».join () вызовом. Однако, это требует больше процессорного времени, ведь по всем объектам придётся пройтись два раза.

Теперь мы можем закодировать сколь угодно большой CMS в DER, практически не потребляя памяти. Но в случае с CRL мы использовали генератор отозванных сертификатов, который иссякнет после окончания первого прохода. Что делать? Просто переинициализировать его снова! 

_, state = crl.encode1st()
crl["tbsCertList"]["revokedCertificates"] = revCertsGenerator()
crl.encode2nd(writer, iter(state))

Безусловно, мы обязаны следить за тем, что результат работы итератора будет точь-в-точь одинаков, иначе мы получим битый DER. Если данные берутся из курсора СУБД, то не забывать про REPEATABLE READ уровень изоляции транзакций и сортировку.

Настоящее потоковое кодирование: CER

Как известно, DER (distinguished encoding rules) это подмножество BER (basic encoding rules), жёстко регламентирующее правила кодирования одним и только одним способом. Это позволяет его применять в криптографических задачах. Но существует ещё одно достойное внимания подмножество BER: CER (canonical encoding rules). Как и DER, оно имеет только одно возможное представление данных. CER отличается от DER несколькими мелочами, но они позволяют выполнять действительно потоковое кодирование данных. К сожалению, CER не стал так популярен как DER.

Опуская не столь бросающиеся отличия (типа сортировки тэгов в SET), CER имеет два основополагающих отличия от DER:

  • Длина всех составных типов (constructed, не примитивных) кодируется indefinite методом (LENINDEF в терминах PyDERASN). То есть, для SEQUENCE/SET, SEQUENCE OF/SET OF, EXPLICIT TAG-ов вместо кодирования: 
    TAG_CONSTRUCTED || LEN(VALUE) || VALUE

    указывается LENINDEF (0×80) и EOC (нулевой тэг, нулевой длины) как признак окончания: 

    TAG_CONSTRUCTED || 80 || VALUE || 00 00

  • *STRING-и, длина которых больше 1000-байт, кодируются chunk-ами по 1000-байт. Те, у кого длина меньше или равна, кодируются аналогично DER. Так, 512 байт строка будет закодирована так же как и в DER: 
    TAG_PRIMITIVE || LEN(512) || 512B

    а 2048 байт строка: 
    TAG_CONSTRUCTED || 80 ||
    TAG_PRIMITIVE || LEN(1000) || 1000B ||
    TAG_PRIMITIVE || LEN(1000) || 1000B ||
    TAG_PRIMITIVE || LEN(48) || 48B || 00 00

Всё это (плюс несколько мелочей) позволяет потоково (с 1000 байт буфером для строк) кодировать любые объекты. Точно так же можно использовать mmap и итераторы. Кодирование в CER делается просто вызовом .encode_cer (writer) метода. К сожалению, PyDERASN пока не умеет проверять валидность CER при декодировании, так что мы вынуждены декодировать данные как BER.

Стандарт CMS, между прочим, требует кодирования в BER (и DER, и CER, автоматом, являются BER). Поэтому нашу огромную копию БД мы можем закодировать в CER CMS без двухпроходного DER. Однако, SignedData обязан иметь SignedAttributes элемент закодированным в DER, как и X.509 Certificate сертификаты. PyDERASN позволяет форсировать использование DER в заданных структурах, просто добавляя der_forced = True атрибут.

Потоковое декодирование: evgen-режим

Кодировать то мы научились, а вот при декодировании поможет только mmap. «Настоящий» потоковый декодер, у которого есть ручки управления в виде «дай мне ещё данных», «вот тебе», некое состояние — потребовал бы кардинальной переделки PyDERASN-а. Да и, лично я, не вижу был бы он удобнее текущего решения.

А текущее решение предельно простое. В процессе декодирования, у нас на руках в памяти появляются различные декодированные примитивные объекты, из них собираются вышестоящие составные (constructed), из которых другие составные, и т.д… Мы копим объекты, чтобы из них сделать составные и, дойдя до самого верха, выдать нам один большой объект. Почему бы не сразу же «выдавать» все виды декодированных объектов, как только они у нас появляются на руках? То есть, возвращать не конечный объект, а генератор, порождающий множество декодированных объектов. На самом деле, в PyDERASN теперь все методы декодирования стали генераторами таких «событий» (event generation, evgen).

Если мы включим evgen-режим декодирования нашего огромного CACert.org CRL, то увидим следующую картину: 

$ python -m pyderasn --schema tests.test_crl:CertificateList --evgen revoke.crl
[смещение][T,L,  V len]
     10   [1,1,      1]   . . version: Version INTEGER v2 (01) OPTIONAL
     15   [1,1,      9]   . . . algorithm: OBJECT IDENTIFIER 1.2.840.113549.1.1.13
     26   [0,0,      2]   . . . parameters: [UNIV 5] ANY OPTIONAL
     13   [1,1,     13]   . . signature: AlgorithmIdentifier SEQUENCE
     34   [1,1,      3]   . . . . . . type: AttributeType OBJECT IDENTIFIER 2.5.4.10
     39   [0,0,      9]   . . . . . . value: [UNIV 19] AttributeValue ANY
     32   [1,1,     14]   . . . . . 0: AttributeTypeAndValue SEQUENCE
     30   [1,1,     16]   . . . . 0: RelativeDistinguishedName SET OF

                                 [...]

    188   [1,1,      1]   . . . . userCertificate: CertificateSerialNumber INTEGER 17 (11)
    191   [1,1,     13]   . . . . . utcTime: UTCTime UTCTime 2003-04-01T14:25:08
    191   [0,0,     15]   . . . . revocationDate: Time CHOICE utcTime
    191   [1,1,     13]   . . . . . utcTime: UTCTime UTCTime 2003-04-01T14:25:08
    186   [1,1,     18]   . . . 0: RevokedCertificate SEQUENCE
    208   [1,1,      1]   . . . . userCertificate: CertificateSerialNumber INTEGER 20 (14)
    211   [1,1,     13]   . . . . . utcTime: UTCTime UTCTime 2002-10-01T02:18:01
    211   [0,0,     15]   . . . . revocationDate: Time CHOICE utcTime
    206   [1,1,     18]   . . . 1: RevokedCertificate SEQUENCE

                                 [...]

9144992   [0,0,     15]   . . . . revocationDate: Time CHOICE utcTime
9144985   [1,1,     20]   . . . 415755: RevokedCertificate SEQUENCE
    181   [1,4,9144821]   . . revokedCertificates: RevokedCertificates SEQUENCE OF OPTIONAL
      5   [1,4,9144997]   . tbsCertList: TBSCertList SEQUENCE
9145009   [1,1,      9]   . . algorithm: OBJECT IDENTIFIER 1.2.840.113549.1.1.13
9145020   [0,0,      2]   . . parameters: [UNIV 5] ANY OPTIONAL
9145007   [1,1,     13]   . signatureAlgorithm: AlgorithmIdentifier SEQUENCE
9145022   [1,3,    513]   . signatureValue: BIT STRING 4096 bits
      0   [1,4,9145534]  CertificateList SEQUENCE
  • При начале декодирования, увидели CertificateList SEQUENCE тэг, длину данных, но объект ещё не известно сможет ли быть задекодирован до конца. Пока мы только в процессе работы над ним.
  • Декодируем первый элемент этого SEQUENCE: поле version, состоящее из одного единственного INTEGER. Декодировали это число. Это законченный объект, поэтому создаём событие о его декодировании. (смещение 10)
  • Далее идёт поле signature, являющееся SEQUENCE-ом из двух полей: algorithm и parameters. Декодирование соответствующих OBJECT IDENTIFIER и ANY полей сразу же порождает события. (смещения 15, 26)
  • Лишь после их декодирования, мы видим, что в signature SEQUENCE не осталось лишних данных, нет больше обязательных полей, поэтому эта структура завершена: создаётся событие. (смещение 13)
  • Видим, что каждое RevokedCertificate событие создаётся только после декодирования полей внутри него. (смещения 186, 206, и т.д.)
  • Огромный tbsCertList мы встречаем почти в самом конце вывода. (смещение 5)
  • CertificateList, самый верхний SEQUENCE, идёт последним, так как только в самом конце мы понимаем, что всё хорошо со структурой и данных больше нет. (смещение 0)

Само собой, все *STRING и списки (*OF) не несут в себе реального значения. В случае с DER, зная .offset и .vlen можно из файла (участка памяти?) прочитать значение строки. Объекты последовательностей можно собирать и агрегировать как вам надо, во время приёма всех событий.

Декодированный путь и evgen_mode_upto

Как же понимать что за объект, что за INTEGER у нас на руках? У каждого объекта есть свой, так называемый, decode path, уникально идентифицирующий конкретный объект в структуре. Например, для CACert.org CRL decode path событий: 

tbsCertList:version
tbsCertList:signature:algorithm
tbsCertList:signature:parameters
tbsCertList:signature
tbsCertList:issuer:rdnSequence:0:0:type
                                 [...]
tbsCertList:issuer:rdnSequence
tbsCertList:issuer
                                 [...]
tbsCertList:revokedCertificates:0:userCertificate
tbsCertList:revokedCertificates:0:revocationDate:utcTime
tbsCertList:revokedCertificates:0:revocationDate
tbsCertList:revokedCertificates:0
tbsCertList:revokedCertificates:1:userCertificate
tbsCertList:revokedCertificates:1:revocationDate:utcTime
tbsCertList:revokedCertificates:1:revocationDate
tbsCertList:revokedCertificates:1
                                 [...]
tbsCertList:revokedCertificates:415755:userCertificate
tbsCertList:revokedCertificates:415755:revocationDate:utcTime
tbsCertList:revokedCertificates:415755:revocationDate
tbsCertList:revokedCertificates:415755
tbsCertList:revokedCertificates
tbsCertList
signatureAlgorithm:algorithm
signatureAlgorithm:parameters
signatureAlgorithm
signatureValue

Вот так мы можем распечатать список серийных номеров отозванных сертификатов из этого CRL: 

raw = file_mmaped(open("....crl", "rb"))
for decode_path, obj, tail in CertificateList().decode_evgen(raw):
    if (len(decode_path) == 5) and (decode_path[-1] == "userCertificate"):
        print(int(obj))

Структура RevokedCertificate может содержать много информации, в том числе различные расширения. Чисто технически мы получаем все данные об отозванном сертификате в evgen-режиме, но агрегировать события относящиеся к одному элементу revokedCertificates не очень удобно. Так как каждый конечный RevokedCertificate, на практике, не будет занимать много места, то было бы здорово всё же не все объекты настолько досконально «разбирать» на события. PyDERASN позволяет списком задать пути декодирования, при которых evgen-режим отключается. Так мы можем задать decode path (любой элемент из («tbsCertList», «revokedCertificates») списка) на котором мы хотим получать полный RevokedCertificate объект: 

for decode_path, obj, _ in CertificateList().decode_evgen(raw, ctx={
    "evgen_mode_upto": (
        (("tbsCertList", "revokedCertificates", any), True),
    ),
}):
    if (len(decode_path) == 3) and (decode_path[1] == "revokedCertificates"):
        print(int(obj["userCertificate"]))

Агрегируем строки: agg_octet_string

Теперь проблем с декодированием объектов любого размера у нас нет. Декодировать DER-закодированный CMS с копией БД проблем тоже нет: ждём событие с decode path-ом указывающим на подписанные/шифрованные данные в CMS и по offset+vlen обрабатываем данные из файла. Но что если CMS был в CER формате? Тогда offset+vlen не помогут, так как все наши 10 GiB разбиты на кусочки по 1000 байт, между которыми по DER-заголовку. А что если у нас BER, в котором вложенность *STRING-ов может быть какова угодно? 

SOME STRING[CONSTRUCTED]
    OCTET STRING[CONSTRUCTED]
        OCTET STRING[PRIMITIVE]
            DATA CHUNK
        OCTET STRING[PRIMITIVE]
            DATA CHUNK
        OCTET STRING[PRIMITIVE]
            DATA CHUNK
    OCTET STRING[PRIMITIVE]
        DATA CHUNK
    OCTET STRING[CONSTRUCTED]
        OCTET STRING[PRIMITIVE]
            DATA CHUNK
        OCTET STRING[PRIMITIVE]
            DATA CHUNK
    OCTET STRING[CONSTRUCTED]
        OCTET STRING[CONSTRUCTED]
            OCTET STRING[PRIMITIVE]
                DATA CHUNK

При декодировании в evgen-режиме, для каждого кусочка мы получим соответствующее событие и нам достаточно собирать лишь примитивные (не constructed) *STRING события, где offset+vlen содержат настоящие кусочки данных. В PyDERASN имеется удобная вспомогательная agg_octet_string функция это выполняющая. Ей достаточно передать генератор событий, decode path «ниже» которого необходимо агрегировать строку, бинарные данные (или memoryview) и writer — функцию, вызываемую с каждым полученным кусочком данных. Хотим посчитать SHA512 хэш и одновременно сохранять содержимое encapContentInfo.eContent CMS-ки? Найдём местоположение content поля (в котором будет расположен SignedData), а дальше декодируем его CER содержимое, одновременно записывая на ФС и хэшируя: 

fdIn = open("data.p7m", "rb")
raw = file_mmaped(fdIn)
for decode_path, obj, _ in ContentInfo().decode_evgen(raw, ctx={"bered": True}):
    if decode_path == ("content",):
        content = obj
        break
hasher_state = sha512()
fdOut = open("dump.sql.zst", "wb")
def hash_n_save(data):
    write_full(fdOut, data)
    hasher_state.update(data)
    return len(data)
evgens = SignedData().decode_evgen(
    raw[content.offset:],
    offset=content.offset,
    ctx={"bered": True},
)
agg_octet_string(evgens, ("encapContentInfo", "eContent"), raw, hash_n_save)

Здесь используется ещё одна утилита write_full, вызывающая writer до тех пор, пока все данные не будут записаны, так как, в общем случае, при записи в файл, ОС не обязана обрабатывать все переданные данные и нужно продолжать процесс до полной записи.

Пару ласковых о SET OF

Чисто технически SET OF не может быть закодирован на лету в DER и CER кодировках, так как закодированные представления всех элементов должны быть отсортированы. Тут не поможет ни CER, ни двухпроходный DER. Современный ASN.1 стандарт поэтому не рекомендует применять как SET (требующий аналогичной сортировки в DER), так и SET OF.

А что это за картинка в начале статьи?

Это в PyDERASN появился интерактивный простенький ASN.1 броузер, лично мне несколько раз помогавший писать обработчики для сложных структур. Позволяет гулять по всей декодированной структуре, показывая полную детализацию о каждом объекте, его местоположение в бинарных данных, decode path. Кроме того, любой элемент можно сохранить в отдельном файле, как например сертификаты или CRL прилагаемые в CMS.

Сергей Матвеев, шифропанк, Python/Go-разработчик, главный специалист ФГУП «НТЦ «Атлас».

© Habrahabr.ru