一、簡介

隨著智慧型裝置普及化,在可預見的未來,人們將部屬大量的數位裝置,其中不少裝置可能在運算、儲存、能源上有相當程度的限制,而這些裝置可能被用於健康監測、金融交易等,因此其對於通訊和儲存的安全性有所要求。然而,傳統的密碼學演算法,如 AES、RSA 等,所需要的運算效能或空間往往太大,不足以在這些裝置上執行,因此我們迫切地需要能夠在這些裝置上運作的加密系統。

Lightweight Cryptography(輕量加密,以下簡稱 LC)泛指一種運算量較傳統密碼學演算法小的密碼學演算法,旨在提供運算能力不強、對於能源效率有較高要求的裝置。LC 在過去十多年有非常巨大的發展,早期有 DESL、PRESENT 等,NSA 也於 2013 年也提出了他們的演算法,不過遭到 ISO/IEC 29192 “Lightweight Cryptography” 系列拒絕接受,NIST 則於 2015 年起開始新一代 LC 標準的徵選。

本文將簡短地介紹 LC 的設計原則與幾個經典演算法的介紹。在第二節中,我們將概述 LC 在設計時有哪些事情需要考慮,又有哪些很不同於經典演算法。之後的章節,則會探討每個密碼學領域的演算法的發展過程,並介紹幾個重要演算法。

二、設計原則

一般而言,每個 LC 的設計者都嘗試在安全、成本、效能之間做平衡,要同時在這三個面向都達到令人滿意的效果很困難。舉例來說,一個安全又高效能的密碼學演算法的硬體實作,可能可以抵禦旁道攻擊,但也就會有較高的面積需求和成本。

對於 LC 而言,首要被考慮的是運算效能。在此我們必須將效能分成兩種來探討:硬體實作與軟體實作,因為兩者可能在許多面向上有迥異的特徵。舉例來說,bit permutation 在硬體實作上幾乎毫無成本,可是在軟體實作上可能會拖垮整個演算法的效率,又如 substitution table 對於軟體實作而言相當簡單,但對硬體實作而言卻有很高的製造成本。此外,對於衡量效能,兩者也有很大的差異:對於軟體而言,我們更在乎的是這樣的運算佔用多少 RAM 和 ROM(ROM 需求通常與演算法實作的 binary 大小有關)、所需 register 的數量;對於硬體而言,我們在乎的是製造成本、晶片大小(與 FPGA 的 logic block 數量等有關);而兩者我們都在乎運算需要多少 clock cycle。

不過整體而言,對於 LC 效能的衡量包含功率、能量消耗、運算延遲、吞吐量和資源需求。功率和能量消耗對於行動裝置或電源取得不易的裝置(如 RFID 設備)而言很重要。運算延遲是指完成一輪運算所需要的時間,對於回應時間要求較高的使用情境,如汽車駕駛輔助工具等,是不可忽視的衡量標準。吞吐量則是指單位時間內可以處理的明文或密文,對大量產生資料的使用情境是尤其重要的。

在 LC 情境下的硬體實作的成本,通常是在講述需要多少邏輯閘等。以一個低成本的 RFID 晶片而言,大概會有 1000~10000 個邏輯閘,其中可能只有 1/5 的邏輯閘可以供密碼學演算法使用。由此可見,在硬體 LC 的實作中,對於邏輯閘的數量要求有很嚴苛的限制。在某些情境下,開發者並不需要實作完整的演算法,例如生物特徵監測的裝置只需要定期向外回傳資訊,則這樣的設備可能只需要加密資料,不需要解密資料,若能只實作加密所需的硬體,則可以降低製造成本。此外這也意味著也許可以選用可以很有效率地加密,但解密需要較高成本的演算法,例如 DESL 跟 PRESENT。[5]

回到演算法本身,LC 將演算法變得輕量的策略大概不外乎是下述兩種:第一種是,針對演算法的限制條件做約化,第二種則是使用較小的 key sizes, internal states, building blocks,或是較少 rounds, key schedules。然而這些策略對於安全性而言則有很大的影響。舉例來說,有些 LC 演算法選擇將 key size 壓到 80 bits 或 96 bits,小於 NIST 建議的下限 112 bits;較小的 block size 和 output size 可能導致可以用字典攻擊;較少的 key schedules 也可能造成演算法更容易有 weak key 或 related key;太小的 internal states 則可能難以抵禦碰撞。因此,如何在維繫安全性的條件下盡可能地降低成本和提升效能,考驗著許多密碼學家。不過對於 IoT 設備而言,有一個優勢是,也許其不需要這麼高的安全性,例如有些資訊可能只需要保密很短的時間(如數十分鐘),一旦過了這個時間,則此資訊將不具有價值,在此情境下,也許可以透過犧牲安全性來換取效率,因為該資訊確實不需要這麼強悍的安全性。[5, 7]

三、LC 的一些演算法

Block Cipher

對稱式加密,指加密與解密採用同一個金鑰,特色是加解密速度遠比非對稱式加密快。在對稱式加密中,又可以分為 Block Cipher 和 Stream Cipher。Block Cipher 每次加密是以一個區塊(例如 128 bits)為單位做加密,如經典的 DES、AES 等都屬於這類。

Block Cipher 的結構大致可以分為下述幾種:

  • Feistel Network:每一輪只使用一個 round function $F$ 加密一半(或 $1/n$)的區塊,然後區塊會對調或是重組。DES 屬於此類。
  • Substitution Permutation Network (SPN):每一輪有一個 substitution box (S-box) 和 permutation box (P-box),通常 S-box 是 non-linear 的,負責混淆(confusion),而 P-box 是 linear 的,有擴散(diffusion)的效果。AES 屬於此類。
  • Add-Rotate-XOR (ARX):只使用 modular addition、rotation 和 XOR。
  • LFSR-based:使用一個或多個 LSFR (Linear Feedback Shift Registers) 來建構出 non-linear 的結構。KATAN 屬於此類。
    此外還有 LS-design, XLS-design 等。[7]

以下則整理了幾種常見的輕量化策略,以及這些策略的潛在問題:

  • 較小的 block size:為了節省所需的 RAM,Lightweight Block Cipher 可以使用比 AES 更小的 block size,例如 64 bits 或 80 bits。不過,使用較小的 block size 可能會降低最多可以加密的區塊數量,例如 64 bits 的 block size 在某些 mode of operation 底下可能會把最多能加密的明文區塊降低到 $2^{32}$ 塊,因為若超過這個大小,則其機率分佈會和隨機資料的機率分佈有顯著的差異。
  • 較小的 key size:一些 Lightweight Block Cipher 為了提高效率,會使用較小的 key size,例如 PRESENT 的 key size 為 80 bits。這樣可能降低安全性,因此 NIST 在對 LC 做徵選時規定至少要 112 bits。
  • 較簡單的 key schedule:適度地降低 key schedules 的複雜度,可以減少 RAM 的使用並增加運算效率與降低延遲,因此多數的 Lightweight Block Cipher 會使用較為簡單的 key schedules,並在運算時動態地產生 subkey。不過這樣可能導致更容易出現 weak key 或 related key,以及增加 chosen-key 的風險。有一種解決方式是在加密前先過一層 Key derivation function 來減少攻擊者對於 key 的掌握度。
  • 較簡單的 rounds:在許多傳統 Block Cipher 中,有 rounds 的概念,及每一輪要做某些運算,當完成足夠多輪時,明文就被充分地加密了。在 Lightweight Block Cipher 中,為了減少 RAM 消耗、降低硬體成本等,可能簡化這些流程。例如在傳統 Block Cipher 中,時常使用 8 bits 的 S-Box,但 PRESENT 只使用了 4 bits,把硬體成本降低到 28GEs(AES 的 S-Box 佔用 395 GEs)。不過這樣的缺點則是,需要更多 rounds 才能達到一樣的安全性,進而犧牲效能。[6]

前面舉例中提到的 PRESENT 以外,另一個很重要的 block cipher 是 LEA (Lightweight Encryption Algorithm)。LEA 是 ARX 結構,支援 key size 128, 192, 256 bit,目前認為 LEA 大概比 AES 快 1.5~2 倍,且目前已知最佳攻擊對 LEA 造成的 security margin 有 37.50%,因此被認為是安全的演算法。LEA 是 ISO/IEC 29192-2 標準的一部分。[5, 7]

除了從頭打造一套全新的密碼系統以外,也有人嘗試優化 DES 以達到輕量化的目的。原生的 DES 只能處理 32-bit 和 48 bit words,輕量化的 DES 變種(處理 4-bit 和 6-bit words)已透過硬體實作成功,將其降低到 2,310 GEs 和 144 clock cycle。不過 DES 最為人詬病的是 key size 只有 56bit 不夠安全,有一種策略是使用 key-whitening,只要多兩層 XOR 就可以把 key size 提升到 184 bit,並把安全性提升到 118 bit(因為有 birthday attack),此變種稱為 DESX。為了降低硬體成本,DES 有另一款變種是 DESL,其把八個 S-boxes 換成固定一個 S-box,藉此省掉七個 S-boxes 和 multiplexer 的成本,如此則可以把硬體實作壓縮到 1,850 GEs,若再搭配 key-whitening,則稱為 DESXL,可以使用 2,170 GEs 和 144 clock cycles 達到 118 bits 的安全性。[5]

Stream Cipher

不同於 Block Cipher 以區塊為加密單位,Stream Cipher 一次只在一個或數個 bit 做操作。Stream Cipher 的演算法透過 key 產生一串偽亂數的 keystream,然後與明文做 bitwise-XOR(或其他操作,但多數都還是 XOR),藉此產生密文。因為整個流程很像是「明文流進演算法,再流出密文」,所以稱其為 Stream Cipher。使用同一個金鑰與 IV 所能產生的密碼流有限,一旦超過該限制,就會開始重複,使用重複的 key 加密會導致資訊洩漏,因此在設計 Stream Cipher 演算法時盡可能地增加 keystream,並且在初始化時就會約定最多能加密多少 bit。

一直以來,Stream Cipher 在學界都受到較少的重視,但是在歐盟 eSTREAM 計畫之後,有不少原有或新開發的 Stream Cipher 的 LC 重新得到重視,加上許多現存的被廣泛使用的 Stream Cipher 被證實為不安全,如 GSM protocol 使用的 A5/1、Bluetooth 使用的 E0、MIFARE Classic 使用的 Crypto-1,我們可以想見未來 Stream Cipher 會獲得更多重視。

eSTREAM 計畫分成兩個部份:軟體實作與硬體實作。eSTREAM 本身並非 LC 標準,不過就結果而言部份被提出的演算法具備 LC 的特質,故我們還是針對這個標準做介紹。eSTREAM 軟體實作的部份,比較值得一提的有兩者:Salsa20 和 LEX。Salsa20 是建立在數個基本的 arithmetic operation 之上,所以速度很快,有相同特徵的還有 Tiny Encryption Algorithm (TEA) 和 International Data Encryption Algorithm (IDEA),這些演算法所佔用的 RAM 和 ROM 很小,且初始化也很快。LEX 則是對 AES 做一些修改,把 internal state 拿出來當作 keystream 使用,這樣的好處是,可以直接運用 AES 許多已知的安全特性,不須從頭設計、分析、攻擊,此外在初始化階段,也只需要一次 AES 即可。不過 Salsa20 的硬體實作非常繁複,LEX 則根本仍是 AES,兩者都不適合作為硬體的 LC。eSTREAM 計畫另外還有 Grain,目前已經被廣泛地分析,且在實作上具有彈性,其中一款變種又可以提供可驗證性。Mickey 則還沒有被很透徹地研究(與 Grain 及 Trivium 相比),且較不具備彈性,且因為其 Irregular Clocking 的特性,容易被旁道攻擊。[7]

另一個很有潛力的 LC Stream Cipher 則是由 Hitachi 提出的 Enocoro。Enocoro 是 Panama 的改良,首次於 2007 年被提出,key size 為 80 bit 或 128 bit。Enocoro 使用經典的 $GF(2^8)$ Linear Transform 加上 S-box,最後過一層 byte-wise rotation。其限制則是 keystream 可能不夠長(Enocoro 80bit 有 $2^{32}$),不過這個長度已經足以滿足多數 LC 應用場景。作者宣稱 Enocoro 80bit 的硬體實作只需要 2,700 GEs。目前 Enocoro 已經成為 ISO/IEC 29192-3 標準的一部分。[9]

Asymmetric Cipher

非對稱式密碼系統(Asymmetric Cipher)指,加密與解密使用不同的金鑰,這樣的特性也造就了許多用途,例如電子簽章、金鑰管理等功能都和非對稱式加密有關。常見的非對稱式密碼系統包含 RSA、ECC、Elgamal 等。不過它天生的劣勢是運算速度慢,例如一個最佳化過的 ECC 硬體實作比 AES 慢上 100~1000 倍,也造就數百倍的耗電量,這樣的差距對於運算效能很糟糕或使用電池的裝置而言是毀滅性的。因此 LC 發展的一個很重要的面向是如何設計出可以在這些裝置上運作的非對稱式加密系統。[5]

然而,到目前為止,LC 的非對稱式密碼系統發展仍然十分緩慢,其中一個很大的原因是目前 ECC、RSA 及 Rabin 其實已經足夠供多數情境使用。當裝置不需要自行生成 key-pair 的時候,RSA 和 Rabin 可以很快速地在運算效率不強的裝置上完成加解密(目前已經有許多對兩者的加速演算法,且以 RSA 來說, e=3 在多數情境下若搭配足夠好的 padding,也已經足以提供很好的安全性),此外 RSA 與 Rabin 並沒有受到專利保護。兩者的缺點在於 key size 太大,以 RSA 來說,目前認為至少要 2048-bit 才能算是安全,這樣的 key-size 對於多數需要 LC 的設備來說太大了,不過這可以從兩個方面去解決:首先如同前述,有些情境所需的安全性不需要這麼大的 key-size,此外,若使用 RSA-OAEP 搭配 SHA-256,則可以把 key-size 壓到 66 bytes。RSA 和 Rabin 最大的缺陷在於,其 key-pair 生成所需的運算效能和空間極大,以致在許多運算效率不強的設備上難以產生 key-pair。[3]

若需要在設備上生 key-pair,則可以使用 ECC(如 ECDSA, ed25519)。ECC 有許多 RSA 和 Rabin 無法取代的優點,例如 key generation 非常簡單而快速,在 private key 上做運算(例如電子簽章等)很快、key size 較小。雖然 RSA 也可以透過獨立的硬體晶片來完成快速加解密與 key generation(這樣的晶片在許多智慧卡上可見),但相較於 ECC 不需要獨立晶片也能完成,RSA 仍有先天劣勢。ECC 亦可透過一些方式做改進,例如改用 binary field 而非 prime field,在 GF(2^m) 上運算,因為前者是 carry-free arithmetic,硬體實作成本較低,或是用 Montgomery algorithm 來實作 point multiplication,藉此減少運算時所需的 RAM 以及將一個 iteration 壓縮到 1 addition 和 4 multiplication。[5]

另一個重要的演算法是 NTRU,他可以抵禦 Shor’s algorithm 的攻擊,一般被認為是 Post-Quantum Crypto,但因為其速度很快,有時也被視為一種 LC。NTRU 系統包含兩個部份:加解密的 NTRUEncrypt 與電子簽章的 NTRUSign。NTRU 在實務應用上仍然有許多困難,首先,早期的 NTRU 受到專利保護,甚至不允許開源的實作,一直到 2013 年才允許開源實作,NTRUEncrypt 直到 2017 年才變成 public domain,而 NTRUSign 至今仍受到專利保護。再來是,雖然 NTRUEncrypt 目前被認為是安全的,但 NTRUSign 被認為可能是不安全的。整體而言,在可預見的未來,在 LC 中,RSA、Rabin、ECC 仍會佔據非對稱式密碼系統的主流。[3]

Hash Function

Hash function 是一種可以把任意長度的輸入變成固定長度輸出的函數,被廣泛用於驗證完整性與電子簽章。一般而言,Hash 必須要能抵禦碰撞攻擊,包含:Hash 應該是無法還原的、不能輕易找到兩個字串有同樣的 hash digest、給定一個字串不能輕易找到另一個擁有一樣 hash digest 的字串。

最常見的 Hash 建構方法是 Merkle-Damgård (MD) construction。在 MD costruction 中,輸入被填充到指定長度後,會被切成數個固定長度的區塊,而每個區塊和其前一個區塊的輸出會通過名為 compression function 的函數,並成為下一個區塊的輸入。這樣可以確保每一個區塊是被綁在一起的,並且改動一個小地方就會讓 Hash digest 截然不同(Avalanche effect)。常見的如 MD5、SHA-1 都是使用 MD costruction。

另一種建構方式是 Sponge Construction。給定一個固定長度 b bits 的 zero vector(b 是 message block 大小 + capacity,而 capacity 決定安全性和效率的權衡),該 zero vector 會通過數個 function f(可能是 unkeyed permutation (P-Sponge) 或是 random function (T-Sponge)),並在每一層之間 XOR 輸入,即要算 digest 的資料,當完成「吸收」(absorb)所有輸入後,接著又通過數個 function f,其中每一層之間將狀態拿出,稱為「擠出」(squeezed out)。因為整個過程有如海綿吸水再擠出水,所以稱為 Sponge Construction。應用有如 SHA-3。[7]

不過這些傳統作法的問題在於其仰賴太多 internal states,例如 SHA-3 有 1600 bits,而 SHA-256 有 256 bits。過多的 internal states 會造成效率下降以及硬體成本上升。幾種可行的輕量化策略有:

  • 較小的 interal state 與 output size:有些情境下,碰撞防禦(collision resistance)可能沒有那麼重要,例如只需要有 one-way property 即可,此時可以降低 output size 和減少 internal state 數量來換取較低的硬體成本與較好的運算效率。當需要碰撞防禦時,則可以減少 internal state 數量。
  • 較小的輸入:許多 Hash function 在設計時,都假設輸入會非常大(例如 $2^64$ bits),不過在實務運用上,這些裝置不一定真的需要這麼大的輸入,許多情境可能 256 bits 便足夠,故 Hash function 可以對較短的輸入做優化來滿足 LC 的使用情境。[7]

舉例來說,有一個知名的 LC Hash 稱為 SPONGENT,是結合了 Sponge construction 和 PRESENT,他運用 sponge construction 來作到輸入任意大小,輸出 n bit,並使用一種類似於 PRESENT 的結構來做 permutation。[1]


(SPONGENT 結構,擷取自 [1])

目前 Lesamnta-LW、PHOTON、SPONGENT 已經成為 ISO/IEC 29192-5:2016 所核定的 Hash function。

Message Authentication Code

Message Authentication Code(MAC)用於保護資料的完整性與可驗證性。其使用方法為:為一段資料藉由一個 secret key 產生一個 tag,故發送者和接收者事先約定好 secret key,當發送者送出資料時,夾帶一組透過事先約定的 secret key 所算出的 tag,接收者可以將資料透過 secret key 算出 tag,並檢查是否與發送者所給予的 tag 一樣,藉此驗證資料來自發送者,以及並未被竄改。MAC 可以透過 Block Cipher 來建構,例如 CBC-MAC、OCB-MAC,亦可透過 Hash function 來建構,例如 HMAC。

目前針對使 MAC 輕量化的方法包含:使用較小的 tag size、較為簡單的 key schedules、不使用 nonce,以及對於 CBC-MAC 等基於 Block Cipher 的 MAC 改用 Lightweight Block Cipher(目前大多使用 AES)。使用較小的 tag size 或不使用 nonce 之所以可行在於,有些應用中,並非每一筆資訊都需要具備可驗證性,例如 VoIP,若有部份封包不具備可驗證性,對於整體安全性的影響可能不會太大,因此省去 nonce 或改用較小的 tag 在審慎的計算與考量下,是可接受的。[7]

在規範 LC MAC 的 ISO/IEC 29192-6:2019 中,包含了三種 LC 的 MAC:LightMAC, Tsudik’s keymode, Chaskey-12。舉例來說,LightMAC 便是建立在 Block Cipher 之上,其本身其實是個 mode of operataion。LightMAC 需要兩把 K bit 的 key $K_1$ 與 $K_2$,其運作方式是:把 Message 切成 $L$ 等分 $M_1, \dots , M_L$,對於最前面 $L-1$ 等分,每一等分都複製成四份並加上指定大小的位移,以 $M_{i,1}, \dots, M_{i,4}$ 表示,並用一個 block cipher 使用 $K_1$ 對每一等份做加密(其中作者推薦的 Block Cipher 是 AES 和 PRESENT),接著把密文都 XOR 起來($E_k = Enc(M_{1,k}) \oplus \dots \oplus Enc(M_{L-1, k})$),最後再 XOR $L_{L, k}$ 的明文,並透過一個 block cipher 使用 $K_2$ 把前面的計算結果加密並 trancate 到 $t$ 個 bit。我們可以看到,如果他所使用的 Block Cipher 很有效率(例如 PRESENT),則這樣的 MAC 也會很有效率。[4]

目前針對無線感測網路(Wireless sensor network),有三種已被提出的 Lightweight MAC:TinySec、MiniSec、SenSec,其中,TinySec 與 MiniSec 推薦使用 CBC-MAC 和 OCB-MAC,而 SenSec 推薦使用 XCBC-Mac,三者都生成 32-bit tag,不過目前認為 32 bits 不太夠,應該至少要 64 bits。[7]

四、LC 標準化的過程

密碼學演算法的一個天生限制是,這個演算法一定要有夠多人願意用,才可以有效保障通訊安全。因此多數密碼學演算法都需要得到某種形式的標準化,而通常標準化會由 ANSI, IEEE, ISO/IEC 等重要的學界、產業界、國際機構來完成。在此段,我們將介紹兩個重要的 LC 標準化:ISO/IEC 29192 與 NIST。

ISO/IEC 29192

ISO/IEC 29192 是一系列的 LC 標準,指定了包含 Blocker cipher, Stream Cipher, Hash 等重要密碼學演算法分類應該使用哪些特定演算法。

以下我們會簡短地介紹 ISO/IEC 29192 的各個分類與所定義的演算法:
首先在 ISO/IEC 29192-1:2012,定義了何謂 LC,以及對於 LC 的基本概念。ISO/IEC 29192-2:2019 指定了 Block Cipher 的規範,包含 PRESENT, CLEFIA, LEA。在 ISO/IEC 29192-3:2012 則是 Stream cipher 的規範,包含前面提過的 Enocoro 與 Trivium。在 ISO/IEC 29192-4:2013,則是要求建立在 discrete logarithms 的 unilateral authentication mechanism、LC 的 key exchange、identity-based signature mechanism。ISO/IEC 29192-5:2016 接著定義 LC 的 Hash,成為標準的有 PHOTON, SPONGENT, Lesamnta-LW。於 ISO/IEC 29192-6:2019 是有關 MAC 的規範,指定 LightMAC, Tsudik’s keymode, Chaskey-12。ISO/IEC 29192-7:2019 定義了 Broadcast authentication protocols。目前則是在制定 ISO/IEC 29192-8,是有關 Authenticated encryption 的部份。

目前對於整套 ISO/IEC 29192 何時會完成仍不知道。從 ISO/IEC 29192-1:2012 可得,於 2012 年時,相關 committee 認為 ISO/IEC 29192 只會有前四個章節,也就是只會討論 Block Cipher, Stream Cipher, key exchange,不過隨著標準化進行,越來多部份被加入,以致至今近十年都尚未完成標準化。[7]

Simon 與 Speck 於 ISO/IEC 29192-2

在 ISO/IEC 29192-2 Block Cipher 的一個很有趣的重大事件是 Simon 與 Speck 的標準化過程。Simon 與 Speck 是兩款由美國國家安全局(NSA)於 2013 所提出的的 Block Cipher,而有鑑於不久前才發生 Dual_EC_DRBG 被 NSA 塞後門的事件,導致當時國際專家普遍對 NSA 有強烈的不信任感。在此段,我們會簡單地講述 Simon 與 Speck 在標準化時發生的事情。

Simon,或有時用 Simon $2n/mn$ 表示,其中 $2n$ 是 block size,而 $mn$ 是 key size。Simon 使用 Feistel structure,而 round function 只使用了 XOR、bitwise AND 和 cyclic bit rotation,key schedule 則使用 LSFR,因此在硬體運算速度上非常快。Speck,或有時用 Speck $2n/mn$ 表示,同樣地,其中 $2n$ 是 block size,而 $mn$ 是 key size。Speck 使用的是 Add-Rotate-XOR (ARX) 結構。Speck 在軟體實作上很快,不過 ARX 結構有個問題是 diffusion 比較慢,因此一般來說需要比較多 round 才能保障安全性,不過 Speck 所使用的 round 很少(block size 與 key size 均為 128 時,round 只有 32 次),Speck 的設計者堅持這樣的數量已經足夠,不過被許多其他密碼學家懷疑。

一般來說,密碼學演算法,尤其 Block Cipher,的設計團隊為了讓其他人知道他們為何如此設計,會釋出一份 “Design Rationale” 來解釋為何演算法結構會如此設計,他們在設計時考慮了什麼樣的攻擊,這些攻擊是否成功,會如何降低演算法安全性。Design Rationale 在分析安全性的效益在於,讓其他學者可以快速了解到設計者已經嘗試過哪些攻擊,他們就可以去尋找其他攻擊方式,以及讓他人對於這個演算法的安全性有基本的概念。Simon 與 Speck 在 2013 年提出,但始終沒有釋出 Design Rationale,這引起學界以及 ISO 標準化委員會的批評,一直到了 2017 年,NSA 才釋出 Design Rationale,然而這並沒有讓攻擊停止。

NSA 釋出 Design Rationale 後,並沒有平息爭議,反而掀起更多批評。Ashur 和 Luykx 整理了許多對於對於這份 Design Rationale 的批評,我們以下舉例幾個我們認為很重要的批評。首先,在 Cryptoanalysis 領域中,他們聲稱有使用 Matsui’s algorithm 與 SAT/SMT solvers 來檢測,不過沒有公佈 differential paths 和 linear paths 長度的上限,或是攻擊所使用的 script,所以他們所宣稱的安全幾乎都無法重現。另一個重要問題是 round number 是如何被選取的。Simon 普遍被認為 round number 可能不太夠,Speck 則是,如同前述,round number 對 ARX 結構而言很可能不足。不過在公佈的 design rationale 中,雖然他們提到了對於 round number 的批評,但他們的回應仍被認為是過份高估安全性,或是隱瞞了重要訊息。

在 2017 年的 ISO 會議時,因為公佈了 design rationale,所以代表國重新針對 Simon 與 Speck 是否成為標準做投票時,許多代表提出對於 round number 的疑義,不過 Simon 與 Speck 的研究團隊只回應說他們在 design rationale 上已經表達清楚,認為是那些代表曲解了 design rationale 的文字,並指出「任何一個英文母語使用者都會了解我們想表達什麼」,然後拒絕為非英文母語使用者做解釋。最後 Simon 與 Speck 的 LC 標準化於 2018 的 ISO 會議正式宣告終止。不過雖然 Simon 和 Speck 沒有被納入 ISO/IEC 29192-2,但他們成功被納入 RFID air interface standard,並成為現在的 ISO/29167-21 (Simon) 與 ISO/29167-22 (Speck)。[7]

NIST

NIST (National Institute of Standards and Technology) 可說是在密碼學標準化上,最具影響力的組織。最早於 1997 年時,NIST 便組織了一場公開競賽,以開發 DES 的替代品。該競賽有 15 個來自各國的參賽隊伍提交的演算法。 2000 年時,由 Joan Daemen 和 Vincent Rijmen 設計的 Rijndael 獲勝,成為新的 Block Cipher 標準,也就是如今 AES。 2007 年時,NIST 再舉辦了一場有關 Hash 標準的競賽,並收到 64 個參賽的演算法,最後由 Keccak 獲勝,成為 SHA-3。

2018 年時,NIST 再次組織了一場密碼學演算法的選拔,這次是關於 LC 的標準化。這次競賽總共收到來自 25 國的 57 份參賽演算法,其中 56 份通過審查進入 Round 1。在 2019/04/28 公佈 Round 1 後,又接著於 2019/08/30 公佈 Round 2 名單,由 NIST 選出比較有潛力的 32 個公開出來給大家做分析與嘗試攻擊。最後在 2021/03/29 公佈了最後十個成功進入 Final 的演算法:ASCON, Elephant, GIFT-COFB, Grain128-AEAD, ISAP, Photon-Beetle, Romulus, Sparkle, TinyJambu, Xoodyak。接著會有為期 12 個月的最終審查,並預計於 2022 年初公佈結果。[2]

五、總結

隨著現代科技的進步,各項需要隱私、安全的新興技術,如 RFID、IoT 等,對於加解密函式有更多的限制或要求,像是低能量消耗、低延遲等特性。而輕量密碼學 LC 將這些特性設為基準進行發展,將密碼學拓展到更廣的領域裡。然而,目前對 LC 最大的挑戰包含標準化不完全,許多正在被使用的密碼學演算法尚未經過完整的破密分析,甚至有些不安全的密碼學演算法因為已經廣泛部屬而難以召回修正。例如早在十年前,德國研究員 Harald Welte 以及台大電機系的鄭振牟教授便已成功破解使用 Mifare Classic 的悠遊卡,但至今我們仍都在使用悠遊卡。[10]

目前正有許多專家以及機構,像是 ISO/IEC、NIST,在進行 LC 的標準化。可以看到密碼學的每個部分,如 Block Cipher、Asymmetric Cipher 等等,都有與之對應的輕量化策略。再過不久,我們便會看到全新的、經過學界嚴密分析與挑戰過的並得到認可的 LC 標準誕生,屆時對於新技術的隱私及安全將能夠提供更多保障,我們相信這會對於相關產業與學界有深遠的影響。

六、參考資料

[1] Buchanan, W. J. (n.d.). SPONGENT. https://asecuritysite.com/encryption/spongent.

[2] Computer Security Division, I. T. L. (n.d.). Lightweight Cryptography: CSRC. CSRC. https://csrc.nist.gov/projects/lightweight-cryptography.

[3] fgrieu. (2015, December 15). Lightweight Asymmetric encryption algorithm. Cryptography Stack Exchange. https://crypto.stackexchange.com/a/31297.

[4] Luykx, A., Preneel, B., Tischhauser, E., Yasuda, K. (2016). A MAC Mode for Lightweight Block Ciphers. Fast Software Encryption, 43–59. https://doi.org/10.1007/978-3-662-52993-5_3

[5] Eisenbarth, T., Kumar, S., Paar, C., Poschmann, A., & Uhsadel, L. (2007). A Survey of Lightweight-Cryptography Implementations. IEEE Design & Test of Computers, 24(6), 522–533. https://doi.org/10.1109/mdt.2007.178

[6] McKay, K. A., Bassham, L., Turan, M. S., & Mouha, N. (2017). Report on lightweight cryptography. https://doi.org/10.6028/nist.ir.8114

[7] Mileva, A., Dimitrova, V. C., Kara, O., & Mihaljevi, M. (2021). Catalog and Illustrative Examples of Lightweight Cryptographic Primitives. In Security of ubiquitous computing systems: selected topics (pp. 21–47). essay, Springer.

[8] Nohl, K., Evans, D., Starbug, & Plötz, H.. (2008). Reverse-engineering a cryptographic RFID tag. In Proceedings of the 17th conference on Security symposium (SS'08). USENIX Association, USA, 185–193.

[9] D. Watanabe, K. Ideguchi, J. Kitahara, K. Muto, H. Furuichi and T. Kaneko, “Enocoro-80: A Hardware Oriented Stream Cipher,” 2008 Third International Conference on Availability, Reliability and Security, 2008, pp. 1294-1300, doi: 10.1109/ARES.2008.84.

[10] 有關悠遊卡事件一些誤會的澄清. Hacks in Taiwan Conference 台灣駭客年會. (n.d.). https://blog.hitcon.org/2011/09/blog-post.html.

後記

此文撰寫於 2021 年六月。原為密碼學的期末報告,因為有些部份不是我寫的,故有經過相當程度的刪減與改寫,以讓移除他人撰寫部份後的文章也是完整的。