Криптографические алгоритмы

Recovery mode Разработка собственного алгоритма симметричного шифрования на Php

17.07.2020 02:15:28 |

Автор: admin

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

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

Собственно, исходный код класса можно посмотреть здесь, а потестировать можно тут

Итак, задача (данного исследовательского эксперимента, так его назовем) стояла следующая:

Разработать собственный алгоритм обратимого шифрования, притом что:

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

Поехали.

Для разработки было выбрано симметричное шифрование.

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

Описываемый здесь алгоритм более похож на поточный шифр, хотя не является им в чистом виде.
Задумывая реализацию алгоритма, в самых общих чертах было понимание, что секретный ключ должен быть лишь одним из элементов финального аккорда в симфонии шифрования, но не самим этим аккордом. То есть в идеале, говоря образно, каждое сообщение должно по хорошему как бы само шифровать себя, а ключ должен быть лишь некой стартовой точкой этого алгоритма, если хотите, неким инициализирующим вектором.
Основная идея ~~прелесть~~ получившегося алгоритма заключается в том, что для каждого акта шифрования не используется один и тот же секретный ключ, а генерируется функция обхода исходного ключа, так называемая сигнатура пути обхода (pathKeySignature в коде), причем функция зависит от нескольких аргументов. А именно от сложной комбинации sha-512 хешей соли приложения, исходного сообщения, уникального идентификатора uniqid, а также от хешкодов отправителя и получателя сообщения.
Что такое сигнатура обхода ключа на пальцах? Если упростить, это фактически алгоритм обхода ключа. Например, берем первый символ ключа, затем 14-ый, затем 22-ой, затем 37-ой, затем 49-ый и т.д. Каждый новый такой обход уникален (в силу уникальности генерируемого pathKeySignature).
Кроме того, в алгоритм внесены элементы двухфакторного шифрования (более подходящего термина не нашел, речь идет о коротких пин-паролях у отправителя и получателя, подробнее ниже по тексту). Далее, непосредственно ~~"под капотом"~~ используется обычный xor-метод.

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

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

Предварительно магия начинается здесь.

private function attachKey($message, $salt)    {        return md5(hash('sha512', $message . uniqid() . $salt) . hash('sha512', $salt));    }    private function pathKeySignature($user_code_1, $user_code_2, $attach_key)    {        return hash('sha512', $user_code_1 . $attach_key . $user_code_2);    }

Собственно, наличие md5 хеш-функции может поначалу немного смутить, но этот элемент алгоритма отвечает лишь только за внесение хаотичности, лавинности изменений (как и sha512) в генерируемый attachKey. Функция uniqid отдает нам уникальный идентификатор, что по итогу позволяет шифровать одно и то же исходное сообщение каждый раз новым шифром, что в конечном счете гуд. Зачем так заморачиваться? Представьте, что вы разрабатываете свой месседжер с шифрованием. Шифрование одних и тех же сообщений одним и тем же конечным шифром если не прямая уязвимость, то явный шаг в ее сторону. Почему? Как правило, в данном контексте пользователи обмениваются весьма однотипным набором данных, из серии "привет!", "я понял", "ок", "скоро буду", "как дела?". Допустим, к примеру, у нас такой месседжер. Канал шифрования установлен, пользователь 1 отправил пользователю 2 шифрованное сообщение "0372985dee", пользователь 2 прочел сообщение и через 5 секунд ответил "0372985dee" обратно. Что зашифровано там? Ответ почти очевиден.
Это было лирическое отступление на тему уместности uniqid, возвращаемся к коду.

Магия продолжается здесь. Собственно, здесь в методе cipher происходит непосредственно обход ключа посредством сигнатуры $path_key_signature, а метод byteShifting дополнительно вносит хаотичность в генерируемый шифр посредством добавления различных сдвигов в определенных границах.

private function cipher($path_key_signature, $message, $generateKey)    {...        for ($i = 0; $i < count($message); $i++) {            if ($sign_key >= self::hash_length) $sign_key = 0;            $key_code_pos = hexdec($path_key_signature[$sign_key]);            $cur_key_pos = $cur_key_pos + $key_code_pos;            if ($cur_key_pos >= $key_length) {                $cur_key_pos = $cur_key_pos - $key_length;            }            $shifted_key_symbol = $generateKey[$cur_key_pos];            // byte shifting            $shifted_key_symbol = $this->byteShifting($i, $shifted_key_symbol);            $shifter = $this->mb_ord($message{$i}) ^ $this->mb_ord($shifted_key_symbol);            $cipher_message .= $this->mb_chr($shifter);            $sign_key++;        }        return $cipher_message;    }

Непосредственно в публичном методе шифрования не так много интересного, ибо все интересное а ля создание присоединяемого хеша attachKey и генерация пути обхода pathKeySignature описаны выше. Разве что, стоит отметить, что к выходящему наружу в незащищенный канал шифру конкатенируется $attach_key

public function codeMessage($message, $generateKey, $user1_pass, $receiver_hashcode)    {        $sender_hashcode = $this->sender_hashcode($user1_pass);        $attach_key = $this->attachKey($message, $this->salt);        $path_key_signature = $this->pathKeySignature($sender_hashcode, $receiver_hashcode, $attach_key);        $result_cipher = $this->cipher($path_key_signature, $message, $generateKey) . $attach_key;        $result_cipher = base64_encode($result_cipher);        return gzencode($result_cipher, 9);    }

Возможно, возникнет резонный вопрос. Почему бы не ограничиться в функции пути обхода просто одним attachKey, для чего добавлять туда хешкоды отправителя и получателя? Ответ находится тут же, "рядом" attachKey расположен фактически на виду в создаваемом шифре, и зная его, не составляет труда реконструировать последовательность прохождения ключа при шифре. Сам секретный ключ это, разумеется, напрямую восстановить не даст, но сведет на нет всю идею "рандомизации" ключа. Поэтому, нужен дополнительный фактор, которым являются хешкоды получателей. Они представляют собой своего рода второй секретный элемент алгоритма помимо ключа. Этакое своего рода двухфакторное шифрование.

Метод decodeMessage детально рассматривать не будем, он практически тривиален, если учитывать полную симметричность с методом шифрования только в обратной последовательности.

Алгоритм выглядит вполне законченным, по крайней мере для некоего теоретического эксперимента.
Плюсы:

Относительно быстр по скорости шифрования/дешифрования (об этом ниже)
Прост и понятен
Открыт для изучения и улучшения, ибо опенсорс

Минусы:

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

В двух словах по поводу тестирования.
По скорости работы алгоритма относительно быстр (разумеется, все относительно и познается в сравнении, речь о скорости шифрования в рамках высокоуровнего яп вообще и в рамках php в частности). 2 мегабайта рандомного текста было зашифровано и расшифровано за 4 секунды, использовался при этом php 7.2. Система: Intel Core i7-8700 CPU @ 3.20GHz 12, параллельно еще работал браузер с кучей вкладок и виртуальная машина. Резюме скорость шифрования ~ 1 мб/сек на среднестатистическом железе на php7.0 и выше.

Подробнее..

Категории: Информационная безопасность , Алгоритмы , Php , Криптография , Шифрование данных , Симметричное шифрование , Криптографические алгоритмы , Безопасность веб-приложений

Из песочницы Задача о ранце в криптографии (Knapsack problem in cryptography)

23.11.2020 00:11:51 |

Автор: admin

Задача о рюкзаке (или Задача о ранце) в криптографии (англ. Knapsack problem) это задача, на основе которой американские криптографы Ральф Меркл и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом.

Далее в программе

Формулировка задачи о рюкзаке (+почему рюкзак?)
Легкая и трудная проблемы
Примеры
История

Что такое шифрование с открытым ключом?

Для криптографии с открытым ключом требуется два ключа.

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

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

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

Хотя это кажется малополезным, если вы пытаетесь сохранить что-то в секрете!

Первый общий алгоритм с открытым ключом использовал алгоритмом ранца.

Исходя из определения систем с открытым ключом, чтобы успешно шифровать (и расшифровать) сообщение нужны два ключа. Легальный получатель сообщения знает секретный ключ $inline$А$inline$, отправитель же владеет другим открытым ключом $inline$B$inline$.

Что делать, если злоумышленнику стал известен открытый ключ?

Есть ответ: открытый ключ должен получаться из секретного ключа при помощи преобразования ( односторонней функции) $inline$f$inline$, обладающего следующими двумя свойствами:

$inline$B = f(A)$inline$, зная A, вычислить саму функцию легко

$inline$A = f^{-1} (B)$inline$, а вычислить обратную функцию трудно

Что такое легко и трудно?

Алгоритмы с открытым ключом основаны на вычислительной сложности различных задач.
Более точно термин легко обычно означает, что проблему можно решить за полиномиальное время от длины входного сообщения. Т.е. пусть входное сообщение состоит из $inline$n$inline$ битов, тогда время вычисления $inline$t \propto n^a$inline$, где $inline$a $inline$ зафиксированная константа. Будем говорить, что алгоритм из класса полиномиальных алгоритмов Р.

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

Т.е. пусть входное сообщение состоит из $inline$n$inline$ битов, и время вычисления функции $inline$t \propto 2n$inline$, то будем говорить, что это вычислительно невозможная задача.

Задача о рюкзаке формулируется так

Задан набор (рюкзачный вектор) $inline$A = (a_1, ... , a_n) $inline$ это упорядоченный набор из $inline$n$inline$ ($inline$n > 2), $inline$ различных натуральных чисел $inline$a_i$inline$. Пусть есть число $inline$k$inline$ целое и положительное. Задачей является нахождение такого набора $inline$a_i$inline$, чтобы в сумме они давали ровно $inline$k$inline$.

В наиболее известном варианте задачи о рюкзаке требуется выяснить, обладает ли данная пара $inline$(A , k)$inline$ решением. В варианте, используемом в криптографии, нужно для данного входа $inline$(A , k)$inline$ построить решение, зная, что такое решение существует. Оба эти варианта являются NP-полными.

Аналогия с рюкзаком

В самом простом случае $inline$k$inline$ обозначает размер (вместительность) рюкзака, а каждое из чисел $inline$a_i$inline$ указывает размер (вес) предмета, который может быть упакован в рюкзак. Задачей является нахождение такого набора предметов, чтобы
рюкзак был полностью заполнен.

Т.е представьте, что у вас есть набор гирь 1, 6, 8, 15 и 24, вам нужно упаковать рюкзак весом 30.

В принципе решение всегда может быть найдено полным перебором подмножеств $inline$А$inline$ и проверкой, какая из их сумм равна $inline$k$inline$. В нашем случае, это означает перебор $inline$2^5 = 32$inline$ подмножеств (включая при этом и пустое множество). Это вполне осуществимо.

Но что будет, если существует несколько сотен чисел $inline$a_i$inline$?
В нашем примере n = 5, чтобы не усложнять изложение. В реальных условиях пpимер будет иметь, скажем, 300 $inline$a_i-х$inline$. Суть здесь в том, что неизвестны алгоритмы, имеющие существенно меньшую сложность по сpавнению с полным перебором. Поиск среди $inline$2^{300}$inline$ подмножеств не поддается обработке. В самом деле, задача о рюкзаке известна как NP-полная NP-полные задачи рассматриваются как трудновычислимые.

Подходит ли функция под указанные требования?

Определим функцию $inline$f(x)$inline$ следующим образом. Любое число $inline$0 x 2n 1$inline$ может быть задано двоичным представлением из $inline$n$inline$ pазpядов, где пpи необходимости добавляются начальные нули. Теперь определим $inline$ f(x)$inline$ как число, получаемое из $inline$A$inline$ суммированием всех таких $inline$a_i$inline$, что соответствующий pазpяд в двоичном представлении $inline$x$inline$ равен 1.

Т.е.

$$display$$f(1) = f(0 . . . 001) = a_n$$display$$

$$display$$f(2) = f(0 . . . 010) = a_{n1}$$display$$

$$display$$f(3) = f(0 . . . 011) = a_{n1} + a_n$$display$$

$$display$$...$$display$$

Функция $inline$f(х )$inline$ определялась $inline$n-$inline$ набором $inline$ A$inline$. Очевидно, что если мы в состоянии вычислить $inline$x$inline$ из $inline$f(x)$inline$, то пpактически за то же время будет решена задача о рюкзаке: по $inline$x$inline$ немедленно вычисляется его двоичное представление, которое в свою очередь дает компоненты набора $inline$A$inline$, входящие в сумму для $inline$f(x)$inline$. С другой стороны, вычисление $inline$f(x)$inline$ из $inline$x$inline$ является легким. Так как задача о рюкзаке NP-полна, $inline$f(x)$inline$ является хорошим кандидатом для односторонней функции. Конечно, надо потребовать, чтобы $inline$n$inline$ было достаточно большим, скажем, не менее $inline$200$inline$.

Шифрование

Открытый текст

Открытый текст (англ. plain text) в криптографии исходный текст, подлежащий шифрованию, либо получившийся в результате расшифровки. Может быть прочитан без дополнительной обработки (без расшифровки).

Шифровать можно двумя способами:

Шифр сообщения получается, если возвести элементы данного рюкзачного вектора в степень соответствующих им бит шифруемого сообщения и далее перемножить все результаты, то есть если $inline$A = (2,3,5)$inline$, а сообщение $inline$(100)$inline$, то шифром будет число $inline$2^1*3^0*5^0=2$inline$. Это мультипликативным способ.
Шифр сообщения получается, если умножить элементы данного рюкзачного вектора на соответствующие им биты шифруемого сообщения и далее просуммировать все результаты, то есть если $inline$A = (2,3,5)$inline$, а сообщение $inline$(100)$inline$, то шифром будет число $inline$2^ *1+3^ *0+5^ *0= 2$inline$. Такой способ называют аддитивным.

Пример

Для шифрования открытого текста в двоичном представлении его разбивают на блоки длины $inline$n$inline$ (например, Вы можете представить вес 30 двоичным кодом 11110). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие.

Шифрование рюкзака обеспечивает хороший подход к созданию открытых и закрытых ключей, где закрытый ключ прост в использовании, а открытый ключ трудно вычислить.
Так, мы можем составить систему, где:

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

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

Лёгкая проблема

Сверхрастущий рюкзачный вектор

Рюкзачный вектор $inline$A=(a_{1},...,a_{n})$inline$ называется сверхрастущим, если $inline$_{i=1}^{j-1} a_{i} < a_{j}$inline$ для $inline$j=2,...,n$inline$, т.е каждый член последовательности больше суммы предыдущих.

Для сверхрастущих векторов задача о рюкзаке легко решаема. Т.е. рюкзак собрать несложно.
Рассмотрим на примере:

Алгоритм

Общий вес ранца сравнить с наибольшим весом в последовательности.
Если общий вес меньше числа, значит, в рюкзаке его нет. Если общий вес больше числа, он в рюкзаке.
Вычесть число из общей суммы и сравните со следующим по величине числом.
Повторить (1)-(2) пока общая сумма не достигнет нуля.
Если сумма не достигает нуля, то решения нет.

Трудная проблема

Расшифровать задачу о несверхувеличивающемся рюкзаке гораздо сложнее.
Один алгоритм, который использует сверхувеличивающийся рюкзак для частного ключа и несверхувеличивающийся рюкзак для открытого ключа, был создан Мерклом и Хеллманом.
Они сделали это, взяв задачу сверхувеличивающегося рюкзака и преобразовав ее в несверхувеличивающую задачу.
(Меркл и Хеллман, используя модульную арифметику, разработали способ трансформации лёгкого рюкзака в трудный)

Создание открытого ключа

Несколько важных понятий

Обозначим $inline$(x, mod m)$inline$наименьший неотрицательный остаток от деления $inline$x$inline$ на $inline$m$inline$,
где $inline$x$inline$ целые, $inline$m > 1$inline$, [x/m] целая часть,
$$display$$x = (x, mod m) + [x/m]*m$$display$$

Модульное умножение
Рассмотрим рюкзачный вектор $inline$A$inline$, целое число $inline$m > max A$inline$ и натуральное $inline$t < m$inline$ такое, что наибольший общий делитель $inline$(t, m) = 1$inline$.
Если $inline$B = (b_1, . . . , b_n)$inline$ такой вектор, что $inline$b_i = (ta_i, modm)$inline$, для $inline$i = 1, . . . , n$inline$, то говорят, что вектор B получен из A с помощью модульного умножения относительно модуля m и множителя t или, короче, относительно пары $inline$(m, t)$inline$.
Условие $inline$(t, m) = 1$inline$ гарантирует существование обратного
числа $inline$t^{1} = u$inline$, такого, что

$$display$$tu 1 (mod m)$$display$$

и $inline$1 u < m$inline$. Это означает, что также и обратно $inline$A $inline$получается из $inline$B$inline$
модульным умножением относительно $inline$m, u$inline$.

Если вышеуказанное условие $inline$m > max A$inline$ заменяется более сильным
условием $inline$m > _{i=1}^{n} a_{i} $inline$, то говорят, что $inline$B$inline$ получается из $inline$A$inline$сильным модульным умножением относительно $inline$m, t$inline$.

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

Создатель криптосистемы выбирает такую систему $inline$A, t, m, B$inline$, что вектор $inline$A$inline$ является сверхрастущим, а $inline$B$inline$ получается из $inline$A$inline$ сильным модульным умножением относительно $inline$m, t$inline$. Вектор $inline$B$inline$ раскрывается как ключ зашифpования и двоичные блоки длины $inline$n$inline$ посылаются к проектировщику как числа $inline$$inline$, полученные с помощью вектора $inline$B$inline$.

Перехватчик сообщений должен решать задачу о рюкзаке для входа $inline$(B, )$inline$. Создатель же криптосистемы вычисляет $inline$ = (u, modm)$inline$
и решает задачу о рюкзаке для входа $inline$(A, )$inline$. Почему все это работает,
показывает следующая лемма.

Лемма. Предположим, что $inline$A = (a_1, . . . , a_n) $inline$сверхрастущий вектор и вектор $inline$B$inline$ получен из $inline$ A$inline$ сильным модульным умножением относительно $inline$m, t$inline$. Предположим далее, что $inline$u t^{1} (mod m)$inline$, $inline$$inline$ произвольное натуральное число и $inline$ = (u,modm)$inline$. Тогда справедливы следующие утверждения.

(i) Задача о рюкзаке $inline$(A, )$inline$ разрешима за линейное время. Если решение существует, то оно единственно.
(ii) Задача о рюкзаке $inline$(B, )$inline$ имеет не более одного решения.
(iii) Если существует решение для входа $inline$(B, )$inline$, то оно совпадает с единственным решением для входа $inline$(A, )$inline$.
доказательство(стр. 104)

Пример

Возмём сверхрастущую последовательность; например, {1, 2, 4, 10, 20, 40}. Модуль должен быть больше суммы всех чисел в последовательности, например 110. Множитель не должен иметь общих делителей с модулем. Итак, давайте выберем 31.

Итак, мы вычислили открытый ключ: {31, 62, 14, 90, 70, 30} и закрытый ключ {1, 2, 4, 10, 20.40}.

Теперь попробуем отправить двоичную последовательность: 100100111100101110

Некоторые преимущества открытых ключей

При использовании криптосистемы с открытым ключом обе стороны не встречаются, они даже могут не знать друг друга и использовать любые виды связи.

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

История

Долгое время ранцевые криптосистемы рассматривались как наиболее привлекательные и перспективные криптосистемы благодаря их NP-полноте и высокой скорости шифрования и дешифрования. Многие схемы используют задачу о ранце (в различных вариациях), вот лишь несколько из них: the compact knapsack problem, the multiplicative knapsack problem, the modular knapsack problem, the matrixcover problem, the group factorization problem

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

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

Тут есть несколько НО.

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

Материал подготовлен на основе данной литературы:

(1) А. Саломаа. Криптография с открытым ключом/ Public-Key Cryptography. Springer-Verlag, 1990. Стр. 75-82, стр. 101111

(2) Мин Кин Лай. Ранцевые криптосистемы: прошлое и будущее Калифорнийский университет, 2001
(3) Baocang Wang, Qianhong Wu, Yupu Hu. A knapsack-based probabilistic encryption scheme. 2007

(4) (5)

Подробнее..

Категории: Информационная безопасность , Научно-популярное , Криптография , Криптографические алгоритмы

Recovery mode Элементарная гигиена и слив базы сторонников Навального

16.04.2021 14:07:36 |

Автор: admin

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

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

Для такого случая отлично бы подошло любое асимметричное шифрование. Суть его, я полагаю, большинству известна. А кому не известна, - я поясню. Асимметричное шифрование - это такой способ шифрования, при котором для зашифровки используется один ключ, а для расшифровки - другой. Первый ключ мы используем для шифрования данных (в том числе имэйлов) - потерять его вообще не страшно, его можно выложить хоть в открытый доступ, потому что расшифровать с помощью него ничего не получится. Второй же ключ - храним в очень тайном месте и никому не говорим о нём, и, тем более, не выкладываем его на сервер, который могут взломать. Когда набралось бы ожидаемые пол миллиона человек, можно было бы достать ключ для расшифровки и получить список адресов из БД, например, для рассылки о том, что "пора".

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

Подробнее..

Категории: Информационная безопасность , Анализ и проектирование систем , Криптография , Хранение данных , Шифрование , Криптографические алгоритмы , Асимметричная криптография

Честное онлайн-голосование миф или реальность?

27.05.2021 22:07:59 |

Автор: admin

Привет, Хабр! Меня зовут Иван, я разрабатываю сервис онлайн-голосований WE.Vote на основе блокчейн-платформы Waves Enterprise. Сама идея голосований в онлайне уже давным-давно реализована разными компаниями, но в любых кейсах повышенной ответственности все равно прибегают к старой доброй бумаге. Давайте посмотрим, как электронное голосование сможет посостязаться с ней в максимально строгих условиях.

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

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

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

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

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

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

Чего мы хотим добиться

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

Организатор голосования создает повестку и хочет управлять правилами доступа к этой повестке: сделать ли ее публичной или раскрыть только участникам голосования.
Организатор голосования создает список его участников и хочет быть уверенным, что в его голосовании примут участие именно они. Сами участники также заинтересованы в этом, так как подразумевается, что они принимают решение по важному для них вопросу и мнение/намерения/выгода третьих лиц не должны на это решение повлиять.
Организатор задает правила проведения голосования. Эти правила без раскрытия сути голосования должны быть доступны широкой публике, чтобы организатор, участники голосования и третьи лица (например, регулятор) могли убедиться, что способ принятия решения был выбран корректно и все прошло по заранее известному плану.
Участник голосования получает повестку голосования и хочет убедиться, что это именно тот список вопросов, который получат все остальные, что ему не прислали укороченную версию. Эти сомнения выглядят нелепо для бумажного голосования, где все бланки заранее распечатаны, все выдаются из общей стопки и нет никакой возможности персонализировать бюллетень. Но в случае онлайн-голосования все, что мы имеем, это байты информации, которые легко изменить на лету. Поэтому хотелось бы иметь больше гарантий аутентичности.
Участник голосования заполняет бюллетень и хочет убедиться, что его голос будет учтен, его голос не будет изменен и никто не сможет определить, как именно он проголосовал (частный случай открытых голосований оставим в стороне).
Организатор и участники голосования узнают его результаты. В этот момент все хотятбыть уверены,что никто не вмешивался в ход голосования, не фильтровал бюллетени, не делал вбросов, не подправлял итоги и т.п.. Все включая и оператора онлайн-сервиса голосований.

При чем тут блокчейн

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

Распределенное хранение

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

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

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

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

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

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

Пара ключей создается пользователем локально, на его персональном устройстве. Приватный ключ этого устройства не покидает, а публичный сохраняется набэкендекак параметр учетной записи. Организатор голосования работает со списком участников в виде Ф.И.О. и e-mail. При сохранении данных голосования в блокчейне туда же уходит список публичных ключей. Голос подписан ключом пользователя, и если публичный ключ отправителя есть в списке участников, мы принимаем бюллетень. Такая схема позволяет,с одной стороны,не светить персональными данными пользователей, а с другой сделать более прозрачной работу системы.

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

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

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

Подводя промежуточный итог, можно сказать,что:

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

Но, несмотря на то что мы обещали обойтись без магии, она все-таки произошла. Для шифрования бюллетеней нам понадобился открытый ключ голосования, но никто не сказал, откуда он взялся! Очевидно, что это предельно важная часть всего процесса голосования и к нему нельзя отнестись легкомысленно. Еще более интересным кусочком пазла является приватный ключ, соответствующий открытому ключу голосования, так как именно с его помощью мы сможем получить итоги голосования.Настал момент шагнуть в область криптографии (которая для 99.9% людей не сильно отличается от магии).

Криптография

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

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

Несколько болеенадежным вариантом будет техника разделения приватного ключа после генерации хорошо известная схема разделения секрета Шамира. Ключевая пара создается, публичный ключ сохраняется в блокчейне как открытый ключ голосования, а приватный ключ разделяется на несколько частей, которые независимо хранятся доверенными участниками. Чтобы подвести итоги голосования, приватный ключ необходимо собрать и после этого расшифровать бюллетени. Если кто-то из доверенных участников заболел, схема Шамира предполагает возможность сбора приватного ключа меньшим количеством участников. То есть если ключ был разбит на N частей, собрать обратно его можно, используя K частей, где K < N.

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

Конечно, существуют механизмы разрыва первой связки персональных данных и открытого ключа через технику слепой подписи, но это очень своеобразный механизм, который необходимо правильно внедрить. При этом всё равно может сохраниться возможность вычислить по IP голосующего. Он приходит на авторизованный метод получать слепую подпись, а потом стучится на неавторизованный метод отправить голос. Формально во втором случае мы не знаем, кто именно к нам пришел, и опираемся только на проверку слепой подписи. Но у нас есть возможность сопоставить параметры устройства/браузера/соединения и понять, что это тот самый Иванов, который 5 минут назад получал у нас слепую подпись. Или представим похожую атаку на сопоставление по времени получения подписи и отправки голоса. Когда голосующие идут толпой по 500 человек в секунду, такая атака теряет свою эффективность, но при меньшей нагрузке вполне себе работает.

Попробуем сделать лучше?

Распределенная генерация ключа

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

Для формирования общегооткрытогоключа голосования (MainPubliсKey) используется алгоритм DKG (distributed key generation) из статьи TorbenPrydsPedersenA threshold cryptosystem without a trusted party,перенесенный на эллиптические кривые (в оригинальной статье используется мультипликативная группа конечного поля (поля Галуа)GF(p)). При этом есть ограничение:при любой жалобе (не сходится контрольная сумма) одного из участников на другого необходимо перезапустить процесс генерации с самого начала.

В нашей текущей реализации DKG используются стандартные эллиптические кривые seсp256k1 (Bitcoin, Ethereum) и функция хеширования SHA-256. Можно легко добавить, например, Ed25519 или даже российские кривые ТК-26 и хеш Стрибог, если потребуется. Также можно не завязываться на 256-битных кривых, а использовать 512-битные.

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

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

Протокол DKG Pedersen 91 на эллиптических кривых

Параметры протокола:

Эллиптическая кривая E и генератор (Base) подгруппы этой кривой большого простого порядка q.
Другой генератор (BaseCommit) той же подгруппы, для которого число x из соотношения BaseCommit = x * Base неизвестно никому.
(k, n), гдеnобщее число развернутых криптографических сервисов (DecryptService), сгенерировавших пары ключей, аkминимальное число сервисов, которое необходимо для восстановления общего секрета. k <= (n+1)/2, то есть еслиk - 1участниковнечестные или у них украли ключи, то это никак не повлияет на безопасность общего секрета (MainPubliсKey).

Шаг 0. Индексы DecryptService

Каждому изnDecryptServiceприсваивается уникальный порядковый номер от 1 доn. Это нужно, потому что от порядкового номераDecryptServiceзависит коэффициент Лагранжа, который потребуется для реализации схемы K из N.

Шаг 1. Создание открытого ключа голосования

Каждый изnDecryptServiceгенерирует пару публичного (Pub_n)и приватного (priv_n) ключей для эллиптической кривой: j-йсервер генерирует пару ключей:priv_j,Pub_j,гдеPub_j = priv_j * Base(точка Base генератор простой подгруппы). И делает Pedersen commitment для публичного ключа:

Генерируется случайное число, скалярr_j.
Вычисляется точка, коммитС_j = r * BaseCommit + Pub_j.
С_jпубликуется в блокчейн.

После того как каждый изnDecryptServiceопубликовал свой коммит ПедерсенаС_j, каждый DecryptService публикует свой скалярr_j. На основе опубликованных в блокчейне скаляров любой сторонний наблюдатель может восстановить публичные ключи каждого DecryptService Pub_j =С_j -r * BaseCommit а затем вычислить общий публичный ключ Pub (MainPublicKey) как сумму отдельныхPub_j.

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

Шаг 2. Генерация полиномов и раздача теней

Каждыйj-йDecryptService случайным образом:

Генерирует полином степениk - 1:f_j(x) = f_j_0 + f_j_1*x + ... + f_j_k-1* x^(k-1), где коэффициентf_j0 = priv_j, а остальные случайные элементы поляGF(q), гдеq порядок подгруппы точек.
Считает значения полинома для каждогоi-гоизnзначений:f_j(i) = f_j_0+ f_j_1*i + ... + f_j_k-1* i^(k-1). Значениеf_j(i)называется тенью (shadow).
Шифруетf_j(i)при помощиPub_iдля всех других серверов и публикует результаты шифрования. Таким образом,значениеf_j(i)может узнать только владелецpriv_i, т.е. DecryptService номерi.

Шаг 3. Проверка коэффициентов полиномов

Чтобы убедиться, что каждый из DecryptService следует протоколу DKG, они проверяют значения теней, полученных друг от друга. Каждый DecryptServiceпубликует каждый коэффициент своего полинома, умноженного на генератор Base: j-й сервер:f_j,0* Base, f_j,1* Base, ... , f_j,k-1* Base, где f_j,k-1 это коэффициент при степениk - 1.

После этого каждыйi-йDecryptServiceпроверяет все расшифрованные тениf_j(i)(гдеjиз множества от 1 доn, исключаяi), которые для него зашифровали другиеn - 1участников DKG. i-йDecryptServiceдля тени от сервераj:

Вычисляетf_j(i) * Base
Берет экспоненты его коэффициентов:f_j,0* Base, f_j.1* Base, ... , f_j,k-1* Base
Домножает каждый на соответствующую степеньi:f_j,0* Base, i * ( f_j,1* Base), ... , i^(k-1) * ( f_j,k-1* Base)
Складывает их.

Если результат сложения равенf_j(i) * Base(тень отjдляi, умноженная на генератор), то результат принимается. В противном случае публикуется жалоба на серверj: значение тениf_j(i), и протокол запускается с самого начала шага 0.

Если ни у кого нет жалоб, то каждый сервер вычисляет свой секретный ключs_iкак сумму значенийf_j(i)от всехjсерверов, включая себя.

Если взять любые изkучастников, то сложив ихs_i * Lagrange(k, i), где Lagrange(k, i) коэффициент Лагранжа, который зависит от номеров из выбранной группы (k) и номераi, мы получим приватный ключ, соответствующий общему ключу Pub (MainPublicKey), то есть по сути сумму всехpriv_i.

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

Мы решили проблему угона приватного ключа до начала голосования. Он не был создан централизовано, и чтобы получить доступ к данным голосования, злоумышленнику необходимо взломать K серверов, а не один. Но остается вопрос: как мы будем проводить расшифровывание. Будем ли мы собирать приватный ключ в этот момент и дадим ли шанс злоумышленнику? Пожалуй, не дадим.

Шаг 4. Распределенное дешифрование

Допустим, мы зашифровываем сообщение M на открытом ключе голосования (MainPublicKey):

Генерируем число r и считаем R = r * Base.
ВычисляемС = M + r *MainPublicKey.
Получившийся шифротекст пара точек (R, C) мы публикуем в блокчейне.
Владелец приватного ключаprivвычисляет значение:priv * R.
И расшифровываетM:M = С -priv * R.

Таким образом, для расшифровывания (R, C) нужно вычислитьpriv * R.

Если наш приватный ключ распределен (допустим, что (k, n) = (3,6)), каждый криптографический сервис независимо считает значениеs_i * R, используя свою часть приватного ключа, и публикует результат в блокчейне. Назовем это значение частичной расшифровкой. Дальше остается домножить любые 3 из 6 результатовs_i * Rна соответствующий коэффициент Лагранжа, сложить три точки и получить priv * R. А используя это значение, мы расшифровываем сообщение М.

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

Гомоморфное шифрование

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

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

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

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

Бюллетень в виде матрицы вопросов и вариантов ответов

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

Подсчет результатов в зашифрованном виде

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

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

Зашифрованное сообщение 1: ( R1, С1 ) =( r1 * Base,M1 + r1 *MainPublicKey)

Зашифрованное сообщение 2: ( R2, С2 ) =( r2 * Base,M2 + r2 *MainPublicKey)

Их сумма: ( R1 + R2, C1 + C2 ) = ( ( r1+r2 ) * Base, M1 + M2 + ( r1 + r2 ) *MainPublicKey)

Сумму расшифровываем так же, как отдельные сообщения (помним чтоMainPublicKey= priv * Base):

( M1 + M2 ) = ( C1 + C2 ) priv * ( R1 + R2 ) = M1 + M2 + ( r1 + r2 ) *MainPublicKey priv * ( r1 + r2 ) * Base = M1 + M2

Кто-то скажет магия, кто-то возразит математика.

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

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

Доказательства с нулевым разглашением (ZKP Zero Knowledge Proofs)

Однако не только организатор или внешний злоумышленник могут иметь мотивацию повлиять на исход выборов. Нарушитель может затесаться и в ряды участников голосования. Поскольку мы используем очень простую механику сложения столбиком и не заглядываем в индивидуальные бюллетени, у участника голосования есть возможность покопаться в клиентском приложении и сформировать бюллетень, где он вместо "1" проставит за своего кандидата значение 100500. Или 100500 за того, кого недолюбливает. Система посчитает итоги, и кандидат нарушителя победит с внушительным преимуществом.

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

Одна из самых наглядных демонстраций работы ZKP (интерактивной разновидности) это Пещера Али-Бабы или Лабиринт:

Участник A обладает ключом, открывающим дверь в лабиринте, и хочет доказать это участнику B, но не хочет показывать ключ. Чтобы В мог убедиться в верности утверждения А, они организуют серию испытаний:

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

Шанс того, что А просто повезло, и он, не имея ключа, изначально пошел налево, составляет 50/50. Поэтому они повторяют испытание еще и еще раз, пока вероятность везения не станет пренебрежимо малой, и В не признает, что А действительно обладает ключом. При этом В не увидит самого ключа, не получит никакой информации, которой обладает А (направление, которое А выбирает в каждом испытании), но в результате серии испытаний он получит достоверное (вероятностное, но с любой необходимой В точностью) доказательство.

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

ZKP на бюллетене

По каждому вопросу мы, помимо заполненных и зашифрованных ячеек с вариантами выбора, к каждой ячейке приложим NIZK, доказывающее, что в этой ячейке зашифровано одно из значений 0 или 1 но не раскрывающее, какое именно. И дополнительно приложим доказательство, что зашифрованная сумма значений всех ячеек по вопросу равна 1. Это означает, что участник голосования может поставить 1 в любую из ячеек и выбрать только один вариант.

При желании (а оно у нас есть) мы можем на базе этой схемы ZKP реализовать более сложные схемы голосований. Например, взвешенное голосование, где каждый участник отдает не один голос, а количество голосов, пропорциональное своей доле акций компании. Для этого мы должны вместо 1 создать ZKP для значения веса голоса участника. Или вариант голосования с множественным выбором, где каждый голосующий может выбрать не один вариант из N, а несколько. Для этого мы по каждой ячейке добавляем ZKP для ряда значений [0, 1, 2, 3]. Суммарный ZKP может быть на значение [3] тогда голосующий должен распределить все свои голоса. Или на ряд значений[1, 2, 3] то есть он может выбрать от 1 до 3 вариантов, но не может не ответить на вопрос.

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

Структура зашифрованного бюллетеня выглядит следующим образом:

(R_1, C_1), Proof_1,

.........................

(R_M, C_M), Proof_M,

Sum_Proof

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

ZKP на частичных расшифровках

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

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

Второе условие: если расшифровывание нескладывается,и мы подозреваем, что некоторые криптографические сервисы решили саботировать голосование, неплохо бы иметь возможность проверить, какой именно из сервисов сбоит. Для этого при публикации частичных расшифровок каждый криптосервис создает и прикладывает ZK-доказательство расшифровки, используя алгоритмZKP Chaum-Pedersen, который доказывает знание числа x для двух соотношений A = x * B и C = x * D (где A B, C, D точки на одной кривой).

Теперь у любого квалифицированного стороннего наблюдателя есть возможность:

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

Для удобства последний шаг мы проведем сами и зафиксируем итоги голосования в блокчейне как массива массивов вида [ [ 2,5,6 ], [ 3,5,5 ], [ 7,6 ], [ 10,3 ] ].

Смарт-контракты

Фух, кажется, мы описали протокол голосования, который, используя распределенные технологии и криптографию, позволяет дать честным участникам и организаторам голосований все необходимые гарантии и защищает процесс коллективного принятия решений от внутреннего и внешнего нарушителя. Очевидно, при условии правильной децентрализации распределении узлов системы между независимыми участниками; без этого мы получаем замороченные Google Forms :)

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

Именно такую роль выполняют смарт-контракты в блокчейне. Это умный ящик для голосования, который фиксируетправила голосования,хранит список участников и статусную модель голосования: какой публичный ключ принадлежит участнику, какой криптографическому сервису. Также смарт-контракт регистрирует публичные данные протокола DKG, проверяет и сохраняет отправленные голоса и результаты голосования.

А что дальше?

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

Еще одно важное для нас направление развития то, о чем разработчики, увлеченные красивым решением технической проблемы, склонны забывать. А именно UX опыт пользователя :)Прикрутить блокчейн это современно, модно,и в данном случае даже целесообразно, но попробуйте пользователю, который привык к UX современных мобильных и веб-приложений, объяснить, что такое его персональный приватный ключ и что без него он не сможет сделать в системе ровным счетом ничего.Или дать ему одновременно гарантию, что отправленная им транзакция будет принята системой, не заставляя ждать его, пока мы сами в этом убедимся. Нода майнит, прелоадер крутится, пользователь ждет и не понимает чего именно: Ну не знаю, почту я отправляю, все работает мгновенно, а тут чего-то ждать надо?. Поэтому мы активно работаем над тем, чтобы система сохраняла привычные пользовательские свойства, не теряя своих технологических преимуществ.

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

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

Подробнее..

Категории: Информационная безопасность , Математика , Криптография , Шифрование , Распределенные системы , Электронное голосование , Децентрализованные сети , Блокчейн , Смарт-контракты , Криптографические алгоритмы

	Русский
	English

Криптографические алгоритмы

Recovery mode Разработка собственного алгоритма симметричного шифрования на Php

Из песочницы Задача о ранце в криптографии (Knapsack problem in cryptography)

Задача о рюкзаке формулируется так

Аналогия с рюкзаком

Шифрование

Лёгкая проблема

Трудная проблема

Некоторые преимущества открытых ключей

История

Recovery mode Элементарная гигиена и слив базы сторонников Навального

Честное онлайн-голосование миф или реальность?

Чего мы хотим добиться

При чем тут блокчейн

Распределенное хранение

Криптография

Распределенная генерация ключа

Протокол DKG Pedersen 91 на эллиптических кривых

Гомоморфное шифрование

Доказательства с нулевым разглашением (ZKP Zero Knowledge Proofs)

ZKP на бюллетене

ZKP на частичных расшифровках

Смарт-контракты

А что дальше?

Категории

Последние комментарии