ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

KHUẤT QUANG DUY

NGHIÊN CỨU HAI HỆ MẬT MÃ HẠNG NHẸ GIÀNH
CHIẾN THẮNG TRONG CUỘC THI CAESAR
ACORN VÀ ASCON

LUẬN VĂN THẠC SĨ
Ngành: Khoa học máy tính

HÀ NỘI - 2019


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

KHUẤT QUANG DUY

NGHIÊN CỨU HAI HỆ MẬT MÃ HẠNG NHẸ GIÀNH
CHIẾN THẮNG TRONG CUỘC THI CAESAR
ACORN VÀ ASCON

Ngành: Khoa học máy tính
Chuyên ngành: Khoa học máy tính
Mã số: 8480101.01

LUẬN VĂN THẠC SĨ
Ngành: Khoa học máy tính


Đầu tiên, tôi muốn gửi lời cảm ơn chân thành nhất tới tiến sĩ Lê Phê Đô, người đã
luôn tận tình hướng dẫn tôi nghiên cứu đề tài này. Nếu không có sự định hướng, những
lời dạy bảo của thầy thì luận văn này tôi rất khó có thể hoàn thiện được.
Tôi xin cảm ơn Khoa công nghệ thông tin, Trường Đại học Công nghệ đã tạo điều
kiện, môi trường thuận lợi cho học viên trong quá trình học tập, nghiên cứu và hoàn thiện
luận văn thạc sĩ.
Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới các thầy, cô, bạn bè trong khoa
Công nghệ thông tin, ngành Khoa học máy tính, đã luôn nhiệt tình giúp đỡ tôi trong suốt
quá trình học tập và nghiên cứu.
Cuối cùng, tôi muốn gửi lời cảm ơn tới gia đình, người thân, những người luôn quan
tâm, động viên để giúp tôi có động lực học tập, nghiên cứu và hoàn thiện đề tài nghiên
cứu này.
Bước đầu đi vào nghiên cứu, tìm hiểu các vấn đề về An toàn thông tin với kiến thức
còn hạn chế, do vậy tôi không tránh khỏi những thiếu sót trong luận văn này. Tôi rất
mong nhận được những ý kiến đóng góp của các thầy cô và bạn bè để hoàn thiện luận văn
hơn nữa.
Tôi xin chân thành cảm ơn!


iii

LỜI CAM ĐOAN
Tôi xin cam đoan các kết quả trong luận văn này là do tôi thực hiện dưới sự hướng
dẫn của tiến sĩ Lê Phê Đô.
Tất cả các tham khảo từ những nghiên cứu liên quan đều được trích dẫn nguồn gốc
một cách rõ ràng từ danh mục tài liệu tham khảo trong luận văn. Luận văn không sao chép
tài liệu, công trình nghiên cứu của người khác mà không chỉ rõ về mặt tài liệu tham khảo.
Các kết quả thực tế của luận văn đều được tiến hành thực nghiệm.
Nếu phát hiện có bất kỳ sự gian lận nào, tôi xin hoàn toàn chịu trách nhiệm trước hội
đồng, cũng như kết quả luận văn tốt nghiệp của mình.

1.1.2.

Nguyên lý thiết kế ......................................................................................... 3

1.1.3.

Quá trình phát triển ....................................................................................... 5

1.2.

Mã hóa có xác thực .............................................................................................. 6

1.2.1.

Khái niệm ..................................................................................................... 6

1.2.2.

Nguyên lý thiết kế ......................................................................................... 7

1.2.3.

Quá trình phát triển ....................................................................................... 8

1.3.

Cuộc thi CAESAR ............................................................................................. 10

Chương 2: HAI HỆ MẬT MÃ HẠNG NHẸ GIÀNH CHIẾN THẮNG TRONG CUỘC
THI CAESAR: ACORN VÀ ASCON ............................................................................ 16

Các đặc trưng an toàn của thuật toán ........................................................... 40

2.2.3.

Một số cuộc tấn công lên hệ mã Ascon ....................................................... 44


v
2.2.4.

Hiệu suất của thuật toán .............................................................................. 50

Chương 3: CÀI ĐẶT THỰC NGHIỆM TRÊN THIẾT BỊ ANDROID ........................... 53
3.1.

Mô tả bài toán .................................................................................................... 53

3.2.

Cài đặt ............................................................................................................... 53

3.2.1.

Môi trường thực nghiệm ............................................................................. 53

3.2.2.

Cài đặt thuật toán ACORN (v3), Ascon-128 (v1.2) và AES-128-GCM ....... 54

3.2.3.

Hình 2.1: Kiến trúc thanh ghi dịch của ACORN [19] ...................................................... 16
Hình 2.2: Lược đồ mã hóa của ACORN [20] .................................................................. 20
Hình 2.3: Cơ chế hoạt động của Ascon [32] .................................................................... 34
Hình 2.4: Cấu trúc từ thanh ghi trạng thái của Ascon [32] ............................................... 37
Hình 2.5: Cấu trúc lớp thay thế của Ascon [32]............................................................... 38
Hình 2.6: Triển khai bitsliced của S-box 5 bit S(x) [32] .................................................. 39
Hình 2.7: Lớp khuếch tán tuyến tính của Ascon, trộn các bit trong các từ thông qua hàm
∑𝑖 (𝑥𝑖 ) [32]...................................................................................................................... 40
Hình 3.1: Java Native Interface trong Android ................................................................ 56
Hình 3.2: Kiến trúc ứng dụng CryptoCamera .................................................................. 57
Hình 3.3: Giao tiếp socket thông qua giao thức UDP ...................................................... 58
Hình 3.4: Ứng dụng CryptoTest để đánh giá thời gian thực thi ....................................... 59
Hình 3.5: Ứng dụng CryptoCamera truyền video mã hóa thời gian thực ......................... 60
Hình 3.6: Thời gian thực thi của các thuật toán ............................................................... 61
Hình 3.7: Kích thước bộ nhớ RAM bị chiếm khi thực hiện mã hóa – giải mã.................. 62


vii

DANH MỤC BẢNG BIỂU
Bảng 1.1: Số lượng ứng viên tham dự CAESAR............................................................. 11
Bảng 1.2: Các ứng viên bị loại và rút khỏi cuộc thi ......................................................... 11
Bảng 1.3: Một số cuộc tấn công trên các ứng viên của CAESAR .................................... 13
Bảng 2.1: Sự khác nhau giữa ACORN-v1 và ACORN-v2,v3 .......................................... 19
Bảng 2.2: Một số cuộc tấn công lên hệ mã ACORN ....................................................... 26
Bảng 2.3: Tốc độ (cpb) của ACORN với các độ dài bản rõ khác nhau ............................ 32
Bảng 2.4: Các tham số cài đặt đề xuất cho Ascon [32] .................................................... 33
Bảng 2.5: Hằng số vòng sử dụng trên các hoán vị pa và pb [32] ....................................... 37
Bảng 2.6: S-box 5 bit của Ascon [32] ............................................................................. 38
Bảng 2.7: Tuyến bố bảo mật của Ascon [32] ................................................................... 40

con người được cung cấp một định danh
của riêng mình, và tất cả có khả năng
truyền tải, trao đổi thông tin, dữ liệu qua
một mạng duy nhất mà không cần đến sự
tương tác trực tiếp giữa người với người,
hay người với máy tính

CAESAR

Competition for Authenticated Encryption:
Security, Applicability and Robustness:
cuộc thi lựa chọn một thuật toán mã hóa có
xác thực đảm bảo ba yếu tố là tính bảo mật,
khả năng ứng dụng và độ mạnh

RFID

Radio Frequency Identification: Hệ thống
nhận dạng bằng tần số của sóng vô tuyến

RAM

Random Access Memory: một loại bộ nhớ
khả biến cho phép truy xuất đọc-ghi ngẫu
nhiên đến bất kỳ vị trí nào trong bộ nhớ dựa
theo địa chỉ bộ nhớ

PC

Personal Computer: máy tính cá nhân


Message authentication code: Mã xác thực
thông báo

SSL/TLS

Secure

Sockets

Layer/Transport

Layer

Security: là các giao thức mật mã được thiết
kế để cung cấp truyền thông an toàn qua
một mạng máy tính
IND-CPA

Indistinguishability under chosen-plaintext
attack: định nghĩa về an toàn cho hệ khóa
công khai

WPA

Wifi Protected Access: Phương thức được
liên minh Wifi đưa ra để thay thế WEP

WEP


mạch điện tử kỹ thuật số

UDP

User Datagram Protocol: giao thức giúp
chương trình trên mạng máy tính có thể gửi
những dữ liệu ngắn tới máy khác. UDP
không cung cấp sự tin cậy và thứ tự truyền
nhận

MSB

Most significant bit: bit có trọng số cao
nhất

LSB

Least significant bit: bit có trọng số thấp
nhất


1

MỞ ĐẦU
1.

Cơ sở khoa học và tính thực tiễn của đề tài
Trong thời đại phát triển bùng nổ của cuộc cách mạng công nghiệp 4.0, nhu cầu về

kết nối và trao đổi thông tin ngày càng trở nên mạnh mẽ. Đi cùng với đó là yêu cầu về vấn


Nội dung nghiên cứu
Nội dung chính của luận văn được trình bày trong 3 chương:
Chương 1: Giới thiệu tổng quan về mật mã nhẹ, mật mã có xác thực (một số khái

niệm, nguyên lý thiết kế, quá trình phát triển) và cuộc thi CAESAR.
Chương 2: Nghiên cứu hai hệ mật mã nhẹ giành chiến thắng trong cuộc thi
CAESAR: ACORN và Ascon. Trình bày tổng quan thuật toán. Đánh giá các thuật toán
trên phương diện đặc trưng an toàn và hiệu suất trong cài đặt.
Chương 3: Cài đặt và so sánh hiệu suất của các thuật toán ACORN, Ascon và AESGCM trên điện thoại thông minh chạy hệ điều hành Android. Xây dựng và đánh giá tính
khả thi của ứng dụng truyền video thời gian thực sử dụng các thuật toán mã hóa nói trên.


3

Chương 1: TỔNG QUAN
1.1. Mật mã nhẹ
1.1.1.

Khái niệm

Hiện nay, vẫn chưa có một định nghĩa chính thức nào về mật mã nhẹ được công bố
bởi các hệ thống đánh giá mật mã tiêu chuẩn. Tuy nhiên, trong nhiều nghiên cứu, mật mã
nhẹ có thể được hiểu là những thuật toán và giao thức mật mã được thiết kế để phù hợp
cho việc cài đặt trên các môi trường bị hạn chế về tài nguyên như các thẻ RFID, cảm biến,
thẻ thông minh, các hệ thống nhúng, …
Các đặc trưng của mật mã nhẹ được mô tả trong tiêu chuẩn ISO/IEC 29192 [1].
Theo đó, độ an toàn tối thiểu của mật mã nhẹ là 80 bit. Đặc tính “nhẹ” phụ thuộc vào nền
tảng cài đặt. Đối với triển khai phần cứng, đặc tính này được tính toán và đo lường thông
qua diện tích chip và năng lượng tiêu thụ. Đối với triển khai phần mềm, kích thước mã


4

An toàn
48 vòng

256 bit

Kích thước khóa

Số vòng

80 bit

8 vòng

Chi phí

Hiệu suất
Kiến trúc
Nối tiếp

Song song

Hình 1.1: Nguyên lý thiết kế của mật mã nhẹ
Trên thực tế, có thể dễ dàng đạt được hai trong số ba mục tiêu thiết kế. Trong khi
đảm bảo được cả ba mục tiêu lại là một nhiệm vụ khá khó khăn. Ví dụ, có thể thiết kế
được một thuật toán có độ an toàn và hiệu suất tốt, nhưng để thực thi thuật toán lại yêu
cầu phần cứng với diện tích mạch lớn, dẫn đến tăng chi phí.
Một số phương pháp thường được các nhà mật mã học sử dụng để đạt được các mục

Nhu cầu về mật mã nhẹ xuất phát từ một thực tế rằng mạng lưới kết nối vạn vật
(IoT) ngày càng phát triển mạnh. Số lượng lớn thiết bị được kết nối với nhau đồng nghĩa
với việc những rủi ro về bảo mật sẽ tăng lên. Hơn nữa, không phải chỉ những thiết bị
truyền thống với khả năng xử lý mạnh mẽ như PC, laptop, điện thoại di động, mà còn có
rất nhiều các thành phần khác, với khả năng tính toán và cơ sở phần cứng hạn chế được
kết nối vào các mạng IoT (như các cảm biến, thẻ thông minh, thiết bị y tế, …). Do đó, yêu
cầu đặt ra là cần xây dựng những mật mã có khả năng thực thi trên môi trường tài nguyên
giới hạn trong khi vẫn đảm bảo được được độ an toàn cần thiết.
Nghiên cứu về mật mã nhẹ trở nên phát triển từ năm 2004 với dự án đầu tiên được
chọn làm chủ đề cho Chương trình Khung (Framework Programmes) lần thứ 6 và 7 của
Liên minh Châu Âu. Quá trình tiêu chuẩn hóa vẫn đang được hoàn thiện, bao gồm tiêu
chuẩn ISO/IEC 29192, trong đó định nghĩa các thuật toán mật mã nhẹ cho từng lĩnh vực
kỹ thuật và ISO/IEC 29167, mô tả công nghệ mật mã nhẹ cho các thiết bị nhận dạng tần
số vô tuyến (RFID). Viện Tiêu chuẩn và Kĩ thuật Quốc gia (NIST) Hoa Kỳ cũng đã tổ
chức những hội thảo về mật mã nhẹ từ năm 2015 và chính thức phát động chương trình
“Lightweight Cryptography” để thu hút, đánh giá và chuẩn hóa mật mã nhẹ vào năm 2017
[2].
Trong vòng 25 năm qua, đặc biệt từ năm 2011, rất nhiều thuật toán mã hóa theo
khuynh hướng “nhẹ” đã ra đời. Dưới đây là thống kê số lượng mật mã nhẹ đối xứng tính
đến năm 2017 (Hình 1.2) [3]


6

Hình 1.2: Số lượng mật mã nhẹ đối xứng tính đến 2017
Tháng 4/2019, NIST đã công bố danh sách 56 thành viên (trên tổng số 57 yêu cầu
được gửi đến) cho vòng đầu tiên của dự án “Lightweight Cryptography” [2]. Chương
trình hứa hẹn sẽ tìm ra được những ứng viên chiến thắng, trở thành tiêu chuẩn mật mã nhẹ
và được sử dụng rộng rãi trên toàn bộ thị trường.
1.2. Mã hóa có xác thực


Hình 1.3: Mã hóa có xác thực
1.2.2.

Nguyên lý thiết kế

Cách tự nhiên nhất để xây dựng các lược đồ mã hóa xác thực là kết hợp các nguyên
thủy mã hóa hiện có. Phương pháp này được gọi là “generic composition” [4]. Có ba cách
tiếp cận chính, bao gồm: Encrypt-and-MAC, Encrypt-then-MAC và MAC-then-Encrypt.

Bản rõ

Bản rõ

Bản rõ

Khóa

Hàm băm
Mã hóa

Khóa 1

Mã hóa

Khóa

Hàm băm
Bản rõ


(transport layer) của SSH
Encrypt-then-MAC (EtM)
Đầu tiên, bản rõ được mã hóa, sau đó MAC được sinh ra dựa trên bản mã kết quả.
Bản mã và MAC được gửi đi cùng nhau. Cách tiếp cận này được sử dụng trong giao thức
IPsec.
MAC-then-Encrypt (MtE)
MAC được tạo ra dựa vào bản rõ. Sau đó bản rõ và MAC cùng được mã hóa để thu
được bản mã. Bản mã (chứa MAC đã mã hóa) được gửi đi. MtE được sử dụng trong giao
thức SSL/TLS
Thông qua nghiên cứu của mình, Ballare và Namprempre cũng đã chứng minh rằng
mã hóa một bản tin, sau đó áp dụng MAC vào bản mã (EtM) là tối ưu hơn so với hai
phương pháp còn lại [4].
Ngoài các cách tiếp cận tự nhiên như trên, cũng có nhiều cách khác để xây dựng mật
mã có xác thực. Trong những năm qua , nhiều lược đồ mã hóa xác thực hiệu quả hơn đã
được xây dựng bằng các kỹ thuật khác nhau [5, 6], bao gồm hoán vị không sử dụng khóa
(keyless permutations) [7] và mật mã dòng [8]. Những cách tiếp cận mới này đã thay đổi
hiểu biết của các nhà mật mã học về AE từ việc pha trộn các nguyên thủy mật mã sang
xây dựng một một khối thống nhất ngay từ đầu.
1.2.3.

Quá trình phát triển

Nhu cầu về mã hóa xác thực được hình thành từ việc chúng ta nhận thấy rằng một số
cuộc tấn thực tế được đưa vào các giao thức (bao gồm SSL/TLS) là do thiếu xác thực và
kiểm tra tính toàn vẹn của dữ liệu.
Giao thức Needham-Schroeder được Roger Needham và Michael Schroeder phát
minh vào năm 1978, là một giao thức vận chuyển hướng tới sử dụng trên các mạng không
an toàn. Bao gồm giao thức Needham-Schoroeder khóa đối xứng, nhằm mục đích thiết




10
bản tin. WEP sau đó đã được đổi thành WPA (sử dụng TKIP), bản dự thảo tiếp theo dựa
trên OCB (R, Bellare, Black, Krovetz 2001). Tuy nhiên để tránh các vấn đề về chính trị
và bằng sáng chế, CCM (Whiting, Housley, Ferguson 2002) đã được phát triển và sử
dụng cho WPA2.
Kể từ năm 2017, “Galois Counter Mode” (GCM) [14, 15] đã trở thành kỹ thuật phổ
biến nhất để chuyển đổi một lược đồ mã hóa thông thường sang AE. GCM thường được
áp dụng cho AES, và lược đồ AES-GCM được sử dụng trong rất nhiều cài đặt khác nhau,
ví dụ như các giao thức bảo mật cho Ethernet, OpenVPN, và nhiều dịch vụ giao tiếp web
an toàn khác. Số lượng ứng dụng và bối cảnh cần đến mã hóa có xác thực ngày càng tăng,
cũng như những điểm yếu đã xuất hiện trong GCM [16], đã đặt ra yêu cầu định nghĩa một
tiêu chuẩn cho AE. Vì lý do này, cộng động nghiên cứu mật mã quốc tế đã phát động một
cuộc thi trên toàn thế giới để chọn ra danh mục các thuật toán cho AE, mang tên
CAESAR.
1.3. Cuộc thi CAESAR
Cuộc thi CAESAR bắt đầu từ năm 2013 và được đồng sáng lập bởi NIST và Dan
Berstein. Mục tiêu của cuộc thi là kêu gọi cộng đồng mật mã thiết kế các chương trình AE
an toàn mới. Ứng viên chiến thắng dự kiến sẽ cải thiện AES-GCM với độ bảo mật cao
hơn (với hiệu suất tương đương) hoặc nhanh hơn (với độ bảo mật tương đương). 57 đề án
đã được đề xuất ở vòng đầu tiên của cuộc thi [17, 18].
Các kiến trúc cơ sở cho các ứng viên của CAESAR bao gồm: mật mã khối (Block
Cipher), Sponge, mật mã dòng (Stream Cipher), Hoán vị (Permutation), hàm nén
(Compression Function), và các kiến trúc chuyên dụng (Dedicated)


11
Bảng 1.1: Số lượng ứng viên tham dự CAESAR
Kiến trúc


STT

Ứng viên

Tuyên bố bảo mật

1

AES-COBRA

Độ an toàn 64-bit cho cả tính Tấn công giả mạo trên khối

Các cuộc tấn công

riêng tư và tính toàn vẹn; 128-bit mã n-bit chỉ với độ phức tạp
trước tấn công phục hồi khóa và O(n) và xác suất thành công
tấn công dự đoán thẻ xác thực
2

Calico

là 1/2.

Độ an toàn 127-bit cho tính riêng Tấn công giả mạo và phục
tư của bản rõ và 63-bit cho tính hồi khóa, yêu cầu 264 truy
toàn vẹn

vấn trực tuyến với xác suất
thành công bằng 1 để phục
hồi 128 bit khóa


tương
attack)

quan
lên


12
128 và 256 bit)

cho tính toàn vẹn tương ứng cho FASSER-128.
2 phiên bản 128 và 256 bit.

Tấn

công

phân

biệt

(distinguishing attack) lên cả
hai phiên bản 128 và 256 bit
với chỉ 16 và 64 từ khóa
(keystream words).
Tấn công khôi phục khóa
thời gian thực có thể được
thực hiện trên FASER-128
chỉ với 64 từ khóa (key

vẹn
Tuyên bố mật mã Mambo không
thể phân biệt (indistinguishable)
đối với các hệ dự đoán ngẫu
nhiên với một khóa cố định

8

PAES

Độ an toàn 128-bit cho cả tính Tấn công giả mạo phổ quát

(2 phiên bản riêng tư và tính toàn vẹn với cả lên PAES-8 trong trường


13
PAES-4

và hai phiên bản trong mô hình hợp nonce-ignoring setting
nonce-respecting, và chỉ 128-bit với chỉ 211 truy vấn

PAES-8)

toàn vẹn của PAES-8 trong
nonce-ignoring setting
9

Độ an toàn 128-bit cho cả tính Tấn công giả mạo trong

PANDA

AES-JAMBU
AES-CMCC

Mật mã khối
AEZ
AVALANCHE
CBA

Các cuộc tấn công
Tấn công giả mạo
Tấn công giả mạo phổ quát
Tấn công phân biệt
Tấn công phân biệt và tấn công
giả mạo
Tấn công giả mạo và tấn công
khôi phục khóa
Tấn công giả mạo và tấn công
khôi phục khóa
Tấn công phân biệt