Mật mã hậu lượng tử - thuật toán mới "ra đời sau 60 phút"

Chúng tôi đã viết về PQC, viết tắt của mật mã hậu lượng tử, nhiều lần trước đây.

Trong trường hợp bạn đã bỏ lỡ tất cả sự phấn khích của giới truyền thông trong vài năm qua về cái gọi là điện toán lượng tử…

… Đó là (nếu bạn sẽ tha thứ cho điều mà một số chuyên gia có thể sẽ coi là đơn giản hóa quá liều lĩnh) là một cách xây dựng các thiết bị máy tính có thể theo dõi nhiều kết quả có thể xảy ra của một phép tính cùng một lúc.

Với rất nhiều sự cẩn thận và có lẽ một chút may mắn, điều này có nghĩa là bạn có thể viết lại một số loại thuật toán để có câu trả lời đúng hoặc ít nhất là loại bỏ chính xác toàn bộ câu trả lời sai mà không cần thử và kiểm tra mọi kết quả có thể xảy ra từng cái một.

Hai tốc độ phân tích mật mã thú vị có thể thực hiện được bằng cách sử dụng thiết bị tính toán lượng tử, giả sử rằng một thiết bị có thể thực sự được xây dựng mạnh mẽ và đáng tin cậy một cách phù hợp:

• Thuật toán tìm kiếm lượng tử của Grover. Thông thường, nếu bạn muốn tìm kiếm một nhóm câu trả lời được sắp xếp ngẫu nhiên để xem liệu câu trả lời của bạn có trong danh sách hay không, thì tệ nhất là bạn sẽ phải xem qua toàn bộ danh sách trước khi nhận được câu trả lời dứt khoát. Ví dụ: nếu bạn muốn tìm khóa giải mã AES 128 bit để giải mã tài liệu, bạn cần tìm kiếm danh sách tất cả các khóa có thể có, bắt đầu từ 000..001, ..2, ..3, v.v., cho đến FFF..FFF (Giá trị 16 byte của FF), để chắc chắn hoàn thành vấn đề. Nói cách khác, bạn phải có ngân sách để thử cả 2¹²⁸ chìa khóa khả thi trước khi tìm đúng chìa khóa hoặc xác định rằng không có chìa khóa. Tuy nhiên, thuật toán của Grover với một máy tính lượng tử đủ lớn và mạnh mẽ, tuyên bố có thể hoàn thành kỳ tích tương tự với căn bậc hai của nỗ lực thông thường, do đó bẻ khóa mã, về lý thuyết, chỉ trong 2⁶⁴ thay vào đó hãy thử.
• Thuật toán phân tích thừa số lượng tử của Shor. Một số thuật toán mã hóa hiện đại dựa trên thực tế rằng việc nhân hai số nguyên tố lớn với nhau có thể được thực hiện nhanh chóng, trong khi việc chia tích số của chúng trở lại thành hai số mà bạn đã bắt đầu là điều không thể. Để cảm nhận điều này, hãy thử nhân 59 × 87 bằng bút và giấy. Có thể mất một phút hoặc lâu hơn để lấy nó ra (5133 là câu trả lời), nhưng nó không khó lắm. Bây giờ hãy thử cách khác. Chia, giả sử, 4171 trở lại thành hai yếu tố của nó. Khó hơn nhiều! (Nó là 43 × 97.) Bây giờ hãy tưởng tượng làm điều này với một số có độ dài 600 chữ số. Nói một cách dễ hiểu, bạn đang gặp khó khăn với việc cố gắng chia số 600 chữ số cho mỗi số nguyên tố có thể có 300 chữ số cho đến khi bạn trúng giải độc đắc hoặc nhận thấy không có câu trả lời. Tuy nhiên, thuật toán của Shor hứa hẹn sẽ giải quyết vấn đề này với logarit của nỗ lực thông thường. Do đó, việc bao thanh toán một số gồm 2048 chữ số nhị phân sẽ mất thời gian gấp đôi so với việc bao thanh toán một số 1024 bit, không lâu gấp đôi so với việc bao thanh toán một số 2047 bit, thể hiện một tốc độ rất lớn.

Chống lại mối đe dọa

Mối đe dọa từ thuật toán của Grover có thể được đối phó đơn giản bằng cách tăng kích thước của các số bạn đang sử dụng bằng cách bình phương chúng, có nghĩa là tăng gấp đôi số bit trong hàm băm mật mã hoặc khóa mã hóa đối xứng của bạn. (Nói cách khác, nếu bạn cho rằng SHA-256 là ổn ngay bây giờ, thì việc sử dụng SHA-512 thay thế sẽ cung cấp một giải pháp thay thế kháng PQC.)

Nhưng thuật toán của Shor không thể bị phản công dễ dàng như vậy.

Khóa công khai 2048 bit sẽ cần kích thước của nó tăng lên theo cấp số nhân, không chỉ đơn giản bằng cách bình phương, để thay vì khóa 2 × 2048 = 4096 bit, bạn cần một khóa mới với kích thước không thể là 2²⁰⁴⁸ chút ít…

… Hoặc bạn phải áp dụng một loại hệ thống mã hóa hậu lượng tử hoàn toàn mới mà thuật toán của Shor đã không áp dụng.

Chà, cơ quan tiêu chuẩn Hoa Kỳ NIST đã chạy một PQC "cạnh tranh" kể từ cuối năm 2017.

Quá trình này đã được mở cho tất cả mọi người, với tất cả những người tham gia được chào đón, tất cả các thuật toán được công bố công khai và sự giám sát công khai không chỉ có thể mà còn tích cực khuyến khích:

Kêu gọi Đề xuất. [Đóng cửa từ ngày 2017 tháng 11 năm 30]. […] Dự kiến, các tiêu chuẩn mật mã khóa công khai mới sẽ chỉ định một hoặc nhiều bổ sung chữ ký số chưa được phân loại, tiết lộ công khai, mã hóa khóa công khai và thuật toán thiết lập khóa khả dụng trên toàn thế giới và có khả năng bảo vệ thông tin nhạy cảm của chính phủ trong tương lai gần, kể cả sau sự ra đời của máy tính lượng tử.

Sau ba vòng đệ trình và thảo luận, NIST đã thông báo, vào ngày 2022-07-05, nó đã chọn bốn thuật toán mà nó coi là "tiêu chuẩn" có hiệu lực ngay lập tức, tất cả đều có những cái tên nghe có vẻ tinh tế: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONvà SPHINCS+.

Cái đầu tiên (CRYSTALS-KYBER) được sử dụng như những gì được gọi là Cơ chế thỏa thuận chính (KEM), trong đó hai đầu của một kênh giao tiếp công khai kết hợp an toàn khóa mã hóa riêng tư dùng một lần để trao đổi giá trị dữ liệu của phiên một cách bí mật. (Chỉ cần đặt: những kẻ rình mò chỉ nhận được bắp cải cắt nhỏ, vì vậy họ không thể nghe trộm cuộc trò chuyện.)

Ba thuật toán khác được sử dụng cho Chữ ký số, nhờ đó bạn có thể đảm bảo rằng dữ liệu bạn lấy ra ở cuối trùng khớp chính xác với những gì người gửi đưa vào ở người khác, do đó ngăn chặn việc giả mạo và đảm bảo tính toàn vẹn. (Chỉ cần đặt: nếu có ai đó cố gắng làm hỏng hoặc xáo trộn dữ liệu, bạn sẽ biết.)

Cần nhiều thuật toán hơn

Đồng thời khi công bố các tiêu chuẩn mới, NIST cũng công bố vòng thứ tư cạnh tranh của nó, đưa thêm bốn thuật toán về phía trước như là KEM thay thế có thể. (Hãy nhớ rằng, tại thời điểm viết bài, chúng tôi đã có ba thuật toán chữ ký số được phê duyệt để lựa chọn, nhưng chỉ có một KEM chính thức.)

Đây là những: BIKE, Classic McEliece, HQC và SIKE.

Thật hấp dẫn, Thuật toán McEliece được phát minh từ những năm 1970 bởi nhà mật mã học người Mỹ Robert Mc Eliece, người đã qua đời vào năm 2019, ngay sau khi cuộc thi của NIST đã được tiến hành.

Tuy nhiên, nó không bao giờ thành công vì nó đòi hỏi một lượng lớn vật liệu quan trọng so với giải pháp thay thế phổ biến hiện nay, thuật toán Diffie-Hellman-Merkle (DHM, hoặc đôi khi chỉ là DH).

Thật không may, một trong ba thuật toán của Vòng Bốn, cụ thể là SIKE, dường như đã bị bẻ khóa.

Trong một bài báo xoắn não có tựa đề MỘT CÔNG CỤ KHÔI PHỤC CHÍNH HIỆU QUẢ TRÊN SIDH (PHIÊN BẢN CHÍNH), Các nhà mật mã học người Bỉ Wouter Castryk và Thomas Decru dường như đã giáng một đòn chí mạng vào thuật toán SIKE

Trong trường hợp bạn đang thắc mắc, SIKE là viết tắt của Đóng gói khóa Isogeny siêu cấpvà SIDH là viết tắt của Siêu dị thường Isogeny Diffie-Hellman, một cách sử dụng cụ thể của Thuật toán SIKE theo đó hai đầu của một kênh giao tiếp thực hiện “mật mã” giống như DHM để trao đổi một loạt dữ liệu công khai cho phép mỗi đầu lấy một giá trị riêng tư để sử dụng làm khóa mã hóa bí mật một lần.

Chúng tôi sẽ không cố gắng giải thích cuộc tấn công ở đây; chúng tôi sẽ chỉ lặp lại những gì bài báo tuyên bố, cụ thể là:

Nói một cách dễ hiểu, đầu vào ở đây bao gồm dữ liệu công khai được cung cấp bởi một trong những người tham gia mật mã thiết lập khóa, cùng với các tham số được xác định trước (và do đó được công khai) được sử dụng trong quy trình.

Nhưng đầu ra được trích xuất (thông tin được gọi là isogeny φ ở trên) được cho là phần không bao giờ được tiết lộ của quy trình - cái gọi là khóa riêng.

Nói cách khác, chỉ từ thông tin công khai, chẳng hạn như dữ liệu được trao đổi công khai trong quá trình thiết lập khóa, các nhà mật mã tuyên bố có thể khôi phục khóa cá nhân của một trong những người tham gia.

Và một khi bạn biết khóa riêng của tôi, bạn có thể dễ dàng và không bị phát hiện giả mạo là tôi, do đó quá trình mã hóa bị hỏng.

Rõ ràng, thuật toán bẻ khóa mất khoảng một giờ để thực hiện công việc của nó, chỉ sử dụng một lõi CPU duy nhất với loại sức mạnh xử lý mà bạn tìm thấy trong một máy tính xách tay hàng ngày.

Điều đó chống lại thuật toán SIKE khi được định cấu hình để đáp ứng Cấp độ 1, cấp độ bảo mật mã hóa cơ bản của NIST.

Phải làm gì?

Không có gì!

(Đó là tin tốt.)

Như các tác giả của bài báo đề xuất, sau khi lưu ý rằng kết quả của họ vẫn còn sơ bộ, "Với tình hình hiện tại, SIDH dường như bị phá vỡ hoàn toàn đối với bất kỳ đường cong cơ sở nào được tạo công khai."

(Đó là tin xấu.)

Tuy nhiên, cho rằng thuật toán SIKE chưa được chính thức phê duyệt, hiện tại nó có thể được điều chỉnh để ngăn chặn cuộc tấn công cụ thể này (điều mà các tác giả thừa nhận là có thể xảy ra), hoặc đơn giản là loại bỏ hoàn toàn.

Bất cứ điều gì cuối cùng xảy ra với SIKE, đây là một lời nhắc nhở tuyệt vời về lý do tại sao việc cố gắng phát minh ra các thuật toán mã hóa của riêng bạn lại đầy rẫy nguy hiểm.

Đây cũng là một ví dụ điển hình về lý do tại sao các hệ thống mã hóa độc quyền dựa vào tính bí mật của chính thuật toán để duy trì an ninh của họ đơn giản là không thể chấp nhận được vào năm 2022.

Nếu một thuật toán PQC như SIKE tồn tại bền bỉ và được các chuyên gia trên toàn cầu thăm dò trong hơn năm năm, mặc dù đã được tiết lộ cụ thể để nó có thể bị công chúng giám sát…

… Thì không cần phải tự hỏi bản thân rằng các thuật toán mã hóa ẩn từ chế độ xem được tạo ra tại nhà của bạn có khả năng hoạt động tốt như thế nào khi được tung ra môi trường tự nhiên!

---