Rắc Rối Hóa Chương Trình

Rắc rối hóa chương trình

-- © NQH (12/05/2005)

Trong bài về các chương trình đẹp xấu, vân vân, tôi có nhắc đến các chương trình C được rắc rối hóa (obfuscated C code) và cả một cuộc thi quốc tế hàng năm cho các chương trình này. Sau đây là một ví dụ:

#include <stdio.h> int O,o,i;char*I="";main(l){O&=l&1?*I:~*I,*I++||(l=2*getchar(),i+=O>8\?o:O?0:o+1,o=O>9,O=-1,I="t8B~pq`",l>0)?main(l/2):printf("%d\n",--i);}

Bạn thử bỏ vài phút nghĩ xem chương trình trên làm gì? Tôi chọn ví dụ này vì nó ngắn. Các ví dụ khác trông “ghê gớm” hơn nhiều: ví dụ 1, ví dụ 2, ví dụ 3.

Thế các chương trình loại này chỉ dùng để đố nhau cho vui, hay có ứng dụng gì khác?

Thử tưởng tượng ta tìm được một phương thức nào đó để viết một chương trình O làm công việc như sau: cho một chương trình P bất kỳ, O sẽ biến P thành chương trình O(P) với chức năng hệt như P, chỉ khác ở chỗ là đọc O(P) ta không thể hiểu được logic của nó, và vì thế ta không biết P thật sự chạy như thế nào. [Kể cả là đọc bằng máy tính hay đọc bằng mắt thường!]

Một chương trình O như vậy có rất nhiều ứng dụng trong mật mã hóa, đánh dấu mờ (watermark) phần mềm, bảo vệ phần mềm (software protection), vân vân.

Ví dụ tôi có một giải thuật tân kỳ nào đó và tôi muốn bán cho người khác để họ dùng giải thuật này trong một chương trình lớn. Tôi viết giải thuật này thành một đoạn mã gọi là P, sau đó tôi gửi O(P) cho người mua và họ có thể dùng O(P) trực tiếp mà tôi không bị tiết lộ giải thuật này. Nói chung, O có thể dùng để chống reverse-engineering. Đây là ứng dụng bảo vệ phần mềm của O.

Đánh dấu mờ phần mềm (wartermarking software) là một ứng dụng hay nếu ta có thể thực sự viết O. Ý nghĩa căn bản của cái gọi là “đánh dấu mờ” như sau:

• Giả dụ ta có một chương trình P đem bán cho khách hàng, nhưng muốn tránh việc khách hàng copy P cho người khác, ta tìm cách, với mỗi khách hàng G, trộn vào trong P một đoạn mã C(G) nào đó, biến P thành P(G).
• P(G) về mặt chức năng thì giống hệt P, và việc thêm C(G) vào P không ảnh hưởng nhiều đến hiệu suất của P.
• C(G) còn có một thuộc tính toán học nào đó mà ta có thể kiểm tra bằng cách kiểm tra P(G). Thuộc tính toán học này có thể dùng để chứng minh rằng P(G) thuộc về khách hàng G. Như vậy, hai khách hàng G1 và G2 khác nhau sẽ có hai chương trình P(G1) và P(G2) khác nhau [và ta kiểm tra được điều đó], dù là chúng giống hệt nhau về mặt chức năng.
• C(G) có thể xem như con dấu hay chữ ký của khách hàng G đã đóng vào P. Như thế G sẽ không đem bản của mình cho người khác được.
• Dĩ nhiên là cả hệ thống phải được thiết kế sao cho việc lấy C(G) ra khỏi P(G) là cực kỳ khó làm. Ngoài ra, bất kể người ta biến đổi P(G) như thế nào (rắc rối hóa nó, dịch nó sang ngôn ngữ khác, vân vân), thì “con dấu” C(G) vẫn bị dính kèm.

Những điều trên có khả năng hiện thực hóa được nếu ta có bộ rắc rối hóa O. Ta bỏ vào trong P một đoạn mã C(G) nào đó để nhận dạng khách hàng G. (C(G) không làm gì cả, chỉ dùng để nhận dạng G.) Sau đó ta đưa cho khách hàng chương trình O(P). Chương trình O(P) giống hệt P+C(G), nhưng đã bị rắc rối đến mức khách hàng không thể hiểu được logic của nó, và vì thế không thể bỏ C(G) ra khỏi nó được. Dĩ nhiên còn nhiều chi tiết kỹ thuật và lý thuyết cần dùng cho việc này, nhưng về mặt trực quan thì có khả năng điều này có thể hiện thực hóa được nếu ta có O.

Hệ thống mật mã khóa công cộng (public key crypto-system, hay PKC) là ý tưởng đột phá của ngành mật mã học (cryptography). Các PKC như RSA hiện nay đóng vai trò thiết yếu trong các hoạt động cần bảo mật máy tính như thương mại điện tử (e-commerce), chữ ký điện tử (digital signature), vân vân. Whitfield Diffie, Martin Hellman, và Ralph Merkle có thể được coi là cha đẻ của ý tưởng mật mã hóa không cần bí mật này, mặc dù tổ chức GCHQ của Anh nói rằng họ có ý tưởng này trước đó vài năm, nhưng không đăng báo vì là bí mật quốc gia.

Bài báo đầu tiên về đề tài này của Diffie và Hellman đăng năm 1976 (W. Diffie and M. Hellman. New Directions in Cryptography. IEEE Trans. Info. Theory 22(6): 644-654 (1976)). Tuy nhiên họ đã trình bày ý tưởng này ở một hội nghị vào tháng 6 năm 1975.

“Mật mã hóa không cần bí mật” nghe có vẻ nghịch lý. Chính vì thế mà ý tưởng PKC là một đột phá của thế kỷ 20 trong ngành mật mã học. Trước khi có ý tưởng PKC, để gửi hay lưu trữ một tài liệu mật nào đó, ta cần một khóa bí mật (secret key - còn gọi là khóa riêng - private key). Khi mật mã hóa tài liệu, ta dùng khóa bí mật. Khi giải mã tài liệu, ta cũng cần nó. Mức độ bảo mật của hệ thống bằng với mức độ bảo mật của khóa này, và trong chừng mực nào đó, mức độ bảo mật của giải thuật mã hóa và giải mã. Hiển nhiên là một giải thuật tốt thì có nhiều người cần dùng, và vì thế ta chỉ có thể giữ bí mật cái khóa riêng thôi, còn giải thuật thì không phải là bí mật.

Khó khăn của hệ thống mật mã khóa riêng (private key crypto-system) kiểu này nằm ở việc phân phối khóa riêng. Nếu một người ở Mỹ muốn gửi tài liệu bí mật cho người ở Việt Nam mà phải mang cái khóa này sang Việt Nam thì mang luôn cái tài liệu mật cho xong. Như vậy, ta cần một hệ thống mật mã mà trong đó người gửi có thể mã hóa và gửi tài liệu bằng cách nào đó mà chỉ có người nhận mới giải mã được, ngoài ra người gửi không cần biết một bí mật nào đó thì mới làm được việc này. Đây là lý do tại sao ta gọi PKC là hệ thống mật mã không cần bí mật.

Ý tưởng của một hệ thống PKC như sau. Người nhận có một cặp khóa D (bí mật) và E (công cộng). Người nhận cho thiên hạ biết khóa E. Để đơn giản, bạn có thể hiểu E như một hàm số hay một chương trình mà cho một thông điệp M thì E(M) là thông điệp M đã được mật mã hóa. Dĩ nhiên việc giải mã ra M từ E(M) là cực kỳ khó, trừ khi ta có D. Ta chỉ cần D(E(M)) = M với mọi M là xong. (Chú ý rằng cả E và D đều có thể xem như các chương trình máy tính. E là chương trình công cộng, còn D là chương trình bí mật.)

Vậy PKC thì liên quan gì đến rắc rối hóa chương trình?

Với bộ rắc rối hóa chương trình O, ta có thể biến một hệ thống mật mã khóa riêng thành hệ thống mật mã khóa công cộng. Hệ thống mật mã khóa riêng có thể được mô tả như sau: bên gửi và bên nhận dùng chung một khóa bí mật K cùng với một giải thuật mã hóa E và giải mã D. Gọi EK là chương trình mã hóa dùng E với khóa K, và DK là chương trình giải mã dùng D với khóa K. Để mã hóa một thông điệp M thì bên gửi sẽ gửi EK(M), và bên nhận giải mã với DK(EK(M)) = M.

Như ta đã nói trong các bài trước, việc làm thế nào để phân phối và đồng ý với khóa K là vấn đề khó giải quyết của hệ thống mật mã khóa riêng. Với bộ rắc rối hóa O, bên nhận có thể cho mọi người biết O(EK). Ai muốn gửi thông điệp M thì chỉ cần gửi O(EK)(M) là xong. Nhờ có O, không thể đoán được K từ O(EK).

Cho đến đây, ta vẫn chưa định nghĩa rõ ràng thế nào là một bộ rắc rối hóa chương trình bằng toán học. Bộ rắc rối hóa phải thỏa mãn những tính chất gì thì các ứng dụng nêu trên mới có thể thành hiện thực được? Tệ hơn nữa, nhỡ khi không tồn tại một bộ rắc rối hóa như ta mong muốn thì sao? Làm sao chứng minh được điều này?

Về mặt trực quan, một chương trình P sau khi được rắc rối hóa thành O(P) thì ta không thể hiểu được logic của O(P) nữa. Làm thế nào để mô tả điều này về mặt toán học?

Một bài báo của Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, và Yang nghiên cứu định nghĩa như sau. Tôi chỉ mô tả lại đây ý tưởng chính đằng sau định nghĩa của họ. Định nghĩa cụ thể bằng toán học bạn có thể đọc trực tiếp.

Nếu O(P) cực kỳ khó hiểu, thì có O(P) cũng không khác gì có P như một hộp đen (blackbox). Hộp đen ở đây được hiểu là ta không biết P hoạt động thế nào, chỉ biết rằng cho bất kỳ input x nào thì ta biết output P(x) tương ứng của chương trình P, nhưng không có thông tin gì khác về việc làm thế nào mà P tính được P(x). Ví dụ, người ta có thể bán cho bạn một cái máy mà ta gõ vào tiếng Việt thì máy dịch sang tiếng Anh. Giả sử bạn không bao giờ mở máy ra xem thì bạn có truy cập theo kiểu hộp đen đến cái giải thuật dịch đấy. Nếu P là giải thuật dịch, việc bạn có O(P) cũng chẳng hơn gì có cái máy dịch không được tháo ra, dù O(P) vẫn là mã nguồn của P (chỉ bị rắc rối hóa đi thôi).

Cụ thể hơn về mặt toán học, thì O là bộ rắc rối hóa tốt nếu những gì ta tính toán được hay suy ra được từ O(P) cũng y như những gì ta tính toán được hay suy ra được từ truy cập kiểu hộp đen đến P.

Nếu ta chấp nhận định nghĩa này của bộ rắc rối hóa (định nghĩa có thể hơi mạnh quá), thì các tác giả bài báo trên chứng minh được rằng tồn tại một họ F các hàm số không thể rắc rối hóa được theo nghĩa như sau. Tồn tại một thuộc tính p: F –> {0,1} của các hàm số này thỏa mãn tính chất sau đây:

1. Nếu có bất kỳ chương trình Q nào tính một hàm f thuộc F, thì thuộc tính p(f) có thể tính được một cách hiệu quả,
2. Trong khi đó nếu ta chỉ có truy cập kiểu hộp đen đến một hàm f chọn ngẫu nhiên từ họ F, thì không có giải thuật hiệu quả nào để tính p(f) tốt hơn cách đoán bừa (random guessing).

Có lẽ cần giải thích chi tiết hơn một chút. Giả sử tồn tại một bộ rắc rối hóa O. Nếu O là bộ rắc rối hóa tốt thì, theo định nghĩa, nếu ta chọn một hàm f bất kỳ từ họ F thì việc có O(f) cũng không hơn gì việc có truy cập kiểu hộp đen đến f. Gọi Q = O(f). Theo tính chất (1) thì ta có thể tính p(f) một cách hiệu quả. Theo tính chất (2) thì ta không tính được p(f) một cách hiệu quả nếu chỉ có truy cập kiểu hộp đen đến f. Như vậy rõ ràng là O(f) chứa nhiều “thông tin” (trong trường hợp này là thuộc tính p của f) hơn là cái hộp đen tính f. Nói cách khác, O đã không hoàn toàn rắc rối hóa f.

Vài hướng nghiên cứu tiếp:

• Tìm một định nghĩa có ý nghĩa về mặt thực tiễn (cho software protection, watermarking, vân vân) cho bộ rắc rối hóa sao cho việc rắc rối hóa này vẫn có thể làm được về mặt lý thuyết.
• Giả sử ta vẫn dùng định nghĩa trên, có một lớp các hàm số nào hữu dụng mà lại có thể rắc rối hóa được hay không? (Bộ hàm số F như trên chỉ là một phản ví dụ không bao gồm hết các hàm hữu dụng trong thực tế.)

-- © NQH (12/05/2005)