Ошибка при исправлении ключа шифрования

Question

Скажем, у меня есть схема, которая выводит ключ от N различных входов. Каждый из входов может быть не полностью защищен (f.x. плохие пароли), но в совокупности они безопасны. Простой способ сделать это - объединить все входы в порядок и использовать хэш в результате.

Теперь я хочу разрешить ключ-деривацию (или, скорее, дешифрование ключа), только N-1 из входов N. Простой способ сделать это - создать случайный ключ K, сгенерировать N временных ключей из разных N подмножеств ввода, каждый с одним отсутствующим входом (т.е. Hash(input_{1}, ..., input_{N-1}), Hash(input_{0}, input_{2}, ..., input_{N-1}), Hash(input_{0}, input_{1}, input_{3},..., input_{N-1}), ..., Hash(input_{0}, ..., input_{N-2})), затем зашифровать K с каждым из ключей N и сохранить все Результаты.

Теперь я хочу обобщенное решение, где я могу расшифровать ключ, используя K из N входов. Наивный способ расширения вышеприведенной схемы требует сохранения (N) значений, которые быстро становятся неосуществимыми.

Есть ли хороший алгоритм для этого, что не влечет за собой столько хранения?

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

Answer 1

Корректирующие ошибки коды являются наиболее прямым способом решения этой проблемы. Однако они не особенно удобны в реализации.

Лучшим подходом будет использование Reed Solomon Code. При получении пароля в первый раз вы также вычисляете избыточность, требуемую кодом, и храните его. Когда вы хотите пересчитать ключ, вы используете избыточность для исправления неправильных или отсутствующих входов.

Answer 2

Одним из подходов было бы создание чисто случайного ключа (или путем хэширования всех входов, если вы хотите избежать RNG по какой-либо причине), разделить его с помощью пороговой схемы k-of-n и зашифровать каждый делиться с помощью отдельных входов пароля (например, отправлять их через PBKDF2 с 100000 итерациями, а затем шифровать/MAC с AES-CTR/HMAC). Это потребует меньшего объема памяти, чем хранение хэш-подмножеств; примерно N * (размер долей + размер соли + размер MAC)

Answer 3

Вместо того, чтобы просто допускать несколько ошибок из большого количества входов, вы должны разделить входы на группы и разрешить некоторое количество ошибок в каждой группе. Если вы должны были разрешить 4 ошибки из 64 входов, тогда у вас должно было быть 15 249 024 зашифрованных ключей, но если вы разделите это на две группы по 32, что позволит две ошибки для каждой группы, тогда вам нужно будет иметь только зашифрованные ключи 1984 года.

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

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

Answer 4

Для шифрования/создания:

Возьмите N входов. Поверните каждый в блок хорошим/безопасным способом. Используйте Рид Соломон для генерации блоков избыточности М из комбинации блоков N. Теперь у вас есть блоки N + M, из которых вам нужно всего N, чтобы генерировать исходные N блоков.

Используйте блоки N для шифрования или создания защищенного ключа.

Если во-первых, храните зашифрованный ключ и блоки избыточности M. Если второй, сохраните только блоки избыточности M.

Для расшифровки/извлечения:

Take N - R правильно входные блоки, где R = < М. Объединить их с блоками резервирования вы хранящимися для создания оригинальных N блоков. Используйте оригинальные блоки N для дешифрования или создания защищенного ключа.

(Спасибо https://stackoverflow.com/users/492020/giacomo-verticale:. Это, по сути, что он/она говорит, но я думаю, что немного более явным/понятнее)

Answer 5

Shamir's share secret является techinique, который используется, когда вы хотите разделить секрет в нескольких акций так что только комбинация минимальных k частей откроет тайную тайну. Если вы не уверены в правильности инициатора и хотите проверить это, вы используете verifiable secret sharing. Либо основаны на полиномиальной интерполяции