Две недели назад на Хабре писали о найденной уязвимости в системе электронного голосования на выборах в Мосгордуму. Разработчики обещали ее устранить, но как выяснилось это породило новую уязвимость.
В опубликованной на сайте arxiv.org заметке Александра Головнева указывается, что хотя разработчики устранили найденную Пьерриком Годри уязвимость в реализации схемы Эль-Гамаля, они вновь реализовали ее неправильно, что привело к возможности подсчета голосов в любой момент работы системы. Поскольку у нас в стране публикация результатов голосования запрещена до окончания выборов это, видимо, является серьезной уязвимостью.
Как показал Головнев, проблема текущей реализации заключается в том, что при шифровании результата голосования не происходит хэширования значения голоса, что приводит к возможности различить с помощью простого критерия Эйлера различные голоса.
Головнев предложил способ устранения уязвимости введением хэширования результата голосования в группу квадратичных вычетов. Однако, по его мнению, основной проблемой этой системы голосования является отсутствие полного описания ее функционала, что не позволяет провести нормальный аудит.
В опубликованной на сайте arxiv.org заметке Александра Головнева указывается, что хотя разработчики устранили найденную Пьерриком Годри уязвимость в реализации схемы Эль-Гамаля, они вновь реализовали ее неправильно, что привело к возможности подсчета голосов в любой момент работы системы. Поскольку у нас в стране публикация результатов голосования запрещена до окончания выборов это, видимо, является серьезной уязвимостью.
Как показал Головнев, проблема текущей реализации заключается в том, что при шифровании результата голосования не происходит хэширования значения голоса, что приводит к возможности различить с помощью простого критерия Эйлера различные голоса.
Под спойлером немного математики
Пусть 
и 
простые числа длины порядка 1024 бита. 
— группа квадратичных вычетов по модулю 
, 
. Для шифрования система выбирает 
, 
— открытый и 
— секретный ключи (
). Результат шифрования голоса 
имеет вид пары
, 
-случайное число.
Если квадратичный вычет, то при любом второй компонент шифротекста тоже квадратичный вычет (аналогично — если не квадратичный вычет). Это дает возможность отличать различные голоса с помощью критерия Эйлера. Для этого нам достаточно возвести шифротекст в степень 
и проверить равен ли результат единице (в этом случае — это квадратичный вычет).
Например, номера кандидатов 1, 3 и 4 — квадратичные вычеты, а 2- нет. То есть, мы можем анализируя блокчейн по мере его обновления подсчитывать количество голосов за кандидата 2.
Атака будет работать даже тогда, когда вместо номеров кандидатов будут произвольные идентификаторы, правда с меньшей вероятностью успеха.
и простые числа длины порядка 1024 бита. — группа квадратичных вычетов по модулю , . Для шифрования система выбирает , — открытый и — секретный ключи (). Результат шифрования голоса имеет вид пары, -случайное число.Если
квадратичный вычет, то при любом второй компонент шифротекста тоже квадратичный вычет (аналогично — если не квадратичный вычет). Это дает возможность отличать различные голоса с помощью критерия Эйлера. Для этого нам достаточно возвести шифротекст в степень и проверить равен ли результат единице (в этом случае — это квадратичный вычет). Например, номера кандидатов 1, 3 и 4 — квадратичные вычеты, а 2- нет. То есть, мы можем анализируя блокчейн по мере его обновления подсчитывать количество голосов за кандидата 2.
Атака будет работать даже тогда, когда вместо номеров кандидатов будут произвольные идентификаторы, правда с меньшей вероятностью успеха.
Головнев предложил способ устранения уязвимости введением хэширования результата голосования в группу квадратичных вычетов. Однако, по его мнению, основной проблемой этой системы голосования является отсутствие полного описания ее функционала, что не позволяет провести нормальный аудит.
