Введение

Метод разделения секрета таким образом, чтобы для его восстановления требовалось сотрудничество нескольких сторон, в случаях, когда весь секрет известен всем участникам. Разделение секрета (также называемое разделением секретов) относится к методам распределения секрета между группой лиц таким образом, что ни один отдельный участник не обладает осмысленной информацией о секрете, но при объединении "долей" достаточного количества участников секрет может быть восстановлен. В отличие от небезопасного разделения секрета, которое позволяет злоумышленнику получать больше информации с каждой долей, безопасное разделение секрета работает по принципу "всё или ничего" (где "всё" означает необходимое количество долей). В одной из схем разделения секрета присутствует один дилер и n участников. Дилер предоставляет каждому участнику долю секрета, но участники смогут восстановить секрет из своих долей только при выполнении определенных условий. Дилер обеспечивает это, распределяя доли таким образом, чтобы любая группа из t (порог) или более участников могла совместно восстановить секрет, но ни одна группа, состоящая менее чем из t участников, не могла этого сделать. Такая система называется (t, n)-пороговой схемой (иногда записывается как (n, t)-пороговая схема). Независимо друг от друга, метод разделения секрета был изобретён Ади Шамиром и Джорджем Блэкли в 1979 году.

Важность

Секретные схемы распределения идеально подходят для хранения информации, которая является крайне конфиденциальной и важной. Примеры включают: ключи шифрования, коды запуска ракет и номера банковских счетов. Каждая из этих частей информации должна храниться в строжайшей тайне, поскольку ее раскрытие может иметь катастрофические последствия; однако, также критически важно, чтобы она не была потеряна. Традиционные методы шифрования не позволяют одновременно достичь высокого уровня конфиденциальности и надежности. Это связано с тем, что при хранении ключа шифрования необходимо выбирать между хранением единственной копии ключа в одном месте для максимальной секретности или хранением нескольких копий ключа в разных местах для большей надежности. Повышение надежности ключа за счет хранения нескольких копий снижает конфиденциальность, создавая дополнительные векторы атак; увеличивается вероятность попадания копии в чужие руки. Схемы распределения секретов решают эту проблему и позволяют достичь произвольно высоких уровней конфиденциальности и надежности. Распределение секретов также позволяет распространителю секрета доверять группе в целом. Традиционно, передача секрета группе для хранения требовала бы полного доверия ко всем членам группы. Схемы распределения секретов позволяют распространителю безопасно хранить секрет в группе, даже если не всем членам можно доверять постоянно. До тех пор, пока число предателей не превысит критическое число, необходимое для восстановления секрета, секрет останется в безопасности. Схемы распределения секретов важны в облачных вычислительных средах. Таким образом, ключ может быть распределен по множеству серверов с помощью механизма распределения секретов по порогу. Затем ключ восстанавливается по мере необходимости. Распределение секретов также было предложено для сенсорных сетей, где каналы связи могут быть перехвачены, путем отправки данных в виде долей, что затрудняет задачу перехватчика. Безопасность в таких средах можно повысить, постоянно меняя способ формирования долей.

"Безопасный" против "небезопасного" обмена секретами

Система безопасного распределения секрета распределяет доли таким образом, что любой, у кого меньше *t* долей, не имеет больше информации о секрете, чем тот, у кого 0 долей. Рассмотрим, например, схему распределения секрета, в которой секретная фраза "password" разделена на доли "pa––––––", "––ss––––", "––––wo––" и "––––––rd". Человек, не имеющий ни одной доли, знает только то, что пароль состоит из восьми букв, и, следовательно, должен был бы угадать пароль из 26⁸ = 208 миллиардов возможных комбинаций. Однако человеку, имеющему одну долю, нужно было бы угадать только шесть букв из 26⁶ = 308 миллионов комбинаций, и так далее, по мере того как больше людей вступают в сговор. Следовательно, эта система не является "безопасной" схемой распределения секрета, поскольку игрок с меньшим количеством секретных долей способен упростить задачу получения исходного секрета, не нуждаясь сначала в получении всех необходимых долей. В отличие от этого, рассмотрим схему распределения секрета, где X – это секрет, который необходимо разделить, Pi – публичные асимметричные ключи шифрования, а Qi – их соответствующие закрытые ключи. Каждому игроку J предоставляется {P₁(P₂(…(Pₙ(X))…)), Qⱼ}. В этой схеме любой игрок, обладающий закрытым ключом 1, может снять внешний слой шифрования, игрок, обладающий ключами 1 и 2, может снять первый и второй слои, и так далее. Игрок с меньшим количеством, чем N, ключей никогда не сможет полностью восстановить секрет X без предварительного расшифрования зашифрованного блока с открытым ключом, для которого у него нет соответствующего закрытого ключа – задача, которая в настоящее время считается вычислительно неразрешимой. Кроме того, мы видим, что любой пользователь, обладающий всеми N закрытыми ключами, способен расшифровать все внешние слои и получить X, секрет, и, следовательно, эта система является безопасной системой распределения секрета.

t = 1

t = 1 секретное разделение тривиально. Секрет можно просто предоставить всем n участникам.

1 < t < n

Трудность заключается в создании схем, которые остаются безопасными, но не требуют всех n долей. Когда эффективность использования памяти не является проблемой, тривиальные схемы 1=t=n можно использовать для восстановления секрета любым желаемым подмножествам игроков, просто применяя схему для каждого подмножества. Например, чтобы восстановить секрет s для любых двух из трех игроков – Алисы, Боба и Кэрол – создайте три различные схемы 1=t=n=2 для секрета s, предоставив три набора по две доли Алисе и Бобу, Алисе и Кэрол, а также Бобу и Кэрол.

t принадлежащий любому желаемому подмножеству {1, 2, ..., n}

Представьте, что совет директоров компании хочет защитить свою секретную формулу. Президент компании должен иметь доступ к формуле при необходимости, но в случае чрезвычайной ситуации любые 3 из 12 членов совета директоров смогут совместно разблокировать секретную формулу. Один из способов реализации этого – схема разделения секрета, где t = 3 и n = 15: президенту выдается 3 доли секрета, а каждому члену совета директоров – по одной доле.

Эффективное обмен секретами

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

Схема Шамира

В этой схеме для восстановления секрета можно использовать любые t из n долей. Система основана на идее, что для любого набора из t точек, лежащих на многочлене, можно построить единственный многочлен степени t − 1. Для определения прямой нужны две точки, для полной определенности квадратичной функции – три точки, для кубической кривой – четыре точки и так далее. Иными словами, для определения многочлена степени t − 1 требуется t точек. Метод заключается в создании многочлена степени t − 1, где секрет является первым коэффициентом, а остальные коэффициенты выбираются случайным образом. Затем находятся n точек на этой кривой и каждая из них передается одному из участников. Когда хотя бы t из n участников раскроют свои точки, появляется достаточно информации для построения многочлена степени (t − 1) по этим точкам, при этом первый коэффициент этого многочлена и будет являться секретом.

Схема Блэкли

Две непараллельные линии в одной плоскости пересекаются ровно в одной точке. Три непараллельные плоскости в пространстве пересекаются ровно в одной точке. В более общем случае, любые n непараллельных (n − 1)-мерных гиперплоскостей пересекаются в определенной точке. Секрет может быть закодирован как любая отдельная координата точки пересечения. Если секрет закодирован с использованием всех координат, даже если они случайны, то инсайдер (лицо, обладающее одной или несколькими (n − 1)-мерными гиперплоскостями) получает информацию о секрете, поскольку он знает, что секрет должен лежать на его гиперплоскости. Если инсайдер может получить больше знаний о секрете, чем аутсайдер, то система больше не обладает информационной безопасностью. Если используется только одна из n координат, то инсайдер не знает больше, чем аутсайдер (то есть, что секрет должен лежать на оси x для двухмерной системы). Каждому участнику предоставляется достаточно информации для определения гиперплоскости; секрет восстанавливается путем вычисления точки пересечения гиперплоскостей и последующего выбора заданной координаты этой точки. Схема Блэкли в трех измерениях: каждая доля представляет собой плоскость, а секрет – это точка, в которой пересекаются три доли. Двух долей недостаточно для определения секрета, хотя они предоставляют достаточно информации, чтобы сузить его до линии пересечения обеих плоскостей. Схема Блэкли менее эффективна с точки зрения занимаемого места, чем схема Шамира; в то время как доли Шамира имеют размер, равный размеру исходного секрета, доли Блэкли в t раз больше, где t – пороговое число участников. Схему Блэкли можно усилить, добавив ограничения на то, какие плоскости могут использоваться в качестве долей. Полученная схема эквивалентна полиномиальной схеме Шамира.

Используя китайскую теорему остатка

Китайская теорема об остатках также может быть использована в схемах разделения секрета, поскольку она предоставляет метод однозначного определения числа S по модулю k попарно взаимно простых целых чисел, при условии, что существует k таких чисел. Существуют две схемы разделения секрета, использующие китайскую теорему об остатках: схемы Мигнотта и Асмута — Блума. Это пороговые схемы разделения секрета, в которых доли генерируются путем вычисления остатка от деления на целые числа, а секрет восстанавливается путем решения системы сравнений с использованием китайской теоремы об остатках.

Проактивное обмен секретами

Если игроки хранят свои доли на небезопасных компьютерных серверах, злоумышленник может взломать систему и похитить эти доли. Если изменить секрет не представляется возможным, нескомпрометированные доли (в стиле Шамира) можно обновить. Дилер генерирует новый случайный многочлен с нулевым свободным членом и вычисляет для каждого оставшегося игрока новую упорядоченную пару, где x-координаты старой и новой пар совпадают. Затем каждый игрок складывает старые и новые y-координаты и сохраняет результат как новую y-координату секрета. Все не обновленные доли, накопленные злоумышленником, становятся бесполезными. Злоумышленник сможет восстановить секрет только в том случае, если ему удастся найти достаточно других не обновленных долей для достижения порога. Этой ситуации не должно произойти, поскольку игроки удалили свои старые доли. Кроме того, злоумышленник не сможет получить какую-либо информацию об исходном секрете из файлов обновления, так как они содержат только случайные данные. Дилер может изменить пороговое значение при распространении обновлений, но всегда должен следить за тем, чтобы игроки не хранили устаревшие доли.

Поддающиеся проверке секреты

Игрок может солгать о своей доле, чтобы получить доступ к долям других игроков. Схема проверяемого разделения секрета (VSS) позволяет игрокам быть уверенными, что другие игроки не искажают информацию о содержимом своих долей, с разумной вероятностью ошибки. Такие схемы невозможно вычислить традиционными методами; игроки должны коллективно складывать и умножать числа, не зная, что именно складывается и умножается. Тал Рабин и Майкл Бен Ор разработали систему многосторонних вычислений (MPC), которая позволяет игрокам выявлять нечестность дилера или до одной трети от порогового числа игроков, даже если эти игроки скоординированы "адаптивным" злоумышленником, способным менять стратегии в реальном времени в зависимости от раскрытой информации.

Обмен секретами с компьютерной безопасностью

Недостатком безусловно безопасных схем разделения секрета является то, что хранение и передача долей требуют объема ресурсов памяти и пропускной способности, эквивалентного размеру секрета, умноженному на количество долей. Если размер секрета значителен, например, 1 ГБ, а количество долей равно 10, то акционерам необходимо хранить 10 ГБ данных. Для значительного повышения эффективности схем разделения секрета были предложены альтернативные методы, отказывающиеся от требования безусловной безопасности. Одна из этих техник, известная как "разделение секрета, сделанное коротким", сочетает алгоритм рассеивания информации Рабина (IDA) с разделением секрета Шамира. Сначала данные шифруются случайным ключом с использованием алгоритма симметричного шифрования. Затем эти данные разбиваются на N частей с помощью IDA Рабина. Эта IDA конфигурируется с порогом аналогично схемам разделения секрета, но, в отличие от них, размер полученных данных увеличивается в (количество фрагментов / порог) раз. Например, если порог равен 10, а IDA генерирует 15 фрагментов, общий размер всех фрагментов составит (15/10), то есть в 1,5 раза больше размера исходных данных. В этом случае эта схема в 10 раз эффективнее, чем при непосредственном применении схемы Шамира к данным. Последним шагом в технике "разделение секрета, сделанное коротким" является использование разделения секрета Шамира для создания долей случайного симметричного ключа (обычно порядка 16–32 байт), а затем предоставление каждой стороне одной доли и одного фрагмента. Связанный подход, известный как AONT RS, применяет преобразование "все или ничего" к данным в качестве предварительной обработки перед использованием IDA. Преобразование "все или ничего" гарантирует, что любое количество долей, меньшее порога, будет недостаточно для расшифровки данных.

Другие виды использования и применения

Схема разделения секрета может обеспечить защиту секрета на нескольких серверах и оставаться восстанавливаемой, несмотря на выход из строя нескольких серверов. Распределитель может выступать в качестве нескольких различных участников, распределяя доли секрета между ними. Каждая доля может храниться на отдельном сервере, но распределитель может восстановить секрет, даже если несколько серверов выйдут из строя, при условии, что удастся восстановить хотя бы t долей; однако, злоумышленники, получившие доступ к одному серверу, не смогут узнать секрет, если на каждом сервере хранится менее t долей. Это одна из ключевых концепций проекта Vanish в Университете Вашингтона, где случайный ключ используется для шифрования данных, а сам ключ распределяется как секрет между несколькими узлами в P2P-сети. Для расшифровки сообщения необходимо, чтобы в сети были доступны как минимум t узлов; принцип, лежащий в основе этого проекта, заключается в том, что количество узлов, участвующих в разделении секрета, со временем естественным образом уменьшается, что в конечном итоге приводит к исчезновению секрета. Однако сеть уязвима к атаке Сивиллы, что делает Vanish небезопасной. Любой участник, получивший достаточно информации для расшифровки содержимого в любой момент времени, может скопировать и сохранить X. Следовательно, хотя инструменты и методы, подобные Vanish, могут сделать данные невосстановимыми в пределах собственной системы через некоторое время, невозможно принудительно удалить данные после того, как они были просмотрены злоумышленником. Это одна из основных проблем в области управления цифровыми правами. Распределитель может отправить t долей секрета, все из которых необходимы для восстановления исходного секрета, одному получателю. Злоумышленнику потребуется перехватить все t долей, чтобы восстановить секрет, что сложнее, чем перехватить один файл, особенно если доли передаются по разным каналам связи (например, некоторые через Интернет, некоторые – на компакт-дисках). Для больших секретов может быть эффективнее зашифровать сам секрет, а затем распространить ключ, используя схему разделения секрета. Разделение секрета является важным примитивом в нескольких протоколах для безопасных многосторонних вычислений. Разделение секрета также может использоваться для аутентификации пользователей в системе.