Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Совместное использование секрета (также называемое разделением секрета ) относится к методам распределения секрета между группой участников, каждому из которых выделяется доля секрета. Секрет может быть восстановлен только тогда, когда будет объединено достаточное количество долей, возможно различных типов; отдельные акции сами по себе бесполезны.

В одном типе схемы разделения секрета есть один дилер и n игроков . Дилер дает долю секрета игрокам, но только при выполнении определенных условий игроки смогут восстановить секрет из своих долей. Дилер выполняет это, давая каждому игроку долю таким образом, чтобы любая группа из t (для порога ) или более игроков могла вместе восстановить секрет, но никакая группа из менее чем t игроков не могла. Такая система называется ( t , n ) -пороговой схемой (иногда ее записывают как ( n , t )-пороговая схема).

Разделение секретов было изобретено независимо Ади Шамиром [1] и Джорджем Блейкли [2] в 1979 году.

Важность [ править ]

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

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

«Безопасное» или «небезопасное» совместное использование секрета [ править ]

Схема безопасного совместного использования секрета распределяет общие ресурсы таким образом, что любой, у кого меньше t общих ресурсов, имеет не больше информации о секрете, чем кто-либо с 0 долями.

Рассмотрим, например, схему разделения секрета, в которой секретная фраза «пароль» разделена на доли «pa ––––––», «––ss ––––», «–––– wo––», и «–––––– рд». Человек с 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 .

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

  • Каждая доля секрета должна быть не меньше размера самого секрета. Этот результат основан на теории информации , но может быть понят интуитивно. Учитывая t - 1 акций, никакая информация о секрете не может быть определена. Таким образом, итоговая папка должна содержать столько же информации, сколько и сам секрет. Иногда есть обходной путь для этого ограничения, сначала сжимая секрет перед тем, как поделиться им, но это часто невозможно, потому что многие секреты (например, ключи) выглядят как высококачественные случайные данные и, следовательно, их трудно сжать.
  • Все схемы разделения секрета используют случайные биты . Чтобы распределить однобитовый секрет между людьми с порогом t , необходимо t - 1 случайных битов. Для распределения секрета произвольной длины b битов необходима энтропия ( t - 1) × b битов.

Тривиальное разделение секретов [ править ]

t = 1 [ редактировать ]

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

t = n [ редактировать ]

Существует несколько ( t , n ) схем разделения секрета для t = n , когда для восстановления секрета необходимы все общие ресурсы:

  1. Кодировать секрет как двоичное число произвольной длины s . Дайте каждому игроку i (кроме одного) случайное число p i той же длины, что и s . Передайте последнему игроку результат ( s XOR p 1 XOR p 2 XOR ... XOR p n −1 ), где XOR является побитовым исключающим ИЛИ . Секрет в побитовом исключающем ИЛИ всех номеров игроков ( p ).
  2. Кроме того, (1) может быть выполнено с использованием любого линейного оператора в любом поле . Например, вот альтернатива, функционально эквивалентная (1). Выберем 32-битные целые числа с четко определенной семантикой переполнения (т.е. правильный ответ сохраняется по модулю 2 32 ). Во-первых, s можно разделить на вектор из M 32-битных целых чисел, называемый v secret . Затем ( n - 1) игрокам дается вектор из M случайных целых чисел, игрок i получает v i . Оставшемуся игроку дается v n = ( v secret- v 1 - v 2 - ... - v n −1 ). Затем секретный вектор может быть восстановлен путем суммирования всех векторов игрока.

1 < t < n и, в более общем смысле, любое желаемое подмножество {1,2, ..., n} [ править ]

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

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

Эффективный обмен секретами [ править ]

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

Схема Шамира [ править ]

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

Схема Блейкли [ править ]

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

Схема Блэкли менее компактна, чем схема Шамира; в то время как каждая доля Шамира равна первоначальному секрету, акции Блэкли в t раз больше, где t - пороговое количество игроков. Схему Блекли можно ужесточить, добавив ограничения на то, какие самолеты можно использовать в качестве акций. Полученная схема эквивалентна системе полиномов Шамира.

Использование китайской теоремы об остатках [ править ]

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

Активный обмен секретами [ править ]

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

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

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

Поддающийся проверке секретный обмен [ править ]

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

Вычислительно безопасное совместное использование секретов [ править ]

Недостаток безоговорочно безопасных схем совместного использования секрета состоит в том, что для хранения и передачи общих ресурсов требуется объем памяти и ресурсов полосы пропускания, эквивалентный размеру секрета, умноженному на количество общих ресурсов. Если размер секрета был значительным, скажем 1 ГБ, а количество акций было 10, то акционеры должны хранить 10 ГБ данных. Были предложены альтернативные методы для значительного повышения эффективности схем совместного использования секретов за счет отказа от требования безусловной безопасности.

Один из этих методов, известных как тайный обмен расправился , [3] сочетает в себе алгоритм информации рассредоточения Рабин [4](IDA) с секретным делом Шамира. Сначала данные шифруются случайно сгенерированным ключом с использованием симметричного алгоритма шифрования. Затем эти данные разделяются на N частей с использованием IDA Рабина. Эта IDA конфигурируется с порогом, аналогично схемам совместного использования секрета, но в отличие от схем совместного использования секрета размер результирующих данных увеличивается в раз (количество фрагментов / порог). Например, если порог равен 10, а количество фрагментов, созданных IDA, равно 15, общий размер всех фрагментов будет (15/10) или в 1,5 раза больше размера исходного ввода. В этом случае эта схема в 10 раз эффективнее, чем если бы схема Шамира применялась непосредственно к данным.Заключительный шаг в сокращении совместного использования секрета - это использование совместного использования секрета Шамира для создания долей случайно сгенерированного симметричного ключа (который обычно составляет порядка 16–32 байтов), а затем передача одной доли и одного фрагмента каждому акционеру.

Связанный подход, известный как AONT-RS, [5] применяет преобразование « все или ничего» к данным в качестве этапа предварительной обработки к IDA. Преобразование «все или ничего» гарантирует, что любое количество долей, меньшее порогового, недостаточно для расшифровки данных.

Мультисекретный и эффективный (пакетный) обмен секретами [ править ]

Теоретически безопасная схема совместного использования секрета k -of- n генерирует n общих ресурсов, размер каждой из которых не меньше размера самого секрета, что приводит к общему требуемому хранилищу, превышающему размер секрета как минимум в n раз. В совместном использовании нескольких секретов, разработанном Мэтью К. Франклином и Моти Юнгом , [6] множество точек полиномиальных секретов хоста; метод оказался полезным во многих приложениях, от кодирования до многосторонних вычислений. В космическом эффективном совместном использовании секрета, разработанном Абхишеком Парахом и Субхашем Каком , каждая доля составляет примерно долю (k-1) размера секрета. [7]

Эта схема использует повторяющуюся полиномиальную интерполяцию и имеет потенциальные приложения для безопасного распространения информации в Интернете и в сенсорных сетях . Этот метод основан на разделении данных с участием корней многочлена в конечном поле. [8] Некоторые уязвимости связанных схем эффективного использования пространства секретов были указаны позже. [9] Они показывают, что схему, основанную на методе интерполяции, нельзя использовать для реализации схемы ( k , n ) , когда k секретов, подлежащих распределению, по своей природе генерируются из полинома степени меньше k - 1., и схема не работает, если все секреты, которые должны быть разделены, одинаковы и т. д. [10]

Другое использование и приложения [ править ]

Схема совместного использования секрета может обеспечить защиту секрета на нескольких серверах и сохранить возможность восстановления, несмотря на множественные отказы серверов. Дилер может действовать как несколько отдельных участников, распределяя акции между участниками. Каждая акция может храниться на другом сервере, но дилер может восстановить секрет, даже если несколько серверов выйдут из строя, при условии, что они могут восстановить не менее t долей; однако взломщики, которые взламывают один сервер, все равно не знают секрет, пока на каждом сервере хранится менее t общих ресурсов.

Это одна из основных концепций компьютерного проекта Vanish в Вашингтонском университете , где для шифрования данных используется случайный ключ, а ключ распределяется как секрет между несколькими узлами в сети P2P . Чтобы расшифровать сообщение, в сети должны быть доступны по крайней мере t узлов; Принцип этого конкретного проекта заключается в том, что количество узлов, разделяющих секреты, в сети со временем будет естественным образом уменьшаться, что в конечном итоге приведет к исчезновению секрета . Однако сеть уязвима для атаки Сибиллы , что делает Vanish небезопасным. [11]

Любой акционер, у которого когда-либо будет достаточно информации для расшифровки контента в любой момент, может взять и сохранить копию X. Следовательно, хотя инструменты и методы, такие как Vanish, могут сделать данные безвозвратными в их собственной системе через некоторое время, это невозможно. для принудительного удаления данных после того, как злоумышленник их увидел. Это одна из главных загадок управления цифровыми правами .

Дилер может отправить t акций, все из которых необходимы для восстановления исходного секрета, одному получателю. Злоумышленник должен будет перехватить все t общих ресурсов, чтобы восстановить секрет, задача, которая более сложна, чем перехват одного файла, особенно если общие ресурсы отправляются с использованием разных носителей (например, некоторые через Интернет , некоторые отправляются по почте на компакт-дисках ).

Для больших секретов может быть более эффективным зашифровать секрет, а затем распространить ключ с использованием совместного использования секрета.

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

См. Также [ править ]

  • Структура доступа
  • Византийская отказоустойчивость
  • Код стирания - когда восстанавливаемые данные не секрет
  • Гомоморфный обмен секретами - упрощенный децентрализованный протокол голосования.
  • Ортогональный массив - используется для построения некоторых пороговых схем.
  • Разделение секретов с помощью китайской теоремы об остатках
  • Безопасные многосторонние вычисления
  • Обмен секретами Шамира
  • Визуальная криптография

Ссылки [ править ]

  1. Шамир, Ади (1 ноября 1979 г.). «Как поделиться секретом» (PDF) . Коммуникации ACM . 22 (11): 612–613. DOI : 10.1145 / 359168.359176 . S2CID  16321225 . Архивировано (PDF) из оригинала 10 августа 2017 года.
  2. ^ Блейкли, GR (1979). «Защита криптографических ключей» (PDF) . Управление знаниями требований, Международный семинар по (AFIPS) . 48 : 313–317. DOI : 10,1109 / AFIPS.1979.98 . S2CID 38199738 .  
  3. ^ Кравчик, Hugo (1993). Сокращение секретного обмена (PDF) . CRYPTO '93.
  4. ^ Рабин, Майкл О. (1989). «Эффективное распространение информации для обеспечения безопасности, балансировки нагрузки и отказоустойчивости». Журнал ACM . 36 (2): 335–348. CiteSeerX 10.1.1.116.8657 . DOI : 10.1145 / 62044.62050 . S2CID 13166422 .  
  5. ^ Реш, Джейсон; Планк, Джеймс (15 февраля 2011 г.). AONT-RS: сочетание безопасности и производительности в распределенных системах хранения (PDF) . Usenix FAST'11 .
  6. ^ Франклин, Мэтью; Юнг, Моти (4 мая 1992 г.). «Коммуникационная сложность безопасных вычислений (расширенная аннотация)» . STOC '92 Труды двадцать четвертого ежегодного симпозиума ACM по теории вычислений : 699–710. DOI : 10.1145 / 129712.129780 . ISBN 0897915119. S2CID  7486402 .(также доступно на [1] )
  7. ^ Парах, Абхишек; Как, Субхаш (январь 2011 г.). «Эффективное использование секретов для неявной защиты данных». Информационные науки . 181 (2): 335–341. DOI : 10.1016 / j.ins.2010.09.013 .
  8. ^ Парах, Абхишек; Как, Субхаш (сентябрь 2009 г.). «Онлайн-хранилище данных с неявной безопасностью». Информационные науки . 179 (19): 3323–3331. DOI : 10.1016 / j.ins.2009.05.013 .
  9. ^ Сахасрананд, КР; Nagaraj, N .; Раджан, С. (2010). «Как не поделиться множеством секретов». Международный журнал компьютерных наук и информационной безопасности . 8 : 234–237. arXiv : 1001,1877 . Bibcode : 2010arXiv1001.1877S .
  10. ^ Лю, Яньхун; Чжан, Футаи; Чжан, Цзе (февраль 2016 г.). «Атаки на некоторые проверяемые схемы совместного использования нескольких секретов и две улучшенные схемы». Информационные науки . 329 : 524–539. DOI : 10.1016 / j.ins.2015.09.040 .
  11. ^ «Unvanish: восстановление самоуничтожающихся данных» . Архивировано из оригинала на 2012-03-20.
  12. ^ Гупта, Кишор Датта и др. «Обмен секретами Шамира для аутентификации без восстановления пароля». 2020 10-й ежегодный семинар и конференция по вычислительной и коммуникационной технике (CCWC). IEEE, 2020.

Внешние ссылки [ править ]

  • Ubuntu Manpage: gfshare - объяснение секретного обмена Шамиром в GF (2 8 )
  • Описание схем Шамира и Блейкли
  • Патент на использование совместного использования секрета для восстановления парольных фраз PGP (и других?) Патент США 6,662,299
  • Библиография по схемам разглашения секретов
  • Системы подписи кода с использованием Shared Secret на Wayback Machine (архивировано 14 февраля 2008 г.)
  • Беймель, Амос (2011). «Схемы обмена секретами: обзор» (PDF) .