Giảm từ đa người dùng thành một người dùng
Trước tiên, vui lòng lưu ý rằng có sự giảm thiểu giữa bảo mật nhiều người dùng và bảo mật một người dùng tiêu chuẩn cho sơ đồ chữ ký:
nó đã được chứng minh vào năm 2002 bởi Galbraith, Malone-Lee và Smart (GSM) rằng đối với bất kỳ hệ thống chữ ký nào, tấn công lược đồ trong cài đặt nhiều người dùng với $N$ khóa công khai không thể tăng tỷ lệ thành công của kẻ tấn công (là thương số của xác suất thành công và thời gian chạy của nó) nhiều hơn một hệ số. $N$ so với việc tấn công lược đồ trong cài đặt một người dùng.
Đây là một kết quả mạnh mẽ, sử dụng ký hiệu của bạn, điều đó có nghĩa là trong cài đặt MU, giới hạn của bạn bị giới hạn bởi $\frac{Nt}{2^k}$ bạn có $\frac{t}{2^k}$ trong cài đặt SU.
NHƯNG chúng tôi không biết bất kỳ cuộc tấn công thực tế nào đạt được giới hạn như vậy đối với các sơ đồ chữ ký. Lưu ý rằng nếu đúng như vậy, nếu chúng ta có một N lớn chẳng hạn như 2^32 chẳng hạn, thì tác động đến tính bảo mật của các sơ đồ chữ ký sẽ rất lớn!
Chúng tôi thường thích chặt chẽ hơn sự cắt giảm.
Chú ý rằng các cuộc tấn công chống lại các chương trình chữ ký trong cài đặt nhiều người dùng không được trộn lẫn với các cuộc tấn công chống lại MAC trong cài đặt đó, không nhất thiết phải tốt như các sơ đồ chữ ký như đã thảo luận trong phần xuất sắc "Một cái nhìn khác về Độ kín" bài viết của Chatterjee, Menezes và Sarkar và phần tiếp theo của nó"Một cái nhìn khác về Độ kín II". Cả hai đều là những bài đọc xuất sắc về những vấn đề kiểu này.
Tôi khuyên bạn cũng nên đọc "An ninh của sơ đồ chữ ký trong cài đặt nhiều người dùng" của Menezes và Smart từ năm 2004, vì nó liên quan đến các định nghĩa bảo mật trong cài đặt MU cho các lược đồ chữ ký:
chúng tôi lập luận rằng định nghĩa bảo mật được chấp nhận rộng rãi cho các lược đồ chữ ký (không thể giả mạo tồn tại đối với các cuộc tấn công thông điệp được chọn thích ứng) của Goldwasser et al. [18] không đủ cho cài đặt nhiều người dùng. May mắn thay, có vẻ như định nghĩa này có thể dễ dàng được mở rộng để tính đến các cuộc tấn công này trong cài đặt nhiều người dùng.
Họ cũng quan tâm đến cái gọi là "Các cuộc tấn công thay thế chính" được đề cập trong định nghĩa của họ.
Đáng chú ý nhất (nhấn mạnh của tôi):
Trong Phần 2.2, chúng tôi đã lập luận rằng kẻ thù của sơ đồ chữ ký trong cài đặt nhiều người dùng sẽ thành công nếu nó tạo ra sự giả mạo tồn tại hoặc thay thế khóa. Trong cả hai trường hợp, cuộc tấn công nhằm vào một khóa công khai cụ thể. Do đó, chỉ cần xem xét cài đặt nhiều người dùng trong đó ban đầu chỉ có một khóa chung. Điều này không làm mất đi tính tổng quát vì đối thủ tấn công một thực thể có thể mô phỏng các thực thể khác bằng cách chọn các khóa công khai của chúng để nó biết các khóa riêng tương ứng.
Rõ ràng là, một đối thủ trong cài đặt một người dùng sẽ tự nhiên giảm xuống một đối thủ trong cài đặt nhiều người dùng.
Và họ cũng kết luận rằng không có thực cần lo lắng về cài đặt nhiều người dùng cho các sơ đồ chữ ký ngay khi chúng tôi có thể liên kết chúng với khóa chung và có một kết quả rất thú vị:
Các lược đồ chữ ký được bảo mật trong cài đặt một người dùng có thể dễ dàng được chuyển đổi thành các lược đồ được bảo mật theo định nghĩa mới của chúng tôi trong cài đặt nhiều người dùng bằng cách băm khóa chung cùng với thông báo khi tính toán thông báo tóm tắt
N.B: điều này đáng chú ý giải thích lý do tại sao chúng tôi thêm khóa công khai vào thông báo tóm tắt trong sơ đồ chữ ký "giống Schnorr" "EdDSA“.
(Thực ra cũng có thể là do DJB tìm thấy một lỗ hổng trong việc giảm từ cài đặt một người dùng sang cài đặt nhiều người dùng đã được GSM đưa ra vào năm 2002, nhưng trong khi đó chúng tôi có bằng chứng khác điều đó cho thấy nó không cần thiết đối với chữ ký của Schnorr... Nhưng DJB đã dogfood khi anh ấy tạo EdDSA, tôi đoán vậy ;))
Mô hình tấn công nhiều người dùng cho lược đồ chữ ký
Ngoài ra, vui lòng lưu ý rằng mô hình tấn công giả mạo trong cài đặt nhiều người dùng là đối thủ được cung cấp $n$ ký lời tiên tri, một cho mỗi khóa công khai, và được phép thực hiện tối đa $q$ truy vấn đến các oracle này.
Khi kết thúc cuộc tấn công, đối thủ phải xuất trận (với xác suất nhiều nhất là $\epsilon$) một bộ chứa:
- một trong những $n$ khóa công khai, $y$
- một thông điệp $m$
- một chữ ký $\sigma$,
sao cho chữ ký $\sigma$ là hợp lệ cho tin nhắn $m$ dưới khóa công khai $y$.
Ở đâu $m$ lẽ ra không phải là một truy vấn đối với nhà tiên tri ký tương ứng với khóa đó $y$.
Độ an toàn của sơ đồ như vậy sau đó được xác định tùy thuộc vào $q$, $n$.
Đây được gọi là mô hình "nhiều người dùng không thể sửa chữa trước các cuộc tấn công thông báo đã chọn" (MU-UF-CMA).
Về ý nghĩa của bảo mật cho các chương trình chữ ký
Ngoài ra, trước khi "xác định" bảo mật cho sơ đồ chữ ký trong bất kỳ cài đặt nào, chúng ta cần biết "loại bảo mật nào" mà chúng ta đang cố gắng đạt được.
Thật tuyệt khi nói rằng "sơ đồ chữ ký mang lại k-bit bảo mật trong cài đặt một người dùng", nhưng chống lại loại tấn công nào?
Về chủ đề đó, các giấy tinh dịch của Goldwasser, Micali và Rivest là một cuốn sách hay, mặc dù chắc chắn là hơi lỗi thời và thiếu một chút về cài đặt nhiều người dùng.
Khái niệm phổ biến nhất về bảo mật cho sơ đồ chữ ký được gọi là "EUF-CMA" có nghĩa là "không thể giả mạo tồn tại dưới các cuộc tấn công thông điệp được chọn thích ứng", nghĩa là kẻ thù sẽ khó đưa ra một thông báo "giả mạo" cho một được cấp khóa công khai.
(Cũng có một khái niệm về SUF-CMA "Khả năng không thể thay đổi tồn tại mạnh mẽ trong cuộc tấn công bằng tin nhắn được chọn", đang cố gắng giảm tính linh hoạt của các lược đồ chữ ký)
Nhưng trong cài đặt nhiều người dùng, có một khái niệm khác thú vị, đó là khái niệm "Tấn công thay thế chính" (KSA), nơi chúng tôi có thể tạo khóa công khai mới cũng sẽ xác minh một cặp (tin nhắn, chữ ký) nhất định. Và có các cuộc tấn công thay thế khóa trong các sơ đồ chữ ký EUF-CMA có thể chứng minh được an toàn! (Ví dụ: trong NTRUSign hoặc trong "Short sơ đồ chữ ký không có lời tiên tri ngẫu nhiên")
Điều thực sự thú vị với KSA, đó là một người ký ác ý cũng có thể là một diễn viên trong bối cảnh như vậy!
Trên k-bit bảo mật
Cuối cùng, "có k-bit bảo mật" thực sự là chống lại một số mô hình tấn công (nhưng cái nào?) và thực sự là một cách để chúng ta so sánh mật mã khóa công khai với các cuộc tấn công mật mã/bruteforce khóa đối xứng. Đó là cách chúng tôi sử dụng để có một số liệu cho phép chúng tôi so sánh chúng, nhưng đôi khi khá khó để đánh giá một cách tuyệt đối.
Có những giấy tờ như những cái trên https://www.keylength.com/ cho phép bạn thấy các cách khác nhau mà chúng tôi phải "ước tính" tính bảo mật của tiền điện tử bất đối xứng khi so sánh với tiền điện tử đối xứng và như bạn có thể thấy ở đó, các giá trị đang thay đổi từ tờ báo này sang tờ báo khác.
Cuối cùng, những gì chúng tôi đang cố gắng đánh giá với số liệu k-bit là độ khó của việc phá vỡ một sơ đồ nào đó khi so sánh với một cuộc tấn công vũ phu. (Tôi khuyên bạn nên đọc bài luận này của DJB về các cuộc tấn công vũ phu.)
Nhưng đó là sử dụng tốt nhất đã biết các cuộc tấn công chống lại các lược đồ khóa công khai này và do đó, nó không phải là tuyệt đối, nó là một biện pháp tương đối.
định nghĩa của bạn, sử dụng $t/2^k$ đại khái là một cuộc tấn công vũ phu:
số lần thử chia cho "số tối đa".
Vì vậy, những gì bạn đang nói về cơ bản là chúng tôi định nghĩa "có k-bit bảo mật" là "khó như một cuộc tấn công vũ phu vào khóa k-bit", điều mà tôi hoàn toàn đồng ý. Chúng tôi làm.
Nhưng một "định nghĩa đúng đắn về Bảo vệ" đối với các sơ đồ chữ ký khóa công khai sẽ không dựa vào khái niệm "bit bảo mật". Nó vẫn có khái niệm về tham số bảo mật $k$ và nó vẫn đang sử dụng một giá trị $\mathbb{1}^k$ thường là đầu vào, nhưng nó được sử dụng như một cách để hạn chế kẻ thù thực hiện ít hơn một cuộc tấn công vũ phu đơn thuần và do đó cũng là đầu vào cho kẻ thù, nhưng nó sẽ được xác định bằng cách sử dụng một số mô hình tấn công như trên.
Đây là lý do tại sao tôi đã thảo luận về "mô hình tấn công" trước đây và thực sự không thể cung cấp cho bạn định nghĩa tốt hơn "Vâng, chắc chắn rồi: lý tưởng nhất là bruteforce phải có cùng độ khó như trong cài đặt một người dùng đối với hành vi giả mạo trong cài đặt nhiều người dùng".
Nhưng vì chúng tôi không có mức giảm chung "chặt chẽ" hơn mức đó, nên chúng tôi không thể nói chắc liệu đó có thực sự là trường hợp hay không nói chung. Nhưng nó chắc chắn là trường hợp của chữ ký Schnorr theo cả hai ở trên liên kết giấy tờ.
Lưu ý rằng câu trả lời của fgrieu cũng gợi ý về khái niệm chặt chẽ đó, nhưng từ quan điểm ngược lại.
