Điểm:3

Có an toàn không khi tiết lộ một điểm EC tùy ý nhân với một khóa bí mật?

lá cờ jp

Chúng tôi có một nhóm EC theo thứ tự chính. Cần thực hiện một giao thức (sắp xếp) DH, trong khi khóa là vĩnh viễn, không phải là nonce (khóa tạm thời sử dụng một lần).

Vì vậy, chúng tôi nhận được một phần tử nhóm tùy ý (điểm EC) từ một bên không đáng tin cậy và tiết lộ phần tử đó nhân với khóa bí mật.

Có luôn luôn an toàn để làm điều đó? Ý tôi là, kẻ tấn công có thể tạo điểm EC theo cách nào đó để trích xuất một số thông tin về khóa không? Chúng tôi đảm bảo rằng điểm EC thực sự nằm trên đường cong và như tôi đã đề cập, đó là nhóm có thứ tự chính.

Maarten Bodewes avatar
lá cờ in
Tôi nghĩ rằng bạn có thể suy luận điều này từ thực tế là DH tĩnh phù du sẽ cực kỳ bị hỏng nếu không phải như vậy. Nếu tôi nhớ không nhầm thì không có kiểm tra nào khác đối với khóa công khai tạm thời ngoài việc kiểm tra nó trên đường cong.
lá cờ jp
@MaartenBodewes: thông thường trong DH, đồng nghiệp không có động cơ nào để trích xuất nonce của bạn.
fgrieu avatar
lá cờ ng
@valdo: Mô tả của bạn thiếu hai chi tiết quan trọng: liệu các đối thủ có thể thực hiện nhiều truy vấn (giả sử $2^{24}$) không? Và đây có phải là truy vấn _iterated_ hay không? Điều đó tạo ra sự khác biệt, bởi vì các truy vấn lặp $k$ cho phép một người tính toán $(d^{k+1})\,G$ trong đó $d$ là khóa riêng và $d\,G$ là khóa chung đã biết, trong khi đó Các truy vấn được thiết lập trước $k\ge1$ sẽ cho phép tính toán $(d^2)\,G$ chứ không phải $(d^j)\,G$ cho $j\ge3$ bất kể $k$ là bao nhiêu. Một cách độc lập: nếu kết quả của DH (trước chức năng dẫn xuất khóa) được công khai, thì các đối thủ trong DH phù du sẽ ở vị trí mà bạn mô tả.
lá cờ jp
@fgrieu: Vâng và vâng. Vì vậy, đối thủ có thể dễ dàng tính toán `(d^n)G` cho sức mạnh tùy ý `n`. Điều gì khác biệt nó làm? Điều này có cho phép đối thủ trích xuất bất kỳ thông tin nào về khóa không?
fgrieu avatar
lá cờ ng
@valdo: nếu $k$ chia $p-1$ và đối thủ có $G, d\,G, (d^k)\,G$, thì theo tôi đọc bản tóm tắt của Jung Hee Cheon's _Security Analysis of bài toán Strong Diffie-Hellman_ (trong [kỷ yếu của Eurocrypt 2006](https://doi.org/10.1007/11761679_1)), có một cuộc tấn công $\sqrt k$ nhanh hơn Baby Step/Giant Step để khôi phục $d$ . Như trong bản tóm tắt, cuộc tấn công yêu cầu nhiều bộ nhớ một cách phi thực tế, nhưng BSGS cũng vậy, nhưng tìm kiếm xung đột giải quyết được điều đó và cho phép phân phối; để nó có thể trở nên thiết thực. Lưu ý: Tôi nên _not_ nhận được tín dụng vì đã đưa ra ý tưởng này cho câu hỏi này.
lá cờ jp
@MaartenBodewes: có, nhưng tùy thuộc vào ý của bạn là "bị hỏng". Mục đích chính của AFAIK DH không phải là bảo vệ khóa bí mật, mà là suy luận ra bí mật chung với một bên hợp tác qua kênh liên lạc công khai, phải không?
Maarten Bodewes avatar
lá cờ in
Chúng tôi có thể vui lòng sử dụng khóa riêng "(phù du / tĩnh) thay vì" nonce "hoặc" khóa bí mật không? "s sau khi sử dụng KDF. Đối với *static* DH, tất nhiên, tất cả là về việc bảo vệ khóa riêng tư. Nếu bạn có khóa riêng tư, bạn cũng sẽ tiết lộ bí mật dùng chung, chẳng hạn như khóa chung (hoặc các điểm khóa chung) nên được xem xét công khai. Nếu nó cũng được sử dụng để xác thực một bên - như phổ biến trong DH tĩnh tạm thời - thì việc rò rỉ khóa riêng tĩnh sẽ phá hủy tính xác thực đó.
lá cờ jp
@fgrieu: cám ơn nhiều! Đây là một điểm tuyệt vời. Tốt để biết. Tôi tin rằng trong trường hợp cụ thể của tôi, điều này vẫn ổn. Trên thực tế, kẻ thù có thể gọi giao thức này vài triệu lần, thậm chí có thể là hàng tỷ, nhưng không phải hàng nghìn tỷ. Chúng ta đang nói về thứ tự p là 2^256. Vì vậy, độ phức tạp của cuộc tấn công giảm đi khoảng 30/2 = 15 bit. từ 128 bit thành 113 bit. Vẫn đủ tốt cho trường hợp cụ thể của chúng tôi.
fgrieu avatar
lá cờ ng
@valdo: bạn sẽ quan tâm đến thông tin [ở đó](https://chat.stackexchange.com/transcript/message/59152377#59152377) (và trong đó là [tài liệu được liên kết](https://mailarchive.ietf.org /arch/msg/cfrg/YDVS5Trpr6suig_VCFEOH6SOn8Q/)). Tôi nhận được nó chủ yếu xác nhận những gì tôi nghi ngờ ở trên, nhưng tôi ở quá xa vùng thoải mái của mình để viết câu trả lời.
Điểm:2
lá cờ kr

Giả sử rằng "thứ tự chính" có nghĩa là "thứ tự chính" thì đây được gọi là bài toán Diffie-Hellman tĩnh và có một số cuộc tấn công đã biết chống lại nó. Những điều chính cần xem xét ngoài đỉnh đầu của tôi sẽ là:

  • Cheon DLP với đầu vào phụ trợ tấn công: có một số biến thể, nhưng ví dụ nếu thứ tự chính $p$ các đường cong elip của bạn thỏa mãn điều đó $d$ là một ước số của $p-1$, sau đó kẻ tấn công thực hiện nhiều các truy vấn có thể giải quyết vấn đề nhật ký rời rạc kịp thời $\widetilde{O}(\sqrt{p/d} + \sqrt{d})$, mà trong trường hợp xấu nhất $d = \Theta(p^{1/2})$$\widetilde{O}(p^{1/4})$. Về nguyên tắc, điều này có thể khá tệ, nhưng có nhiều lý do khiến cuộc tấn công không quá nguy hiểm trong bối cảnh này. Thứ nhất, do yêu cầu về bộ nhớ của cuộc tấn công và thực tế là hầu hết các giá trị của $p$ sẽ khá xa so với trường hợp xấu nhất, nó có thể khó áp dụng vào thực tế trong hầu hết các tình huống. Thứ hai, nếu $\alpha$ là khóa bí mật, kẻ tấn công cần bằng cách nào đó lấy được cả hai $\alpha G$$\alpha^d G$$G$ trình tạo nhóm và cách duy nhất để làm như vậy dường như là $d$ truy vấn thích ứng tuần tự $G \to \alpha G \to \alpha^2 G \to \cdots \to \alpha^d G$. Điều này là rất nhiều để mong đợi từ lời tiên tri, và vì nó cần có thời gian $O(d)$, điều này làm giảm tối ưu $d$ đến $\Theta(p^{1/3})$ và tăng độ phức tạp kết quả lên $\widetilde{O}(p^{1/3})$ (giả sử một lần nữa rằng $p-1$ có dạng yêu cầu). Không có nhiều cài đặt mà nhà tiên tri sẽ trả lời $2^{85}$ truy vấn từ đối phương. Đây là lý do tại sao cuộc tấn công Cheon thường phù hợp hơn trong các cài đặt nơi nhóm các phần tử của biểu mẫu $\alpha^j G$ có sẵn dưới dạng tài liệu khóa công khai, thay vì thu được bằng các truy vấn tuần tự;

  • Granger trường mở rộng tấn công nếu bạn tình cờ sử dụng các đường cong trên các trường độ mở rộng $\geq 3$ (rất có thể không phải như vậy).


Cảm ơn @fgrieu đã chỉ ra chính xác rằng một số nhận xét tôi đưa ra về điều này là không chính xác và cũng chỉ ra các cuộc thảo luận có liên quan trong danh sách gửi thư của IETF.

fgrieu avatar
lá cờ ng
Tôi không hiểu tại sao cuộc tấn công Cheon mà bạn đề cập lại không hoạt động ở một mức độ nào đó, khi câu hỏi sử dụng các truy vấn lặp lại và $p-1$ có thừa số nguyên tố vừa phải.
lá cờ jp
@fgrieu: trong trường hợp cụ thể của tôi, số lượng truy vấn quá nhiều không thực tế lắm. Như tôi đã nói, giới hạn trên của số lượng truy vấn là một triệu.
lá cờ jp
Tái bút cụ thể hơn: chúng tôi có một ứng dụng gọi là "plugin". Plugin này không thể có quyền truy cập trực tiếp vào khóa, nhưng chúng tôi cho phép nó lấy hình ảnh của nó (k*G). Gần đây, chúng tôi quyết định cho phép nó nhận (k*P), trong khi P là một phần tử nhóm tùy ý. Thời gian chạy của plugin bị giới hạn (tức là không thể chạy trong ngày). Người dùng có thể trích xuất bất kỳ thông tin nào nếu họ muốn. Vì vậy, đó là về việc bảo vệ người dùng khỏi plugin độc hại.
fgrieu avatar
lá cờ ng
@valdo: Tôi hiểu rồi. Mặc dù bạn có thể chỉ mới xem [bình luận của tôi ở trên](https://crypto.stackexchange.com/posts/comments/206590) gần đây), đó là một bình luận cũ, có trước [bình luận này bạn đã làm](https://crypto.stackexchange .com/posts/comments/206603) làm rõ số lượng truy vấn mà đối thủ có thể thực hiện.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.