Tác giả: Sylvain Pelissier Biên dịch: Cointime.com 237

Các chuỗi khối công khai có một lịch sử lâu dài về các cuộc tấn công vào chữ ký ECDSA của chúng. Vì tất cả các giao dịch đều được hiển thị công khai, điều này cung cấp một nền tảng thử nghiệm hoàn hảo cho các cuộc tấn công bằng mật mã. Một cuộc tấn công mạng có tên "Trường hợp tò mò về các số ngẫu nhiên ECDSA nửa Bitcoin" gần đây đã được xuất bản và thử nghiệm trên Bitcoin. Là một đội Thụy Sĩ yêu thích nước xốt giảm một nửa và giảm một nửa, chúng tôi phải điều tra cuộc tấn công này. Chúng tôi thấy rằng cuộc tấn công trước đó của chúng tôi, "số ngẫu nhiên đa thức", cũng hoạt động với cách tạo số ngẫu nhiên ECDSA này. Trong bài báo này, chúng tôi giải thích cách thực hiện và chỉ ra cách chúng tôi so sánh với kết quả thu được trong bài báo.

cuộc tấn công trước

Để ký một thông điệp, ECDSA sử dụng một giá trị được gọi là nonce. Nonce phải được tạo ngẫu nhiên và phải là duy nhất cho mỗi tin nhắn được ký. Đối với các đường cong secp256k1 của Bitcoin và Ethereum, các giá trị nonce điển hình như sau:

Một cạm bẫy phổ biến nổi tiếng và được nghiên cứu kỹ lưỡng của ECDSA là tái sử dụng nonce. Như tên ngụ ý, nếu một nonce được sử dụng lại trong các chữ ký khác nhau, thì khóa riêng tư có thể được phục hồi từ các chữ ký đó; rõ ràng, cuộc tấn công đầu tiên được áp dụng cho các chuỗi khối là cuộc tấn công tái sử dụng nonce. Ngay sau khi hai tin nhắn khác nhau được ký với cùng một nonce, khóa riêng tư sẽ bị xâm phạm. Vấn đề này thường được giải quyết bằng cách tạo các số ngẫu nhiên xác định theo RFC 6979.

Tuy nhiên, các nonce của ECDSA rất quan trọng đến mức ngay cả sự sai lệch trong thế hệ của chúng cũng có thể dẫn đến việc khôi phục khóa riêng tư. Do đó, các cuộc tấn công dựa trên mạng khéo léo hơn sau đó đã được áp dụng trên các chuỗi khối công khai. Các cuộc tấn công này có thể khôi phục các nonce có độ dài ngắn hơn dự kiến, với độ dài 64, 110, 128 và 160 bit. Ví dụ: các số ngẫu nhiên được tạo như sau dễ bị tấn công dựa trên mạng:

Nonce càng nhỏ, kích thước của mạng được sử dụng cho cuộc tấn công càng nhỏ và số lượng chữ ký cần thiết cho một cuộc tấn công thành công càng nhỏ. Theo bài viết về Số ngẫu nhiên thiên vị, hai số ngẫu nhiên 128 bit và mạng 3 chiều cho xác suất thành công là 75% (khôi phục khóa riêng tư). Khi sử dụng ba số ngẫu nhiên 170 bit và mạng 4 chiều, chúng ta có thể có xác suất thành công là 95%, v.v. Một biến thể của cuộc tấn công cũng có thể áp dụng để khám phá các nonce có tiền tố và hậu tố dùng chung. Ví dụ: các số ngẫu nhiên được tạo như sau đều dễ bị tấn công và các cấu trúc hậu tố phổ biến đã nói ở trên:

đa giác

Một cách khác để tấn công ECDSA là giả định mối quan hệ đại số giữa các số ngẫu nhiên. Nhóm của chúng tôi đã đề xuất một cuộc tấn công Polynonce, giả định rằng có một mối quan hệ đa thức giữa các hệ số a_i chưa biết, ở dạng sau:

k_{n+1} = a_1 k_n + a_0

hoặc

k_{n+1} = a_2 k_n^2 + a_1 k_n + a_0

Sau đó, một cuộc tấn công Polynonce có thể khôi phục đại số khóa riêng với xác suất thành công 100%, nhưng yêu cầu 4 chữ ký trong trường hợp tuyến tính, 5 chữ ký trong trường hợp bậc hai, v.v. Cuộc tấn công chủ yếu dựa vào việc giải các phương trình đa thức, vì vậy nó rất nhanh so với các cuộc tấn công dựa trên mạng. Để biết thêm chi tiết, cuộc tấn công sẽ được trình bày tại hội nghị DEFCON sắp tới.

chữ ký đơn

Tất cả các cuộc tấn công trước đây đều yêu cầu ít nhất hai chữ ký khác nhau từ cùng một khóa riêng. Tuy nhiên, các ví như Ledger ký giao dịch bằng một khóa riêng và sau đó thay đổi khóa riêng. Điều này sẽ giải thích tại sao nhiều địa chỉ công khai Bitcoin hiện chỉ được sử dụng một lần. Dưới đây là biểu đồ dữ liệu chuyển Bitcoin (kể từ ngày 5 tháng 9 năm 2022, khối 752759) được vẽ trên thang logarit giới hạn cho các giao dịch P2PKH:

Điều này cho thấy 92% khóa công khai được sử dụng cho các giao dịch P2PKH chỉ được sử dụng một lần. Tính năng này chủ yếu dành cho quyền riêng tư, nhưng gián tiếp cũng bảo vệ chống lại các cuộc tấn công trước đó. Đối với Ethereum, tình hình có một chút khác biệt. Chúng tôi đã phân tích 1759432087 chữ ký từ 151429561 khóa duy nhất và tạo một biểu đồ tỷ lệ tuyến tính:

Điều này cho thấy 92% khóa công khai được sử dụng cho các giao dịch P2PKH chỉ được sử dụng một lần. Tính năng này chủ yếu dành cho quyền riêng tư, nhưng gián tiếp cũng bảo vệ chống lại các cuộc tấn công trước đó. Đối với Ethereum, tình hình có một chút khác biệt. Chúng tôi đã phân tích 1759432087 chữ ký từ 151429561 khóa duy nhất và tạo một biểu đồ tỷ lệ tuyến tính:

Đây là một tình huống hoàn toàn khác: 42% khóa công khai chỉ được sử dụng cho một chữ ký, 22% cho hai chữ ký, 13% cho ba chữ ký, v.v. Do đó, có vẻ như các phương pháp bảo vệ quyền riêng tư có ít hoặc không có ứng dụng trên Ethereum.

nửa nửa số ngẫu nhiên

Một phương pháp tấn công mới đã xuất hiện gần đây tạo ra một số vấn đề khi nonce được nối với nửa trên của khóa riêng tư bằng cách sử dụng nửa trên của hàm băm thông báo. Nói cách khác, số ngẫu nhiên k có thể được biểu diễn như sau:

k = h_{msb} || d_{msb}

Điểm mới của cuộc tấn công này là nó cho phép khôi phục khóa riêng d từ một chữ ký duy nhất. Tương tự như các cuộc tấn công dựa trên mạng trước đây, một biểu thức cho số ngẫu nhiên k được thêm vào công thức ECDSA và được sắp xếp lại để tạo thành một thể hiện của bài toán ẩn số. Ví dụ sau đó được giải quyết bằng thuật toán BKZ. Kỹ thuật này rất mạnh vì chỉ cần một chữ ký duy nhất để tấn công các giao dịch được cấp bằng khóa riêng chỉ được sử dụng một lần. Phiên bản tối ưu hóa của cuộc tấn công có thể khôi phục khóa riêng trong 0,48 giây với tỷ lệ thành công 99,99%. Điều đó khá mạnh mẽ, nhưng các tác giả đã mất 49 năm CPU để thực hiện cuộc tấn công vào chuỗi khối Bitcoin.

Áp dụng Polynonce cho một nửa số ngẫu nhiên

Trong khi đọc về các cuộc tấn công nửa vời, chúng tôi đã phát hiện ra rằng Polynonce cũng có thể được sử dụng để khôi phục các khóa riêng tư bằng cách sử dụng các số ngẫu nhiên nửa vời. Đối với chữ ký ECDSA (r, s), hàm băm thông báo h và khóa riêng d, chúng tôi có mối quan hệ sau liên quan đến nonce:

k = s^{-1}(h + rd) mod q

Nếu chúng ta có hai số ngẫu nhiên k_0 và k_1 được tạo bằng công thức nửa nửa trước đó, sự khác biệt của chúng là:

k_0 - k_1 = s_0^{-1}h_0 - s_1^{-1}h_1 + (s_0^{-1}h_0 - s_1^{-1}h_1)d = h_{0,msb} - h_{1, msb}

Chúng tôi đã tìm thấy một phương trình tuyến tính cho d trong đó tất cả các giá trị khác đã biết. Điều này cung cấp một cách rất nhanh để giải phương trình và khôi phục khóa riêng d. Tuy nhiên, việc sử dụng Polynonce yêu cầu hai nonce và hai chữ ký từ cùng một khóa riêng tư. Chúng tôi đã mất một lợi thế rất lớn so với các cuộc tấn công trước đó. Tuy nhiên, vì biến thể tấn công này rất nhanh nên có thể sử dụng nó trước tiên trên các khóa công khai có nhiều chữ ký, sau đó sử dụng các cuộc tấn công dựa trên mạng trên các chữ ký còn lại.

Vì chênh lệch số ngẫu nhiên trong phương trình của chúng ta chỉ phụ thuộc vào h_{0,msb} - h_{1,msb}, nên điều này cho phép chúng ta quay lại sử dụng công thức k_i = h_{i,msb} || c (trong đó c là a (bí mật) hằng số) tất cả các số ngẫu nhiên được tạo. Điều này tổng quát hơn, nhưng phức tạp hơn một chút đối với Bitcoin. Bắt đầu từ chữ ký ECDSA (r, s), các chữ ký khác nhau (r, -s) của cùng một thông báo cũng hợp lệ. Vì Bitcoin từ chối chữ ký có giá trị lớn nhất là s để tránh giả mạo chữ ký, điều này có nghĩa là chúng ta phải tính cả -k và k. Do đó, trong cuộc tấn công của chúng tôi, chúng tôi phải đoán dấu hiệu của từng nonce.

Việc xây dựng này lẽ ra cũng đã được phát hiện bởi nghiên cứu trước đây về các cuộc tấn công mạng vào các hậu tố được chia sẻ, nhưng tỷ lệ thành công chỉ là 75%.

kết quả

Chúng tôi đã thực hiện phân tích của mình trên tệp kết xuất chuỗi khối Bitcoin đã được sử dụng trong phân tích trước đó của chúng tôi (khối 752.759 kể từ ngày 5 tháng 9 năm 2022). Chúng tôi đã phân tích 34 triệu khóa công khai với ít nhất 2 chữ ký. Trên bộ xử lý AMD 16 nhân tốc độ 2,7 GHz, mất 10 phút 23 giây.

Chúng tôi đã định vị và khôi phục thành công 110 khóa riêng tư duy nhất. Ví dụ, địa chỉ

18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7

giao dịch

Chúng tôi đã định vị và khôi phục thành công 110 khóa riêng tư duy nhất. Ví dụ, địa chỉ

18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7

giao dịch

f3151fc1b29c117f1e4b67045b2d2901e7c289f596c242d7de123243fb623981

Và

f7bf1edf9d9cefa8421322c53bb00ecf118f99489171da72a9c11cf8d02b65f8

Tạo số ngẫu nhiên bằng phương pháp nửa rưỡi. Tập lệnh của chúng tôi có thể khôi phục khóa riêng cho địa chỉ này:

Nếu chúng tôi tính toán lại nonce cho các giao dịch như vậy, chúng tôi sẽ nhận được:

Chúng tôi thấy rõ ràng rằng một nửa số ít quan trọng nhất bằng một nửa quan trọng nhất của khóa riêng. Tuy nhiên, như đã đề cập ở trên, chúng tôi có thể khôi phục các trường hợp thú vị khác; đối với cùng một địa chỉ, chúng tôi đã tìm thấy hai nonce:

Trong trường hợp này, khóa riêng tư không liên quan vì chúng tôi thực sự đã tìm thấy một hằng số không xác định khác. Chúng tôi cũng có thể xác nhận những phát hiện trước đây rằng một số khóa sử dụng các số ngẫu nhiên như vậy là các khóa nhỏ: d = {1, 2, 4, 7, 11, 24, 75, 77, 87, 128, 144, 549, 897 }. Do đó, các khóa này có thể được khôi phục dễ dàng bằng các phương pháp vũ phu, tương tự như công việc được thực hiện trên trang web https://privatekeys.pw. Chúng tôi không tìm thấy tài khoản có số dư khác 0 mà chúng tôi tin rằng tài khoản này được theo dõi bởi bot và làm trống khi số dư thay đổi.

Vì cuộc tấn công này quá nhanh nên chúng tôi cũng thực hiện cuộc tấn công tương tự trên các biến thể khác của tạo số bán ngẫu nhiên: k = h_{lsb} || d_{msb}, k = d_{msb} || h_{msb} và k = d_{msb} || h_{lsb}, nhưng chúng tôi không tìm thấy kết quả bổ sung nào.

Chúng tôi cũng thực hiện cuộc tấn công tương tự vào bộ dữ liệu Ethereum được thu thập trong cuộc tấn công trước đó. Cuộc tấn công diễn ra trong 49 phút 11 giây trên cùng một máy. Cuộc tấn công này đã không phục hồi bất kỳ khóa riêng nào.

Các cấu trúc tạo số ngẫu nhiên sáng tạo khác nhau trong quá khứ thú vị đến mức chúng tôi tự hỏi liệu có cấu trúc kỳ lạ nào khác ngoài kia không. Mặc dù các cuộc tấn công mới này không khôi phục khóa riêng mới, nhưng điều đó không có nghĩa là các thuật toán tạo số ngẫu nhiên yếu khác không được sử dụng trong các giao dịch trước đó, cũng như không có nghĩa là có thể khôi phục được bằng các phương pháp tương tự. Nếu những vấn đề như vậy được phát hiện, cách tốt nhất để bảo vệ tiền là chuyển chúng đến địa chỉ mới chưa từng được sử dụng cho các giao dịch và để trống địa chỉ dễ bị tấn công. Kịch bản tấn công của chúng tôi và kết quả chúng tôi thu được có sẵn trên kho lưu trữ Github của cuộc tấn công Polynonce.