Долговременное хранение ЭД - что такое дерево хешей?

Вадим Малых
30.10.2013
При обсуждении вопросов долговременной сохранности электронных документов, иногда можно слышать упоминания некоего загадочного дерева хешей. Однако что это и с чем его едят как его можно использовать для сохранности ЭД обычно остается за пределами обсуждения. Ниже приведена краткая информация о сути этой технологии и ее возможных применениях к вопросу хранения ЭД.

Итак что такое дерево хешей, и при чем тут долговременное хранение ЭД? Концепция была запатентована Ральфом Мерклом еще в 1979 году, а само дерево получило название дерево Меркла (Merkle tree). Базовая идея достаточно проста - это обычное дерево (структура данных) в узлах которого находятся хеши, полученные по данным всех дочерних узлов (обычно используются бинарные деревья - то есть у каждого узла есть два дочерних, но это необязательное требование и теоретически их может быть сколько угодно). В конечных узлах (листьях) дерева находятся хеши файлов или частей файлов (блоков данных). Хорошая картинка есть здесь.

Дерево хешей по блокам данных одного файла удобно использовать для контроля его целостности при передаче по частям, например в системах P2P, вроде торрентов. Для таких вещей наиболее распространена инкарнация дерева хешей, известная как TTH (Tiger tree hash), представляющая собой бинарное дерево хешей, в котором в качестве хеш-функции использован алгоритм Tiger. В нашем контексте долговременного хранения ЭД данное применение дерева хешей не особо интересно.

Для обеспечения же долговременного доверия к подлинности документа может быть использована схема цифровой подписи Меркла (Merkle signature scheme), основанная на том же принципе дерева хешей. Схема базируется на алгоритмах "одноразовых подписей", например Lamport signature. Использование дерева Меркла всего лишь добавляет возможность подписания одним ключом не одного, а некоторого ограниченного количества документов. Одноразовые алгоритмы позволяют получать устойчивые к взлому подписи даже в случае неимоверного увеличения вычислительной мощности компьютеров (например возможного изобретения квантового компьютера в будущем). А значит сертификат такого ключа можно было бы выпускать на гораздо большее время, чем нынешний 1 год для наших "обычных" усиленных подписей, то есть теоретически сертификат подписи может действовать на протяжении всего необходимого срока хранения документа. Или таким "долгоиграющим" ключом можно подписывать штампы времени для усовершенствованной подписи документа (CAdES-Т).

Существует еще одна техника, имеющая отношение как к дереву хешей, так и к долговременному хранению документов. Речь идет о Linked time-stamping. Если очень коротко, то это способ генерации штампов времени (time-stamp), при котором они криптографически связаны друг с другом при помощи дерева хешей (или другой структуры с подобными свойствами). Корневой хеш публикуется в каком-нибудь широко распространенном публичном издании, а так как все хеши в дереве математически связаны между собой, мы получаем неопровержимое доказательство факта, что все они существовали раньше времени выхода публикации (а значит и существовали данные, по которым были сгенерированы таймстампы). Этот способ таймстампинга позволяет уйти от зависимости от закрытого ключа TSA (Time-Stamp Authority). В случае обычных time-stamps, которые подписаны закрытым ключом, мы должны доверять этому ключу, и как только заканчивается срок действия соответствующего сертификата нам необходимы дополнительные меры обеспечения доверия к time-stamp и к данным, с которыми он ассоциирован (пролонгация). В случае Linked time-stamp этой проблемы не возникает - имея доверие только к одному корневому хешу, мы имеем доверие ко всему дереву.

Опубликовал: Александр Абрамов (info@ict-online.ru)

Ключевые слова: электронный документооборот