# 密碼學 Final Project

## Proposal

- Team members:
- P10942A04 董晉志
- P10942A03 李維哲
- R10921119 呂旻軒
- Project title: Lightweight Cryptography
- Main reference：Lightweight Cryptography Algorithms for Resource-Constrained IoT Devices: A Review, Comparison and Research Opportunities(IEEE Access 2021)
- Project type: (b) Survey
- Motivation:
- IoT is becoming more common and popular due to its wide range of applications in various domains. As most of IoT devices are limited in resources (energy, memory, power etc.), it needs more efficient way to ensure the security. As we know, lightweight symmetric cryptography is seen as one of the solutions in recent years. We would like to survey this topic to realize the trade-off between the security and efficiency by using lightweight cryptography.
- What we are going to do:
- We will do an extensive survey on "lightweight cryptography" among the cryptography related conferences/journals and articles/forums. Documentations related to ISO/IEC 29192 and NISTIR 8369 will also be referenced for extensive research.
- What we expect to achieve in this project:
- Study the design pattern of lightweight cryptography.
- Understand the trend of lightweight cryptography.
- Compare the design logic and advantage/disadvantage of lightweight cryptography to modern encryption algorithms.

## Presentation

- Choose a team member to represent your team to report your term project
- Prepare a roughly **30-minute presentation**
- **Record your presentation** (using EverCam), and output the video in .mp4 format
- Upload your powerpoint presentation file and your .mp4 video to NTU COOL by **2022/01/16**

## Term Report

- Your term report should include
- Description related to the topic:
- Introduction
- Problem addressed
- Solutions and techniques
- Comparisons of the approaches survey
- Conclusions
- Your comments and conclusion about the topic
- References
- A contribution table which describe the contribution of each team member
- Send your final report to [e-mail] by **2022/01/21**

### Title

### Abstract

### Introduction

### Related works

### Backgroud

### … (What you do …)

### Discussions

### Conclusion

---

# 繳交檔案命名規則

請嚴格遵守以下命名規則

1. 檔案名稱一律以 T##-2021- 開始，其中 ## 是你們的 team number.
2. 影片及 ppt 檔(demo 可和口頭報告合併或分開繳交)
- 口頭報告檔: T##-2021-oral.mp4，T##-2021-oral.ppt
- 例如 T03-2021-oral.mp4，T03-2021-oral.ppt
- Demo 檔案: T##-2021-demo.mp4，T##-2021-demo.ppt
- 例如 T18-2021-demo.mp4，T18-2021-demo.ppt
- 口頭報告和 Demo 合併檔:T##-2021-oral+demo.mp4，T##-2021-oral+demo.ppt
- .ppt 可以用.pdf 檔取代
3. 期末報告檔: T##-2021-report.doc或T##-2021-report.pdf
4. Source Code: T##-2021-src.zip (將所有相關檔案壓縮成一個檔案)

影片及 ppt 檔請在 01/17/2022 前上傳至 NTU COOL
期末報告檔 (Source Code) 請在 01/21/2022 前上傳至 NTU COOL

2022/01/18（二） 00:00 AM 前，試算表後方放上 Google Drive (*.mp4) / Youtube 影片連結。

2022/01/22（六） 00:00 AM 前，將書面報告上傳至作業區。

請確認檔案/影片是否完成共用。（無權限，可以讓所有人觀看）

參考分組試算表 (https://docs.google.com/spreadsheets/d/1lCwh-ArmxnxCl61fKsfdBDy7V8RMTjACJ3Z04CBYgec/edit?usp=sharing)

---

## A survey of the current state of lightweight cryptography for the Internet of things

- Introduction
輕量級加密演算法主要就是為了在有限資源的設備上也能夠進行資安管控所提出的，其中輕量化的概念在於要維持演算法在效能、安全以及成本上的平衡，而物聯網裝置便是在這些有限資源的設備中佔了最大宗的一環，本文的目的在於檢驗目前被開發或發表出來的加密解決方案、比較他們之間的優缺點（效能的統計數據與抵抗攻擊的能力）以及目前可能的研究缺口。

- Problem addressed

- Classification

輕量級加密演算法可以根據實現方式（硬體和軟體）或架構（對稱式和非對稱式）進行分類。
- 實現方式（Mode of Implementation）
- 軟體優化的演算法：
舉例：HC-128、Rabbit、SOSEMANUK、Salsa、Speck、Zorro、Robin、Pride、RC5、LEA、SPARX及RoadRunneR。
這種方法的主要缺點是，如果攻擊者以物理方式或通過網絡存取設備，可能可以透過竄改軟體並發起攻擊。此外，軟體必須定期更新這點也會消耗設備已經有限的頻寬和運算能力。
- 硬體優化的演算法：
這類演算法旨在優化硬體資源，並且由於加密轉化為硬體的邏輯閘時的特性而通常更容易構建。這種方法的優點是，即使攻擊者獲得了對設備的實體存取權，也很難在不破壞或改變整個設備的情況下竄改加密的狀態。
- 架構（Architecture）
- 對稱式金鑰演算法：
此架構提供了一種簡化與更快的運作模式，但主要缺點是必須想辦法以安全的方式在兩個用戶之間共享金鑰。在對稱式金鑰演算法支援的加密模式之中，主要有三種加密模式：區塊加密、雜湊函數以及串流加密；然而，雜湊函數和串流加密都可以透過區塊加密實現，因此，區塊加密在研究領域中較受到歡迎。
在現有的對稱式金鑰演算法之中，比較著名的有NSA發表的AES、 Simon以及Speck。完整的清單可參考下列由A.與P. Biryukov所維護的Lightweight Cryptography Lounge：https://cryptolux.org/index.php/Lightweight_Cryptography
- 非對稱式金鑰演算法：
這種方法的優勢在於金鑰更安全，但是對於物聯網設備來說可能代價高昂，因為設備需要擁有與其通訊的其他主機的所有公鑰。另一個缺點是與開源的私鑰系統不同，大多數公鑰系統是有專利的，而且它們通常也比其他演算法更慢、更複雜，因此較不受歡迎。輕量級非對稱演算法最著名的例子是NTRU，而最主要的應用則在於Elliptic Curve Cryptography（ECC）。

- 密碼分析（Cryptanalysis）
密碼分析指的是指對密碼系統的分析。以目前可取得的研究成果來說，我們發現仍非常需要在弱點和攻擊漏洞方面徹底了解輕量級加密演算法。本文將密碼分析分為兩類：通用攻擊（Generic Attack）和非通用攻擊（Non-Generic Attacks /Shortcut Attack）
- 通用攻擊（Generic Attacks）
此類型的攻擊與密碼的內部狀態（internal state）無關，因此只能通過小心選擇金鑰的長度、區塊的大小或是內部狀態的大小來防止攻擊，使攻擊在運算上不可行（Computationally Non-feasible）。
- Exhaustive Key Attack / Brute Force Attack
攻擊者會嘗試窮舉所有可能的金鑰，而根據目前的標準，只要能夠被暴力破解的密碼都會被視為不安全，以現今的技術來說，只要金鑰長度大於128位元理論上便可以抵擋此類型的攻擊。
- Table Lookup Attack
攻擊者事先知道金鑰的長度，並事先計算好預加密的訊息對應的所有密文儲存於對應的表格。當攻擊者攔截到符合的密文時，便可以透過查表的方式找到相對應的金鑰。此攻擊的條件是攻擊者必須要有足夠的記憶體空間能夠儲存n（金鑰長度）位元的密文區塊。
- Dictionary Attack
此攻擊完全忽略了恢復金鑰這個步驟，僅通過收集足夠多的明文和相應的密文，並在需要的時候透過密文反查明文。此攻擊僅適用於已經擁有大量的明文密文字典的情況，並且假設所有這些明文密文都使用相同的密鑰加密。
- 非通用攻擊（Non-Generic Attacks/Shortcut Attacks）
最常見的非通用攻擊為linear與differential攻擊，此類型的攻擊會使用數學模型操控密碼的內部狀態以重新建立密鑰、內部狀態、明文以及密文，相較於通用攻擊來說更難防禦。
- Linear Attack
此攻擊最早是由Matsui於1993年開發用於破解DES的，它使用線性模型來建立明文、密文以及密鑰之間的關係，藉以推導出密鑰的部分定義。
- Differential Attack
此攻擊是由Biham和Shamir發明的，目的是為了揭露區塊加密FEAL的弱點。它提出的論點是，通過分析系統輸出中引起的差異，當特定的差異應用於輸入時，便可以揭露系統的狀態。
- Algebraic Attack
此攻擊嘗試利用「大多數密碼系統都可以被描述為具有多變量非線性方程式（Multivariate Non-linear Equation）的二進位系統，因此求解方程式會揭露密鑰」這個事實，雖然求解這些方程式被認為是NP-hard的，但是目前也有Gröbner basis和線性化（Linearization）等理論正在被研究嘗試作為解決方案。

- 基準測試工具（Benchmarking Tools）
為了準確地衡量和分析演算法的效能，我們需要一個穩定的基準測試工具。這裡按照發布的順序簡單介紹最受歡迎的的幾個工具。
- XBX for SUPERCOP
eXternal Benchmarking eXtension（XBX）為針對SUPERCOP改善後的工具。SUPERCOP只能在符合POSIX標準的Shell上執行，而無法在有限資源的設備（PDAs、行動電話以及FPGA等平台）上運作。除此之外，XBX還嘗試融合各種來自研究人員在不同平台、實現方式和CPU上分析相同演算法的結果。
- ATHENa
Automated Tool for Hardware Evaluation （ATHENa）此計畫主要專注於分析針對硬體（尤其是FPGA）的加密工具，其主要優點在於能夠自動產出和優化結果，並通過綜合批量測試自動驗證實現方式。此計畫的缺點在於作者為了保護知識財產權沒有公開原始碼。
- BLOC
The BLOC Project主要目標在於分析輕量級區塊加密法在受限環境中的效能。其考慮的主要指標：安全模型（Security Model）與其證明、密碼分析、設計與安全參數以及效能評估。該計畫的主要缺點是對於RAM需求的計算錯誤。該計畫已於2016年3月31日結束。
- FELICS
The Fair Evaluation of Lightweight Cryptographic Systems（FELICS）是目前最受歡迎以及最新發表的基準測試工具。它支援多種密碼實現方式的擴展，並且在其網站上接受提交。該工具還以Figure of Merit（FOM）的形式提供密碼效能分級系統，可用於從不同角度計算資料的呈現方式。

缺乏的工具類型：現有的工具除了針對如NIST Test Suite與FIPS (2001) standard等NIST發表的Statistical Test Suite之外，都沒有辦法提供通用的密碼分析。此外，目前也沒有能夠分析ECC密碼系統的工具。

- Comparisons of the approaches survey

- Conclusions

本文調查並分析了輕量級加密演算法如何作為物聯網設備的資安解決方案，並展示了演算法的不同分類以及對應的案例。在評估一些輕量級加密演算法效能的同時，也介紹了針對它們的主要密碼分析技術。此外，本文也整理出了在這個領域中出色的研究機會和一些值得注意的機構、團體以及研究人員，並作為擴展到像是物聯網安全以及設備實體安全等領域的研究基礎。

- Your comments and conclusion about the topic

- References

---
## A Survey of Lightweight-Cryptography Implementations

- Introduction
>在現代科技發展下，智慧型設備普及化，而體積較小的裝置受限於有限的資源，具有記憶體不足、運算速度慢、電源供應不足等問題，難以負荷現存加密 系統的大量計算，因此為顧及某些需要保密的小型設備，如 RFID 應用等，發展 出多種 lightweight 加密演算法，意即運算量較傳統密碼學演算法小的密碼學演 算法，期望最大化減輕計算的負擔並確保資料安全。
在本文中，將展示一些 state-of-the-art 的輕量級加密演算法，並將它們與各自領域的最新成果進行比較，而研究涵蓋了對稱和非對稱密碼的軟體和硬體實作，並 將軟體和硬體分開討論，因為在特定情況下兩者可能會出現相悖的情況，例如 bit permutations 在硬體架構下實作容易，但卻會在軟體架構下顯著減緩速度， 因此本文將分析各種 lightweight 演算法在不同架構下的成果。
- Symmetric Ciphers:經典演算法有 DES、AES、Present 等，過去經常透過軟體實現
> 以硬體實作的對稱式 lightweight 加密演算法:
> 1. 輕量版 DES:相較原版的 DES 使用 32 或 48 bits 的 block size，lightweight 的版本使用 4 或 6 bits 的 block size，減少每個 block 的計算，使得它僅需 2310 個 gate equivalents(GE) 並可以在 144 個 block cycle 內完成加密，達到了減少運算量的要求。但 DES 同時也存在著缺陷，過短僅 56 bits 的密鑰使得它 容易受到暴力窮舉法破解，在專門進行解密的電腦攻擊下，只需幾天就能破 解密鑰，因此較適用在 short-term security 的應用下，對於資訊的加密時間 並不要求太高，而通常此演算法安全性已足夠應付部分的應用。
>2. DESX:增加 DES 安全性的演算法，使用”key-whitening”的技巧，在 DES 中 額外加入兩個 XOR gate，分別透過 XOR gate 對原文和密文加上特定值，使 得 key size 可以提升至 184 bits，即便在特定針對的攻擊下也能保有 118 bits 的安全性，大幅增加整體的安全性。
>3. DESL and DESXL:因為在 DES 的運算中，S box 的計算時間佔整體 32%，因此 有效減少 S box 的複雜度可以節省運算量，在 DESL 的架構內，將原本 8 個 的 S box 替換為一個新的 S box 架構，相較 DES 的 2310 個 GE，DESL 減少了 約 20%的計算量只需 1850 GE，又因為新增的 S box 是受到謹慎設計的，能 應付大部分的常見攻擊法，因此安全性並沒有下降太多。而 DESXL 則是在 DESL 的設計下，使用”key-whitening”的技巧，使得整體能提升到 118 bits 的安全性。
>4. Present:不同於改造現有的演算法，Present 是建立在 lightweight 的基準下 所設計的加密演算法，它的計算基於 substitution permutation network，進 行共 32 輪的 substitution 和 permutation，每個 block size 為 64 bits 而密鑰的
size 則為 80 或 128 bits。Present 的設計原則相當簡單，在沒有充分的理由 下，不隨意加入閘門至架構中，因此運算量相較其他演算法少，且它充分發 揮硬體的特性，硬體偏好重複執行相同的操作，因此 Present 的運算過程會 重複執行 substitution 和 permutation，但此特性容易遭到針對，所以每輪操 作中會額外添加不同的常數，並在此設計下 Present 可抵擋多數的攻擊。

>以軟體實作的對稱式 lightweight 加密演算法:
>在這階段，作者比較幾項透過軟體實作的 lightweight 演算法，Salsa20 和 LEX， 其中 LEX 是一種基於 AES 的 stream cipher 方法，一次只在一個或數個 bit 做操 作，它抽取部分中間狀態的密文作為 key stream 使用，而它的優點在於相對 AES 能更快地處理長訊息，而 Salsa20 也是一款 stream cipher 演算法，主要使 用 add-rotate-xor 的方式對資訊加密，運算過程簡單因此速度相當快。

- Asymmetric Ciphers:經典演算法有 ECC、RSA、discrete logarithms 等，其中 ECC 因為其相對低的計算量，被視作最適合嵌入式環境的非對稱式演算法。
> ECC:為了使用在資源受限的設備上，作者設計了一個以硬體實作的橢圓曲線演 算法，達到計算快速並保有安全性的要求。這邊犧牲掉演算法的靈活性，使用 binary field 而非 prime field，binary field 相較 prime field 可以更簡單的被硬體所 實作，因為在其計算過程不需要考慮進位問題，此外 binary field 的架構也相對 簡單，這可以使小型智慧設備更有效計算橢圓曲線演算法，同時也能達到 113 bits 的安全性，已達到多數的情況下的安全性要求。
---
---
## State of the Art in Lightweight Symmetric Cryptography
- Abstract
> 近年隨著5G通訊的發展帶動了人們對於物聯網(Internet of Things, IoT)應用的想像，IoT在各領域的廣泛應用變得越來越普遍。IoT裝置收集許多隱私數據並通過網路來傳輸，其資訊安全的重要性不言可喻。然而，IoT裝置為了快速廣泛佈署，通常具有輕量、簡潔、便利等特性，對於裝置的大小、電力消耗、CPU處理能力、記憶體儲存空間等都有諸多限制，無法負擔傳統密碼學演算法所需要的運算資源，故IoT裝置通常採用輕量級密碼學(Lightweight Cryptography)的演算法來確保資訊安全，目前已有超過50種的輕量級加密演算法可用於特定市場應用。標準制定方面，目前ISO/IEC 29192有一系列的相關規範仍在逐步增加，而NIST也自2015年起開始了新一代標準的徵選。
本文將探討Lightweight Cryptography的設計原理，將其軟硬體性能實現成本與傳統密碼學的優缺點予以比較，並同時說明其發展趨勢，如何在優化成本、性能和安全性之間取得平衡。
- Introduction
> 物聯網 (IoT) 是計算機科學中最重要的流行語之一，可預期不久的將來會有越來越多的設備利用互聯網相互連接，其中一些設備或許會具備如同個人電腦功能般的高效能處理器，並使用複雜的加密演算法。然而，更多的裝置僅會搭配低功耗的微控制器，只能承擔一小部分的計算力及安全性，常規的演算法可能會導致過高的延遲或者過高的功率消耗。lightweight是一個概念，對應不同的案例，有著各種不同屬性的演算法，因此很難針對該術語提出一個明確定義。例如，lightweight演算法是否可以安全抵禦大樣數據的攻擊、裝置是否僅適用於RFID設備？是否支援連結網路做下載更新？
- Design Constraints
> 通常優化是以記憶體消耗、演算法實作大小和計算速度作為評斷指標，成本低廉且具有高效率的晶片可能會遭受到side-channel attacks，抵禦side-channel attacks的效果也跟實作成本高低有所關聯，Lightweight演算法的標準即是去提供一個較佳的trade-off方法，在安全性、運算表現及所花費的成本間做權衡。
* 硬體部分：
* 所需記憶體消耗跟硬體空間大小，越小越好。
* 每秒處理明文的bits或bytes數，越高越好。
* 運算的延遲，越低越好。
* 電力消耗的瓦特數，越低越好。
上述四個標準是相互影響的。根據研究，相互比較不同的AES演算法實作，發現迄今為止實作成本最小的，速度也是迄今為止最慢的，但是最節省功率消耗的。在這些標準之間作較為理想的trade-off是需要考量使用情境，有些情境必須要低延遲，有些則是需要低功率消耗，不同的情境要有不同的方案。舉例來說，考量耗能效率的硬體實作，可以使用Midori，需要極低延遲可以選擇PRINCE。
* 軟體部分：
* RAM的消耗量跟用於加密函式的資料量多寡有關，以bytes為單位，應最小化。
* 程式碼大小是固定的，與輸入的資料量是獨立無關的，以bytes為單位，應最小化。
* 吞吐量(throughput)計算在每個時鐘週期內處理的平均數據量，以每個週期的字節數(bytes/cycle)為單位，應最大化。
上述三個標準也是相互影響的。例如，將資料從RAM加載到CPU registers是一項代價高昂的操作，從registers到RAM亦是如此。 因此，若限制此類操作的數量可以讓RAM消耗減少並增加吞吐量。
微控制器在8、16、32bits的words處理可能會產生與直覺相反的成本。在大多數的32位元處理器，所有32-bit rotations都有著相同的成本，但8位元微控制器並不適用這樣的做法，而是以8的倍數rotations，將8-bit registers做shuffling，而且也沒有其他專門的指令來處理32-bit rotations。基於上述理由，不同裝置有著不同位元的處理器，rotations的方式不一樣，耗費成本也就有所不同，這也跟硬體使用bit permutation成本較為低廉的情況不同。
而軟體部分跟硬體的狀況很像，在軟體部分有不同的trade-offs跟實作技術。舉例來說，block cipher的subkeys可以在加密過程中預先計算(precomputed)來達到節省時間。也可以在一些特定的狀況去使用較為複雜的技術像是bit-slicing來提升性能，近期一些lightweight演算法已可以在常規電腦上實現bit-slicing，如SKINNY或GIFT。
* Side-Channel Attack：
Side-channel attacks (SCAs)是一種基於對特定加密實現技術的知識而產生的攻擊手法。例如，透過觀察加密過程的功率消耗，可以得出有關S-Box的輸出的Hamming weight的洩漏訊息，功率消耗的估值S(0)必然會跟S(128)有所差異，這個功率消耗會透露出一些跟於S-box的輸入資訊及內部加密的狀態。這種類型的攻擊手法需要仰賴實體存取這些裝置才有辦法做到，像傳統電腦鎖在機房的話一般人是無法輕易存取，但具備無線sensor的IoT裝置卻可以輕易地滿足這個條件，進而達到上述攻擊手法。

- Trade-Offs in Lightweight Cryptography
* Performances vs. Security
在各種方面來說，Performances跟Security通常都是互斥的。最普遍的考量就是計算rounds的次數，較少次的rounds有較低延遲及較高資訊吞吐量，但也導致降低了Security。在考量計算速度跟安全性去選擇適當的rounds次數是一個有難度的權衡。這種權衡也以微妙的方式表現出來，例如，使用具有高代數次方(a high algebraic degree)、低微分均勻性(low differential uniformity)和低線性度( low linearity)的strong S-Box可以增加常見攻擊的抗性。然而，其必然伴隨較高的成本，甚至使用越高代數次方、越複雜的函式是越難去隱藏加密方式。所以，許多lightweight演算法的實現，比較傾向在那些容易隱藏加密方式的實作中才去選擇strong S-Box。
* Specialization vs. Versatility
Leightweight演算法的Trade-off，更具體地來說其實就是Specialization跟Versatility的比較。例如要思考演算法是否要針對特定的用途而去設計，或是可以在一般眾多情況下有較好的表現即可？例如KTANTAN、QUARK和Plantlet等演算法是特別就硬體中低gate數的狀況進行優化。又以Block cipher的PRINCE演算法為例，其採用較複雜的round function(對內部不同狀態的部分使用不同的二進制矩陣)，這些round的結構不盡相同，要完成序列化的實作較為困難。而從PRINCE的fuction level中也可以看到其Specialization之處，PRINCE的𝛼-reflection實作是一個採用Merkle-Damgård架構的壓縮hash function，如果是其他採用Stream ciphers的演算法就沒有辦法輕易地插入去使用這些運算。其他的演算法或許可以明確的設計用來跨平台運算去獲得更好的表現，像是採用Block cipher的Noekon演算法用了硬體實作較容易的bit-sliced S-Box，使用了名為rotations跟XORs的32-bits的word運算，可以在軟、硬體上很容易地被實作。甚至有些rotations是8的倍數，可以降低在8-bits微控制器上的實作成本。
* Subsets of Lightweight Cryptography
Lightweight Cryptography的subsets中，有一些為了提高性能而願意做出更大膽的設計，而另一些則力求多功能性和更保守的安全邊際。AES就是後者的一個很好的例子。 雖然它最小的實現在硬體需求上來說比Grain(Stream ciphers)要大，但其仍然具有相當的競爭力；並且，與Stream ciphers不同，其可以用於加密、身份驗證等。鑑於此，建議將primitives分為以下兩類，更重要的是，建議設計人員使用這種區分來更精確地分類他們的算法：
* Ultra-Lightweight Cryptography
對於使用案例非常特定的演算法，像是ASICs(採用低gate數的Stream cipher)、在高運算速度的32-bit微控制器上採用Block cipher的演算法等等，由於其性能是我們較為重視的因素，故在性能與安全性的權衡中做出更大膽的選擇是有意義的。此外，由於其使用情境已被限定，故只提供像是加密或身份驗證之類的單一功能。此類的primitives範例像是：Grain（硬體中gate數較少的stream cipher）、Qarma（硬體中具有低延遲的可調整block cipher）和 Chaskey（微控制器上的高速MAC）等等。
* Ubiquitous Cryptography
在功能和屬性等面向有較多功能性的primitives，應用在各種平台（8位、16位、32位微控制器、ASIC、FPGA、32位和64位處理器）上高效運行，並允許有效抵抗Side-channel attacks的對策實作，其應該提供下列幾種功能：雜湊、加密、身分驗證。此類的primitives範例像是：Ascon、GIMLI 及AES等等。
- Conclusion
> lightweight Cryptographic在過去的二十年中受到了極大的關注，在過去的5年中更是如此。 AES演算法在軟、硬體中雖然都有良好的表現，但仍不能解決所有的設計限制。NIST和CRYPTREC著手進行標準化lightweight Cryptographic演算法，證明了對該演算法的需求已逐漸提升。最後，作者建議區分Ultra-Lightweight Cryptography和Ubiquitous Cryptography的密碼學，討論primitives應提供的安全級別時可以作為標準。
---
## A Survey on Lightweight Cryptographic Algorithm
- Introduction:
>與前一篇高度重複
- Lightweight Cryptography Algorithms:
>物聯網設備在現代社會中有極廣泛的應用，而如何安全地保存這些裝置的資訊成為一項議題，因為這些設備受限於有限的運算能力、電源供應和儲存空間，因此，需要為這些低效能的設備設計專門的加密演算法，稱為輕量級演算法，這些演算法的共同的特點是對基本資源要求極低，包括:用於計算的硬體大小、微處理機的計算能力、RAM、ROM 等。
其中，輕量級演算法可分為 block cipher 和 stream cipher 二種。
- Block cipher:
>1. S-AES:
Simplified AES，操作流程基本上和 AES 相同，差別在於使用的 key size 為 16 bits，block size 為 16 bits，同時也減少 round 的數量，僅進行兩輪，在此架 構下運算量得以降低，加密時只需要 3600 Gate equivalents，而即便在減少 AES 架構的複雜度後，遭受 biclique attack 仍能保持其安全性。
>2. ICEBERG:
是一種快速的 involutive cipher，使用 128 bits 的 key 和 64 bits 的 block，共 執行 16 輪，此演算法的優勢在於硬體實作下可以在每個 clock cycle 中更改 key，而不會降低性能，因此可以非常有效率的產生各種加密及解密組合， 至於計算量的部分，它共需要 5800 GE 來達到 400kbps 的輸出。
>3. DES 及延伸:
和前篇 paper 內容相近。
>4. TEA 及延伸:
Tiny encryption algorithm，是一種適用於微小裝置的快速安全 feistel 演算 法，它使用 128 bits 的 key 和 64 bits 的 block，並且不使用 S- box，進行共 32 輪的操作卻只需要 2100 GE，相較只進行 16 輪的 DES 還快，但它也存在 安全性的風險，使用 equivalent key attack 可將其破解，因此延伸出 XTEA 補 足安全上的缺陷，XTEA 使用更加複雜的 key，使每一輪使用的密鑰有更大的 差別，並重新排列 TEA 的架構如 addition 或 xor，但經證實 XTEA 的安全性依 舊不足，所以再次更改架構設計 XXTEA 來減輕此問題。
>5. Miniature CRYPTON:
根據 crypton 架構所改良的演算法，他使用 64 bits 的 block size，和共 13 round 的運算，最精簡的 mCRYPTON 實作下只需 2709GE，並且可以調整 key size 以配合不同的設備。
>6. HIGHT:
64 bits 的 block size 和 128 bits 的 key，共 32 輪的運算，具有低耗能低計算 量的特性，非常適合在計算能力受限的設備上使用，只需要 3048 GE，而安 全性很好能通過 NIST 的所有檢測。
- Stream ciphers:
>1. GRAIN:
專門為體積非常小的硬體所設計的演算法，最大化減少使用的 gate 數量並 維持其安全性，它的架構主要為兩個 shift register，而兩個 shift register 輸出 的頻率為 1 bit/clock。此架構共用到 4008 GE。
>2. Trivium:
透過硬體實作的同步 stream ciphers 演算法，可以讓使用者在速度和體積間
做選擇，其核心架構是一個密碼學安全的偽亂數產生器(CSPRNG)，將 plaintext 和 initial vector 送入 CSPRNG 產生亂數後，再使用 key 和亂數做 XOR，便會得到 ciphertext。
- Hybrid Ciphers:結合 block cipher 和 stream cipher 的特性
>1. Hummingbird:
使用 256 bits key 和 16 bits block size，共 20 rounds 的計算，由於組合兩種 symmetric algorithm，因此可以在使用較小的 block size 同時符合安全性的需 求，且也能滿足小型設備對於能耗的限制。
- Attacks on Lightweight Ciphers:
>在設計輕量級演算法時，必須對安全性、成本及效率作考量，例如密鑰的長度 影響了安全性及成本，硬體架構則影響了安全性和效率，要同時顧及三項需求 是一件困難的事，而密碼分析旨在分析輕量級演算法在追求成本及效率的同 時，是否會使安全性有所降低。常見的密碼分析可分為三大類:differential attack、linear attack、integral analysis。
- 對上述 lightweight 演算法的分析:
>1. S-AES:
目前仍未發現可以破解 AES 演算法的攻擊，但有幾項研究指出對於簡化版的 S-AES 可透過 particle swarm optimization 的方式分析密鑰，透過 linear attack 的方式可以使只有兩輪的 S-AES 在 linear calculation 下被破解。
>2. ICEBERG:
ICEBERG 在 differential attack 和 linear attack 下，能分別保持它的 key 複雜度 在 160 bits 和 64 bits，這對於一般的使用已達到極高的安全性，同時它也可 以透過調整加密模式來抵擋大部分的 side-channel attacks，因此 ICEBERG 較 難被破解。
>3. DES and its variants:
部分攻擊使用 differential attack 檢查 S-box 之間的 collision，可以藉此推斷出 DES 的密鑰，但若採取 key-whitening 來增加演算法的複雜度，便可抵擋此類
攻擊，同時減少 S-box 的數量也可以有效避免此問題，因此 DES 的變化版具
有更高的安全性。
>4. TEA and its extension:
TEA 容易被 equivalent keys、related-key、slide attacks 所破解，而其延伸 XTEA 和 XXTEA 也有研究指出受到 chosen plaintext attack，它們的複雜度會大 幅降低，因此 TEA 是較不安全的演算法。
>5. Miniature CRYPTON:
根據研究，related-key rectangle 在面對 mCRYPTON 時有高達 94%的正確率， 因此 mCRYPTON 並不足夠安全。
>6. PRESENT:
常見的破解方式是採用 statistical saturation attack，它只需 2 的 35.6 次方的 Plaintext/ciphertext pairs，便可將長達 15 輪的 PRESENT 所破解，此外 PRESENT 也容易被 side-channel attacks 破解。
>7. HEIGHT:
經過實驗，related-key impossible differential attacks 可以大幅降低其安全 性，因此 HEIGHT 所使用的 round 數必須較高才能避免此問題。
>8. GRAIN:
對 GRAIN 的攻擊法中，經研究證實 shortcut key-recovery attacks 和 Related- key attacks 可以有效破解出 key。
>9. Trivium:
Trivium 較難抵擋 fault injection attack，injection attack 攻擊標準的 trivium 成 功率為 68%至 100%。
>10. Hummingbird:
當 Hummingbird 中的 stream cipher 架構 degree 較低，容易被 cube attack 所 攻擊，此外當它受到 related-key chosen-IV attack，他的 key 可以在 2 的 27 次方內破解，經過實測只需 10.2 至 16.1 分鐘便可回推出 key，因此它的安 全性並不符合大多數的應用。
---
## Lightweight cryptography methods

- Methods

在輕量級加密演算法之中，PHOTON、SPONGENT以及Lesamanta-LW為ISO/IEC 29192-5:2016核定的雜湊演算法標準。
> 除雜湊之外的類型大量重疊，略過
- 雜湊（Hashing）
MD5與SHA-1以及現代大多數用於加密的雜湊函式對於物聯網設備來說不夠有效率。因此，NIST建議使用新的雜湊方式，例如：SPONGENT、PHOTON、Quark以及Lesamnta-LW。這些方法相較來說少佔用了很多記憶體，並且只需要目標輸入256個字元（一般雜湊函式最高支援64位元的輸入）。
- SPONGENT
SPONGENT使用的Sponge函式如下圖所示。總體而言，該方法使用有限狀態機、並通過加入輸入資料的同時來迭代其狀態。除了可以被應用在雜湊上，SPONGENT還可以被用於建立Stream Cipher。
- Lesamnta-LW
Lesamnta-LW使用AES作為其核心，並且使用與AES相同的S-box結構。開發人員預估它只需要8.24k Gates，並且擁有125 Mbit/s的吞吐量（比SHA-256快5倍，並且還提供256-bit的雜湊）。另外在8-bit處理器上，開發人員估計Lesamnta-LW只需要使用50 bytes的RAM。
- Quark
Quark主要由三種不同方法組成：u-Quark、d-Quark以及s-Quark，並且同樣使用Sponge函式。Quark除了可以被使用到雜湊上、也可以被應用在Stream加密。在三種方法之中，u-Quark佔用的空間最小，並可在1379 digital gate上提供64-bit security，至於s-Quark則可提供112-bit security。
- Keccak
Keccak是加密Sponge函式的成員之一，已於 2015年成為FIPS 202（SHA-3）的標準。Keccak在硬體與軟體方面都可以提供很高的彈性和效能，並且具有適度的implementation size與RAM使用量，因此適用於輕量級的應用程式。
- PHOTON
PHOTON是一種基於AES-type方法、用於雜湊的輕量級加密演算法。它可以建立80-bit、128-bit、160-bit、224-bit以及256-bit的雜湊，並接受任意長度的輸入以產生可變長度的輸出。

- 輕量級雜湊演算法的摘要

---
## A Survey on Lightweight Cryptographic Algorithm
- Introduction:
物聯網 (IoT) 在智能交通與物流、智能醫療、智能環境、智能基礎設施（智能城市、智能家居、智能辦公室、智能商場、工業 4.0）、智能農業等各個領域的應用已成為近年的熱門研究題材。許多研究人員和行業專家根據其應用和實施領域對物聯網給出了不同的定義，但簡單來說，物聯網是一個連接事物的網絡，每個事物都有一個唯一的標識，能夠通過網絡收集和交換數據。在任何物聯網解決方案或應用程序中，物聯網設備都是關鍵元素。 這些物聯網設備可分為兩大類：

1.擁有豐富資源：伺服器、個人電腦、平板電腦和智能手機等。
2.資源受限：工業sensor或sensor node、RFID標籤等。
在本文中，我們關注第二類物聯網設備。 這些連接的設備由於其在各種應用中的使用而變得越來越流行，並將隨著物聯網的出現湧入市場，從而導致之間的巨大數據交換率。
當數十億智能設備（連接設備）在不同的平台上工作時，尤其是從伺服器轉向sensor時，會給它們的所有者或用戶帶來各種前所未有的挑戰，例如安全和隱私、互操作性、壽命和支持程度、技術等等。此外，物聯網設備很容易被訪問並暴露於許多安全攻擊，因為它們直接與物理世界交互以收集機密數據或控制物理環境變量，這使得它們成為攻擊者的有吸引力的目標。
所有這些情況都使網絡安全成為物聯網設備面臨的一項重大挑戰，需要機密性、數據完整性、身份驗證和授權、可用性、隱私和監管標準以及定期系統更新 。

在這種情況下，密碼學可能是保證通過物聯網設備遍歷數據的機密性、完整性以及身份驗證和授權的有效措施之一。它也可以是一種用來保護通過網絡存儲或遍歷的數據的解決方案。然而，傳統基於 PC 的加密算法由於資源需求高，不適合資源受限的物聯網設備。這些解決方案的更輕量級版本，lightweight cryptography可以解決這些挑戰，以保護在資源受限的物聯網設備中的通信。
- Lightweight cryptography的特性：
- (硬體與軟體以及各演算法的細節與上面內容高度重複，此部分省略，保留部分補充)
CLEFIA 提供 128 位塊，分別通過 18、22、26 round選擇 128、192、256 位的key。它以相對較高的成本顯示出高性能和對各種攻擊的強大免疫力，因為最緊湊的版本需要 2488 GE（僅加密）用於 128 位key。 CLEFIA 對安全攻擊的強大免疫力得益於其雙重混淆和擴散特性。 相反的，這需要更高的記憶體資源並限制其在超小型應用中的使用。

- Lightweight cryptography軟硬體實作細節一覽表及排行：
- Lightweight cryptography安全性比較一覽表：

- Conclusion
由於各個領域的物聯網設備數量呈指數增長，物聯網安全是近期關注點之一。因此，需要一種在成本、性能和安全性之間進行權衡的輕量級算法。對於資源受限的物聯網設備，Lightweight cryptography是一種通過轉換數據來保護通信的有效方法。從文獻回顧來看，PRESENT 和 CLEFIA 是 NIST 批准的block cipher，因為其安全性以及可接受的性能和成本。

---
## NISTIR 8369

- Introduction
NIST（National Institute of Standards and Technology）近年來正在通過一個公開、競爭的方式來選擇適用於受限環境中、應用於身份驗證的一種或多種加密與雜湊方案，並且於2021年7月發布了NIST Internal Report (NISTIR) 8369，也就是針對輕量級密碼標準化流程的第二輪進度報告。從2019年2月的57個候選演匴法、2019年4月的56個、到2019年9月的32個進入第二輪評選，而一直到2021年3月，NIST終於宣布了10名進入最終評選的名單。NISTIR 8369此報告主要就是在說明第二輪評選時的評估標準以及評選過程。

- 第二輪評選主要更新內容
1. 能夠支持安全聲明的新證明與論據。
2. 新的軟體與硬體實現方式（包括能夠防止Side-channel Attacks的類型）。
3. 新的第三方分析結果與預期可能產生的結果或影響（Implications）。
4. 候選演算法表現優於當前NIST標準的平台與指標
5. 優化候選演算法的目標應用程式以及使用案例。
6. 如果提交的演算法成功進入評選名單，計劃調整的內容與任何其他相關資訊。

- 10名進入最終評選的演算法名單
- ASCON
- Elephant
- GIFT-COFB
- Grain-128AEAD
- ISAP
- PHOTON-Beetle
- Romulus
- SPARKLE
- TinyJAMBU
- Xoodyak

- 評估標準（Evaluation Criteria）

標準化流程的評估標準於2018年8月公布，下列總結了第二輪評選時的標準：
1. Cryptographic Security
為最重要的評選標準。主要著重於演算法是否經過具有影響力的第三方分析，並且基於易於理解的設計原則和安全性證明。 NIST除了自己的內部分析外，還會研究從密碼學社群收到的回饋以及提交者提供的文件。
2. Performance
針對候選演算法在各種性能和成本指標方面進行了評估與比較，主要著重於那些表現明顯優於當前NIST標準（尤其是AES-GCM和SHA-2）的演算法。
3. Side-channel Resistance
儘管針對這個方面對候選演算法的綜合比較並不多，但NIST有將提交文件中的聲明和相關文獻作為衡量標準。
4. 其他
沒有明確要求，但是若多個候選演算法的安全性以及效能差不多時會考慮下列標準：
- Nonce-Misuse Security
Nonce-Misuse Resistance Schemes確保說即使隨機的nonce被重複使用也不會洩漏明文，而在Nonce-Misuse Scenario中，發現可以通過發現State Collision進行簡單的偽造攻擊，因此沒有任何一個第二輪候選演算法能夠保證其完整性。
- Releasing Unverified Plaintext（RUP） Security
在Releasing Unverified Plaintext（RUP）的情境底下，即使使用的是無效的Tags，也可以通過解密查詢取得未經驗證的明文。當AEAD加密模式能夠在RUP情境底下保證其完整性，我們又稱之為INT-RUP-secure。然而沒有任何一個第二輪候選演算法有INT-RUP-secure。
- Impacts of State Recovery
通過對密碼內部狀態的了解分析從中恢復密鑰的複雜性。部分第二輪候選的演算法聲稱支援額外的功能，確保可以在State Recovery的情況下也能僅受到有限的損失。
下列這些演算法都基於具有金鑰初始化與Finalization階段的Sponge-type模式，因此很難透過了解Secret State就成功復原密鑰：
- ACE、ASCON、ISAP、SPIX、Spook以及WAGE
- Post-Quantum Security
儘管標準化的流程沒有正式要求此項目，但是針對量子威脅的防護在現今已經是一個值得關注的議題。一個夠強大的量子電腦可以輕易破解基於Integer Factorization、Discrete Logarithm以及Elliptic-Curve Discrete Logarithm問題的公鑰加密系統。下列為第二輪之中有針對量子安全於提交文件說明的候選演算法：
- ASCON、Gimli以及SATURNIN

---
### References

- [對 Lightweight Cryptography 的簡單 Survey](https://blog.allenchou.cc/post/lightweight-crypto/)
- [NISTIR 8369: Status Report on the Second Round of the NIST Lightweight Cryptography Standardization Process. https://doi.org/10.6028/NIST.IR.8369](https://csrc.nist.gov/publications/detail/nistir/8369/final) (Done)
- [Lightweight Cryptography Algorithms for Resource-Constrained IoT Devices: A Review, Comparison and Research Opportunities](https://ieeexplore.ieee.org/document/9328432) (Done)
- [Recent Advances and Trends in Lightweight Cryptography for IoT Security](https://ieeexplore.ieee.org/document/9269083)
- [State of the Art in Lightweight Symmetric Cryptography](https://eprint.iacr.org/2017/511.pdf)(Done)
- [A survey on lightweight-cryptography status and future challenges](https://ieeexplore.ieee.org/document/8370965)
- [W. Julian Okello, Q. Liu, F. Ali Siddiqui and C. Zhang, "A survey of the current state of lightweight cryptography for the Internet of things," 2017 International Conference on Computer, Information and Telecommunication Systems (CITS), 2017, pp. 292-296, doi: 10.1109/CITS.2017.8035317.](https://ieeexplore.ieee.org/document/8035317) (Done)
- [A Survey of Light-Weight Cryptographic Algorithm for Information Security and Hardware Efficiency In Resource Constrained Devices](https://ieeexplore.ieee.org/document/8899376)
- [Lightweight cryptography for constrained devices](https://ieeexplore.ieee.org/document/7029580)
- [A Survey on Lightweight Cryptographic Algorithms](https://ieeexplore.ieee.org/document/8650352) (閱讀中)
- [A Survey of Lightweight-Cryptography Implementations](https://ieeexplore.ieee.org/document/4397176) (Done)
- [Buchanan, W., Li, S., & Asif, R. (2017). Lightweight cryptography methods. Journal of Cyber Security Technology, 1(3-4), 187-201. https://doi.org/10.1080/23742917.2017.1384917](https://doi.org/10.1080/23742917.2017.1384917) (Done)