Các bit bảo mật tương đối của các chức năng chậm hơn

Bỏ qua các giả định về độ cứng của bộ nhớ, một số hàm băm chậm là các phiên bản chuỗi băm muối được lặp lại của các hàm băm mật mã thông thường. Điều này thường được xác định bởi một vòng tham số tức là trong PBKDF2. Có tài liệu mật mã nào đề cập đến định nghĩa bit bảo mật dựa trên hệ số vòng của các lời gọi liên tiếp tuyến tính (không song song) cho một tính toán đầu ra?

Tức là, một ví dụ cụ thể: đang phá vỡ hình ảnh trước của sha3(fresh_salt, input_value) dễ hơn sha3(sha3(sha3(sha3(fresh_salt, input_value)))) đối với một số entropy thấp giá trị đầu vào (tức là 64 bit) và nếu có cái sau có cung cấp thêm 2 bit bảo mật không vì nỗ lực tương đối mà kẻ tấn công yêu cầu gấp 4 lần? Bất kỳ tài liệu nghiên cứu nào thảo luận về điều đó (nỗ lực đối nghịch tương đối cần thiết giữa các chức năng độc lập hoặc phụ thuộc tuyến tính so với các bit thực dụng của bảo mật được cung cấp)?

• Câu hỏi này tương tự như Ý nghĩa bảo mật của hàm băm chậm theo thiết kế đối với bảo mật tương đối so với kích thước hàm băm, nhưng tôi chủ yếu quan tâm đến câu trả lời liên quan đến bằng chứng bảo mật.

Đã có những quan niệm tinh tế về ý nghĩa của việc một giao thức có $\lambda$-bit bảo mật. Người nổi tiếng nhất có lẽ là Micciancio-Walter Về bảo mật bit của mật mã nguyên thủy.

Khái niệm về bảo mật bit sẽ khác nhau cho dù một người đang làm việc với một

• trò chơi quyết định, nó ở đâu $\min_A\log_2 \frac{T(A)}{(\mathsf{adv}^A)^2}$, tức là quy mô bậc hai với lợi thế đối thủ, hoặc

• trò chơi tìm kiếm, nó ở đâu $\min_A \log_2 \frac{T(A)}{\mathsf{adv}^A}$, tức là quy mô tuyến tính với lợi thế đối phương.

Các $\min_A$ là giảm thiểu trên tất cả các đối thủ tấn công một nguyên thủy, và $T(A)$ là thời gian chạy của $A$. Lưu ý rằng lợi thế cho trò chơi tìm kiếm/quyết định được định nghĩa khác nhau (đối với trò chơi tìm kiếm, đó là xác suất thành công đại khái, đối với trò chơi quyết định, nó là $2\delta-1$, ở đâu $\delta$ là xác suất thành công).

Dù sao, trong khuôn khổ này, bạn có thể cố gắng chứng minh điều gì đó như

Nếu $H(\cdot)$ là một hàm băm $\kappa$-bit chống hình ảnh trước, sau đó $H^{\circ k}(\cdot)$, các $k$-lần thành phần của $H$, Là $(\log_2(k) + \kappa)$-bit trước hình ảnh kháng.

Bằng chứng đại khái như sau

1. Bắt đầu với $\min_A \log_2 \frac{T(A)}{\mathsf{adv}_H^A}\geq \kappa$, ở đâu $\mathsf{adv}^A_H$ là lợi thế của $A$ trong một trò chơi xác định điện trở hình ảnh trước.

2. Thiết lập một số loại ràng buộc lợi thế $\mathsf{adv}_{H^{\circ k}}^A \leq \mathsf{adv}_H^A$, theo dõi thời gian chạy của đối thủ mới $B$ một cấu trúc (ngầm) như một phần của điều này.Để đơn giản, giả sử rằng $\mathsf{adv}_{H^{\circ k}}^B \leq \mathsf{adv}_H^A$, và $T(B) = kT(A)$ --- tôi không rõ điều này có đúng không, nhưng tôi nghĩ giả định này ẩn chứa trong câu hỏi của bạn.

3. Sau đó, chúng ta có điều đó $\min_B \frac{T(B)}{\mathsf{adv}_{H^{\circ k}}^B} \geq \min_A\frac{kT(A)}{\mathsf{adv}_{ H}^A} = \log_2 k + \kappa$.

Như # 2 ở trên đã chỉ ra, điều này thực sự làm giảm việc hiển thị một giới hạn lợi thế (truyền thống) của biểu mẫu.

Đối với bất kỳ đối thủ $B$ chống lại $SHA3^{\circ k}$, có đối thủ $A$ chống lại $SHA3$ với

• $T(B) = kT(A)$, và
• $\mathsf{adv}^B_{SHA3^{\circ k}} \leq \mathsf{adv}^A_{SHA3}$.

Điều này có nghĩa là khung MW cho phép một người thảo luận về thời gian chạy cao hơn của $B$ tác động đến bảo mật (đó là câu hỏi của bạn), nhưng người ta vẫn cần chứng minh một lợi thế bị ràng buộc.

Một vài suy nghĩ về điều này, không thực sự chắc chắn liệu câu trả lời của tôi có phù hợp với bạn hay không và có lẽ nó có sai sót.

Đầu tiên là một vài điều về bảo mật. Khi chúng ta nói rằng một lược đồ mật mã có $λ$ các bit bảo mật mà chúng tôi thường muốn nói là cách duy nhất để phá vỡ nó là dùng vũ lực thông tin về cửa sập và vì vậy hãy thử $2^λ$ sự kết hợp. Tất nhiên, chúng tôi không xem xét bất kỳ loại tấn công nào khác, tấn công kênh bên, v.v. Sau đó, chúng tôi xem xét mô hình đối thủ, ví dụ: giới hạn tính toán. Và nếu chúng tôi chứng minh rằng kế hoạch này an toàn trước kẻ thù này thì chúng tôi nói rằng nó có $λ$ chút bảo mật.

Vì bạn đang đề cập đến bảo mật lý thuyết nên câu trả lời là không. Có thể là có nếu bạn đang đề cập đến bảo mật định lượng. Tôi sẽ cố gắng đưa ra một phản ví dụ rất trực quan.

Ví dụ, thay vì xem xét một hàm băm, hãy xem xét RSA trong Sách giáo khoa với phần đệm thích hợp. Hãy xác định bảo mật của nó chỉ về mặt bảo mật ngữ nghĩa. Vì vậy, nó là an toàn, và do đó chúng tôi nói nó có $1^λ$ bit bảo mật, nếu có $PPT$ đối thủ (trên tham số bảo mật) bất kỳ cặp thông báo có cùng độ dài nào $m_1, m_2$, các văn bản mật mã trong lõi của chúng không thể phân biệt bằng máy tính. Nếu giả định RSA đúng, chúng tôi biết RSA an toàn về mặt ngữ nghĩa.

Bây giờ hãy xem xét một kế hoạch mới trong đó $c=Enc_k(Enc_k(x))$. Nếu sơ đồ mã hóa cuối cùng an toàn hơn sơ đồ mã hóa đầu tiên, điều này có nghĩa là đối thủ sẽ có thể đạt được lợi thế không đáng kể trong một trò chơi mà nó được cung cấp hai bản mã, mỗi bản mã được mã hóa bằng hai sơ đồ, ví dụ: các bản phân phối sẽ cần phải gần nhau một cách không đáng kể. Từ giả định RSA, điều này không thể xảy ra.