Перейти к материалам
разбор

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

11 карточек
  • Что случилось?
  • Он правда взломал систему?
  • Как ему это удалось?
  • Почему разработчики выбрали такой маленький ключ?
  • И что теперь делать?
  • То есть теперь любой сможет понять, за кого я проголосовал?
  • Если анонимность голосования в безопасности, то этот взлом бессмысленный?
  • Российские спецслужбы знали об этой уязвимости?
  • Разработчики московской системы голосования признали взлом успешным?
  • Я могу повторить взлом системы голосования?
  • Я не буду сам ничего считать! Можно как-то иначе проверить?
1

Что случилось?

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

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

2

Он правда взломал систему?

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

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

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

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

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

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

3

Как ему это удалось?

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

Сотрудники ДИТ сделали ставку на систему асимметричного шифрования Эль-Гамаля. Шифрование там основано на операции возведения в степень. Поиск секретного ключа сводится к обратной задаче — вычислению дискретного логарифма. Это очень сложная задача, но чем меньше длина ключа, тем проще ее решить.

Кроме того, математики разработали специальные методы, которые позволяют немного ее упростить. Один из них — это общий метод решета числового поля. Для просеивания чисел через такое решето создано много специальных программ: в их числе CADO-NFS, одним из основных разработчиков которой является сам Годри.

Если интересно, есть про это лекция. Если не очень, можно обойтись и читать дальше — там и так все понятно.

Защита информации. Криптосистема Эль-Гамаля и инфраструктура открытых ключей
Лекторий МФТИ
4

Почему разработчики выбрали такой маленький ключ?

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

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

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

И что теперь делать?

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

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

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

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

6

То есть теперь любой сможет понять, за кого я проголосовал?

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

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

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

7

Если анонимность голосования в безопасности, то этот взлом бессмысленный?

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

8

Российские спецслужбы знали об этой уязвимости?

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

9

Разработчики московской системы голосования признали взлом успешным?

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

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

10

Я могу повторить взлом системы голосования?

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

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

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

11

Я не буду сам ничего считать! Можно как-то иначе проверить?

Да, можно — мы все посчитали за вас! Следите за репозиторием московской системы интернет-голосования. Последний раз разработчики ДИТ обновляли наборы публичных ключей и зашифрованных сообщений 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

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

Денис Дмитриев