Mã Một Lần Và Bảo Mật Tuyệt Đối

Mã Một Lần Và Bảo Mật Tuyệt Đối

One Time Pad - OTP (Mã Một Lần) là một trong số rất ít những cryptosystem đạt được độ bảo mật tuyệt đối, kể cả đối với tiêu chuẩn ngày nay! Ta cũng sẽ đi đến định nghĩa "bảo mật" đối với cryptography, và đi đôi với nó sẽ phải trả cái giá nào, dẫn đến những cải tiến đối với những hệ thống chúng ta sử dụng ngày nay.

Và xin disclaim, OTP trong đây không có nghĩa giống như OTP mà các bạn thường nghe tới - One Time Password - đâu nha.

Mã Một Lần là gì?

Còn được biết đến là Vernam Cipher, ban đầu sử dụng punched tape (băng đục lỗ) khi kết hợp băng message (tin nhắn) với băng key. Từ "pad" từ cái tên bất nguồn từ những xấp giấy (pad of paper) sử dụng làm key.

Phép thực hiện OTP thường được biết đến là phép XOR, nhưng nhìn chung thì những
phương thức mã hóa bằng cách cộng modulo đều là OTP. Thật vậy, XOR chỉ là phép
cộng modulo 2.

Nếu bạn nhớ lại thì Vigenere Cipher sử dụng phép cộng modulo 26, có nghĩa là
Vigenere Cipher là OTP chăng?

OTP có 1 điều kiện quan trọng: Độ dài key phải ít nhất dài bằng độ dài plaintext.
Nếu key dài hơn message thì ta có thể lờ đi phần cuối của key.

Dưới những điều kiện này, ta sẽ lấy ví dụ plaintext = hello và key = xmckl, 1
string ngẫu nhiên.
Giờ ta thực hiện phép cộng modulo 26, giống Vigenere Cipher:

   7 (h)   4 (e)  11 (l)  11 (l)  14 (o)  message
+ 23 (x)  12 (m)   2 (c)  10 (k)  11 (l)  key
= 30      16      13      21      25      message + key
=  4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) (message + key) mod 26
      E       Q       N       V       Z   CIPHERTEXT

Decryption thì không khó đoán, ta sẽ thực hiện phép trừ modulo 26.
Có lẽ bạn đang thắc mắc: Vậy nó cũng giống như Vigenere Cipher thôi, làm sao nó
"bảo mật tuyệt đối" được?

Để hình dung, ta sẽ giới thiệu cuộc giao tiếp giữa 2 nhân vật Alice và Bob, và họ
đều có key = xmckl.

Alice muốn gửi tin nhắn "hello" cho Bob, nhưng encrypt bằng key thành "EQNVZ" nhằm
ngăn chặn những người nghe lén (eavesdropper) đọc được tin nhắn.

Bob nhận tin "EQNVZ" là ciphertext, sẽ sử dụng key để decrypt và thu lại được tin
"hello".

Giờ ta giả sử có eavesdropper tên là Eve chặn được tin "EQNVZ". Cô có thể brute
force, thu được key xmckl, và phá được tin nhắn "hello", nhưng cô cũng có thể thu
key tquri và decrypt thành tin nhắn "later" và cả hai đều hợp lí.

Thực ra, Eve sẽ tìm được nhiều key khác nhau, và mỗi key cho ra 1 plaintext có nghĩa
với độ dài là 5. Và vì xác suất đúng của mỗi key là như nhau, Eve sẽ không có cách
nào biết key nào là chính xác.

Vậy nếu kẻ tấn công chỉ đơn thuần cố tìm key từ ciphertext (Ciphertext Only Attack), sẽ không có cách nào biết key nào là chính xác, dẫn tới plaintext thật sự.

Thế còn Known Plaintext Attack thì sao? Cái tên có từ "one time" ám chỉ rằng key sẽ chỉ được dùng 1 lần. Vì thế, kể cả khi mà phá được key thì key đó cũng coi như vứt bỏ, vì nó sẽ không được sử dụng lần thứ hai. Thực chất, trong khoảng thời gian đầu sử dụng, OTP thiếu bảo mật là do những băng đục lỗ đôi khi có pattern lặp lại, vậy là có key được dùng tới lần thứ hai. Việc sử dụng một lần được áp dụng sau đó, khi tính chất bảo mật tuyệt đối được phát hiện.

Tuy nhiên, "bảo mật tuyệt đối" không có nghĩa là cipher an toàn tuyệt đối trước mọi loại tấn công. An toàn, ít nhất chỉ là trước những eavesdropper.

Perfect Security

Lý thuyết này được Claude Shannon, một nhà toán học, kĩ sư điện tử, và cryptographer, đề cập tới trong tài liệu mật "Communication Theory of Secrecy Systems" vào năm 1949.

Vậy "bảo mật tuyệt đối" là như thế nào?

Câu trả lời ngắn gọn: ciphertext không nên để lộ bất kì thông tin gì về plaintext.

Câu trả lời ngắn gọn khác: Tin nhắn phải hoàn toàn độc lập so với tin mật, tức là cả hai không có mối quan hệ gì với nhau hết (mối quan hệ có thể là bằng nhau, tổng bằng một số đặc biệt nào đó, v.v.)

Câu trả lời phức tạp: Cho (E, D) là một cipher qua các tập hợp (K, M, C) (E là thuật toán encryption, D là thuật toán decryption; K là tập hợp các key, M là tập hợp các tin nhắn - message, C là tập hợp các tin mật - ciphertext.) Ngoài ra, xác suất xuất hiện của mỗi key trong tập K là như nhau. Thế thì, với bất kì 2 tin nhắn m0, m1 nào trong M và bất kì tin mật c nào trong C thì:

Pr[E(k, m0) = c] = Pr[E(k, m1) = c]

Trong đó Pr chỉ xác suất xảy ra của một sự kiện. Tức Pr[E(k, m0) = c] là xác suất mà encryption của m0 dưới key k thành c. Hiểu đơn giản là thế này, mọi tin nhắn đều có xác suất bằng nhau là decryption của một tin mật cho trước, khi ta không biết chìa khóa. Lấy lại ví dụ phía trên, khi Eve cố gắng decrypt tin "EQNVZ", cô không có cách nào biết được tin nhắn thật sự là "hello" hay "later" hay bất cứ từ 5 chữ nào khác, xác suất mỗi tin nhắn đúng là như nhau trừ khi ta có key để xác nhận.

Bằng tổ hợp xác suất, ta hoàn toàn có thể chứng minh được tính bảo mật tuyệt đối này của OTP.

Tuy nhiên, hãy hình dung. Nếu Alice và Bob sử dụng OTP để trao đổi một file 1GB qua lại cho nhau, họ cần phải chia sẻ trước key bí mật cũng 1GB! Điều này hoàn toàn không thiết thực, nhưng lý thuyết về bảo mật tuyệt đối không cho phép chúng ta tối ưu hóa độ dài của key hơn nữa.

Shannon cũng đã thiết lập rằng, một điều kiện cần của tính chất bảo mật tuyệt đối là: Tập hợp key phải lớn hơn tập hợp message: |K| > |M|. Điều này ám chỉ rằng key không thể ngắn hơn message, chỉ có thể dài bằng hoặc hơn.

Vậy tức là OTP là cipher tối ưu nhất mà có thể mang tính chất "bảo mật tuyệt đối". Và như ta đã đề cập, xách theo cả 1 cái key 1GB chỉ để bảo vệ 1 cái file 1GB là thật không tốt cho cái bộ nhớ tí nào.

Dẫu vậy, OTP mang lại một ý tưởng tuyệt vời cho các nhà phát minh và thiết kế cryptosystem trong tương lai. Phép XOR (hay phép cộng modulo nói chung) là một phép hoàn hảo để mang lại xác suất cân bằng hơn đối với các key ngẫu nhiên. Ta chỉ cần tìm cách để cải tiến những nhược điểm sau:

  • Key cần phải ngắn hơn (những key thông dụng sẽ dài từ 128 đến 2048 bit)
  • Xác suất không nhất thiết phải cân bằng hoàn toàn, có thể khác biệt đến một mức độ rất sát 0 (cỡ     2-100 được coi là an toàn với tiêu chuẩn hiện nay)

và ta sẽ tìm hiểu về những cải tiến này trong một bài viết tương lai, với một lớp cipher hiện đại mà công cụ chính là phép XOR, giống OTP.

Để kết thúc bài viết này, mình xin đề cập một điểm "thiếu an toàn" của bảo mật tuyệt đối. "Bảo mật" ở đây chỉ bảo vệ chúng ta trước những kẻ nghe lén, nhưng hoàn toàn bất lực trước những kẻ tấn công mạnh hơn, có thể chỉnh sửa tin nhắn.

Ta sẽ gặp lại những người bạn Alice và Bob của chúng ta, và kẻ tấn công Eve.

Lần này, đến lượt Bob gửi tin nhắn cho Alice, cũng mã hóa bằng OTP.

Eve chặn được tin nhắn của Bob. Không may thay, Eve biết được chính xác những
từ đầu tiên của tin nhắn là: "From: Bob". Vì Eve biết tin được mã hóa bằng OTP,
cô có thể lợi dụng tính chất của OTP và chỉnh sửa trực tiếp ciphertext, sao cho
plaintext tương ứng sẽ thành "From: Eve".

Eve truyền tin nhắn lại cho Alice, và khi Alice giải mã, cô sẽ thấy tin nhắn
này là "From: Eve", tức là cô sẽ thực sự nghĩ tin nhắn này là tới từ Eve, không
phải là từ Bob. Và Alice không có cách nào để xác minh.

Đây là một điều rất tệ trong cryptography, nhưng ta thấy rằng điều này xảy ra
thường xuyên trên thế giới mạng trong cuộc sống hàng ngày. Như vậy, ta cần phải
có biện pháp để ngăn chặn những kiểu tấn công "chủ động" này.

Tạm kết

Đến đây thì ta mới chính thức kết thúc hành trình qua chiều dài lịch sử cryptography, khi ta khám phá OTP - một hệ thống từ thế kỉ XX, bảo mật nhưng không thực tế, và là nền móng quan trọng cho những hệ thống hiện nay.

Như thường lệ, hy vọng các bạn thưởng thức bài viết này :) Hãy đón xem những bài viết tiếp theo nhé!