Разделение секрета (также называемое разделением секрета ) относится к методам распределения секрета среди группы таким образом, что ни один человек не владеет какой-либо понятной информацией о секрете, но когда достаточное количество людей объединяет свои «доли», секрет может быть восстановлен. В то время как небезопасное разделение секрета позволяет злоумышленнику получать больше информации с каждой долей, безопасное разделение секрета — это «все или ничего» (где «все» означает необходимое количество долей).
В одном типе схемы разделения секрета есть один дилер и n игроков . Дилер дает игрокам долю секрета, но только при выполнении определенных условий игроки смогут восстановить секрет из своих долей. Дилер достигает этого, давая каждому игроку долю таким образом, что любая группа из t (для порога ) или более игроков может вместе восстановить секрет, но никакая группа из менее чем t игроков не может. Такая система называется ( t , n ) -пороговой схемой (иногда ее записывают как ( n , t ) -пороговую схему).
Разделение секрета было изобретено независимо друг от друга Ади Шамиром [1] и Джорджем Блейкли [2] в 1979 году.
Схемы разделения секрета идеально подходят для хранения информации, которая является высокочувствительной и очень важной. Примерами являются: ключи шифрования , коды запуска ракет и номерные банковские счета . Каждая из этих частей информации должна храниться в строгой конфиденциальности, поскольку их раскрытие может иметь катастрофические последствия; однако также важно, чтобы они не были утеряны. Традиционные методы шифрования плохо подходят для одновременного достижения высоких уровней конфиденциальности и надежности. Это связано с тем, что при хранении ключа шифрования необходимо выбирать между хранением одной копии ключа в одном месте для максимальной секретности или хранением нескольких копий ключа в разных местах для большей надежности. Повышение надежности ключа путем хранения нескольких копий снижает конфиденциальность, создавая дополнительные векторы атак; появляется больше возможностей для попадания копии в чужие руки. Схемы разделения секрета решают эту проблему и позволяют достичь произвольно высоких уровней конфиденциальности и надежности. [3]
Распределение секрета также позволяет распространителю секрета доверять группе «в совокупности». Традиционно, предоставление секрета группе для безопасного хранения требует, чтобы распространитель полностью доверял всем членам группы. Схемы распределения секрета позволяют распространителю надежно хранить секрет в группе, даже если не всем членам можно доверять все время. Пока число предателей никогда не превышает критического числа, необходимого для восстановления секрета, секрет в безопасности.
Схемы разделения секрета важны в облачных вычислительных средах. Таким образом, ключ может быть распределен по многим серверам с помощью порогового механизма разделения секрета. Затем ключ восстанавливается при необходимости.
Разделение секретов также было предложено [ кем? ] для сенсорных сетей , где связи могут быть перехвачены, путем отправки данных в виде общих данных, что усложняет задачу перехватчика. [ нужна цитата ] Безопасность в таких средах может быть повышена за счет постоянного изменения [ как? ] способа построения общих данных. [ нужна цитата ]
Безопасная схема разделения секрета распределяет доли таким образом, что любой, у кого меньше t долей, имеет не больше информации о секрете, чем тот, у кого нет долей.
Рассмотрим, например, схему разделения секрета, в которой секретная фраза «пароль» делится на доли «pa––––––», «––ss––––», «––––wo––» и «–––––––rd». Человек с 0 долями знает только, что пароль состоит из восьми букв, и, таким образом, должен будет угадать пароль из 26 · 8 = 208 миллиардов возможных комбинаций. Однако человеку с одной долей придется угадать только шесть букв из 26 · 6 = 308 миллионов комбинаций, и так далее по мере сговора большего количества людей. Следовательно, эта система не является «безопасной» схемой разделения секрета, потому что игрок с менее чем t долями секрета способен уменьшить проблему получения внутреннего секрета без необходимости сначала получать все необходимые доли.
Напротив, рассмотрим схему разделения секрета, где X — секрет, который будет разделен, P i — открытые асимметричные ключи шифрования, а Q i — их соответствующие закрытые ключи. Каждому игроку J предоставляется { P 1 ( P 2 (...( P N ( X )))), Q j }. В этой схеме любой игрок с закрытым ключом 1 может удалить внешний слой шифрования, игрок с ключами 1 и 2 может удалить первый и второй слои и т. д. Игрок с менее чем N ключами никогда не сможет полностью получить секрет X без необходимости сначала расшифровать зашифрованный открытым ключом блок, для которого у него нет соответствующего закрытого ключа — задача, которая в настоящее время считается вычислительно невыполнимой. Кроме того, мы можем видеть, что любой пользователь со всеми N закрытыми ключами может расшифровать все внешние слои, чтобы получить X , секрет, и, следовательно, эта система является безопасной системой распределения секрета.
Несколько схем обмена секретами считаются информационно-теоретически безопасными и могут быть доказаны, в то время как другие отказываются от этой безусловной безопасности ради повышения эффективности, сохраняя при этом достаточную безопасность, чтобы считаться такими же безопасными, как и другие распространенные криптографические примитивы. Например, они могут позволить защищать секреты с помощью акций с энтропией 128 бит каждая, поскольку каждая акция будет считаться достаточной, чтобы загнать в угол любого мыслимого современного противника, требуя атаки грубой силы среднего размера 2 127 .
Общие для всех безусловно безопасных схем разделения секрета ограничения: [ необходима ссылка ]
Примечание: n — общее количество «игроков», между которыми распределяются акции, а t — минимальное количество игроков, необходимое для раскрытия секрета.
t = 1 разделение секрета тривиально. Секрет может быть просто распространен среди всех n участников.
Существует несколько схем разделения секрета ( t , n ) для t = n , когда для восстановления секрета необходимы все доли:
Трудность [ необходимо разъяснение ] заключается в создании схем, которые по-прежнему безопасны, но не требуют всех n акций.
Когда эффективность пространства не имеет значения, тривиальные схемы t = n могут использоваться для раскрытия секрета любым желаемым подмножествам игроков, просто применяя схему для каждого подмножества. Например, чтобы раскрыть секрет s любым двум из трех игроков Алиса, Боб и Кэрол, создайте три ( ) различных t = n = 2 секретных доли для s , предоставив три набора из двух долей Алисе и Бобу, Алисе и Кэрол и Бобу и Кэрол.
Например, представьте, что совет директоров компании хотел бы защитить свою секретную формулу. Президент компании должен иметь возможность доступа к формуле при необходимости, но в чрезвычайной ситуации любые 3 из 12 членов совета смогут вместе разблокировать секретную формулу. Один из способов сделать это — использовать схему совместного использования секрета с t = 3 и n = 15 , где 3 акции предоставляются президенту, а по одной акции — каждому члену совета.
Тривиальный подход быстро становится непрактичным по мере увеличения числа подмножеств, например, при раскрытии секрета любым 50 из 100 игроков, что потребовало бы создания схем и поддержания каждым игроком различных наборов акций для каждой схемы. В худшем случае рост экспоненциальный. Это привело к поиску схем, которые позволяют эффективно делиться секретами с пороговым числом игроков.
В этой схеме любые t из n акций могут быть использованы для восстановления секрета. Система основана на идее, что вы можете подогнать уникальный многочлен степени t − 1 к любому набору t точек, которые лежат на многочлене. Требуется две точки, чтобы определить прямую линию, три точки, чтобы полностью определить квадратичную кривую, четыре точки, чтобы определить кубическую кривую, и так далее. То есть, требуется t точек, чтобы определить многочлен степени t − 1 . Метод заключается в создании многочлена степени t − 1 с секретом в качестве первого коэффициента и остальными коэффициентами, выбранными случайным образом. Затем найдите n точек на кривой и дайте по одной каждому из игроков. Когда по крайней мере t из n игроков раскроют свои точки, будет достаточно информации, чтобы подогнать им многочлен степени ( t − 1) , причем первый коэффициент будет секретом.
Две непараллельные прямые в одной плоскости пересекаются ровно в одной точке. Три непараллельные плоскости в пространстве пересекаются ровно в одной точке. В более общем смысле, любые n непараллельных ( n − 1) -мерных гиперплоскостей пересекаются в определенной точке. Секрет может быть закодирован как любая отдельная координата точки пересечения. Если секрет закодирован с использованием всех координат, даже если они случайны, то инсайдер (кто-то, обладающий одной или несколькими из ( n − 1) -мерных гиперплоскостей ) получает информацию о секрете, поскольку он знает, что он должен лежать на его плоскости. Если инсайдер может получить больше знаний о секрете, чем посторонний, то система больше не имеет информационной теоретической безопасности . Если используется только одна из n координат, то инсайдер знает не больше, чем посторонний (т. е. что секрет должен лежать на оси x для 2-мерной системы). Каждому игроку дается достаточно информации, чтобы определить гиперплоскость; Секрет раскрывается путем вычисления точки пересечения плоскостей и последующего взятия заданной координаты этого пересечения.
Схема Блэкли менее эффективна с точки зрения пространства, чем схема Шамира; в то время как доли Шамира по размеру равны исходному секрету, доли Блэкли в t раз больше, где t — пороговое число игроков. Схему Блэкли можно ужесточить, добавив ограничения на то, какие плоскости можно использовать в качестве долей. Полученная схема эквивалентна полиномиальной системе Шамира.
Китайская теорема об остатках также может использоваться в разделении секрета, поскольку она предоставляет нам метод однозначного определения числа S по модулю k попарно взаимно простых целых чисел , учитывая, что . Существуют две схемы разделения секрета, которые используют китайскую теорему об остатках, схемы Миньотта и Асмута-Блума. Это пороговые схемы разделения секрета, в которых доли генерируются путем редукции по модулю целых чисел , а секрет восстанавливается путем решения системы сравнений с использованием китайской теоремы об остатках.
Если игроки хранят свои акции на незащищенных компьютерных серверах, злоумышленник может взломать и украсть акции. Если нецелесообразно менять секрет, нескомпрометированные (в стиле Шамира) акции могут быть возобновлены. Дилер генерирует новый случайный полином с постоянным членом ноль и вычисляет для каждого оставшегося игрока новую упорядоченную пару, где x-координаты старой и новой пар одинаковы. Затем каждый игрок складывает старые и новые y-координаты друг с другом и сохраняет результат как новую y-координату секрета.
Все необновленные акции, накопленные злоумышленником, становятся бесполезными. Злоумышленник может восстановить секрет, только если он сможет найти достаточно других необновленных акций, чтобы достичь порога. Такая ситуация не должна происходить, поскольку игроки удалили свои старые акции. Кроме того, злоумышленник не может восстановить какую-либо информацию об исходном секрете из файлов обновления, поскольку они содержат только случайную информацию.
Дилер может изменить пороговое значение при распространении обновлений, но он всегда должен следить за тем, чтобы игроки не оставляли просроченные акции.
Игрок может лгать о своей доле, чтобы получить доступ к другим долям. Проверяемая схема разделения секрета (VSS) позволяет игрокам быть уверенными в том, что никто из других игроков не лжет о содержании своих долей, вплоть до разумной вероятности ошибки. Такие схемы не могут быть вычислены обычным способом; игроки должны коллективно складывать и умножать числа, при этом никто не должен знать, что именно складывается и умножается. Таль Рабин и Майкл Бен-Ор разработали систему многосторонних вычислений (MPC) , которая позволяет игрокам обнаруживать нечестность со стороны дилера или со стороны до одной трети порогового числа игроков, даже если эти игроки координируются «адаптивным» злоумышленником, который может менять стратегии в реальном времени в зависимости от того, какая информация была раскрыта.
Недостатком безусловно безопасных схем разделения секрета является то, что хранение и передача акций требуют объема ресурсов хранения и пропускной способности, эквивалентного размеру секрета, умноженному на количество акций. Если размер секрета был значительным, скажем, 1 ГБ, а количество акций было 10, то акционерам необходимо было бы хранить 10 ГБ данных. Были предложены альтернативные методы для значительного повышения эффективности схем разделения секрета путем отказа от требования безусловной безопасности.
Один из этих методов, известный как сокращенный секретный обмен [ 4], объединяет алгоритм рассеивания информации Рабина [5] (IDA) с секретным обменом Шамира. Сначала данные шифруются случайно сгенерированным ключом с использованием симметричного алгоритма шифрования. Затем эти данные разделяются на N частей с использованием IDA Рабина. Этот IDA настроен с порогом, аналогично схемам секретного обмена, но в отличие от схем секретного обмена размер результирующих данных увеличивается в (количество фрагментов / порог). Например, если порог был равен 10, а количество фрагментов, созданных IDA, было равно 15, общий размер всех фрагментов был бы (15/10) или в 1,5 раза больше размера исходного ввода. В этом случае эта схема в 10 раз эффективнее, чем если бы схема Шамира была применена непосредственно к данным. Последним шагом в сокращенном виде разделения секрета является использование разделения секрета Шамира для создания долей случайно сгенерированного симметричного ключа (обычно размером порядка 16–32 байт) и последующей выдачи одной доли и одного фрагмента каждому держателю.
Связанный подход, известный как AONT-RS, [6] применяет преобразование «все или ничего» к данным в качестве шага предварительной обработки для IDA. Преобразование «все или ничего» гарантирует, что любое количество акций, меньшее порогового значения, недостаточно для расшифровки данных.
Информационно-теоретически безопасная схема разделения секретов k -из -n генерирует n частей, каждая из которых имеет размер не меньше размера самого секрета, что приводит к тому, что общий требуемый объем хранилища будет по крайней мере в n раз больше, чем секрет. В разделении мультисекретов, разработанном Мэтью К. Франклином и Моти Юнгом , [7] несколько точек полиномиальных секретов хоста; метод оказался полезным в многочисленных приложениях от кодирования до многосторонних вычислений . В разделении секретов с эффективным использованием пространства, разработанном Абишеком Парахом и Субхашем Каком , каждая часть примерно равна размеру секрета, деленному на k − 1. [ 8]
Эта схема использует повторную полиномиальную интерполяцию и имеет потенциальные приложения для безопасного распространения информации в Интернете и в сенсорных сетях . Этот метод основан на разбиении данных, включающем корни полинома в конечном поле. [9] Некоторые уязвимости связанных схем эффективного использования пространства для разделения секретов были указаны позже. [10] Они показывают, что схема, основанная на методе интерполяции, не может использоваться для реализации схемы ( k , n ) , когда k секретов, которые должны быть распределены, по сути генерируются из полинома степени меньше k − 1 , и схема не работает, если все секреты, которые должны быть разделены, одинаковы и т. д. [11]
Схема разделения секрета может защитить секрет на нескольких серверах и оставаться восстанавливаемым, несмотря на множественные сбои сервера. Дилер может действовать как несколько отдельных участников, распределяя акции среди участников. Каждая акция может храниться на другом сервере, но дилер может восстановить секрет, даже если несколько серверов выйдут из строя, если он сможет восстановить по крайней мере t акций; однако взломщики, которые взломают один сервер, все равно не узнают секрет, пока на каждом сервере хранится меньше t акций.
Это одна из основных концепций, стоящих за компьютерным проектом Vanish в Вашингтонском университете , где случайный ключ используется для шифрования данных, и ключ распространяется как секрет по нескольким узлам в сети P2P . Чтобы расшифровать сообщение, должны быть доступны по крайней мере t узлов в сети; принцип этого конкретного проекта заключается в том, что количество узлов, разделяющих секрет, в сети будет естественным образом уменьшаться с течением времени, поэтому секрет в конечном итоге исчезнет . Однако сеть уязвима для атаки Сивиллы , что делает Vanish небезопасным. [12]
Любой акционер, у которого когда-либо будет достаточно информации для расшифровки контента, в любой момент может взять и сохранить копию X. Следовательно, хотя инструменты и методы, такие как Vanish, могут сделать данные невосстановимыми в их собственной системе через некоторое время, невозможно принудительно удалить данные после того, как их увидел злонамеренный пользователь. Это одна из главных загадок управления цифровыми правами .
Дилер может отправить t акций, все из которых необходимы для восстановления исходного секрета, одному получателю. Злоумышленнику придется перехватить все t акций, чтобы восстановить секрет, что сложнее, чем перехват одного файла, особенно если акции отправляются с использованием разных носителей (например, некоторые через Интернет , некоторые по почте на компакт-дисках ).
Для больших секретов может быть эффективнее зашифровать секрет, а затем распространить ключ с помощью обмена секретом.
Разделение секрета является важным примитивом в нескольких протоколах для безопасных многосторонних вычислений . Разделение секрета также может использоваться для аутентификации пользователей в системе. [13]
