Một số sai lầm trong nghiên cứu ma trận MDS

22:58 | 19/05/2015 | GP MẬT MÃ

Mã tách tuyến tính có khoảng cách cực đại (mã MDS) đã được nghiên cứu từ lâu trong lý thuyết mã sửa sai, nhưng gần đây khi mật mã hiện đại phát triển mạnh mẽ, thì việc nghiên cứu MDS để áp dụng vào mật mã đã phát triển rất nhanh chóng. Tuy nhiên, nhiều sai sót vẫn tồn tại, và rất may là chúng đã sớm được phát hiện.

1. MA TRẬN MDS

Mã MDS đã được nghiên cứu từ lâu trong lý thuyết mã sửa sai. Nếu C là mã tuyến tính với tham số [n,k,d], trong đó n là độ dài từ mã, k là độ dài bản rõ cần mã và d là khoảng cách của mã C thì người ta thấy rằng các tham số này sẽ thỏa mãn bất đẳng thức d <= k+1. Đó là giới hạn Singleton. Mã MDS là mã tuyến tính [n,k,d], trong đó d = n-k+1 nghĩa là nó tối ưu về khoảng cách mã. Mã MDS là trường hợp đặc biệt của mã Reed-Solomon.

Gắn với mã C là ma trận sinh G. Đó là ma trận có k hàng, n cột, có hạng k (k n) và khi cần mã một thông báo có độ dài k thì người ta thực hiện phép nhân véc tơ a với G như sau để được từ mã c có độ dài n: c = aG. Luôn luôn có thể đưa G về dạng G = [I | A], trong đó I là ma trận đơn vị bậc k, A là ma trận k hàng, n-k cột. Nếu C là mã MDS thì A được gọi là ma trận MDS.

Ma trận MDS được sử dụng trong tầng khuếch tán của nhiều mã khối như AES, SHARK, Square, Twofish, Anubis, KHAZAD, Manta, Hierocrypt, Camellia, trong mã dòng MUGI và hàm hash mật mã WHIRLPOOL. Đối với mã khối, độ an toàn chống lại các tấn công mạnh (như tấn công tuyến tính, tấn công lượng sai) phụ thuộc vào số nhánh của tầng khuếch tán. Số nhánh càng lớn thì độ an toàn càng cao. Điều đáng nói ở đây là, số nhánh của tầng khếch tán <= m+1, trong đó m là số đầu vào của tầng khuếch tán. Số nhánh này đạt giá trị lớn nhất nếu ma trận MDS được dùng trong tầng khuếch tán. Điều đặc biệt là, nếu số nhánh tuyến tính đạt giá trị lớn nhất thì số nhánh lượng sai cũng đồng thời đạt giá trị lớn nhất.

Do hữu ích như vậy nên ngoài cách xây dựng ma trận MDS từ mã MDS, ngày càng xuất hiện nhiều phương pháp khác được nghiên cứu để tạo ra chúng. Người ta chứng minh được rằng, ma trận A là ma trận MDS nếu và chỉ nếu mọi ma trận con, vuông của A đều không suy biến (tức là có định thức khác 0). Việc áp dụng tiêu chuẩn này cho phép nghiên cứu trực tiếp ma trận và tránh sử dụng mã MDS nhưng nếu áp dụng trực tiếp thì khá phức tạp, bởi lẽ số ma trận con của một ma trận là khá lớn. Chẳng hạn, nếu A là ma trận vuông cấp 4 thì số ma trận con vuông của nó là:

Trong nhiều nghiên cứu về ma trận MDS, đã có một số sai lầm và chúng được phát hiện nhờ tính chất nói trên. Phần sau chúng ta sẽ đề cập đến chúng.

2. MỘT SỐ SAI LẦM TRONG NGHIÊN CỨU MA TRẬN MDS

Trường hợp thứ nhất.

Trong [1], các tác giả đưa ra ma trận

và cho rằng đó là ma trận MDS. Tuy nhiên, ma trận con cấp 2 của nó:

được tạo từ các phần tử thứ 2 và thứ 4 trên dòng 1 và trên dòng 3 của ma trận ban đầu là suy biến. Vì vậy ma trận cấp 4 nói trên không là ma trận MDS.

Trường hợp thứ hai.

Trong [2], các tác giả đưa ra khái niệm ma trận mũ trực tiếp như sau:

Định nghĩa. Cho F là trường Galois. Đối với ma trận cho trước A = [aij]mxn, aij thuộc F, ta xác định

nó được gọi là ma trận mũ trực tiếp bậc e của A. Ma trận này còn được gọi là ma trận bình phương trực tiếp của A.

Sau đó, các tác giả đưa ra kết quả:

Mệnh đề. Cho F là trường Galois. Nếu:

là ma trận MDS thì A(2) cũng là ma trận MDS.

Tuy nhiên, trong [3] các tác giả đã chứng tỏ rằng mệnh đề trên là không chính xác. Để cụ thể, họ giả sử

Một mặt, họ chỉ ra rằng lập luận trong chứng minh của [2] có 2 điều không đúng.

Thứ nhất, trong [2] suy luận rằng hai dòng của ma trận S’ (có 2 dòng, 2 cột) không tỷ lệ nên nó là ma trận không suy biến. Rõ ràng suy luận này không chính xác, người ta có thể chỉ ra những ma trận cấp 2 suy biến nhưng hai hàng của nó không tỷ lệ nhau (có trong ví dụ ở dưới đây).

Thứ hai, đối với số k nào đó thuộc F, các tác giả nói rằng có thể đặt k = (k’)^2 với k’ thuộc F. Thật ra, nếu k F là thặng dư bậc hai thì tồn tại k’ như vậy. Ngược lại, sẽ không tồn tại k’ thỏa mãn k = (k’)^2 với mọi k’ thuộc F.

Mặt khác, họ đưa ra phản ví dụ để bác bỏ mệnh đề nêu trên bằng chính ma trận MDS trong AES:

Xét ma trận bình phương trực tiếp A^(2) của A. Dựa trên bảng nhân trong [4] đối với trường Galois

ta nhận được

Vì ma trận con của A^(2) ở góc trên bên trái có định thức bằng 0:

nên A^(2) không là ma trận MDS. Như vậy, tác giả của [3] kết luận rằng mệnh đề của [2] không đúng với p = 2.

Giả sử p > 2. Xét ma trận vuông bậc 3 trên GF(7):

Ta tính tất cả 19 định thức cả các ma trận con vuông bậc 1, 2 và 3 của nó và kiểm tra thấy rằng tất cả chúng đều khác 0 theo mô đun 7:

Nghĩa là, A là ma trận MDS. Mặt khác, với ma trận bình phương trực tiếp A^(2) của nó:

ta thấy rằng ma trận con

của A(2) là kỳ dị (suy biến) vì giá trị det = 0, nghĩa là ma trận A^(2) không là MDS.

Phản ví dụ này chứng tỏ rằng mệnh đề nói trên của [2] nói chung không đúng đối với p > 2.

Trường hợp thứ ba.

Trong năm 2009, [5] đã đề xuất một ma trận cỡ 16x16 trên

bằng cách sử dụng ma trận Cauchy. Họ khẳng định ma trận của họ là MDS và đối hợp (involutory). Tuy nhiên trong [6] các tác giả đã chứng minh rằng ma trận đó không phải là MDS.

Trường hợp thứ tư.

Phản ví dụ trong trường hợp thứ hai có chỗ không chính xác. Đó là trường hợp ma trận MDS của AES:

Nếu áp dụng công thức do [3] dẫn ra

thì bản thân ma trận A cũng không phải là ma trận MDS, bởi ma trận con B cấp 2 ở góc trên bên trái của nó:

sẽ có định thức bằng 0, tức là suy biến. Sơ suất của [3] là ở chỗ xét việc tính toán ma trận A và ma trận bình phương trực tiếp của nó trên hai trường Galois khác nhau có cùng các phần tử.

Như vậy, đối với trường hợp GF(2^n), tính đúng đắn của mệnh đề nói trên cần được tiếp tục nghiên cứu sâu hơn.

3. KẾT LUẬN

Ma trận MDS đóng vai trò quan trọng trong mật mã, nhưng việc nghiên cứu thành công trong lĩnh vực này thật không dễ dàng. Tuy nhiên, ma trận MDS vẫn đang được tiến hành nghiên cứu mạnh mẽ. Điều đáng chú ý là, tuy những sai lầm là khó tránh khỏi nhưng chúng đã phát hiện sớm điều đó rất có ích đối với các ứng dụng mật mã.

TÀI LIỆU THAM KHẢO

[1]. Fatma Ahmed and Dalia Elkamchouchi, Strongest AES with S-Boxes Bank and Dynamic Key MDS Matrix (SDK-AES),International Journal of Computer and Communication Engineering, Vol. 2, No. 4, July 2013.

[2]. Murtaza G, Ikram N. Direct Exponent and Scalar Multiplication Classes of an MDS Matrix [EB/OL], (2011-01-10) [2011-04-15]. Cryptology ePrint Archive: Listing for 2011 , Available at //eprint. iacr.orgl201 l/ 15 1.pdf.

[3]. Yang Jun, Mazhi-xia, YangJie, Cheng Jiang, On direct exponentiation of maximum distance separable matrices, Journal of Southwest University for Nationalities. Natural Science Edition, May 2011, 1003-2843(2011)03-0452-04

[4]. LIDL R, NIEDERREITER H. Finite Fields[M]. Addison-Wesley Publishing Company, 1983: 541-546.

[5]. Jorge Nakahara Jr and Elcio Abrah˜ao, A New Involutory MDS Matrix for the AES, International Journal of Network Security, Vol.9, No.2, PP.109–116, Sept. 2009

[6]. Kishan Chand Gupta and Indranil Ghosh Ray, On Constructions of Involutory MDS Matrices, Africacrypt 2013, LNCS 7918, pp. 43-60, 2013, Springer-Verlag Berlin Heidelberg

‹ › ×

Tin liên quan

Xây dựng các ma trận MDS từ mã Gabidulin

13:00 | 17/02/2021

Ma trận MDS là một thành tố quan trọng trong việc xây dựng, thiết kế các mã khối an toàn. Bài báo này giới thiệu về mã Gabidulin (một mã tuyến tính trong lý thuyết mã) và cách xây dựng các mã MDS từ mã Gabidulin.

Xây dựng các ma trận MDS cặp đôi từ mã Reed-Solomon

15:00 | 24/09/2021

Bài báo này giới thiệu về MDS cặp đôi - một ma trận có dạng đối xứng đặc biệt và phương pháp xây dựng các ma trận này nhờ một mã cyclic nổi tiếng, đó là mã Reed-Solomon. Những ma trận dạng này có thể hữu ích trong việc nâng cao tốc độ xử lý hoặc hiệu quả trong thiết kế phần cứng.

SDK-AES: Thuật toán mã khối động ở cả tầng thay thế và khuếch tán

15:00 | 26/08/2019

Trong những năm gần đây, lĩnh vực mã khối động đã được nhiều nhà mật mã quan tâm nghiên cứu nhờ khả năng nâng cao độ an toàn của mã khối, chống lại nhiều loại thám mã khác nhau. Các mã khối có thể được “động hóa” ở một trong những thành phần của nó. Bài viết này giới thiệu thuật toán mã khối động SDK-AES có hai thành phần quan trọng được làm động, là tầng thay thế và tầng khuếch tán.

Tin cùng chuyên mục

Thực trạng và giải pháp trong bảo mật ứng dụng web

13:00 | 29/12/2023

Hiện nay, số lượng các vụ tấn công mạng trên ứng dụng web đang có xu hướng ngày càng gia tăng cả về quy mô lẫn mức độ tinh vi, với mục tiêu nhắm vào các dịch vụ cơ sở trọng yếu, khối tài chính, ngân hàng và các tổ chức/doanh nghiệp (TC/DN) lớn. Hậu quả của các cuộc tấn công này có thể là giả mạo giao dịch, gián đoạn hoạt động kinh doanh hay vi phạm dữ liệu, dẫn đến nguy cơ rò rỉ thông tin và mất mát dữ liệu quan trọng. Điều này gây ra nhiều thiệt hại đáng kể về tài chính cũng như uy tín của các TC/ DN. Bài báo sẽ trình bày thực trạng về bảo mật ứng dụng web năm 2023 dựa trên báo cáo của công ty an ninh mạng OPSWAT, cùng các giải pháp phòng tránh mối đe dọa tấn công mạng này.

Học sâu và ứng dụng phương pháp học sâu có đảm bảo tính riêng tư?

17:00 | 18/12/2023

Ngày nay, Trí tuệ nhân tạo (AI) hiện diện trong mọi lĩnh vực của đời sống con người, từ kinh tế, giáo dục, y khoa cho đến những công việc nhà, giải trí hay thậm chí là trong quân sự. Học máy là một ứng dụng của trí tuệ nhân tạo cung cấp cho các hệ thống khả năng tự động học hỏi và cải thiện từ kinh nghiệm mà không cần lập trình rõ ràng. Học máy tập trung vào việc phát triển các chương trình máy tính có thể truy cập dữ liệu và sử dụng nó để tự học. Do đó, vấn đề đảm bảo tính riêng tư trong ứng dụng phương pháp học sâu đang là một vấn đề được quan tâm hiện nay.

Google Chrome tự động nâng cấp để kết nối an toàn cho tất cả người dùng

10:00 | 10/11/2023

Google đã thực hiện một bước quan trọng nhằm tăng cường bảo mật Internet của Chrome bằng cách tự động nâng cấp các yêu cầu HTTP không an toàn lên các kết nối HTTPS cho toàn bộ người dùng.

Đánh giá một số công cụ lẩn tránh antivirus

10:00 | 15/02/2023

Phần mềm diệt virus (antivirus) là một trong những giải pháp bảo mật được sử dụng phổ biến, nhằm ngăn chặn tin tặc xâm nhập vào hệ thống. Tuy nhiên, hiện nay tin tặc đã phát triển các kỹ thuật để qua mặt các giải pháp antivirus và giành quyền truy cập vào các hệ thống được bảo vệ. Những kỹ thuật này được sử dụng trong các công cụ lẩn tránh giải pháp antivirus sẵn có dưới dạng công cụ mã nguồn mở mà tin tặc có thể dễ dàng sở hữu và sử dụng để xâm nhập hệ thống máy tính có trang bị chương trình antivirus.

Tin được quan tâm

Bảo đảm an ninh thông tin cơ sở hạ tầng quan trọng của Hoa Kỳ

08:00 | 11/01/2024 | Chính sách - Chiến lược
Giải pháp phân loại tương tác giữa 2 người trong chuỗi ảnh rời rạc (Phần I)

09:00 | 10/01/2024 | Giải pháp khác

Giải pháp tăng cường an ninh mạng ở Italia

09:00 | 05/01/2024|Chính sách - Chiến lược
Cạnh tranh Mỹ - Trung về cáp quang biển toàn cầu (phần 1)

09:00 | 05/01/2024|An ninh – Quốc Phòng

CISA cung cấp dịch vụ an ninh mạng cho các tổ chức trọng yếu không thuộc Chính quyền

09:00 | 21/12/2023|CA Công cộng
5 lưu ý giúp tăng cường bảo mật công nghệ vận hành cho các doanh nghiệp sản xuất

14:00 | 14/08/2023|Giải pháp khác

Giải pháp khác

Về một ứng dụng của RO-PUF trong bảo vệ phần cứng FPGA

Cùng với sự phát triển của khoa học kỹ thuật có ngày càng nhiều những cuộc tấn công vào phần cứng và gây ra nhiều hậu quả nghiêm trọng. Nhiều giải pháp để bảo vệ phần cứng được đưa ra, trong đó, hàm không thể sao chép vật lý PUF (Physically Unclonable Functions) đang nổi lên như là một trong số những giải pháp bảo mật phần cứng rất triển vọng mạnh mẽ. RO-PUF (Ring Oscillator Physically Unclonable Function) là một kỹ thuật thiết kế PUF nội tại điển hình trong xác thực hay định danh chính xác thiết bị. Bài báo sẽ trình bày một mô hình ứng dụng RO-PUF và chứng minh tính năng xác thực của PUF trong bảo vệ phần cứng FPGA.

10:00 | 13/05/2024
Tăng cường bảo mật trên Window11
Kích hoạt tính năng bảo vệ trẻ em trên điện thoại thông minh sử dụng hệ điều hành Android
Những yếu tố quan trọng giúp khôi phục dữ liệu hiệu quả sau khi bị tấn công mã độc tống tiền

GP ATM

Nguy cơ gia tăng hình thức tấn công bằng mã độc không sử dụng tệp và một số biện pháp phòng chống

Mã độc không sử dụng tệp (fileless malware hay mã độc fileless) còn có tên gọi khác là “non-malware”, “memory-based malware”. Đây là mối đe dọa không xuất hiện ở một tệp cụ thể, mà thường nằm ở các đoạn mã được lưu trữ trên RAM, do vậy các phần mềm anti-virus hầu như không thể phát hiện được. Thay vào đó, kẻ tấn công sử dụng các kỹ thuật như tiêm lỗi vào bộ nhớ, lợi dụng các công cụ hệ thống tích hợp và sử dụng các ngôn ngữ kịch bản để thực hiện các hoạt động độc hại trực tiếp trong bộ nhớ của hệ thống. Bài báo tìm hiểu về hình thức tấn công bằng mã độc fileless và đề xuất một số giải pháp phòng chống mối đe dọa tinh vi này.

10:00 | 17/05/2024
Xu hướng về chia sẻ tệp an toàn trong năm 2024
CISA phát hành phiên bản mới của hệ thống phân tích mã độc Malware Next-Gen
Giải pháp Datadiode cho phép ứng dụng giữa hai vùng mạng kết nối sử dụng API