WikiSort.ru - Не сортированное

Threefish Block

Threefish — это настраиваемый блочный шифр, определённый для блоков размером 256, 512 и 1024 бит. Шифр реализован в виде подстановочно-перестановочной сети. В основе шифра лежит простая функция MIX, принимающая на вход два 64-битных слова и состоящая из блоков сложения, циклического сдвига на константу, и сложения по модулю 2 (XOR). Используется 72 раунда для 256-битного и 512-битного шифра, и 80 раундов для 1024-битного шифра. Между раундами происходит перестановка слов, а каждые четыре раунда добавляется ключ, за счёт чего появляется нелинейность.

UBI

Threefish в Skein используется в режиме UBI (Unique Block Iteration) хеширования. Режим UBI — это разновидность режима Matyas-Meyer-Oseas.[1] Каждое звено UBI комбинирует входные сообщения с предыдущего звена цепи с последовательностью произвольной длины и устанавливает на выходе значение фиксированного размера. Сообщение, передающееся между звеньями (твик), содержит информацию о том, сколько байт было обработано, флаги начала и конца цепочки, и поле типа данных, которое позволяет различать сферы применения UBI. UBI гарантирует невоспроизводимость результата хеширования одного и того же сообщения и дополнительную защиту за счёт того, что на вход хеш-функции и шифра попадают одни и те же сообщения. UBI устроен следующим образом. Каждое звено цепи — это функция ${\displaystyle f(G,M,T_{s})}$

${\displaystyle G}$  — начальное ${\displaystyle N_{b}}$ -байтное значение

${\displaystyle M}$  — сообщение, представленное строкой байт (длина этой строки может быть произвольной, но максимум ${\displaystyle 2^{99}-8}$ бит)

${\displaystyle T_{s}}$  — стартовое значение твика целочисленного типа (128 бит).

Твик содержит следующие поля:

• Position — количество уже обработанных байт.
• Reserved — зарезервированные нулевые биты
• TreeLevel — позиция в дереве хеширования, либо ноль, если этот способ хеширования не применяется.
• BitPad — флаг, который поднимается в случае, если в блоке обрабатывался последний байт входного сообщения, которое содержит не целое число байт. В остальных случаях поле имеет значение 0.
• Type тип вызова UBI. Возможные значения см. ниже.
• First — флаг начала цепочки.
• Final — флаг конца цепочки.

Вычисления происходят следующим образом. Если количество бит ${\displaystyle M}$ делится на 8, то положим ${\displaystyle B=0}$ и ${\displaystyle M'=M}$ . Если количество бит ${\displaystyle M}$ не делится на 8, то дополним последний (неполный) байт следующим образом: старшему неиспользуемому биту присвоим значение 1, остальным 0 положим ${\displaystyle B=1}$ и ${\displaystyle M'=M}$ с учётом дополненного байта. ${\displaystyle N_{M}}$ — это число байт в ${\displaystyle M'}$ . Входное значение ограничено ${\displaystyle N_{M}<2^{96}}$ . Далее дополним ${\displaystyle M'}$ нулями так, чтобы количество бит ${\displaystyle M'}$ , было кратно ${\displaystyle N_{b}}$ и назовём полученный результат ${\displaystyle M''}$ . Разобьём ${\displaystyle M''}$ на ${\displaystyle k}$ блоков по ${\displaystyle N_{b}}$ байт каждый. Значение UBI вычисляется так:

${\displaystyle H_{0}=G}$

${\displaystyle H_{i+1}=E(H_{i};ToBytes(T_{s}+min(N_{M};(i+1)N_{b})+a_{i}2^{126}+b_{i}(B2^{119}+2^{127});16);M_{i})\bigoplus M_{i}}$ ,

где ${\displaystyle E}$  — функция вычисления блочного шифра, ${\displaystyle a_{0}=b_{k-1}=1}$ , остальные ${\displaystyle a_{i}=b_{i}=0}$

Твик вычисляется по формуле:

${\displaystyle T_{s}+min(N_{M};(i+1)N_{b})+a_{i}2^{126}+b_{i}(B2^{119}+2^{127})}$

Первое слагаемое определяет поля TreeLevel и Type, второе — поле Position, третье — выставляет флаг First, четвёртое — флаги Final и BitPad.

Дополнительные аргументы

В поле Type путём присвоения соответствующего значения ${\displaystyle T_{s}}$ могут быть заданы следующие параметры

• Key (Ключ). Используется в случае, если Skein работает как MAC или KDF. Вызов UBI с этим параметром происходит первым, чтобы использовать дополнительные возможности защиты.
• Configuration (Конфигурация). Используется всегда. Задаёт размер выходного значения и параметры для поддержки дерева хеширования.
• Personalisation (Персонализация). Параметр, который используется, если для разных пользователей требуются разные функции.
• Public Key (Открытый ключ). Используется для хеширования открытого ключа для подписи сообщения.
• Key Derivation Identifer.
• Nonce. Используется для работы в режиме потокового шифра
• Message (Сообщение). Сообщение для хеширования
• Output (Выход). Используется всегда, указывает на выходное преобразование.

Skein

В окончательном варианте вычисление Skein происходит следующим образом. Skein имеет следующие входные аргументы:

• ${\displaystyle N_{b}}$ Внутренний размер в байтах. Может принимать значения 32, 64, or 128.
• ${\displaystyle N_{0}}$ Размер выходного значения в битах.
• ${\displaystyle K}$ Ключ длиной ${\displaystyle N_{k}}$ байт. Может быть пустой строкой.
• ${\displaystyle Y_{l}}$ Размер листа дерева хеширования.
• ${\displaystyle Y_{f}}$ Коэффициент разветвления дерева.
• ${\displaystyle Y_{m}}$ Максимальная высота дерева
• ${\displaystyle L}$ Список из ${\displaystyle t}$ наборов (${\displaystyle T_{i}}$ , ${\displaystyle M_{i}}$ ) где ${\displaystyle T_{i}}$  — значение поля Type, ${\displaystyle M_{i}}$  — строка байт.

Сначала генерируется ключ ${\displaystyle K'}$ . Если ${\displaystyle K}$  — пустая строка, то начальное значение :${\displaystyle K'=0^{N_{b}}}$ . Если нет, то ${\displaystyle K'}$ вычисляется так:

${\displaystyle K'=UBI(0^{N_{b}},K,T_{cfg}2^{120})}$

Далее вычисления происходят по следующей схеме:

${\displaystyle G_{0}=UBI(K',C,T_{cfg}2^{120})}$

Здесь ${\displaystyle C}$  — конфигурационная строка, которая содержит идентификатор (он нужен, чтобы различать разные функции, созданные на основе UBI), информацию о версии, длине выходного значения, параметрах дерева.

${\displaystyle G_{i+1}=UBI(G_{i},M_{i},T_{i}2^{120})}$

Окончательный результат определяется так называемой функцией ${\displaystyle Output(G_{t},N_{0})}$ , которая определяется, как ведущие ${\displaystyle N_{0}/8}$ байт выражения

${\displaystyle UBI(G,ToBytes(0,8),T_{out}2^{120})\|UBI(G,ToBytes(1,8),T_{out}2^{120})\|...}$

Если параметры ${\displaystyle Y_{l}}$ , ${\displaystyle Y_{f}}$ , ${\displaystyle Y_{m}}$ ненулевые, то вычисления производятся иначе. Определяется размер листа дерева как ${\displaystyle N_{l}=N_{b}2^{Y_{l}}}$ и размер узла как ${\displaystyle N_{n}=N_{b}2^{Y_{f}}}$ .

Сообщение l-го уровня ${\displaystyle M_{l}}$ делится на блоки ${\displaystyle M_{li}}$ размером ${\displaystyle 8N_{l}}$ и вычисляется следующий уровень дерева, как слияние по всем ${\displaystyle i\in (0,k-1)}$

${\displaystyle M_{1+1}=UBI(G,M_{li},iNn+(l+1)2^{112}+T_{msg}2^{120})}$

Если же длина ${\displaystyle M_{l}}$ равна ${\displaystyle N_{b}}$ , то хеширование окончено и его результат ${\displaystyle G_{0}=M_{l}}$ . Если длина ${\displaystyle M_{l}}$ больше ${\displaystyle N_{b}}$ , но ${\displaystyle l=Y_{m}-1}$ , достигнута максимальная высота дерево, и в этом случае результат хеширования ${\displaystyle G_{0}=UBI(G,M_{l},Y_{m}2^{112}+T_{msg}2^{120})}$ .

Также существует упрощённая версия Skein с аргументами ${\displaystyle N_{b}}$ , ${\displaystyle N_{0}}$ , ${\displaystyle M}$ . Поле Type может принимать только значения Cfg и Msg