Đề xuất S-Hộp có tính chất mật mã tốt cho hoán vị của hàm băm Keccak

 + 3 + 2, + 2] ⋙ ) ⇒ 6. (x, y) = (1, 0): a = 43, b = 44, c = 31, d = 
 14, e = 0 
 휃
 ← (퐿[ + 3 + 2, + 2] ⋙ ) ⊕ 7. (x, y) = (1, 1): a = 3, b = 20, c = 45, d = 
 4 4
 ∑푖=0(퐿[ + 3 + 1, 푖] ⋙ ) ⊕ ∑푖=0(퐿[ + 61, e = 28 
 3 + 3, 푖] ⋙ ( − 1)). 
 8. (x, y) = (1, 2): a = 25, b = 6, c = 8, d = 18, 
 (6) 
 e = 1 
40 No 1.CS (11) 2020 
 Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
9. (x, y) = (1, 3): a = 10, b = 36, c = 15, d = có kích thước 5×5 bit, chi tiết minh họa thuật ngữ 
 56, e = 27 slice có thể tham khảo trong [1]. Chúng ta chỉ 
 quan tâm đến các giá trị của , , , và 푒 mà 
10. (x, y) = (1, 4): a = 39, b = 55, c = 41, d = chúng liên tiếp nhau. Ví dụ, trong trường hợp 
 2, e = 62 ( , ) = (0, 0), có = 44 và = 43. Vì trong 
11. (x, y) = (2, 0): a = 31, b = 43, c = 14, d = các biểu thức của , , , và chứa các thành 
 0, e = 44 phần , − 1, , − 1, , − 1, , − 1, 푒 và 
 푒 − 1 (thỏa mãn như phần in đậm ở phân tích 
12. (x, y) = (2, 1): a = 45, b = 3, c = 61, d = theo bảng offset). Nếu không có các giá trị liên 
 28, e = 20 tiếp như vậy, có nghĩa là các bit nằm ở các slice 
13. (x, y) = (2, 2): a = 8, b = 25, c = 18, d = 1, khác nhau, nghĩa là trong biểu thức của , , , 
 e = 6 và sẽ không chứa các lane chung hoặc chứa các 
 lane chung nhưng các bit tương ứng nằm ở các 
14. (x, y) = (2, 3): a = 15, b = 10, c = 56, d = slice khác nhau. Từ đây, chúng ta sẽ có kết luận 
 27, e = 36 về số bit phụ thuộc. 
15. (x, y) = (2, 4): a = 41, b = 39, c = 2, d = Xét các trường hợp cụ thể sau: 
 62, e = 55 
 Trường hợp (풙, 풚) = ( , ), có: 
16. (x, y) = (3, 0): a = 14, b = 31, c = 0, d = 
 4
 44, e = 43 휃−1
 → (퐿[1,1] ⋙ 44) ⊕ ∑(퐿[0, 푖] ⋙ 44)
17. (x, y) = (3, 1): a = 61, b = 45, c = 28, d = 푖=0
 4
 20, e = 3 
 ⊕ ∑(푳[ , 풊] ⋙ ퟒ ) 
18. (x, y) = (3, 2): a = 18, b = 8, c = 1, d = 6, 푖=0
 e = 25 4
 휃−1
19. (x, y) = (3, 3): a = 56, b = 15, c = 27, d = → (푳[ , ] ⋙ ퟒ ) ⊕ ∑(퐿[1, 푖] ⋙ 43)
 36, e = 10 푖=0
 4
20. (x, y) = (3, 4): a = 2, b = 41, c = 62, d = ⊕ ∑(퐿[3, 푖] ⋙ 42) 
 55, e = 39 푖=0
21. (x, y) = (4, 0): a = 0, b = 14, c = 44, d = Thấy rằng khi 푖 = 2, hai biểu thức trên có 1 
 43, e = 31 lane chung là 퐿[2,2] ⋙ 43. Do vậy, trong 
 trường hợp này 64 bit thuộc 퐿[0,0] sẽ phụ thuộc 
22. (x, y) = (4, 1): a = 28, b = 61, c = 20, d = vào 11 + 11 + 11 + 11 + 11 – 1 = 54 bit đầu vào. 
 3, e = 45 
 Trường hợp (풙, 풚) = ( , ), có: 
23. (x, y) = (4, 2): a = 1, b = 18, c = 6, d = 25, 
 4
 e = 8 휃−1
 → (푳[ , ] ⋙ ퟒ ) ⊕ ∑(퐿[1, 푖] ⋙ 43)
24. (x, y) = (4, 3): a = 27, b = 56, c = 36, d = 푖=0
 10, e = 15 4
 ⊕ ∑(퐿[3, 푖] ⋙ 42) 
25. (x, y) = (4, 4): a = 62, b = 2, c = 55, d = 푖=0
 39, e = 41 
 Trong mỗi lane ở các biểu thức trên, đại 
lượng , , , và 푒 sẽ quy định xem các bit có 
nằm cùng 1 slice hay không (slice là một mặt bit 
 Số 1.CS (11) 2020 41 
Journal of Science and Technology on Information security 
 4
 휃−1 7 128 1164 1564 1564 
 → (퐿[1,1] ⋙ 44) ⊕ ∑ (퐿[0, 푖] ⋙ 44)
 8 256 1382 1591 1591 
 푖=0
 4 9 512 1491 1598 1598 
 ⊕ ∑(푳[ , 풊] ⋙ ퟒ ) 
 10 1024 1545 1599 1599 
 푖=0
 11 1408 1572 1599 1599 
 Thấy rằng, khi 푖 = 2, hai biểu thức trên có 1 
lane chung là 퐿[2,2] ⋙ 43. Do vậy, trong 12 1536 1586 1599 1599 
trường hợp này, 64 bit thuộc lane 퐿[1,0] sẽ phụ 13 1578 1593 1599 1599 
thuộc vào 11 + 11 + 11 + 11 + 11 – 1 = 54 bit 14 1592 1596 1599 1599 
đầu vào. 
 15 1597 1598 1599 1599 
 Tương tự, trong các trường hợp ( , ) = 16 1599 1599 1599 1599 
(2, 0), (3, 0) và (4, 0) thì mỗi 64 bit tương ứng 
thuộc mỗi lane 퐿[2,0], 퐿[3,0] và 퐿[4,0] phụ Từ Bảng 5 thấy rằng, phải đến vòng thứ 16 
thuộc vào 54 bit đầu vào. Như vậy, sẽ có 5 × thì bậc đại số của dạng biểu diễn phương trình 
64 = 320 bit đầu ra phụ thuộc vào 54 bit đầu đại số đối với hoán vị trong Keccak mới đạt cực 
vào. Còn lại 1600 – 320 = 1280 bit đầu ra phụ đại. Còn khi thay bằng S-hộp đề xuất sẽ là 10. 
thuộc vào 55 bit đầu vào.■ Như vậy, khi bậc đại số của S-hộp cao hơn sẽ 
 ảnh hưởng trực tiếp đến các ước lượng trong 
 Như vậy, với S-hộp đề xuất, hàm vòng tương 
 Bảng 5. Hơn nữa, điều này cũng được giải thích 
ứng nhận được có số bit phụ thuộc lớn hơn nhiều 
 phần nào thông qua đánh giá số bit phụ thuộc ở 
so với trong Keccak. Điều này có được là do biểu 
 Mệnh đề 2, 3. Do vậy, hoán vị Keccak-f với S-
thức đại số của các hàm bool trong S-hộp đề xuất 
 hộp đề xuất là có tính chất đại số tốt hơn của 
là phức tạp hơn. Do vậy dạng biểu diễn phương 
 Keccak-f nguyên thủy. Với tính chất đại số như 
trình đại số qua các vòng của hoán vị sử dụng S-
 vậy, hàm băm Keccak sử dụng S-hộp đề xuất sẽ 
hộp này sẽ có bậc đại số cao hơn trong Keccak. 
 có khả năng kháng lại tốt hơn trước các tấn công 
B. Bậc đại số của hoán vị Keccak-f sử dụng S- phân biệt dựa trên tổng bằng 0 so với hàm băm 
hộp đề xuất Keccak nguyên thủy. 
 Áp dụng các kết quả nghiên cứu về bộ phân C. Tính tuyến tính hóa không đầy đủ của S-hộp 
biệt tổng bằng 0 cho hoán vị Keccak-f trong [2], đề xuất 
chúng ta có bảng ước lượng sau: 
 Ở các mục trên, nhóm tác giả đã phân tích 
 BẢNG 5. BẬC ĐẠI SỐ CHO SỐ VÒNG RÚT GỌN TRONG tính chất tuyến tính hóa không đầy đủ đối với S-
 KECCAK-F VÀ KECCAK-F SỬ DỤNG S-HỘP ĐỀ XUẤT hộp trong Keccak-f. Có nghĩa rằng, tồn tại các 
 tập con mà ở đó một số phương trình biểu diễn 
 Hoán vị sử dụng S-
 Hoán vị gốc S-hộp trong Keccak-f có dạng tuyến tính (ví dụ 
 hộp đề xuất 
 r các tập trong Bảng 2). Với tính chất này, các tác 
 deg(푅 ) deg(푖푛푣푅 ) deg(푅 ) deg(푖푛푣푅 ) giả trong [8]-[10] thực hiện việc lập hệ phương 
 1 2 3 4 4 trình cho số vòng nhỏ của Keccak. Từ đó đưa ra 
 tấn công. Áp dụng tương tự đối với S-hộp đề 
 2 4 9 16 16 
 xuất trong bài báo thấy rằng, các tính chất như 
 3 8 27 64 64 trong [8] là không còn đúng nữa. Do vậy, việc 
 4 16 81 256 256 sử dụng các phương trình tuyến tính để mở rộng 
 5 32 243 1024 1024 số vòng trong tấn công tìm va chạm theo các 
 cách tiếp cận trong [8]-[10] là không áp dụng 
 6 64 729 1456 1456 
42 No 1.CS (11) 2020 
 Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
được cho phiên bản hàm băm Keccak mà sử VI. ĐÁNH GIÁ KHẢ NĂNG THỰC THI KHI SỬ DỤNG 
dụng S-hộp đề xuất này. S-HỘP ĐỀ XUẤT TRONG HOÁN VỊ KECCAK-F 
D. Sự ảnh hưởng đến cấu trúc Sponge của hàm Nhóm tác giả đã thực hiện xây dựng chương 
băm Keccak trình cài đặt trên ngôn ngữ C cho thuật toán 
 SpongeHash. Cài đặt ở đây không áp dụng một 
 Các nhà thiết kế mật mã thông thường sẽ lựa 
 chỉ lệnh SIMD hay Assembler nào. Cài đặt và 
chọn một cấu trúc tổng thể, sau đó có những đánh 
 biên dịch sử dụng Visual Studio 12 trên một nhân 
giá về cấu trúc này trước khi thiết kế cho các 
 máy Intel(R) Core(TM) i5-6200U CPU @ 
thành phần ở bên trong nó. Ví dụ như mã khối có 
 2.30GHz 2.40GHz, Windows 10, phiên bản x64 
các cấu trúc thông dụng: mạng SPN, mạng 
 bit. Bảng thống kê dưới đây thể hiện tốc độ thực 
Feistel,... Hàm băm có: cấu trúc Merkle-
 thi của các thuật toán, trong đó (AT) – ký hiệu 
Damgard, cấu trúc Sponge,... Trước khi đánh giá 
 cài đặt an toàn. Cài đặt an toàn được thực hiện 
lên những cấu trúc này, chúng ta thường lý tưởng 
 theo kỹ thuật mặt nạ hai chia sẻ trong [16]. 
hóa thành phần bên trong nó như là các mã khối 
lý tưởng, hoán vị ngẫu nhiên, biến đổi hay hàm BẢNG 6. TỐC ĐỘ THỰC THI CỦA 
ngẫu nhiên,... Kết quả, chúng ta sẽ có được SPONGEHASH VÀ KECCAK 
những tấn công tổng quát. Nói cách khác, tấn 
 Thuật toán Tốc độ Mb/s 
công tổng quát là những tấn công mà không khai 
 Phiên Cài đặt 
thác bất kỳ một thuộc tính mật mã bên trong một Cài đặt 
 Tên bản bình 
nguyên thủy mật mã, mà chỉ sử dụng cấu trúc an toàn 
 (bit) thường 
tổng thể trong thiết kế của nó. 
 256 1101,93 781,25 
 Đối tượng mà chúng tôi muốn hướng ở phần Keccak 
 512 599,70 422,83 
này đến là cấu trúc Sponge trong thiết kế hàm 
băm Keccak. Các tấn công tổng quát lên nó có 256 925,93 702,99 
 SpongeHash 
thể kể đến là: tìm va chạm bên trong, tìm chu kỳ 512 520,83 384,99 
đầu ra, tìm đường dẫn đến trạng thái trong, khôi 
 256 970 
phục trạng thái,... [14]. Ở những phân tích này, SHA-2 
các tác giả đã đưa ra những ước lượng độ an toàn 512 640 
cụ thể cho hai trường hợp sử dụng biến đổi ngẫu 
 BẢNG 7. SO SÁNH TỐC ĐỘ CÀI ĐẶT CỦA 
nhiên và hoán vị ngẫu nhiên trong cấu trúc 
 SPONGEHASH VÀ KECCAK 
Sponge. Ở một khía cạnh khác, với các biến đổi 
ngẫu nhiên và hoán vị ngẫu nhiên, nhóm tác giả Hàm băm Keccak 
trong [14] đã có những đánh giá lợi thế phân biệt Phiên 
 512 256 
của cấu trúc Sponge với bộ tiên tri ngẫu nhiên bản 512 256 
 (AT) (AT) 
(Theorem 7, Theorem 9 [14]). Có thể nói rằng, (bit) 
những phân tích trong các tài liệu nói trên đã 
 512 ↓13,1% 
không sử dụng một thuộc tính nào của hàm được 
sử dụng trong cấu trúc Sponge. Chính vì vậy, 256 ↓15,9% 
việc thay đổi và đề xuất S-hộp mới không làm 512 
 ↓10,0% 
thay đổi cấu trúc Sponge trong hàm băm Keccak. (AT) 
Nó không ảnh hưởng đến độ an toàn chứng minh SpongeHash 256 
 ↓8,9% 
được của cấu trúc Sponge trong hàm băm này. (AT) 
 Số 1.CS (11) 2020 43 
Journal of Science and Technology on Information security 
BẢNG 8. TỐC ĐỘ THỰC THI CÀI ĐẶT AN TOÀN SO VỚI CÀI hộp đề xuất có xác suất vi sai tốt hơn S-hộp 
 ĐẶT THÔNG THƯỜNG CỦA SPONGEHASH VÀ KECCAK nguyên thủy trong Keccak, nó sẽ đảm bảo được 
 rằng hàm băm Keccak sử dụng S-hộp đề xuất có 
 Hàm băm Keccak SpongeHash 
 khả năng kháng lại thám mã vi sai và biến thể 
 Phiên không kém hàm băm nguyên thủy. Nhóm tác giả 
 bản 512 256 512 256 sẽ tập trung phân tích những đánh giá theo hướng 
 (bit) 
 này ở những nghiên cứu tiếp theo. 
 512 
 ↓29,4% 
 (AT) Một vấn đề mở cũng đặt ra ở đây liên quan 
 đến các tấn công của nhóm Boura và cộng sự [2]-
 256 
 Keccak ↓29,1% 
 (AT) [5], cụ thể với các phân tích của nhóm này mà số 
 vòng của Keccak phiên bản hiện thời đã được 
 512 
 ↓26,1% tăng lên 24 so với 18 như ở phiên bản đầu tiên. 
 (AT) Vì vậy, khi sử dụng S-hộp đề xuất với các tính 
 256 chất đại số tốt hơn, liệu có thể giảm số vòng được 
 ↓24,1% 
 SpongeHash (AT) không? Khi đó tốc độ có thể cân bằng được với 
 phiên bản nguyên thủy. 
 Kết quả thống kê thấy rằng, sử dụng S-hộp 
đề xuất cho tốc độ thực thi có thể so sánh được 
so với phiên bản nguyên thủy, mặt khác độ an TÀI LIỆU THAM KHẢO 
toàn lại được cải thiện. 
 [1] NIST, SHA-3 Stadard: Permutation-Based Hash 
 VII. KẾT LUẬN And Extendable Output Functions. 8/2015. 
 Trong bài báo, nhóm tác giả đã khảo sát độ [2] Boura, C. and A. Canteaut. Zero-sum 
an toàn hàm băm Keccak dựa trên phân tích tính distinguishers for iterated permutations and 
chất của S-hộp được sử dụng trong nó. Kết quả application to Keccak-f and Hamsi-256. in 
chỉ ra rằng, các tham số mật mã của S-hộp trong International Workshop on Selected Areas in 
hoán vị Keccak-f đóng vai trò quan trọng ảnh Cryptography. 2010. Springer. 
hưởng lên độ an toàn của nó. Trên cơ sở các phân [3] Boura, C. and A. Canteaut. A zero-sum property 
tích này, chúng tôi đề xuất lựa chọn một S-hộp for the Keccak-f permutation with 18 rounds. in 
có các tính chất mật mã tốt hơn, thay thế S-hộp 2010 IEEE International Symposium on 
này vào hoán vị Keccak-f và thực hiện phân tích Information Theory. 2010. IEEE. 
sự ảnh hưởng của chúng như đối với hoán vị [4] Boura, C., A. Canteaut, and C. De Canniere. 
Keccak-f ban đầu. Kết quả phân tích chứng tỏ S- Higher-order differential properties of Keccak 
hộp đề xuất mang lại độ an toàn cao hơn. Với S- and Luffa. in International Workshop on Fast 
hộp đề xuất, bài báo cũng so sánh khả năng cài Software Encryption. 2011. Springer. 
đặt so với S-hộp gốc (Bảng 4). Một điều cũng dễ 
 [5] Boura, C. and A. Canteaut. On the algebraic 
hiểu rằng, với cấu trúc đại số phức tạp hơn thì S-
 degree of some SHA-3 candidates. in 
hộp đề xuất sẽ có tính chất cài đặt phức tạp hơn Proceedings of the Third SHA-3 Candidate 
so với S-hộp ban đầu. Tuy nhiên, phụ thuộc vào Conference, Washington DC. 2012. 
người sử dụng và từng bối cảnh cụ thể, với một 
tốc độ băm chấp nhận được, trong khi độ an toàn [6] Aumasson, J.-P. and W. Meier, Zero-sum 
được nâng cao hơn chắc chắn đây là một lựa chọn distinguishers for reduced Keccak-f and for the 
 core functions of Luffa and Hamsi. rump session 
không tồi trong bối cảnh phát triển của khoa học 
 of Cryptographic Hardware and Embedded 
thám mật mã trong thám mã. Systems-CHES, 2009. 2009: p. 67. 
 Bài báo cũng chưa đề cập đến độ an toàn của 
đề xuất mới trước thám mã vi sai. Tuy nhiên, S-
44 No 1.CS (11) 2020 
 Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
[7] Duan, M. and X. Lai, Improved zero-sum SƠ LƯỢC VỀ TÁC GIẢ 
 distinguisher for full round Keccak-f 
 TS. Nguyễn Văn Long 
 permutation. Chinese Science Bulletin, 2012. 
 57(6): p. 694-697. Đơn vị công tác: Phân viện 
 NCKHMM, Viện KH-CN mật mã, 
[8] Song, L., G. Liao, and J. Guo. Non-full sbox Ban Cơ yếu Chính phủ. 
 linearization: applications to collision attacks on Email: longnv@bcy.gov.vn. 
 round-reduced Keccak. in Annual International Quá trình đào tạo: Năm 2008 tốt 
 Cryptology Conference. 2017. Springer. nghiệp Học viện FSO – Liên bang 
[9] Qiao, K., et al. New collision attacks on round- Nga chuyên ngành “An toàn thông tin các hệ thống viễn 
 reduced Keccak. in Annual International thông”. Năm 2015 bảo vệ thành công luận án tiến sĩ tại 
 học viện FSO Liên bang Nga theo chuyên ngành “Các 
 Conference on the Theory and Applications of 
 phương pháp bảo vệ thông tin”. 
 Cryptographic Techniques. 2017. Springer. 
 Hướng nghiên cứu hiện nay: Nghiên cứu, thiết kế các 
[10] Dinur, I., O. Dunkelman, and A. Shamir. New thuật toán mã đối xứng an toàn, hiệu quả trong cài đặt. 
 attacks on Keccak-224 and Keccak-256. in 
 International Workshop on Fast Software 
 ThS. Lê Duy Đức 
 Encryption. 2012. Springer. 
 Đơn vị công tác: Khoa Kỹ thuật 
[11] Li, M. and L. Cheng. Distinguishing property for cơ sở, Học viện Phòng không - 
 full round keccak-f permutation. in Conference Không quân. 
 on Complex, Intelligent, and Software Intensive Email: leduchnnt@gmail.com. 
 Systems. 2017. Springer. Quá trình đào tạo: Năm 2006 tốt 
 nghiệp Học viện Kỹ thuật quân sự; 
[12] Guo, J., et al., Practical collision attacks against 
 Năm 2014 tốt nghiệp Thạc sĩ tại Học viện Kỹ thuật 
 round-reduced SHA-3. Journal of Cryptology, 
 quân sự. 
 2020. 33(1): p. 228-270. 
 Hướng nghiên cứu hiện nay: vô tuyến điện tử. 
[13] Rajasree, M.S. Cryptanalysis of Round-Reduced 
 KECCAK Using Non-linear Structures. in 
 International Conference on Cryptology in 
 India. 2019. Springer. 
[14] Bertoni, G., et al. Sponge functions. in ECRYPT 
 hash workshop. 2007. Citeseer. 
[15] Nguyễn Văn Long. “Phân tích các thành phần mật 
 mã trong hoán vị Keccak-p”. Nghiên cứu Khoa 
 học và Công nghệ trong lĩnh vực An toàn thông 
 tin, ISSN 2615-9570, No 08. Vol 02. 2018. 
[16] Bertoni, G., et al., Keccak implementation 
 overview. URL:  neokeon. 
 org/Keccak-implementation-3.2. pdf, 2012. 
 Số 1.CS (11) 2020 45