Điểm:0

Giả mạo chữ ký số trên 60000 tin nhắn bằng vũ lực

lá cờ us

Giả sử một hệ điều hành sử dụng chữ ký số để đảm bảo các tệp thực thi có thể được xác thực và không thể sửa đổi; trong đó chữ ký điện tử được xây dựng bằng cách tạo hàm băm của tệp thực thi (ví dụ: SHA256), mã hóa hàm băm bằng khóa riêng (ví dụ: RSA), sau đó đính kèm hàm băm được mã hóa và khóa chung (chữ ký) vào tệp thực thi.

Giả sử có 1000 phần mềm (từ nhiều nhà xuất bản) được cập nhật (trung bình) mỗi tháng một lần trong 5 năm.

Kẻ tấn công thu thập hàm băm và chữ ký số cho tất cả 60000 phần mềm. Kẻ tấn công viết phần mềm độc hại trojan của riêng chúng với một số phần đệm dự phòng ở cuối tệp thực thi của chúng. Kẻ tấn công tính toán một phần hàm băm của tệp thực thi của chúng, nhưng dừng lại (lưu trạng thái tính toán hàm băm) ngay trước phần đệm.

Kẻ tấn công đặt lại trạng thái tính toán hàm băm, hoàn thành phép tính hàm băm cực kỳ nhanh chóng, sau đó kiểm tra xem hàm băm có tương ứng với một trong 60000 chữ ký số mà chúng đã thu thập hay không. Nếu không, họ sẽ tăng phần đệm ở cuối tệp thi hành của mình và thử lại. Kẻ tấn công thực hiện điều này song song trên nhiều máy tính (đa CPU), cho đến khi chúng tìm thấy chữ ký của thứ khác mà chúng có thể sử dụng để ký phần mềm độc hại của mình.

điều này có thể được ngăn ngừa bằng cách nào?

Sức mạnh của sơ đồ mã hóa là không quan trọng. Việc tăng kích thước hàm băm chỉ có nghĩa là kẻ tấn công cần thu thập nhiều chữ ký số hơn và/hoặc sử dụng nhiều CPU hơn trong thời gian dài hơn để tìm ra chữ ký hợp lệ cho phần mềm độc hại của chúng. Giả sử kẻ tấn công có thể nhận được nhiều CPU hơn bằng cách ẩn javascript trong một trang web phổ biến, sử dụng dịch vụ đám mây, ẩn nó trong phần mềm được xuất bản với chữ ký hợp pháp của riêng họ (ví dụ: tiện ích khai thác tiền điện tử), v.v.

Có bất kỳ thuật toán băm hiện có nào đủ mạnh không?

kelalaka avatar
lá cờ in
Liên quan [Tấn công đa mục tiêu để băm](https://crypto.stackexchange.com/q/75880/18298)
Điểm:4
lá cờ my

Có bất kỳ thuật toán băm hiện có nào đủ mạnh không?

Đúng; trên thực tế, bất kỳ thuật toán băm bảo mật bằng mật mã nào (chẳng hạn như SHA-2, SHA-3, Blake2) sẽ đủ mạnh.

Để nhấn mạnh điều này, hãy để tôi chỉ ra rằng MD5 đủ mạnh. Bây giờ, MD5 được coi là khá yếu (và không ai ở đây tán thành việc sử dụng nó); tuy nhiên, ngay cả với những điểm yếu đã biết, nó vẫn đủ mạnh để chống lại cuộc tấn công cụ thể này.

MD5 có đầu ra 128 bit (trái ngược với các hàm băm mật mã mà chúng tôi sử dụng trong thực tế, có đầu ra lớn hơn nhiều). Ngoài ra, có nhiều cách đã biết để tạo "va chạm", tức là các cặp đầu vào mà MD5-băm thành cùng một giá trị. Tuy nhiên, những phương pháp đó giả định rằng cuộc tấn công có quyền kiểm soát đối với cả hai đầu vào - trong trường hợp này, nhà xuất bản hợp lệ tạo ra hình ảnh hợp lệ và kẻ tấn công không thể thay đổi những gì nhà xuất bản ký, do đó, điểm yếu va chạm của MD5 không áp dụng. MD5 không có điểm yếu nào đối với các cuộc tấn công 'tạo ảnh trước thứ hai' hoặc đối với một cuộc tấn công 'tạo ảnh trước thứ hai đa mục tiêu' (chính xác là đây là gì), và do đó, cách tiếp cận duy nhất mà kẻ tấn công có là băm các đầu vào khác nhau cho đến khi hắn tìm thấy kết quả phù hợp.

Bây giờ, chúng tôi giả định rằng có $60.000 \xấp xỉ 2^{16}$ chữ ký hợp lệ; nếu kẻ tấn công băm một phỏng đoán, điều đó có khoảng $2^{-128+16} = 2^{-112}$ xác suất băm đến một trong các mục tiêu. Nói cách khác, để có cơ hội một phần nghìn tìm thấy một hình ảnh băm vào một trong các mục tiêu, anh ta sẽ cần băm khoảng $2^{102}$ hình ảnh.

Bây giờ, người ta ước tính rằng ngành khai thác bitcoin toàn cầu đánh giá khoảng $2^{68}$ băm mỗi giây (thực tế, ít hơn một chút); điều đó có nghĩa là nếu cuộc tấn công có thể dành tất cả quá trình xử lý đó [1] để tấn công hệ thống của bạn, thì chúng sẽ cần phải thực hiện điều đó trong khoảng $2^{34}$ giây (hoặc khoảng 500 năm) để đạt được cơ hội có 1 phần nghìn đó.

Nếu bạn hoán đổi MD5 bằng một hàm băm tiền điện tử thực, thì 500 năm đó sẽ biến thành loại khung thời gian 'cái chết nóng của vũ trụ'.

[1]: Tất nhiên, cơ sở hạ tầng khai thác bitcoin hiện tại được xây dựng xung quanh SHA-256 - Tôi sẽ bỏ qua chi tiết đó.

lá cờ us
Bạn đang xem vấn đề sinh nhật? Tôi đã mong đợi rằng 1
poncho avatar
lá cờ my
@Brendan: như tôi đã đề cập ở trên "trong trường hợp này, nhà xuất bản hợp lệ tạo hình ảnh hợp lệ và kẻ tấn công không thể thay đổi những gì nhà xuất bản ký và do đó, điểm yếu va chạm của MD5 không áp dụng". Nếu điều này không đúng (nghĩa là kẻ tấn công có thể chèn các thay đổi của chính mình vào những gì nhà xuất bản ký), thì MD5 có thể không đủ. Mặt khác, nếu chúng tôi quay trở lại SHA256 (thực tế hơn nhiều), thì một cuộc tấn công va chạm cần một số băm $2^{128}$ dự kiến ​​- gần bằng với số lượng đánh giá mà chúng tôi nhận được cho cuộc tấn công tạo ảnh trước đa mục tiêu MD5 - một ước tính thời gian tương tự được áp dụng.
poncho avatar
lá cờ my
@Brendan: tất nhiên, nếu kẻ tấn công có thể chèn các thay đổi của chính mình vào những gì nhà xuất bản ký, tại sao anh ta không đưa phần mềm độc hại của mình vào đó và không bận tâm đến việc cố gắng tạo giả mạo?
lá cờ us
À, bạn nói đúng (tôi đã bỏ lỡ các cuộc tấn công sinh nhật). 1
Điểm:1
lá cờ kr

SHA-256 có khả năng chống lại các cuộc tấn công tạo ảnh trước. Cách duy nhất để tìm một hình ảnh trước tạo ra hàm băm nhất định là cưỡng bức vũ phu. Tài nguyên tính toán hiện tại được sử dụng để khai thác bitcoin trên thế giới tính toán khoảng $2^{90}$ băm mỗi năm. Do đó, ngay cả khi cả thế giới cố gắng tạo một hình ảnh (trong trường hợp của bạn, để tìm phần đệm cụ thể) với hàm băm đã cho, thì điều đó sẽ không thể thực hiện được ngay cả trong vài triệu năm nữa.

poncho avatar
lá cờ my
Trên thực tế, "trong một vài triệu năm nữa" là quá lạc quan; ở mức $2^{90}$ hash/năm và 60.000 mục tiêu, quá trình tìm kiếm sẽ mất khoảng $1,5 dự kiến ​​\times 10^{45}$ năm
lá cờ kr
@poncho: Đúng :-) Nhưng e rằng nếu thật sự nhiều thời gian thì khó hình dung. Bạn có thể nói nó còn tồn tại lâu hơn cả Vũ trụ. Nhưng ngay cả điều này có thể khó tưởng tượng. Có thể thậm chí hàng triệu năm là khó tưởng tượng và hàng nghìn năm có thể tốt hơn :-) Đó là lý do tại sao tôi hy vọng rằng việc sử dụng từ ngữ như vậy làm cho câu trả lời hữu ích hơn.
poncho avatar
lá cờ my
Tôi hiểu rồi, tuy nhiên câu nói của bạn nghe giống như "các ngôi sao cách xa hơn 10 mét". Tôi cho là đúng về mặt kỹ thuật, nhưng cũng là một cách diễn đạt hài hước ...

Đă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.