Câu hỏi: CRY303c - Phần 5: Hàm băm mật mã và bảo vệ toàn vẹn

Đáp án đúng: "2^63 x". Câu hỏi viết "128-bit-long key" nhưng ý là giá trị băm dài n = 128 bit. Phá kháng va chạm mạnh (strong collision resistance, tìm một cặp bất kỳ trùng băm) dùng tấn công ngày sinh (birthday attack), cần cỡ 2^(n/2) = 2^64 lần băm, nên x = 2^64. Phá kháng va chạm yếu (weak collision resistance, cho trước một đầu vào, tìm đầu vào khác cùng băm) không dùng được nghịch lý ngày sinh; theo quy ước của khoá học cho tấn công tiền ảnh thứ hai "trung bình", ta coi như vét cạn 2^128 giá trị băm và trúng sau một nửa, tức 2^(128−1) = 2^127 lần. Tỉ số là 2^127 / 2^64 = 2^63. Chỗ tranh cãi: "2^64 x" có cơ sở theo quy ước khác, vì nếu mỗi lần thử ngẫu nhiên trúng với xác suất 2^(−128) thì số lần thử kỳ vọng là 2^128 và tỉ số là 2^128 / 2^64 = 2^64; ở đây chọn theo quy ước khoá học và chữ "on average". "2^127 x" lấy số lần tuyệt đối của va chạm yếu làm tỉ số, nhân thêm x sẽ ra 2^191. "2^128 x" cũng nhầm số lần tuyệt đối (kỳ vọng của phép thử ngẫu nhiên) với tỉ số. "1x" coi hai việc khó ngang nhau, trái với nghịch lý ngày sinh. "2^256 x" vượt xa cả không gian 2^128 giá trị băm.

Đáp án đúng: "Pre-image resistance". Kháng tiền ảnh (pre-image resistance, còn gọi là tính một chiều) đòi hỏi: cho một giá trị băm h bất kỳ, không thể tìm được một cách khả thi đầu vào x nào sao cho H(x) = h; với hàm băm đầu ra n bit, vét cạn cần cỡ 2^n lần thử. "Weak collision resistance" (kháng va chạm yếu, hay kháng tiền ảnh thứ hai) là tính chất khác: cho trước một đầu vào x cụ thể, khó tìm x' khác x có cùng giá trị băm; kẻ tấn công được biết cả đầu vào chứ không chỉ đầu ra. "Strong collision resistance" (kháng va chạm mạnh) đòi hỏi khó tìm bất kỳ cặp đầu vào khác nhau nào cho cùng giá trị băm; kẻ tấn công tự chọn cả hai đầu vào nên tấn công ngày sinh (birthday attack) chỉ cần cỡ 2^(n/2) lần. Câu hỏi chỉ nói "cho đầu ra, tìm lại đầu vào", đúng định nghĩa tiền ảnh.

Đáp án đúng: "Digital signature". MAC (message authentication code, mã xác thực thông điệp) là một khối dữ liệu ngắn có độ dài cố định, tính từ thông điệp và một khoá bí mật chung K của hai bên; bên nhận tính lại MAC bằng cùng K để kiểm tra toàn vẹn và nguồn gốc. Vì thế nó còn được gọi là "Authenticator" (bộ xác thực), "Tag" (thẻ gắn kèm thông điệp), "Cryptographic checksum" (tổng kiểm tra mật mã, khác checksum thường ở chỗ có khoá) và "Keyed hash" (băm có khoá, như HMAC). Chữ ký số khác về bản chất: nó dùng cặp khoá bất đối xứng, ký bằng khoá riêng và ai có khoá công khai cũng kiểm được, nên cho thêm tính chống chối bỏ (non-repudiation), điều MAC với khoá dùng chung không làm được vì bên nhận cũng tạo ra được đúng MAC đó.

Đáp án đúng: "Confidentiality protection". MAC (Message Authentication Code, mã xác thực thông điệp) là giá trị ngắn tính từ thông điệp và khoá bí mật, gửi kèm thông điệp ở dạng rõ; nó chứng minh nguồn gốc và tính toàn vẹn nhưng không che giấu nội dung, nên bảo vệ tính bí mật không thể là lý do chọn MAC thay cho mã hoá. "Application requirement" là lý do thật: có ứng dụng phát cùng một thông điệp tới nhiều nơi, hoặc chỉ cần xác thực mà không cần giấu nội dung. "Performance" cũng đúng: bên nhận chịu tải lớn có thể chỉ kiểm tra MAC một cách chọn lọc thay vì giải mã mọi thứ. "Flexibility" đúng vì tách xác thực khỏi bảo mật cho phép áp dụng hai cơ chế ở hai tầng khác nhau. "Longer protection" đúng vì MAC có thể lưu cùng thông điệp để kiểm tra toàn vẹn về sau, còn bản đã giải mã thì mất bảo vệ ngay sau khi nhận.

Đáp án đúng: "15". Cây băm (hash tree, cây Merkle) giữ giá trị băm của từng khối ở lá và băm của hai con ở mỗi nút trong, nên một khối lỗi làm lệch đúng một đường từ lá lên gốc. Để khoanh vùng, ta kiểm gốc thấy lệch, rồi ở mỗi tầng kiểm cả hai nút con của nút lệch để biết nhánh nào chứa lỗi. Cây 256 khối có log2(256) = 8 tầng dưới gốc nên cách đếm này cho 1 + 2 × 8 = 17 lần kiểm; cùng cách đếm, cây 16 khối ra 1 + 2 × 4 = 9 và cây 128 khối ra 1 + 2 × 7 = 15. Nói thẳng: 17 không có trong các phương án, nên không lựa chọn nào khớp đúng. "15" (cây 128 khối) và "19" = 1 + 2 × 9 (cây 512 khối) cùng lệch đúng một tầng so với 17; chọn "15" vì nó trùng kết quả của cùng câu hỏi với cây 128 khối, nhiều khả năng số khối đã đổi mà phương án giữ nguyên, chứ không phải vì "19" sai hơn về lập luận. "23" = 1 + 2 × 11 ứng với cây 2048 khối, "27" = 1 + 2 × 13 ứng với 8192 khối, "31" = 1 + 2 × 15 ứng với 32768 khối, đều lệch từ ba tầng trở lên.

Đáp án đúng: "True". Hàm băm (hash function) nhận đầu vào có độ dài tuỳ ý và luôn trả về giá trị băm (digest) có độ dài cố định; ví dụ SHA-256 cho ra đúng 256 bit dù đầu vào là một byte hay một tệp vài gigabyte, MD5 luôn cho 128 bit, SHA-1 luôn cho 160 bit. Tính chất này giúp giá trị băm dùng được như dấu vân tay ngắn gọn của dữ liệu để kiểm toàn vẹn hay ký số. Cũng vì nén vô hạn đầu vào về hữu hạn đầu ra nên va chạm luôn tồn tại, và an toàn của hàm băm nằm ở chỗ khó tìm va chạm chứ không phải không có. "False" sai vì cả hai vế của phát biểu đúng là định nghĩa cơ bản của hàm băm.

Đáp án đúng: "H^{n-1}". Trong sơ đồ mật khẩu dùng một lần theo chuỗi băm của Lamport, người dùng chọn giá trị gốc x rồi băm liên tiếp n lần; máy chủ chỉ lưu H^n(x). Lần đăng nhập kế tiếp, người dùng gửi H^{n-1}(x); máy chủ băm thêm một lần và so: H(H^{n-1}(x)) = H^n(x) thì chấp nhận, rồi thay giá trị lưu bằng H^{n-1}(x) cho lần sau. An toàn vì hàm băm một chiều: biết H^n không lùi được về H^{n-1}. "H^n" đã nằm ở máy chủ và đã lộ, gửi lại chỉ là phát lại. "H^{n+1}" thì ai biết H^n cũng tự tính được. "H^2" và "H" là các mắt xích dùng gần cuối chuỗi, không phải lần kế tiếp. "x (which is the original input of the hash chain)" là gốc bí mật, lộ nó thì cả chuỗi bị tính ra.

Đáp án đúng: "Strong collision resistance". Kháng va chạm mạnh (strong collision resistance, hay collision resistance) đòi hỏi không thể, bằng tính toán khả thi, tìm được bất kỳ cặp x ≠ y nào có H(x) = H(y); kẻ tấn công tự chọn cả hai đầu vào, nên tấn công ngày sinh chỉ cần cỡ 2^(n/2) phép băm với đầu ra n bit. Câu dẫn trộn hai định nghĩa: cụm "for any given input" là cách mở đầu định nghĩa kháng va chạm yếu, còn cụm quyết định là "find any pair", tức được tự chọn cả cặp, nên câu hỏi đang mô tả kháng va chạm mạnh. "Weak collision resistance" (kháng tiền ảnh thứ hai) khác đúng ở chỗ đó: cho trước một x cố định, không tìm được y ≠ x cùng giá trị băm; đầu vào bị ghim sẵn, chỉ được chọn một phía, chứ không phải tìm một cặp bất kỳ. "One-way property" là tính một chiều: cho trước giá trị băm h, không tìm được x nào có H(x) = h. "Pre-image resistance" là tên khác của chính tính một chiều đó, xuất phát từ một giá trị băm chứ không phải đi tìm cặp trùng nhau.

Đáp án đúng: "All the other choices". Hàm băm mật mã nhận đầu vào độ dài tuỳ ý và cho đầu ra độ dài cố định, và để dùng được trong bảo mật nó phải có cả ba tính chất an toàn cùng lúc. "Pre-image resistance" (kháng tiền ảnh, tính một chiều): cho giá trị băm h, không tìm được x có H(x) = h, nhờ đó băm mật khẩu hay chuỗi băm S/Key mới an toàn. "Second pre-image resistance" (kháng tiền ảnh thứ hai, kháng va chạm yếu): cho trước x, không tìm được y ≠ x có H(y) = H(x), giúp kẻ gian không thay được tài liệu đã ký. "Collision resistance" (kháng va chạm mạnh): không tìm được cặp x ≠ y bất kỳ cùng giá trị băm, chống tấn công ngày sinh. Mỗi tính chất đứng riêng chỉ là một mảnh của định nghĩa; thiếu bất kỳ tính chất nào, chẳng hạn MD5 đã mất kháng va chạm, thì hàm không còn được coi là hàm băm an toàn, nên chọn một tính chất đơn lẻ là chưa đủ.

Đáp án đúng gồm bốn ý: "Authenticator", "Tag", "Cryptographic checksum" và "Keyed hash". Mã xác thực thông điệp (message authentication code, MAC) là một giá trị ngắn tính từ thông điệp và một khoá bí mật chung, MAC = C(K, M), gắn kèm thông điệp để bên nhận tính lại và so sánh. Vì thế nó còn được gọi là bộ xác thực (authenticator), thẻ (tag) gắn theo thông điệp, tổng kiểm mật mã (cryptographic checksum) vì giống checksum nhưng phải có khoá mới tính được, và băm có khoá (keyed hash) khi xây từ hàm băm như HMAC. "Digital signature" không dùng thay được: chữ ký số dùng cặp khoá bất đối xứng, ký bằng khoá riêng và ai cũng kiểm được bằng khoá công khai, nên cho tính chống chối bỏ (non-repudiation); MAC dùng khoá đối xứng chung nên cả hai bên đều tạo được cùng một giá trị và không chống chối bỏ được.

Đáp án đúng: "15". Cây băm (hash tree, cây Merkle) với 128 khối dữ liệu là cây nhị phân có log2(128) = 7 tầng dưới gốc. Để khoanh vùng một khối lỗi, ta kiểm gốc trước (1 lần), rồi ở mỗi tầng kiểm cả hai nút con để biết nhánh nào sai và đi xuống nhánh đó (2 lần mỗi tầng); tổng là 1 + 2 × 7 = 15, ít hơn nhiều so với kiểm cả 128 khối. Phương án "11" ứng với 1 + 2 × 5, tức cây chỉ có 2^5 = 32 khối. Phương án "19" ứng với 1 + 2 × 9, tức 2^9 = 512 khối. Phương án "23" ứng với 1 + 2 × 11, tức 2048 khối. Phương án "27" ứng với 1 + 2 × 13, tức 8192 khối. Như vậy số lần kiểm tăng theo logarit số khối, đó chính là ưu điểm của cây băm.

Đáp án đúng: "True". NFT (Non-fungible Token, token không thể thay thế) là một token trên blockchain, thường theo chuẩn ERC-721 của Ethereum, mỗi token có mã định danh duy nhất và không hoán đổi ngang giá với token khác, khác với tiền mã hoá như Bitcoin, nơi mọi đơn vị có giá trị như nhau (fungible). Quyền sở hữu NFT được ghi trong sổ cái phân tán, xác thực bằng chữ ký số của chủ ví và bảo vệ toàn vẹn bằng hàm băm của các khối, nên người ta có thể mua bán, chuyển nhượng và sưu tầm chúng như tài sản mã hoá, thường gắn với tác phẩm số, vật phẩm trò chơi hay vé. Phát biểu đúng như vậy, nên không thể chọn "False"; lưu ý NFT chứng minh quyền sở hữu bản ghi token chứ không tự bảo đảm bản quyền của tệp gốc.

Đáp án đúng: "Independence across bits". Câu hỏi tìm thứ không phải yêu cầu an toàn của MAC. Yêu cầu chuẩn gồm: thấy M và MAC(K, M) thì không tạo được thông điệp khác cùng MAC, tức "Collision resistance" theo nghĩa khó giả mạo; MAC phân bố đều để mỗi lần đoán bừa thẻ n bit chỉ trúng với xác suất 2^(−n), tức "MAC code is uniformly distributed"; mỗi bit thẻ phụ thuộc mọi bit thông điệp, đổi một bit vào thì khoảng nửa số bit ra đổi theo, tức "Avalanche effect". "Large key size" cũng là yêu cầu thật: kẻ tấn công vét khoá k bit tốn cỡ 2^k phép thử, đoán thẻ tốn cỡ 2^n lần, nên công phá MAC cỡ min(2^k, 2^n); khoá 40 bit thì hàm MAC tốt đến đâu cũng bị vét khoá. "Independence across bits" không có trong danh sách đó; nó dễ bị nhầm với lở tuyết, nhưng lở tuyết là quan hệ giữa bit vào và bit ra chứ không phải giữa các bit ra với nhau. Nói thẳng: đáp án in kèm câu hỏi chọn "Large key size", coi độ dài khoá là tham số chứ không phải tính chất của hàm; lời giải này không theo vì thiếu khoá đủ dài thì các tính chất kia không chặn được vét cạn.

Đáp án đúng: "2^127 x". Câu hỏi viết "256-bit-long key" nhưng ý là giá trị băm dài n = 256 bit. Phá kháng va chạm mạnh (tìm một cặp bất kỳ trùng băm) nhờ nghịch lý ngày sinh cần cỡ 2^(n/2) = 2^128 phép băm, nên x = 2^128. Phá kháng va chạm yếu (cho trước một đầu vào, tìm đầu vào thứ hai cùng băm) không tận dụng được nghịch lý ngày sinh; theo quy ước của khoá học cho tấn công tiền ảnh thứ hai "trung bình", ta coi như vét cạn 2^256 giá trị băm và trúng sau một nửa, tức 2^(n−1) = 2^255 lần. Tỉ số là 2^255 / 2^128 = 2^127. Chỗ tranh cãi: "2^128 x" có cơ sở theo quy ước khác, vì nếu mỗi lần thử ngẫu nhiên trúng với xác suất 2^(−256) thì số lần thử kỳ vọng là 2^256 và tỉ số là 2^256 / 2^128 = 2^128; đáp án in kèm câu hỏi theo cách tính này, còn ở đây chọn theo quy ước khoá học và chữ "on average". "2^256 x" lấy số lần tuyệt đối của va chạm yếu làm tỉ số. "2^64 x" và "2^63 x" là tỉ số của hàm băm 128 bit (2^128 / 2^64 và 2^127 / 2^64), không phải 256 bit. "1x" coi hai tấn công tốn như nhau, trong khi va chạm yếu khó hơn rất nhiều.

Đáp án đúng: "Weak collision resistance". Kháng va chạm yếu (weak collision resistance), còn gọi là kháng tiền ảnh thứ hai, nói rằng cho trước một đầu vào x, không tính được trong thời gian khả thi một đầu vào y khác x sao cho H(y) = H(x); đúng như câu hỏi mô tả, vì đầu vào được cho sẵn. "Strong collision resistance" (kháng va chạm mạnh) đòi hỏi không tìm được bất kỳ cặp x khác y nào có cùng giá trị băm, kẻ tấn công được tự chọn cả hai, nên mạnh hơn và chỉ cần cỡ 2^(n/2) phép thử theo nghịch lý ngày sinh. "One-way property" và "Pre-image resistance" là cùng một tính chất: cho trước giá trị băm h, không tìm được đầu vào nào băm ra h; ở đó thứ được cho là đầu ra, không phải một đầu vào.

Đáp án đúng: "Digital signature protects the confidentiality of the data". Câu hỏi tìm phát biểu sai. Chữ ký số chỉ bảo đảm xác thực nguồn gốc, toàn vẹn và chống chối bỏ: người gửi ký giá trị băm của dữ liệu bằng khoá riêng, ai có khoá công khai cũng kiểm được, và dữ liệu vẫn gửi ở dạng rõ, nên chữ ký không che giấu nội dung; muốn bí mật phải mã hoá thêm. Các phát biểu sau đều đúng nên không được chọn: "Digital signature is based on asymmetric/public-key cryptography" đúng vì ký bằng khoá riêng, kiểm bằng khoá công khai (RSA, DSA, ECDSA). "Digital signature is typically smaller than the data size." đúng vì chỉ ký giá trị băm, chữ ký RSA 2048 bit dài 256 byte dù tệp lớn bao nhiêu. "Digital signature tends to require more computational resources than message authentication" đúng vì luỹ thừa modulo số lớn tốn hơn nhiều so với HMAC chỉ dùng hàm băm và khoá đối xứng.

Đáp án đúng: "Given an input, a hash function can produce multiple outputs.". Câu hỏi tìm phát biểu SAI. Hàm băm là hàm tất định: cùng một đầu vào luôn cho đúng một giá trị băm, nếu không bên nhận không thể tính lại để kiểm toàn vẹn hay xác minh chữ ký. Các phát biểu kia đều đúng nên không được chọn: "Across varying inputs, the output of the hash function needs to be uniformly distributed." đúng vì đầu ra phải trải đều, trông như ngẫu nhiên, để khó đoán và khó tìm va chạm; "The output size is fixed." đúng, ví dụ SHA-256 luôn ra 256 bit; "The input size can vary." đúng vì hàm băm nhận đầu vào độ dài tuỳ ý.

Đáp án đúng gồm ba ý: "Digest", "Hash value" và "Fingerprint". Hàm băm nhận đầu vào độ dài tuỳ ý và cho ra một chuỗi độ dài cố định, ví dụ 256 bit với SHA-256. Đầu ra này được gọi là giá trị băm (hash value), là bản tóm lược thông điệp (message digest, nên gọi tắt là digest), và cũng được gọi là dấu vân tay (fingerprint) vì nó đại diện gần như duy nhất cho dữ liệu: đổi một bit đầu vào thì đầu ra đổi hẳn, như vân tay nhận diện một người. "Message" là đầu vào của hàm băm, thứ được băm, chứ không phải đầu ra. "Cache" là vùng nhớ đệm lưu dữ liệu để truy cập nhanh; bảng băm có thể dùng làm bộ đệm nhưng đó không phải tên gọi đầu ra của hàm băm mật mã.

Đáp án đúng: "23". Trong cây băm (hash tree, cây Merkle), mỗi nút cha giữ băm của hai nút con; để khoanh vùng khối lỗi, ta kiểm gốc rồi đi xuống, ở mỗi tầng kiểm cả hai con của nút sai. Cây 128 khối sâu log2(128) = 7 tầng. Với hai khối lỗi có tổ tiên chung gần nhất ở độ sâu s, số lần kiểm là 1 + 2(s + 1) + 4(6 − s) = 27 − 2s: đoạn chung có một nút sai mỗi tầng (2 lần kiểm), sau chỗ tách có hai nút sai (4 lần kiểm). Cần nói thẳng: con số phụ thuộc vị trí hai khối lỗi mà đề không cho. Tách ngay dưới gốc (s = 0) cần 27 lần, đúng quy ước 4 × log2(n) − 1 (16 khối ra 15); tổ tiên chung ở độ sâu 2 cho 1 + 2 × 3 + 4 × 4 = 23 lần. "23" được chốt vì gần quy ước nhất trong các phương án. "15" chỉ đúng khi hai khối lỗi là hai lá anh em (s = 6, 1 + 2 × 7 = 15). "19" ứng với tổ tiên chung ở độ sâu 4 (27 − 8), cũng chỉ là một vị trí riêng. "11" nhỏ hơn cả 15 lần tối thiểu để lần qua 7 tầng, không thể xảy ra.

Đáp án đúng: "True". Mã hoá đối xứng có thể cung cấp xác thực thông điệp ở mức nhất định: chỉ người nắm khoá bí mật chung mới tạo được bản mã mà khi giải ra cho bản rõ hợp lệ, nên khi bên nhận giải mã được nội dung có cấu trúc mong đợi (văn bản có nghĩa, trường kiểm tra, mã kiểm lỗi nằm bên trong) thì có cơ sở tin thông điệp đến từ bên kia và không bị sửa. Tuy vậy, cách này phụ thuộc vào việc bản rõ có độ dư (redundancy) để nhận biết, nên trong thực tế người ta thường dùng thêm MAC hoặc mã hoá có xác thực như AES-GCM. "False" sai vì nó phủ nhận hoàn toàn khả năng này.