Когда надо соображать на троих?

Что бы ответить на это вопрос необходимо построить некоторый идеальный мирок, со следующими определениями и положениями:
ТермоРектальныйКриптоАнализ ^[1] (ТРКА). — процесс который может применить Злоумышленник к НКИ, в результате НКИ сообщает ключ. Главное ограничение этого процесса, что он может применяться только при непосредственном контакте Злоумышленника и НКИ. Если Злоумышленник может представит офферту, то нет гарантии что НКИ сообщит ключ шифрации.
Информационная система (ИС) — некоторый программный комплекс, который содержит в себе защищенную информацию. Информация зашифрована надежным алгоритмом. ИС может быть скопирована злоумышленником в полном объеме.
Ключ, ключ шифрации — достаточно длинная случайная битовая последовательность. Длина данной последовательности определяется алгоритмом шифрации ИС.
Злоумышленник — субъект пытающийся получить доступ до зашифрованной информации в ИС. Злоумышленник знает все об ИС кроме: ключа шифрации информации и самой защищенной информации.
Носитель ключевой информации (НКИ) — некоторый субъект который вводит в ИС ключ. С помощью этого ключа, и только с помощью него! защищенная информация может быть получена из ИС.

Теперь населим на мир персонажами.
Директор некоторый субъект который владеет защищаемой информацией. Директор не любит работать и часто зависает на Канарах. Поэтому он нанял системного администратора Васю и сделал его НКИ.
Вася каждое утро включает сервер и вводит ключ и все нормально.
Сразу оговоримся, варианты хищения ключей из ИС типа: охлаждение модулей памяти азотом и переносом их в dump устройство для последующего поиска ключа в памяти. Или варианта подключения через pci/pci-е шину dumper-а который в режиме bus master сольет оперативную память на внешнее устройство для анализа. Вася не дурак в его сервере есть контроль за отворачиванием 100 винтов на корпусе, любой чих и сервер забывает все.
Но Вася в глубине душе знает что как только ему покажут устройство для ТРКА то он расскажет все ключи которые знает и не знает.
А вот директор боится другого, что Васю переедет рельсовоеэлектродижущие транспортное средство — трамвай. И Васина голова отделится от туловища и тут жидкий азот для замораживания уже не поможет. Поэтому директор обязал Васю записать ключ на бумажку и положить его в конверт, а конверт положить в сейф. Кажется что жизнь то налаживается!
Но Злоумышленник хитрец! Он заказывает маски-шоу и сейф в котором лежит конверт, в котором лежит бумажка, на которой написан ключ тю-тю и Злоумышленник теперь празднует победу.

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

Хотя Директор и любит отдыхать на Канарах, он решает разделить ключ между сотрудниками своей мега-контры. Поэтому принимает на работу одного олимпийский бегуна Петю, и неоднократного победителя в MotoGP мотогонщика Марчелло. И инструктирует их: «Как только на горизонте появляется маски-шоу Петя бежит сломя голову налево, а Марчелло что есть дури гонит на право до канадской границы.»
И теперь каждое утро Вася, Петя и Марчелло вводят свои ключи в ИС и ИС работает.Жизнь опять насладилась!
Даже не потребовалось вносить серьезных доработок в ИС. Как известно функция XOR (исключающее ИЛИ) является абсолютно надежной функций шифрования при равенстве длинны ключа и данных. Подобную схему формирования ключа KeyM для шифрования можно изобразить так:

Вася заканчивает университет и подсказал что надо не просто разделить ключ на троих, а ввести некоторый изменяемый ключ K0 который позволил менять ключи Васи, Пети и Марчелло без изменения мастер ключа. Т.к если поменять мастер ключ то надо перекодировать терабайты информации в ИС.
Не большое примечание для изобретателей велосипедов: не надо пытаться заменить XOR на суммирование, конкатенацию строк или еще какие доморощенные функции! XOR это 100% надежность!
И вновь кажется что жизнь то налаживается!

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

Как улучшить данную систему? Что можно противопоставить планам дьявола на счет Марчелло? И каково может быть решение подобной задачи?
Решение довольно простое, но с некоторыми ограничениями, а в чем то может наоборот улучшениями.
Вместо XOR необходимо использовать так называемую мажоритарную функцию ^[2]

Ее смысл таков что она возвращает значение равное наибольшему количеству бит на входе. Вот ее таблица истинности для 3-х входов:

И вот ее свернутая таблица истинности для 5 входов:

Если взглянуть на рисунок рисунок ^[3] то видно что в логике работы ИС не сложно будет заменить в нем функцию XOR на мажоритарную функцию. Но Дьявол был хитер и противопоставил нам законы математики и вот в чем ответный шаг дьявола.
Если взглянуть на схему из 3-х ключей Key1, Key2, Key3 и формирования итогового ключа KeyM, то видно

Наша схема не работает. Чуть позже поясню почему Key3 есть инверсия Key1, Key2. Для нашей схемы на 3-х, потеря или ошибка в одном из ключей приводит к тому что KeyM не может быть получен. В чем тут ошибка? На самом деле мы внесли не одну ошибку, а целых две! Изначально у нас было 3 ключа, один мы сделали «ошибочным» — Key3, а потом еще один ключ сделали ошибочным! В итоге у нас 1 — корректный ключ и 2 — не корректных ключа. Ясно что мажоритарная функция даст не корректный ключ в результате.
Для нашей схемы должно соблюдаться следующее правило:
что 50% от количества ключей должно быть строго больше чем 2 (1 — изначально ошибочный, 1 — введенный ошибочно)
для нашего случая минимальное количество ключей это 5.
Чуть ниже табличное объяснение варианта на 5 ключей будет показано.

Сейчас необходимо вернутся к вопросу что это за ключ Key3 и может быть возникшему вопросу «Почему это у вас Key1, Key2 равны да они еще равны и KeyM ?!?!»
Идея проста и не замысловата смотрим на рисунок

Уникальные ключи очень легко генерируются: необходимо просто циклически сдвинуть каждый битовый столбец и вау-ля у вас 5 различных ключей которые действительно формируют корректный KeyM. Количество сдвигов и алгоритм сдвига может быть любым главное что бы он перемешивал биты в столбцах.

Если теперь допустить ошибки, то получим что то типа:

Полные варианты переборов публиковать не буду, их легко получить из рисунка ^[4].

Может мы не смогли сообразить на 3-х, но получили систему на 5-х. Есть еще хакерский ход, систему на 5-х можно сделать системой на 4-х, но где 5-ым будет сервер с ИС. Т.е. один из ключей мы можем хранить непосредственно на сервере.
В итоге мы получили некоторую систему которая устойчива к потере одного бойца. Для больших чисел участников система уже справляется с потерями и 2-х и 3-х участников. Но самое главное, пока злоумышленник не получит в сове распоряжение тела и мозги ^[5] 50% НКИ у него нет шансов.

Не знаю почему, но данная система защиты не применяется. По крайней мере мне не попадались публичные варианты реализации такой системы. Удобство такой системы перевешивают сложности ее реализации и  возможны  очень красивые системы безопасности.

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

Или делаем что то похожее на
iwlist scan | grep EESID | majority_decrypt
И вы уже довольно не плохо привязались к местности работы /запуска своего скрипта.

P.S. Когда статья публиковалось в черновиках, мне показалось и рассказал какой то секрет или чей то патент. По первой части я не носитель подобных секретов, а по второй базу патентов еще не изучал.

Автор: Cobolorum

Источник ^[6]