20.04.2021 05:53
ilya_dt 18 869 Источник

Вступление


Схема разделение секрета, ключа или пароля не новая, но во всех спецификациях, которые я встречал есть главный недостаток — доли и сам секрет различимы по структуре или длине. To есть по каждой доле разделяемого секрета можно было сказать это "доля", а не настоящий секрет.


Хотелось бы посмотреть в другую сторону и сделать совершенную схему, в которой


  • восстановить секрет можно только имея $K$ из $N$ долей $(K?N, K,N ?2)$
  • длина доли и секрета была одной и той же
  • у доли не было бы структуры, то есть доля была похожа на случайную последовательность байт
  • каждая доля сама по себе были бесполезные. Более того, количество долей меньших $K$ тоже были бесполезными и не раскрывали искомого секрета
  • длина искомого секрета могла быть любой
  • при утере долей, меньших $K$, можно было разделить секрет на доли заново, а после этого уничтожить оставшиеся доли. Тем самым секрет никогда не будет восстановлен по утерянным долям.

Исследование


В статье на википедии представлены несколько способов по разделению секрета, для моих целей самая практичная и простая из них — пороговая схема $K-N$ Шамира.


Идея крайне проста —


  1. Задается произвольный многочлен $f(x) = a_{K-1}x^{K-1} + a_{K-2}x^{K-2} +..+a_1x + a_0$ коэффициентами $\{a_{K-1}, .., a_0\}$, где $a_0$ является секретом.
  2. Вычисляются N точек $(x_i, f(x_i))$, которые и представляют собой доли ( $x_i ? 0$).


Доли — (1,-2), (2,-1), (3,2), (4,7). Любых 3х долей достаточно, чтобы получить f(0)


Итого, из любых $K$ точек можно составить $K$ линейных уравнений, подставляя $x_i$ и $f(x_i)$ в общий вид многочлена. $K$ линейных уравнений дают однозначное определение $\{a_{K-1}, .., a_0\}$ коэффициентов, где $a_0$ является исходным секретом. Причем из числа точек меньшего $K$, $a_0$ может принимать абсолютно любое значение при степени многочлена $K-1$.


Но работать с рациональными числами и целыми числами мы не можем, по причине того, что зная алгоритм генерирования коэффициентов, можно сузить число возможных варианта секрета, подробнее об этой проблеме тут.


Поэтому мы переходим к вычетам по модулю простого числа $p$. В этом поле $p$ элементов от $0$ до $p-1$. Естественно, выбираем $p ? s$, чтобы наш секрет принадлежал этому полю.


Преимущества


  • Длины секрета и долей примерно равны, если выбираем $p$ близкое к $s$
  • Длины секретов могут быть любыми
  • Можно сколько угодно раз разделить секрет заново, так как "много" многочленов степени $K-1, f(0)=s$
  • По долям, меньших $K$, невозможно восстановить секрет, либо часть его

Проблемы


  1. Для больших длин секретов приходилось бы искать большое простое число, заведомо большее длины секрета, чтобы секрет находился в этом поле.
    Для секрета длиной 8 байт простое число должно быть не меньше 1,8e19.
    Нахождения простого числа, большего заданного $X$ задача нетривиальная. Да и работа с большими числами на практике сложная.
  2. Доля в схеме Шамира это точка с координатам $x$ и $y$. Длина секрета и координаты $y$ доли равны, но где-то нужно хранить координату $x$. Так как мы хотим получить идеальную схему разделения, чтобы длины секрета и ключа совпадали, мы не можем добавить её к нашей доле конкатенацией.

Схема Шамира была самой подходящей для решения мой задачи, поэтому алгоритм chipndale будет основан на ней.


Chipndale


Chipndale разделяет секрет по байтам, то есть секрет должен иметь длину, кратную байту. Так же секрет не может иметь длину меньше 8 байт, так как меньшее число байт является ненадежным секретом само по себе.


В алгоритме задается $maxShares$ — максимальное количество долей, на которое делится секрет — в моей реализации это 5, но на самом деле их может быть и больше.


Ограничение


  • Секрет — последовательность байт длины $L$
  • Длина секрета ? 8 байт
  • Максимально возможное $N=5$ (которое в конкретной реализации можно расширить)

Решение описанных проблем


Решение проблемы №1


Для того, чтобы не работать с большими числами мы сперва разобьем наш секрет на байты, тогда минимальное простое число будет $p=257$, и каждый байт по отдельности разделим по схеме Шамира.


То есть из 256 значений секрета мы получаем 257 значений доли, но тогда доля будет иметь больший размер, чем искомый секрет, что нам не подходит.


Для того, чтобы размерность секрета и доли совпадала мы перейдем от поля вычетов простого числа $p$ к полю Галуа в котором число элементов равно $GF(p^n)$.


Если поле вычетов по модулю простого числа задается простым числом $p$, то поле
Галуа задается числами $p$, $n$ и неприводимым многочленом степени $n$.


Так как деление побайтовое $p^n$ = 256 при p=2, n=8.


С неприводимым многочленом сложнее, их несколько для одних и тех же значений $p$ и $n$. Я выбрал тот, которых используется в AES (п 4.2) — 0x11b.


Таким образом, проблема решена: больше не нужно работать с большими простыми числами и множество значений доли совпадает с множеством значений секрета.


Решение проблемы №2


Для решение второй проблемы в значении функции $f(255)$ сделаем проверочный вектор, который позволит расположить доли в единственном порядке.


Сам код проверки будет иметь длину 4 байта и вычисляться на основании исходного секрета и случайного ключа $csKey$ длины $L-4$.


Рассчитываться $csKey$ будет по следующей формуле


$cs_L = csKey_{L-4}|| hmac\_sha256(S_L,csKey_{L-4})_4$


Индексы показывают длину величины в байтах. От результата функции $hmac\_sha256$ берутся первые 4 байта.


Случайное число $csKey$ нужно для того, чтобы злоумышленник имея $K-1$ долей не мог определить секрет, перебирая всевозможные значения секрета.


Разбиение секрета


  1. Генерируем $K-2$ координаты $y_i$ длины $L$, точек $(x_i,y_i)$, где $x_i = \{1,..,K-2\}$
  2. Секрет будет иметь координаты $(0,s)$
  3. Генерируем ключ $csKey$ длиной $L-4$ байта
  4. Вычисляем контрольную сумму $cs_L = csKey_{L-4}|| hmac\_sha256(S_L,csKey_{L-4})_4$, тем самым получаем точку с координатами $(255,cs)$
  5. Вычисляем оставшиеся $N-(K-1)$ точек c координатами $x=\{K-1,..,N\}$ на основании $K$ точек из 1,2,3 пунктов по формуле Лагранжа.
  6. Проверяем, что любая перестановка по координатам $x=\{1,..,maxShares\}$ сочетаний $C^К_N$, кроме одной, дает неверную контрольную сумму. Это и есть условие однозначного декодирования.

Наглядно картина разделения chipndale выглядит так:



Подробное описание есть в спецификации


Восстановление секрета


Переставляем $K$ из $N$ долей по координатам $x=\{1,..,maxShares\}$, вычисляя $f(0)$ и $f(255)$ по формуле Лагранжа, пока не совпадет контрольная сумма.
Если контрольная сумма совпала, значит вектор $f(0)$ и является искомым секретом.
Если нет таких координат, значит доли неверные или недостаточные.


Восстановить секрет имея число долей, меньших К-1


Если имеется $K-2$ долей, то восстановить секрет невозможно.


Если мы имеем $K-1$ долей, то для восстановления секрета нам потребуется сгенерировать $256^{L-4}$ ключей и для каждого подобрать оставшуюся часть секрета — $256^{4}$, чтобы совпадал код-аутентификации.
Итого имеем, что для атаки грубой силой нужно перебрать $256^{L}$ значений и тогда получим $256^{L-4}$ возможных значения секрета.


То есть сокращение возможных вариантов секрета в 4,2e9 раз.


На самом деле это небольшая цифра, как могло показаться.


Кол-во байт секрета Кол-во значений секрета Кол-во значений секрета, имея K-1 долей
8 256**8 = 1,8e19 256**4 = 4,3e9
16 256**16 = 3,4e38 256**12 =7,9e28
32 256**32 = 1,1e77 256**28 = 2,7e67

В сравнительной таблице видно, что множество вариантов значений секрета хоть и сужается, но не дает практической пользы, так как кол-во вариантов секретов все равно слишком большое.
Поэтому для упрощения можно считать, что отдельные $K-1$ долей являются бесполезными.


Генератор случайных чисел


Для разделения секрета по схеме Шамира или chipndale требуются случайные числа для долей секрета. Если злоумышленник знает алгоритм генерации случайных чисел, то он знает $csKey$, а также $K-2$ доли. Это может быть вектором атаки.


Например, если злоумышленник так же владеет одной К-1 долей тоже, он может перебрать $256^4$ значений и подобрать секрет.


Всегда используйте только надежные источники случайных чисел.


Действия в случае утере доли(ей)


При потере долей таким образом, что осталось менее $K$ частей, можно считать, что секрет утерян полностью без возможности восстановления.


В ином случае у Вас осталось $K$ частей, и нужно


  1. Восстановить секрет из любых оставшихся $K$ долей.
    При утере долей большем либо равным $K$ нужно пересоздать сам секрет и заменить его во всех местах использования.
    При утере менее $K$ долей пересоздавать секрет не нужно.
  2. Разделить секрет на доли заново.
  3. Предыдущие оставшиеся доли обязательно уничтожить

При утере $?K$ долей существует малая вероятность, что, если


  • к злоумышленнику попали $K$ долей
  • злоумышленник знает, что это доли одного секрета
  • злоумышленник знает, что делать с восстановленным секретом
  • злоумышленник воспользовался секретом до того, как Вы пересоздали секрет

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


Заключение


Тем самым мы получили схему деление секрета Chipndale-K-N, в которой


  • секрет и доли неразличимы по структуре, что позволяет правдоподобно отрицать существование реального секрета
  • только $K$ из $N$ участников могут получить первоначальный секрет
  • искомый секрет может иметь любую длину
  • секрет может быть поделен на части сколь угодно много раз в случае утери как-либо из частей.

К недостаткам алгоритма можно отнести, что максимальное теоретически возможное число долей 254. Сложность алгоритма растет пропорционально факториалу максимальному числу долей, т.е. $~maxShares!$, поэтому теоретическое число долей вряд ли возможно.
В мой реализации максимальное число долей равно 5.


Демо


Я создал страницу с реализацией chipndale


https://ilyadt.github.io/chipndale/


Код полностью открытый и доступен в репозитории https://github.com/ilyadt/chipndale/


Сама библиотека покрыта юнит-тестами, а так же есть тестовые вектора для проверки разделения секрета. Например:


{
    "n": 4,
    "k": 2,
    "secret": "b1008f3a39a4466147f26f925bcabbecebc7549a8c2005ce1e176f7e224f2b74",
    "randomCsKey": "1f5e6947af4d06540936e9acdf13ed0c77bae41a54ca92e698271cf3",
    "randomCoordinateVector": [],
    "shares": [
      "3632a9812836077bae41a54ca92e6982227ca01874960883d4617c70d3323f05",
      "a464c3571b9bc4558e8fe035a419043062aaa78567571f5491fb4962dbb50396",
      "2356e5ec0a09854f673c2aeb56fdd65eab1153079fe112195b8d5a6c2ac817e7",
      "9bc817e07dda5909ce086ac7be77de4fe21da9a441ce31e11bd42346cba07bab"
    ]
}

Федерация


Схема разделения chipndale может быть применена как федерация, то есть любая доля может быть поделена на доли.


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


Тогда я делю искомый секрет по схеме SH1,SH2,SH3=Chipndale-2-3(s). SH1, SH2 оставляю себе и храню в разных местах, тем самым я могу воспользоваться секретом самостоятельно. SH3 делю следующим образом — SH3a1, SH3a2, SH3a3, SH3a4 = Chipndale-2-4(SH3) и раздаю доли 4 друзьям, и в случае потери доли мною любые 2 друга вместе со мной восстановят секрет. А также делю SH3b1, SH3b2, SH3b3, SH3b4 = Chipndale-5-3(SH3) и раздаю семье, тем самым в случае утере доли мною, я могу попросить 3 членов семьи восстановить секрет. Причем семья и друзья без меня восстановить секрет не смогут.


Ссылки