ПРИМЕНЕНИЕ ХЭШ-ФУНКЦИЙ ДЛЯ СХЕМЫ РАЗДЕЛЕНИЯ СЕКРЕТА, ОСНОВАННОЙ НА ЛАТИНСКОМ КВАДРАТЕ

Аннотация

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

Основные определения

Введём некоторые определения, которые будут использованы в работе.

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

Латинский квадрат порядка n – квадратная матрица размером n x n, элементы которой принадлежат множеству M = {1, 2, ..., n}, причем каждое число из M встречается ровно один раз в каждой строке и в каждом столбце.

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

Критическое множество латинского квадрата – частичный латинский квадрат, который может быть расширен до полного квадрата единственным образом. Если удалить какой-нибудь элемент из такого критического множества, то свойство однозначного восстановления теряется.

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

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

Введение

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

Очень важно эффективно организовать способ разделения секрета. Однако то, каким образом представить разделенный секрет, важно не меньше. Ведь если нам удастся узнать секрет полным перебором, то тогда мы сможем обойти схему разделения секрета и будет не важно, насколько она хороша. Желательно также сделать секрет одновременно и коротким, и сложным для обнаружения. Подходящим решением для реализации такой схемы может послужить латинский квадрат. Например, существует 10³⁷ различных латинских квадратов степени 10. Для постороннего субъекта становится достаточно сложно обнаружить секрет из-за огромного количества вариантов. Можно даже сделать более эффективно: вместо полного латинского квадрата раздать участникам части его критического множества. И, если какая-то часть участников соберется, и они смогут сформировать критическое множество, то исходный латинский квадрат и, следовательно, секрет смогут быть восстановлены.

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

1) В [1] схема не является совершенной, то есть каждая часть участника содержит долю информации о секрете.

2) В [2] схема является совершенной, но не является ни идеальной, ни универсальной. Каждому участнику необходимо иметь свою уникальную часть для того, чтобы быть в составе той санкционированной группы, к которой он принадлежит.

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

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

Свойства криптографических хэш-функций

Ниже представлены общие свойства, которыми должна обладать хэш-функция:

1. При подаче в хэш-функцию строки произвольной длины, на выходе должна быть строка фиксированной длины.
2. При подаче сообщения в хэш-функцию, значение h(x) должно вычисляться достаточно быстро.
3. Если дано хэш-значение y, то должно быть невозможно найти такое x, что h(x)=y. То есть h – стойкая к восстановлению прообраза функция
4. Если дана пара входного и выходного значений (x,y) для хэш-функции, то должно быть невозможно найти такой прообраз x¢, что x¢ ¹ x, но h(x) = h(x¢) = y. Это свойство называется стойкостью к восстановлению второго прообраза.
5. Если даны две разные входные строки x, x¢ и (x ¹ x¢), то должен быть невозможен случай, что h(x) = h(x¢). Это свойство стойкости к коллизиям.

«Подгон» хэш-значения и атака Нострадамуса

Итеративные хэш-функции подвержены атакам методом «подгона» и атакам Нострадамуса. Эти атаки используют тот факт, что несложно найти промежуточные хэш-значения, которыми можно заменить подлинные блоки сообщения с помощью итеративного применения функции сжатия, и сгенерировать аналогичный исходный хэш h.

Первым шагом в реализации атаки является построение большого числа хэш-значений первого уровня: h₁₁, h₁₂, …, h1w. Вторым шагом - построение промежуточных хэш-значений второго уровня: h₂₁, h₂₂, …, h_2w/2 таким образом, что соблюдаются следующие условия:

• существует сообщение m₁₁ такое, что C(h₁₁, m₁₁) = h₂₁
• существует сообщение m₁₂ такое, что C(h₁₂, m₁₂) = h₂₁
• существует сообщение m₁₃ такое, что C(h₁₃, m₁₃) = h₂₂
• существует сообщение m₁₄ такое, что C(h₁₄, m₁₄) = h₂₂

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

Рисунок 1. Дерево промежуточных хэш-значений

Мы утверждаем, что можем предсказать событие, которое случится в будущем, предоставляя хэш-значение предсказания. После того, как мы узнаем результат, необходимо сформировать сообщение следующим образом:

M = (Префикс || M* || Суффикс),

где Префикс - то, что было заявлено нами как известное;

М* – блок сообщений, который связывает Префикс с любым из хэш-значений первого уровня;

Суффикс – оставшиеся блоки сообщений, которые связывают М* с конечным хэш-значением.

Схема разделения секрета

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

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

В 1979 Ади Шамир предложил (t+1, n) пороговую схему, в которой секрет разделяется на части и распределяется между n участниками, где любая группа числом t+1 или более может восстановить секрет.

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

Применение хэш-функций к латинским квадратам

Для получения хэш-значения секретного латинского квадрата порядка 10, нам необходимо 81 число (последнюю строку и столбец хранить не обязательно). Будем использовать хэш-функцию MD5, поступив следующим образом. Для сохранения одной ячейки будем использовать тройку чисел: (i, j, k), обозначающие строку, столбец и элемент соответственно. Двигаясь слева направо и сверху вниз обойдем все ячейки, содержащие значения, конкатенируя в строку тройки, их обозначающие.

Продемонстрируем на конкретном примере. Пусть у нас имеется латинский квадрат, изображенный на рисунке 2. Выпишем тройки, обозначающие ячейки: (0, 0, 0), (0, 1, 1), (0, 2, 2), (0, 3, 3), (0, 4, 4), …, (8, 8, 6).

Рисунок 2. Пример латинского квадрата порядка 10

В результате конкатенации получим строку:

«00001102203304405506607708810111212313414515616717818920221322423524625726 827928030331432533634735836937038140441542643744845946047148250551652753854 955056157258360661762863964065166267368470771872973074175276377478580881982 0831842853864875886»

Применим хэш-функцию к этой строке и получим хэш сообщения: «43d5f9ed347518f5f3f81f24492cd4ac».

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

Построение идеальной (t + 1, n) пороговой схемы

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

Во-первых, случайно сгенерируем участникам части более или менее одинакового размера с хэш-значением. Затем, выделим различные санкционированные подмножества такие, что каждое подмножество состоит из (t + 1) или более различных участников.

Пусть N – размер структуры доступа, то есть общее число санкционированных подмножеств: N = C (n, t + 1) + C (n, t+2) + … + C (n, n),

где

Таким образом нам необходимо иметь N сообщений для N санкционированных подмножеств.

У каждого участника есть часть и любая комбинация санкционированной группы породит одно из Nсообщений. Следующим шагом является «подгон» хэш-значений этих N сообщений к итоговому хэш-значению с помощью построения связывающих сообщений.

Предположим, что санкционированная группа состоит из участников P₁, P₂, …, P_bи их части m₁, m₂, …, m_bв свою очередь являются отдельными частями сообщения M. Когда они соберутся вместе, они смогут сформировать закрытое сообщение M_priv = m₁ || … || m_b и найти соответствующее связывающее открытое сообщение M_pub, как показано на рисунке 3. Затем они смогут восстановить секрет g, применяя хэш-функцию к M_priv || M_pub, то есть f(M_priv || M_pub) = h.

Рисунок 3. Сообщение M и его части.

В атаке Нострадамуса нам необходимо следующее:

1. Построить огромное дерево промежуточных хэш-значений, которые будут вести к итоговому хэш-значению h.

2. После того, как результат известен, необходимо найти сообщение, связывающее его с одним из хэш-значений первого уровня.

Но в нашем случае этого делать не нужно, так как мы уже знаем хэш-значения этих N сообщений. Это снижает затраты на вычисления во много раз.

Для любого сообщения M_priv, полученного комбинацией частей участников санкционированной группы, есть соответствующее сообщение M_pub в дереве хэш-значений. Их соединение приведет нас к итоговому хэш-значению. Таким образом у нас есть (t + 1, n) пороговая схема, построенная с помощью техники «подгона» хэш-значения. Связывающие сообщения могут храниться в месте, доступном свободно для любого из участников. Когда любая группа участников числом t + 1 или более соберется вместе, они смогут использовать соответствующее связывающее сообщение и свои части для восстановления секрета.

Свойства предложенной схемы:

• Схема совершенна. Одно из основных свойств криптографических хэш-функций – это их случайность. Имея сообщение, мы не сможем получить никакой информации о его хэш-значении. Таким образом исключается вероятность обнаружения частичной информации кем бы то ни было из участников. Когда все участники соберутся вместе, они смогут восстановить секрет, применяя хэш-функцию f к сообщению M = M_priv || M_pub. Чтобы поддержать необходимый уровень безопасности, длина каждой части должна быть как минимум равна длине хэш-значения. С другой стороны, увеличение длины части не увеличивает уровень безопасности. Поэтому желательно иметь случайно сгенерированные части, длиной примерно равной хэш-значению. Это будет выполнятся в случае, если сообщение сгенерировано случайно, что обеспечивает совершенную схему, потому что если отсутствует хоть один из участников, то его часть не сможет быть восстановлена и не удастся получить никакой информации о самом секрете.
• Схема идеальна. Каждый участник имеет часть, равную длине хэш-значения.
• Быстрое восстановление секрета. Значение хэш-функции вычисляется достаточно быстро, что обеспечивает быстрое восстановление частичного латинского квадрата и, следовательно, полного.
• Отсутствие критических множеств. С использованием новой схемы отсутствует необходимость в поиске критических множеств. Это делает схему более эффективной и контролируемой.

Пример полученной схемы

Возьмем (2, 3)-пороговую схему.

Пусть m₁, m₂, m₃ части участников P₁, P₂, P₃. Тогда структура доступа состоит из четырех подмножеств, как показано на рисунке 4.

 будут связывающими сообщениями, доступными публично.

Рисунок 4. Пример (2, 3)-пороговой схемы.

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

Предположим, мы знаем, что P₂, P₃ – члены одной семьи или хорошие друзья и мы не хотим, чтобы у них была возможность восстановить секрет. Тогда общая (2, 3)-пороговая схема не будет работать. Но для нашего случая, мы можем просто пропустить создание сообщения .

Построение проверяемой схемы

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

Пусть f и g – криптографические хэш-функции и M – такое сообщение, что f(M) = s, где s – разделенный секрет. Дилер разделяет сообщение M на части m₁, m₂, …и распределяет их между участниками. Затем он публикует хэш-значения этих частей с использованием функции g в качестве проверочных ключей (g₁, g₂, …).

Участник i проверяет свою часть, применяя функцию . Если все участники подтверждают, что, подавая на вход функции g свою часть, они получают ключ g_n, опубликованный дилером, то мы делаем заключение, что были розданы правильные части. Аналогично, когда участники вернут свои части, дилер может проверить их таким же образом.

Как видно выше, мы используем две хэш-функции g и f. Хэш-функция g используется для того, чтобы сделать схему проверяемой. Хэш-функция f используется для восстановления секрета: f(M). Участнику i, возможно, удастся скрыть свою настоящую часть, если он найдет такое сообщение , что . Однако, если gустойчива к коллизиям, этого достичь достаточно трудно, и схема является безопасной.

Заключение

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

Список литературы

1. J.A. Cooper, D. Donovan, and J. Seberry. Secret sharing schemes arising from Latin squares. Bulletin of the ICA, 12:33–43, 1994.

2. G. Chaudhry and J. Seberry. Secret sharing schemes based on room squares. In Proc. of DMTCS’96 - Combinatorics, Complexity and Logic, pages 158–167, 1996.