Viện Công Nghệ Thông Tin Và Truyền Thông
ĐẠI HỌC BÁCH KHOA HÀ NỘI

Luận Văn Thạc Sĩ
NGHIÊN CỨU THUẬT TOÁN MÃ HÓA CÓ
XÁC THỰC NORX
Nguyen Thanh Long

Ha Noi, 2023


ii

MỤC LỤC
LỜI CẢM ƠN ................................................................................................. i
LỜI CAM ĐOAN .......................................................................................... ii
MỤC LỤC .................................................................................................... iii
CÁC KÝ HIỆU, CHỮ VIẾT TẮT ................................................................. v
DANH MỤC BẢNG BIỂU ........................................................................... vi
DANH MỤC HÌNH VẼ ............................................................................... vii
LỜI MỞ ĐẦU ................................................................................................ 1
CHƯƠNG 1: TỔNG QUAN VỀ HỆ MẬT MÃ DỊNG VÀ MÃ HĨA CĨ
XÁC THỰC ................................................................................................... 4
1.1. Hệ mật mã dòng ...................................................................................... 4
1.1.1. Định nghĩa về hệ mật mã dòng ............................................................. 4
1.1.2. Một số đặc điểm của hệ mã dòng .......................................................... 5
1.1.3. Phân loại mã dòng ................................................................................ 6
1.2. Mã hóa có xác thực .................................................................................. 7
1.2.1. Khái niệm ............................................................................................. 7
1.2.2. Cấu trúc chung của lược đồ mã hóa có xác thực ................................ 11
1.2.3. Mã hóa có xác thực với dữ liệu liên kết............................................... 17

CHƯƠNG 2: THUẬT TỐN MÃ HĨA CĨ XÁC THỰC NORX .............. 19
2.1 Thuật tốn mã hóa có xác thực NORX ................................................... 19
2.1.1. Các ký hiệu ......................................................................................... 19
2.1.2. Giới thiệu về NORX ............................................................................ 20
2.1.3. Kiến trúc tổng quan ............................................................................ 22
2.1.4. Các hàm được sử dụng trong thuật tốn NORX .................................. 23
2.2. Q trình thực hiện của thuật toán NORX ............................................. 27
2.2.1. Cấu trúc mức cao ............................................................................... 27
2.2.2 Cấu trúc mức thấp ............................................................................... 28
2.3. Sự an toàn của thuật toán NORX ........................................................... 35


iii
2.3.1. Mục tiêu an toàn ................................................................................. 35
2.3.2. Một số đặc tính an tồn trong thiết kế của NORX ............................... 37
2.3.3. Một số tấn cơng lên thuật tốn NORX................................................. 42
CHƯƠNG 3: CÀI ĐẶT CHƯƠNG TRÌNH MƠ PHỎNG THUẬT TỐN
MÃ HĨA CĨ XÁC THỰC NORX .............................................................. 47
3.1. Cài đặt thuận toán NORX ...................................................................... 47
3.1.1. Cài đặt quá trình khởi tạo ................................................................... 49
3.1.2. Cài đặt quá trình xử lý dữ liệu liên kết header .................................... 51
3.1.3. Cài đặt q trình mã hóa .................................................................... 52
3.1.4. Cài đặt quá trình xử lý dữ liệu trailer ................................................. 58
3.1.5. Cài đặt quá trình tạo thẻ xác thực ....................................................... 58
3.1.6. Cài đặt quá trình giải mã và xác thực ................................................. 59
3.2 Kết quả quá trình cài đặt thuật tốn NORX ............................................. 60
3.2.1. Kiểm tra tính đúng đắn của quá trình cài đặt...................................... 60
3.2.2. Kết quả thực hiện thuật toán NORX .................................................... 64
KẾT LUẬN .................................................................................................. 67
TÀI LIỆU THAM KHẢO ............................................................................ 68



iv

CÁC KÝ HIỆU, CHỮ VIẾT TẮT
Viết tắt
AE
AEAD

Tiếng Anh

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

Authenticated Encryption
Authenticated

Encryption Mã hóa có xác thực với dữ liệu
liên kết

with Associated Data

for Cuộc thi mã hóa có xác thực:

Competition
CAESAR

Tiếng Việt

Authenticated


Encryption: an toàn, khả năng áp dụng và

Security, Applicability, and

tính mạnh mẽ

Robustness
E&M

Encrypt and MAC

Mã hóa và mã xác thực

EtM

Encrypt then MAC

Mã hóa rồi xác thực

Indistinguishability under a

Khả năng khơng phân biệt dưới

Chosen Plaintext Attack

tấn công lựa chọn bản rõ

Indistinguishability under a

Khả năng không phân biệt dưới


Chosen Ciphertext Attack

tấn công lựa chọn bản mã

IND-CPA

IND-CCA

INT-CTXT Integrity of Ciphertext

Tính tồn vẹn của bản mã

INT-PTXT Integrity of Plaintext

Tính tồn vẹn của bản rõ

MAC
MtE
NIST

NM-CPA

SE

Message

Authentication Mã xác thực thơng báo

Code

Xác thực rồi mã hóa

MAC then Encrypt
National

Institute

of Viện tiêu chuẩn và công nghệ

Standards and Technology

quốc gia

Non-malleability under a Tính khơng mềm dẻo dưới tấn
Chosen Plaintext Attack
Symmetric
Schemes

cơng lựa chọn bản rõ

Encryption Lược đồ mã hóa đối xứng


1
LỜI MỞ ĐẦU

1. Tính cấp thiết của đề tài
Trong mơi trường mạng máy tính hiện nay, vấn đề bảo mật trong truyền
nhận thông tin là một yêu cầu rất quan trọng trong các lĩnh vực của đời sống
xã hội. Thông tin được truyền phải đảm bảo chỉ có thể được biết bởi người có

thẩm quyền và xác minh đúng người gửi, người nhận. Do vậy, ứng dụng của
các giao thức bảo mật hay các thuật toán mật mã càng trở nên quan trọng
trong việc cung cấp các tính chất bí mật, xác thực và tồn vẹn cho nội dung
thơng tin.
Để bảo mật dữ liệu trên đường truyền ta có các tiêu chuẩn, giao thức đã
được biết đến như IEEE 802.11i, IPsec ESP và IKEv2, NIST SP 800-38D,
ANSI C12.22 và ISO/IEC 19772:2009. Với các thuật tốn mã hóa thì mật mã
khóa đối xứng thường được áp dụng để cung cấp tính bí mật và tồn vẹn dữ
liệu, sau đó sử dụng mã xác thực thơng báo MAC để đem lại tính xác thực. Ví
dụ, ta có thể dùng mã khối AES ở chế độ CBC để mã thơng tin, sau đó dùng
thuật toán AES-CMAC (hoặc HMAC) để xác thực. Phương pháp này tác
động tới tính an tồn vì q trình mã hóa và xác thực có thể được phân tích
gần như riêng biệt. Chính vì thế, hướng đi mới là xây dựng các lược đồ mã
hóa có xác thực (AE) và các lược đồ mã hóa có xác thực với dữ liệu liên kết
(AEAD). Dữ liệu liên kết này là loại dữ liệu đi kèm nội dung thông báo sẽ
không cần phải mã hóa nhưng sẽ được xác thực trong khi truyền.
Để đáp ứng yêu cầu trên, Viện tiêu chuẩn và công nghệ quốc gia Hoa
Kỳ NIST (National Institute of Standards and Technology) đã tổ chức cuộc
thi về mã hóa có xác thực CAESAR (Competition for Authenticated
Encryption: Security, Applicability, and Robustness) nhằm chọn ra thuật tốn
mã hóa có xác thực tốt nhất đảm bảo các tính năng an tồn, khả năng áp dụng
và tính mạnh mẽ, đồng thời có lợi thế hơn AES-GCM. Thuật tốn mã hóa có
xác thực NORX là một trong 57 ứng viên của cuộc thi này và là một trong 15
thuật tốn được lựa chọn vào vịng 3 của cuộc thi.


2

.
2. Tổng quan về tình hình nghiên cứu

Ngày 12/1/2013 cuộc thi CAESAR được khai mạc tại Luxembourg.
Cuộc thi đã gây được sự chú ý của cộng đồng khoa học mật mã thế giới. Đã
có 57 thuật tốn của các nhà mật mã học được gửi đến tham gia cuộc thi.
Thuật tốn NORX của của nhóm tác giả Jean-Philippe Aumasson, Philipp
Jovanovic, Samuel Neves là một ứng viên tại vòng ba của cuộc thi CAESAR.
Thuật toán được giới thiệu lần đầu tiên vào 03/2014. Trong thời gian qua, các
nhà mật mã trên thế giới đã có nhiều nghiên cứu về thuật tốn, sự an tồn và các
tấn cơng lên NORX.
Trong q trình thực hiện đồ án tốt nghiệp, em đã tìm hiểu, xem xét một
số tài liệu đã được công bố trước đó để phục vụ q trình hồn thiện đồ án
của mình. Tài liệu chính đã nghiên cứu bao gồm:
- “NORX v3.0, 2016”, của các tác giả Jean-Philippe Aumasson, Philipp
Jovanovic, Samuel Neves. Tài liệu này mơ tả về thuật tốn NORX gồm các
hàm, các q trình hoạt động và phân tích sự an toàn của NORX.
- “Distinguishing Attack on NORX Permutation, 2018” của tác giả Tao
Huang và Hongjun Wu. Tài liệu này tóm tắt kết quả một số tấn cơng lên phiên
bản cũ của NORX và trình bày một tấn cơng phân biệt trên hoán vị nhân của
NORXv3.0.
- “Authenticated encryption: Relations among notions and analysis of
the generic composition paradigm, 2007” của tác giả Bellare và
Namprempre. Tài liệu này mô tả cấu trúc chung của mã hóa có xác thực và
đánh giá sự an tồn của các phương thức trong mã hóa có xác thực.
Ngồi ra em cịn tham khảo một số tài liệu khác có liên quan.
3. Mục tiêu nghiên cứu
- Tìm hiểu thuật tốn mã hóa có xác thực NORX.
- Cài đặt chương trình mơ phỏng thuật tốn mã hóa có xác thực NORX.
4. Đối tượng và phạm vi nghiên cứu


3


- Đối tượng nghiên cứu: thuật tốn mã hóa có xác thực NORX.
- Phạm vi nghiên cứu: đề tài nêu khái quát về hệ mã dòng, các vấn đề
chung về mã hóa có xác thực; thuật tốn mã hóa có xác thực NORX; cài đặt
chương trình mã hóa có xác thực NORX.
5. Phương pháp nghiên cứu
Đề tài sử dụng các phương pháp nghiên cứu như phương pháp tổng
hợp, phương pháp so sánh, phương pháp phân tích và kế thừa một số kết quả
nghiên cứu đã có, đồng thời thu thập thơng tin, tài liệu để phục vụ cho q
trình nghiên cứu.
6. Những đóng góp của đồ án
- Về lý thuyết: Đồ án trình bày các vấn đề về thuật tốn mã hóa có xác
thực như khái niệm, cấu trúc chung của mã hóa có xác thực. Trình bày về các
q trình hoạt động, sự an tồn của thuật tốn NORX.
- Về tính ứng dụng: Đồ án trình bày q trình cài đặt chương trình thực
thi thuật tốn mã hóa có xác thực NORX.
7. Kết cấu của đồ án tốt nghiệp
Nội dung đồ án tốt nghiệp gồm 3 chương:
Chương 1: Tổng quan về hệ mật mã dịng và mã hóa có xác thực.
Chương này trình bày những kiến thức tổng quan về hệ mã dịng và mã
hóa có xác thực bao gồm: tổng quan về hệ mã dòng, khái niệm về mã hóa có
xác thực, cấu trúc chung của mã hóa có xác thực và mã hóa có xác thực với
dữ liệu liên kết.
Chương 2: Thuật tốn mã hóa có xác thực NORX.
Chương này trình bày về cấu trúc, tham số các tính năng của thuật tốn
mã hóa có xác thực NORX, các hàm sử dụng trong thuật tốn NORX, q
trình mã hóa, giải mã của thuật tốn. Dựa trên cấu trúc đó để phân tích sự an
tồn của thuật tốn. Bên cạnh đó giới thiệu một số tấn cơng lên thuật tốn
NORX.
Chương 3: Cài đặt chương trình mơ phỏng thuật tốn mã hóa có

xác thực NORX.
Trình bày q trình cài đặt chương trình thực thi thuật tốn mã hóa có
xác thực NORX. Kiểm tra tính đúng đắn của q trình cài đặt thuật toán.


4

CHƯƠNG 1: TỔNG QUAN VỀ HỆ MẬT MÃ DÒNG VÀ MÃ HĨA CĨ
XÁC THỰC
Chương này trình bày những kiến thức tổng quan về hệ mật mã dịng và
mã hóa có xác thực bao gồm: tổng quan về hệ mã dòng, khái niệm về mã hóa
có xác thực, các thành phần và cấu trúc chung của mã hóa có xác thực và mã
hóa có xác thực với dữ liệu liên kết.
1.1. Hệ mật mã dòng
1.1.1. Định nghĩa về hệ mật mã dịng
Hệ mật mã dịng là hệ mã mà trong đó mỗi ký tự của bản rõ được mã
hóa tách biệt [1]. Trong hệ mã dịng, một dịng khóa z = z1z2 ... được sinh ra
và được dùng để mã hóa một xâu bản rõ

R = r1r2 ... theo quy tắc sau:

M = m1m2... = Ez (r1)Ez (r2 )...
1

2

Hình 1. 1. Sơ đồ mã hóa của hệ mã dịng
Một hệ mã dòng đồng bộ được định nghĩa như sau:

Định nghĩa: Một hệ mã dòng đồng bộ là một bộ (R,M,K, L,E,D)

thỏa mãn các điều kiện sau:
1. R là một tập hữu hạn các bản rõ có thể.
2. M là tập hữu hạn các bản mã có thể.
3. K là tập hữu hạn các khóa (mầm khóa) có thể.


5

4. L là tập hữu hạn các ký tự của dịng khóa.
5. g là bộ tạo dịng khóa. Với đầu vào là khóa K, g sẽ tạo một dịng khóa

z = z1z2 ..., với

zi  L,i 1.

6. Với mỗi dòng khóa

z = z1z2 ... có một quy tắc mã

Ez E và một quy

tắc giải mã Dz D tương ứng. Ez :R → M và Dz : M →R là các
hàm thỏa mãn Dz (Ez (R)) = R với mọi bản rõ R R .
1.1.2. Một số đặc điểm của hệ mã dòng
Trong hệ mã dòng, phép lập mã và phép dịch mã là các phép biến đổi
đơn giản và tuyến tính theo dịng khóa được sử dụng [1]. Hệ mã dịng có một
số đặc điểm sau:
- Phép lập mã và phép dịch mã được thực hiện trên cùng một dòng khóa.
- Độ dài bản rõ và độ dài bản mã là như nhau và bằng độ dài dịng khóa.
- Biết bản rõ và bản mã dễ dàng tính ra dịng khóa tương ứng.

- Độ bảo mật của hệ mã dịng phụ thuộc vào độ bảo mật của khóa.
- Nếu là khóa ngẫu nhiên và dùng một lần thì hệ mã dịng có độ bảo mật
cao nhất.
- Một hệ mã dịng được gọi là tuần hoàn với chu kỳ d nếu

zi+d = zi với

mọi số nguyên i  1.
- Trong hệ mã dòng, bảng chữ cái rõ, bảng chữ cái mã, và bảng chữ cái
khóa thường được mơ tả trong bộ chữ nhị phân {0,1}, tức là
R = M = L = Z2 . Trong trường hợp này, phép lập mã và dịch mã là phép

cộng modulo 2:
Ez (r) = (r + z)mod 2 và Dz (m) = (m + z) mod 2 .
zi

zi
ri



mi

Kênh khơng
an tồn

mi




Hình 1. 2. Sơ đồ mã hóa và giải mã với hệ mã dịng.

ri


6

1.1.3. Phân loại mã dòng
-Hệ mã dòng đồng bộ: là hệ mã dịng mà dịng khóa được sinh ra
khơng phụ thuộc vào xâu bản rõ. Tức là dịng khóa được sinh ra từ hàm của
mầm khóa S.
Hệ mã dịng này có ưu điểm là khơng có hiệu ứng lan truyền lỗi, mỗi bit
lỗi khi truyền sẽ dẫn đến sai lệch chỉ một bit bản mã khi dịch. Hơn nữa, hệ mã
này cịn bảo vệ khỏi việc chèn, xóa hay dùng lại các ký tự của bản mã, các thao
tác này sẽ làm mất đồng bộ và ngay lập tức sẽ bị phát hiện ở bên nhận [1].
- Hệ mã dòng tự đồng bộ: là hệ mã dòng mà mỗi phần tử của dịng
khóa zi phụ thuộc vào một phần tử rõ hoặc các phần tử rõ trước đó ( r1r2..., ri−1
và/hoặc m1m2 ..., mi−1 ) và khóa K.
Hệ mã dịng này có nhược điểm là lan truyền các lỗi. Hơn nữa, rất khó
để phát hiện ra việc chèn, xóa hay dùng lại các ký tự của bản mã, nếu phát
hiện được thì cũng khơng dịch đúng bản mã.
- Hệ mã dịng với khóa đệm dùng một lần (one-time-pad): là hệ mã
dịng với khóa được chọn ngẫu nhiên và khơng dùng lại. Nguyên lý cơ bản
của hệ mật khóa ngẫu nhiên dùng một lần là đảm bảo tính độc lập thống kê
giữa bản rõ và bản mã bằng cách sử dụng dãy khóa ngẫu nhiên đúng. Một hệ
mật được gọi là có độ mật hồn thiện (hay cịn gọi là có độ an tồn vơ điều
kiện) nếu thơng tin tương hỗ giữa bản rõ và bản mã tương ứng là bằng khơng,
độc lập với độ dài của bản rõ đó. Khi nhận được bản mã, thám mã không thể
suy diễn bất kỳ thơng tin gì về bản rõ được mã hóa, mà vẫn chỉ có phân bố
xác suất tiên nghiệm trên tập các bản rõ có thể. Hệ mật khóa ngẫu nhiên dùng

một lần có độ mật hồn thiện. Tuy nhiên, dãy khóa ngẫu nhiên sử dụng trong
hệ mã một lần cần phải tạo ra trước và phân phối trước tới cả người gửi và
người nhận. Đây là vẫn đề rất khó trong thực tế sử dụng, đặc biệt là trong các
hệ thống tự động hóa.
Trong thực tế khơng thể có được dãy ngẫu nhiên lý tưởng, điều đó dẫn
đến nghiên cứu các phương pháp tạo dãy gần ngẫu nhiên, giả ngẫu nhiên. Đây


7

là cách tiếp cận tuy có làm giảm đi độ bảo mật của hệ mã dòng nhưng lại làm
cho quá trình sinh khóa và phân phối khóa dễ dàng với khối lượng lớn tùy ý.
Việc sinh khóa giả ngẫu nhiên địi hỏi phải thỏa mãn về tốc độ sinh
khóa, và các tiêu chí về độ bảo mật. Khóa giả ngẫu nhiên được sinh ra từ một
đoạn mầm khóa và một thuật tốn sinh khóa phải thỏa mãn tính chất sau:
- Dù cho mã thám biết mọi điều trừ mầm khóa thì cũng khơng đồng bộ
được dịng khóa dịch mã để tìm ra bản rõ.
- Biết những đoạn hoặc phần khóa rời rạc khơng đủ khả năng sinh lại
được cả dịng khóa trừ khi biết mầm khóa.
Việc sử dụng khóa giả ngẫu nhiên sẽ rất thuận lợi đối với những máy
mã hoặc những hệ thống mật mã tự động cần khối lượng khóa lớn với tốc độ
sinh khóa nhanh. Tuy nhiên, do sử dụng các quy luật toán học để sinh khóa
nên độ bảo mật sẽ bị ảnh hưởng từ quan điểm đại số và độ phức tạp tính tốn.
Mặt khác, dãy khóa giả ngẫu nhiên phải có đủ các tính chất ngẫu nhiên của
dãy ngẫu nhiên. Đây là những vấn đề lớn đang được nghiên cứu nhằm làm
cho hệ mã dịng có độ bảo mật và năng suất thực hiện cao nhất để đáp ứng
yêu cầu thực tế ngày càng cao hiện nay.
1.2. Mã hóa có xác thực
1.2.1. Khái niệm
Mã hóa có xác thực là một dạng mã hóa đối xứng có mục tiêu bảo vệ

đồng thời tính bí mật, xác thực và tồn vẹn cho dữ liệu [3].
Ví dụ: Một bác sĩ muốn gửi thơng tin tình trạng bệnh cho bệnh nhân là
Alice. Trong trường hợp này họ muốn cả sự riêng tư và xác thực.
- Cả hai đều muốn thơng tin tình trạng bệnh của Alice được giữ bí mật
để đảm bảo riêng tư.
- Alice muốn xác thực thơng tin nhận được là do chính bác sĩ gửi cho
mình và đảm bảo thơng tin khơng bị sửa đổi.
Vì vậy trong trường hợp này cần sử dụng mã hóa có xác thực.


8

Mã hóa có xác thực được thiết kế xuất phát từ yêu cầu kết hợp giữa chế
độ bí mật và chế độ xác thực. Khái niệm này được tập trung nghiên cứu vào
khoảng những năm 2000. Đặc biệt, sau khi Charanjit Jutla đưa ra chế độ mã
hóa có xác thực là IAPM [8]. Điều này đã gây được sự quan tâm của cộng
đồng khoa học mật mã thế giới. Đã có nhiều nghiên cứu dẫn đến sự ra đời
một số chế độ mã hố có xác thực khác nhau là: OCB, Key Wrap, CCM,
EAX, và GCM. Các chế độ này đã được chuẩn hóa trong ISO/IEC
19772:2009. Ngồi ra, mã hóa có xác thực đã được đưa vào trong các giao
thức ứng dụng thực tế như SSH, SSL, IPSec.
Ngoài bảo vệ tính tồn vẹn và bí mật thơng tin, mã hóa có xác thực có
thể được dùng để chống lại các tấn công lựa chọn bản mã. Trong kiểu tấn
công này, mã thám sẽ cố gắng để đạt được một số lợi thế so với hệ mật (ví dụ
như thơng tin về khóa bí mật) bằng cách chọn các bản mã, gửi nó tới người
nhận và phân tích kết quả giải mã. Các thuật tốn mã hóa có xác thực có thể
nhận ra các bản mã không phải từ đúng người gửi và từ chối giải các bản mã
đó. Điều này sẽ ngăn chặn các tấn công yêu cầu giải mã bất kỳ bản mã nào.
Trong lược đồ mã hóa có xác thực, người gửi mã hóa thơng báo với khóa
để cho ra bản mã và một thẻ xác thực. Quá trình giải mã được thực hiện bởi

người nhận có cùng khóa với người gửi dùng để giải mã bản mã cho ra thông
báo từ người gửi hoặc một cảnh báo chỉ ra rằng bản mã là không hợp lệ.
Một lược đồ mã hóa có xác thực có thể được tổng quát cấu trúc bằng
việc kết hợp một lược đồ mã hóa đối xứng (Symmetric Encryption scheme –
SE) với một mã xác thực thông báo (Message Authentication Code - MAC).
Lược đồ mã hóa đối xứng là bộ SE = (M,C,K
kiện sau:

thỏa mãn các điều

,E,D)

1. M là không gian thông báo bao gồm một tập hữu hạn các thơng báo
M có thể.
2. C là không gian mã bao gồm một tập hữu hạn các bản mã C có thể.
3. K là khơng gian khóa bao gồm một tập hữu hạn các khóa K có thể.


9

4. Với mỗi khóa K K có một quy tắc mã EK  E và một quy tắc giải
mã DK D . Trong đó, mỗi

EK : M →

và DK :C → M là các hàm mã

C
hóa đảm bảo DK (EK (M )) = M với mọi thông báo M M .
Trong các điều kiện trên thì điều kiện 4 là quan trọng nhất, điều kiện

này chỉ ra rằng, khi mã hóa một thơng báo bằng hàm lập mã EK , thì ta có thể
giải mã nó bằng hàm giải mã DK . Đây là yêu cầu thông thường và bắt buộc
của lược đồ mã hóa đối xứng.
Theo mơ hình của lược đồ mã hóa đối xứng (Hình 1.3), người gửi A tạo
một thông báo M trong không gian thông báo M . Để mã hóa M, phải chọn
ngẫu nhiên một khóa K K . Nếu khóa K đã được tạo bởi người gửi thì sau
đó khóa này phải được phân phối tới người nhận qua kênh an tồn. Nếu khóa
K được tạo bởi bên thứ ba tin cậy thì bên thứ ba này cũng phải phân phối tới
cả người gửi và người nhận qua kênh an tồn.
M’

Mã thám

Người gửi
A

M

Mã hóa

EK (M ) = C

C

Kênh
truyền tin

K’

C


Giải mã

DK (C) = M

M

Người nhận
B

Kênh an tồn
K
Nguồn
khóa K

Hình 1. 3. Mơ hình lược đồ mã hóa đối xứng.
Với đầu vào là thơng báo M và khóa K, hàm lập mã EK
C tương ứng:

tạo ra bản mã

C = EK (M ). Bản mã C được gửi tới cho người nhận B qua

kênh truyền tin (đây là kênh khơng an tồn).
Sau khi nhận được bản mã C từ kênh truyền tin, người nhận sẽ giải mã
bản mã C để khôi phục lại thông báo M qua hàm giải mã DK với khóa giải mã
K là: M = DK (C).


10


Khi bản mã C được gửi cho người nhận B qua kênh truyền tin, do đây
là kênh khơng an tồn nên mã thám có thể chặn bắt được mà khơng có hạn
chế. Tuy nhiên, mã thám khơng biết khóa K nào trong khơng gian khóa đã
được sử dụng cũng như thông báo M tương ứng với bản mã C đã bắt được. Vì
vậy, mã thám sẽ cố gắng để tìm ra thơng báo M hoặc khóa K hoặc cả thơng
báo và khóa. Với giả định là mã thám có hiểu biết đầy đủ về thuật toán mã và
giải mã. Nếu mã thám chỉ quan tâm đến một thông báo cụ thể thì mã thám sẽ
chú trọng để khám phá thơng báo M bằng cách tạo ra một giá trị ước lượng
của thông báo M’. Tuy nhiên, nếu mã thám quan tâm tới khả năng giải mã
được các bản mã tiếp theo mà cũng được mã bằng khóa K đã sử dụng, khi đó
mã thám sẽ cố gắng để khám phá khóa K bằng cách tạo ra một giá trị ước
lượng của khóa K’.
Trong lược đồ mã hóa đối xứng, khóa mã và khóa giải mã là giống nhau
hoặc từ khóa này có thể tính tốn để tìm ra khóa kia và ngược lại. Vì vậy,
thơng thường chỉ phải phân phối khóa mã cho người gửi và người nhận. Hơn
nữa, khóa phải được giữ bí mật và chỉ được biết bởi người gửi và người nhận.
Mã xác thực thông báo là một cơ chế được sử dụng để xác thực tính tồn
vẹn của thơng báo. Mã xác thực thơng báo đảm bảo rằng dữ liệu nhận được là
chính xác như khi nó được gửi (tức là khơng bị sửa đổi, chèn, xóa hay phát lại).
Trong nhiều trường hợp, định danh của người gửi có thể được bảo vệ.
Lược đồ mã xác thực thông báo (MAC – Message Authentication
Codes) là bộ MA = (M,B,K ,T ,tf

thỏa mãn các điều kiện sau:

)
1. M là không gian thông báo bao gồm một tập hữu hạn các thơng báo
M có thể.
2.


B là khơng gian thẻ bao gồm tập hữu hạn các thẻ  có thể.

3. K là khơng gian khóa bao gồm một tập hữu hạn các khóa K có thể.
4. Với mỗi khóa K K có một quy tắc gắn thẻ T T và một quy tắc
xác thực thẻ V tf . Trong đó, mỗi

TK : M → B và VK : M,B →tf

các hàm đảm bảo VK (K,M ,TK (M )) = v =1 với mọi thông báo M M .

là


11

Để một mã MAC được đánh giá là an toàn và hiệu quả, cần có tính chất sau:
- Tính chất dễ tính tốn: với quy tắc gắn thẻ TK , một khóa bí mật K và
đầu vào M bất kì, TK (M ) là dễ tính tốn.
- Tính chất nén: với đầu vào M có độ dài tùy ý hữu hạn, qua quy tắc gắn
thẻ TK tạo thành một thẻ  có độ dài cố định.
- Tính chất kháng tính toán: cho trước một hoặc nhiều cặp (Mi −  i ) ,
khơng thể tính tốn để tìm ra một cặp (M − ) cho đầu vào mới M  Mi .

Hiện nay, việc xây dựng các thuật toán mã hóa có xác thực có sự an
tồn cao, khả năng triển khai dễ dàng trên nền tảng phần mềm cũng như phần
cứng đang là vấn đề được quan tâm của cộng đồng khoa học mật mã trên thế
giới. Xuất phát từ yêu cầu trên, Viện Tiêu chuẩn và Công nghệ NIST
(National Institute of Standards and Technology) đã tổ chức cuộc thi
CAESAR – cuộc thi chọn ra chuẩn thuật toán mã hóa có xác thực (tương tự

như cuộc thi chọn ra chuẩn mã hóa nâng cao AES). Cuộc thi CAESAR đã thu
hút sự tham gia của rất nhiều nhà mật mã trên thế giới. Đã có 57 ứng viên
tham gia vào cuộc thi này. Thuật tốn mã hóa có xác thực NORX trình bày
sau đây là một ứng viên tại vịng 3 của cuộc thi.
1.2.2. Cấu trúc chung của lược đồ mã hóa có xác thực
1.2.2.1. Mã hóa và xác thực (E&M)
Thơng báo M

Mã hóa
E

Bản mã C

Khóa K

MAC

Thẻ xác thực

Hình 1. 4. Lược đồ mã hóa và xác thực.


12

Lược đồ mã hóa có xác thực

AE = (K
,E,D)

được xây dựng bằng


cách kết hợp lược đồ mã hóa đối xứng SE với lược đồ mã xác thực thông

báo MA theo phương pháp mã hóa và xác thực (Hình 1.4) như sau:
*. Thuật tốn tạo khóa K
$
- Ke ⎯
⎯Ke ;
$
- Km ⎯
⎯Km ;

- Return Ke || Km .
*. Thuật toán mã hóa E (Ke || K m ,M )
- C '  E (K e ,M );
-   T (K m ,M );
- C C '||  ;
- Return C.
*. Thuật tốn giải mã D (Ke || Km,C)
- Phân tích C thành C '||  .
- M  D (Ke,C ');
-v

 tf (Km ,M , );

- Nếu v=1 thì return M, ngược lại return Fail.
Thẻ xác thực

 được tạo ra từ thơng báo M. Thơng báo được mã hóa để


tạo ra bản mã C. Thẻ xác thực  và bản mã C được gửi cùng nhau tới nơi nhận.
Tại nơi nhận, người nhận sẽ giải mã bản mã để tìm ra thơng báo M. Sau đó xác

minh thẻ  với thông báo M vừa giải mã. Phương pháp này được sử dụng trong
giao thức SSH.


13

1.2.2.2. Xác thực rồi mã hóa (MtE)
Thơng báo M

MAC

Thơng báo M

Khóa K

Thẻ xác thực

Mã hóa
E
Bản mã C

Hình 1. 5. Lược đồ xác thực rồi mã hóa.
Lược đồ mã hóa có xác thực

AE = (K ,E,D được xây dựng bằng
)


cách kết hợp lược đồ mã hóa đối xứng SE với lược đồ mã xác thực thông

báo MA bằng phương pháp xác thực rồi mã hóa (Hình 1.5) như sau:
*. Thuật tốn tạo khóa K
$
- Ke ⎯
⎯Ke ;

$
- Km ⎯
⎯Km ;

- Return Ke || Km .
*. Thuật tốn mã hóa E (Ke || K m ,M )
-   T (K m ,M );

- C  E (Ke,M || );
- Return C.
*. Thuật toán giải mã D (Ke || Km,C)
- M '  D (Ke,C);
- Phân tích M ' thành M || .
-v

 tf (Km ,M , );


14
- Nếu v=1 thì trả về M, ngược lại trả về Fail.



15

Thẻ xác thực

 được tạo ra dựa trên thông báo ban đầu, sau đó thực

hiện mã hóa cả thơng báo và thẻ xác thực này bằng một hàm mã hóa để tạo ra
bản mã. Bản mã (chứa cả thẻ xác thực

 đã được mã hóa) được gửi tới nơi

nhận. Tại nơi nhận, quá trình giải mã và xác thực được thực hiện bằng cách
giải mã để có được thơng báo và thẻ xác thực, sau đó xác minh thẻ. Phương
pháp này được sử dụng trong giao thức bảo mật mạng SSL.
1.2.2.3. Mã hóa rồi xác thực (EtM)

Thơng báo M

Mã hóa
E

Khóa K

MAC

Bản mã C

Thẻ xác thực

Hình 1. 6. Lược đồ mã hóa rồi xác thực.

Lược đồ mã hóa có xác thực AE

= (K ,E,D)

được xây dựng bằng

cách kết hợp lược đồ mã hóa đối xứng SE với lược đồ mã xác thực thơng

báo MA bằng phương pháp mã hóa rồi xác thực (Hình 1.6) như sau:
*. Thuật tốn tạo khóa K
$
- Ke ⎯
⎯Ke ;


16

$
- Km ⎯
⎯Km ;

- Return Ke || Km .
*. Thuật tốn mã hóa E (Ke || K m ,M )
- C '  E (K e ,M );
-  '  T (K m ,C ');
- C C '||  ';
- Return C.
*. Thuật toán giải mã D (Ke || Km,C)
- Phân tích C thành C '||  ' .
-v


 tf (Km ,C ', ');

- Nếu v=1 thì tiếp tục giải mã, ngược lại return Fail.
- Return M  D (K e ,C') .
Thơng báo M sẽ được mã hóa cho ra bản mã C’. Tiếp theo, thẻ xác thực

 được tạo ra từ bản mã C’. Bản mã và thẻ xác thực được gửi cùng nhau đến
nơi nhận để đảm bảo tính bí mật và xác thực. Q trình giải mã và xác thực
được thực hiện bằng cách: đầu tiên xác minh thẻ, nếu thẻ

 là chính xác sẽ

tiếp tục giải mã bản mã C’ để được thông báo là M, ngược lại dừng lại và
thông báo thẻ không hợp lệ. Đây là phương pháp có thể đạt được sự an tồn
cao nhất trong mã hóa có xác thực. Việc xác minh thẻ có thể cho ta biết được
tính tồn vẹn và xác thực của bản mã mà khơng cần tới giải mã. Phương pháp
này được sử dụng trong giao thức bảo mật IPsec.
1.2.2.4. So sánh các phương pháp mã hóa có xác thực
*. Phương pháp mã hóa và xác thực
- Đảm bảo tính tồn vẹn của thơng báo.
- Khơng đảm bảo tính tồn vẹn trên các bản mã, vì thẻ xác thực  được
tạo ra từ thơng báo.


17

- Nếu hệ mật có tính mềm dẻo (Melleable), nội dung của các bản mã có
thể thay đổi, nhưng khi giải mã, mã thám phải tìm ra thơng báo là hợp lệ.
- Trên lý thuyết, việc tiết lộ thông tin về thơng báo trong thẻ xác thực 

là có thể, nhưng điều này chỉ xảy ra với điều kiện là các thông điệp rõ được
lặp đi lặp lại và các dữ liệu được xác thực không bao gồm một bộ đếm.
*. Phương pháp xác thực rồi mã hóa
- Đảm bảo tính tồn vẹn của thơng báo.
- Khơng đảm bảo tính tồn vẹn trên các bản mã, vì khơng thể biết được
liệu bản mã là giả mạo hay không cho đến khi thực hiện giải mã.
- Nếu hệ mật có tính mềm dẻo, nó có thể tạo ra thơng báo hợp lệ với
một thẻ xác thực  hợp lệ.
- Thẻ xác thực  không thể cung cấp bất kỳ thông tin nào về thơng
báo.
*. Phương pháp mã hóa rồi xác thực
- Đảm bảo tính tồn vẹn của thơng báo.
- Đảm bảo tính tồn vẹn của bản mã. Với thẻ xác thực  , có thể suy ra
được liệu một bản mã là xác thực hoặc đã bị giả mạo.
- Nếu hệ mật có tính mềm dẻo, khơng cần phải q quan tâm vì thẻ xác
thực  sẽ lọc ra các bản mã không hợp lệ này.
- Thẻ xác thực  không cung cấp bất kỳ thơng tin về thơng báo.
Tóm lại, mã hóa rồi xác thực là phương pháp lý tưởng nhất. Bất kỳ sự
sửa đổi bản mã mà có một thẻ xác thực không hợp lệ đều được lọc ra trước
khi giải mã. Thẻ xác thực không thể được sử dụng để suy ra bất cứ điều gì về
thơng báo. Cả 2 phương pháp mã hóa và xác thực và xác thực rồi mã hóa
cung cấp mức độ an tồn khác nhau, nhưng khơng phải là phương pháp hồn
chỉnh như mã hóa rồi xác thực.


18

Theo các chứng minh về sự an tồn được trình bày trong tài liệu [3], có
thể đưa ra sự an tồn của các phương pháp mã hóa có xác thực như sau:
Bảng 1. 1. Sự an toàn của các phương pháp mã hóa có xác thực

Tính bí mật
Phương pháp

Mã hóa và xác thực

Tính tồn vẹn

IND-

IND-

NM-

INT-

INT-

CPA

CCA

CPA

PTXT

CTXT

Khơng

Khơng


Khơng

an tồn

an tồn

an tồn

Khơng

Khơng

an tồn

an tồn

An tồn

An tồn

Xác thực rồi mã hóa

An tồn

Mã hóa rồi xác thực

An tồn

An tồn

An tồn
An tồn

Khơng
an tồn
Khơng
an tồn
An tồn

Trong đó:
- IND-CPA: Khả năng không phân biệt dưới tấn công lựa chọn bản rõ.
- IND-CCA: Khả năng không phân biệt dưới tấn cơng lựa chọn bản mã.
- NM-CPA: Tính khơng mềm dẻo dưới tấn cơng lựa chọn bản rõ.
- INT-PTXT: Tính tồn vẹn của bản rõ.
- INT-CTXT: Tính tồn vẹn của bản mã.
1.2.3. Mã hóa có xác thực với dữ liệu liên kết
Mã hóa có xác thực với dữ liệu liên kết (AEAD - Authentiacted
Encryption with Associated Data) [9, 11] là phần mở rộng của mã hóa có xác
thực với phần dữ liệu liên kết khơng được mã hóa mà chỉ có chức năng bảo tồn
tính tồn vẹn và xác thực của thơng báo nhằm ngăn chặn các gói tin giả mạo.
Dữ liệu liên kết thông thường chứa các thông tin như:
- Định danh phiên liên lạc hoặc liên kết bảo mật.
- Địa chỉ nguồn và địa chỉ đích của thơng báo.
- Số thứ tự và các thông tin khác được gắn thêm.


19

Thơng tin này có thể được truyền đi dưới dạng rõ, nhưng nội dung của
nó vẫn phải được đảm bảo tồn vẹn.

Người gửi A
Dữ liệu liên kết

Truyền
rõ

Giá trị
Nonce

Thơng báo

Khóa bí mật

Lược đồ mã hóa
AEAD

Bản mã

Thẻ xác thực

Lược đồ giải mã
AEAD

Thơng báo

Hoặc

Giải mã thất bại

Người nhận B


Hình 1. 7. Mã hóa có xác thực với dữ liệu liên kết.
Dữ liệu đầu vào của lược đồ AEAD bao gồm thông báo là phần thông
tin cần gửi, phần thông tin này yêu cầu phải được bảo đảm bí mật và xác thực;
phần liên kết dữ liệu – Associated Data cần được xác thực; giá trị Nonce ngẫu
nhiên, nó thường là duy nhất đối với mỗi thơng báo, nó có thể tùy biến gửi
hoặc không khi truyền bản mã từ nơi gửi đến nơi nhận; phần cuối cùng là
khóa bí mật. Khóa bí mật khơng truyền cùng với bản mã, nó được phân phối
trước tới các người sử dụng.
Thơng báo M được mã hóa qua lược đồ AEAD tạo ra bản mã xác thực
gồm một bản mã C và một thẻ xác thực  . Phần dữ liệu liên kết AD được gửi
cùng với bản mã xác thực trên được truyền dưới dạng rõ. Ba phần (AD || C || 
) được truyền tới người nhận B. B sẽ tiến hành giải mã thông báo, xác thực với


20

khóa bí mật được phân phối trước. Kết quả thu được là M’. Nếu q trình xác
thực được thơng qua thì M’ được chấp nhận là gửi từ chính người gửi A, ngược
lại nếu xác thực thất bại thì xác định thông báo không phải được gửi từ A.
CHƯƠNG 2: THUẬT TỐN MÃ HĨA CĨ XÁC THỰC NORX
Chương này trình bày về kiến trúc, các tham số, các hàm hoán vị; q
trình mã hóa, giải mã của thuật tốn. Tiếp theo, nghiên cứu các đặc tính an
tồn dựa trên thiết kế của thuật tốn. Bên cạnh đó giới thiệu một số kết quả
tấn cơng lên thuật tốn NORX.
2.1 Thuật tốn mã hóa có xác thực NORX
2.1.1. Các ký hiệu
Bảng 2. 1. Ký hiệu được sử dụng trong tài liệu.
Kí hiệu
𝜺


Ý nghĩa
Chuỗi bit trống có độ dài 0.

0n

Chuỗi bit 0 có độ dài 𝑛.

|𝒙|

Chiều dài của chuỗi bit 𝑥 trong các bit.

|𝒙|𝒏

Chiều dài của chuỗi bit 𝑥 trong khối 𝑛 bit.

𝒙‖𝒚

Ghép nối chuỗi bit x và y

¬,∧,∨,⊕
𝒙 ≪ 𝒏; 𝒙 ≫ 𝒏
𝒙 ⋘ 𝒏; 𝒙 ⋙ 𝒏
⟵

Phủ định theo bit, AND, OR và XOR.
Dịch trái/ phải chuỗi bit x bởi n bit.
Quay vòng trái/ phải chuỗi bit x bởi n bit.
Gán biến số.


𝒍𝒆𝒇𝒕𝒍 (𝒏)

Cắt ngắn chuỗi bit x với l bit ngoài cùng bên trái.

𝒓𝒊𝒈𝒉𝒕𝒓(𝒏)

Cắt ngắn chuỗi bit x với r bit ngoài cùng bên phải.

𝒉𝒘(𝒙)

Trọng lượng Hamming chuỗi bit 𝑥.


21

2.1.2. Giới thiệu về NORX
Cuộc thi về mã hóa có xác thực Competition for Authenticated
Encryption: Security, Applicability, and Robustness (CAESAR) được tổ chức
nhằm chọn ra lược đồ mã hóa có xác thực với dữ liệu liên kết (AEAD) tốt
nhất. Mục tiêu là đáp ứng tính an tồn, khả năng áp dụng và tính mạnh mẽ;
có lợi thế hơn AES-GCM và đáp ứng yêu cầu phổ biến rộng rãi.
NORX, một ứng cử viên trong cuộc thi CAESAR được giới thiệu bởi
Jean-Philippe Aumasson, Philipp Jovanovic, Samuel Neves là một chương
trình mã hóa có xác thực với dữ liệu liên kết. NORX được xây dựng dựa trên
kiến trúc monkeyDuplex với mức độ mã hóa song song và kích thước thẻ có
thể được điều chỉnh tùy ý [2].
Các phiên bản của thuật toán NORX: từ khi được công bố đến nay, các
tác giả đã liên tục điều chỉnh các tham số nhằm tăng sự an tồn cho thuật tốn.
Các phiên bản gồm NORXv1.0, NORXv1.1, NORXv2.0, NORXv3.0. Nội dung
của nghiên cứu này chủ yếu tìm hiểu NORXv3.0, là phiên bản mới nhất, có

nhiều thay đổi lớn và độ bảo mật cao. Những thay đổi từ v2.0 đến v3.0:
- Kích thước nonce tăng từ 2w lên 4w (w=32 hoặc 64 bit).
- Giao diện gói dữ liệu thích hợp để xử lý nonce kích thước lớn hơn.
- Khóa được XOR vào các bit capacity sau q trình khởi tạo và sau
mỗi lần trạng thái được chuyển đổi bởi Fl ở giai đoạn cuối.
- Thẻ được tách ra từ các bit capacity thay vì các bit rate của trạng thái.
Những thay đổi từ v1.1 đến v2.0: đổi tên các biến số như trong Bảng 2.2.
Bảng 2. 2. Sự thay đổi của các biến số.
Kiểu

Cũ

Mới

Kiểu

Cũ

Mới

Kích thước từ

W

w

Header

H


A

Số vịng

R

l

Payload

P

M

Độ song song

D

p

Trailer

T

Z

Kích thước thẻ

|A|


t

Tag

A

T