Một cải tiến cận an toàn kháng va chạm cho lược đồ Hirose trong mô hình mã pháp lý tưởng

n hoàn (cyclic 
double block length). tức là s là giá trị nhỏ nhất (lớn hơn 0) 
 Định nghĩa 4 (Definition 6, [14]). Cho thoả mãn  s ss . 
 ,* là một nhóm, N . Gọi (ii) Nếu có một giá trị c N* thoả mãn 
F CYC :22 0,1b  là một hàm nén thoả  sSsc%%: , ta nói rằng thứ tự của ánh xạ 
 CYC  , được ký hiệu là  , bằng c, tức là 
mãn GHFGHMiiiii,,, 11 trong đó 
 b  c . Nếu không tồn tại c như vậy thì 
GHGHiiii 11,,,  và Mbi 0,1 , 0. Cho 
  :0 . Chú ý rằng nếu  0 thì bậc của 
EBC   ,0,1 b là một mã khối; và  
  bằng bậc của một phần tử bất kỳ được 
 b
là các hoán vị trên  2 0,1 và TB, là các chọn từ S. 
hoán vị trên  . Đặt Định nghĩa 6 (Definition 8, [14]). Cho 
 CYC
 2 b F ,,  như được định nghĩa trong Định 
ZGHM:,,0,1  iii 11  . Khi đó 
 CYC
XXKKTBTB,,,0,1   b thoả mãn nghĩa 4. Nếu  2 thì F được gọi là hàm 
 nén độ dài khối kép tuần hoàn (CDBL) với độ 
 XKZTT, và XKZBB,  . Khi 
 dài chu kỳ là  . 
đó F CYC chứa mã khối E được biểu diễn như 
 Trong trường hợp hàm nén Abreast-DM và 
sau: 
 Hirose, ta có: 
 GEMX TTT* 
 i KT Hàm nén Abreast-DM: 
 HEMX BBB* n TB
 i K B  0,1 ,,,,b nIDXXID và 
  G,,,, H MH M G . Hàm nén Abreast-DM 
trong đó tính toán đưa ra Gi thường được gọi 
là hàng trên và tính toán Hi được gọi là hàng có chu kỳ  c 6 . 
dưới. Hàm nén Hirose: 
 CYC
 Hàm nén F được minh hoạ như trong  0,1n ,,,b nIDID TB và 
Hình 5. 
  Gi 1,,,, H i 1 M i  G i 1 c H i 1 M i . Hàm nén 
 Hirose có chu kỳ  2 . 
32 Số 1.CS (09) 2019 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 III. ĐỘ AN TOÀN CỦA CẤU TRÚC Fleichmann cùng đồng sự [16] đã cải tiến cận 
 ABREAST-DM VÀ TANDEM-DM này. Kết quả được đưa ra trong Định lý 2. 
 Đã có nhiều kết quả nghiên cứu độc lập chỉ Định lý 2 (Theorem 2, [16]). Cho 
ra Abreast-DM và Tandem-DM đạt độ an toàn F ADM :0,10,1 32nn  là hàm nén dựa trên mã 
và kháng tiền ảnh tối ưu. Phần này nhắc lại một khối được mô tả như Hình 1. Cho 0 là một 
số kết quả tốt nhất đã có cho 2 lược đồ này đến số nguyên và N, q là các số tự nhiên thoả mãn 
nay theo hiểu biết của các tác giả. n
 N 2 . Khi đó 
 Trong [15], Lee cùng đồng sự đã đưa ra cận 
an toàn kháng va chạm cho hàm nén Abreast- Pre 16 8q 2 eq 4 q
 AdvADM q 2 2 . 
DM là NNNNN 2 
 2
 Coll qq18 Hệ quả 2 (Corollary 2, [16]). Ta có 
 AdvqADM . 
 26n q n 2 Pren 210 
 26 q AdvoADM 21/21 
 Tuy nhiên, trong [14] Fleischmann cùng trong đó o 1 tiến đến 0 khi n . 
đồng sự cũng đã độc lập đưa ra cận an toàn Trong [17], Lee và đồng sự đã đưa ra cận 
kháng va chạm cho hàm nén Abreast-DM chặt kháng va chạm và kháng tiền ảnh cho Tandem-
hơn như sau: DM như sau: 
 Định lý 1 (Theorem 1, [14]). Cho Định lý 3 (Theorem 1, [17]). Cho 
 ADM
FF: như trong Định nghĩa 1 và n, q là NqNNNq 2,/2,2n và một số nguyên 
 n 2 . 5 8
các số tự nhiên với q 2 . Khi đó thoả mãn 12 q . Khi đó 
 2 
 Coll q 244eqqq 
 Adv q 18 . Coll 
 ADM n 1 AdvqNTDM 2. 
 2 NNN 
Từ đó, ta có kết quả sau: Một ví dụ cho Định lý 3 là với 
 120.87
 Hệ quả 1. Cho FF: ADM như trong Định nq 128,2 và 16 ta có 
 n 3.58
nghĩa 1 và n, q là các số tự nhiên với q 2 . Coll 120.87
 AdvTDM 21/ 2 . 
Khi đó 
 Định lý 4 (Theorem 2, [17]). Cho 
 1
 AdvqoColl 1 NqN 2,n 2 và 0 là một số nguyên. Thì 
 ADM 2
trong đó o 10 khi n . Pre 0 16824 qeqq 
 AdvqTDM 2 2 . 
 NNNNN 2 
 2 
 q 1
 Chứng minh. Xét 18 n 1 suy ra Một ví dụ cho Định lý 4 là với 
 22
 nq 128,2 245.99 q1/2 /2
 n 1 và ta có 
 2 n 1 log2 6 n 3.58
q 22 . Áp dụng Định lý 1 Pre 0245.99
 6 AdvTDM 20.498 . 
với q 2n 3.58 suy ra điều phải chứng minh. 
 IV. ĐỘ AN TOÀN CỦA LƯỢC ĐỒ HIROSE 
 Hệ quả 1 có ý nghĩa đó là một kẻ tấn công 
 n 3.58 Một điều đáng chú ý đó là lược đồ Hirose 
bất kỳ thực hiện ít hơn 2 truy vấn đến bộ 
tiên tri mã khối thì không thể tìm được một va được đề xuất sau hơn 10 năm so với thời điểm 
chạm cho hàm nén Abreast-DM với một xác hai lược đồ Abreast-DM và Tandem-DM được 
suất đáng kể (ở đây là lớn hơn bằng 1/2). đề xuất. Nhưng cũng phải đến gần đây các kết 
 quả an toàn chứng minh được của cả 3 lược đồ 
 Trong [15] Lee và Kwon đã chỉ ra cận an này mới được đưa ra. Trong đó, các kết quả chỉ 
toàn kháng tiền ảnh cho Abreast-DM là ra rằng lược đồ Hirose đạt được độ an toàn 
 Pre n 2
AdvADM q 6 q / 2 6 q . Tuy nhiên, cận này kháng va chạm và kháng tiền ảnh cao hơn hai 
 n lược đồ còn lại. 
trở nên vô nghĩa khi q 2 / 6 . Sau đó, 
 Số 1.CS (09) 2019 33 
Journal of Science and Technology on Information Security 
 A. Độ an toàn kháng va chạm của lược đồ Chứng minh của Định lý 5 có thể áp dụng 
Hirose cho trường hợp tổng quát của các lược đồ hàm 
 Trong [14], Lee cùng đồng sự đã đưa ra kết nén tuần hoàn có  2 . Tuy nhiên, chúng tôi 
quả sau: đã xem xét và chứng minh lại đối với trường 
 Định lý 5 (Theorem 3, [14]). (Độ an toàn hợp cụ thể là lược đồ Hirose theo cách tiếp cận 
kháng va chạm cho  2) cho FF: CYC là của [18] và đưa ra một cận tốt hơn so với hệ 
 quả 5. Cụ thể chúng tôi đưa ra định lý sau: 
một hàm nén tuần hoàn với chu kỳ c  2 
 Định lý 6. Cho F Hirose :0,10,132nn là 
như trong Định nghĩa 6. Nếu TB thì a 1  
nếu không a 2 . Khi đó với q 1 và 2qN , một hàm nén dựa trên mã khối được mô tả như 
ta có Hình 3. Khi đó 
 Coll 2
 2 AdvqqqNq 1/ . 
 Coll 22aqq Hirose
 AdvqF . 
 Nq 2 2 Nq 2 Chứng minh. Xét một kẻ tấn công A bất 
 1
 Áp dụng cho hàm nén Hirose ta có Hệ quả kỳ thực hiện q truy vấn lên mã khối E hoặc E 
 H i r o s e
sau: để tìm va chạm đối với hàm nén F . A sẽ 
 q
 Hirose 32nn lưu một lịch sử truy vấn Q= Q , trong đó 
Hệ quả 3. Cho F :0,10,1   là một i i 1
 Q K X Y ,, thoả mãn E X Y . Chú ý 
hàm nén dựa trên mã khối được mô tả như iiii Kiii 
Hình 3. Khi đó rằng A không bao giờ thực hiện lặp lại 1 truy 
 Coll 2 2 vấn mà hắn đã biết câu trả lời. Chúng ta xét một 
 AdvqqNqqNqHirose 2/22/2 . 
 kẻ tấn công A mô phỏng A nhưng đôi khi sẽ 
 Chứng minh. Áp dụng Định lý 5 cho lược thực hiện thêm một truy vấn bổ sung lên bộ tiên 
  2,
đồ Hirose với TB ta có điều phải tri E dưới một số điều kiện nào đó. Do đó, A 
chứng minh. là mạnh hơn A và ta chỉ cần tìm cận trên của 
 Hệ quả 4. Cho F Hirose :0,10,1 32nn  là xác suất thành công của A để đưa ra một va 
 Hirose
một hàm nén dựa trên mã khối được mô tả như chạm cho hàm nén F . 
Hình 3. Khi đó với q 2n 2.77 ta có Kẻ tấn công A sẽ duy trì một danh sách 
 L (được khởi tạo là rỗng) mô tả một đầu 
 Coll
 Advqo 1/ 21 Hirose
 Hirose vào/đầu ra bất kỳ của hàm nén F mà có thể 
trong đó o 1 tiến về 0 khi n tiến ra vô cùng. tính được bởi kẻ tấn công A . Một phần tử 
 5n
 Chứng minh. Trước tiên ta thấy rằng vế L L là một bộ 4 giá trị KXYY, , , 0,1
phải của Hệ quả 3 là một hàm đồng biến theo q trong đó KX 0,1,0,12nn  là đầu vào 3n bit 
với qN /2. Xét 
 của hàm nén thoả mãn KHM i 1, và 
 2/22/21/qNqqNq2 2 2 . 
 XG i 1 . Các giá trị n bit YY, được cho bởi 
 Đặt qNqt/2 ta có phương trình bậc 2 YEX K và YEXC K . 
 2tt2 2 1/ 2 . Danh sách được xây dựng như sau. Kẻ tấn 
 công A sẽ thực hiện truy vấn thứ i lên E hoặc 
 Phương trình có nghiệm dương là 
 E 1 với 1 iq. Nếu là truy vấn lên E, kẻ tấn 
 12 q 12
t . Trả lại biến suy công sẽ thu được bộ 3 KXY,, trong đó 
 2 Nq 22 i i i 
 EXY . Nếu là truy vấn lên E 1 , kẻ tấn 
ra: Kiii 
 12 công vẫn thu được một bộ 3 KXYi,, i i nhưng 
 qN 2n 2.77 . 
 22 là EYX 1 . Trong mỗi trường hợp đó, giá 
 Kiii 
 Áp dụng Hệ quả 3, suy ra điều phải chứng trị XYii được xác định một cách ngẫu nhiên. 
minh. Bây giờ, A sẽ kiểm tra xem một phần tử 
 LKX ii, ,*,* hoặc LKXC  ii, ,*,* có 
34 Số 1.CS (09) 2019 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
trong danh sách L hay không, trong đó “*” là Coll qq 1 
 Adv Hirose A . 
một giá trị tuỳ ý. Khi đó, chúng ta phân tích 2 F Nq 2
trường hợp mà A gặp phải. 
 Vì A là một kẻ tấn công bất kỳ thực hiện q 
 Trường hợp 1: Cả L và L đều không có 
 truy vấn nên ta có 
trong L . Khi đó A sẽ thực hiện một truy vấn 
 Coll 2
xuôi Y E  X C . Do hằng số C khác 0 AdvqqqNqHirose 1/ . 
 iKi i 
nên giá trị của Y xuất hiện ngẫu nhiên đều và Hirose 32nn
 i Hệ quả 5. Cho F :0,10,1   là 
độc lập với . Khi đó, đặt LKXYY:,,, và 
 Yi iiiii một hàm nén dựa trên mã khối được mô tả như 
thêm vào danh sách L . hình 3. Khi đó với q 2n 1.27 ta có 
 Bây giờ chúng ta định nghĩa thế nào là một Coll
 Advqo 1/21 
va chạm trong danh sách. Cố định 2 số nguyên Hirose
 trong đó o 1 tiến về 0 khi n tiến ra vô cùng. 
ab, với ab , sao cho LKXYYaaaaa ,,, là 
phần tử thứ a trong L và LKXYYbbbbb ,,, là Chứng minh. Trước tiên ta thấy rằng vế phải 
 của Định lý 6 là một hàm đồng biến theo q với 
phần tử thứ b trong L . Ta nói rằng La và Lb va 
chạm nếu một va chạm của hàm nén xảy ra sử qN . Xét 
dụng các kết quả truy vấn trong L và L . Sự 2
 a b qqNq 1/1/2 . 
kiện này xảy ra khi và chỉ khi một trong 2 điều 
kiện sau xảy ra. Suy ra 
 qN 212 n 1.27 . 
 (i) YXYXaabb  và YXYXaabb   
 (ii) và 
 YXYXCaabb  Áp dụng Định lý 6, suy ra điều phải chứng minh. 
 YXYXC   
 aabb B. Độ an toàn kháng tiền ảnh của lược đồ 
 Đối với truy vấn thứ i có tối đa i 1 phần tử Hirose 
trong danh sách L có thể va chạm với L . Do 
 i Trong [15], Lee và Kwon đã chứng minh 
đó, xác suất thành công của truy vấn thứ i lớn 2
 rằng AdvqqNqPre 2/2 , cận này trở 
nhất là Hirose
 nên vô nghĩa khi qN /2. Sau đó, 
 i 1 2 21 i 
 . 
  22 Fleischmann cùng đồng sự [16] đã đưa ra một 
 j 1 N q N q cận cải tiến như sau: 
 Vì kẻ tấn công A thực hiện tối đa q truy Định lý 7 (Theorem 1, [16]). Cho 
vấn, nên danh sách L không thể chứa nhiều F Hirose :0,10,1 32nn  là một hàm nén dựa 
hơn q phần tử (với mỗi truy vấn của kẻ tấn 
 trên mã khối được mô tả như hình 3. Khi đó 
công A chỉ có thể thêm tối đa 1 phần tử vào 
 Pre 2
danh sách L của A ). Do đó, xác suất thành AdvqqNqNNHirose 8/8/2 . 
công đối với q truy vấn là Pre
 Đặc biệt, AdvqHirose bị chặn trên bởi xấp 
 q
 211 iq q 2
 . xỉ 16qN / . 
  22
 i 1 NqNq 
 V. KẾT LUẬN 
 Trường hợp 2: Rõ ràng theo cách xây 
 Trong bài báo này, chúng tôi đã đưa ra và 
dựng, không thể xảy ra trường hợp chỉ có chính 
 chứng minh một cận an toàn kháng va chạm 
xác 1 trong 2 giá trị L và L nằm trong L . Do 
 chặt hơn cho lược đồ hàm nén Hirose. Trong 
đó, giả sử rằng cả hai giá trị này đều đã có 
 đó, cận an toàn kháng va chạm mới của chúng 
trong L . Khi đó A sẽ bỏ qua truy vấn này vì 
 tôi cho lược đồ Hirose (Định lý 6) là tốt hơn 
chúng ta biết rằng A không có cơ hội chiến nhiều so với cận được đưa ra trong [14], và 
thắng, nếu không thì chúng ta đã đưa tấn công n 1.27
cho kẻ tấn công trước đó. tiệm cận đến độ an toàn tối ưu ( 2 ). 
 Hướng nghiên cứu tiếp theo: Có thể thấy cả 
 Vậy, xác suất để kẻ tấn công A thành 
 3 lược đồ Abreast-DM, Tandem-DM và Hirose 
công là: 
 Số 1.CS (09) 2019 35 
Journal of Science and Technology on Information Security 
đều sử dụng song song hai lược đồ Davies- [12]. Hirose, S. Provably secure double-block-
Meyer và đạt độ an toàn tối ưu, do đó có thể length hash functions in a black-box model. in 
hướng đến việc đề xuất và nghiên cứu độ an International Conference on Information 
toàn của các lược đồ hàm nén mới sử dụng các Security and Cryptology. 2004. Springer. 
lược đồ hàm nén đơn khác như lược đồ Matyas- [13]. Özen, O. and Stam, M. Another glance at 
Meyer-Oseas hoặc Miyaguchi–Preneel. Ngoài double-length hashing. in IMA International 
ra, việc xem xét độ an toàn của các lược đồ Conference on Cryptography and Coding. 
hàm nén trên trong mô hình mã pháp yếu (weak 2009. Springer. 
cipher model) cũng cần được nghiên cứu thêm. [14]. Fleischmann, E., Gorski, M., and Lucks, S. 
 Security of cyclic double block length hash 
 TÀI LIỆU THAM KHẢO functions. in IMA International Conference on 
[1]. Meyer, C.H. and Schilling, M. Secure program Cryptography and Coding. 2009. Springer. 
 load with manipulation detection code. in Proc. [15]. Lee, J. and Kwon, D., The security of 
 Securicom. 1988. Abreast-DM in the ideal cipher model. IEICE 
[2]. Lee, J. and Stam, M. MJH: A faster alternative transactions on fundamentals of electronics, 
 to MDC-2. in Cryptographers’ Track at the communications and computer sciences, 2011. 
 RSA Conference. 2011. Springer. 94(1): p. 104-109 
[3]. Lee, J. and Stam, M., MJH: a faster alternative [16]. Armknecht, F., et al. The preimage security 
 to MDC-2. Designs, Codes and Cryptography, of double-block-length compression functions. 
 2015. 76(2): p. 179-205 in International Conference on the Theory and 
 Application of Cryptology and Information 
[4]. Hohl, W., et al. Security of iterated hash Security. 2011. Springer. 
 functions based on block ciphers. in Annual 
 International Cryptology Conference. 1993. [17]. Lee, J., Stam, M., and Steinberger, J.J.J.o.C., 
 Springer. The security of Tandem-DM in the ideal cipher 
 model. 2017. 30(2): p. 495-518 
[5]. Prencel, B., et al. Collision-free hashfunctions 
 based on blockcipher algorithms. in Security [18]. Fleischmann, E., et al., Weimar-DM: The 
 Technology, 1989. Proceedings. 1989 Most Secure Double Length Compression 
 International Carnahan Conference on. 1989. Function. 
 IEEE. SƠ LƯỢC VỀ TÁC GIẢ 
[6]. Brown, L., Pieprzyk, J., and Seberry, J. LOKI— ThS. Trần Hồng Thái 
 a cryptographic primitive for authentication Đơn vị công tác: Viện Khoa học – 
 and secrecy applications. in International Công nghệ Mật mã, Ban Cơ yếu 
 Conference on Cryptology. 1990. Springer. Chính phủ. 
[7]. Mennink, B. Optimal collision security in E-mail: ththai@bcy.gov.vn. 
 double block length hashing with single length Nhận bằng Kỹ sư năm 2000 và 
 key. in International Conference on the Theory Thạc sĩ năm 2007 chuyên ngành Kỹ 
 and Application of Cryptology and Information thuật mật mã, Học viện Kỹ thuật 
 Security. 2012. Springer. Mật mã. 
[8]. Jetchev, D., Özen, O., and Stam, M. Collisions Hướng nghiên cứu hiện nay: Nghiên cứu đánh giá độ 
 an toàn của mã khối và hàm băm mật mã 
 are not incidental: A compression function 
 CN. Hoàng Đình Linh 
 exploiting discrete geometry. in Theory of 
 Cryptography Conference. 2012. Springer. Đơn vị công tác: Viện Khoa học - 
 Công nghệ Mật mã, Ban Cơ yếu 
[9]. Lai, X. and Massey, J.L. Hash functions based Chính phủ. 
 on block ciphers. in Workshop on the Theory 
 and Application of of Cryptographic Email: hoangdinhlinh@bcy.gov.vn 
 Techniques. 1992. Springer. Quá trình đào tạo: Nhận bằng cử 
 nhân Toán học tại Đại học Khoa 
[10]. Hirose, S. Some plausible constructions of học tự nhiên - Đại học Quốc gia Hà 
 double-block-length hash functions. in Nội năm 2014. 
 International Workshop on Fast Software 
 Encryption. 2006. Springer. Hướng nghiên cứu hiện nay: Nghiên cứu, thiết kế, 
 đánh giá độ an toàn chứng minh được của các thuật 
[11]. Stam, M. Blockcipher-based hashing toán mã hóa đối xứng. 
 revisited. in Fast Software Encryption. 2009. 
 Springer. 
36 Số 1.CS (09) 2019