Электронная подпись и голосование через интернет

[Darsh]

товарищ с почтой на мёртвом домене

Если уж так хочется пообщаться с товарищем - то почему бы не погуглить? :-)
https://www.usenix.org/legacy/events/ev ... asting.pdf ==> C. Andrew Neff [email protected]
:-)

А вообще мы тут, похоже, велосипед изобретаем... :-)
http://en.wikipedia.org/wiki/Election_technology
http://en.wikipedia.org/wiki/Electronic_voting_examples


Darsh

[Darsh]

Тем что это anonimity through honesty (I should coin that one). Сдампив левую и правую базу мы немедленно получаем соответствие голос ↔ личность.

А по-другому-то никак. Не предъявляя личность, не сможешь проголосовать.

Такие утверждение, в общем-то, принято сопровождать формальными доказательствами :)

Пожалуйста. Требуется:
1) обеспечить проверку права голоса;
2) обеспечить единственность голоса;
3) обеспечить анонимность голоса.

1) требует идентификации человека по базе избирателей, чтобы определить - имеет он право голосовать или нет. 2) требует проверки голоса избирателя по базе голосов, чтобы определить - проголосовал он уже или нет. 3) требует отвязать избирателя от голоса, что делает невозможным 1)+2).
Достаточно формально?

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

(Перечитав) согласен, утверждение "3) делает невозможным 1)+2)" несколько голословно. Но, хоть убей, я не вижу, как можно, сохраняя связку "один человек - один голос", отвязать при этом этого человека от этого голоса... На обычных выборах за этим человеком от получения бюллетеней до кабинки голосования физически следят, разрывая связку только в кабинке голосования. Как это реализовать в онлайне?..

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

(Мечтательно) Вот если бы полученный токен пользователь мог бы зашифровать one-waу так, чтобы он изменялся, не теряя при этом своей валидности для голосования - вот это было бы то, что нужно. Тогда он по-преждему годился бы для голосования, но по нему нельзя было бы свериться с базой человек-токен, чтобы определить, какой именно человек этот токен использовал...
Есть технология шифрования, которая позволяла бы такой финт?

Поразмышляю ещё. Идея с колодой карт интересна, но к латвийским выборам с их плюсиками и вычёркиваниями, увы, не вполне применима. Что, собственно, сам автор статьи и признаёт: "That protocol works well when ballots have only questions of a simple “choose (at most) m of n” type. This effectively precludes “write-in” responses".


Darsh

[popoffka]

Мне кажется, даже аудиты здесь не столь критичны (хотя и нужны) - keyserver'ы будут неявными аудиторами друг для друга, если для активации публичного ключа он должен будет зарегестрирован у большинства. Главная трудность - сохранить простоту процесса для тех, кому всё равно

Кстати, я тут подумал о штуке, которая должна бы тебе понравится. Что если идеи Certificate Transparency (штука, которую гугл предлагает для SSL сертификатов) применить к eP?
Т.е. скажем, что у человека не может быть одновременно двух валидных сертификатов (в т.ч. одной eID и одного виртуального eP). Обяжем LVRTC публиковать таймстампнутый и подписанный список записей вида (дата события, перс. код, хэш сертификата, новое состояние сертификата), где новое состояние — выдан или отозван. Тогда перед верификацией подписи легко проверить, что предъявленный сертификат — единственный валидный сертификат данного гражданина. Такой подход не позволяет гос-ву подписать ещё один сертификат на твоё имя, не отзывая настоящий. Поскольку из eID приватные ключи не извлекаются, то пользователи eID, получается, в полной безопасности.
Что самое классное, немножечко помудрив здесь, мне кажется, можно также сделать возможной публикацию «урезанной подписи» — т.е. verifier, проверяя подпись, сможет урезать подпись, выкинув из неё все личные данные, кроме ПК. Тогда такую подпись можно смело публиковать (можно ведь, правда? если я просто публикую чужой ПК, не давая никакого способа узнать, чей он, вряд ли я нарушаю FPDAL) и любой сможет проверить, что на момент верификации эта подпись действительно была валидна.

Если уж так хочется пообщаться с товарищем - то почему бы не погуглить?

«Почта на мёртвом домене» — это такой депрессивный комментарий о состоянии дел.

(Перечитав) согласен, утверждение "3) делает невозможным 1)+2)" несколько голословно. Но, хоть убей, я не вижу, как можно, сохраняя связку "один человек - один голос", отвязать при этом этого человека от этого голоса... На обычных выборах за этим человеком от получения бюллетеней до кабинки голосования физически следят, разрывая связку только в кабинке голосования. Как это реализовать в онлайне?..

Выше я уже предложил одну такую схему — собираем со всех граждан по ключу, а по пути все ключи перемешиваем (с технической т.з. это очень похоже на то, что ты предложил с необратимым шифрованием токенов). Г-н Neff утверждает, что для ElGamal/DSA это реализуемо.

[Darsh]

(Перечитав) согласен, утверждение "3) делает невозможным 1)+2)" несколько голословно. Но, хоть убей, я не вижу, как можно, сохраняя связку "один человек - один голос", отвязать при этом этого человека от этого голоса... На обычных выборах за этим человеком от получения бюллетеней до кабинки голосования физически следят, разрывая связку только в кабинке голосования. Как это реализовать в онлайне?..

Выше я уже предложил одну такую схему — собираем со всех граждан по ключу, а по пути все ключи перемешиваем (с технической т.з. это очень похоже на то, что ты предложил с необратимым шифрованием токенов). Г-н Neff утверждает, что для ElGamal/DSA это реализуемо.

Я не слишком въезжал в описанное г-ном Neff-ом, более-менее разобрал только про тасование колоды карт, но, если я правильно понимаю, чтобы расшифровать присланное гражданином, тебе понадобится именно его ключ. В данном случае у покера всего два игрока, а не все граждане плюс государство. А, получая ключ от гражданина, ты получаешь связку гражданин-голос - и анонимности каюк. Neff описывает покер на двоих, где колода - это бюллетени, и, тасуя их, ты таким образом скрываешь, какому именно ты отдал голос. В латвийских реалиях это не сработает, потому что игроку "гражданин" надо не просто выбрать одну карту из 15-20, предварительно зашифрованную игроком "государство", но ещё и расшифровать её, чтобы поставить плюсы-вычёркивания, а затем зашифровать обратно - что ломает всю схему.

Я больше думал про шифрование токена, которое добавит голосу анонимности, но по-прежнему позволит им воспользоваться. MD5, увы, не катит - зашифрованное гражданином MD5 можно проверить со стороны государства plain-text ключом - а его, в свою очередь, можно будет затем проверить на соответствие гражданин-токен. Какое-то решение должно быть. Токен надо зашифровать one-way (чтобы нельзя было получить из него обратно clear text и пробить по базе человек-токен), но чтобы при этом этот one-way можно было проверить и пометить по базе токен-голос.
Нет, всё равно не получается. Если можно проверить и пометить - значит, можно и идентифицировать по нему, кому он был выдан (при условии, что в обеих базах хранятся plain text токены).

Надо бы в базе человек-токен держать plain text - для выдачи гражданину, а в токен-голос класть MD5 hash токена. Тогда по MD5 hash нельзя будет определить, какому человеку этот токен принадлежит. А гражданин, предъявляя при голосовании plain text токен, позволит его сравнить с MD5 hash, хранящейся в базе токен-голос, чтобы проверить на валидность и пометить. Но здесь, увы, опять же слишком много доверия выдаётся государству - доверия, что оно зашифрует все токены, удалив при этом соответствие plain text - MD5 hash. Удалит - ура, схема работает. Не удалит - увы, опять дырка.
Хорошо бы доверить превращение plain text в MD5 hash самому пользователю - но тогда опять появляется связка человек-голос. Замкнутый круг :-(

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


Darsh

[popoffka]

Я не слишком въезжал в описанное г-ном Neff-ом, более-менее разобрал только про тасование колоды карт, но, если я правильно понимаю, чтобы расшифровать присланное гражданином, тебе понадобится именно его ключ. В данном случае у покера всего два игрока, а не все граждане плюс государство. А, получая ключ от гражданина, ты получаешь связку гражданин-голос - и анонимности каюк. Neff описывает покер на двоих, где колода - это бюллетени, и, тасуя их, ты таким образом скрываешь, какому именно ты отдал голос. В латвийских реалиях это не сработает, потому что игроку "гражданин" надо не просто выбрать одну карту из 15-20, предварительно зашифрованную игроком "государство", но ещё и расшифровать её, чтобы поставить плюсы-вычёркивания, а затем зашифровать обратно - что ломает всю схему.

Neff не описывает ни покер, ни выборы — он описывает криптографический примитив. Он предлагает применение своей схемы к электронным выборам, но оно работает не так, как ты говоришь.
Neff предлагает, по сути, следующее: пусть все пользователи просто сгенерят себе ключи для алгоритма подписей DSA/ElGamal и публичные части кинут серверу — в этот момент у сервера есть большой список публичных ключей и потенциально есть соответствие между каждым из ключей и конкретными гражданами. Дальше начинается перетасовка: приходит какой-нибудь гражданин, берёт все публичные ключи, «мутирует» каждый, перетасовывает и отправляет новый список ключей обратно на сервер, попутно доказывая, что никакие ключи не заменил. Тут суть в том, что «мутация» ключа — это односторонний процесс, т.е. наш гражданин меняет каждый публичный ключ на другой, но таким образом, чтобы владелец соответствующего приватного ключа мог посчитать приватный ключ и к новому публичному. Поскольку сервер не знает приватных ключей, после перетасовки он уже не может восстановить соответствие между ключами и гражданами. Перетасовка, конечно, может повториться несколько раз независимыми сторонами (а мне даже кажется, что список ключей можно дробить на части и каждую часть давать каждому гражданину на перетасовку ещё в тот момент, когда он сдаёт свой публичный ключ, чтобы весь процесс проходил быстрее и в нём поучаствовал каждый). Теперь на сервере есть публичные ключи, образованные от публичных ключей граждан, но без соответствия с личностями самих граждан, так что граждане могут спокойно голосовать новыми приватными ключами, просто подписывая свой голос, даже без какого-либо шифрования.

Признаюсь, что я пока до конца не понимаю, как именно работает эта «мутация» ключей, но если она действительно необратима (почти наверняка) и если новые ключи генерят подписи, не сопоставимые с подписями старых (вот в этом я пока не уверен), то этого должно бы быть достаточно.

P.S. Буквально на днях правительство Норвегии приняло решение отказаться от идеи выборов в интернете: http://www.regjeringen.no/en/dep/kmd/pr ... ?id=764300 http://www.zdnet.com/norway-internet-vo ... TRE17cfd61
Насколько могу понять из статей, причиной являются не технические сложности, а непонимание голосующими технологий, которые обеспечивали анонимность/честность выборов, в результате чего введение интернет-выборов не повлияло ни на доверие граждан к выборам, ни на явку.

[Darsh]

Хм. Почитаю его ещё - по идее, должно подходить под требование к перетасовке токенов.

А как предполагается оперировать таким диким количеством ключей? Поочерёдно подбирать к зашифрованному тексту или подписи все имеющиеся в наличии публичные, пока не подойдёт? Это ж только для Латвии в пределе полтора миллиона переборов к каждой записи, про расширение этой схемы на более людные страны я уж молчу. Решение получается немасштабируемое.
Или я что-то упускаю?

Кроме того, процесс требует уточнения. Как гражданин доказывает, что ни одного ключа не заменил? Как можно защитить систему от злонамеренных попыток её положить (DoS атака мутации ключей, скажем)?


Darsh

[Darsh]

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

А, мы это уже с микроматчами проходили :-)
И продолжаем проходить с новой формулой МАК-рейтинга :-)


Darsh

[popoffka]

А как предполагается оперировать таким диким количеством ключей? Поочерёдно подбирать к зашифрованному тексту или подписи все имеющиеся в наличии публичные, пока не подойдёт? Это ж только для Латвии в пределе полтора миллиона переборов к каждой записи, про расширение этой схемы на более людные страны я уж молчу. Решение получается немасштабируемое.
Или я что-то упускаю?

Я это вижу так: каждый гражданин может без особых проблем узнать, который из публичных ключей принадлежит ему (поскольку логи всего, что происходит с пулом ключей, в любом случае должны быть доступны), так что, отправляя свой голос, он может указать, которым из публичных ключей его следует проверять.

Кроме того, процесс требует уточнения. Как гражданин доказывает, что ни одного ключа не заменил?

Криптографическая магия Есть такой раздел криптографии — zero knowledge proofs, который занимается именно разработкой способов раскрывать какую-то информацию о данных, не раскрывая сами данные. Собственно, именно об этом Neff и распинается на двадцати страницах.

Как можно защитить систему от злонамеренных попыток её положить (DoS атака мутации ключей, скажем)?

Не совсем понимаю, что ты под этим имеешь в виду.

[Darsh]

Я это вижу так: каждый гражданин может без особых проблем узнать, который из публичных ключей принадлежит ему (поскольку логи всего, что происходит с пулом ключей, в любом случае должны быть доступны), так что, отправляя свой голос, он может указать, которым из публичных ключей его следует проверять.

Пожалуй, годится. Тогда его публичный ключ ищется в базе ключей, если находим, и он подходит - токен годится, голос принят, ключ помечен как "уже использованный".
Ещё вопрос: а как обычный пользователь генерит свой новый приватный ключ после мутации?

Как можно защитить систему от злонамеренных попыток её положить (DoS атака мутации ключей, скажем)?

Не совсем понимаю, что ты под этим имеешь в виду.

Системный вопрос: скольким мутациям можно подвергнуть базу ключей?
Со стороны пользователя: Какой объём информации надо скачать/закачать при мутации базы ключей? Какая нагрузка на процессор пользователя?
Со стороны центральной системы: насколько я понимаю, мутация ключей подразумевает удаление системой базы старых ключей при получении и положительной проверке базы новых. Это нагрузка на процессор, соответственно, не моментальная операция. Соответственно, параллельные запросы могут привести к тому, что два запроса взяли одну и ту же старую базу, затем один записал новую, затем второй её переписал. Либо же запрещать параллельные запросы - что, опять же, удар по масштабируемости, если толпа пользователей должна будет ждать, пока система переварит мутацию одного.

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

В общем, идея, наверное, правильная, надо только обмозговать, как бы её грамотнее применить...


Darsh

[popoffka]

Ещё вопрос: а как обычный пользователь генерит свой новый приватный ключ после мутации?

Пересчитывает свой старый по известной формуле.

Системный вопрос: скольким мутациям можно подвергнуть базу ключей?
Со стороны пользователя: Какой объём информации надо скачать/закачать при мутации базы ключей? Какая нагрузка на процессор пользователя?
Со стороны центральной системы: насколько я понимаю, мутация ключей подразумевает удаление системой базы старых ключей при получении и положительной проверке базы новых. Это нагрузка на процессор, соответственно, не моментальная операция. Соответственно, параллельные запросы могут привести к тому, что два запроса взяли одну и ту же старую базу, затем один записал новую, затем второй её переписал. Либо же запрещать параллельные запросы - что, опять же, удар по масштабируемости, если толпа пользователей должна будет ждать, пока система переварит мутацию одного.

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

Ну, тут много всего можно придумать. Я пока вижу это так: каждый пользователь, когда сдаёт свой ключ, заодно называет K случайных ключей, которые уже лежат в списке. Сервер выбирает ещё K других ключей из списка, полученные 2K ключей отправляет клиенту шаффлить. То есть каждый пользователь шаффлит только часть ключей. Правильно выбирая K и алгоритм выбора ключей сервером, по идее можем обеспечить эквивалентную безопасность, но тут нужно всё-таки просчитать вероятности заранее. Если есть сомнения, то можно после сбора ключей пару раз зашаффлить всё целиком — например, позволить каждой партии зашаффлить ключи один раз (примерно по аналогии с наблюдателями от партий в бумажных выборах).

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

В общем, идея, наверное, правильная, надо только обмозговать, как бы её грамотнее применить...

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