Расскажу про эволюцию формата зашифрованных пакетов в store-and-forward утилитах NNCP, о которых я уже писал на Хабре. Что может быть проще, чем передать пакет данных в зашифрованном виде? Но всё возникающие дополнительные потребности и пожелания пользователя, заставляют усложнять и исхитряться с форматом пакета.
Участники NNCP сетей обмениваются друг с другом зашифрованными пакетами. Каждый отправитель заранее знает долгоживущие публичные ключи получателя для алгоритмов подписи и согласования ключей. Как мог бы выглядеть наш зашифрованный пакет в простейшем случае?
Sender и Recipient — идентификаторы отправителя (хэши от публичных ключей). DHPub — эфемерный публичный ключ, использующийся для выработки сессионного ключа шифрования пакета. Sign — подпись, использующаяся для аутентификации отправителя и контекста шифрования.
Как известно, повсеместно применяется гибридная криптография с использованием асимметричных и симметричных алгоритмов. Первые крайне медленны, вторые очень быстры и имеют куда лучшую безопасность. Но симметричные алгоритмы можно использовать на практике тогда, когда вы безопасно можете обменяться ключами. Что в большинстве случаев невыполнимо, так как мы не можем встречаться физически лично с каждым участником. Асимметричные алгоритмы, такие как алгоритмы подписи и согласования ключей, использующие пары из публичного-приватного ключей, дают возможность согласовать симметричные ключи и аутентифицировать собеседников.
Одним из первых на практике применяющимся алгоритмом согласования ключей был протокол Диффи-Хеллмана (Diffie-Hellman). DH стал именем нарицательным, обозначением процесса согласования ключей. На практике используемые популярные DH-алгоритмы принципиально работают следующим образом:
Результат DH подаётся на вход специализированной функции выработки ключей (KDF, key derivation function), типа HKDF. Некоторые современные хэш-функции имеют KDF режим работы из коробки, как например BLAKE2 или BLAKE3, использованные в NNCP. KDF выдаст необходимое количество ключей, пригодных для использования в симметричных функциях шифрования и аутентификации.
Шифротекст, в простейшем случае, можем получить применяя алгоритм шифрования AES/Кузнечик в режиме счётчика (CTR) и алгоритм аутентификации сообщений (MAC) на основе хэш-функции типа HMAC-SHA2/HMAC-Стрибог поверх шифротекста.
Современные протоколы, типа TLS 1.3 и Noise, вместо функций шифрования используют функции аутентифицированного шифрования: AEAD (Authenticated Encryption with Associated Data). Их пользователь не думает о последовательности и особенностях совместного применения функций шифрования и аутентификации данных. Будет ли AEAD шифрование более безопасным чем какая-то определённая схема применения шифрования и аутентификации данных? Возможно что нет. Будет ли AEAD быстрее? Тоже не факт. Но использование AEAD не может быть не правильным. Для людей не очень разбирающихся в прикладной криптографии, с AEAD меньше возможностей фатально напортачить.
Большинство библиотек для AEAD шифрования предоставляют интерфейс не дружащий с потоковой обработкой данных. В Go, на котором написан NNCP, интерфейс блочного шифра позволяет потоково прокачивать любой объём данных. AEAD же интерфейс позволяет работать только с массивами байт. Поэтому мы вынуждены разбить наш передаваемый пакет на блоки, AEAD-шифруя каждый по отдельности. NNCP использует блоки размером 128KiB.
Это увеличивает размер передаваемых данных на размер MAC-тэга идущего в конце каждого блока. Если MAC будет 128-бит, то каждый гигабайт полезной нагрузки увеличится на 128KiB. Терпимые копейки. Но зато при дешифровании блоков, мы сразу же получим ошибку аутентификации блока, если что-то не в порядке.
Кроме того. AEAD функция принимает на вход ещё и опциональные ассоциированные данные, в качестве которых можно использовать заголовок пакета, тем самым, явно «связывая» и аутентифицируя шифротекст с контекстом: явно с эфемерным DH ключом, отправителем и получателем. Защищает ли это от гипотетических атак применимых в каких-то особых случаях использования? Возможно. Хуже не будет, неправильным быть не может.
AEAD шифры, как правило, имеют ещё один обязательный аргумент: nonce, некое одноразовое число. Его повторное использование будет фатально для безопасности. Но в случае с эфемерными сессионными ключами, абсолютно безопасно использовать просто счётчик.
Но перейдя на AEAD шифрование, мы только что создали серьёзную уязвимость: теперь шифротекст можно отрезать по границе блока и получатель даже не узнает что что-то пошло не так — он получит обрезанную по длине полезную нагрузку. Прежде это было невозможно, так как конец всего пакета имел MAC, аутентифицирующий весь объём данных, а не только единичного блока. Просто добавим поле с длиной полезной нагрузки:
NNCP не предлагает ничего для анонимизации участников, но иметь хоть какие-то базовые средства защиты метаданных было бы не плохо. Имеется особый отдельный тип пакета: промежуточный (transitional), который используется как обёртка над уже существующим зашифрованным пакетом. В сети Tor такой подход называется луковичным шифрованием. Но если в Tor это используется для анонимизации, то в NNCP промежуточные узлы предполагается использовать при невозможности прямой связи собеседников.
Полезной нагрузкой промежуточных пакетов является зашифрованный пакет для другого узла. Если мне надо отправить с узла A на узел D сообщение, а между ними связь возможна только через посредников B и C, то зашифрованный пакет будет:
В некоторых случаях это может дать и некую анонимизацию: например B понятия не имеет что пакет предназначается для D. Однако размер пакета является важной деанонимизирующей информацией. Сторонний наблюдатель сети, видя пакет с размером 12345, вряд ли часто будет видеть подобного размера остальные. Поэтому сможет косвенно понимать путь его прохождения.
Можем просто зашифровать это поле длины, а после шифротекста добавить псевдослучайный мусор.
В этом случае, размер уже не обязательно подписывать внутри Sign, так как ключ шифрования размера будет всё равно выработан из согласованного ключа DH.
Сторонний наблюдатель будет видеть сплошной псевдослучайный шум, не имея возможности понять где в нём граница между действительно полезной нагрузкой и дополнением. Если мы укажем NNCP, что минимальный размер пакета должен быть равен 100KiB, то все почтовые сообщения меньшего размера будут дополнены и неотличимы по размеру друг от друга. Кроме того, NNCP позволяет ограничивать и максимальный размер пакета, дробя его на части. Таким образом легко добиться того, что вообще весь трафик между участниками будет состоять из пакетов фиксированного размера.
Дополнением может быть полезная нагрузка из нулевых байт. AEAD шифрование превратит их в псевдослучайный шум. Но решено было использовать XOF-функцию, ключ к которой также вырабатывается через KDF. XOF-функцию можно рассматривать как хэш, но с очень большой длиной результата. Например BLAKE2 выдаёт хэш размером до 512-бит, а BLAKE2X XOF-функция до 256GiB. Это значительно быстрее работает чем AEAD-шифрование нулей.
Изначально, внутри пакета не было указания длины дополненных данных. Злоумышленник может взять зашифрованный пакет, отрезать от него один байт, отправить нам и каким-то образом разузнать смогли ли мы его обработать (дешифровать). Если смогли, то значит этот байт был частью дополнения, проигнорированного нами. Далее можно отрезать ещё один байт, итеративно дойдя до момента когда мы не сможем обработать пакет, поняв настоящую длину полезной нагрузки. Но даже при осуществлении подобной атаки на метаданные, аутентичность и конфиденциальность полезной нагрузки всё равно вне опасности.
Идентификатором пакета является хэш от его содержимого. Проверка целостности пакета «встроена» в идентификатор. При получении пакета по online каналам связи, сначала проверяется его целостность, а уж только потом он обрабатывается (дешифруется). Такая раздельная проверка целостности и обработки пакета приятна тем, что целостность можно проверить без знания приватного ключа, на котором будет вырабатываться сессионный ключ и вычисляться MAC.
Например вы взяли с собой ноутбук и находитесь в транспорте, в общественном месте. Если бы пришлось задействовать приватные ключи на ноутбуке, под прицелом наводнивших наши публичные места камер, то парольная фраза их защищающая с высокой долей вероятности будет скомпрометирована. Когда процесс передачи и проверки целостности пакетов изолирован от процесса их дешифрования и обработки, то приватные ключи можно задействовать в более безопасном окружении в другое время.
При online передаче пакетов, NNCP на лету считает их хэш. Скорость современных хэш-функций, типа BLAKE2 или BLAKE3, очень высока и вряд ли будет являться бутылочным горлышком на практике, не мешая максимально утилизировать как сетевые интерфейсы, так и накопители данных.
Однако, если передача файла была прервана, возможно программы и компьютер перезапущены, то состояние хэш-функции мы теряем. Мы будем вынуждены повторно прочитать пакет с диска с самого начала для проверки его целостности, а ведь он может занимать многие гигабайты.
Хэш-функции в массе своей устроены так, что последующие блоки зависят от предыдущих. Поэтому нет возможности что-то посчитать с середины, а потом «досчитать» недостающее с начала. Помочь тут могут деревья Меркле, известные ещё с конца 70-х годов, активно применяющиеся в огромном количестве задач. Принцип хэширования в них очень прост: данные разбиваются на блоки, от каждого независимо считается хэш, а дальше вычисляется хэш для каждой пары нижестоящих хэшей:
Кроме того что оно позволяет распараллеливать вычисление top хэша, оно даёт возможность вычислять хэши от произвольных частей данных. Хэшируется в деревьях Меркле чуть больше данных чем однократное применение хэш-функции ко всему объёму. NNCP использует 128KiB блоки: для 1TiB объёма L1 уровень будет содержать 256MiB хэшей. BLAKE2/BLAKE3 хэш функции на современных домашних ПК могут обрабатывать гигабайты данных в секунду на одном ядре — поэтому накладные расходы от деревья Меркле можно проигнорировать.
Для предотвращения возможной second preimage атаки на дерево, необходимо различать вызовы хэш функции вычисляющей значение L0 уровня и для вышестоящих. Популярен подход с добавлением констант 0x00 и 0x01 к хэшируемым данным. В NNCP применяется BLAKE3, внутри себя аналогично имеющий дерево хэшей для распараллеливания вычислений. При несимметричном количестве блоков L0 внутри BLAKE3, у нас появится ещё один L-уровень в дереве, что лишняя нагрузка. Так как в NNCP блоки 128KiB, то, добавление одного единственного байта, сделает деревья хэшей асимметричными. Но ничто не мешает использовать BLAKE3 с выставленным вшитым ключом: один ключ будет использоваться для расчёта L0 блоков, а другой для всех остальных. Это позволит эффективнее использовать внутреннее дерево BLAKE3.
Таким образом, во время докачивания файла, часть хэшей уже можно считать на лету, по мере сохранения на диск, а также сразу вычислять некоторые значения L2 и вышестоящих уровней. Когда пакет будет полностью докачан, то достаточно будет прочитать с диска только начальную часть.
Явное указание длины полезной нагрузки в начале пакета требует, собственно, знание этой длины. Для передачи файлов это не проблема: мы видим их размер на файловой системе. Но NNCP позволяет передавать и данные полученные через стандартный поток ввода (stdin), например при отправке почты. Изначально проблема с узнаванием размера решалась предварительной записью данных во временный файл. Конечно же, шифруя данные на лету эфемерным симметричным ключом, чтобы на диске ничего не оставалось в открытом виде.
Двойная запись на диск (во временный файл, а из него потом уже в зашифрованный пакет) не эффективна. Но для почты, где размер данных достаточно мал по современным меркам — приемлемо. А если учитывать кэширование и отложенную запись современных файловых систем, то на диск временный файл имеет шанс и не попасть вовсе. Но некоторые пользователи NNCP активно используют передачу большого объёма данных именно через stdin, что неприятно медленно из-за этого временного файла.
В общем случае, учитывая что у нас потоковое AEAD-шифрование, шифрующее побайтно, а не поблочно, где каждый последующий байт независим от предыдущих, мы можем изменять данные в шифротексте. Если хотим заменить X на Y в AEAD-блоке, то достаточно применить XOR (битовое исключающее ИЛИ) операцию между блоком и особым подготовленным с X XOR Y значением:
и вычислить новое значение MAC-а в конце этого блока. Можно бы было поле длины не трогать во время формирования зашифрованного блока, вернувшись к нему когда stdin сигнализирует о завершении передачи. Так как целостность пакета (хэш от него) считается параллельно сразу же с формированием шифротекста, то до использования деревьев Меркле, было бы невозможно изменение полей в начале пакета.
Но всё это усугубляется тем, что transitional пакеты формируются тоже сразу же на лету: если надо отправить пакет через десяток промежуточных узлов, то NNCP потоково формирует 11 зашифрованных пакетов, без каких-либо временных файлов. Но значение длины неизвестно в каждом из этих пакетов. Чисто математически мы можем высчитать необходимые XOR-ы для изменения заголовков всех 11 пакетов. Но звучит как не самая тривиальная задача.
Но так ли пользователям NNCP важно знать настоящий размер полезной нагрузки в зашифрованном пакете не дешифруя его полностью? Я не нашёл практических аргументов в пользу этого. А раз так, то нам достаточно лишь сигнализировать где полезная нагрузка в шифротексте кончается.
Можно легко решить задачу: просто передавая внутри каждого блока информацию о количестве полезной нагрузки в нём, и не конец ли это. По сути у нас есть только один особый блок — в котором заканчивается полезная нагрузка и начинается опциональное дополнение шумом. То есть, отличить нам нужно всего лишь один единственный блок среди всех остальных. Добавить к шифротексту явный признак его особенного формата — не вариант, так как сторонний наблюдатель его тоже увидит. Добавлять структуру в каждую полезную нагрузку каждого блока — слишком большие накладные расходы на такую мелочь.
Сигнализировать об особенности блока можно применением другого ключа шифрования. Такая практика например используется в распространённой CMAC функции, где два разных ключа используются в последнем блоке для сигнализации о наличии или отсутствия дополнения открытого текста, экономя один блок шифротекста. В NNCP можно применить такой же подход: другой ключ шифрования использовать для блока, в котором первые 64-бита содержат размер суммарной полезной нагрузки. Формат пакета становится таким:
IPad это опциональное дополнение данных внутри блока, нулевые байты. OPad же генерируется XOF-функцией.
Но если Size также будет включать в себя и размер дополнения (ещё одно 64-бит число), то злоумышленник уже не сможет, отрезая по байту, разузнать размер дополнения. Причём явно аутентифицировать содержимое OPad нам не нужно: дополнение вырабатывается полностью детерминировано, с использованием неизвестного стороннему наблюдателю ключу, и нам достаточно генерировать XOF-последовательность у себя, сравнивая со значением в пакете.
Таким образом, мы получаем возможность потокового создания пакета, с явной аутентификацией размера полезной нагрузки и дополнения. Полностью избавляясь от необходимости использования временного файла.
Простейший пакет
Участники NNCP сетей обмениваются друг с другом зашифрованными пакетами. Каждый отправитель заранее знает долгоживущие публичные ключи получателя для алгоритмов подписи и согласования ключей. Как мог бы выглядеть наш зашифрованный пакет в простейшем случае?
+------- signed --------+ / \ Sender || Recipient || DHPub || Sign || Ciphertext || MAC
Sender и Recipient — идентификаторы отправителя (хэши от публичных ключей). DHPub — эфемерный публичный ключ, использующийся для выработки сессионного ключа шифрования пакета. Sign — подпись, использующаяся для аутентификации отправителя и контекста шифрования.
Как известно, повсеместно применяется гибридная криптография с использованием асимметричных и симметричных алгоритмов. Первые крайне медленны, вторые очень быстры и имеют куда лучшую безопасность. Но симметричные алгоритмы можно использовать на практике тогда, когда вы безопасно можете обменяться ключами. Что в большинстве случаев невыполнимо, так как мы не можем встречаться физически лично с каждым участником. Асимметричные алгоритмы, такие как алгоритмы подписи и согласования ключей, использующие пары из публичного-приватного ключей, дают возможность согласовать симметричные ключи и аутентифицировать собеседников.
Одним из первых на практике применяющимся алгоритмом согласования ключей был протокол Диффи-Хеллмана (Diffie-Hellman). DH стал именем нарицательным, обозначением процесса согласования ключей. На практике используемые популярные DH-алгоритмы принципиально работают следующим образом:
- Каждый участник генерирует ключевую пару из приватного и публичного ключа: у Алисы DHPubAlice, DHPrvAlice, а у Боба DHPubBob, DHPrvBob;
- Алиса и Боб обмениваются своими публичным ключами;
- Алиса вызывает функцию DH: DH(DHPrvAlice, DHPubBob), а Боб DH(DHPrvBob, DHPubAlice). Результат работы этих двух вызовов (свой приватный, чужой публичный) выдаёт идентичный результат.
Результат DH подаётся на вход специализированной функции выработки ключей (KDF, key derivation function), типа HKDF. Некоторые современные хэш-функции имеют KDF режим работы из коробки, как например BLAKE2 или BLAKE3, использованные в NNCP. KDF выдаст необходимое количество ключей, пригодных для использования в симметричных функциях шифрования и аутентификации.
Шифротекст, в простейшем случае, можем получить применяя алгоритм шифрования AES/Кузнечик в режиме счётчика (CTR) и алгоритм аутентификации сообщений (MAC) на основе хэш-функции типа HMAC-SHA2/HMAC-Стрибог поверх шифротекста.
AEAD
Современные протоколы, типа TLS 1.3 и Noise, вместо функций шифрования используют функции аутентифицированного шифрования: AEAD (Authenticated Encryption with Associated Data). Их пользователь не думает о последовательности и особенностях совместного применения функций шифрования и аутентификации данных. Будет ли AEAD шифрование более безопасным чем какая-то определённая схема применения шифрования и аутентификации данных? Возможно что нет. Будет ли AEAD быстрее? Тоже не факт. Но использование AEAD не может быть не правильным. Для людей не очень разбирающихся в прикладной криптографии, с AEAD меньше возможностей фатально напортачить.
Большинство библиотек для AEAD шифрования предоставляют интерфейс не дружащий с потоковой обработкой данных. В Go, на котором написан NNCP, интерфейс блочного шифра позволяет потоково прокачивать любой объём данных. AEAD же интерфейс позволяет работать только с массивами байт. Поэтому мы вынуждены разбить наш передаваемый пакет на блоки, AEAD-шифруя каждый по отдельности. NNCP использует блоки размером 128KiB.
+------- signed --------+ / \ Sender || Recipient || DHPub || Sign || AEAD(Block0) || AEAD(Block1) || ...
Это увеличивает размер передаваемых данных на размер MAC-тэга идущего в конце каждого блока. Если MAC будет 128-бит, то каждый гигабайт полезной нагрузки увеличится на 128KiB. Терпимые копейки. Но зато при дешифровании блоков, мы сразу же получим ошибку аутентификации блока, если что-то не в порядке.
Кроме того. AEAD функция принимает на вход ещё и опциональные ассоциированные данные, в качестве которых можно использовать заголовок пакета, тем самым, явно «связывая» и аутентифицируя шифротекст с контекстом: явно с эфемерным DH ключом, отправителем и получателем. Защищает ли это от гипотетических атак применимых в каких-то особых случаях использования? Возможно. Хуже не будет, неправильным быть не может.
AEAD шифры, как правило, имеют ещё один обязательный аргумент: nonce, некое одноразовое число. Его повторное использование будет фатально для безопасности. Но в случае с эфемерными сессионными ключами, абсолютно безопасно использовать просто счётчик.
Размер пакета и приватность
Но перейдя на AEAD шифрование, мы только что создали серьёзную уязвимость: теперь шифротекст можно отрезать по границе блока и получатель даже не узнает что что-то пошло не так — он получит обрезанную по длине полезную нагрузку. Прежде это было невозможно, так как конец всего пакета имел MAC, аутентифицирующий весь объём данных, а не только единичного блока. Просто добавим поле с длиной полезной нагрузки:
+----------- signed ------------+ / \ Sender || Recipient || DHPub || Size || Sign || AEAD(Block0) || AEAD(Block1) || ...
NNCP не предлагает ничего для анонимизации участников, но иметь хоть какие-то базовые средства защиты метаданных было бы не плохо. Имеется особый отдельный тип пакета: промежуточный (transitional), который используется как обёртка над уже существующим зашифрованным пакетом. В сети Tor такой подход называется луковичным шифрованием. Но если в Tor это используется для анонимизации, то в NNCP промежуточные узлы предполагается использовать при невозможности прямой связи собеседников.
Полезной нагрузкой промежуточных пакетов является зашифрованный пакет для другого узла. Если мне надо отправить с узла A на узел D сообщение, а между ними связь возможна только через посредников B и C, то зашифрованный пакет будет:
From:A || To:B || DHPubAB || ...
|
+---------------------------+
|
+-> From:A || To:C || DHPubAC || ...
|
+---------------------------+
|
+-> From:A || To:D || DHPubAD || payload
В некоторых случаях это может дать и некую анонимизацию: например B понятия не имеет что пакет предназначается для D. Однако размер пакета является важной деанонимизирующей информацией. Сторонний наблюдатель сети, видя пакет с размером 12345, вряд ли часто будет видеть подобного размера остальные. Поэтому сможет косвенно понимать путь его прохождения.
Можем просто зашифровать это поле длины, а после шифротекста добавить псевдослучайный мусор.
+------- signed --------+ / \ Sender || Recipient || DHPub || Sign || AEAD(Size) || AEAD(Block0) || AEAD(Block1) || ...
В этом случае, размер уже не обязательно подписывать внутри Sign, так как ключ шифрования размера будет всё равно выработан из согласованного ключа DH.
Сторонний наблюдатель будет видеть сплошной псевдослучайный шум, не имея возможности понять где в нём граница между действительно полезной нагрузкой и дополнением. Если мы укажем NNCP, что минимальный размер пакета должен быть равен 100KiB, то все почтовые сообщения меньшего размера будут дополнены и неотличимы по размеру друг от друга. Кроме того, NNCP позволяет ограничивать и максимальный размер пакета, дробя его на части. Таким образом легко добиться того, что вообще весь трафик между участниками будет состоять из пакетов фиксированного размера.
Дополнением может быть полезная нагрузка из нулевых байт. AEAD шифрование превратит их в псевдослучайный шум. Но решено было использовать XOF-функцию, ключ к которой также вырабатывается через KDF. XOF-функцию можно рассматривать как хэш, но с очень большой длиной результата. Например BLAKE2 выдаёт хэш размером до 512-бит, а BLAKE2X XOF-функция до 256GiB. Это значительно быстрее работает чем AEAD-шифрование нулей.
Изначально, внутри пакета не было указания длины дополненных данных. Злоумышленник может взять зашифрованный пакет, отрезать от него один байт, отправить нам и каким-то образом разузнать смогли ли мы его обработать (дешифровать). Если смогли, то значит этот байт был частью дополнения, проигнорированного нами. Далее можно отрезать ещё один байт, итеративно дойдя до момента когда мы не сможем обработать пакет, поняв настоящую длину полезной нагрузки. Но даже при осуществлении подобной атаки на метаданные, аутентичность и конфиденциальность полезной нагрузки всё равно вне опасности.
Докачивание файлов
Идентификатором пакета является хэш от его содержимого. Проверка целостности пакета «встроена» в идентификатор. При получении пакета по online каналам связи, сначала проверяется его целостность, а уж только потом он обрабатывается (дешифруется). Такая раздельная проверка целостности и обработки пакета приятна тем, что целостность можно проверить без знания приватного ключа, на котором будет вырабатываться сессионный ключ и вычисляться MAC.
Например вы взяли с собой ноутбук и находитесь в транспорте, в общественном месте. Если бы пришлось задействовать приватные ключи на ноутбуке, под прицелом наводнивших наши публичные места камер, то парольная фраза их защищающая с высокой долей вероятности будет скомпрометирована. Когда процесс передачи и проверки целостности пакетов изолирован от процесса их дешифрования и обработки, то приватные ключи можно задействовать в более безопасном окружении в другое время.
При online передаче пакетов, NNCP на лету считает их хэш. Скорость современных хэш-функций, типа BLAKE2 или BLAKE3, очень высока и вряд ли будет являться бутылочным горлышком на практике, не мешая максимально утилизировать как сетевые интерфейсы, так и накопители данных.
Однако, если передача файла была прервана, возможно программы и компьютер перезапущены, то состояние хэш-функции мы теряем. Мы будем вынуждены повторно прочитать пакет с диска с самого начала для проверки его целостности, а ведь он может занимать многие гигабайты.
Хэш-функции в массе своей устроены так, что последующие блоки зависят от предыдущих. Поэтому нет возможности что-то посчитать с середины, а потом «досчитать» недостающее с начала. Помочь тут могут деревья Меркле, известные ещё с конца 70-х годов, активно применяющиеся в огромном количестве задач. Принцип хэширования в них очень прост: данные разбиваются на блоки, от каждого независимо считается хэш, а дальше вычисляется хэш для каждой пары нижестоящих хэшей:
hash() hash() hash() hash() L1 ^ ^ ^ ^ | | | | Block0 || Block1 || Block2 || Block3 || ... L0 ------------------------------------------------
hash() hash() L2
/ \ / \
/ \ / \
hash() hash() hash() hash() L1
^ ^ ^ ^
| | | |
Block0 || Block1 || Block2 || Block3 || ... L0
------------------------------------------------
top
^
|
+---hash()---+ L3
/ \
hash() hash() L2
/ \ / \
/ \ / \
hash() hash() hash() hash() L1
^ ^ ^ ^
| | | |
Block0 || Block1 || Block2 || Block3 || ... L0
------------------------------------------------
Кроме того что оно позволяет распараллеливать вычисление top хэша, оно даёт возможность вычислять хэши от произвольных частей данных. Хэшируется в деревьях Меркле чуть больше данных чем однократное применение хэш-функции ко всему объёму. NNCP использует 128KiB блоки: для 1TiB объёма L1 уровень будет содержать 256MiB хэшей. BLAKE2/BLAKE3 хэш функции на современных домашних ПК могут обрабатывать гигабайты данных в секунду на одном ядре — поэтому накладные расходы от деревья Меркле можно проигнорировать.
Для предотвращения возможной second preimage атаки на дерево, необходимо различать вызовы хэш функции вычисляющей значение L0 уровня и для вышестоящих. Популярен подход с добавлением констант 0x00 и 0x01 к хэшируемым данным. В NNCP применяется BLAKE3, внутри себя аналогично имеющий дерево хэшей для распараллеливания вычислений. При несимметричном количестве блоков L0 внутри BLAKE3, у нас появится ещё один L-уровень в дереве, что лишняя нагрузка. Так как в NNCP блоки 128KiB, то, добавление одного единственного байта, сделает деревья хэшей асимметричными. Но ничто не мешает использовать BLAKE3 с выставленным вшитым ключом: один ключ будет использоваться для расчёта L0 блоков, а другой для всех остальных. Это позволит эффективнее использовать внутреннее дерево BLAKE3.
Таким образом, во время докачивания файла, часть хэшей уже можно считать на лету, по мере сохранения на диск, а также сразу вычислять некоторые значения L2 и вышестоящих уровней. Когда пакет будет полностью докачан, то достаточно будет прочитать с диска только начальную часть.
Потоковое шифрование
Явное указание длины полезной нагрузки в начале пакета требует, собственно, знание этой длины. Для передачи файлов это не проблема: мы видим их размер на файловой системе. Но NNCP позволяет передавать и данные полученные через стандартный поток ввода (stdin), например при отправке почты. Изначально проблема с узнаванием размера решалась предварительной записью данных во временный файл. Конечно же, шифруя данные на лету эфемерным симметричным ключом, чтобы на диске ничего не оставалось в открытом виде.
Двойная запись на диск (во временный файл, а из него потом уже в зашифрованный пакет) не эффективна. Но для почты, где размер данных достаточно мал по современным меркам — приемлемо. А если учитывать кэширование и отложенную запись современных файловых систем, то на диск временный файл имеет шанс и не попасть вовсе. Но некоторые пользователи NNCP активно используют передачу большого объёма данных именно через stdin, что неприятно медленно из-за этого временного файла.
В общем случае, учитывая что у нас потоковое AEAD-шифрование, шифрующее побайтно, а не поблочно, где каждый последующий байт независим от предыдущих, мы можем изменять данные в шифротексте. Если хотим заменить X на Y в AEAD-блоке, то достаточно применить XOR (битовое исключающее ИЛИ) операцию между блоком и особым подготовленным с X XOR Y значением:
DATA || X || DATA
\ /
+-------------------+
|
v
XOR
^
|
+-------------------+
/ \
0000 || X XOR Y || 0000
и вычислить новое значение MAC-а в конце этого блока. Можно бы было поле длины не трогать во время формирования зашифрованного блока, вернувшись к нему когда stdin сигнализирует о завершении передачи. Так как целостность пакета (хэш от него) считается параллельно сразу же с формированием шифротекста, то до использования деревьев Меркле, было бы невозможно изменение полей в начале пакета.
Но всё это усугубляется тем, что transitional пакеты формируются тоже сразу же на лету: если надо отправить пакет через десяток промежуточных узлов, то NNCP потоково формирует 11 зашифрованных пакетов, без каких-либо временных файлов. Но значение длины неизвестно в каждом из этих пакетов. Чисто математически мы можем высчитать необходимые XOR-ы для изменения заголовков всех 11 пакетов. Но звучит как не самая тривиальная задача.
Но так ли пользователям NNCP важно знать настоящий размер полезной нагрузки в зашифрованном пакете не дешифруя его полностью? Я не нашёл практических аргументов в пользу этого. А раз так, то нам достаточно лишь сигнализировать где полезная нагрузка в шифротексте кончается.
Можно легко решить задачу: просто передавая внутри каждого блока информацию о количестве полезной нагрузки в нём, и не конец ли это. По сути у нас есть только один особый блок — в котором заканчивается полезная нагрузка и начинается опциональное дополнение шумом. То есть, отличить нам нужно всего лишь один единственный блок среди всех остальных. Добавить к шифротексту явный признак его особенного формата — не вариант, так как сторонний наблюдатель его тоже увидит. Добавлять структуру в каждую полезную нагрузку каждого блока — слишком большие накладные расходы на такую мелочь.
Сигнализировать об особенности блока можно применением другого ключа шифрования. Такая практика например используется в распространённой CMAC функции, где два разных ключа используются в последнем блоке для сигнализации о наличии или отсутствия дополнения открытого текста, экономя один блок шифротекста. В NNCP можно применить такой же подход: другой ключ шифрования использовать для блока, в котором первые 64-бита содержат размер суммарной полезной нагрузки. Формат пакета становится таким:
+------- signed --------+
/ \ key=full key=full
Sender || Recipient || DHPub || Sign || AEAD(Block0) || AEAD(Block1) || ...
|
+--------------------------------------------------------------------+
|
v key=full key=size
... || AEAD(Block.) || AEAD(Block.) || OPad ...
/ \
/ \
Size || Payload || IPad
IPad это опциональное дополнение данных внутри блока, нулевые байты. OPad же генерируется XOF-функцией.
Но если Size также будет включать в себя и размер дополнения (ещё одно 64-бит число), то злоумышленник уже не сможет, отрезая по байту, разузнать размер дополнения. Причём явно аутентифицировать содержимое OPad нам не нужно: дополнение вырабатывается полностью детерминировано, с использованием неизвестного стороннему наблюдателю ключу, и нам достаточно генерировать XOF-последовательность у себя, сравнивая со значением в пакете.
Таким образом, мы получаем возможность потокового создания пакета, с явной аутентификацией размера полезной нагрузки и дополнения. Полностью избавляясь от необходимости использования временного файла.