← Все статьи

Математическое «доказательство» правильного подсчёта голосов — с встроенной секретной лазейкой

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

Весна 2019 года. Где-то в офисах Swiss Post принимается решение, которое выглядит как радикальная прозрачность. Федеральное почтовое ведомство, сотрудничая с испанским поставщиком Scytl, вот-вот опубликует полный исходный код системы интернет-голосования Швейцарии. Не краткое описание. Не брошюру. Весь код — каждую строчку — в открытом доступе для всего мира, чтобы читать, атаковать и оценивать.

Это должно было стать моментом, который закончит спор.

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

Три независимых исследователя — Сара Джейми Льюис, Оливье Перейра и Ванесса Тег — приняли Swiss Post в слово. Они посмотрели.

То, что они обнаружили, казалось невозможным.

Доказательство, которое ничего не доказывало

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

Интернет-голосование имеет принципиальную проблему: когда избиратель подаёт бюллетень через интернет, как кому-либо — включая самого избирателя — подтвердить, что он был подсчитан правильно и не заменён другим бюллетенем сервером посередине? Ответ, который разработали криптографы, называется микссетью или сетью перемешивания. Голоса поступают зашифрованными. Система их перемешивает — как карточную колоду — и затем, что самое главное, публикует математическое доказательство честности перемешивания: что оно переместило голоса, но не изменило ни один из них.

Это доказательство — основное утверждение системы о проверяемости. Каждый, имеющий нужное программное обеспечение, может его проверить. Если доказательство пройдёт, голоса целы. Если оно не пройдёт, вы знаете, что что-то не так.

За исключением того, что в само доказательство была встроена лазейка.

Льюис, Перейра и Тег описали своё открытие в статье, которую озаглавили — со ссылкой на Магритта — Ceci n'est pas une preuve. «Это не доказательство». Они обнаружили, что доказательство перемешивания в системе Swiss Post–Scytl использовало схему обязательства с лазейкой: математическую структуру, которая функционирует честно в нормальных условиях, но которую, если вы знаете скрытый набор значений (лазейку), можно использовать в собственных целях. Орган власти, обладающий этими значениями, мог бы создать стенограмму доказательства перемешивания, которая бы прошла все проверки верификации — при этом фактически изменив голоса.

Прочитайте это медленно. Доказательство могло пройти. Математика могла сойти. Каждое ПО аудитора бы сказало: проверено. И голоса были бы неправильными.

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

Что на самом деле означает «проверяемость»

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

Проверяемость для кого?

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

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

Случай Swiss Post показывает более глубокую проблему. Система чёрного ящика, которая говорит «верьте нам», явно просит веры. Но система с опубликованным кодом, которая говорит «проверьте математику» и встраивает лазейку в саму математику, просит ту же веру, маскируя её как доказательство. Видимость проверяемости опаснее, чем признание непрозрачности, потому что она закрывает вопрос.

Как опубликованный код обнаружил недостаток, который пропустила сертификация

Вот что важно понимать: недостаток был обнаружен потому что код был опубликован.

Swiss Post не обязана была открывать исходный код. Большинство поставщиков этого не делают. Аппарат сертификации, существующий в большинстве демократий — в Соединённых Штатах, добровольные руководящие принципы по системам голосования Комиссии по помощи избирателям; в других юрисдикциях, национальные испытательные лаборатории — предусматривает проверку систем экспертами в контролируемых условиях, часто под соглашениями о неразглашении, с выводами, которые суммируются, но не всегда публикуются. Когда эксперт говорит «мы проверили и система прошла», общественность доверяет эксперту. Рассуждение скрыто.

Когда Swiss Post опубликовала код, она сделала возможным другой вид проверки: состязательный, независимый, без ограничений. Льюис, Перейра и Тег не были оплачены Swiss Post. Они не подписывали соглашение о неразглашении. Они опубликовали весь свой анализ со ссылками и уравнениями для всех, чтобы прочитать и оспорить. Это не процесс сертификации. Это научный процесс — и он обнаружил то, что процесс сертификации пропустил.

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

Сравните пробное интернет-голосование в округе Колумбия в 2010 году, когда команда Мичиганского университета получила почти полный контроль над пилотной программой возврата голосов менее чем за 48 часов — именно потому, что юрисдикция открыла систему для публичной проверки до того, как были поданы реальные голоса. Уязвимости были обнаружены, потому что кому-то было позволено атаковать. Или рассмотрим систему iVote в Новом Южном Уэльсе в 2015 году, где исследователи обнаружили серьёзные недостатки на живых выборах, которые уже собрали около 280 000 голосов — недостатки, которые проверка безопасности перед выборами разрешила. В каждом случае открытие исходило не из официального процесса, а из-за его пределов.

Закономерность сохраняется: открытая проверка находит то, что закрытая сертификация пропускает. Не всегда. Не автоматически. Но достаточно последовательно, чтобы бремя доказывания сместилось. Когда орган власти говорит «мы её сертифицировали», вопрос, который нужно задать: сертифицировано кем, против какой модели угроз, с каким доступом, и где опубликованы результаты?

Лазейка как категориальная проблема

Конкретный недостаток в системе Swiss Post — лазейка в криптографическом доказательстве — это не ошибка реализации в обычном смысле. Это не переполнение буфера и не неправильно настроенный сервер. Это ошибки. Это был выбор проекта, или как минимум ошибка проектирования, в математической структуре, на которой покоилась гарантия проверяемости системы.

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

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

Льюис, Перейра и Тег были мотивированы находить проблемы. Они нашли одну. Это не осуждение намерений Swiss Post — компания признала открытие и приступила к его исправлению. Это аргумент в пользу процесса, который привёл к этому открытию.

Что оставляет открытым утверждение «аудит подтвердил»

Когда система Swiss Post была приостановлена, официальные лица могли сказать: процесс сработал. Недостаток был найден; развёртывание было остановлено; последует исправление. И в узком смысле это верно. Но стоит задать вопрос, что бы произошло, если бы код не был опубликован.

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

Заявление о проверяемости, которое вы не можете независимо проверить, неотличимо от отсутствия проверяемости вообще. Это критика не уникальна для электронного голосования. Она применяется к каждому утверждению корректности в избирательной системе — включая подсчёты бумажных бюллетеней. Повторный подсчёт бюллетеней Грузии в 2020 году примерно пяти миллионов голосов подтвердил результат машинного подсчёта с точностью примерно в одну десятую процента, что впечатляет. Но это зависело от существования стойких бумажных бюллетеней, которые можно было независимо проверить, а не от доверия к машинам, которые их впервые подсчитали. Бумага была независимой проверкой. Доказательство, которое вы действительно могли инспектировать.

Случай Swiss Post — криптографический эквивалент: код, став опубликованным, был бумагой. И бумага показала, что доказательство было выдумкой.

Что сделало бы его действительно проверяемым

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

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

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

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

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

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

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

Злодей — это доказательство, которое вы не можете проверить

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

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

Злодей в истории Swiss Post — это не Swiss Post, и это не Scytl. Это непрозрачность, маскирующаяся под прозрачность — доказательство, которое выглядит проверяемым и не является. Решение — не отказываться от криптографической проверяемости, а требовать её реальную версию: схемы без лазеек, проверку без соглашений о неразглашении, доказательства, которые независимые исследователи могут проверить и, когда необходимо, опровергнуть.

Это то, к чему TrustVoting стремится: систему, правильность которой никто не должен принимать на веру, потому что доказательства опубликованы в форме, которую может инспектировать каждый. Не «мы её аудировали». Не «математика сошла». Вот математика. Проверьте её сами.

Версия для распространения: Швейцария опубликовала код своей системы электронного голосования, чтобы доказать её надёжность. Исследователи обнаружили лазейку, которая позволяла инсайдеру сфабриковать верное доказательство, одновременно изменяя голоса. Доказательство прошло. Голоса были бы неправильными. «Проверено» имеет смысл только если кто-то независимый имеет право проверять — и право сказать нет.

Что ещё не проверяемо: используют ли какие-либо другие развёрнутые криптографические системы электронного голосования аналогично проблемную схему обязательства, и включали ли ли процессы сертификации этих систем состязательную независимую криптографическую проверку с опубликованными выводами. Пока эта проверка существует и её результаты являются общественными, утверждение «система была сертифицирована» остаётся заявлением, а не доказательством.

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

Посмотрите, насколько распространён этот пробел верификации по всему миру →

Прочитайте 2-минутную версию этой проблемы →

Изучите документированные случаи непроверяемых результатов выборов →

Источники

Все статьиИзучить уязвимости