it-swarm-vi.com

Một nhà tiên tri mật mã là gì?

Tôi đã bắt gặp thuật ngữ "Oracle mật mã" và mặc dù có một chút lờ mờ, tôi không thể bắt gặp một định nghĩa rõ ràng, súc tích. Oracle mật mã là gì và nó làm gì? Bất cứ ai có thể đưa ra một ví dụ?

35
josh-cain

Một Oracle là một cá nhân biết số điện thoại di động cá nhân của một vị thần. Điều này cho phép anh ta (hoặc cô ta) có được một số thông tin thường được coi là ngoài tầm với của những người bình thường, chẳng hạn như những cái nhìn thoáng qua về tương lai. Trong mật mã học, điều đó cũng tương tự, ngoại trừ việc không có vị thần nào tham gia: Oracle là bất kỳ hệ thống nào có thể cung cấp thêm một số thông tin trên một hệ thống, nếu không thì sẽ không có sẵn.

Chẳng hạn, hãy xem xét mã hóa bất đối xứng với RSA . Tiêu chuẩn tôi liên kết với các trạng thái nên mã hóa một phần dữ liệu bằng khóa chung. Cụ thể, mã hóa bắt đầu bằng thao tác đệm , trong đó phần dữ liệu được mở rộng đầu tiên bằng cách thêm tiêu đề, sao cho độ dài dữ liệu được đệm phù hợp độ dài khóa công khai RSA. Tiêu đề phải bắt đầu bằng hai byte 0x00 0x02, theo sau là ít nhất tám byte khác không ngẫu nhiên và sau đó là 0x00. Khi dữ liệu đã được đệm, đã đến lúc áp dụng thao tác toán học là cốt lõi của hoạt động RSA (lũy thừa mô-đun). Chi tiết của phần đệm rất quan trọng đối với bảo mật.

Kết quả mã hóa là một modulo số nguyên mô đun RSA , một số nguyên lớn là một phần của khóa chung. Đối với khóa RSA 1024 bit, mô đun n là một giá trị nguyên lớn hơn 21023, nhưng nhỏ hơn 21024. Một đoạn dữ liệu được mã hóa chính xác, với RSA, mang lại một giá trị nguyên giữa 1 n-1 . Tuy nhiên, phần đệm ngụ ý một số cấu trúc , như được hiển thị ở trên. Bên giải mã PHẢI tìm thấy, khi giải mã, tiêu đề PKCS # 1 được hình thành đúng cách, bắt đầu bằng 0x00 0x02 byte, theo sau là ít nhất tám byte khác không và phải có 0x00 đánh dấu sự kết thúc của tiêu đề. Do đó, không phải tất cả các số nguyên giữa 1 n-1 đều là RSA hợp lệ tin nhắn được mã hóa (ít hơn 1 cứ 65000 số nguyên như vậy sẽ mang lại một phần đệm phù hợp khi giải mã).

Biết liệu một số nguyên modulo đã cho n sẽ mang lại, khi giải mã, a cấu trúc đệm hợp lệ, được cho là không khả thi đối với những ai không biết khóa riêng. Chủ sở hữu khóa riêng (vị thần) có được thông tin đó và hơn thế nữa: nếu giải mã hoạt động, chủ sở hữu khóa riêng thực sự nhận được thông báo, đó là điểm giải mã. Giả sử rằng một thực thể, ở đâu đó, người có thể cho bạn biết liệu một số nguyên modulo đã cho n là một phần dữ liệu được mã hóa hợp lệ với RSA; thực thể đó sẽ không cung cấp cho bạn kết quả giải mã đầy đủ, nó sẽ chỉ cho bạn biết liệu giải mã có hoạt động hay không. Đó là thông tin một bit, một cái nhìn thoáng qua về những gì vị thần sẽ có được. Thực thể là Oracle của bạn: nó trả về các phần của thông tin chỉ có sẵn cho chủ sở hữu khóa riêng.

hóa ra rằng, được cấp quyền truy cập vào một Oracle như vậy, có thể xây dựng lại khóa riêng bằng cách gửi các số nguyên được chế tạo đặc biệt modulo n (phải mất một triệu hoặc hơn các giá trị như vậy và khá nhiều toán học, nhưng nó có thể được thực hiện). Nó cũng chỉ ra rằng hầu hết SSL/TLS thực hiện vào thời điểm đó (đó là vào năm 1999) đã vô tình đóng vai trò là nhà tiên tri: nếu bạn đã gửi, với tư cách là khách hàng, một tin nhắn ClientKeyExchange được mã hóa RSA không hợp lệ, máy chủ đã phản hồi với một thông báo lỗi cụ thể ("duh, thông điệp ClientKeyExchange của bạn bốc mùi"), trong khi nếu giải mã hoạt động, máy chủ vẫn tiếp tục với giao thức, sử dụng bất kỳ giá trị nào được giải mã (thường không biết đến máy khách nếu khách hàng gửi một giá trị ngẫu nhiên , vì vậy giao thức thất bại sau này, nhưng khách hàng có thể thấy sự khác biệt giữa phần đệm hợp lệ và không hợp lệ). Do đó, với cách triển khai như vậy, kẻ tấn công có thể (sau một triệu kết nối không thành công) xây dựng lại khóa riêng của máy chủ, thường được coi là một điều xấu.

Đó là những gì tiên tri là: một mô tả toán học về rò rỉ dữ liệu, sẽ được sử dụng trong các bằng chứng bảo mật. Trong trường hợp RSA, điều này chứng tỏ rằng việc biết một giá trị có đệm đúng hay không bằng cách nào đó tương đương với việc học khóa riêng (nếu bạn biết khóa riêng, bạn có thể thử giải mã và xem phần đệm cho chính mình; cuộc tấn công Bleichenbacher cho thấy rằng nó cũng hoạt động theo cách khác vòng).

67
Thomas Pornin

Một Oracle là một cái gì đó có thể ngay lập tức (O(1)) cung cấp cho bạn câu trả lời cho một số vấn đề, thường là một vấn đề không thể hoặc không thể. Ví dụ: a "Tạm dừng vấn đề Oracle" có thể cho bạn biết ngay lập tức liệu một chương trình nhất định trên một đầu vào nào đó có dừng lại hay không, mặc dù vấn đề tạm dừng là không thể tính toán được chúng ta chỉ là phàm nhân. Tuy nhiên, đôi khi chúng ta có thể chứng minh một số tính chất hữu ích bằng cách giả vờ một số phép lạ tồn tại.

Ví dụ, trong các bài viết về mật mã, các nhà tiên tri thường được sử dụng để chỉ ra rằng, thậm chí nếu những kẻ tấn công của chúng tôi đã truy cập vào một số Oracle dường như vô dụng, họ still sẽ không có bất kỳ lợi thế (đáng kể) nào để phá vỡ bảo mật của chúng tôi. Ví dụ: một thuộc tính quan trọng của thuật toán mã hóa (được gọi là khả năng chống lại các cuộc tấn công bằng văn bản đã biết ) là nếu kẻ tấn công được cung cấp một thông điệp được mã hóa bằng khóa của bạn m' và họ muốn biết tin nhắn gốc m (hoặc tìm ra khóa của bạn), sau đó gửi cho họ một tin nhắn khác n và mã hóa bằng khóa của bạn n' không nên giúp họ làm như vậy dưới bất kỳ hình thức nào.

Đưa điều này đến mức cực đoan ( đã chọn tấn công bằng văn bản ): cung cấp cho kẻ tấn công một Oracle có thể mã hóa hoặc giải mã any tin nhắn với khóa ngoại trừ cho mm'. Ngay cả trong những điều kiện khắc nghiệt này, chúng tôi muốn chứng minh cho mã hóa của mình rằng kẻ tấn công với Oracle sẽ không có lợi thế trong việc tìm kiếm m (hoặc khóa của bạn) so với kẻ tấn công không có Oracle. Điều này có nghĩa là mã hóa của chúng tôi an toàn trước các cuộc tấn công bằng văn bản đã chọn.


[Chỉnh sửa]
[.__.] Đây là một ví dụ thực tế khác. Trong câu hỏi Có thể một chương trình có thể biết nếu một chương trình khác chơi cờ không , chúng tôi cho thấy rằng không có chương trình nào như vậy tồn tại bằng cách trước tiên giả sử rằng có một Oracle phát hiện cờ vua, sau đó cho thấy sự tồn tại của nó dẫn đến một sự bất khả thi logic.

Các nhà tiên tri mật mã là một phương thức nhập/xuất hộp đen.

Nó sẽ đáp ứng bất kỳ đầu vào nào với phản hồi giả ngẫu nhiên nhưng sẽ luôn cung cấp cùng một đầu ra cho một đầu vào cụ thể.

Chúng thường được sử dụng cho các hàm băm trong đó tính ngẫu nhiên rất quan trọng để bảo mật cao hơn.

Rõ ràng vẫn còn có vấn đề về bảo mật vì đây chỉ là một hàm toán học đang trả về các số có vẻ giả ngẫu nhiên, nhưng rõ ràng chúng mạnh hơn một số đối tác ít ngẫu nhiên hơn.

Đây là một bài viết chắc chắn về họ và thiết kế của họ - http://cseweb.ucsd.edu/users/mihir/ con/rr.pdf

1
doyler