Tôi đang cố gắng tìm một va chạm giữa hai thư sẽ dẫn đến cùng một mã CRC. Xem xét tôi đang sử dụng CRC32, có cách nào tôi có thể rút ngắn danh sách các thông điệp có thể có mà tôi phải thử khi thực hiện một cuộc tấn công bạo lực không?CRC32 Collision
Bất kỳ liên kết nào đến trang web có gợi ý về điều này sẽ hữu ích. Tôi đã có một thuật toán bạo lực sẽ làm điều này nhưng nó chỉ đơn giản là tăng số nguyên và xem nếu nó sẽ phù hợp với băm khác.
Điều đó hoàn toàn phụ thuộc vào ý bạn là "thông báo". Nếu bạn có thể thêm bốn byte vô nghĩa vào một trong các thư. (I.E. bốn byte không có ý nghĩa trong ngữ cảnh của thông điệp.) Sau đó, nó trở nên tầm thường theo nghĩa chân thật nhất của từ đó.
Suy nghĩ về các bit di chuyển qua máy trạng thái CRC32.
CRC32 dựa trên thanh ghi thay đổi phản hồi galois, mỗi bit trong trạng thái của nó sẽ được thay thế bằng cảm ứng 32 bit từ dữ liệu tải trọng. Tại thời điểm cảm ứng của từng bit, các vị trí được chỉ thị bởi đa thức sẽ là độc quyền với chuỗi được quan sát từ cuối thanh ghi Shift. Trình tự này không bị ảnh hưởng bởi dữ liệu đầu vào cho đến khi thanh ghi thay đổi đã được lấp đầy.
Như một ví dụ, hãy tưởng tượng chúng ta có một thanh ghi dịch đầy trạng thái ban đầu 10.101.110, đa thức 10.000.011, và điền với bit không rõ, X.
Polynomial * ** |feedback (End of SR.)
State 10101110 0
State X1010111 1
State XX101000 0
State XXX10100 0
State XXXX1010 0
State XXXXX101 1
State XXXXXX01 1
State XXXXXXX1 1
State XXXXXXXX 0
Phản hồi không phải là về mặt X cho đến khi SR đã được lấp đầy! Vì vậy, để tạo ra một tin nhắn với một kiểm tra định trước, bạn có tin nhắn mới của bạn, tạo ra nó CRC và làm việc ra nó là 32 bit tiếp theo của thông tin phản hồi. Điều này bạn có thể làm trong 32 bước của hàm CRC. Sau đó, bạn cần tính toán hiệu ứng mà phản hồi này có trên nội dung của thanh ghi thay đổi.
Phím tắt để thực hiện việc này là để đệm thư của bạn với bốn byte bằng 0 và sau đó nhìn vào tổng kiểm tra. (Checksum là trạng thái của SR ở cuối, mà nếu đệm với bốn byte không là ảnh hưởng của phản hồi và các byte trống.)
Độc quyền HOẶC ảnh hưởng đến giá trị tổng kiểm tra bạn muốn, thay thế đoạn giới thiệu bốn byte bằng giá trị được tính đó và tạo lại tổng kiểm tra. Bạn có thể làm điều này với bất kỳ chương trình nào tạo CRC32, trình chỉnh sửa hex và máy tính có thể xử lý hex.
Nếu bạn muốn tạo hai thư có ý nghĩa hoàn chỉnh và không chứa dấu vết rác, mọi thứ trở nên khó khăn hơn một chút. Xác định một số phần mà bạn có thể viết các lựa chọn thay thế hợp lý, với chính xác cùng độ dài.
Sử dụng văn xuôi tiếng Anh làm ví dụ. "Tôi nghĩ rằng điều này có thể hoạt động" và "Tôi tin vào phương pháp này" Có ý nghĩa tương tự rộng và chính xác cùng độ dài.
Xác định đủ ví dụ trong thư là bit phức tạp (Trừ khi bạn muốn gian lận với khoảng trắng!) CRC 32 là tuyến tính, miễn là dữ liệu có độ lệch chính xác trong thông báo. Vì vậy, CRC ([messagea] [padding])^CRC ([padding] [messageb]) = CRC ([messagea] [messageb]) Có một số cảnh báo với sự liên kết từ mà bạn sẽ cần phải đối phó với, như một gợi ý, bạn muốn mở rộng các đoạn ra thành các phần "cố định" của tin nhắn. Theo nguyên tắc chung, bạn muốn có các lựa chọn thay thế cho n * 1.5 đoạn, trong đó n là kích thước của CRC.
Bây giờ bạn có thể tính CRC mà thông điệp xương có, ấn tượng rằng mỗi đoạn thay thế sẽ có trên đó, và sau đó vẽ lên một bảng so sánh ảnh hưởng mà mỗi thay thế cho mỗi đoạn văn sẽ có. Sau đó, bạn cần phải chọn các lựa chọn thay thế sẽ sửa đổi CRC xương để phù hợp với CRC bạn muốn. Vấn đề đó thực sự khá thú vị để giải quyết, Trước tiên hãy tìm bất kỳ lựa chọn thay thế nào mà sửa đổi một chút, nếu bit đó cần thay đổi cho CRC của bạn, hãy chọn thay thế đó và gấp ảnh hưởng của nó vào CRC, sau đó đi vòng lại. Điều đó sẽ giảm không gian giải pháp mà bạn cần tìm kiếm.
Đó là một điều khá khó khăn để mã hóa, nhưng nó sẽ tạo ra va chạm của bạn trong một khoảng thời gian rất ngắn.
Tôi sẽ giả định rằng bạn có nghĩa là "tin nhắn" thay vì "khóa".
Nếu bạn được phép chọn cả hai "chìa khóa", thì sức mạnh vũ phu sẽ nhanh hơn vì lý do sinh nhật. Chọn các thông điệp ngẫu nhiên, tính CRC của chúng, nhớ tất cả chúng và CRC liên quan, và mỗi cái mới có nhiều cơ hội hơn để va chạm với một cái hiện có khi chúng tích lũy. Thành thật mà nói, tôi hy vọng cách tiếp cận này sẽ nhanh hơn trên một máy tính hiện đại hơn là tìm kiếm các cách tiếp cận đã biết để làm cho CRC32 va chạm.
Tôi tin CRC là tuyến tính, vì vậy nếu bạn sửa đổi (tại chỗ, mà không thay đổi độ dài) hai phần khác nhau của tệp,
sự khác biệt trong CRC sẽ được xâu cùng nhau.
- chỉnh sửa: nó có vẻ không đơn giản như vậy. Tuy nhiên, đây vẫn là loại tack tôi sẽ cố gắng xây dựng một vụ va chạm - bạn cần phải theo dõi toán học chi tiết hơn tôi có khuynh hướng làm tối nay ...
Chỉ hôm qua có this question here on SO, một vài con trỏ được đề cập ở đó có thể giúp bạn.
ngắn của một lỗ hổng với tính toán của tôi, khả năng không đã tìm thấy một va chạm sau khi N thử nghiệm là xấp xỉ trong bảng sau:
N Probability
------- -----------
50,000 74.7%
77,000 50.1%
78,000 49.2%
102,000 29.8%
110,000 24.5%
128,000 14.8%
150,000 7.3%
200,000 0.95%
Nói cách khác, xác suất của việc phải tính toán nhiều hơn hơn 200.000 giá trị CRC32 trước khi tìm kiếm trùng lặp nhỏ hơn 1% hoặc xác suất tìm kiếm trùng lặp trước 102.000 lần thử là 70,2%
BTW điều này là đáng chú ý vì xác suất tìm thấy một va chạm trên, ví dụ: rất nỗ lực 200.000 vẫn còn theo thứ tự 1/1000th 1% ((4M - 200,0000)/4M), nhưng có thể đã tìm thấy một va chạm trước nỗ lực 200.000 là một sự chắc chắn gần đúng (tốt, trên 99% anyway). Điều này cho thấy sự quan tâm của việc giữ một cơ sở dữ liệu của CRCs tính đến nay. Chúng tôi chắc chắn có thể dành thời gian nghiên cứu thuật toán CRC32 và toán học cơ bản của nó, trong một nỗ lực để tìm thấy tin nhắn nhiều khả năng để tạo ra một vụ va chạm CRC32, nhưng số lượng tương đối thực sự ngẫu nhiên cần thiết để tìm thấy ít nhất một va chạm với sự gần như chắc chắn, làm cho loại phương pháp mã hóa này hầu như không xứng đáng với nỗ lực. Ví dụ giả định rằng chúng ta có thể khám phá một cách để chọn các tin nhắn có khả năng va chạm với nhau nhiều gấp 10 lần, chúng ta vẫn phải thử theo thứ tự 63.000 lần trước khi đạt tới 99% cơ hội có ít nhất một va chạm (tốt hơn 200.000 nhưng vẫn yêu cầu cùng loại ứng dụng.)
Điều duy nhất chúng tôi có thể muốn xem xét, trong khu vực này là để tránh thư ngắn hơn 4 byte (Tôi đọc ở đâu đó CRC32 là tính từ trong không gian thư này) và tránh thư quá tương tự (nghĩa là chỉ khác nhau bởi một hoặc hai ký tự), vì sau khi mục đích ban đầu của CRC32 là phát hiện (và có thể tự động sửa) những khác biệt nhỏ như vậy trong các thư. Do đó, có vẻ như độ khó của bài tập không phải là quá nhiều để tìm cách tính CRC32 ở tốc độ nóng bỏng (mặc dù chúng ta cũng không nên quá chậm), nhưng thay vì để quản lý nhanh chóng cơ sở dữ liệu có thể tìm kiếm lên đến 200.000 Tin nhắn (hoặc thông báo "khóa", chi tiết hơn về điều này bên dưới) và giá trị CRC32 được liên kết của chúng.
Một vài ý tưởng để thực hiện tất cả điều này
Lực lượng vũ phu bạn cần về thông điệp độ dài ngẫu nhiên sqrt (6N) cho một băm có kích thước N để có được xác suất 95% cho va chạm. Ví dụ. CRC32, N = 2^32, bạn cần khoảng 160 000 thư
OK, nhưng tôi thấy nó thú vị khi bạn nói "sửa đổi" tại chỗ. Tôi đã nghĩ CRC được thiết kế để phát hiện những sửa đổi nhỏ hơn trong các tệp/chuỗi lớn hơn vì nó được sử dụng để kiểm tra tính toàn vẹn. –
Đó là vấn đề. CRC rất nhanh để tính toán và phát hiện các thay đổi ngẫu nhiên, không phải lúc chịu được sự giải mã. –