Криптограф взломал систему интернет-голосования в Москве. Мы тоже это сделали, и вы тоже можете

Французский криптограф Пьеррик Годри (Pierrick Gaudry) опубликовал работу «Взлом схемы шифрования московской системы интернет-голосования». 8 августа Годри отчитался о взломе на сайте исследовательской лаборатории Лотарингии в области информатики и ее приложений. 14 августа опубликовал препринт работы на сайте arXiv.org.

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

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

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

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

Успешный взлом, по словам разработчиков, должен удовлетворять трем критериям:

• секретные ключи должны быть восстановлены
• секретное сообщение должно быть расшифровано
• все это должно быть сделано за 12 часов (столько идет реальное голосование)

Годри сумел восстановить все три секретных ключа. На обычном компьютере у него ушло на это чуть больше 20 минут. «Медуза» повторила эксперимент — расчеты заняли примерно столько же времени. Когда секретные ключи известны, расшифровка сообщения становится тривиальной задачей.

Если коротко, разработчики московской системы голосования слабо зашифровали сообщения. Пьеррик Годри обнаружил, что они выбрали слишком маленькие ключи для шифрования — меньше 256 бит. Вообще-то это все равно очень длинное число, просто недостаточно длинное для этой задачи.

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

Сам Годри выдвинул несколько предположений по поводу длины ключа:

1. Проектировщики московской системы интернет-голосования ошибочно полагали, что последовательное шифрование одного сообщения тремя небольшими ключами троекратно повышает устойчивость всей схемы к взлому. На самом деле она остается примерно такой же, как если бы данные были зашифрованы одним ключом.
2. Разработчики думали, что размер их ключей слишком мал для использования метода решета числового поля.
3. Возможно, сотрудники ДИТ столкнулись с особенностями языка программирования Solidity, на котором написаны смарт-контракты для их блокчейна. Дело в том, что Solidity не умеет напрямую оперировать целыми числами, размер которых больше 256 бит.

Нужно увеличить длину ключей хотя бы до 2048 бит. Разработчики ДИТ пообещали, что увеличат размер ключей, — правда, только до 1024 бит.

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

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

Решить проблему проще — спрятать публичные ключи — нельзя. Без них вся система интернет-голосования не будет работать. Избиратель просто не сможет зашифровать свой бюллетень.

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

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

С другой стороны, анонимизация будет работать только в том случае, если технические исполнители интернет-голосования (в данном случае это сотрудники ДИТ Москвы) будут действовать честно. Наблюдатели не могут проконтролировать их действия.

Это не так. Годри показал, что можно будет следить за ходом голосования в реальном времени, а это противоречит российскому закону. В России публиковать результаты выборов можно только после окончания голосования. Предварительные данные могут мотивировать избирателей прийти и проголосовать (особенно если исход не определен) или, наоборот, остаться дома (так как ничего уже не изменить).

Мы не знаем. Заместитель гендиректора компании «КриптоПро» Станислав Смышляев заявил РБК, что такую уязвимость нашла бы любая лаборатория, аккредитованная ФСБ России. При этом заместитель руководителя ДИТ Артем Костырко на одной из встреч технической рабочей группы упоминал, что систему интернет-голосования проверяли специалисты из ФСБ и ФСТЭК. Главный редактор радиостанции «Эхо Москвы» и член Общественной палаты Москвы Алексей Венедиктов утверждал, что к тестированию системы голосования привлекались военные хакеры из ГРУ.

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

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

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

• Загрузите операционную систему Debian или Ubuntu. Можно запустить ее в виртуальной машине или в Windows с установленной подсистемой для Linux.
• Скачайте скрипт с сайта лаборатории. Не копируйте скрипт из препринта: во-первых, там обратные апострофы (`) ошибочно поменялись на кавычки (‘), во-вторых, он уже устарел.
• Выберите, какие ключи вы будете восстанавливать.
• Откройте терминал командной строки.
• Сделайте загруженный файл исполняемым.
• Запустите скрипт в терминале и ждите.

Добыв секретные ключи, довольно просто взять зашифрованные данные и получить исходное сообщение. Годри прислал «Медузе» код для алгебраической системы Pari/GP с примером расшифровки первой строчки сообщения, опубликованного 1 августа 2019 года. Как пояснил исследователь, он специально не стал автоматизировать этот процесс, опасаясь, что разработчики московского интернет-голосования не станут обновлять систему.

Да, можно — мы все посчитали за вас! Следите за репозиторием московской системы интернет-голосования. Последний раз разработчики ДИТ обновляли наборы публичных ключей и зашифрованных сообщений 7 августа. «Медуза» воспользовалась программой Годри и восстановила сначала секретные ключи:

1. 1393935061253186055964331093400654​5571226217500117326307030583977076​763344499
2. 2565177719999585878717260388222976​5380985053464236845790939731277353​558297286
3. 1078011785340015232642767248536152​8937136300033257083884184875333234​218384885

А затем с их помощью и первых три исходных сообщения:

1. 7438540792728440932827646081550800​7098689576133894315552148334378862​50488521
2. 1053929517477640963094586116689877​3173052252753697257641105742721542​071422795
3. 1414002331027548679611207416633822​5679441084383601852304419833648734​658806595

Когда (если) разработчики ДИТ опубликуют секретные ключи и исходные сообщения в своем репозитории, вы сможете их сверить.