關於 rsync algorithm 演算法

        因為專案需要, 我希望能夠稍微了解真正底層用到的rsync技術, 所以我選讀的這篇文章就是位於澳洲首都特區坎培拉的研究型國立大學, 由 Andrew Tridgell 和 Paul Mackerras 在 1996 年6月所發表 The rsync algorithm [1]這篇技術報告. 而 Andrew Tridgell 在 1999年的2月發表了博士論文 Efficient Algorithms for Sorting and Synchronization [2]. 而目前在 Linux/Unix 底下使用的 rsync [4] 指令是由 Wayne Davison 所維護. 而知名的 Dropbox 服務底層則是改良自 librsync [5].

        而這篇文章, 我主要是著重在於技術報告中提到的 Rolling Checksum 和 Checksum searching 的部份. 由於我並不是資工系畢業的, 也沒學過工程數學或是一些高深的數學演算法, 因此看這篇技術報告時, 只能搭配程式碼來研讀. 網路上其實有不少介紹 Rolling Checksum的文章, 也有對岸簡體文章在說明這部份. 但, 後來找到一個網站是 Jakob Jenkov 所寫的 RSync - Remote Synchronization Protocol [3] 中的 Checkums 章節. 才能比較理解 Rolling checksum 作法的好處, 以及如果要實作 Rolling Checksum 應該怎樣實作. 接著陸續找到一些網路上實作 Rolling checksum 的程式碼研讀後, 對於 Rolling Checksum 就比較能夠掌握.

The rsync algorithm:

        假設有兩台分別為 α 和 ß 的電腦.  α 電腦存取一個檔案 A, 且 ß 電腦存取一個檔案 B. 當檔案 A和檔案 B 具有類似的相同內容時. 在 α 和 ß 電腦之間要同步這個檔案時,可以透過 rsync 演算法來解決每次都要完整傳送整份檔案的困擾. rsync 演算法包含 5 個步驟

1.  ß 將檔案 B 分割成一系列不重疊的固定大小的區塊(Block), 區塊大小(Block size)的為 S bytes. 最後一個區塊的大小可能會小於 S bytes.
2.  ß 會把每一個區塊計算出兩個 checksums: 一個稱作 weak "rolling" 32-bits checksum. 另一個是 strong 128-bit MD4 checksum.
3. 接著 ß 將這些 checksums 都送給  α .
4. α 會對於檔案 A 中尋找在任何 offset 上所有大小 S bytes的區塊是否有相同的 weak and strong checksum 和 ß 所提供的相同. 這是透過 rolling checksum 的特性, 所以速度相當快.
5. 最後, α 會傳送一連串的intructions給 ß 來建構出檔案A的複製版本. 每一個 instruction 都會是參照到檔案 B的一個區塊或是 literal data. Literal data 指的是那些在檔案 A 中出現, 但是不符合檔案 B中任何一個區塊的資料. 

        最後,  ß 將會得到一個完整的檔案A的複製, 但是 α 只需要傳送部份檔案A中不存在於檔案B的資料 literal data 給 ß 就可以了. 

Rolling checksum:

        基本上, 如果你是學數學或是資工背景的, 看技術報告 Rolling checksum 章節的定義, 應該就完全能夠理解它所提的 weak rolling checksum 是怎樣運作的.

        在開始解釋它之前, 我們先回到前面 rsync algorithm 的第4個步驟, α 必須對於檔案A 中在任何 offset 上所有大小 S bytes 的區塊, 尋找是否有和  ß 所提供的區塊有相同的 weak and strong checksum. 假設, 檔案 A 的大小為 10 個 bytes, 而 ß 所提供的區塊大小 S 為 4 bytes 的資料給 α . 這時 α 必須從第 0 個 byte 開始比對且必須依序移動每一個 byte 後抓4個bytes的資料來比對, 最差的情況要6次才能比對完一個 ß 所提供第一個區塊資料. 請參考如下圖:

        透過前面這一個簡單的圖示, 我們可以知道, 如果檔案Ａ的資料很大時候,要比對完 ß 所提供的不同區塊, 它會是一個大量的資料運算.

        現在, 回到技術報告中所節錄的 Rolling checksum 定義如下:

        Rolling checksum 是由兩個值計算後所組成, 分別為 a (k, l) 和 b(k, l). 一個區塊的 block 的 Rolling checksum 可以用 s (k, l) 來表示. 而 s (k, l) = a (k, l) + (2^16)* b(k, l).  為了方便解釋, 這裡先會忽略掉 mod M 的部分. 此處我們可以節錄自 Jakob Jenkov 寫的 RSync - Remote Synchronization Protocol [3] 中的 Checkums 章節 中 Rolling Checksum Algorithm 的解釋, 以下的 A 其實就是表示 a(k, l), 而 B 就是表示 b(k, l).

data = 是指一個區塊(block)的資料
i    = index 是區塊上表示每一個 byte 的位置. 如果區塊大小為 4 bytes, 即 blockSize = 4.
       則 i = 0, 1, 2, 3          

        

a(k,l)即是 A = data[0] + data[1] + ... data[i];

b(k,l)即是 B = blockSize * data[0] + (blockSize-1) * data[1] + ... +
              (blockSize - i) * data[i] ... + 1 * data[blockSize-1];

        假設有一個區塊大小 4 bytes 的資料如下, 這個區塊的每個byte的值分別為 3, 5, 7, 9. 根據定義計算 A = a(0, i) 和 B = b(0, i) 的方式分別如下：

         而這個特性, 透過觀察可以得到 B 其實是每次的累加 A 所組成

A += data[i];
B += A;

        在 Jakob Jenkov 所寫的 RSync - Remote Synchronization Protocol [3] 中的 Checkums 章節 裡面有提到為什麼 A+= data[i] 後, 要算出 B只要用 B += A; 即可求出.

        因此, 當我們要移動 1 個 byte 來計算下 1 個 4 bytes長度區塊的 Rolling checksum 時, 我們並不需要重新完整算一次. 只需要知道下 1 個 byte的值. 就可以求出來 A 和 B 的值. (以下節錄自Jakob Jenkov的文章 )

start = start index of new block.
end   = end index of new block.  

A -= data[start-1];   //remove old, first byte.
A += data[end];       // 算出新的 A

B -= blockSize * data[start-1];
B += A;               // 算出新的 B

Checksum searching:

        根據技術報告中提到的 checksum searching, 它可以分為 3 個 Level 的 searching方式, 我用以下這張概念圖來解釋它.

        當 α 收到 ß 傳送過來的 checksums 資料時候, 會建立一個大小為 2^16的 Hash Table , 而每個 key 所存的值就是表示一個區塊 32 bits長度 Rolling checksum 的 hash值, 長度為 16 bits. 而 Hash Table每個 key 對應的 entry 可能會指向 null 也可能會指向一個 list 的資料. 這個 list 中的 Node 包含 Rolling Checksum 以及一個 Strong Checksum. 比對的方式如下:

1. 從A檔案中第 0 個byte開始, 抓出 block size大小的區塊算出 rolling checksum 以及 rolling checksum的 hash值. 如果 hash 值有符合就表示通過了 Level 1的 Check.
2. 當 Level 1 Check 通過後, 開始找 list 中的node比較其 rolling checksum是否符合.若有則表示通過 Level2 Check.
3. 一旦 Level2 Check通過, 就要把A檔案中的這個完整區塊的 strong checksum算出來和 node中的 Strong checksum 比對. 

        如果這個offset所取出的區塊在比對過程中有找到符合的, α 就要把目前 offset 以及對應到檔案 B 中的哪一個 block的資訊記錄下來, .如果完全都沒有比對到, 則繼續移動1個byte抓出相同 block size的區塊再比對一次.直到檔案A的所有區塊都比對過為止.

        另外, 以上這張概念圖中 Hash Table 的 key值是排序過的, 這和我們一般所熟知的 Hash Table的是稍微不同的.在 Efficient Algorithms for Sorting and Synchronization [2]論文中的 3.2 章節有一張圖如下, 這才是原作者在 rsync 中所實作的方式.

Reference:

[1] The rsync algorithm, June 1996

[2] Efficient Algorithms for Sorting and Synchronization, February 1999

[3] RSync - Remote Synchronization Protocol

[4] Samba Rsync - http://rsync.samba.org

[5] librsync - http://librsync.sourceforge.net
[6] How rsync works - http://rsync.samba.org/how-rsync-works.html

儲存 Password 安全性

Password

        Password 是大部份系統用來認證或是識別使用者最常見的方式，特別是網站系統最需要這種機制，來提供一般使用者進行登入取得瀏覽的權限或是使用網站的服務。網站系統最常見的保護方式就是在網頁上提供隨機的圖形驗證碼 CAPTCHA ，來避免有心人透過工具作自動化的方式暴力破解使用者的密碼。然而，一個系統的安全性取決於系統環節中最弱的一環。因此，擋得住網站系統前端，卻擋不住系統後端資料庫時，一旦被攻破資料庫時，若使用者的密碼沒有被保護而以明文(Plain-Text)的方式儲存時，這樣的系統可以說是完全沒有任何安全性。因此，比較有良心的開發人員，會透過其他方式來保護使用的密碼。

早期 Password 的保護方式

        早期對於Password的保護方式是透過 password + salt 方式，把這兩個值當作參數進行 Hash 運算(MD5, SHA1,SHA256...etc)，每一個 password 都需要搭配一個隨機產生的 salt，並且透過 One-way 的 Hash 函數算出一個亂數值的字串來存放。所謂的 One-way 的 Hash 函數是指無法透過知道 salt 和產生後的亂數值算出原本的 password。對於這方面的技術有興趣的可以參考 Slated Password Hashing 的文章。在過去硬體的運算能力不夠快的情況下，這樣的保護機制其實是足夠的。然而運算能力越來越強的情況下，這種保護機制隨即崩盤，請參考2012年Speed Hashing 的文章，裡面主要是提到GPU運算能力可以很容易的破解 SHA1+Salt 所保護的密碼。

建議的 Password 的保護方式

        目前(2013)在密碼學領域建議用來保護密碼的 key derivation function 我目前知道的有以下這幾種： scrypt, bcrypt, PBKDF2. 之前的專案曾經用Python版本的 bcrypt 來做 Password Protection的處理.

Reference

Salted  Password Hash - https://crackstation.net/hashing-security.htm

Scrypt - http://www.tarsnap.com/scrypt/scrypt.pdf

              http://www.tarsnap.com/scrypt/scrypt-slides.pdf

Using scrypt in Python and PostgreSQL - http://kevinryan.me/using-scrypt-in-python-and-postgresql/

Threat Modeling

        Threat Modeling 是在系統設計階段的早期, 以 Data Flow Diagram 為基礎, 來對整個系統設計做安全性威脅的分析. 而這個過程是一個重複的過程, 透過重複分析安全性的威脅, 並且提出相對應的解決方式,並且解加以驗證是否解決或是降低威脅性.

        然而, 它不僅只是在設計階段, 當系統增加功能或是改變原有的功能時, 也可以利用它來分析系統的變動是否出現安全性的威脅.

為了做 Threat modeling 的分析, 我們必須先將系統的 Data Flow Diagram 畫出來. 這個可以藉由微軟所提供的工具 SDL Threat Modeling Tool 來完成 Data Flow Diagram 以及後續的分析.

Data Flow Diagram (DFD)

        基本上 Data Flow Diagram 可以根據不同情況來畫出對應的 DFD. 並且依據每個DFD來進行分析. Data Flow Diagram 主要有 5 個 Elements 如下:

• Process
  以 High Level 的角度來看時, 它可以是Web Services或是在作業系統上的一個Service. 以 Detail Level 的角度上來看可以是一個DLLs或是一個EXEs的執行檔.
• Data Store
  通常指的是存放資料的地方, 常見的有資料庫,檔案或是Shared Memory甚至是Queue或Stack.
• External Entity
  通常指的是會與你的系統互動的使用者或是外部的 Systems 或 Services.
• Data Flow
  就是指以上 3 種 Elements: Process,External Entity以及 Data Store之間溝通的資料流.
• Trust Boundary
  是指不容易受到外部影響或是干涉內部運作的一個範圍的分界. 例如: 都在同一個Private Data Center 內部之間的Server溝通. 例如: 透過網路溝通的兩個 processes 通常會有一個 trust boundary 在它們之間, 即使他透過安全的通訊方式也是如此. 

        而畫 Data Flow Diagram 最重要的一個是畫出 Trust Boundary, 它主要的目的是用來判斷哪些 Data Flow的運作是具有安全性威脅.  舉例來說: 一個 Process 內部的 Thread 通常都算是 Trust Boundary 內的, 原因是 Thread 所擁有的權限都是由 Process 所提供且共享的. 常見的 Trust Boundary 例子有 Machine boundaries, privilege boundary, integrity boundary ...等等這些.
       
        此外, 我們也應該要檢視每一個 Processes 和 Data Stores 是否需要再進一步畫出更詳細的 DFD. 所以 DFD 通常又可以分為以下四種, 但是很少需要畫到 Leve 3, 大多只需要畫到 Level 2 就已經可以.

• Context Diagram
  非常 high-level 完整的 component 或是 product, system 之間的互動
• Level 1 Diagram
  High level 但是只針對某一個單一的功能或是情況的互動
• Level 2 Diagram
  多個功能中需要用到的 sub-component 比較詳細的部份
• Level 3 Diagram
  更為詳細部分

        最後, DFD 應該詳細條列出對應的假設或是相依性的關係. 一開始可以先以 High Level 的方式畫出 DFD, 之後可根據是否需要更詳細的解釋說明安全性在設計上的影響, 或是需要資料通過 trust boundary 的細節...etc. 來決定是否畫出更詳細的 Level 1 ~ Level 3 的 DFD.

        畫 DFD 時候, 需要透過以下幾個問題來驗證你的 DFD 能夠拿來做 threat modeling 分析.

• Data 如何產生? 來自於 external entities 還是來自於 data stores
• Data 用在什麼地方? 誰會使用它? 儲存這些資料的理由?
• Data 如何在不同的 Process 中傳遞.
• Data 被哪些 Process從 Data Store 存取

Identify Threats

        如果有安全性的專家參予其中分析是最好的, 如果沒有的話,可以透過 STRIDE 的步驟來檢視 DFD 中的每個 element. STRIDE 就是指以下這些:

• Spoofing 偽造
  例如: 申請類似的網址,偽裝某個知名的網站
• Tampering 竄改
  例如: 修改軟體所需要的DLL植入惡意程式,或是竄改封包的內容
• Repudiation 否認
  例如: 否認發送過某個 Email, 或拒絕承認瀏覽過某個網站
• Information Disclosure 資訊外洩
  例如: 無論是惡意或是無意, 將重要的客戶資料流出, 讓未經授權的人使用.
• Denial of Service 中斷服務
  例如: 系統無法運作, 或是網站無法服務
• Elevation of Privilege 提高權限
  例如: 讓一個遠端一般使用者,透過非正常的管道,提升權限能夠執行一些只有系統管理員才能使用的指令集.

        對於DTD中的每一個Element而言, 都有個別需要注意的威脅如下圖:

       
   
相對於以上這些威脅, 必須有效的降低它們所造成的風險, 每一種威脅都有對應的解決方案.

Reference:

• Introduction to Threat Modeling - Microsoft (.ppsx )
• Security Design by Threat Modeling
• Managing Software Security Risks using Application Threat Modeling 
• Improving Web Application Security: Threats and Countermeasures - Chapter 3 Threat Modeling
• OWASP - Threat Risk Modeling 

Python M2Crypto - RSA 的 Encrypt, Decrypt, Sign and Verify

        這裡要介紹一些RSA基本知識，以及如何產生一把 RSA 的非對稱式(asymmetric) 公開金鑰 (public key)和 私有金鑰(private key)。並且用一個簡單的範例程式來解釋如何用RSA來進行加密解密和簽章驗證的應用。

RSA的基本知識和重要名詞

        RSA是一種asymmetric演算法，它是透過一組public key和private key來進行Encrypt/Decrypt或是Sign/Verify。它的優點是：資料交換過程當中，雙方只需要拿到對方的public key即可加密資料，然後將加密後的密文(cipher)傳送給對方。只有正確的接收者才會有private key能夠解出密文(cipher)。缺點是，加密或是解密的效能較差不適合用於大量的資料加密。RSA的private key的建議長度最少是1024 bits以上，才具有基本的安全性, private key長度越長所需要的加解密運算成本越高,相對也會更加安全。

Key Length

        RSA 的Key Length 決定了RSA被破解的強度，長度越長基本上越難以被破解。但是，不是永遠不能破解，只是目前還沒有提出有效的破解方法。

Public Exponent

        公開指數是為了滿足RSA演算法所需要的一個整數，而且必須是質數Exponent ，然而很多密碼學的函式庫所內建的RSA Public Exponent都是65537的質數。有個討論在探討RSA Public Exponent 選擇 3 是否不夠安全的問題，有興趣的可以參考這網頁。無論如何，基本上選擇 65537的質數應該是一個較為安全且建議的作法。雖然選擇過大的質數會影響解密和驗證的效率，但是除非是要應用在運算能力非常弱的環境上，否則選擇小的質數當作Public Exponent應該不建議的，特別是Padding Mode很差的情形。但是，若選用合適的Padding Mode時，即使選擇3當作 RSA Public Exponent對於安全性並沒有太大的不同。

Padding Mode

        RSA基本上必須透過隨機的Padding方式，以確保即使每次都加密相同明文(Plan-Text)時候，不會產生完全相同的密文(Cipher-Text)。而OpenSSL支援 4 種 Padding Modes，以下截取自OpenSSL官方文件。而M2Crypto目前只支援 RSA_PKCS1_PADDING 和 RSA_PKCS1_OAEP_PADDING，根據官方文件上的建議就是使用 RSA_PKCS1_OAEP_PADDING。
• RSA_PKCS1_PADDING
• RSA_PKCS1_OAEP_PADDING
• RSA_SSLV23_PADDING
• RSA_NO_PADDING

RSA Encrypt / Decrypt 的基本範例程式解說

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import M2Crypto import M2Crypto.BN as BN def generate_keypair_as_pem(key_len, exponent): def empty_callback(): pass rsa = M2Crypto.RSA.gen_key(key_len, exponent, empty_callback) # Get RSA Public Key in PEM format buf = M2Crypto.BIO.MemoryBuffer('') rsa.save_pub_key_bio(buf) public_key = buf.getvalue() # Get Private Key in PEM format buf = M2Crypto.BIO.MemoryBuffer('') rsa.save_key_bio(buf, None) private_key = buf.getvalue() # RSA Private Key return (public_key, private_key) if __name__ == '__main__': keylen = 1024 # 1024 bits exponent = 65537 padding = M2Crypto.RSA.pkcs1_oeap_padding # Generate RSA key-pair in PEM files for public key and private key public_key, private_key = generate_keypair_as_pem(keylen, exponent) message = 'This is a plain text data' # Use public key to encrypt 'message' buf = M2Crypto.BIO.MemoryBuffer('') buf.write(public_key) rsa1 = M2Crypto.RSA.load_pub_key_bio(buf) cipher_message = rsa1.public_encrypt(message, padding) # Use private key to decrypt 'cipher_message' rsa2 = M2Crypto.RSA.load_key_string(private_key) plaintext_message = rsa2.private_decrypt(cipher_message, padding)

1. 使用RSA演算法之前，必須產生 RSA 金鑰(Public Key and Private Key Pair)
2. 第 22 和 23 行指定 key長度為 1024 bits，選用的public exponent 為 65537 
3. 產生 RSA Key-Pair 在第 8 行，透過 M2Crypto.RSA.gen_key 函數並指定 key 長度和 public exponent。第 3 個參數基本上只要給 empty_callback 即可，若是沒有給時，你呼叫這個函數會在 standard output 中出現類似....++的符號。它只是用來表示初始化  RSA key-pair 的進度狀態。此時我們可以取得 RSA 的 instance，存在 rsa 變數中。
4. 分別取得 RSA public key 和 private key。M2Crypto 提供的方法，會將 Public key 和Private key 轉成 PEM 格式。
5. 第 10 ～12 行是取得 RSA public key 的方式，第 15 ～17 行是取得RSA private key的方式。差別在於 rsa.save_key_bio(buf, None) 的第 2 個參數設定為 None的原因，是希望直接取得真正的 RSA private key 而不要再經由 aes_128_cbc的方式來保護。否則執行到這段程式碼時，系統會在 console 要求使用者輸入 passphrase 。細節請參M2Crypto官方文件。 但是，一般來說如果是要存在系統中某個地方時候，是會透過另一種加密演算法來保護這把 RSA private key。
6. 第 31 ～33 行是載入 RSA public key 取得 RSA的 instance 存在變數 rsa1 中，第 34 行呼叫  rsa1.public_encrypt(message, padding)來加密明文(Plain Text)，其中指定 padding mode 為 OEAP Padding 。
7. 第 37 ～38 透過 RSA private key 解開密文(Cipher Text)，也必須指定相同的 padding mode 。

RSA Sign and Verify Signature 的基本範例程式解說

以下這個範例，是 sender 以安全的方式傳送一個 message 給 receiver 的 RSA 常見的應用。為了方便解釋，以下我們稱 A 為 sender, Ｂ為 receiver 。它大致上有 7 個步驟如下：

1. Ａ與Ｂ各自產生一個 RSA的 key-pair (private and public key)
2. Ａ與Ｂ交換自己的 public key。
3. Ａ使用Ｂ的 public key來加密訊息產生 Cipher message。
4. Ａ再使用自己的 private key 來為 Cipher message 產生 Signature。
5. 然後 Ａ 把 Signature 和 Cipher message 傳送給 B。
6. B 必須用 Ａ的 public key 來驗證所收到的 Signature 是否正確。
7. B 再用自己的 private key 來解開 Cipher Message，即可得到Ａ傳送的訊息內容。 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

import M2Crypto import M2Crypto.BN as BN def generate_keypair_as_pem(key_len, exponent): def empty_callback(): pass rsa = M2Crypto.RSA.gen_key(key_len, exponent, empty_callback) # Get RSA Public Key in PEM format buf = M2Crypto.BIO.MemoryBuffer('') rsa.save_pub_key_bio(buf) public_key = buf.getvalue() # Get Private Key in PEM format buf = M2Crypto.BIO.MemoryBuffer('') rsa.save_key_bio(buf, None) private_key = buf.getvalue() # RSA Private Key return (public_key, private_key) def get_data_digest(data): msg_digest = M2Crypto.EVP.MessageDigest('sha256') msg_digest.update (data) digest = msg_digest.digest() return digest def generate_secure_msg(A_private_key, B_public_key, message): padding = M2Crypto.RSA.pkcs1_oaep_padding buf = M2Crypto.BIO.MemoryBuffer('') buf.write(B_public_key) rsa1 = M2Crypto.RSA.load_pub_key_bio(buf) cipher_message = rsa1.public_encrypt(message, padding) # Use A's private key to sign the 'cipher_message' digest1 = get_data_digest(cipher_message) rsa2 = M2Crypto.RSA.load_key_string(A_private_key) signature = rsa2.sign(digest1, 'sha256') return cipher_message, signature def read_secure_msg(A_public_key, B_private_key, cipher_message, signature): try: # Use A's public key to verify 'signature' buf = M2Crypto.BIO.MemoryBuffer('') buf.write(A_public_key) rsa3 = M2Crypto.RSA.load_pub_key_bio(buf) # Verify digest2 = get_data_digest(cipher_message) rsa3.verify(digest2, signature, 'sha256') # Use B's private key to decrypt 'cipher_message' rsa4 = M2Crypto.RSA.load_key_string(B_private_key) padding = M2Crypto.RSA.pkcs1_oaep_padding plaintext_message = rsa4.private_decrypt(cipher_message, padding) return plaintext_message except Exception as err: print 'Verify Fail:%r'% err raise if __name__ == '__main__': keylen = 1024 # 1024 bits exponent = 65537 padding = M2Crypto.RSA.pkcs1_oaep_padding # Generate RSA key-pair in PEM files for public key and private key A_pub_key, A_priv_key = generate_keypair_as_pem(keylen, exponent) # Generate RSA key-pair in PEM files for public key and private key B_pub_key, B_priv_key = generate_keypair_as_pem(keylen, exponent) # A is sender, B is receiver msg = 'A want to send this message to B' # Sender's behavior cipher_msg, signature = generate_secure_msg(A_priv_key, B_pub_key, msg) # Receiver's behavior plain_text = read_secure_msg(A_pub_key, B_priv_key, cipher_msg, signature)

附註：
        實務上 RSA 通常都會搭配 AES 做 secure key 的保護，純粹是根據你所要保護的資料大小以及應用所著重的特點而有不同，此外 RSA 並不適合用來加密大量資料。

Reference:

• M2Crypto https://pypi.python.org/pypi/M2Crypto
• OpenSSL http://www.openssl.org
• Block Cipher mode of operation https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
• RSA algorithm http://www.di-mgt.com.au/rsa_alg.html
• Generating CA certs and CA signed certs using python m2crypto https://gist.github.com/eskil/2338529

Python M2Crypto - AES 的 Encrypt 與 Decrypt

        這邊要介紹有關 AES 的 Encrypt 和 Decrypt ，其中會介紹一些 AES 的基本知識和相關名詞以及一個簡單的範例程式說明。

AES的基本知識

        AES(Advanced Encryption Standard)是一種對稱式(symmetric)的加密演算法，是透過對每個固定大小的4x4位元矩陣區塊(block = 128 bits = 16 bytes)，對其每一個元素進行多次交互置換和XOR運算。簡單來說，就是用同一把 secret key 進行Encrypt和Decrypt的動作。優點是對於資料大的檔案加解密的速度較快，而且容易透過硬體實作，運算所需要的記憶體較少，但是缺點是在資料交換的過程中，雙方必須取得這把相同的secret key。否則，接收到加密檔案的接收者，無法解開加密後的檔案。而它的安全性強度取決於金鑰(secret key)的長度，目前美國國防安全局審核認定的AES標準演算法secret key長度有128 bits, 192 bits和256 bits 三種。secret key的長度越長就越安全，但是相對的加密所需的時間就越多，然而實際上secret key長度對於加密時間的影響並不大，主要還是取決於所選擇的 Block Cipher Mode以及需要加密的資料大小。

AES演算法中常見的專有名詞

        在AES演算法中，不管是網路上的文章或是API文件中，常見到以下這些名詞：

Initialization vector (IV)

        "初始化向量"或稱"起始變數"，它的用途主要在於避免相同的資料加密多次都產生相同的密文(Cipher Text)。因此，使用上必須要注意的是，相同的一把金鑰(secret key)在加密的時候，不可以使用相同的 IV，否則就破壞了AES的安全性。此外 IV 本身並不需要保護，它是可以被公開的。而IV的最大長度必須是 16 bytes，而且產生IV的方式必須是無法預測的，也就是隨機產生即可。

以下是關於幾種常見的IV類型：
(1) Fixed IV
　　顧名思義就是，在使用同一把金鑰(secret key)在加密的時候，所使用的IV都是固定的。這會造成兩個相同的 plain-text 的區塊，產生的 cipher-text 區塊是相同的。

(2) Counter IV
　　是指在使用同一把金鑰(secret key)在加密的時候，每次加密一個訊息時，都將 IV 累加 1。

(3) Random IV
　　是指隨機產生一個亂數當作 IV。建議的作法是將第一個 IV 當作密文的第一個 cipher-text 區塊。從第二個 cipher-text 區塊才是真正的加密資料。

(4) Nonce-Generated IV
　　是指使用相同的一把金鑰(secret key)在加密的時候，用一個 nonce 來產生 IV 。nonce 是指 number used once 的意思，主要的精神在於同一把金鑰(secret key)不可以使用相同的 nonce。例如：假設選擇 nonce = 0 開始後，使用相同的一把金鑰(secret key)在加密的時候，不可以出現使用 nonce = 0 第 2 次。

Padding

        由於AES加密過程，是針對每個固定大小的區塊(16 bytes)，進行多次的交互置換和XOR運算，因此當需要被加密的資料小於矩陣區塊16 bytes 的時候，或是資料的size 不是 16 bytes的倍數時，為了讓加密能夠順利進行，必須將資料的 size 補齊到能夠被 16 bytes 整除的大小。舉例來說，假設需要保護的資料總長度只有 5 bytes，那在進行AES加密之前，必須補齊資料長度達到16 bytes。至於，不同補齊的方式可以參考 Use Padding in Encryption 這篇文章。

特別註記，以下的圖出自於維基百科 (https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation)

Block cipher mode 

• ECB (Electronic codebook，ECB)
  ECB是對於每一個資料區塊都用同一把金鑰(secret key)去加密，而且沒有使用 IV。缺點是在於相同的資料區塊，加密後的密文(Cipher Text)會是相同的。優點是每個區塊都可以獨立進行加密，因此可同時對每個區塊進行加密。
  
  
• CBC (Cipher-block chaining)
  CBC是一種串鏈的加密方式，第一個資料區塊必須加入IV和金鑰(secret key)進行加密，之後將加密後的密文(Cipher Text)作為第二個資料區塊的IV再加上金鑰進行加密，以此類推下去，直到所有區塊都被加密完成。這種方式在加密過程當中，下一個區塊必須依賴這個區塊加密後的結果才能夠得到IV，因此無法同時進行。但是在解密的時候，可以同時對所有區塊進行解密，因為前後兩個密文(Cipher Text)區塊，後面的密文區塊要解密時候所需要的IV就是前一個密文區塊。
  
  
• CFB (Cipher feedback)
  CFB 則是將 IV 和金鑰(secret key) 產生出 密文(Cipher Text)區塊，然後把密文(Cipher Text)區塊和明文資料區塊進行XOR運算後的值，當做下一個資料區塊的IV再和金鑰(secret key)產生出下一個密文區塊，以此類推下去做相同的運算，直到所有區塊都被加密完成。
  
  
• OFB (Output feedback)
  OFB 則是將 IV 和 金鑰 (secret key) 產生密文區塊(Cipher Block)，然後將Cipher Block和明文區塊 PlainText 進行 XOR 運算。而這個區塊產生的 Cipher Block 則當作下一個資料區塊加密處理所需的 IV。
  
  
  
  
  
• CTR (Counter)
  CTR 則是先透過所謂的 nonce (其實就是IV) 加上可以在長時間內每次都產生不重復 sequence 整數的 counter 所組合出來的一個整數值, 接著用同一把金鑰 (secret key) 對這個整數值加密後的產生一個密文區塊 (Cipher Block), 最後把這個密文區塊和明文區塊(PlainText)進行XOR運算。這種做法每個區塊都可以獨立地進行加密或是解密，因此可運用在平行處理的加解密運算。
  
  

AES Encrypt / Decrypt 基礎範例程式解說

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

import M2Crypto.EVP as EVP import cStringIO ENCRYPT_OP = 1 DECRYPT_OP = 0 def aes_encrypt(iv, secret_key, plain_text): cipher = EVP.Cipher(alg='aes_128_cbc', key=secret_key, iv=iv, op=ENCRYPT_OP) input_buffer = cStringIO.StringIO(plain_text) cipher_data1 = cipher.update(input_buffer.read()) cipher_data2 = cipher.final() input_buffer.close() output_buffer = cStringIO.StringIO() output_buffer.write(cipher_data1) output_buffer.write(cipher_data2) cipher_text = output_buffer.getvalue() output_buffer.close() return cipher_text def aes_decrypt(iv, secret_key, cipher_text): cipher = EVP.Cipher(alg='aes_128_cbc', key=secret_key, iv=iv, op=DECRYPT_OP) input_buffer = cStringIO.StringIO(cipher_text) plain_text1 = cipher.update(input_buffer.read()) plain_text2 = cipher.final() input_buffer.close() output_buffer = cStringIO.StringIO() output_buffer.write(plain_text1) output_buffer.write(plain_text2) plain_text = output_buffer.getvalue() output_buffer.close() return plain_text if __name__ == '__main__': IV = 'c782dc4c098c66cb' # 16 bytes secrect_key = 'c286696d887c9aa0' # 16 bytes data = 'This is a 48-byte message (exactly 3 AES blocks)' cipher_text = aes_encrypt(IV, secrect_key, data) plain_text = aes_decrypt(IV, secrect_key, cipher_text) print('Cipher Text length is %d bytes'% len(cipher_text)) print('Cipher Text is as following') print('####################') print(cipher_text) print('####################') print('Plain Text=%s'% plain_text)

        EVP是OpenSSL針對對稱式加密所提供的模組，它針對某些對稱式(Symmetric)密碼學演算法在處理加密或是解密時，所需要的API規格。

1. 因此在加密或是解密之前，需要產生一個Cipher的物件來負責加密或是解密。
2. 初始化Cipher物件時，第 8 和 27 行程式的 alg 參數指定使用 128-bits 長度的 AES-CBC模式的演算法。這個 alg 參數在AES演算法的使用上，可以指定以下幾種分別代表不同長度和模式：
• ECB
• aes_128_ecb 
• aes_192_ecb
• aes_256_ecb
• CBC
• aes_128_cbc
• aes_192_cbc
• aes_256_cbc
• CFB
• aes_128_cfb
• aes_192_cfb
• aes_256_cfb
• OFB
• aes_128_ofb
• aes_192_ofb
• aes_256_ofb
3. 初始化Cipher物件時，第 9 和 28 行程式的 key 參數是用來指定加密或是解密時，所需要用到的金鑰(secret key)。它的長度至少需要128 bits 也就是16 bytes。若你是使用aes_256_cbc模式，則金鑰長度必須為256 bits 等於 32 bytes長度。
4. 初始化Cipher物件時，第 10 和 29 行程式的 iv 參數是用來指定初始向量(Initialization vector)，它的最大長度為 16 bytes。
5. 初始化Cipher物件時，根據要做加密或是解密來決定 op的參數。若是用於加密，則 op 參數要設定為 1 。反之，用於解密時，則 op 參數必須指定為 0。
6. 在程式碼的的 第 47 行，我們選定的 IV 長度為 16 bytes 。根據我的實驗結果，在M2Crypto API 使用上，即使所給的 IV不足 16 bytes，它還是可以執行。在 secret key不變的情況下，每次執行後的密文都會改變。但是，如果指定的 IV 剛好是 16 bytes長度時，執行多次後的密文是相同的。如果指定的 IV 長度大於  16 bytes，則超過16 bytes後的資料將不會被當做 IV 使用。然而，演算法上 IV 的長度應該要取決於你所使用的 AES mode 與金鑰長度來決定。
7. 在程式碼的第 48 行，我們選定的 secret key 長度為 16 bytes 。因為這個範例程式指定的 AES模式為 aes_128_cbc，就 AES 128 bits 加密所需要的長度就是16 bytes 。但是，在 M2Crypto API 使用上，它的行為和 IV 有類似的狀況。以這個範例來說，如果 secret key 少於 16 bytes 而 IV 不變的情況下，對相同的資料加密後所產生的密文，對相同的資料執行多次後的密文都會不同。但是，如果 secret key 剛好指定 16 bytes 時候，對相同資料執行多次加密後所得到的密文是相同的。如果指定的 secret key 超過 16 bytes 時候，超過16 bytes 後的資料不會被當作 secret key來使用。

Important warring: You should select the correct cipher mode,  for example: CCM or GCM mode. (Update 2022/03/04) The reason is the CBC mode is vulnerable to padding oracle attacks.

Reference:

• M2Crypto https://pypi.python.org/pypi/M2Crypto
• OpenSSL http://www.openssl.org
• AES CBC和CTR加解密實例 http://www.metsky.com/archives/585.html
• Block Cipher mode of operation https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
• Use Padding in Encryption http://www.di-mgt.com.au/cryptopad.html

Python GUI in Tkinter

過去也曾透過Java Swing進行GUI Programming，2008年工作時上需要透過Python來開發GUI。從沒寫過Python 到開始寫用Tkinter來開發GUI程式，大概花了幾天。 目前，撰寫plus-in讓Python能夠透過去連Serial Console， 另外還把一些C的Header檔案和陣列的宣告和使用進行簡易的 Parsing和Link並resolve出一些Constants的值以及Configuration資訊。 接著根據這些資訊透過Python自動產生GUI。

說實在的，我用的很不習慣。特別是它的Layout只有三種管理的方式Pack、Grid、Place三種，讓我覺得Twinter不是非常直覺。我是覺得用它來寫一些簡單方便的GUI還可以，如果要拿來寫複雜的視窗程式 可能會花很多時間。否則就要另外在包一層這樣用起來會比較順手。

Tkinter主要的事件反應都是透過configure每個Widget所對應的處理函數。以Button來說，透過指定command對應的函數，當Button發生press事件時會呼叫對應的函數。

以下這張圖是Demo1.py執行的結果，這個範例中SHOW_JF1、SHOW_JF2 與SHOW_JF3三個Button分別透過三種寫法來處理Button的事件反映。



Demo1.py的程式碼如下所示：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
from Tkinter import *

class ActionListener:
    main = None
    def __init__(self, main):
        self.main = main;

def action(self):
        print("ActionListener!");
        self.main.showJF2();

class Main:

    def __init__(self):   
        tk = Tk();
        self.mjf = Frame(tk, borderwidth = 3, relief=SUNKEN);   
        self.jf1 = Frame(self.mjf);
        self.jf1.configure(borderwidth = 3, background = "green", relief=GROOVE);

        bt1 = Button(self.jf1, text="JF1");
        bt2 = Button(self.jf1, text="JF1");
        bt3 = Button(self.jf1, text="JF1");
        bt1.pack(side = LEFT, fill=BOTH, expand=YES);
        bt2.pack(side = LEFT, fill=BOTH, expand=YES);
        bt3.pack(side = LEFT, fill=BOTH, expand=YES);


        self.jf2 = Frame(self.mjf);
        self.jf2.configure(borderwidth = 3, background = "red", relief=RIDGE);

        bt1 = Button(self.jf2, text="JF2");
        bt2 = Button(self.jf2, text="JF2");
        bt3 = Button(self.jf2, text="JF2");
        bt1.pack(side = LEFT, fill=BOTH, expand=YES);
        bt2.pack(side = LEFT, fill=BOTH, expand=YES);
        bt3.pack(side = LEFT, fill=BOTH, expand=YES);        



        self.jf3 = Frame(self.mjf);
        self.jf3.configure(borderwidth = 3, background = "yellow", relief=RIDGE);
        bt1 = Button(self.jf3, text="JF3");
        bt2 = Button(self.jf3, text="JF3");
        bt3 = Button(self.jf3, text="JF3");
        bt1.pack(side = LEFT, fill=BOTH, expand=YES);
        bt2.pack(side = LEFT, fill=BOTH, expand=YES);
        bt3.pack(side = LEFT, fill=BOTH, expand=YES);

        btFrame = Frame(tk);
        bt1 = Button( btFrame, text="SHOW_JF1");
        bt2 = Button( btFrame, text="SHOW_JF2");
        bt3 = Button( btFrame, text="SHOW_JF3");
        
        #[ 1. Anonymous Callback Function with arguments
        bt1.configure(command = lambda s=self, event="JF1": s.showJF(event));

        #[ 2. ActionListener with arguments
        bt2.configure(command = ActionListener(self).action);

        #[ 3. Direct Callback Function
        bt3.configure(command = self.showJF3);

        bt1.pack(side = LEFT, fill=BOTH, expand=YES);
        bt2.pack(side = LEFT, fill=BOTH, expand=YES);
        bt3.pack(side = LEFT, fill=BOTH, expand=YES);

        btFrame.pack(side = TOP)
        self.mjf.pack(side = TOP, fill=BOTH, expand=YES);

        newBtFrame = Frame(tk);
        newBtFrame.pack(side = TOP ,fill=X, expand=YES);
        bt1 = Button( newBtFrame, text="Bottom Button1");
        bt2 = Button( newBtFrame, text="Bottom Button2");
        bt1.pack(side=LEFT);
        bt2.pack(side=RIGHT);

        self.showJF("JF2");

    def showJF(self, event):
        print("Anonymous Callback Function with arguments");
        if(self.currJF != None):
            self.currJF.pack_forget();

        if (event=="JF1"):
            self.jf1.pack(side = TOP, fill=BOTH, expand=YES);
            self.currJF = self.jf1;

        if (event=="JF2"):
            self.jf2.pack(side = TOP, fill=BOTH, expand=YES);
            self.currJF = self.jf2;

        if (event=="JF3"):
            self.jf3.pack(side = TOP, fill=BOTH, expand=YES);
            self.currJF = self.jf3;
           
    def showJF2(self):
        if(self.currJF != None):
            self.currJF.pack_forget();

        self.jf2.pack(side = TOP, fill=BOTH, expand=YES);
        self.currJF = self.jf2;

    def showJF3(self):
        if(self.currJF != None):
            self.currJF.pack_forget();

        self.jf3.pack(side = TOP, fill=BOTH, expand=YES);
        self.currJF = self.jf3;

def main():
    m = Main();
    mainloop();



Reference:

http://www.pythonware.com/library/an-introduction-to-tkinter.htm
http://effbot.org/tkinterbook/
http://www-acc.kek.jp/WWW-ACC-exp/KEKB/control/Activity/Python/TkIntro/introduction/index.htm

Python GUI: Tcl/Tk

2008年夏天在 MOXA-IW 開發公司內部使用的自動化測試工具，花了30個工作天，寫了約五千行Python也算是完 成第一版的雛形。 基本上此系統架構，部分GUI畫面是透過組態檔設定即 可自動產生，並 支援資料輸入的防呆機制。另外透過我所設計的Assert Model可將所需判斷的參數都自動產生GUI提供測試人員方便輸入。在系統 執行測試時，可透過XML組態檔方式來描述Assert的邏輯以及參數擷取方式。

此套工具可 指定排程，透過Console操控多台公司的產品，進行測試的設備組態設定， 並自動更新Firmware。隨後執行指定的Tool Actions，並針對 Assert的判定結果產生報表。每個TestCase都會有一個對應的log檔案，詳細記錄每個 TestCase執行的細節。

以下是部分的工具畫面，最後是報表畫面。

報表畫面(log牽涉指令細節，連結已被移除)

http://www.millerlai.info-a.googlepages.com/autotestreport