Luận văn Nghiên cứu và xây dựng các mô hình chứng thực dựa trên các bài toán khó của lý thuyết đồ thị

6 Chương 1. MỞ ĐẦU Ngày nay, cùng với sự phát triển mạnh mẽ của khoa học và công nghệ, đặc biệt là máy tính, người ta có khả năng giải quyết được nhiều bài toán rất phức tạp. Tuy nhiên, còn những vấn đề là “không giải được” cho dù kỹ thuật máy tính có phát triển và cũng có những vấn đề được xem là “quá phức tạp”, vượt mọi khả năng tính toán thực tế vì mất quá nhiều thời gian. Việc nghiên cứu về độ phức tạp của thuật toán đã cho phép chúng ta phân loại được các lớp bài toán theo từng mức độ phức tạp khác nhau, và chỉ ra ranh giới giữa các lớp bài toán giải được và những lớp bài toán không thể giải được trong thời gian đa thức. 1.1. Các lớp bài toán Khái niệm thuật toán mà chúng ta sử dụng cho đến nay có tính chất là, kết quả thực hiện mỗi phép toán được xác định duy nhất. Thuật toán với tính chất đó được gọi là thuật toán tất định (deterministic algorithm). Bên cạnh đó, có những thuật toán mà kết quả của nó không phải là một giá trị được xác định duy nhất mà là một tập hữu hạn các giá trị được gọi là thuật toán không tất định (nondeterministic algorithm), chẳng hạn như các thuật giải ngẫu nhiên, thuật giải heuristic… Dựa vào thuật toán tất định và không tất định, ta có các lớp bài toán sau: - Lớp P (Polynomial) bao gồm tất cả các bài toán giải được bằng thuật toán tất định trong thời gian đa thức. - Lớp NP (Non Derterministic Polynomial) bao gồm tất cả các bài toán có thể giải được bởi thuật toán không tất định trong thời gian đa thức. Rõ ràng thuật toán tất định là trường hợp đặc biệt của thuật toán không tất định, do đó lớp P là lớp con của lớp NP. Cho L1 và L2 là hai bài toán. Ta nói L1 dẫn về L2, ký hiệu L1 ∝ L2, nếu bất kỳ thuật toán tất định trong thời gian đa thức giải được L2 thì cũng có thể được dùng để giải L1. 7 Dễ thấy quan hệ “dẫn về” có tính bắc cầu, có nghĩa là nếu L1 ∝ L2 và L2 ∝ L3 thì L1 ∝ L3. - Một bài toán L là NP-Hard nếu với mọi bài toán L’ thuộc NP ta có L’ ∝ L. - Một bài toán L là NP-Complete nếu L thuộc NP và L là NP-Hard. Như vậy, một bài toán là NP-Complete có thể giải được trong thời gian đa thức nếu và chỉ nếu tất cả các bài toán NP-Complete khác giải được trong thời gian đa thức. Nếu một bài toán NP-Hard giải được trong thời gian đa thức thì tất cả các bài toán NP-Complete giải được trong thời gian đa thức. Người ta đã chỉ ra rằng, mọi bài toán NP-Complete đều là NP-Hard nhưng ngược lại, một bài toán NP-Hard không nhất thiết là NP-Complete. Tóm lại, ta có mối quan hệ giữa các lớp P, NP và P, NP, NP-Complete (NPC) như sau: Hình 1.1: Mối quan hệ giữa lớp P và NP Hình 1.2: Mối quan hệ giữa lớp P, NP và NPC NP P NP NP P 8 1.2. Các bài toán khó trong lý thuyết đồ thị Các lớp bài toán NP-Complete là rất rộng. Hầu hết các bài toán nổi tiếng mà chúng ta đã biết như bài toán người bán hàng, bài toán balô, các bài toán tổ hợp, phân tích ra thừa số… đều là các bài toán khó. Sau đây là một số bài toán khó thuộc lớp NP-Complete trong lý thuyết đồ thị: Bài toán phủ đỉnh (Vertex-Cover) Bài toán được phát biểu như sau: - Cho đồ thị G = (V, E) và số k ∈ *N sao cho k ≤ |V| - Hỏi tồn tại hay không một tập con V’ của V sao cho |V’| < k và mỗi cạnh {u, e} ∈ E thì một trong 2 đỉnh u hoặc e (hoặc cả đỉnh u và e ) phải thuộc V’. Định lý 1.1: Bài toán phủ đỉnh là bài toán NP-Complete [1], [12]. Bài toán đồ thị con đủ (Clique Problem) Bài toán được phát biểu như sau: - Cho đồ thị G = (V, E) và k ∈ *N thoả mãn k ≤ |V| - Hỏi tồn tại hay không một tập con V’ của V sao cho ⎜V’⎜≥ k mà mọi cặp đỉnh trong V’ đều được nối bởi 1 cạnh trong E. Định lý 1.2: Bài toán đồ thị con đủ là bài toán NP-Complete [12]. Bài toán đồ thị con đẳng cấu (Subgraph Isomorphism) - Cho hai đồ thị: G1 = (V1, E1) và G2 = (V2, E2). - Hỏi G1 có chứa đồ thị con G’ = (V’, E’) đẳng cấu với đồ thị G2, tức tồn tại tập con V’ ⊆ V, E’ ⊆ E thỏa |V’| = |V2|, |E’| = |E2| và một song ánh f : V2 → V’ sao cho ∀ (u, v) ∈ E2 khi và chỉ khi {f(u), f(v)} ∈ E’. Định lý 1.3: Bài toán đồ thị con đẳng cấu là bài toán NP-Complete [12]. Bài toán chu trình Hamilton (Hamilton Cycle) Chu trình Hamilton là chu trình sơ cấp đi qua tất cả các đỉnh của đồ thị (xem Định nghĩa 2.15 – tr28). Bài toán được phát biểu như sau: - Cho đồ thị G = (V, E) có chu trình Hamilton H. 9 - Tìm trong đồ thị G một chu trình Hamilton đúng bằng chu trình H đã cho. Định lý 1.4: Bài toán tìm một chu trình Hamilton cho trước là bài toán NP- Complete [12]. Bài toán người bán hàng (Traveling Salesman) Cho đồ thị G và 1 số k nguyên, mỗi cạnh e của G có một trọng số nguyên c(e). Vấn đề đặt ra là có tồn tại một chu trình đi qua tất cả các đỉnh của G (mỗi đỉnh đúng một lần) mà tổng trọng số các cạnh đã đi qua không vượt quá k? Ta phát biểu lại bài toán như sau: - Cho tập n thành phố C = {C1, C2, …, Cn} với khoảng cách d(Ci, Cj) ∈ Z+ và một số nguyên dương k - Hỏi có tồn tại một hoán vị π trên {1, 2, …, n} sao cho: ∑− = 1 1 n i d(Cπ(i), Cπ(i+1)) + d(Cπ(m), Cπ(1)) ≤ k hay không? Định lý 1.5: Bài toán người bán hàng là bài toán NP-Complete [1], [12]. 1.3. Các mô hình chứng thực lẫn nhau Chứng thực (Authentication) là một thủ tục có chức năng xác minh nhận dạng (identity) của một đối tượng trước khi trao quyền truy xuất cho đối tượng này một tài nguyên nào đó. Có hai phương thức chứng thực phổ biến: Chứng thực một chiều (one way authentication) và chứng thực hai chiều hay còn gọi là chứng thực lẫn nhau (mutual authentication). Chứng thực một chiều chỉ cung cấp cơ chế để một đối tượng (thường là máy chủ) kiểm tra nhận dạng của đối tượng kia (người dùng) mà không cung cấp cơ chế kiểm tra ngược lại, tức không cho phép người dùng kiểm tra nhận dạng của máy chủ. Do đó, người sử dụng không có khả năng nhận biết được đây là máy chủ thật hay giả mạo. Chứng thực hai chiều cho phép hai đối tượng trong giao tác chứng thực lẫn nhau, cho nên tính chính xác của quá trình chứng thực được đảm bảo. 10 Với những ưu điểm của phương thức chứng thực lẫn nhau mà hiện nay đã có một số mô hình chứng thực lẫn nhau đang được nghiên cứu và ứng dụng như mô hình dựa vào hệ mã, mô hình dựa vào đồ thị… 1.3.1. Mô hình dựa vào hệ mã Giao thức Kerberos Kerberos là một giao thức dùng để chứng thực trong các mạng máy tính hoạt động trên đường truyền không an toàn với mục đích chống lại việc nghe lén hay gửi lại các gói tin cũ và đảm bảo chứng thực lẫn nhau cho client và server. Kerberos sử dụng một bên thứ ba tham gia vào quá trình chứng thực gọi là "Trung tâm phân phối khóa" (Key Distribution Center - KDC). KDC bao gồm hai chức năng: "Máy chủ xác thực" (Authentication Server - AS) và "Máy chủ cung cấp thẻ" (Ticket Granting Server - TGS). "Thẻ" trong hệ thống Kerberos chính là các chứng thực chứng minh nhận dạng của người sử dụng. Mỗi người sử dụng (cả client và server) trong hệ thống chia sẻ một khóa chung với máy chủ Kerberos. Việc sở hữu thông tin về khóa chính là bằng chứng để chứng minh nhận dạng của một người sử dụng. Trong mỗi giao dịch giữa hai người sử dụng trong hệ thống, máy chủ Kerberos sẽ tạo ra một khóa phiên dùng cho phiên giao dịch đó. Có thể tóm lược thủ tục chứng thực của Kerberos như sau (Hình 1.3): 1- Người dùng đăng nhập vào máy con và yêu cầu AS cung cấp thẻ xác nhận người dùng (Ticket - granting - Ticket). 2- AS kiểm tra quyền truy cập của người dùng trong cơ sở dữ liệu, phát sinh và mã hóa thẻ xác nhận người dùng và khóa phiên bằng mật khẩu của người dùng, sau đó gửi cho máy con. 3- Máy con yêu cầu người dùng cung cấp mật khẩu và sử dụng mật khẩu làm khóa để giải mã thông điệp do AS gửi đến. Sau đó gửi yêu cầu truy xuất dịch vụ có chứa thông tin về tên người dùng, địa chỉ mạng, thời gian cho TGS. 4- TGS kiểm tra yêu cầu và cung cấp thẻ truy xuất dịch vụ (Service Granting Ticket) cho máy con. 11 5- Máy con gửi yêu cầu truy xuất dịch vụ cho máy chủ. 6- Máy chủ kiểm tra thẻ truy xuất dịch vụ, quyền truy cập của máy con và thực hiện chứng thực lẫn nhau với máy con (nếu có yêu cầu). Hình 1.3: Thủ tục chứng thực Kerberos Giao thức Kerberos đòi hỏi đồng hồ của tất cả những máy tính liên quan phải được đồng bộ. Nếu không đảm bảo điều này, cơ chế chứng thực sẽ không hoạt động. Thiết lập mặc định của giao thức Kerberos là sai lệch giữa các đồng hồ không quá 10 phút. Giao thức SSL (Secure Sockets Layer) Để tạo ra một liên kết giữa client và server, SSL sử dụng giao thức bắt tay (handshake protocol), đây là giao thức phức tạp nhất của SSL dùng để chứng thực lẫn nhau, thống nhất các thuật toán xác thực thông điệp (Message Authentication Code) và mã hóa. Giao thức này cũng được dùng để trao đổi các khóa bí mật dùng cho mã hóa, xác thực thông điệp và được thực hiện trước khi truyền dữ liệu. Giao thức bắt tay gồm 4 giai đoạn, được mô tả theo hình sau: Kerberos Máy chủ chứng thực (AS) Máy chủ cấp thẻ (TGS) Máy con (C) Cấp thẻ xác nhận người dùng Yêu cầu thẻ xác nhận người dùng Yêu cầu thẻ truy xuất dịch vụ Cấp thẻ truy xuất dịch vụ Máy chủ (S) Yêu cầu dịch vụ Cung cấp dịch vụ chứng thực 12 Hình 1.4: Thủ tục bắt tay SSL Client client_hello server_hello Chứng thực khóa server Khóa bí mật của server Yêu cầu cung cấp chứng thực Kết thúc server_hello Chứng thực khóa client Khóa bí mật của client Xác minh chứng thực khóa Thay đổi thông số mã Kết thúc Thay đổi thông số mã Kết thúc Giai đoạn 1: Thiết lập các thông số bảo mật như phiên bản của giao thức, nhận dạng phiên giao dịch, thuật toán mật mã, phương pháp nén và số ngẫu nhiên ban đầu Giai đoạn 2: Server có thể gửi chứng thực khóa, trao đổi khóa và yêu cầu client cung cấp chứng thực khóa Giai đoạn 3: Client gửi chứng thực khóa khi được yêu cầu từ phía server, trao đổi khóa với server. Client cũng có thể gửi xác minh chứng thực khóa công khai cho server (certificate verification) Giai đoạn 4: Thay đổi các thông số của thuật toán mật mã và kết thúc giao thức bắt tay. Server 13 1.3.2. Mô hình dựa vào đồ thị Trong những năm gần đây nhờ sự hỗ trợ của công nghệ thông tin và máy tính điện tử, đồ thị càng ngày càng trở thành công cụ hiệu quả, năng động giải quyết các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị có thể sử dụng để giải các bài toán tối ưu trên mạng, các bài toán về lập lịch, thời khóa biểu, phân bố tần số cho các trạm phát thanh, truyền hình cũng như xây dựng các hệ mã, thuật toán dựa trên đồ thị như mã dòng (stream ciphers), mã khối (block ciphers) [13] hay thuật toán chia sẽ khóa bí mật chung [10]. Bên cạnh việc phát triển các hệ mã, người ta cũng chú ý đến việc xây dựng các giao thức chứng thực dựa trên các bài toán thuộc lớp NP-Complete trong lý thuyết đồ thị và đã đạt được nhiều kết quả khả quan. Điển hình đó là giao thức chứng thực lẫn nhau dựa vào đồ thị đẳng cấu cho mạng không dây (WLAN) của nhóm tác giả Trần Ngọc Bảo và Nguyễn Đình Thúc [6]. Giao thức đề nghị ngoài việc đảm bảo an ninh cho mạng máy tính còn có khả năng chống được một số kiểu tấn công phổ biến, như tấn công lặp lại (replay attacks), tấn công người trung gian (man-in-the- middle attacks) và tấn công đánh cắp phiên làm việc (session hight-jacking). Hay dựa vào giao thức Woo-Lam (Woo-Lam protocol), nhóm tác giả XIE Hong-bo, WU Yuan-cheng, ZHOU Ming-tian đã đề xuất mô hình chứng thực lẫn nhau dựa trên đồ thị có hướng [16]… Ngoài ra, dựa vào nguyên tắc hoạt động của giao thức Tri thức trị không (zero- knowledge protocol) mà càng ngày có nhiều mô hình chứng thực được xây dựng dựa trên đồ thị, như đồ thị đẳng cấu (graph isomorphism) [7], [9]; đồ thị con đẳng cấu (subgraph isomorphism) [7]; tô màu đồ thị (graph colourability) [7]… Và như chúng ta biết, bài toán tìm một chu trình Hamilton cho trước trong một đồ thị là một bài toán khó thuộc lớp NP-Complete (Định lý 1.4). Tuy nhiên qua khảo sát cho thấy, việc ứng dụng bài toán trên vào quá trình xây dựng các mô hình chứng thực lẫn nhau vẫn chưa có nhiều công trình công bố mà chủ yếu mới dừng lại ở việc ứng dụng chu trình hamilton vào xây dựng các giao thức chứng thực dựa trên Tri thức trị không [9], hay kết hợp với hệ mã ma trận [5]. 14 1.4. Mục tiêu luận văn Như trên đã phân tích, không tồn tại một thuật toán tất định trong thời gian đa thức để giải một bài toán thuộc lớp NP-Complete. Do đó, việc tập trung đi sâu vào nghiên cứu, tìm hiểu các bài toán thuộc lớp NP-Complete, đặc biệt là các bài toán khó trong lý thuyết đồ thị có ý nghĩa rất lớn trong việc phát triển một số hệ mã cũng như xây dựng các mô hình chứng thực cho các hệ thống đòi hỏi phải có tính bảo mật cao. Dựa vào các yêu cầu trên, luận văn tập trung nghiên cứu những vấn đề sau: i) Tìm hiểu các mô hình chứng thực người dùng, trong đó tập trung vào các mô hình chứng thực lẫn nhau (mutual authentication). ii) Khảo sát, nghiên cứu một số bài toán khó trong lý thuyết đồ thị thuộc lớp NP-Complete, đặc biệt là bài toán chu trình Hamilton. iii) Trên cơ sở các mô hình nghiên cứu, luận văn xây dựng giao thức chứng thực dựa trên một bài toán khó trong lý thuyết đồ thị vừa đảm bảo tính đúng đắn, tính hiệu quả vừa có khả năng chống được các kiểu tấn công phổ biến, như tấn công lặp lại (replay attack), tấn công vét cạn (brute-force attack) và tấn công người trung gian (man-in-the-middle attack). iv) Xây dựng một chương trình ứng dụng nhằm thực nghiệm và đánh giá giao thức trên. 1.5. Bố cục luận văn Ngoài phần mục lục và danh mục các bảng, hình vẽ, tài liệu tham khảo, luận văn được bố cục thành 4 chương: Chương 1. Mở đầu Ở chương này, luận văn trình bày một cách khái quát về khái niệm độ phức tạp qua các lớp P, NP, NP-Complete. Trên cơ sở đó giới thiệu một số bài toán điển hình trong lý thuyết đồ thị thuộc lớp NP-Complete. Chương 2. Cơ sở toán học 15 Trình bày một số khái niệm cơ bản về lý thuyết số học, đại số ma trận và lý thuyết đồ thị có liên quan đến việc xây dựng giao thức chứng thực ở Chương 3. Chương 3. Ứng dụng đồ thị Hamilton vào chứng thực Trong chương này, luận văn sẽ trình bày giao thức chứng thực người dùng dựa trên chu trình Hamilton. Qua đó phân tích và đánh giá tính đúng đắn, tính khả thi về mặt lý thuyết của giao thức. Chương 4. Thực nghiệm và đánh giá Trên cơ sở những kết quả đạt được, luận văn sẽ tiến hành xây dựng hoàn chỉnh một ứng dụng chứng thực dựa vào phương pháp chia sẽ bí mật chung nhằm minh họa cho giao thức được đưa ra ở Chương 3. Qua đó tiến hành thực nghiệm để đánh giá mức độ hiệu quả về không gian, thời gian và tính an toàn của giao thức làm cơ sở cho việc đưa ra một số kiến nghị, đề xuất cũng như định hướng cho việc phát triển tiếp theo của luận văn trong thời gian tới.