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 http://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

Cách nhận biết và phòng tránh lừa đảo phát tán SMS Brandname giả mạo

09:00 | 18/07/2024

Mới đây, Bộ Công an đã thông tin về tình trạng tin nhắn tin nhắn thương hiệu (SMS Brandname) giả mạo phần lớn xuất phát từ việc các đối tượng sử dụng trạm phát sóng BTS giả mạo để gửi hàng loạt tin nhắn lừa đảo tới người dùng với mục đích nhằm chiếm đoạt tài sản.

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

07:00 | 08/04/2024

Thiết bị truyền dữ liệu một chiều Datadiode có ý nghĩa quan trọng trong việc bảo đảm an toàn thông tin (ATTT) cho việc kết nối liên thông giữa các vùng mạng với nhau, đặc biệt giữa vùng mạng riêng, nội bộ với các vùng mạng bên ngoài kém an toàn hơn. Khi chủ trương xây dựng Chính phủ điện tử, Chính phủ số của Quân đội được quan tâm, đẩy mạnh phát triển. Việc liên thông các mạng với nhau, giữa mạng trong và mạng ngoài, giữa mạng truyền số liệu quân sự (TSLQS) và mạng Internet, giữa các hệ thống thông tin quân sự và cơ sở dữ liệu (CSDL) quốc gia về dân cư, bảo hiểm y tế và các CSDL dùng chung khác yêu cầu phải kết nối. Bài báo sẽ trình bày giải pháp truyền dữ liệu một chiều Datadiode cho phép các ứng dụng giữa hai vùng mạng kết nối sử dụng giao thức Webservice/RestAPI.

Tăng cường bảo mật tệp lưu trữ trên Google Drive

10:00 | 28/03/2024

Google Drive là một trong những nền tảng lưu trữ đám mây được sử dụng nhiều nhất hiện nay, cùng với một số dịch vụ khác như Microsoft OneDrive và Dropbox. Tuy nhiên, chính sự phổ biến này là mục tiêu để những kẻ tấn công tìm cách khai thác bởi mục tiêu ảnh hưởng lớn đến nhiều đối tượng. Bài báo này sẽ cung cấp những giải pháp cần thiết nhằm tăng cường bảo mật khi lưu trữ tệp trên Google Drive để bảo vệ an toàn dữ liệu của người dùng trước các mối đe dọa truy cập trái phép và những rủi ro tiềm ẩn khác.

Vai trò quan trọng của sự ngẫu nhiên thực trong Blockchain và Web3

10:00 | 22/03/2024

Với sự tương tác kinh tế, xã hội và văn hóa ngày càng diễn ra phổ biến trên Internet, nhu cầu ngày càng tăng trong vài thập kỷ qua nhằm bắt chước sự ngẫu nhiên của thế giới tự nhiên và tạo ra các hệ thống kỹ thuật số để tạo ra các kết quả không thể đoán trước. Các trường hợp sử dụng cho tính không thể đoán trước này bao gồm đưa vào sự khan hiếm nhân tạo, xây dựng các cơ chế bảo mật mạnh mẽ hơn và tạo điều kiện cho các quy trình ra quyết định trung lập đáng tin cậy. Trong bài viết này, tác giả sẽ phân tích tính ngẫu nhiên, tìm hiểu về các loại ngẫu nhiên và vai trò quan trọng của sự ngẫu nhiên đối với Blockchain và hệ sinh thái Web3.

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

Cách phát hiện và ngăn chặn các chương trình Keylogger

Keylogger là phần cứng hoặc phần mềm có khả năng theo dõi tất cả các hoạt động thao tác nhập bàn phím, trong đó có các thông tin nhạy cảm như tên người dùng, mật khẩu thẻ tín dụng, thẻ ngân hàng, tài khoản mạng xã hội hay các thông tin cá nhân khác. Keylogger thậm chí có thể ghi lại các hành động gõ phím từ bàn phím ảo, bao gồm các phím số và ký tự đặc biệt. Bài báo sẽ hướng dẫn độc giả cách thức phát hiện và một số biện pháp kiểm tra, ngăn chặn các chương trình Keylogger nhằm bảo vệ máy tính trước mối đe dọa nguy hiểm này.

14:00 | 11/09/2024
INFOGRAPHIC: Mẹo bảo vệ dữ liệu cá nhân trên Tiktok
INFOGRAPHIC: Cuộc hành trình của Zero Trust
Những thách thức và giải pháp an toàn trong lĩnh vực thương mại điện tử hiện nay

GP ATM

Nhận diện và phòng tránh thủ đoạn sử dụng công nghệ deepfake

Cùng với sự phát triển của công nghệ, tội phạm mạng đang gia tăng thủ đoạn sử dụng video, hình ảnh ghép mặt người quen cùng với giọng nói đã được ghi âm sẵn (deepfake) với mục đích tạo niềm tin, khiến nạn nhân tin tưởng và chuyển tiền cho thủ phạm nhằm lừa đảo chiếm đoạt tài sản. Bài báo sau đây sẽ thông tin đến độc giả về cách nhận biết và đưa ra những biện pháp phòng tránh và giảm thiểu trước các cuộc tấn công lừa đảo sử dụng công nghệ Deepfake.

16:00 | 13/09/2024
Giải pháp di động hóa ứng dụng sử dụng trong mạng chuyên dùng có yếu tố bảo mật
Nhận diện về hoạt động của một số mạng botnet, APT, mã độc tại Việt Nam
INFOGRAPHIC: 6 cách bảo mật thông tin cá nhân trực tuyến