Re: [閒聊] 線上投票系統的認證與匿名

看板CSSE (電腦科學及軟體工程)作者 (鍵盤創業家)時間9年前 (2014/06/17 08:05), 編輯推噓6(607)
留言13則, 5人參與, 最新討論串2/3 (看更多)
※ 引述《yoco315 (眠月)》之銘言: : 想要了解一下,有沒有可能作到一種網路投票系統, : 同時具有「驗證身份合法性」的功能,以及「不具名投票」的特性? : 1. 只有合法的身份(透過自然人憑證或類似的)可以送出合法的封包 : 不合法的身份產生的封包在伺服器會被擋下來 : 2. 一個身份只能送出一次合法的封包 : 第二次以後就會被伺服器擋掉 : 3. 系統無法從單一投票封包看出該選民的選項是誰(以確保不具名投票的特性) : 但可以根據所有的投票封包統計出每一位候選人的得票數是多少 : 前兩個不難想像,但第三點我一直很卡 XD : 感覺就是數學或是密碼學問題,有沒有人對這方面有研究的? : 想要了解一下未來的人類社會是不是有機會能透過科技降低「直接民主」的門檻 : 不知道這樣的系統有沒有可能實現,防弊的能力如何… 這是有趣的問題 推文太長 打一堆不如回一篇好了 我沒讀過相關的論文 但知道盲簽章好像其中一個用途就是在做投票用的 所以就想如果是我來做會怎樣做 只是個大略的想法 我喜歡自己先想出方法來再看別人怎麼做 首先,這個方法用到盲簽 http://en.wikipedia.org/wiki/Blind_signature 它是基於 RSA 超長質數的算法變形,盲簽目前安不安全我不太清楚 假設它安全好了,或是有其它替代的安全方法 簡單的語言來解釋盲簽的話,就是 我把我寫的信和複寫紙裝在信封裡封好 交給某個人簽章,某人拿到這信封看不到裡面,但他可以在信封外簽名 簽好後拿回來,拆開,就得到了某個人簽章,但某人卻無法得知內容 以電腦處理的算法大約會是這樣 encrypted_text = encrypt(plain_text, public_key) signed_encrypted_text = ca_blind_sign(encrypted_text) signed_text = decrypt(signed_encrypted_text, private_key) 接著進入方法正題,定義幾個角色 投票者 - 一般投票的人 CA - 公證單位 計票者 - 負責計票的單位 1. 製造選票 首先,投票者造一張票 vote = (nonce, choose) 裡頭包含兩樣資訊 nonce - 一串夠長的隨機亂數 choose - 投票的選擇 這兩樣資訊不包含任何個人訊息,所以無法推回是誰投的票 為了不讓 CA 知道我投了誰,所以在送出前我先用自己的公鑰 (不太確定實作細節,但我想應該是) 進行盲簽加密 encrypted_vote = encrypt((nonce, choose), public_key) 2. 交由 CA 進行盲簽章 有了加密後的票,傳給 CA ,CA 在接受前要檢查自然人憑證 確認投票人的資格,及是否有重覆,沒問題的話,CA 會簽章 signed_encrypted_vote = sign(encrypt((nonce, choose), public_key)) 簽完後傳回給投票人 3. 投票人解密 投票人拿回來後解密 signed_vote = sign((nonce, choose)) 成為一張有效票 4. 投票人經由 P2P 或暱名網路傳給 計票者 投票人不直接傳給計票者,是因為這樣一做,可能就會因為連線的資訊 曝露了自己的身份,取而代之的方法,是透過 P2P 網路 像是 Tor ,或是專門設計的 P2P 網路,使用 P2P 網路還有個好處 計票者如果要惡搞很簡單,票明明有一千張,但我說我只看見五百張 可是如果是公開的 P2P 網路,大家票互相亂傳,這都是公開的 每個人都可以當計票者,或著說投票者也是計票者的一員 這除了有暱名的作用,還有順便監票的作用,有效票傳到每人手上 因為上面的簽章每人都可以驗 計票過程中,同樣 nonce 只會被算一次,如果出現兩張票以上 有著同樣的 nonce ,就全都視為廢票 接著來看這系統是怎樣滿足需求 1. 合法的身份才能投 這點自然人憑證之類的 PKI 系統做掉了,我們假設他們是安全的 (當然,可能還是有弱點,但談理論一般都只假設用的某項手法是安全的 實作的細節問題就暫不管他),所以這點問題不大 2. 同樣的人只能投一次 (或系統設定的次數) 在 CA 那邊的資料庫可以存這些,所以同一人第二次要求 CA 做盲簽時就會被拒決 3. 暱名性 票本身是不俱名的,傳送的手法也盡量保持暱名,所以是非常難以得知投票人是誰 你拿到一張票可能長這樣 ABD897FgljdF9aJL2Amqfo, "候選人 1 號" 前面是 nonce ,也就是無意義的亂數,後面是選擇,這些都無從推起投票人是誰 唯注意簽章不能帶有 timestamp ,否則 CA 可透過來盲簽的時間得知到底是誰投的 接著談談攻擊手法的各種可能性 1. nonce 碰撞攻擊 想讓你的票變廢票,就是開出一張跟你一樣 nonce 的票,但只要這是夠長的亂數 亂數產生器的品質夠好,你猜不到就沒辦法撞到我的 nonce,在這樣假設前提下 nonce 碰撞攻擊是無效的,除此之外,就算讓你猜得到好了,要讓我的票變廢票 你自己的票也會變廢票,也沒太大好處,不如去投對自己有利的人 另一種可能出現的情況是大家約好開同樣的 nonce 去投票,例如 "我愛大咪咪", "候選人 1 號" "我愛大咪咪", "候選人 2 號" "我愛大咪咪", "候選人 3 號" 像這樣也只是來搞笑投廢票的,他不投票或要投廢票都是一樣的,對選情沒影響 2. 有效票的複製 有效票在這系統裡本來就是設計給 P2P 節點到處亂傳的 在每張票都有一個獨一無二的 nonce 的情況下 除非出現 "同樣 nonce", "候選人 1 號" "同樣 nonce", "候選人 2 號" 同 nonce 不同選擇,才會被當廢票,在這種情況下 replay 攻擊應該起不了做用 除此之外,有效票有 CA 的簽章保護,除非能破解,但那又是另外的議題了 在這假設盲簽章是安全的 3. P2P 網路的篩選 透過滲透 P2P 網路確實是一個有可能的方法,但是要花的成本太高 只要參與的節點夠多,就很難被破解,你可以安插你自己的節點 遇到你的對手的選票全都丟掉,但你無法阻止正常的節點散播選票 如果這 P2P 網路加上獎勵機制的話,讓幫忙散播的正常節點有好處拿 攻擊者要競爭就更難了,只是詳細細節還得想怎樣做,但大致方向是這樣 4. CA 攻擊 整個系統看下來我想最大的弱點在 CA ,在這裡必須假設 CA 是公正無私 且不會被攻破的,否則,CA 能幹的壞事太多了,權力和信認太集中 其實都不是太好的設計,CA 要是想多給某人幾張票,這都沒法擋 所以我想要改進的話,最好是能拿掉 CA 這樣的角色,變成完全分散式的設計 不過這樣做又有個矛盾,在於投票可能無可避免需要有民眾的資料 要如何做到去中心化要能夠驗證民眾的身份 可能會非常困難 以上,只是一個很直觀的做法,可能還有我沒考慮到的問題和安全問題 歡迎提出來討論,如果有空的話蠻想實做這樣的專案來玩玩 非常有趣的題目 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 199.241.202.154 ※ 文章網址: http://www.ptt.cc/bbs/CSSE/M.1402963558.A.68A.html

06/17 10:07, , 1F
你可以參考我在上一篇貼的兩篇論文
06/17 10:07, 1F

06/17 10:10, , 2F
你講的在路線上看起來和論文裡的很接近了
06/17 10:10, 2F

06/17 10:11, , 3F
我猜在學界裡或 BTC 社群可以至少找到 prototype 實作
06/17 10:11, 3F

06/17 10:15, , 5F
這篇作者宣稱會出 prototype,但是我還沒去找
06/17 10:15, 5F

06/20 22:53, , 6F
碰撞那邊不太懂,同樣 nonce 會被算一次,所以攻擊
06/20 22:53, 6F

06/20 22:58, , 7F
沒事,看錯了,應該要說同樣 nonce 帶著不同資料就會被
06/20 22:58, 7F

06/20 23:00, , 8F
丟掉,而不是其中一筆會算進來。
06/20 23:00, 8F

06/21 02:59, , 9F
這邊有個 prototype: http://dedis.cs.yale.edu/dissent/
06/21 02:59, 9F

06/21 03:00, , 10F
TISSEC 已經接受, 在等出版的那篇論文分析各種可能的攻擊
06/21 03:00, 10F

06/21 03:01, , 11F
和 dissent 的防治方法, 小弟有幸 piggyback coauthor XD
06/21 03:01, 11F

07/27 06:30, , 12F
07/27 06:30, 12F

10/04 15:09, , 13F
好深遠阿 xd
10/04 15:09, 13F
文章代碼(AID): #1JduPcQA (CSSE)
文章代碼(AID): #1JduPcQA (CSSE)