# Cryptography 2 Xin chào các bạn, chào mừng quay trở lại với **Phần 2** của series về mật mã học! Nếu bạn chưa xem qua **Phần 1**, mình thực sự khuyên bạn nên đọc trước tại [đây](https://dangduongminhnhat.github.io/posts/cryptography/p1/), vì phần đó cung cấp nền tảng quan trọng cho những gì chúng ta sẽ cùng tìm hiểu trong bài này. Trong bài viết này, chúng ta sẽ khám phá khái niệm về **hệ mã tính toán (computational encryption schemes)**, tìm hiểu định nghĩa chính xác của **bảo mật ngữ nghĩa (semantic security)**, và phân tích một loại tấn công đặc biệt gọi là **tấn công khôi phục thông điệp (message recovery attack)**. Đặc biệt, chúng ta sẽ chứng minh một kết quả nền tảng: rằng **bảo mật ngữ nghĩa sẽ ngăn chặn tấn công khôi phục thông điệp** — và chứng minh điều đó thông qua một kỹ thuật cực kỳ quan trọng trong mật mã học: **giảm bảo mật (security reduction)**. Bắt đầu thôi nào! --- ## Computational ciphers và bảo mật ngữ nghĩa Như chúng ta đã biết, trong định lý của Shannon (Định lý 4 của bài blog [Cryptography 1](https://dangduongminhnhat.github.io/posts/cryptography/p1/)), cách duy nhất để đạt được bảo mật tuyệt đối là sử dụng khóa có độ dài bằng với thông điệp. Tuy nhiên, điều này không thực tế, chúng ta mong muốn rằng có thể mã hóa một thông điệp dài (ví dụ, một tài liệu có dung lượng vài megabyte) chỉ với một khóa ngắn (chẳng hạn, chỉ vài trăm bit). Cách duy nhất để vượt qua định lý của Shannon là nới lỏng các yêu cầu bảo mật. Chúng ta sẽ làm điều này bằng cách chỉ xem xét những kẻ tấn công có khả năng tính toán thực tế, tức là những kẻ tấn công trong thế giới thực, phải thực hiện tính toán trên các máy tính thực tế với lượng thời gian và bộ nhớ hợp lý. Điều này dẫn đến một định nghĩa bảo mật yếu hơn, được gọi là **bảo mật ngữ nghĩa** (*semantic security*). Hơn nữa, định nghĩa bảo mật của chúng ta sẽ đủ linh hoạt để cho phép các hệ mật với không gian thông điệp có độ dài thay đổi được coi là an toàn, miễn là chúng không rò rỉ bất kỳ thông tin hữu ích nào về thông điệp đã mã hóa cho kẻ tấn công, ngoại trừ độ dài của thông điệp. Ngoài ra, vì trọng tâm của chúng ta giờ đây là tính thực tiễn thay vì tính khả thi về mặt toán học, chúng ta cũng sẽ yêu cầu các hàm mã hóa và giải mã phải là các thuật toán hiệu quả, chứ không chỉ là các hàm tùy ý. ### Định nghĩa về mật mã tính toán Một **mật mã tính toán** $\mathcal{E} = (E, D)$ là một cặp thuật toán hiệu quả $E$ và $D$: - Thuật toán mã hóa $E$ nhận vào một khóa $k$ cùng một thông điệp $m$, và xuất ra bản mã $c$. - Thuật toán giải mã $D$ nhận vào một khóa $k$ cùng bản mã $c$, và xuất ra thông điệp $m$. Khóa thuộc về một **không gian khóa hữu hạn** $\mathcal{K}$, thông điệp thuộc về **không gian thông điệp hữu hạn** $\mathcal{M}$, và bản mã thuộc về **không gian bản mã hữu hạn** $\mathcal{C}$. Giống như mật mã của Shannon, ta nói rằng $\mathcal{E}$ được định nghĩa trên bộ $(\mathcal{K, M, C})$. #### Mã hóa xác suất Chúng ta nói rằng thuật toán mã hóa $E$ là một thuật toán xác suất, có nghĩa là với một khóa $k$ và thông điệp $m$ cố định, đầu ra của $E(k, m)$ có thể tạo ra nhiều bản mã khác nhau. Để nhấn mạnh tính xác suất của quá trình mã hóa, ta viết dưới dạng $c \xleftarrow{R} E(k, m)$, biểu diễn quá trình thực thi $E(k, m)$ và gán đầu ra vào biến $c$. Tương tự, để biểu diễn việc chọn một khóa ngẫu nhiên từ không gian khóa $K$, ta viết dưới dạng $k \xleftarrow{R} \mathcal{K}$ nghĩa là $k$ được chọn ngẫu nhiên, theo phân phối đều từ không gian khóa $\mathcal{K}$. Tuy nhiên, mặc dù có thể cho phép thuật toán giải mã là một thuật toán xác suất, chúng ta không cần quá quan tâm điều đó ở đây (chúng ta sẽ nhắc lại điều đó trong tương lai). Do đó, chúng ta chỉ thảo luận về các hệ mật mã có thuật toán giải mã **xác định** (*deterministic*). Tuy là vậy, đôi khi ta sẽ cho phép thuật toán giải mã trả về một giá trị đặc biệt (khác với mọi thông điệp hợp lệ), để chỉ ra rằng đã xảy ra lỗi trong quá trình giải mã. #### Tính đúng đắn của giải mã Do thuật toán mã hóa là một thuật toán xác suất, với một khóa $k$ và một thông điệp $m$ nhất định, thuật toán mã hóa có thể sinh ra nhiều bản mã khác nhau. Tuy nhiên, mỗi bản mã này **phải giải mã về đúng thông điệp ban đầu**. Ta có thể phát biểu yêu cầu này một cách chính xác như sau, với mọi khóa $k \in \mathcal{K}$ và mọi thông điệp $m \in \mathcal{M}$, nếu thực thi $c \xleftarrow{R} E(k, m)$, $m' \leftarrow D(k, c)$, thì ta luôn có xác suất $m' = m$ bằng $1$, tức là $\Pr[D(k, c) = m \mid c \xleftarrow{R} E(k, m)] = 1$. Từ nay về sau, khi nhắc đến một hệ mật mã, ta sẽ ngầm hiểu đó là một **mật mã tính toán** dựa theo định nghĩa vừa nêu ở trên. Nếu thuật toán mã hóa là xác định, ta gọi hệ mật đó là một **mật mã xác định** (*deterministic cipher*). #### So sánh với mật mã Shannon Quan sát rằng mọi **mật mã xác định** đều là **mật mã Shannon**. Tuy nhiên, một **mật mã tính toán** không nhất thiết là mật mã Shannon (nếu nó có thuật toán mã hóa xác suất), và ngược lại, một **mật mã Shannon** không nhất thiết là mật mã tính toán (nếu nó không có thuật toán mã hóa hoặc giải mã hiệu quả). Ta cùng xem lại các ví dụ của mã hóa Shannon ở [Cryptography 1](https://dangduongminhnhat.github.io/posts/cryptography/p1/): - **Mật mã một lần (one-time pad)** và **mật mã một lần có độ dài thay đổi** đều là **mật mã xác định**, vì các thao tác mã hóa và giải mã của chúng có thể được thực hiện dễ dàng dưới dạng các thuật toán xác định, hiệu quả. - **Mật mã thay thế (substitution cipher)** cũng là một **mật mã xác định**, miễn là kích thước bảng chữ cái $\Sigma$ không quá lớn. Trong cách triển khai phổ biến, một khóa (hoán vị của $\Sigma$) sẽ được biểu diễn dưới dạng một mảng có chỉ mục là các ký tự trong $\Sigma$. Điều này yêu cầu không gian lưu trữ $O(|\Sigma|)$, do đó chỉ thực tế với những $\Sigma$ có kích thước hợp lý. - **Mật mã một lần có phép cộng (additive one-time pad)** cũng là một **mật mã xác định**, vì cả quá trình mã hóa và giải mã đều có thể được thực hiện hiệu quả. Nếu $n$ lớn, ta có thể cần phần mềm đặc biệt để thực hiện các phép toán số học với số nguyên lớn. ### Định nghĩa về bảo mật ngữ nghĩa Okay, bây giờ ta sẽ tìm hiểu rõ hơn về định nghĩa bảo mật ngữ nghĩa, hãy xem xét một hệ mã hóa xác định $\mathcal{E} = (E, D)$, được định nghĩa trên $(\mathcal{K, M, C})$. Nhắc lại Định lý 2 về bảo mật hoàn hảo ở [Cryptography 1](https://dangduongminhnhat.github.io/posts/cryptography/p1/), ta có $\Pr[\phi(E(\mathbf{k}, m_0))] = \Pr[\phi(E(\mathbf{k}, m_1))]$ với $\mathbf{k}$ là biến ngẫu nhiên được chọn đồng đều từ không gian khóa $\mathcal{K}$. Thay vì yêu cầu hai xác suất này phải bằng nhau tuyệt đối, ta chỉ yêu cầu chúng **rất gần nhau**, tức là $\left| \Pr[\phi(E(\mathbf{k}, m_0))] - \Pr[\phi(E(\mathbf{k}, m_1))] \right| \leq \epsilon$, với $\epsilon$ là một giá trị rất nhỏ, hoặc thậm chí không đáng kể. Tuy nhiên, yêu cầu này vẫn còn quá khắt khe. Vì vậy, thay vì đòi hỏi điều kiện trên đúng với **mọi** $\phi, m_0, m_1$, ta chỉ yêu cầu nó đúng với **các thông điệp $m_0, m_1$ được tạo bởi một thuật toán hiệu quả**, và **các phép thử $\phi$ cũng được tính toán bởi một thuật toán hiệu quả** (các thuật toán này có thể là xác suất). Ví dụ, giả sử rằng ngay cả khi sử dụng **các thuật toán tối ưu nhất**, chạy trên **10.000 máy tính song song trong 10 năm**, điều kiện trên vẫn đúng với $\epsilon = 2^{-100}$. Khi đó, dù hệ mã hóa không hoàn toàn bảo mật, nhưng ta có thể chấp nhận nó là **bảo mật trong thực tế**. Ngoài ra, định nghĩa về bảo mật ngữ nghĩa cũng giải quyết vấn đề được nêu của ví dụ **variable-length one-time pad** không đạt được bảo mật hoàn hảo trong [Cryptography 1](https://dangduongminhnhat.github.io/posts/cryptography/p1/). Chúng ta mong muốn rằng định nghĩa của mình đủ linh hoạt để chấp nhận những hệ mã như vậy, miễn là **chúng không rò rỉ bất kỳ thông tin nào về thông điệp ngoại trừ độ dài của nó**. Bây giờ, chúng ta sẽ đi vào chi tiết để xây dựng một định nghĩa chính xác về **bảo mật ngữ nghĩa**. Ta mô tả một **trò chơi tấn công** giữa hai bên: - **Kẻ thách thức** (challenger) - **Kẻ tấn công** (adversary) Ta sẽ định nghĩa trò chơi tấn công khác nhau với mục đích thể hiện các mức độ bảo mật khác nhau của các hệ mật mã. - **Kẻ thách thức** tuân theo một giao thức cố định. - **Kẻ tấn công** có thể sử dụng một chiến lược tùy ý (nhưng vẫn trong giới hạn tính toán hiệu quả). - Hai bên trao đổi thông điệp với nhau theo giao thức đã quy định, và cuối cùng **kẻ tấn công** đưa ra một phỏng đoán. Trò chơi tấn công cũng xác định một **không gian xác suất**, từ đó tính toán **lợi thế** của kẻ tấn công dựa trên xác suất xảy ra một hoặc nhiều sự kiện nhất định. Ngoài ra, trong một số trò chơi tấn công sẽ bao gồm hai **thí nghiệm** (experiment). - Trong cả hai **thí nghiệm**, kẻ tấn công thực hiện cùng một giao thức. - Tuy nhiên, kẻ thách thức hành xử khác nhau trong mỗi thí nghiệm. Cụ thể: 1. **Kẻ tấn công** chọn hai thông điệp $m_0, m_1$ có cùng độ dài và gửi chúng cho kẻ thách thức. 2. **Kẻ thách thức** thực hiện một trong hai thí nghiệm: - **Experiment 0**: Mã hóa $m_0$ với khóa ngẫu nhiên $k$. - **Experiment 1**: Mã hóa $m_1$ với khóa ngẫu nhiên $k$. 3. **Kẻ thách thức** gửi bản mã $c$ về cho kẻ tấn công. 4. **Kẻ tấn công** phân tích $c$ và đoán xem nó được tạo từ $m_0$ hay $m_1$, bằng cách xuất ra một bit $\hat{b} \in \{0,1\}$. Okay, vậy ta cùng xem xét Trò chơi tấn công trong Bảo mật ngữ nghĩa như sau. Cho một hệ mã hóa $\mathcal{E} = (E, D)$ được định nghĩa trên các tập hợp $(\mathcal{K, M, C})$, và một kẻ tấn công $\mathcal{A}$. Ta định nghĩa hai thí nghiệm: **Experiment 0** và **Experiment 1**. Với $b = 0, 1$, ta định nghĩa **Experiment b** như sau: 1. **Kẻ tấn công** chọn hai thông điệp $m_0, m_1 \in \mathcal{M}$ có cùng độ dài và gửi chúng cho kẻ thách thức. 2. **Kẻ thách thức** thực hiện các bước sau: - Chọn một khóa ngẫu nhiên $k \xleftarrow{R} \mathcal{K}$. - Mã hóa thông điệp $m_b$: $c \xleftarrow{R} E(k, m_b)$. - Gửi bản mã $c$ cho kẻ tấn công. 3. **Kẻ tấn công** quan sát bản mã $c$ và xuất ra một bit dự đoán $\hat{b} \in \{0,1\}$. Để dễ hiểu, ta có thể nhìn vào sơ đồ dưới đây. ![image](https://hackmd.io/_uploads/rkVmWMcTJx.png) #### Định nghĩa lợi thế của kẻ tấn công Ký hiệu $W_b$ là sự kiện kẻ tấn công $\mathcal{A}$ xuất ra giá trị $\hat{b} = 1$ trong **Experiment b**. Khi đó, lợi thế của $\mathcal{A}$ trong việc phá vỡ bảo mật ngữ nghĩa của hệ mã $\mathcal{E}$ được định nghĩa là: $$ \mathtt{SS}\text{adv}[\mathcal{A},\mathcal{E}] := \left| \Pr[W_0] - \Pr[W_1] \right|. $$ Trong trò chơi trên, các sự kiện $W_0$ và $W_1$ được xác định trong không gian xác suất phụ thuộc vào: - **Sự lựa chọn ngẫu nhiên của khóa** $k$. - **Các lựa chọn ngẫu nhiên (nếu có) trong thuật toán mã hóa**. - **Các lựa chọn ngẫu nhiên (nếu có) của kẻ tấn công**. Giá trị $\mathtt{SS}\text{adv}[\mathcal{A},\mathcal{E}]$ luôn nằm trong khoảng $[0,1]$. Nếu $\mathtt{SS}\text{adv}[\mathcal{A},\mathcal{E}]$ rất nhỏ, nghĩa là kẻ tấn công không thể phân biệt giữa hai bản mã tương ứng với $m_0$ và $m_1$, từ đó đảm bảo tính bảo mật ngữ nghĩa của hệ mã hóa. #### Định nghĩa (Bảo mật ngữ nghĩa). Một hệ mã hóa $\mathcal{E}$ được gọi là **bảo mật ngữ nghĩa** nếu với mọi kẻ tấn công hiệu quả $\mathcal{A}$, giá trị $\mathtt{SS}\text{adv}[\mathcal{A},\mathcal{E}]$ là **không đáng kể**. Định nghĩa này chưa hoàn toàn chặt chẽ, vì ta chưa xác định rõ các khái niệm **“các thông điệp có cùng độ dài”**, **“kẻ tấn công hiệu quả”** và **“không đáng kể”**. Chúng ta sẽ quay lại các vấn đề này sau. Giả sử kẻ tấn công $\mathcal{A}$ trong **Trò chơi tấn công trong bảo mật ngữ nghĩa** là **xác định**. Khi đó: 1. $\mathcal{A}$ chọn hai thông điệp $m_0, m_1$ một cách xác định. 2. $\mathcal{A}$ đánh giá một **mệnh đề** $\phi$ trên bản mã $c$ và xuất ra 1 nếu đúng, 0 nếu sai. Bảo mật ngữ nghĩa yêu cầu giá trị $\epsilon$ trong bất đẳng thức $\left| \Pr[\phi(E(k, m_0))] - \Pr[\phi(E(k, m_1))] \right| \leq \epsilon$ là **không đáng kể**. Nếu $\mathcal{A}$ là một thuật toán **ngẫu nhiên**, ta có thể xem $\mathcal{A}$ như sau: 1. Sinh một giá trị ngẫu nhiên $r$ từ một tập hợp phù hợp. 2. Xác định hai thông điệp $m_0^{(r)}$, $m_1^{(r)}$ dựa vào $r$. 3. Đánh giá một **mệnh đề** $\phi^{(r)}$ trên $c$, cũng phụ thuộc vào $r$. Trong trường hợp này, bảo mật ngữ nghĩa yêu cầu giá trị $\epsilon$ trong bất đẳng thức trên (với $m_0, m_1, \phi$ được thay bởi $m_0^{(r)}, m_1^{(r)}, \phi^{(r)}$) là **không đáng kể** — nhưng bây giờ xác suất được tính trên không gian xác suất của **khóa ngẫu nhiên** và **giá trị ngẫu nhiên $r$**. --- Ta có một số nhận xét về yêu cầu rằng hai thông điệp $m_0$ và $m_1$ do kẻ tấn công chọn trong **Trò chơi tấn công trong bảo mật ngữ nghĩa** phải có cùng độ dài. - **Thứ nhất, khái niệm "độ dài" của một thông điệp phụ thuộc vào không gian thông điệp** $\mathcal{M}$. - Khi xác định một không gian thông điệp, ta cần xác định một quy tắc ánh xạ mỗi thông điệp sang một giá trị độ dài (là một số nguyên không âm). - Trong nhiều trường hợp cụ thể, điều này là rõ ràng. Ví dụ, với không gian thông điệp $\{0,1\}^{\leq L}$, độ dài của một thông điệp $m \in \{0,1\}^{\leq L}$ đơn giản là số bit của nó, với $|m|$ là số bit của $m$. - Tuy nhiên, để giữ cho định nghĩa tổng quát, ta không gán một quy tắc cụ thể mà để khái niệm độ dài ở dạng **trừu tượng**. - Trong một số không gian thông điệp, khái niệm độ dài có thể không tồn tại, khi đó ta có thể coi mọi thông điệp đều có độ dài **bằng 0**. - **Thứ hai, yêu cầu rằng $m_0$ và $m_1$ có cùng độ dài đảm bảo rằng kẻ tấn công không thể phá vỡ hệ mã chỉ bằng cách phân biệt độ dài của bản mã.** - Nếu không có yêu cầu này, một hệ mã có thể bị coi là **không an toàn** chỉ vì nó tiết lộ độ dài của thông điệp. - Điều này phản ánh thực tế rằng hầu hết các hệ mã thực tế **cho phép rò rỉ độ dài thông điệp**, nhưng không nên rò rỉ **nội dung** của thông điệp. Chúng ta cùng xem lại **Ví dụ variable length one-time pad** trong bài trước [Cryptography 1](https://dangduongminhnhat.github.io/posts/cryptography/p1/), việc rò rỉ độ dài thông điệp có thể gây ra hậu quả nghiêm trọng trong một số ứng dụng. Tuy nhiên, do **không có giải pháp tổng quát** để che giấu độ dài thông điệp, hầu hết các hệ mã thực tế (ví dụ: **TLS**) không cố gắng che giấu thông tin này. Điều này dẫn đến nhiều cuộc tấn công thực tế và trong một số ứng dụng nhạy cảm, **việc rò rỉ độ dài bản mã có thể dẫn đến rủi ro bảo mật nghiêm trọng**. Tuy vậy, ta vẫn giả sử rằng bảo mật ngữ nghĩa không phụ thuộc vào độ dài thông điệp, ta xem thử ví dụ sau. Giả sử $\mathcal{E}$ là một hệ mã **định xác** (deterministic cipher) có **bảo mật hoàn hảo**. Khi đó, dễ dàng thấy rằng **đối với mọi kẻ tấn công $\mathcal{A}$ (dù hiệu quả hay không hiệu quả), ta có** $\mathtt{SS}\text{adv}[\mathcal{A},\mathcal{E}] = 0$. Điều này gần như suy ra ngay lập tức từ **Định lý 2** trong bài [Cryptography 1](https://dangduongminhnhat.github.io/posts/cryptography/p1/) (chỉ có một điểm cần lưu ý là $\mathcal{A}$ trong **Trò chơi tấn công trong bảo mật ngữ nghĩa** có thể là một thuật toán ngẫu nhiên, nhưng điều này có thể xử lý dễ dàng). Do đó, hệ mã $\mathcal{E}$ là **bảo mật ngữ nghĩa**. Cụ thể là: - Nếu $\mathcal{E}$ là **mật mã một lần (one-time pad)**, ta có $\mathtt{SS}\text{adv}[\mathcal{A},\mathcal{E}] = 0$ $\forall \mathcal{A}$. Nói cách khác, **mật mã một lần là bảo mật ngữ nghĩa**. - Như ta đã nhận xét thứ ở trên về định nghĩa bảo mật ngữ nghĩa rằng kẻ tấn công không thể phá vỡ hệ mã chỉ bằng cách phân biệt độ dài của bản mã, nên ta cũng có thể dễ dàng thấy rằng nếu $\mathcal{E}$ là **variable length one-time pad**, thì ta cũng có $\mathtt{SS}\text{adv}[\mathcal{A},\mathcal{E}] = 0$ $\forall \mathcal{A}$. Điều này có nghĩa là **mật mã một lần với độ dài biến đổi cũng là bảo mật ngữ nghĩa**. --- Trước khi tiếp tục, vì tôi chưa giải thích rõ nên tôi sẽ giải thích dễ hiểu một số thuật ngữ như **"hiệu quả"** (efficient) và **"không đáng kể"** (negligible). Chúng ta sẽ tìm hiểu chi tiết hơn trong tương lai nhưng mọi người có thể hiểu đơn giản như sau: - **Không đáng kể (negligible)**: Một giá trị là **không đáng kể** nếu nó **nhỏ đến mức có thể xem như bằng $0$ trong thực tế**. Ví dụ, xét số $2^{-100}$. Nếu xác suất bạn tự nhiên bốc cháy trong năm tới là $2^{-100}$, thì bạn sẽ không lo lắng về sự kiện đó hơn so với một sự kiện có xác suất **bằng $0$**. - **Kẻ tấn công hiệu quả** là kẻ tấn công chạy trong một lượng thời gian "hợp lý" hay là thời gian chạy của kẻ tấn công hiệu quả được chặn bởi đa thức, điều đó có nghĩa là thời gian chạy của nó không thể vượt quá một số đa thức nào đó theo kích thước đầu vào. Thay vì tập trung vào các chi tiết kỹ thuật, ta sẽ xem một **ví dụ minh họa** cách sử dụng định nghĩa này để phân tích bảo mật của một hệ thống lớn hơn có sử dụng một hệ mã bảo mật ngữ nghĩa. ## **Tấn công khôi phục thông điệp (Message Recovery Attack)** Bắt đầu với ví dụ đầu tiên là trong một cuộc tấn công khôi phục thông điệp, giả sử kẻ tấn công được cung cấp một bản mã của một thông điệp ngẫu nhiên, và có thể **khôi phục lại thông điệp từ bản mã với xác suất tốt hơn đáng kể so với việc đoán ngẫu nhiên**, tức là **tốt hơn xác suất $1/|\mathcal{M}|$**. Tất nhiên, đối với bất kỳ khái niệm bảo mật hợp lý nào cũng phải ngăn chặn được kiểu tấn công này và kể cả **bảo mật ngữ nghĩa (semantic security)** cũng làm được điều đó. Mặc dù điều này có nghe có vẻ hiển nhiên (vì rõ ràng nếu không đoán được $m_0$ hay $m_1$ thì càng không đoán được $m$ ngẫu nhiên), nhưng chúng ta sẽ chứng minh rõ ràng nhận định trên. Và cách chứng minh này cũng là để minh họa chi tiết cho khái niệm **giảm bảo mật (security reduction)** — đây là kỹ thuật chính để lập luận về tính bảo mật của các hệ thống. Về cơ bản, ý tưởng của kỹ thuật security reduction là sẽ lập luận rằng **nếu tồn tại một kẻ tấn công hiệu quả $\mathcal{A}$** có thể thực hiện tấn công khôi phục thông điệp lên $\mathcal{E}$, thì ta có thể **xây dựng một kẻ tấn công hiệu quả $\mathcal{B}$** phá vỡ bảo mật ngữ nghĩa của $\mathcal{E}$. Vì bảo mật ngữ nghĩa đảm bảo rằng không tồn tại kẻ tấn công như vậy $\mathcal{B}$, suy ra cũng không tồn tại $\mathcal{A}$. Tương tự như bảo mật ngữ nghĩa, ta biểu diễn tấn công bằng một trò chơi giữa **người thách thức (challenger)** và **kẻ tấn công (adversary)**, gọi là trò chời tấn công trong Khôi phục thông điệp. Trò chơi như sau, cho trước một hệ mã $\mathcal{E} = (E, D)$, được định nghĩa trên không gian $(\mathcal{K}, \mathcal{M}, \mathcal{C})$, và một kẻ tấn công $\mathcal{A}$, trò chơi diễn ra như sau: - Người thách thức chọn ngẫu nhiên $m \xleftarrow{R} \mathcal{M}$, chọn khoá ngẫu nhiên $k \xleftarrow{R} \mathcal{K}$ và mã hóa $c \xleftarrow{R} E(k, m)$, rồi gửi $c$ cho kẻ tấn công. - Kẻ tấn công xuất ra một thông điệp dự đoán $\hat{m} \in \mathcal{M}$. Gọi $W$ là biến cố $\hat{m} = m$ (tức là kẻ tấn công đoán đúng). Ta nói rằng $\mathcal{A}$ **thắng trò chơi** nếu biến cố $W$ xảy ra. Và **lợi thế khôi phục thông điệp** (Message Recovery Advantage) của $\mathcal{A}$ đối với hệ mã $\mathcal{E}$ được định nghĩa là: $$ \texttt{MR}\text{adv}[\mathcal{A}, \mathcal{E}] := \left| \Pr[W] - \frac{1}{|\mathcal{M}|} \right|. $$ ### **Định nghĩa Bảo mật chống lại tấn công khôi phục thông điệp** Một hệ mã $\mathcal{E}$ được gọi là **bảo mật chống lại tấn công khôi phục thông điệp** nếu với mọi kẻ tấn công hiệu quả $\mathcal{A}$, **lợi thế** của $\mathcal{A}$ trong việc khôi phục thông điệp là một hàm số **không đáng kể** (*negligible*), tức là hệ mã an toàn khi $\texttt{MR}\text{adv}[\mathcal{A}, \mathcal{E}]$ là không đáng kể với mọi $\mathcal{A}$ hiệu quả. Từ đó, ta có định lý sau. **Định lý 1.** Cho hệ mã $\mathcal{E} = (E, D)$, được định nghĩa trên bộ $(\mathcal{K}, \mathcal{M}, \mathcal{C})$. **Nếu $\mathcal{E}$ là bảo mật ngữ nghĩa**, thì **$\mathcal{E}$ cũng an toàn chống lại tấn công khôi phục thông điệp**. **Chứng minh.** Giả sử rằng $\mathcal{E}$ là **bảo mật ngữ nghĩa** (semantically secure). Mục tiêu của ta là chứng minh rằng $\mathcal{E}$ cũng **bảo mật chống lại tấn công khôi phục thông điệp**. Để làm điều này, ta phải chứng minh rằng với mọi kẻ tấn công hiệu quả $\mathcal{A}$, thì lợi thế của $\mathcal{A}$ trong **Trò chơi tấn công khôi phục thông điệp** là không đáng kể. Giả sử $\mathcal{A}$ là một kẻ tấn công hiệu quả bất kỳ. Gọi: - $p$ là xác suất $\mathcal{A}$ thắng trong trò chơi khôi phục thông điệp, - $|\mathcal{M}|$ là số lượng thông điệp có thể có. Khi đó, lợi thế khôi phục thông điệp của $A$ là: $$ \texttt{MR}\text{adv}[\mathcal{A}, \mathcal{E}] = \left| p - \frac{1}{|\mathcal{M}|} \right|. $$ Ý tưởng cho chứng minh này, như ta đã nói ở trên là ta sẽ **xây dựng một kẻ tấn công hiệu quả $\mathcal{B}$** trong trò chơi bảo mật ngữ nghĩa được giới thiệu ở trên, sao cho: $$ \texttt{MR}\text{adv}[\mathcal{A}, \mathcal{E}] \leq \texttt{SS}\text{adv}[\mathcal{B}, \mathcal{E}] \tag{1} $$ Và vì $\mathcal{B}$ là hiệu quả, và $\mathcal{E}$ được giả sử là bảo mật ngữ nghĩa dẫn đến $\texttt{SS}\text{adv}[\mathcal{B}, \mathcal{E}]$ là không đáng kể. Do đó, $\texttt{MR}\text{adv}[\mathcal{A}, \mathcal{E}]$ cũng không đáng kể. Chúng ta không cần biết bên trong $\mathcal{A}$ hoạt động như thế nào, mà chỉ cần sử dụng $\mathcal{A}$ như là một **hộp đen**. **Cách hoạt động của kẻ tấn công $\mathcal{B}$ diễn ra như sau:** 1. $\mathcal{B}$ tạo ra **hai thông điệp ngẫu nhiên** $m_0, m_1 \in \mathcal{M}$, rồi gửi chúng đến **người thách thức trong trò chơi bảo mật ngữ nghĩa ($\texttt{SS}$ challenger)** của chính nó. 2. Người thách thức gửi lại một bản mã $c$, là bản mã của $m_b$ với $b \in \{0, 1\}$ được chọn ngẫu nhiên. 3. $\mathcal{B}$ chuyển tiếp $c$ cho kẻ tấn công $\mathcal{A}$, như thể đó là bản mã được tạo ra trong trò chơi khôi phục thông điệp ($\texttt{MR}$ game). 4. Sau khi nhận được bản mã, $\mathcal{A}$ xuất ra một thông điệp $\hat{m} \in \mathcal{M}$. 5. $\mathcal{B}$ phân tích phản hồi của $\mathcal{A}$: - Nếu $\hat{m} = m_1$, thì $\mathcal{B}$ xuất ra $\hat{b} = 1$. - Ngược lại, $\mathcal{B}$ xuất ra $\hat{b} = 0$. Như vậy, mô tả của kẻ tấn công $\mathcal{B}$ đã hoàn tất. Ta lưu ý rằng **thời gian chạy của $\mathcal{B}$** gần như **bằng với thời gian chạy của $\mathcal{A}$**, vì $\mathcal{B}$ chỉ đơn giản gọi $\mathcal{A}$ như một hộp đen. Giờ ta phân tích lợi thế của $\mathcal{B}$ trong trò chơi bảo mật ngữ nghĩa ($\texttt{SS}$), và liên hệ nó với lợi thế khôi phục thông điệp của $\mathcal{A}$. Gọi: - $p_0$ là xác suất $\mathcal{B}$ đoán $\hat{b} = 1$ khi người thách thức mã hóa $m_0$, - $p_1$ là xác suất $\mathcal{B}$ đoán $\hat{b} = 1$ khi người thách thức mã hóa $m_1$. Theo định nghĩa: $$ \texttt{SS}\text{adv}[\mathcal{B}, \mathcal{E}] = |p_1 - p_0|. $$ Khi $c = E(k, m_1)$, thì $\mathcal{B}$ gửi bản mã đó cho $\mathcal{A}$, và $\mathcal{A}$ cố gắng đoán ra thông điệp ban đầu. Xác suất $\mathcal{A}$ đoán đúng $m_1$ chính là xác suất thắng của $\mathcal{A}$ trong trò chơi khôi phục thông điệp là $p_1 = \Pr[\hat{m} = m_1] = p$. Mặt khác, khi bản mã là của $m_0$, $\mathcal{A}$ nhận bản mã của $m_0$, mà không có thông tin gì về $m_1$, nên việc $\mathcal{A}$ đoán ra $m_1$ từ thông tin đó chỉ là đoán mò. Vì vậy, $p_0 = \Pr[\hat{m} = m_1] = \frac{1}{|\mathcal{M}|}$. Từ đó, ta có: $$ \texttt{SS}\text{adv}[\mathcal{B}, \mathcal{E}] = |p_1 - p_0| = \left| p - \frac{1}{|\mathcal{M}|} \right| = \texttt{MR}\text{adv}[\mathcal{A}, \mathcal{E}]. $$ Điều này chứng minh bất đẳng thức $(1)$ đúng, thậm chí trong trường hợp này **dấu bằng xảy ra**. Tuy nhiên, với mục đích của chứng minh, **không cần phải có dấu bằng**, chỉ cần bất đẳng thức là đủ. --- Các bạn nên chắc chắn rằng mình đã hiểu được logic của chứng minh này, vì kiểu chứng minh như vậy sẽ được sử dụng lặp đi lặp lại trong suốt series này. Chúng ta sẽ cùng ôn lại những phần quan trọng của chứng minh, và đưa ra một cách tiếp cận khác để suy nghĩ về nó. Cốt lõi của chứng minh là thiết lập được mệnh đề sau, **với mọi kẻ tấn công message recovery hiệu quả** $\mathcal{A}$ tấn công $\mathcal{E}$ trong **Trò chơi Tấn công khôi phục thông điệp**, tồn tại một **kẻ tấn công semantic security hiệu quả** $\mathcal{B}$ tấn công $\mathcal{E}$ trong **Trò chơi Tấn công bảo mật ngữ nghĩa** sao cho: $$ \texttt{MR}\text{adv}[\mathcal{A}, \mathcal{E}] \leq \texttt{SS}\text{adv}[\mathcal{B}, \mathcal{E}] \tag{2} $$ Mục tiêu của ta là chứng minh rằng: nếu $\mathcal{E}$ là **an toàn theo nghĩa ngữ nghĩa** (semantically secure), thì $\mathcal{E}$ cũng **an toàn trước tấn công khôi phục thông điệp** (message recovery). Trong chứng minh trên, ta lập luận rằng nếu $\mathcal{E}$ là semantically secure thì vế phải của bất đẳng thức $(2)$ phải là **rất nhỏ** (negligible), từ đó vế trái cũng phải nhỏ. Vì điều này đúng với **mọi** kẻ tấn công hiệu quả $\mathcal{A}$, nên ta kết luận rằng $\mathcal{E}$ là an toàn trước tấn công khôi phục thông điệp. Một cách tiếp cận khác để chứng minh định lý là sử dụng **phản chứng** (contrapositive): > Nếu $\mathcal{E}$ **không** an toàn trước tấn công khôi phục thông điệp, thì $\mathcal{E}$ **không** an toàn theo nghĩa ngữ nghĩa. Cụ thể, giả sử rằng $\mathcal{E}$ không an toàn trước message recovery. Điều này có nghĩa là **tồn tại một kẻ tấn công hiệu quả** $\mathcal{A}$ mà lợi thế message recovery của nó là **không nhỏ** (non-negligible). Sử dụng $\mathcal{A}$, ta xây dựng một kẻ tấn công hiệu quả $\mathcal{B}$ sao cho bất đẳng thức $(2)$ được thỏa mãn. Và vì $\texttt{MR}\text{adv}[\mathcal{A}, \mathcal{E}]$ là không nhỏ, và theo $(2)$ thì $\texttt{SS}\text{adv}[\mathcal{B}, \mathcal{E}] \geq \texttt{MR}\text{adv}[\mathcal{A}, \mathcal{E}]$, nên suy ra $\texttt{SS}\text{adv}[\mathcal{B}, \mathcal{E}]$ cũng không nhỏ. Từ đó kết luận rằng $\mathcal{E}$ **không** semantically secure. Nói ngắn gọn hơn: > Để chứng minh rằng **semantic security** suy ra **message recovery security**, ta chỉ cần chỉ ra cách biến một kẻ tấn công message recovery thành một kẻ tấn công semantic security. Ta cũng nhấn mạnh rằng **kẻ tấn công $\mathcal{B}$** được xây dựng trong chứng minh **chỉ đơn thuần sử dụng $\mathcal{A}$ như một “hộp đen”** (black box). Trên thực tế, hầu hết các cách xây dựng ta sẽ gặp sau này đều có dạng như vậy, $\mathcal{B}$ chỉ là một **lớp bao ngoài (wrapper)** xung quanh $\mathcal{A}$, bao gồm một “lớp giao tiếp” đơn giản và hiệu quả giữa **challenger của $\mathcal{B}$** và một phiên bản chạy duy nhất của $\mathcal{A}$. Ta nói độ phức tạp tính toán của lớp giao tiếp (dữ liệu của $\mathcal{B}$ truyền cho $\mathcal{A}$ và ngược lại) không phụ thuộc vào độ phức tạp của $\mathcal{A}$; tuy nhiên, trong một số trường hợp, điều này không tránh khỏi. Nếu trò chơi tấn công cho phép $\mathcal{A}$ gửi nhiều truy vấn đến challenger, thì càng nhiều truy vấn, lớp giao tiếp sẽ phải xử lý nhiều hơn. Tuy nhiên, lượng công việc này chỉ nên phụ thuộc vào **số lượng truy vấn**, chứ **không phụ thuộc vào thời gian chạy của $\mathcal{A}$**. Do đó, ta định nghĩa $\mathcal{B}$ là một **elementary wrapper** quanh $\mathcal{A}$ nếu nó được xây dựng như trên, với một lớp giao tiếp hiệu quả tương tác với $\mathcal{A}$. Những tính chất đáng lưu ý là: - Nếu $\mathcal{B}$ là elementary wrapper quanh $\mathcal{A}$, và $\mathcal{A}$ hiệu quả, thì $\mathcal{B}$ cũng hiệu quả. - Nếu $\mathcal{C}$ là elementary wrapper quanh $\mathcal{B}$, và $\mathcal{B}$ là elementary wrapper quanh $A$, thì $\mathcal{C}$ là elementary wrapper quanh $\mathcal{A}$. Các khái niệm này sẽ được trình bày một cách **formal** trong tương lai. --- Trong bài viết này, chúng ta đã làm rõ mối liên hệ giữa bảo mật ngữ nghĩa (semantic security) và khả năng chống lại tấn công khôi phục thông điệp (message recovery attack). Thông qua kỹ thuật giảm bảo mật (security reduction), ta đã chứng minh rằng một hệ mã đạt được semantic security thì tất yếu cũng sẽ ngăn chặn được mọi kẻ tấn công cố gắng khôi phục lại thông điệp từ bản mã. Đây là một ví dụ điển hình cho cách tư duy trong mật mã học hiện đại là chứng minh một thuộc tính bảo mật mạnh sẽ kéo theo những thuộc tính yếu hơn, và điều này được thực hiện bằng cách xây dựng một lớp bao (wrapper) hiệu quả giữa các kẻ tấn công. Kiểu chứng minh này – nơi một kẻ tấn công được "đóng gói" lại để hoạt động trong một trò chơi khác – sẽ là kỹ thuật then chốt xuyên suốt nhiều kết quả trong lý thuyết mật mã. Vì vậy, việc hiểu rõ logic trong bài viết này sẽ tạo nền móng vững chắc cho các phần sau trong chuỗi bài viết.