Второй раз за месяц найдена уязвимость в московской системе электронного голосования

Две недели назад на Хабре писали ^[1] о найденной уязвимости в системе электронного голосования на выборах в Мосгордуму. Разработчики обещали ее устранить, но как выяснилось это породило новую уязвимость.

В опубликованной на сайте arxiv.org заметке Александра Головнева ^[2] указывается, что хотя разработчики устранили найденную Пьерриком Годри уязвимость в реализации схемы Эль-Гамаля, они вновь реализовали ее неправильно, что привело к возможности подсчета голосов в любой момент работы системы. Поскольку у нас в стране публикация результатов голосования запрещена до окончания выборов это, видимо, является серьезной уязвимостью.

Как показал Головнев, проблема текущей реализации заключается в том, что при шифровании результата голосования не происходит хэширования значения голоса, что приводит к возможности различить с помощью простого критерия Эйлера ^[3] различные голоса.

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

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

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

Например, номера кандидатов 1, 3 и 4 — квадратичные вычеты, а 2- нет. То есть, мы можем анализируя блокчейн по мере его обновления подсчитывать количество голосов за кандидата 2.

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

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

Автор: starpeer

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