SPHINCS

Материал из Википедии — свободной энциклопедии
Данная страница не проверялась участниками с соответствующими правами.
Перейти к навигации Перейти к поиску

SPHINCS (stateless hash-based signatures) — криптографическая схема, основанная на криптографической стойкости хеш-функции. Схема включает в себя алгоритм формирования и проверки электронной цифровой подписи.

NIST[1] (Национальный институт стандартов и технологий США) опубликовал запрос[2] на разработку новых криптографических алгоритмов с открытым ключом, которые были бы устойчивы к атакам с использованием квантового компьютера. Уже сейчас IBM располагает готовым технологическим решением[3] — квантовой системой, состоящей из 20 кубитов. Возможно, масштабирование квантовой системы, до размеров которые представляли бы угрозу широко употребительным сейчас алгоритмам цифровой подписи, это вопрос ближайших десятилетий.[4] Одним из возможных решений описанной проблемы может являться cхема SPHINCS.

Предпосылки появления, альтернативы, описание

[править | править код]

В настоящее время нет однозначного ответы на вопрос: «Как обеспечить функциональность электронной цифровой подписи в постквантовом мире?»

Под функциональностью обычно понимают:

  • аутентификация источника сообщения
  • контроль целостности сообщения
  • защита сообщения от подделывания
  • малый объём цифровой подписи
  • высокая скорость генерации/проверки цифровой подписи

Рассмотрим известные схемы цифровой подписи:

  1. RSA и ECC, широко распространенные в настоящее время, достаточно компактны и быстры, но взламываются за полиномиальное время с помощью алгоритма Шора(при наличии квантового компьютера)
  2. GGH и другие схемы, построенные на решетках, имеют неясные перспективы роста уровня безопасности (только 80 % от заявленных разработчиками «100 bit» к 2013 году)
  3. Схемы многомерной криптографии, построенные на решениях уравнений, основанных на многомерных полиномах над конечным полем, имеют очень короткие и быстро обрабатываемые подписи, приемлемого размера ключи для использования в распространенных приложениях, но такие же неопределенные перспективы криптографической стойкости для квантового компьютера

Альтернативы

Тип Схема подписи Тип Схема подписи
Криптография на решётках Криптография с использованием хеш-функций
  • Gravity-SPHINCS
  • SPHINCS+
Алгоритмы алгебраического кодирования
  • pqsigRM
  • RaCoSS
  • RankSign
 Многомерная криптография
  • DualModeMS
  • GeMSS
  • Gui
  • HiMQ-3
  • LUOV
  • MQDSS
  • Rainbow

***Полная версия таблицы

В свете вышеизложенного оправданными оказываются схемы, основанные на криптографических хеш-функциях (разумеется другие алгоритмы тоже используют их, но эти не используют ничего кроме них). Безопасность схем такого рода основывается на свойствах стойкости хеш-функций, доказанных даже для такой распространенной функции как MD5.

SPHINCS представляет из себя высоконадежную систему цифровой подписи, основанную на хеш-функции, соответствующую криптографическим стандартам(в случае hash-based подписи это означает схему без контроля состояний ***в англ. литературе stateless), которая предоставляет безопасность «128 bit» против атак квантового компьютера и может быть реализована на существующей элементной базе (4-core 3.5 GHz Intel CPU).

История развития hash-based подписей (предшественники SPHINCS)

[править | править код]
  • Идея создания подписи, основанной на хеш-функции, восходит к американскому учёному, Лесли Лэмпорту. Подпись Лэмпорта предполагает использование одноразовой пары ключей(OTS key pair). Очевидно, что секретный ключ такой подписи нельзя использовать дважды, кроме того для подписи N-бит сообщения требуется использовать последовательность из N открытых ключей, что делает схему трудно применимой на практике.

Пример подписи Лэмпорта

[править | править код]

Пример подписи 1 бита сообщения по схеме Лэмпорта

Имеем: 

Криптостойкую хеш-функцию + Генератор случайных чисел

Сгенерируем секретный и открытый ключ: 

     SK = пара случайных чисел
      PK = 2 числа, результат хеширования SK

Подпишем сообщение: 

     Хешируем сообщение
      Биту хешированного сообщения ставим в соответствие число(X) из пары секретного ключа
      Это число(X) + PK = Подпись

Проверка подписи: 

     Хешируем сообщение
      Биту хешированного сообщения ставим в соответствие число из PK(Y) по тому же правилу, что и при подписи
      Хешируем число(X), переданное в подписи
      Если Y = X , то подпись верна
  • Чтобы иметь возможность подписывать компактным открытым ключом множество сообщений, Меркл предложил алгоритм, который сейчас называется «дерево Меркла». Он взял за основу подпись Лампорта(OTS схему). Чтобы создать многоразовую схему подписей, Меркл инициализировал 2h OTS(пар одноразовых ключей), используя бинарное дерево высоты h. Листья бинарного дерева* есть ни что иное как хешированные открытые ключи из схемы OTS. Секретные ключи из OTS становятся секретными ключами схемы Меркла без изменений. А вот открытым ключом в этой схеме является корень бинарного дерева.
Процесс построения дерева Меркла

Дерево Меркла

[править | править код]

Таким образом полная подпись Меркла включает в себя:

  1. Индекс использованных ключей OTS(one-time signature) в бинарном дереве (они используются в определённом порядке)
  2. Открытый ключ и подпись схемы OTS
  3. Вспомогательные данные, которые позволят дойти от листа дерева до его корня
  • Даже после изобретения дерева Меркла схемы подписей основанные на хеш-функциях имели нерешенные проблемы:
  1. Необходимость контролировать использованные ключи, как неизбежный побочный эффект лежащей в основе OTS(one-time signature) схемы. Это ставило под угрозу целостность таких схем(перенос с одного устройства на другое, восстановление данных)
  2. Экспоненциальный рост временны́х затрат на генерацию подписей и ключей с ростом высоты дерева n

___________________________________________________________________________________________________________________

  • Вышеизложенные проблемы решили две идеи:
  1. Одед Голдрейх предложил вместо определённого порядка использования ключей и индексирования по листьям бинарного дерева высоты n использовать хеш-функцию, которая бы принимала подписываемое сообщение и возвращала число h от 0 до (2n)-1. Это число(h) и определяло бы пару ключей OTS. Также возможно использование генератора случайных чисел с равномерным распределением в том же диапазоне. Тогда криптографическая стойкость схемы будет зависеть от вероятности коллизий. Практика показывает, что можно достигнуть вероятности повторного использования пары ключей 2-30, при количестве подписей 250.
  2. Проблема чрезмерных временных затрат решается путем использования «гипердеревьев», состоящих из слоёв обычных бинарных деревьев. Например, использование d слоёв из деревьев высоты h/d позволяет сократить время генерации ключей c O(2h) до O(d*2h/d), а время генерации подписи с O(2h) до O(h)

Устройство схемы электронно-цифровой подписи SPHINCS

[править | править код]

Составляющие схемы

[править | править код]

SPHINCS[6] использует в своей работе некоторый набор параметров, функций и примитивов(побочных схем):

Функции

  • Две криптографические хеш-функции F:{0,1}n→{0,1}n H:{0,1}2n→{0,1}n
  • Случайная хеш-функция с произвольной областью определения M:{0,1}n * {0,1}*→{0,1}m, где m = poly(n)
  • Семейство псевдослучайных генераторов Gλ:{0,1}n→{0,1λn, для различных значений λ
  • Ансамбль псевдослучайных функций Kλ:{0,1}λ * {0,1}n→{0,1}n
  • Семейство функций произвольного ввода E:{0,1}* * {0,1}n→{0,1}2n

Примитивы

  • Гипердерево[6](дерево деревьев) высоты h∈N, которое состоит из d слоёв, каждый из которых имеет высоту h/d
  • Усовершенствованная схема Winternitz one-time signature (WOTS+[6])
  • Усовершенствованная tree-based few-time signature scheme (HORST[6])

Параметры

  • Главный параметр криптографической безопасности n ∈ N
  • Параметры для достижения пространственно-временного компромисса w ∈ N(WOTS+), t = 2τ ∈ N(HORST), k∈N(HORST) !(k*τ = m)

Например, для схемы SPHINCS-256 имеют место такие параметры n = 256, m =512, h = 60, d = 12, w = 16, t = 2^16, k = 32 _______________________________________________________________________________________________________________

Примитивы

[править | править код]

Далее будут рассмотрены примитивы(составные части подписи SPHINCS)

WOTS+[6]
[править | править код]

На входе имеются параметры n и w. 

     - Определить l1  и l2:

     - Использовать функцию F (F:{0,1}n→{0,1}n) для построения 
       следующей "связывающей функции"(Chaining function)
  • Chaining function ci(x,r)

На входе имеется значение x∈{0, 1}n, счетчик итераций i∈N, и матрица битовых масок r = (r1, . . . , rj) ∈ {0, 1}n×j, где j ≥ i 

     - Если   i = 0, c возвращает x(c0(x, r) = x
     - Для    i > 0  функция определяется рекурсивно: ci(x,r) = F(ci−1(x, r) ⊕ ri)
  • Key Generation Algorithm (sk, pk ← WOTS.kg(S, r))

На входе имеется некоторое значение(семя) S∈{0, 1}n и матрицу битовых масок r = (r1, . . . , rj)∈{0, 1}n×(w-1) 

     - Вычислить секретный ключ: sk = (sk1, . . . ,skl) ← Gl(S)
     - Вычислить открытый ключ:  pk = (pk1, . . . , pkl) = (cw−1(sk1, r), . . . , cw−1(skl, r))
!Семя S занимает меньше памяти, чем ключи, поэтому их можно вычислять по мере необходимости
  • Signature Algorithm (σ ← WOTS.sign(M, S, r))

На входе имеется значение(семя) S∈{0, 1}n, матрица битовых масок r, и n-битное сообщение M 

     - Вычислить представление сообщения M в поле Fw: M = (M1 . . . Ml1), Mi ∈ {0, . . . , w − 1}
     - Вычислить контрольную сумму   C  = ∑l1 {{{1}}}(w − 1 − Mi) 
       И её представление в поле Fw: C = (C1, . . . , Cl2)
     - Вычислить конкатенацию M||C : B = (b1, . . .,bl) = M || C
     - Вычислить подпись             σ = (σ1, . . . , σl) = (cb1(sk1, r), . . . , cbbl(skl, r))
  • Verification Algorithm (pk' ← WOTS.vf(M, σ, r))

На входе имеется значение матрицы битовых масок r, n-битное сообщение M, и подпись σ 

     - Вычислить bi, 1 ≤ i ≤ l так же, как описано в алгоритме генерации подписи
     - Вычислить открытый ключ на стороне приема pk' = (pk'1, . . . , pk'l) = (cw−1−b1(σ1, rb1+1,w−1), . . . , cw−1−bl(σl,rbl+1,w−1))

!Подпись считается верной, если вычисленный на стороне приема открытый ключ pk'совпадает с сеансовым отрытым ключом
Бинарное дерево хешей, использующееся в схеме SPHINCS[6]
[править | править код]
Бинарное дерево хешей

Бинарное дерево высоты h. Оно всегда имеет 2h листьев, которые содержат n-битные строки Li, i ∈ [2h − 1]. Для вычисления остальных узлов дерева Ni,j используется битовая маска подходящей длины Qj ∈ {0, 1}2n, 0 < j ≤ h. Ni,j вычисляются по следующему алгоритму: 

             Ni,j = H((N2i,j−1||N2i+1,j−1) ⊕ Qj )
HORST[6]
[править | править код]
  • Key Generation Algorithm (pk ← HORST.kg(S, Q))

На входе имеется некоторое значение(семя) S∈{0, 1}n и матрица битовых масок Q∈ {0, 1}2n×log(t) 

        - Вычислить секретный ключ            sk = (sk1, . . . ,skt) ← Gt(S)
        - Вычислить значение листьев дерева   Li = F(ski),   для i ∈ [t − 1]
        - Построить бинарное дерево хешей высотой log(t), используя матрицу битовых масок Q()
        - Положить в качестве открытого ключа pk значение корня бинарного дерева хешей
  • Signature Algorithm m ((σ, pk) ← HORST.sign(M, S, Q))

На входе имеется значение(семя) S∈{0, 1}n, матрица битовых масок Q∈ {0, 1}2n×log(t) и сообщение M ∈ {0, 1}m 

        - Вычислить секретный ключ sk как описано выше
        - Разбить сообщение на k битовых строк длиной log(t) каждая:  M = (M0, . . . , Mk-1). 
          Интерпретировать каждую строку как беззнаковое целое число
        - Составить подпись σi = (skMi, AuthMi) для i ∈ [k−1]. Подпись включает в себя Mi-ый элемент секретного ключа и данные
          необходимые для нахождения корня бинарного дерева хешей.
        - Добавить к подписи открытый ключ
  • Verification Algorithm (pk' ← HORST.vf(M, σ, Q))

На входе имеется подпись σ, матрица битовых масок Q∈ {0, 1}2n×log(t) и сообщение M ∈ {0, 1}m 

        - Разбить сообщение на k битовых строк длиной log(t) каждая:  M = (M0, . . . , Mk-1). Интерпретировать каждую строку как
           беззнаковое целое число Mi
        - Вычислить значение корня бинарного дерева хешей для каждого Mi. Это легко сделать, так как подпись содержит все
          необходимое для построения дерева: листья LMi = F(σ1i), вспомогательные данные для продвижения вверх по дереву
          Q и AuthMi = σ2i
        - Сравнить вычисленные значения корня дерева с переданным открытым ключом. Если совпадают, то подпись верна

SPHINCS[6]

[править | править код]

Логическая структура схемы SPHINCS

[править | править код]

SPHINCS представляет собой «гипердерево» высоты h, которое состоит из d слоёв. Каждый слой представляет собой деревья высотой h/d. Каждое из деревьев является бинарным деревом хешей и имеет описываемую ниже структуру. Листья каждого дерева содержат в себе открытые ключи схемы WOTS+. При этом корни деревьев одного слоя, оказываются подписаны по той же схеме WOTS+, примененной к дереву на старшем(ближе к корню) слое. !Слой, содержащий одно единственное дерево, договоримся нумеровать индексом d-1, индекс каждого последующего слоя будем получать вычитанием единицы. И так до слоя с индексом 0. Листья деревьев нулевого слоя(они же пары ключей схемы WOTS+) имеют значения открытых ключей схем HORST

Key Generation Algorithm ((SK, PK) ← kg(1n)

[править | править код]
    -Сгенерировать два n-битных секретных ключа (SK1, SK2) ∈ {0, 1}n × {0, 1)n
         SK1 используется для псевдослучайной генерации вспомогательных ключей
         SK2 используется для непредсказуемого выбора индексов "гипердерева" и для того, 
             чтобы сделать случайным хеширование сообщения
    - Сгенерировать матрицу n-битных масок с равномерным распределением избыточного размера 
      Q ← {0, 1}p×n, достаточного для использования в схемах WOTS+, HORST и построений 
      деревьев хешей.
    - Осталось сгенерировать значение корня единственного дерева на слое d-1.
      Для этого вычислить специальное значение(семя) с помощью адреса, первого секретного 
      ключа и псевдослучайной функции: SA ← Ka(A, SK1), где A = (d − 1||0||i). 
      Инициализируем значение листьев дерева, поставив им в соответствие значения ключа, 
      вычисленного по схеме WOTS+: pkA ← WOTS.kg(SA, QWOTS+ ). Используя матрицу битовых 
      масок Q, построить бинарное дерево хешей и вычислим значение корня
    - Положить открытый ключ PK1 равным корню "гипердерева"

Signature Algorithm (Σ ← sign(M, SK))

[править | править код]

На входе имеется сообщение M ∈ {0, 1}* и секретный ключ (SK1, SK2,Q) 

    - Вычислить контрольную сумму сообщения D. Для этого нужно сгенерировать псевдослучайное 
      R = (R1, R2) ∈ {0, 1}n × {0, 1}n(R ← E(M, SK2)). 
      Затем, собственно, сгенерировать саму контрольную сумму D ← M(R1, M), используя первые n-бит числа R.
    - Использовать последние n-бит числа R для определения индекса пары ключей схемы HORST i.
    - Вычислить подпись и открытый ключ по схеме HORST:  
      (σH, pkH) ← (D, SAHORST ,QHORST), используя специальное значение(семя)
      SAHORST ←Ka(AHORST, SK1) и матрицу битовых масок, где AHORST = (d||i(0,(d −1)h/d)||i((d − 1)h/d, h/d))

    - Заполнить "гипердерево", на каждом слое(от 0 до d-1) выполняя один и тот же алгоритм: 
      принять значения в листьях за открытый ключ схемы WOTS+, вычислить подпись по схеме WOTS+,
      заполнить узлы деревьев слоя по правилам построения бинарного дерева хешей.
    - Использовать в качестве подпись схемы SPHINCS такую структуру
      Σ = (i, R1, σH, σW,0, AuthA0, . . . , σW,d-1, AuthAd-1), где Auth это вспомогательные данные для
      вычисления корня дерева, начиная с соответствующего листа

Verification Algorithm (b ← vf(M, Σ, PK))

[править | править код]

На входе имеется сообщение M ∈ {0, 1}∗, подпись Σ и открытый ключ PK 

    - Вычислить контрольную сумму сообщения D ← H(R1, M)
    - Вычислить открытый ключ схемы HORTS pkH ← HORST.vf(D, σH, QHORST), используя подпись этой схемы σH.
      Проверить правильность данной подписи. Если она не верна, то не верна и подпись общей схемы SPHINCS
    - Проверить подписи для схем WOTS+ на каждом слое "гипердерева":  
      pkW,0 ← WOTS.vf(pkH или pkW,j, σW,0, QWOTS+), вычисляя корни бинарных деревьев хешей.
    - Проверить совпадение PK1 = Rootd-1. Если равенство верно, то вынести вердикт о правильности подписи

Пример подписи на основе SPHINCS

[править | править код]

На примере SPHINCS-256[7] можно увидеть как можно сочетать параметры схемы SPHINCS для обеспечения требований безопасности(128-бит даже при использовании квантового компьютера), а также требований к размерам подписей и ключей

Примечания

[править | править код]
  1. ↑ Архивированная копия. Дата обращения: 18 мая 2022. Архивировано 5 августа 2010 года.
  2. ↑ National Institute of Standards and Technology. Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms. Federal Register (20 декабря 2016). Дата обращения: 20 ноября 2018. Архивировано 20 ноября 2018 года.
  3. ↑ IBM News room - 2017-11-10 IBM Announces Advances to IBM Quantum Systems & Ecosystem - United States. Дата обращения: 20 ноября 2018. Архивировано 19 ноября 2018 года.
  4. ↑ Квантовые компьютеры и конец безопасности | Блог Лаборатории Касперского. Дата обращения: 20 ноября 2018. Архивировано 20 ноября 2018 года.
  5. ↑ Архивированная копия. Дата обращения: 18 ноября 2018. Архивировано из оригинала 29 декабря 2017 года.
  6. ↑ 1 2 3 4 5 6 7 8 Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O’Hearn. SPHINCS: practical stateless hash-based signatures (англ.) // http://sphincs.cr.yp.to : сайт. — 2015. — 2 February. — P. 6—14. Архивировано 7 февраля 2019 года.
  7. ↑ Архивированная копия. Дата обращения: 18 мая 2022. Архивировано 13 мая 2022 года.

Дополнительная литература

[править | править код]

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/wiki/SPHINCS