Đánh giá chính xác cận an toàn cho mã xác thực LightMAC

esource-constrained environments by đƣợc xác thực trong mỗi lần sử dụng khóa rất lớn. 
Atul Luykx has security bound independ on Điều này không gây ảnh hƣởng lớn đến không 
message length. The tag length in LightMAC gian dữ liệu đƣợc xác thực. 
algorithm depend on demand of user’s. Tuy nhiên, trong các môi trƣờng có tài nguyên 
However, the security analysis’s Atul [1] hạn chế, tức là mã xác thực sử dụng mã khối cơ sở 
directly uses the Dodis’s result [2] which có kích cỡ là 32 bit hay 64 bit, thì số lƣợng thông 
presents for the case that tag length is the điệp đƣợc xác thực đối với mỗi khóa sẽ bị giảm đi 
block size. In this paper, we first evaluate the đáng kể. Thật vậy, tƣơng tự nhƣ trên, ta xét số 
security bound of LightMAC when tag lƣợng thông điệp đƣợc xác thực cho mỗi khóa khi 
length is less than the block size. Then, the trong các ứng dụng dùng mã khối 32 bit 
dependence on the message length of , và yêu cầu xác suất giả mạo của kẻ tấn công 
LightMAC’s security bound is reviewed. không vƣợt quá một phần một triệu [1]. Khi đó: 
Từ khóa— hàm giả ngẫu nhiên; mã xác thực 
thông điệp; LightMAC. 
Keywords— pseudorandom function; 
 Từ ràng buộc trên, ta suy ra mỗi khóa chỉ có 
message authentication code; LightMAC. 
 thể xác thực cho 64 thông điệp, mỗi thông điệp 
 I. GIỚI THIỆU gồm 1 khối. Tƣơng tự, chỉ có 32 thông điệp, mỗi 
 thông điệp 4 khối có thể đƣợc xác thực cho mỗi khóa. 
 Các mã xác thực thông điệp thông thƣờng 
nhƣ: CBC MAC, EMAC, CMAC, PMAC đều có Để giải quyết đƣợc vấn đề này, năm 2015, tại 
 hội nghị FSE, Atul Luykx và các cộng sự đã giới 
 thiệu một mô hình xác thực thông điệp sử dụng 
 Bài báo đƣợc nhận ngày 3/10/2018. Bài báo đƣợc nhận xét 
bởi phản biện thứ nhất vào ngày 30/10/2018 và đƣợc chấp mã khối hạng nhẹ với tên gọi là LightMAC [1] có 
nhận đăng vào ngày 14/11/2018. Bài báo đƣợc nhận xét bởi cận an toàn không phụ thuộc vào độ dài thông 
phản biện thứ hai vào ngày 30/10/2018 và đƣợc chấp nhận điệp. Điều này cho phép LightMAC xác thực 
đăng vào ngày 5/11/2018. nhiều thông điệp hơn đối với mỗi khóa. 
 Số 1.CS (07) 2018 59 
Journal of Science and Technology on Information Security 
 Các công trình liên quan. Đánh giá độ an Ta viết nếu nhƣ kẻ tấn công đƣợc quyền 
toàn cho mã xác thực thông điệp LightMAC đƣợc truy cập vào bộ tiên tri là hàm . 
Atul Luykz và các cộng sự trình bày trong [1]. Định nghĩa 1 (Definition 4.6, [4]). Cho là 
Cách tiếp cận này dựa trên mô hình băm-rồi-mac 
 một hàm được chọn ngẫu nhiên. Gọi là một 
của Dodis [2]. Tuy nhiên, kết quả của Dodis chỉ 
 kẻ tấn công phân biệt và hàm ngẫu nhiên 
phát biểu cho trƣờng hợp nhãn xác thực là toàn bộ 
đầu ra của hàm mã, trong khi mô hình của hoàn thiện . Ta xét hai thí nghiệm sau: 
LightMAC phát biểu cho cả trƣờng hợp đầu ra bị 
cắt ngắn. Do đó, cần phải có các đánh giá chính 
xác hơn cho LightMAC. 
 Trả về 
 Đóng góp của chúng tôi. Trong bài báo này, Trả về 
chúng tôi đánh giá lại cận an toàn cho LightMAC Lợi thế của một kẻ tấn công trong việc 
trong trƣờng hợp nhãn xác thực chỉ lấy bit phân biệt giữa với một hàm ngẫu nhiên hoàn 
đầu ra. Ngoài ra, chúng tôi cũng phân tích, so sánh 
 thiện là: 
mức độ phụ thuộc vào độ dài thông điệp của mã 
xác thực thông điệp này với các mã xác thực | [ ]
thông điệp trƣớc đó. 
 [ ]| 
 Phần còn lại của bài báo đƣợc tổ chức gồm: 
Mục II trình bày các kiến thức cơ sở liên quan; Hàm lợi thế trong tấn công phân biệt hàm với 
Mục III sẽ đƣa ra một số kết quả đã có; Cuối cùng một hàm ngẫu nhiên hoàn thiện là: 
trong Mục IV sẽ phân tích độ an toàn của 
LightMAC và đƣa ra một số kết luận. 
 II. CÁC KIẾN THỨC CƠ SỞ trong đó là tập các bộ phân biệt giả 
A. Một số ký hiệu ngẫu nhiên chạy trong thời gian sử dụng tối 
 đa truy vấn. 
 Ký hiệu là tập các chuỗi bit có độ dài ; 
 Tƣơng tự, có định nghĩa khi hàm 
 là tập các chuỗi bit có độ dài không vƣợt 
quá ; là tập các chuỗi bit có độ dài bất kỳ. là một hoán vị đƣợc chọn ngẫu nhiên. 
 là tập các hàm từ vào . Với số nguyên Một hàm đƣợc chọn ngẫu nhiên đƣợc gọi là 
 , biểu diễn cách viết lại theo 
 giả ngẫu nhiên nếu nhƣ không đáng 
bit. Với chuỗi độ dài bit, ký hiệu ⌊ ⌋ là kể với mọi kẻ tấn công có năng lực thực tế. 
bit ít có ý nghĩa nhất của . Ký hiệu là phép Định nghĩa 2. (Definition 1, [2], hàm băm 
lấy ngẫu nhiên; trong khi là phép chia thông hầu 2-phổ quát) Một hàm băm 
điệp thành các khối bit, khối cuối nhỏ hơn là hầu 2-phổ quát nếu như mọi 
hoặc bằng bit. Trong bài báo này ký hiệu và 
 là phép đệm các bit có dạng 100 vào 
sau sao cho | | . [ ] 
B. Một số khái niệm, định nghĩa Trong bài báo này, sẽ thống nhất gọi “ -phổ 
 Hàm đƣợc chọn ngẫu nhiên (tƣơng ứng quát” thay cho “hầu 2-phổ quát”. 
hoán vị đƣợc chọn ngẫu nhiên) ở đây đƣợc hiểu Tính chất 1. (tr 5, [2]). Xét 
là hàm (tƣơng ứng hoán vị) đƣợc lấy ngẫu nhiên 
 là một hàm băm -phổ quát. Gọi là 
từ (tƣơng ứng ) phù hợp với một thông điệp khác nhau. Khi đó: 
phân phối xác suất cố định. Hàm (hoán vị) ngẫu 
nhiên hoàn thiện là hàm (hoán vị) đƣợc lấy ngẫu [ ( )]
nhiên đều từ tập ( ). 
 Tiếp theo sẽ xem xét khái niệm lợi thế phân Tiếp theo, bài báo trình bày định nghĩa mã 
biệt. Theo đó, lợi thế phân biệt của một kẻ tấn xác thực thông điệp và mô hình an toàn của nó. 
công có đƣợc khi phân biệt một hàm đƣợc chọn Để thuận tiện cho các phân tích và đánh giá ở 
ngẫu nhiên với một hàm ngẫu nhiên hoàn thiện. 
60 Số 1.CS (07) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
các phần sau, những khái niệm sau đây đƣợc Hàm lợi thế trong tấn công giả mạo là 
nhắc lại. 
 ( )
Định nghĩa 3. (xem Definition 4.1, [5]) Một mã 
xác thực thông điệp (MAC) gồm có 3 thuật toán ( )
thời gian đa thức (Gen, Mac, Vrfy) thỏa mãn: trong đó giá trị max lấy trên tất cả kẻ tấn công 
1. Thuật toán sinh khóa Gen là phép chọn chạy với thời gian , sử dụng nhiều nhất 
 khóa ngẫu nhiên từ tập khóa truy vấn Mac và truy vấn xác thực. 
2. Thuật toán sinh nhãn Mac (có thể xác suất) C. Thuật toán LightMAC 
 lấy đầu vào là và thông điệp và Trong [1] đã giới thiệu thuật toán 
 đưa ra nhãn . Ta ký hiệu LightMAC. Mô tả ngắn gọn về thuật toán này 
3. Thuật toán xác thực Vrfy tất định lấy đầu đƣợc trình ở Hình 1 và Thuật toán 1 dƣới đây. 
 vào là khóa , thông điệp và nhãn . 
 Thuật toán đưa ra một bit , với 
 nghĩa là hợp lệ còn thì ngược lại. Ta 
 viết lại . 
 Với mọi khóa được sinh bởi Gen và mọi 
 thì luôn có ( ) . 
 Mã xác thực thông điệp an toàn nghĩa là 
không có một kẻ tấn công hiệu quả nào có thể 
giả mạo một giá trị nhãn cho thông điệp mới 
bất kỳ, mà chƣa từng đƣợc sử dụng để trao đổi 
trƣớc đây. 
 Hình 1. Mô tả thuật toán LightMAC 
 Thí nghiệm xác thực thông điệp 
 cho thông điệp ‖ ‖ ‖ với 
1. Chạy thuật toán Gen sinh ra khóa . và 
2. Kẻ tấn công thực hiện tối đa truy 
 Trong đó, là một mã khối, 
 vấn lên bộ tiên tri Gọi và lần lƣợt là các số nguyên không lớn hơn 
 là tập tất cả các truy vấn mà yêu cầu lên 
 và . LightMAC lấy đầu vào là hai khóa , 
 bộ tiên tri. đƣợc chọn đều và độc lập từ tập , và thông 
3. Kẻ tấn công đƣa ra tối đa truy vấn xác điệp có độ dài tối đa bit. Thuật toán 
 thực lên bộ tiên tri . thành công trả về một đầu ra có độ dài bit. Cặp thông điệp-
 nhãn khi đó sẽ là . 
 khi và chỉ khi (1) với cặp 
 truy vấn xác thực nào đó và (2) 
 Thuật toán 1. 
 . Trong trƣờng hợp này thí nghiệm 
 đƣa ra 1, ngƣợc lại thí nghiệm đƣa ra 0. Input: 
 Định nghĩa 4. (Xem Definition 4.2 [5]) Xét Output: 
 1. 
 (Gen, Mac, Vrfy) là một mã xác thực thông 
điệp và là một thuật toán thời gian đa thức 2. \\chia thành các 
xác suất được quyền truy cập lên bộ tiên tri khối bit 
 và sau đó trả về một bit 3. for to do 
như trong thí nghiệm trên. 
 4. ( ) 
 Lợi thế giả mạo của được định nghĩa là 5. end 
 6. 
 [ ] 
 7. ⌊ ⌋ 
 8. return 
 Số 1.CS (07) 2018 61 
Journal of Science and Technology on Information Security 
 III. CÁC KẾT QUẢ ĐÃ CÓ trƣờng hợp nhãn xác thực là toàn bộ đầu ra của 
 hàm , trong khi đó LightMAC chỉ lấy bit. 
 Định lý 1. (Theorem 2, [1]). Lợi thế giả mạo 
lên LightMAC của một kẻ tấn công bất kỳ chạy IV. PHÂN TÍCH CẬN AN TOÀN 
trong thời gian thực hiện tối đa truy vấn CỦA LIGHTMAC 
MAC và truy vấn xác thực với độ dài thông 
 Trong phần này, chúng tôi sẽ đánh giá lại cận 
điệp tối đa là bit, không vượt quá 
 an toàn cho LightMAC trong trƣờng hợp độ dài 
 nhãn xác thực là bit ( ). 
( ) . /
 ⁄ ⁄ Đầu tiên, chúng tôi đƣa ra mệnh đề sau về độ 
 an toàn của mô hình băm-rồi-mac đối với trƣờng 
 hợp đầu ra của hàm băm bị cắt ngắn. 
 Mệnh đề 3. Gọi là một hàm 
 ( ) 
 băm -phổ quát và là một hoán vị ngẫu nhiên 
 trong đó, là kích cỡ khối, hoàn thiện trên . Xét lược đồ MAC với khóa bí 
 ( ) và 
 mật với nhãn xác thực cho thông điệp 
 ( ). 
 được tính bởi: 
 Để chứng minh Định lý 1, Atul Luykx đã sử 
 ⌊ ( )⌋ 
dụng hai Mệnh đề sau: 
 Mệnh đề 1. (Proposition 1, [2]) (Độ an toàn Gọi là một kẻ tấn công thực hiện tối đa 
của băm-rồi-mac) Gọi là một hàm truy vấn Mac và tối đa truy vấn xác 
băm -phổ quát và là một hoán vị ngẫu nhiên thực. Xác suất giả mạo thành công của không 
hoàn thiện trên . Xét lược đồ MAC với khóa bí vƣợt quá: 
mật với nhãn xác thực cho thông điệp 
 { } 
 được tính bởi: 
 ( ) Chứng minh. Để chứng minh kết quả này ta 
 xét là một kẻ tấn công lên lƣợc đồ Mac thực 
 Gọi là một kẻ tấn công thực hiện tối đa 
 hiện tối đa truy vấn Mac và truy vấn 
 truy vấn Mac và tối đa truy vấn xác xác thực. Gọi Coll là sự kiện có xảy ra va chạm 
thực. Nếu ⁄ | | thì xác suất giả 
 giữa hai đầu ra và từ bộ tiên tri Mac của hai 
mạo thành công của không vƣợt quá: 
 truy vấn và sao cho và . 
 Khi đó ta có: 
 Mệnh đề 2. (Proposition 1, [1]). Đặt [ ] 
 . Gọi với [ | ] [ ] 
và định nghĩa là: [ | ̅̅ ̅̅ ̅ ] [ ̅̅ ̅̅ ̅ ] 
 ( ) [ ] [ | ̅̅ ̅̅ ̅ ] 
 Trong đó là hoán vị ngẫu nhiên hoàn thiện Sau đây sẽ lần lƣợt đánh giá hai xác suất trên 
trên , khi đó xác suất để hai thông điệp khác Ta có: 
nhau va chạm là: 
 [ ] 
 [ ] 
 [ ( ) 
 Trong đó và lần lƣợt là độ dài của và 
 ] 
 theo khối -bit làm tròn (khối cuối cùng 
có thể chƣa đủ bit, nhƣng ta xem nhƣ nó là 
một khối đủ bit). ∑ [ ( ) 
 Tuy nhiên, chúng tôi nhận thấy rằng cách 
 ] 
đánh giá của Atul Luykx là dễ gây hiểu nhầm. Bởi 
vì kết quả trong Mệnh đề 1 chỉ phát biểu cho . (theo Tính chất 1). 
62 Số 1.CS (07) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Tiếp theo ta sẽ chứng minh rằng: giống nhau, ta đánh dấu các lần đó là 
 ̅̅̅̅̅ . 
 [ | ] 
 Tƣơng tự cách tính trong trƣờng hợp , ta 
 , -. 
 ⁄ ⁄ 
 có . 
 Với mọi , đặt là xác suất 
 * ( ( )) | ̅̅ ̅̅ ̅ + 
giả mạo thứ của là thành công mà không xảy 
ra va chạm trong truy vấn MAC. Khi đó ta * ( ( )) + 
có [ | ̅̅ ̅̅ ̅ ] ∑ . Ta sẽ 
 ( ) 
chỉ ra rằng , - theo phép quy 
nạp. Chú ý rằng kẻ tấn công đƣa ra truy vấn xác . 
thực phải khác những câu trả lời mà bộ tiên tri 
MAC đã đƣa ra trƣớc đó. = 
 ̅̅̅̅̅
 Trong trƣờng hợp . Nếu chọn truy vấn * ( ( )) | + 
xác thực trong đó với 
 * ( ( )) { }+ 
 nào đó thì có hai trƣờng hợp: 
 hoặc nhƣng 
 ( ) 
⌊ ( )⌋ ⌊ ( )⌋ . Trƣờng hợp đầu 
đồng nghĩa rằng tìm đƣợc một va chạm, tuy . ■ 
nhiên xác suất thành công không vƣợt quá . 
Trong khi trƣờng hợp thứ hai xảy ra với xác suất Áp dụng Mệnh đề 2 và Mệnh đề 3, chúng tôi 
không quá . Nếu chọn truy vấn xác thực đƣa ra hệ quả sau: 
 với với mọi , gọi Hệ quả 1. Lợi thế giả mạo lên LightMAC của 
 là số các phần tử các nhãn khác nhau thì một kẻ tấn công bất kỳ chạy trong thời gian thực 
ta có: 
 hiện tối đa truy vấn MAC và truy vấn 
 xác thực với độ dài thông điệp tối đa là 
 bit, không vượt quá 
 [ ( ) | ̅̅ ̅̅ ̅ 
 ] 
 ( ⁄ ⁄ ) 
 ⁄ ⁄ . 
 { }
 Do đó , -. 
 Giả sử đã chứng minh đến trƣờng hợp , 
 ( ) 
ta sẽ chứng minh rằng , -. Nếu 
 trong đó là kích cỡ khối, 
 chọn truy vấn xác thực ( ) trong đó 
 ( ) và 
 với nào đó. Tƣơng tự nhƣ 
 ( ). 
trƣờng hợp , xác suất để thành công không 
 Chú ý. Trong trƣờng hợp ta luôn có 
vƣợt quá , -. Nếu chọn truy vấn 
 , do đó để thu đƣợc kết quả 
xác thực ( ) với với mọi 
 nhƣ trong Định lý 1 ta cần phải đảm bảo điều kiện 
 . Ta xét hai trƣờng hợp con. Trƣờng hợp con 
thứ nhất, với thì không gian 
của . Khi đó 
 ̅̅̅̅̅ ⁄ 
 [ | ] Điều này có nghĩa số lƣợng truy vấn lên 
 ⁄ . Trƣờng hợp con thứ hai, ( ⁄ )
 bộ tiên tri Mac không đƣợc vƣợt quá . 
 với , khi đó ta chỉ cần đánh giá xác 
 Tuy nhiên, việc đánh giá nhƣ Định lý 1 là không 
suất thành công của khi đƣa ra nhãn 
 cần thiết bởi vì nó sẽ làm mất đi ý nghĩa của cận 
(nếu ngƣợc lại thì sẽ giống với trƣờng hợp ). 
Giả sử rằng, đã thực hiện truy vấn xác thực có an toàn LightMAC trong trƣờng hợp . 
 Số 1.CS (07) 2018 63 
Journal of Science and Technology on Information Security 
 Thực tế độ an toàn của mã xác thực SƠ LƢỢC VỀ TÁC GIẢ 
LightMAC vẫn phụ thuộc vào độ dài thông điệp vì 
khi đánh giá va chạm của hàm vẫn xuất hiện CN. Nguyễn Tuấn Anh 
biến độ dài theo khối . Tuy nhiên, trong cận an Email: tuananhnghixuan@gmail.com 
toàn của LightMAC có thể biểu diễn thông qua 
 Quá trình đào tạo: Nhận bằng cử 
giá trị khoảng , trong khi đối với các mã xác nhân chuyên ngành Toán tài năng 
 tại Đại học Khoa học tự nhiên, Đại 
thực thông điệp trƣớc đó là . Hơn nữa, 
 học Quốc gia Hà Nội năm 2016. 
LightMAC sử dụng điều kiện số khối của thông Hƣớng nghiên cứu hiện nay: Mã 
điệp không vƣợt quá và để làm mất hóa đối xứng. 
đi sự phụ thuộc này. Khi đó, cận an toàn của 
LightMAC sẽ là với ( ), ở 
 ⁄ 
đây ta xét với số truy vấn xác thực . Đối 
với các mã xác thực nhƣ CBC MAC, XOR MAC 
và PMAC, nếu ta cũng đặt giả thiết rằng số khối 
của thông điệp không vƣợt quá một hàm nào 
đấy, khi đó cận an toàn của những mã xác thực 
này cũng không có biến độ dài thông điệp: 
 . Tuy nhiên, điều này không có ý nghĩa 
vì là một số tƣơng đối lớn và cũng 
tƣợng trƣng cho độ dài thông điệp. 
 V. KẾT LUẬN 
 Trong bài báo này, chúng tôi đã đánh giá lại 
cận an toàn cho mã xác thực LightMAC. Sau đó, 
chúng tôi so sánh sự phụ thuộc vào độ dài của 
LightMAC với các mã xác thực khác. Tuy nhiên, 
độ an toàn của LightMAC trong trƣờng hợp sử 
dụng một khóa duy nhất (ví dụ nhƣ sử dụng một 
khóa để dẫn xuất ra hai khóa và ) vẫn là 
câu hỏi mở cần phải nghiên cứu trong thời gian 
tiếp theo. 
 TÀI LIỆU THAM KHẢO 
[1]. Luykx, A., et al. "A MAC mode for lightweight 
 block ciphers". in International Conference on 
 Fast Software Encryption, Springer, 2016. 
[2]. Dodis, Y. and K. Pietrzak. "Improving the 
 security of MACs via randomized message 
 preprocessing". in International Workshop on 
 Fast Software Encryption, Springer, 2007. 
[3]. Bellare, M., K. Pietrzak, and P. Rogaway. 
 "Improved security analyses for CBC MACs". 
 in Annual International Cryptology Conference, 
 Springer 2005. 
[4]. Bellare, M. and P. Rogaway, "Introduction to 
 modern cryptography". Ucsd Cse p. 207, 2005. 
[5]. Katz, J. and Y. Lindell, "Introduction to 
 modern cryptography". CRC press, 2014. 
64 Số 1.CS (07) 2018