Alice 審計報告的 123

AMIS 是 Wallet Service 提供者。除了應用各種基本的安全加密技術,也積極地發展一些先進的密碼技術以強化系統安全。近期 AMIS 除了發佈跨雲備份之技術,更基於安全管理和私鑰之使用而開發 Alice 套件。開放 Alice 不僅是對本公司自行開發之套件深具信心,更是讓其他先進了解並進而檢核我們技術開發的嚴謹性。期許此套件能對整個區塊鏈社群發展產生正向的助益。HTSS 尚有其他發展的可能,歡迎任何有興趣的團隊與我們合作。

Image for post

目的:

AMIS 開源 Library(Alice):Hierarchical Threshold Signature Scheme。這是一個更安全使用數位簽章的套件,包含:

  1. 私鑰在整個使用的生命週期(i.e. 生成、簽名)永遠不會被組出。縱使 memory dump 發生,攻擊者得到私鑰的困難度極高。
  2. Proactive security:如果有些機密資訊在未察覺的情況下洩漏,Alice 可以在不改變私鑰的條件下自主定期更新機密資訊,使得讓洩漏的資訊無用化(i.e. 類似於 forward security)。這對將某些機密資料放在第三方單位(i.e. 比方說 AWS 或是 Google Cloud)的情境下,提供更安全的使用環境。
  3. Alice 也呼應社群的要求推出可以安全且動態調整機密資訊數量的 API。

除了以上所述,HTSS 還有其他的特點,請參考:

  1. 基本觀念介紹Introduction to Hierarchical Threshold Signature(revised version)
  2. Library 基本的使用指引Hierarchical Threshold Signature demonstration
  3. 英文 Audit 報告介紹:AMIS open sources Hierarchical Threshold Signature Scheme library (Alice)

AMIS 其他開源項目請參考此處


由於 Alice 是一個複雜且即將用於實務上的密碼套件。除了公開給社群的愛好者檢驗,AMIS 祈求提高其之安全性,雇用審計過很多密碼套件的 Kudelski Security 審閱。在他們專業且仔細的審計下,指出存在於 Alice 的缺陷:

  • 2 security issues of medium severity
  • 8 security issues of low severity
  • 13 observations related to general code safety

AMIS 團隊也在 Kudelski Security 團隊的協助之下將全部的 medium severity 和 low severity 快速提出修正(PS:可參考 Audit 報告)。對於剩下的 13 observations,AMIS 開啟對應的 git issue 去紀錄目前 AMIS 做了哪些改善。歡迎大家提出想法,AMIS 會持續地精進這個專案。

這邊文章目的是分享三個案例,希望大家將來不要犯同樣的錯誤。


案例 1:Hash of Multiple Inputs Without Domain Separation

場景描述:

在已實作的 Hash function 套件中,通常提供給人可以用來塞入訊息的 input 常常只有一個。然而實務上,使用者可能要 Hash 的資訊除了訊息本身還有時間…等多個 “變數”。該怎麼樣將多個 “變數” 安全的用只有一個 input 的 Hash function 實作出來是這個案例的挑戰。

危險實作方法:

假設我們現在有兩個 input:time 和 message。

一個常見的做法會利用 “串聯”,意指是將 time||message 串聯以後,再去計算 H(time||message)。但這其實是一種危險的實作方式。

這裡的 H 指的是一個 Hash function(e.x. SHA256, blake2b…. 等)。


WHY?

回憶一下,一個 Hash function 稱做被破解,意指可以找到兩個不同的 input 使得它們 Hash 的值相同。以符號來解釋是:

Image for post

有了以上的概念,便可以解釋串聯的實作問題在於:

time = 123 和 message = 456 跟 time = 12 和 message =3456

這兩組串聯的結果是一樣的:123456。

因此使用這樣的實作將會很容易構造出碰撞。因此違反 Hash function 的安全定義。


Solution:

第一個方法:若是每個變數都有固定的長度就可直接避免掉上面所說的問題。

第二個辦法:若是每個變數的長度是不固定的,可以使用適當的分隔符(i.e. 在這用的是 “,” )去分開每個變數。如果我們現在有 time 和 message 那我們就將這兩個變數 serialization 得到:[time, message]。

將此結果用 Hash 取值(i.e. H([time, message]))即完成所求。


案例 2:Modulo Bias in HashProtos

場景描述:

當在使用 Hash function 的時候,會希望 Hash 後的 output 在某個區間 [0,N-1] 的分佈是 uniform distribution(均勻分佈)。

uniform distribution 指的是任何一個在 [0,N-1] 數字,出現的機率都是1/N。

危險實作方法:

實務上會產生這個問題是因為我們用的橢圓曲線群 secp256k1 的個數是 N~256 bit ,但是 N < 2²⁵⁶ 且 Hash 函數(e.x. SHA256)的 output 是 256 bit。

更具體的來說,原本預期想構造一個 Hash function H

Image for post

但事實上 SHA256 會給你

Image for post

因此我們將以上的 SHA256 的 output 做以下的修正:

Image for post

危機便產生!


WHY?

在 N < 2²⁵⁶ 的情況下,以上實作的 output 會使得有些數字比方說 1 出現的機率很可能是其他數字的兩倍。因為

Image for post

因此使得 Hash function 的 output 不再是均勻分佈。

1. 這邊三條線等號指的是:1 跟 N+1 除掉 N 的餘數是相同的。

2. 這個實作在這情況危害很小,因為這樣實作的所產生的 distribution 和理想目標均勻分佈的 distance of distributions 是非常小的。為了嚴謹,仍然需要盡可能的解決。


Solution:

利用經典的統計方法 reject sampling 去解決這個問題。首先,如果我們接受以下的假設:

  • 假設 input 是均勻選取在 [0, 2²⁵⁶-1],則 Hash function 的輸出分佈是均勻分佈 [0,2²⁵⁶-1]。
  • 假設利用 serialization 方式將固定一個變數的雙變數轉成一個變數後,將其除以 2²⁵⁶ 的餘數之分佈也會是均勻分佈在 [0, 2²⁵⁶-1]。

在我們的狀況,對於給定的 message,我們新增一個 input 稱作 salt。

Image for post

利用隨機選取 salt 使得對同一個 message 而言,Hash function 的 output 會適當的變異在範圍 [0, 2²⁵⁶-1]。若是輸出的結果比 N 來的小,那我們就接受這組 salt 和 message。

因此我們藉由隨機且均勻的生成 salt,使得 H(salt, message) 的輸出分布也是均勻分佈,因此如果輸出的範圍不在指定的範圍我們就 reject,如果在我們就接受。這即是 reject sampling 的精神並且確實達到原本的需求。


案例 3:Paillier KeyGen Accepts Any Security Parameter

場景描述:

在使用 Paillier homomorphic encryption 時,我們需要生成私鑰和對應的公鑰。此密碼系統安全性是建立在公鑰的長度並且公鑰是由兩個相同 bit-length 的質數相乘。當用戶使用我們設計的系統時,需要一開始指定生成公鑰的長度。

不好的實作方法:

原本實作的方式,是允許用戶隨意指定 Paillier 系統中公鑰的長度。

WHY?

由於公鑰被人因式分解出是哪兩個質數則此系統等於被破解。一個基本事實是:隨著公鑰的長度越長,則因式分解會越困難達成。因此為了防止使用者使用過短的公鑰,因此應該要在程式中禁止產生太短的公鑰長度。

Solution:

設定最短允許的公鑰長度為 2048 bit。若是使用者使用的公鑰長度小於 2048 bit,則會跳出警告。2048 bit 是參考 NIST 的文件或是原始 GG18 paper

Image for post
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf

結論:

一個安全的 Library 除了上面討論,還應該包含有

  1. 記憶體控制
  2. 避免 Time Attack

…… 等。

根據 Audit 報告的建議,我們盡可能的修正,並且再次讓 Kudelski Security審閱認證其之安全性。歡迎大家使用我們的套件亦或是指正還可能存在的安全性相關 issue。最後希冀大家能藉由閱讀 Audit 的報告去了解如何更安全的實作自己開發的密碼套件。

Thanks to Yu-Te Lin, and Miya Chen.


本文由 AMIS ChihYun Chuang 提供

原文連結

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料