1. Trang Chủ
  2. An ninh - Bảo mật
  3. 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

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

Bài viết đưa ra một cận an toàn kháng va chạm chặt hơn cho lược đồ Hirose. Kết quả khi áp dụng với mã khối có độ dài khối 128 bit và độ dài khoá 256 bit, ví dụ như AES-256, đó là không có một kẻ tấn công bất kỳ nào thực hiện ít hơn 2126.73 truy vấn có thể tìm được một va chạm cho hàm nén Hirose với xác suất lớn hơn 1/2. Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 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 Trần Hồng Thái, Hoàng Đ

Thể loại Tài liệu miễn phí An ninh - Bảo mật

Số trang 8

Ngày tạo 12/29/2020 1:39:34 PM +00:00

Loại tệp PDF

Kích thước 0.82 M

Tên tệp

Tải Một cải tiến cận an toàn kháng va chạm cho lược đồ... (.pdf)

Xem mẫu

  1. Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 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 Trần Hồng Thái, Hoàng Đình Linh Tóm tắt— Trong số các hàm nén dựa trên for Hirose compression function with a mã khối, có 3 hàm nén độ dài khối kép nổi tiếng probability greater than 1/2. đạt được độ an toàn kháng va chạm và kháng Từ khóa: lược đồ Hirose, hàm nén độ dài tiền ảnh tối ưu (lần lượt lên đến 2n và 22n truy khối kép, mã pháp lý tưởng, độ an toàn kháng va vấn) đó là Abreast-DM, Tandem-DM và lược đồ chạm, độ an toàn kháng tiền ảnh. Hirose. Gần đây đã có một số lược đồ mới được Keywords: – Hirose scheme, double-block- đề xuất, tuy nhiên các chứng minh độ an toàn length compression function, ideal cipher, đều dựa trên các kết quả đã có đối với 3 lược đồ collision resistance, preimage resistance. trên. Trong đó, lược đồ Hirose đạt được cận an toàn kháng va chạm và kháng tiền ảnh tốt hơn 2 I. GIỚI THIỆU lược đồ còn lại. Ngoài ra nó còn hiệu quả hơn khi chỉ sử dụng một lược đồ khoá duy nhất cho 2 mã Các hàm băm mật mã nhận một thông báo khối cơ sở. Trong bài báo này, chúng tôi đưa ra đầu vào có độ dài bất kỳ và trả về một xâu bit một cận an toàn kháng va chạm chặt hơn cho đầu ra có độ dài cố định. Đã có nhiều cấu trúc lược đồ Hirose. Kết quả khi áp dụng với mã khối được sử dụng cho việc băm các thông báo có có độ dài khối 128 bit và độ dài khoá 256 bit, ví độ dài thay đổi mà trong đó lặp lại một hàm nén dụ như AES-256, đó là không có một kẻ tấn công có kích thước cố định, như là cấu trúc Merkle- bất kỳ nào thực hiện ít hơn 2126.73 truy vấn có thể Damgård, khung HAIFA, cấu trúc Sponge... tìm được một va chạm cho hàm nén Hirose với Hàm nén cơ sở có thể được xây dựng từ các xác suất lớn hơn 1/2. thành phần hỗn tạp hoặc dựa trên chính các Abstract— Among the compression functions nguyên thuỷ mật mã như mã khối. Gần đây các based on block ciphers, there are three well- cấu trúc hàm nén dựa trên mã khối thu hút được known double-block-length compression nhiều sự quan tâm, vì nhiều hàm băm chuyên functions that achieve collision and preimage dụng đã cho thấy các điểm yếu về độ an toàn. resistance security (up to 2n and 22n, respectively) Cách tiếp cận chung nhất là xây dựng một that are Abreast-DM, Tandem-DM and Hirose hàm nén 2n bit sang n bit sử dụng 1 phép gọi scheme. Recently, several new schemes have been mã khối n bit, được gọi là hàm nén độ dài khối proposed, but the security proofs are based on the results available for the three schemes above. đơn (single block length - SBL). Tuy nhiên, In particular, the Hirose Scheme that achieves một hàm nén như vậy có thể bị tổn thương impact resistance and preimage resistance is trước các tấn công va chạm vì có độ dài đầu better than the other two schemes. In addition, it ngắn. Ví dụ, ta có thể thực hiện thành công tấn is more efficient to use only a single key scheme công ngày sinh lên một hàm nén dựa trên AES- for 2 base block ciphers. In this paper, we give a 128 chỉ dùng xấp xỉ 264 truy vấn. Điều này đã more secure collision resistance for the Hirose thúc đẩy các nghiên cứu về các hàm nén độ dài scheme. The result when applied to block ciphers khối kép (double block length - DBL), là các with a 128-bit block length and a 256-bit key length, such as AES-256, is that no attacker hàm nén có đầu ra gấp đôi độ dài của mã khối make less than 2126.73 queries can find a collision cơ sở. Các hàm nén độ dài khối kép có thể chia Bài báo được nhận ngày 8/8/2019. Bài báo được nhận thành hai lớp: xét bởi phản biện thứ nhất vào ngày 05/9/2019 và được chấp nhận đăng vào ngày 16/9/2019. Bài báo được nhận xét bởi  Lớp thứ nhất là các hàm nén sử dụng mã phản biện thứ hai vào ngày 06/9/2019 và được chấp nhận khối cơ sở có kích cỡ khoá là n bit, tức là đăng vào ngày 12/10/2019. E : 0,1  0,1  0,1 , ký hiệu là lớp n n n Số 1.CS (09) 2019 29
  2. Journal of Science and Technology on Information Security DBLn . Một số hàm nén thuộc lớp 1 là Mô hình mã pháp lý tưởng. Với m, n MDC-2, MDC-4 [1], cấu trúc MJH [2, 3], nguyên dương, ký hiệu: lược đồ Parrallel-DM [4], lược đồ PBGV  E : 0,1m  0,1n  0,1n | K  0,1m ,  [5], lược đồ LOKI DBH [6], lược đồ của BC  m, n    . Mennink [7] và một cấu trúc đưa ra bởi  EK   là mét ho¸ n vÞtr ª n 0,1 n  Jetchev cùng đồng sự [8]. Trong đó chỉ có Trong mô hình mã pháp lý tưởng, một mã MJH và lược đồ của Mennink được chứng khối E được chọn ngẫu nhiên đều từ BC  m, n  . minh là đạt độ an toàn kháng va chạm tối ưu, tuy nhiên vẫn chưa đạt độ an toàn Cho phép 2 kiểu truy vấn EK  X  hoặc EK1 Y  kháng tiền ảnh tối ưu. với X , Y  0,1 , K  0,1 , X, Y và K lần n m  Lớp thứ hai là các hàm nén sử dụng mã khối cơ sở có kích cỡ khoá là 2n bit, tức là lượt được gọi là bản rõ, bản mã và khoá. Câu E :  0,1   0,1   0,1 , ký hiệu là lớp n n n trả lời của một truy vấn ngược EK1 Y  là X  0,1 thoả mãn EK  X   Y . Trong phạm n DBL2n . Một số hàm nén thuộc lớp thứ 2 như Tandem-DM [9] và Abreast-DM [9], vi bài báo này, chúng ta chỉ xét trường hợp lược đồ Hirose [10], hàm nén loại I của m  2n và đặt N  2n . Stam [11] và các thiết kế tổng quát của Hàm nén Abreast-DM và Tandem-DM đã Hirose [12] và Özen cùng Stam [13]. Tất cả được đề xuất tại EUROCRYPT ’92 bởi Xuejia các hàm nén trên đều cung cấp đảm bảo độ Lai và James L. Massey [9]. Các hàm nén này an toàn va chạm tối ưu (lên đến 2n truy sử dụng kết hợp 2 lược đồ hàm nén đơn vấn), các hàm nén Tandem-DM, Abreast- Davies-Meyer lần lượt như Hình 1 và Hình 2. DM và lược đồ Hirose còn được chứng Mô tả chi tiết của các lược đồ này lần lượt được minh thêm là kháng tiền ảnh tối ưu (lên đến đưa ra trong Định nghĩa 1 và Định nghĩa 2. 22 n truy vấn). Trong đó, lược đồ Hirose đạt được cận an toàn kháng va chạm và kháng tiền ảnh tốt nhất trong 3 lược đồ trên. Bài báo này đưa ra một cải tiến cận an toàn kháng va chạm chặt hơn cho lược đồ Hirose. Phần còn lại của bài báo có bố cục như sau: Mục II trình bày một số khái niệm cơ sở về mô hình mã pháp lý tưởng. Mục III nhắc lại một số cận an toàn đã được phân tích đối với hai lược đồ hàm nén Abreast-DM và Tandem-DM. Mục IV phân tích độ an toàn đối với hàm nén Hình 1. Hàm nén Abreast-DM, Hirose, trong đó chúng tôi đưa ra một cận an trong đó “◦” ký hiệu phép bù bit. toàn kháng va chạm chặt hơn cho lược đồ hàm Định nghĩa 1 (Definition 2, [14]). Cho nén Hirose. Cuối cùng là kết luận ở Mục V. : 0,1  0,1  0,1 là một hàm nén ADM 2n n 2n F II. MỘT SỐ KHÁI NIỆM CƠ SỞ thoả mãn Gi , Hi   F ADM Gi 1 , Hi 1 , Mi  trong Gi , H i , M i , Gi 1 , H i 1  0,1 . F ADM sử n Một mã khối là một hàm đó dụng E : 0,1  0,1  0,1 sao cho E  K ,  là một mã khối E có độ dài khoá 2n bit và độ dài m n n khối n bit như sau: một hoán vị trên 0,1 với mỗi K  0,1 . n m Chúng ta gọi m là độ dài khoá và n là độ dài Gi  Gi 1  EH i1 ||M i  Gi 1    khối của mã khối E. Thông thường ta viết  H i  H i 1  EM i ||Gi1  H i 1   EK  X  thay vì E K, X  với trong đó H là ký hiệu phép bù bit của H. K  0,1 , X  0,1 . Ký hiệu hàm EK1  là m n nghịch đảo của EK   . 30 Số 1.CS (09) 2019
  3. Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin trong đó C  0,1 \ 0n  là một hằng số. n Lợi thế kháng va chạm và kháng tiền ảnh. Gọi F : 0,1  0,1 là một hàm nén 3n 2n dựa trên một mã khối lý tưởng E  BC  2n, n  , và A là một kẻ tấn công thông tin-lý thuyết với bộ tiên tri truy cập đến E hoặc E 1 . Thí nghiệm ExpColl A Hình 2. Hàm nén Tandem-DM E  $  BC  2n, n  Định nghĩa 2 (Definition 16, [14]). Cho 1 A E , E cËp nhËt Q : 0,1  0,1  0,1 là một hàm nén TDM 2n n 2n F Nếu A  A, B sao cho thoả mãn Gi , Hi   F TDM Gi 1 , Hi 1 , Mi  trong A Q B và A Q B Gi , H i , M i , Gi 1 , H i 1  0,1 . F TDM sử n đó dụng thì trả về 1 một mã khối E có độ dài khoá 2n bit và độ dài khối n bit như sau: nếu không trả về 0 Wi  EHi1 ||M i  Gi 1  Hình 4a. Thí nghiệm tìm va chạm  Gi  Gi 1  EHi1 ||M i  Gi 1   Gi 1  Wi Khi đó ta thực hiện thí nghiệm ExpColl A như  mô tả trong Hình 4a, để định lượng độ an toàn  H i  H i 1  EM i ||Wi1  H i 1  kháng va chạm của F. Thí nghiệm sẽ lưu lại các Tại FSE’06, Hirose [10] đã đề xuất hàm truy vấn mà kẻ tấn công A thực hiện vào một nén độ dài khối kép F Hirose . Hàm nén được lịch sử truy vấn Q . Một bộ  X , K , Y  Q nếu minh hoạ trong Hình 3 và được mô tả chi tiết A hỏi EK  X  và thu được câu trả lời Y hoặc trong Định nghĩa 3. hỏi EK1 Y  và thu được câu trả lời X. Với A  0,1 , B  0,1 ký hiệu A Q B nếu tồn 3n 2n tại một cặp truy vấn  X1 , K1 , Y1  ,  X 2 , K 2 , Y2  Q sao cho A có tính toán F  A  B sử dụng cặp truy vấn trên. Khi đó lợi thế tìm va chạm của A được định nghĩa là AdvFColl  A   Pr ExpColl A  1 . Xác suất lấy trên mã khối E ngẫu nhiên. Hình 3. Hàm nén Hirose, C là một hằng số Với q  0 , chúng ta định nghĩa AdvFColl  q  là giá Định nghĩa 3 (Definition 15, [14]). Cho trị lớn nhất của AdvFColl  A  trên tất cả các kẻ tấn F Hirose : 0,1  0,1  0,1 là một hàm nén 2n n 2n công A thực hiện q truy vấn. Lợi thế tìm tiền ảnh của A được định thoả mãn Gi , Hi   F Hirose Gi 1 , Hi 1 , Mi  trong nghĩa tương tự sử dụng thí nghiệm ExpAPre được Gi , H i , M i , Gi 1 , H i 1  0,1 . F Hirose sử dụng n đó mô tả trong Hình 4b. Kẻ tấn công A chọn một một mã khối E có độ dài khoá 2n bit và độ dài giá trị ảnh mục tiêu B  0,1 trước khi thực 2n khối n bit như sau: hiện các truy vấn. Lợi thế tìm tiền ảnh của A Gi  Gi 1  EH i1 ||M i  Gi 1   được định nghĩa là   H i  Gi 1  C  EH i1 ||M i  Gi 1  C   AdvFPre  A   Pr Exp APre  1 . Số 1.CS (09) 2019 31
  4. Journal of Science and Technology on Information Security Thí nghiệm ExpAPre E  $  BC  2n, n  A chän B  0,1 2n E , E 1 A  B cËp nhËt Q Nếu A sao cho A Q B thì trả về 1 Hình 5. Hàm nén tuần hoàn nếu không trả về 0 Gi , Hi   F CYC  Z  , Z  Gi 1 , Hi 1 , Mi  Hình 4b. Thí nghiệm tìm tiền ảnh Định nghĩa 5 (Definition 7, [14]). Cho  Xác suất lấy trên mã khối E ngẫu nhiên. là một song ánh trên tập S trong đó Với q  0 , chúng ta định nghĩa AdvFPre  q  là giá S : 2  0,1 . Gọi ID là ánh xạ đồng nhất trên b trị lớn nhất của AdvFPre  A  trên tất cả các kẻ tấn S. Hàm  k được định nghĩa là  k :  o k 1 công A thực hiện q truy vấn. với k  0 và  0 : ID . Hai lược đồ Abreast-DM và Hirose nằm (i) Cố định một phần tử s  S . Bậc của s trong một lớp các hàm nén tổng quát có tên gọi được định nghĩa là s  min r 1  r  s   s  , là hàm nén độ dài khối kép tuầ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  s   s .   là một nhóm, N   . Gọi  ,* (ii) Nếu có một giá trị c  N* thoả mãn F CYC : 2  0,1  2 là một hàm nén thoả s% S : s% c , ta nói rằng thứ tự của ánh xạ b mãn Gi , Hi   F CYC Gi 1 , Hi 1 , Mi  trong đó  , được ký hiệu là  , bằng c, tức là   c . Nếu không tồn tại c như vậy thì , H , G , H  và M i  0,1 , b  0 . Cho b Gi 1 i 1 i i  : 0 . Chú ý rằng nếu   0 thì bậc của  E  BC ,  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 là các hoán vị trên 2  0,1 và  T ,  B là các b chọn từ S. hoán vị trên . Đặt Định nghĩa 6 (Definition 8, [14]). Cho Z :  Gi 1 , H i 1 , M i    0,1 . 2 b Khi đó F ,  ,  như được định nghĩa trong Định CYC X T , X B , K T , K B   0,1 b thoả mãn nghĩa 4. Nếu   2 thì F CYC được gọi là hàm nén độ dài khối kép tuần hoàn (CDBL) với độ X T , K T     Z  và X B , K B       Z   . 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ó: Gi  E T  M T  *  T  X T   K Hàm nén Abreast-DM:   H i  EK B  M  *   X    0,1 , b  n,  T  ID,  B  X   X ,   ID B B B n và trong đó tính toán đưa ra Gi thường được gọi   G, H , M    H , M , G  . Hàm nén Abreast-DM là hàng trên và tính toán H i được gọi là hàng có chu kỳ   c  6 . dưới. Hàm nén Hirose: Hàm nén F CYC được minh hoạ như trong   0,1 , b  n,  T   B  ID,   ID n và Hình 5.   Gi 1 , H i 1 , M i    Gi 1  c, H i 1 , M i  . Hàm nén Hirose có chu kỳ   2 . 32 Số 1.CS (09) 2019
  5. 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 : 0,1  0,1 là hàm nén dựa trên mã 3n 2n ra Abreast-DM và Tandem-DM đạt độ an toàn F ADM 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  2n . Khi đó Trong [15], Lee cùng đồng sự đã đưa ra cận  16 8q  2eq  4q an toàn kháng va chạm cho hàm nén Abreast- Pre AdvADM q   2  2   . DM là N N  N  2   N   N q 18q 2 Hệ quả 2 (Corollary 2, [16]). Ta có ADM  q   AdvColl  .  2n  6q   2n  6q 2 Pre Adv ADM  22n10   1 / 2  o 1 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 F : F ADM như trong Định nghĩa 1 và n, q là N  2n , q  N / 2, N   N  2q và một số nguyên các số tự nhiên với q  2n2.58 . Khi đó  thoả mãn 1    2q . Khi đó 2   q   18  n1  .  q   2 N  2eq  4q 4q q   . Coll Coll Adv AdvTDM    N  N N ADM 2  Từ đó, ta có kết quả sau: Một ví dụ cho Định lý 3 là với Hệ quả 1. Cho F : F như trong Định ADM n  128, q  2120.87 và   16 ta có nghĩa 1 và n, q là các số tự nhiên với q  2n 3.58 . Coll AdvTDM  2120.87   1 / 2 . Khi đó Định lý 4 (Theorem 2, [17]). Cho 1 ADM  q   AdvColl  o 1 N  2n , q  N 2 và   0 là một số nguyên. Thì 2  trong đó o 1  0 khi n   . 16 8q  2eq  4q Pre  0 AdvTDM q   2  2   . 2 N N  N  2 N  N  q  1 Chứng minh. Xét 18  n 1   suy ra Một ví dụ cho Định lý 4 là với 2  2 n  128, q  2245.99 và   q1/ 2 / 2 ta có 2n 1 q  2n 1log2 6  2n 3.58 . Áp dụng Định lý 1 6 Pre  0 AdvTDM  2245.99   0.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 bất kỳ thực hiện ít hơn 2n3.58 truy vấn đến bộ Một điều đáng chú ý đó là lược đồ Hirose 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  q   6q /  2n  6q  . Tuy nhiên, cận này 2 Pre AdvADM kháng va chạm và kháng tiền ảnh cao hơn hai trở nên vô nghĩa khi q  2n / 6 . Sau đó, lược đồ còn lại. Số 1.CS (09) 2019 33
  6. 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 F : F 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,1  0,1 là 3n 2n như trong Định nghĩa 6. Nếu  T   B thì a  1 nếu không a  2 . Khi đó với q  1 và 2q  N , một hàm nén dựa trên mã khối được mô tả như ta có Hình 3. Khi đó  q   q  q  1 /  N  q  . Coll 2 2aq 2 2q AdvHirose Adv Coll q   .  N  2q  N  2q F Chứng minh. Xét một kẻ tấn công A bất 2 Á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 1 sau: để tìm va chạm đối với hàm nén F Hirose . A sẽ lưu một lịch sử truy vấn Q= Qi i 1 , trong đó q Hệ quả 3. Cho F Hirose : 0,1  0,1 là một 3n 2n hàm nén dựa trên mã khối được mô tả như Qi   K i , X i , Yi  thoả mãn EKi  X i   Yi . Chú ý Hình 3. Khi đó rằng A không bao giờ thực hiện lặp lại 1 truy Coll Adv  q   2q /  N  2q  2 2  2q /  N  2q  . vấn mà hắn đã biết câu trả lời. Chúng ta xét một Hirose 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 đồ Hirose với   2,  T   B 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,1  0,1 là 3n 2n xác suất thành công của A  để đưa ra một va 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 Hirose . 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 AdvHirose  q   1/ 2  o 1 vào/đầu ra bất kỳ của hàm nén F Hirose 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ử L  L là một bộ 4 giá trị  K , X , Y , Y   0,1 5n Chứng minh. Trước tiên ta thấy rằng vế phải của Hệ quả 3 là một hàm đồng biến theo q trong đó K  0,1 , X  0,1 là đầu vào 3n bit 2n n với q  N / 2 . Xét của hàm nén thoả mãn K   H i 1 , M  và 2q 2 /  N  2q   2q /  N  2q   1 / 2 . 2 X  Gi 1 . Các giá trị n bit Y , Y  được cho bởi Đặt q /  2 N  q   t ta có phương trình bậc 2 Y  EK  X  và Y   EK  X  C  . 2t 2  2t  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  i  q . Nếu là truy vấn lên E, kẻ tấn 1  2 q 1  2 t . Trả lại biến  suy công sẽ thu được bộ 3  Ki , X i , Yi  trong đó 2 N  2q 2 ra: EKi  X i   Yi . Nếu là truy vấn lên E 1 , kẻ tấn  1  2  n  2.77 công vẫn thu được một bộ 3  Ki , X i , Yi  nhưng q  N    2 .  2 2  là EK1 Yi   X i . Trong mỗi trường hợp đó, giá i Áp dụng Hệ quả 3, suy ra điều phải chứng trị X i  Yi đượ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ử L   Ki , X i ,*,* hoặc L   Ki , X i  C ,*,* có 34 Số 1.CS (09) 2019
  7. 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à q  q  1 Hirose  A    AdvFColl . một giá trị tuỳ ý. Khi đó, chúng ta phân tích 2  N  q 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 xuôi Yi   EKi  X i  C  . Do hằng số C khác 0  q   q  q  1 /  N  q  . Coll 2 AdvHirose nên giá trị của Yi xuất hiện ngẫu nhiên đều và Hệ quả 5. Cho F Hirose : 0,1  0,1 là 3n 2n độc lập với Yi . Khi đó, đặt Li :  Ki , X i , Yi , Yi  và 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 va chạm trong danh sách. Cố định 2 số nguyên Coll AdvHirose  q   1/ 2  o 1 a, b với a  b , sao cho La   K a , X a , Ya , Ya  là trong đó o 1 tiến về 0 khi n tiến ra vô cùng. phần tử thứ a trong L và Lb   Kb , X b , Yb , Yb là Chứng minh. Trước tiên ta thấy rằng vế phải phần tử thứ b trong L . Ta nói rằng La và Lb va của Định lý 6 là một hàm đồng biến theo q với chạm nếu một va chạm của hàm nén xảy ra sử q  N . Xét dụng các kết quả truy vấn trong La và Lb . Sự q  q  1 /  N  q   1 / 2 . 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 (i) Ya  X a  Yb  X b và Ya  X a  Yb  X b qN   2  1  2n 1.27 . (ii) Ya  X a  Yb  X b  C và Áp dụng Định lý 6, suy ra điều phải chứng minh. Ya  X a  Yb  X b  C 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 Li . Do 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  q   2q /  N  2q  , cận này trở 2 rằng AdvHirose Pre nhất là nên vô nghĩa khi q  N / 2 . Sau đó, i 1 2 2  i  1   . Fleischmann cùng đồng sự [16] đã đưa ra một  N  q  N  q 2 2 j 1 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 : 0,1  0,1 là một hàm nén dựa Hirose 3n 2n F 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 danh sách L của A  ). Do đó, xác suất thành Pre AdvHirose  q   8q / N 2  8q / N  N  2 . công đối với q truy vấn là Đặc biệt, AdvHirose Pre  q  bị chặn trên bởi xấp q 2  i  1 q  q  1   . xỉ 16q / N 2 .  N  q  N  q 2 2 i 1 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 cho kẻ tấn công trước đó. tiệm cận đến độ an toàn tối ưu (  2n1.27 ). Vậy, xác suất để kẻ tấn công A  thành Hướng nghiên cứu tiếp theo: Có thể thấy cả 3 lược đồ Abreast-DM, Tandem-DM và Hirose công là: Số 1.CS (09) 2019 35
  8. 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. 2009. Springer. hàm nén trên trong mô hình mã pháp yếu (weak 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 transactions on fundamentals of electronics, [2]. Lee, J. and Stam, M. MJH: A faster alternative communications and computer sciences, 2011. to MDC-2. in Cryptographers’ Track at the 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 [18]. Fleischmann, E., et al., Weimar-DM: The based on blockcipher algorithms. in Security Technology, 1989. Proceedings. 1989 Most Secure Double Length Compression International Carnahan Conference on. 1989. Function. IEEE. SƠ LƯỢC VỀ TÁC GIẢ ThS. Trần Hồng Thái [6]. Brown, L., Pieprzyk, J., and Seberry, J. LOKI— 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ủ. E-mail: ththai@bcy.gov.vn. [7]. Mennink, B. Optimal collision security in 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 Email: hoangdinhlinh@bcy.gov.vn and Application of of Cryptographic 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 Hướng nghiên cứu hiện nay: Nghiên cứu, thiết kế, Encryption. 2006. Springer. đá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
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường