it-swarm-vi.com

Tại sao hàm băm một chiều? Nếu tôi biết thuật toán, tại sao tôi không thể tính toán đầu vào từ nó?

Tại sao băm mật khẩu không thể được thiết kế ngược?

Tôi đã xem xét từ rất lâu rồi và đã đọc rất nhiều về nó, nhưng tôi không thể tìm thấy lời giải thích tại sao nó không thể được thực hiện. Một ví dụ sẽ giúp dễ hiểu câu hỏi của tôi hơn và để mọi thứ đơn giản, chúng tôi sẽ dựa trên thuật toán băm không sử dụng muối ( LanMan ).

Nói mật khẩu của tôi là "Mật khẩu". LanMan sẽ băm cái này và lưu nó trong cơ sở dữ liệu. Các chương trình bẻ khóa có thể bắt bẻ những thứ này bằng cách băm mật khẩu đoán mà bạn cung cấp. Sau đó, nó so sánh hàm băm được tạo với hàm băm trong cơ sở dữ liệu. Nếu có một trận đấu, nó làm việc ra mật khẩu.

Tại sao, nếu trình bẻ khóa mật khẩu biết thuật toán biến mật khẩu văn bản đơn giản thành hàm băm, thì nó có thể đảo ngược quá trình để tính mật khẩu từ hàm băm không?

Câu hỏi này là Câu hỏi bảo mật CNTT trong tuần.
[.__.] Đọc ngày 24 tháng 2 năm 2012 mục blog để biết thêm chi tiết hoặc gửi câu hỏi của riêng bạn Câu hỏi trong tuần.

231
Mucker

Hãy để tôi phát minh ra một "thuật toán băm mật khẩu" đơn giản để cho bạn thấy nó hoạt động như thế nào. Không giống như các ví dụ khác trong chủ đề này, cái này thực sự khả thi, nếu bạn có thể sống với một vài hạn chế mật khẩu kỳ quái. Mật khẩu của bạn là hai số nguyên tố lớn, x y. Ví dụ :

x = 48112959837082048697
y = 54673257461630679457

Bạn có thể dễ dàng viết chương trình máy tính để tính xy trong O ( [~ # ~] n [~ # ~ ] ^ 2) thời gian, trong đó [~ # ~] n [~ # ~] là số chữ số trong x y. (Về cơ bản điều đó có nghĩa là phải mất bốn lần miễn là các số đó dài gấp đôi. Có các thuật toán nhanh hơn, nhưng điều đó không liên quan.) Lưu trữ xy trong cơ sở dữ liệu mật khẩu.

x*y = 2630492240413883318777134293253671517529

Một đứa trẻ học lớp năm, được cho đủ giấy nháp, có thể tìm ra câu trả lời đó. Nhưng làm thế nào để bạn đảo ngược nó? Có nhiều thuật toán mọi người đã nghĩ ra để bao thanh toán số lượng lớn, nhưng ngay cả những thuật toán tốt nhất cũng chậm so với tốc độ bạn có thể nhân x bằng y. Và không có thuật toán nào trong số đó có thể được thực hiện bởi một học sinh lớp năm, trừ khi các số rất nhỏ (ví dụ: x = 3, y = 5).

Đó là thuộc tính chính : việc tính toán sẽ đơn giản hơn nhiều so với tiến lùi. Đối với nhiều vấn đề, bạn phải phát minh ra một thuật toán hoàn toàn mới để đảo ngược một tính toán.

Điều này không liên quan gì đến chức năng tiêm hoặc chức năng. Khi bạn bẻ khóa mật khẩu, thường không có vấn đề gì nếu bạn lấy cùng một mật khẩu hoặc nếu bạn nhận được một mật khẩu khác với cùng một hàm băm. Hàm băm được thiết kế để khó có thể đảo ngược nó và nhận bất kỳ câu trả lời nào, ngay cả một mật khẩu khác có cùng hàm băm. Trong crypto-speak: một hàm băm dễ bị tấn công tiền giả là hoàn toàn vô giá trị. (Thuật toán băm mật khẩu ở trên là nội dung nếu bạn có quy tắc x < y. )

Các chuyên gia mật mã làm gì? Đôi khi, họ cố gắng tìm ra các thuật toán mới để đảo ngược hàm băm (ảnh trước). Họ làm chính xác những gì bạn nói: phân tích thuật toán và cố gắng đảo ngược nó. Một số thuật toán đã được đảo ngược trước đó, một số khác thì không.

Bài tập cho người đọc : Giả sử cơ sở dữ liệu mật khẩu chứa mục sau:

3521851118865011044136429217528930691441965435121409905222808922963363310303627

Mật khẩu là gì? (Cái này thực sự không quá khó đối với máy tính.)

Chú thích : Do số lượng mật khẩu nhỏ mà mọi người chọn trong thực tế, hàm băm mật khẩu tốt không chỉ đơn giản là khó tính toán ngược mà còn tốn thời gian để tính toán chuyển tiếp, để làm chậm các cuộc tấn công từ điển. Là một lớp bảo vệ khác, muối ngẫu nhiên ngăn chặn việc sử dụng các bảng tấn công được tính toán trước (như "bảng cầu vồng").

Chú thích 2 : Làm thế nào để chúng ta biết rằng thật khó để đảo ngược hàm băm? Thật không may, chúng tôi không. Chúng tôi chỉ không biết bất kỳ cách dễ dàng để đảo ngược các hàm băm. Tạo một hàm băm khó có thể đảo ngược là chén thánh của thiết kế hàm băm và nó chưa đạt được (có lẽ điều đó sẽ không bao giờ xảy ra).

235
Dietrich Epp

Bây giờ THAT là một câu hỏi hay.

Trước tiên chúng ta phải đưa ra độ chính xác: nhiều hàm một chiều, đặc biệt là hàm băm như thường được sử dụng trong mật mã, chấp nhận đầu vào từ một không gian lớn hơn nhiều so với không gian của các giá trị đầu ra. Chẳng hạn, SHA-256 được định nghĩa cho các đầu vào là các chuỗi có tới 18446744073709551615 bit; có 218446744073709551616-1 các đầu vào có thể, nhưng vì đầu ra luôn là một chuỗi 256 bit, nên chỉ có 2256 đầu ra có thể cho SHA-256. Nhất thiết, một số đầu vào riêng biệt mang lại cùng một đầu ra. Do đó, đối với một đầu ra nhất định của SHA-256, không thể phục hồi rõ ràng the đầu vào đã được sử dụng, nhưng, có thể, có thể tính toán an đầu vào mang lại giá trị đầu ra đã cho. Điện trở trước nói về điều đó: khó khăn trong việc tìm kiếm đầu vào phù hợp cho đầu ra (bất kể đầu ra đó được lấy ở vị trí đầu tiên như thế nào).

Vì vậy, chúng tôi nói về một chức năng mà mọi người đều có thể tính toán trên bất kỳ đầu vào nào (sử dụng chương trình được biết đến công khai, không có giá trị bí mật nào liên quan - chúng tôi không nói về mã hóa).


Học giả nói gì

Không rõ liệu các chức năng một chiều có thực sự tồn tại hay không. Ngay bây giờ, chúng ta có nhiều chức năng mà không ai biết làm thế nào để đảo ngược; nhưng điều này không có nghĩa là chúng không thể để đảo ngược, theo nghĩa toán học. Tuy nhiên, xin lưu ý rằng điều đó không được chứng minh rằng các hàm một chiều không thể tồn tại, vì vậy hy vọng vẫn còn. Một số người nghi ngờ rằng liệu các hàm một chiều có thể tồn tại hay không có thể là một trong những khẳng định toán học vô nghĩa này không thể chứng minh cũng không bị bác bỏ ( định lý của Gôdel chứng minh rằng những thứ đó phải tồn tại). Nhưng cũng không có bằng chứng về điều đó.

Do đó, không có bằng chứng cho thấy bất kỳ hàm băm nhất định nào thực sự chống lại các tiền giả.

Có một số chức năng có thể được liên kết với các vấn đề khó khăn nổi tiếng. Chẳng hạn, if n là tích của hai số nguyên tố lớn, thì hàm x x2 mod n khó đảo ngược: có thể tính căn bậc hai modulo một số nguyên không nguyên tố n (trên cơ sở chung) là tương đương với khả năng yếu tố n , và vấn đề đó được biết là khó khăn. Không đã được chứng minh là khó khăn, làm phiền bạn; chỉ có các nhà toán học đã cố gắng thực hiện hiệu quả các số nguyên lớn trong (ít nhất) trong 2500 năm qua, và mặc dù đã có một số tiến bộ, nhưng không ai trong số những người thông minh này tìm thấy một thuật toán giết người thực sự cho điều đó. Kỷ lục thế giới về hệ số của một "mô đun RSA" (một sản phẩm của hai số nguyên tố lớn được chọn ngẫu nhiên có độ dài tương tự) là số nguyên 768 bit .

Một số hàm băm dựa trên "các vấn đề khó" như vậy đã được đề xuất; xem ví dụ MASH-1 và MASH-2 (trên vấn đề RSA ) và ECOH ( với các đường cong elip). Chỉ có một vài chức năng như vậy tồn tại, bởi vì:

  • Biến một "vấn đề khó" thành một hàm băm an toàn là không dễ dàng; có rất nhiều vấn đề khó khăn Chẳng hạn, trong khi trích xuất căn bậc hai modulo, một số không phải là số nguyên tố n is thường khó, có các giá trị mà việc trích xuất căn bậc hai là dễ dàng.

  • Hiệu suất của các hàm băm như vậy có xu hướng, giả sử là tối ưu. Giống như chậm hơn 100 lần so với SHA-1 thường được sử dụng.

Cách xây dựng hàm băm "chuẩn" hơn là kết hợp các nhà mật mã học và cùng nhau gặm nhấm một số thiết kế được đề xuất; các chức năng tồn tại trong các nỗ lực mã hóa trong một vài năm sau đó được coi là "có thể mạnh mẽ". Cuộc thi SHA- là một nỗ lực như vậy; người chiến thắng sẽ được công bố vào cuối năm nay. Trên 51 ứng cử viên (những người đã thành công bước hành chính), 14 người được giữ lại cho "vòng 2" và 14 người này đã được nhiều nhà mật mã xem xét tương đối chặt chẽ, và không ai trong số họ tìm thấy điều gì thực sự đáng nói về các chức năng. Danh sách đã được giảm xuống còn 5 và sẽ giảm xuống còn 1 "sớm", nhưng không phải vì lý do bảo mật (hầu hết các dữ liệu thực tế là về hiệu suất, không phải là kháng chiến).


Điều gì khiến MD5 khó đảo ngược

Vì chúng tôi không biết cách chứng minh rằng một hàm khó đảo ngược, điều tốt nhất chúng tôi có thể làm là thử nó trên một hàm cụ thể, để có được "trực giác" của làm thế nào các chức năng đạt được sức đề kháng rõ ràng của nó.

Tôi chọn MD5 , được biết đến nhiều. Đúng, MD5 là "hỏng" , nhưng đó là do va chạm, không phải là tiền đề. Có một cuộc tấn công đã biết tiền tấn công , ít nhất là về mặt lý thuyết, nhanh hơn so với cách chung ("cách chung" là "may mắn", tức là thử đầu vào cho đến khi trận đấu được tìm thấy, với chi phí trung bình 2128 các đánh giá vì MD5 có đầu ra 128 bit; cuộc tấn công Sasaki-Aoki có giá 2123.4, thấp hơn, nhưng vẫn còn quá cao để thực sự được thử, vì vậy kết quả vẫn chỉ là lý thuyết). Nhưng MD5 tương đối đơn giản và đã chịu được các cuộc tấn công trong một thời gian khá dài, vì vậy đây là một ví dụ thú vị.

MD5 bao gồm một số đánh giá về "chức năng nén" đối với các khối dữ liệu. Thông điệp đầu vào được đệm đầu tiên, để độ dài của nó trở thành bội số của 512 bit. Sau đó, nó được chia thành các khối 512 bit. Trạng thái chạy 128 bit (được giữ trong bốn biến 32 bit được gọi là [~ # ~] a [~ # ~], [~ # ~] b [~ # ~ ], [~ # ~] c [~ # ~] [~ # ~] d [~ # ~]) là được khởi tạo thành một giá trị thông thường, sau đó được xử lý bằng hàm nén. Hàm nén lấy trạng thái chạy và một khối thông báo 512 bit và trộn chúng thành một giá trị mới cho trạng thái chạy. Khi tất cả các khối thông báo đã được xử lý, giá trị cuối cùng của trạng thái đang chạy là đầu ra băm.

Vì vậy, hãy tập trung vào chức năng nén. Nó hoạt động như thế này:

  • Đầu vào: trạng thái đang chạy ( A B C D) và khối thông báo [~ # ~] m [~ # ~]. Khối tin nhắn là 512 bit; chúng tôi chia nó thành 16 từ 32 bit M, M1, M2, ... M15.
  • Đầu ra: giá trị trạng thái chạy mới.
  • Chế biến:

    1. Lưu trạng thái hiện tại trong một số biến: A → A ', B → B', C → C ' D → D '
    2. Thực hiện 64 vòng như thế này: [.__.]
      • Tính T = B + ((A + ftôi(B, C, D) + Mk + Xtôi) <<< stôi). Điều này đọc như thế này: chúng tôi tính toán một hàm đã cho ftôi (một hàm bitwise đơn giản, phụ thuộc vào số vòng i) over [~ # ~] b [~ # ~], [~ # ~] c [~ # ~], và [~ # ~] d [~ # ~]. Thêm vào đó là giá trị của [~ # ~] a [~ # ~], một tin nhắn Word Mk và hằng số Xtôi (bổ sung được thực hiện modulo 232). Xoay kết quả sang trái bởi một số bit (lượng dịch chuyển cũng phụ thuộc vào vòng). Cuối cùng, thêm [~ # ~] b [~ # ~]: kết quả là [~ # ~] t [~ # ~].
      • Xoay các từ trạng thái: D → A, C → D, B → C, T → B.
    3. Thêm các giá trị trạng thái đã lưu vào các biến trạng thái hiện tại: A + A '→ A, B + B' → B, C + C '→ C, D + D' → D.

Điểm quan trọng là có 64 vòng, nhưng chỉ có 16 từ tin nhắn. Điều này có nghĩa là mỗi thông báo Word sẽ xử lý bốn lần . Tôi viết nó in đậm vì nó là điểm trung tâm; đề kháng với tiền đề xuất phát từ đặc tính đó. Thông điệp nào Word được sử dụng trong mỗi vòng được mô tả trong thông số MD5 (RFC 1321); đặc tả cũng mô tả các hàm ftôi, số lần xoay stôi và hằng số 32 bit Xtôi.

Bây giờ giả sử rằng bạn đang cố gắng "đảo ngược" MD5; bạn bắt đầu từ đầu ra và làm việc từ từ lên chức năng nén. Trước tiên, bạn phải quyết định đầu ra của vòng 64. Thật vậy, đầu ra của hàm nén là tổng của đầu ra của vòng 64 và trạng thái đã lưu ( A ' B 'C' D ' giá trị). Bạn không có, vì vậy bạn phải chọn. Hy vọng của bạn là bạn sẽ có thể tìm thấy các giá trị cho các từ tin nhắn cho phép bạn có được đầu vào của vòng 1 một số giá trị phù hợp với quyết định tùy ý của bạn về A ' và anh em của nó .

Chúng ta hãy xem mọi thứ trông như thế nào khi bạn lùi chức năng nén. Bạn có đầu ra của một vòng (các biến [~ # ~] a [~ # ~], [~ # ~] b [~ # ~], [~ # ~] c [~ # ~] [~ # ~] d [~ # ~] sau vòng đấu) và bạn muốn tính toán lại input của vòng đó. Bạn đã biết các giá trị trước đó của [~ # ~] b [~ # ~], [~ # ~] c [~ # ~] và = [~ # ~] d [~ # ~], nhưng với [~ # ~] a [~ # ~] Mk bạn có nhiều lựa chọn: mỗi giá trị 32 bit có thể cho [~ # ~] a [~ # ~] và mỗi giá trị có Mk. Lúc đầu, bạn rất vui vì điều đó; Ai sẽ từ chối tự do như vậy? Chỉ cần chọn ngẫu nhiên Mk và điều này mang lại [~ # ~] a [~ # ~] chỉ với một vài thao tác (hãy thử!).

Nhưng sau khi bạn đã đảo ngược cách đó 16 vòng (vòng 49 đến 64, vì bạn đang làm việc ngược), tự do biến mất. Bạn đã "chọn" các giá trị của tất cả các từ tin nhắn. Khi cố gắng đảo ngược vòng 48, bạn muốn tính lại giá trị của [~ # ~] a [~ # ~] ngay trước vòng đó; theo thông số MD5, thông báo Word M2 được sử dụng trong vòng 48 và bạn đã chọn giá trị M2 (khi đảo ngược vòng 63). Vì vậy, chỉ có một lựa chọn cho [~ # ~] a [~ # ~]. Vì vậy, những gì, bạn sẽ nói. Một lựa chọn là đủ để tiếp tục đi bộ lạc hậu. Vì vậy, bạn tiếp tục.

Bây giờ, bạn đang ở đầu của chức năng nén. Hãy nhớ rằng, ban đầu, bạn đã thực hiện một lựa chọn tùy ý các giá trị A 'B' C 'D': điều này cho phép bạn tính toán đầu ra của vòng 64 và bắt đầu đi lùi. Bây giờ bạn đã có được đầu vào của vòng 1, trùng với A 'B' C 'D' ... và nó không khớp. Điều đó khá bình thường: bạn đã chọn A 'B' C 'D' tùy ý và bạn cũng đã chọn các từ tin nhắn Mk tùy ý, vì vậy có thể dự kiến ​​rằng nó sẽ không hoạt động hầu hết thời gian. Vì vậy, bạn cố gắng sửa chữa tính toán, bằng cách thay đổi hồi cứu hoặc lựa chọn ban đầu của bạn là A 'B' C 'D', hoặc một hoặc một vài ngẫu nhiên lựa chọn cho Mk. Nhưng mỗi sửa đổi trên bất kỳ Mk ngụ ý sửa đổi ở nơi khác, vì mỗi Mk được sử dụng bốn lần. Vì vậy, bạn cần sửa đổi khác để hủy bỏ những cái khác, v.v.

Tại thời điểm đó, bạn bắt đầu hiểu vấn đề đảo ngược MD5: mỗi lần bạn chạm vào một bit, nó sẽ kích hoạt rất nhiều sửa đổi trong suốt thuật toán, bạn cần phải hủy bỏ bằng cách chạm vào các bit khác và chỉ có quá nhiều tương tác . Về cơ bản, bạn tung hứng với 2128 quả bóng cùng một lúc, và đó là quá nhiều để theo dõi tất cả chúng.

Nếu mỗi khối tin nhắn dài 2048 bit, chia thành 64 từ và mỗi tin nhắn Word chỉ được sử dụng một lần trong MD5, thì bạn có thể đảo ngược nó dễ dàng. Bạn làm như trên: lựa chọn tùy ý A 'B' C 'D', lựa chọn từ thông báo tùy ý cho các vòng từ 64 đến 5; và trong bốn vòng đầu tiên, bạn chỉ cần xem xét giá trị bạn muốn đạt được cho đầu vào vòng (giá trị phù hợp với lựa chọn tùy ý của bạn là A ', B', C ' hoặc D') và tìm ra thông báo Word tương ứng. Dễ như ăn bánh. Nhưng MD5 không xử lý dữ liệu theo các khối 2048 bit, mà bằng các khối 512 bit và mỗi thông báo Word được sử dụng bốn lần.


Một số vòng xoắn bổ sung

Cấu trúc của hàm nén của MD5 thực sự là một khái quát của một mật mã Feistel . Trong mật mã Feistel, dữ liệu được chia thành hai nửa và, đối với mỗi vòng, chúng tôi thay đổi một nửa bằng cách thêm/xé nó thành giá trị trung gian được tính từ nửa kia và từ khóa; và sau đó chúng tôi trao đổi hai nửa. Mở rộng lược đồ này thành phân chia bốn phần và bạn có cùng cấu trúc so với các vòng MD5 - với góc xoay 90 độ: MD5 trông giống như mã hóa của trạng thái hiện tại sử dụng khối thông báo như key (và có thêm đầu ra của vòng 64 với trạng thái đã lưu, loại bỏ MD5 khỏi một mật mã được xoay).

Vì vậy, có lẽ chúng ta có thể xây dựng các hàm băm ra khỏi mật mã khối? Thật vậy, chúng ta có thể: đó là những gì Whirlpool là về. Hàm băm được xây dựng trên một mật mã khối xoay (khối thông báo là khóa); mật mã khối của Whirlpool là "W", một dẫn xuất của Rijndael, được biết đến với cái tên AES . Nhưng W có các khối lớn hơn (512 bit thay vì 128 bit) và lịch trình khóa được bổ sung.

Khi bạn tạo một hàm băm từ một mật mã khối được xoay, thì các cuộc tấn công tiền tố vào hàm băm có phần tương đương với các cuộc tấn công tái cấu trúc khóa trên mật mã khối; Vì vậy, có một số hy vọng rằng nếu mật mã khối là an toàn, thì hàm băm cũng vậy. Có một lần nữa, có những chi tiết lén lút. Ngoài ra, đối với cấu trúc như vậy, va chạm trên hàm băm giống như các cuộc tấn công khóa liên quan trên mật mã khối; Các cuộc tấn công khóa liên quan thường được coi là không gây tử vong và thường bị bỏ qua (ví dụ, chúng không phải là một phần của tiêu chí đánh giá cho cuộc thi AES và Rijndael được cho là hơi thất vọng về mặt đó, đó là lý do tại sao W có khóa hoàn toàn mới lịch trình).

Một số thiết kế mới hơn được xây dựng trên một mật mã khối là không được xoay, để bảo mật của hàm băm có thể được lấy trực tiếp nhiều hơn từ bảo mật của mật mã khối; xem, ví dụ, ứng cử viên SHA-3 Skein , được xác định qua một mật mã khối gọi là Threefish.

Ngược lại, người ta có thể cố gắng tạo một mật mã khối ra khỏi hàm băm. Xem ví dụ SHACAL , đó là SHA-1 "được đặt thẳng". Và, trên cue, SHACAL có một số điểm yếu liên quan khá giống với điểm yếu đã biết của SHA-1 liên quan đến va chạm (không có va chạm thực tế nào được tính toán, nhưng chúng tôi có một phương pháp nhanh hơn gần một triệu lần so với thuật toán tìm va chạm chung).

Do đó, trái với những gì tôi đã nói trong phần giới thiệu của bài đăng này, chúng tôi đã nói chuyện mã hóa suốt. Vẫn còn nhiều điều cần được khám phá và nghiên cứu về các liên kết giữa các hàm băm và mã hóa đối xứng.


TL; DR: không có TL; DR cho thông báo này. Đọc toàn bộ, hoặc ăn xin.

128
Thomas Pornin

Bước đầu tiên để trả lời ở đây là xem các ví dụ, như Nice từ @Dietrich, các chức năng khó chạy hơn một hướng so với nghịch đảo, và đã chống lại nhiều nỗ lực tìm kiếm một bước đột phá tốc độ. Nhưng vấn đề rất phức tạp, vì vậy tôi sẽ cố gắng giải thích thêm.

Rất nhiều người dường như rơi vào cái bẫy (heh) khi nghĩ rằng các hàm băm là thực sự bằng cách nào đó kỳ diệu - rằng chúng thực sự là "hàm một chiều" tuyệt đối mà toán học không thể chạy ngược tất cả, chỉ vì chúng được gọi là băm. Đây không phải là một cách lành mạnh để suy nghĩ về nó trong một diễn đàn bảo mật. Nó thường sai trong thực tế. Và nó luôn luôn sai trong lý thuyết, đưa ra định nghĩa toán học cơ bản của hàm là ánh xạ từ miền sang hình ảnh .

Tất cả các băm có thể được đảo ngược, theo nguyên tắc. Nó có thể lộn xộn và tàn bạo (như trong vũ phu), nó có thể mất một thời gian dài không chính thức với phần cứng ngày nay, và nó thậm chí có thể giữ được một đoạn đường dài, nhưng về mặt toán học thì đơn giản chỉ là vấn đề thời gian. Như @mucker lưu ý, tất cả thông tin đều có để tìm mật khẩu gốc, (hoặc, ít nhất, một mật khẩu hoạt động). Nếu chúng ta quên điều đó, chúng ta sẽ quên đi sự nguy hiểm của các heuristic thông minh đối với các mật khẩu có khả năng chọn anh đào, điều này tạo ra tin tức thường xuyên. Băm là một vấn đề kỹ thuật và thách thức chính là một vấn đề hiệu quả - làm thế nào để tốn kém để tìm mật khẩu cho hàm băm. Một trong những kết quả chính của kiểu suy nghĩ đó là tầm quan trọng của việc băm mật khẩu chậm

Và khoa học và toán học băm chỉ đang dần trở nên tốt hơn. Thực sự không có bất kỳ bằng chứng nào cho thấy bất kỳ băm nào thực sự khó khăn. Câu trả lời của @ Dietrich là một cách hay để minh họa cách các hàm băm lý tưởng might có thể. Nhưng chỉ cần nhìn vào các chuyên gia thực sự mô tả cách chúng tôi không có bằng chứng cho bất kỳ thuật toán mã hóa tốt nhất nào: Mô hình toán học đằng sau tuyên bố bảo mật của thuật toán mã hóa đối xứng và thuật toán tiêu hóa là gì?

Việc LanMan được trích dẫn trong câu hỏi vẫn còn nhiều bằng chứng cho thấy chúng ta cần tránh lý tưởng hóa các giá trị băm. LanMan là bất cứ thứ gì ngoại trừ một hàm băm lý tưởng, dễ dàng bị đánh bại bởi sự kết hợp của một chút phân tích và một chút vũ phu. Để biết một ví dụ phổ biến khác về hàm băm khủng khiếp, hãy xem MySQL OLD_PASSWORD cryptanalysis? .

Vì vậy, hãy tự mình thoát ra khỏi cái bẫy - rơi vào đó không cần phải là một chuyến đi một chiều. Nhận ra rằng băm có thể đảo ngược và giữ cho tư duy bảo mật đáng tin cậy hoạt động khi bạn tìm cách tốt nhất để đảo ngược chúng. Đó thường là cách tốt nhất để tìm những thứ thực sự khó đảo ngược. Tôi không cố gắng thực hiện tham vọng về các thực tiễn tốt nhất hiện có, như bcrypt hoặc PBKDF2 hoặc tiền điện tử. Nhưng bằng chứng rõ ràng là ngay cả những lập trình viên giỏi cũng nhận được những thứ này quá thường xuyên. vì vậy hãy cẩn thận với cách bạn sử dụng chúng và đừng cố gắng tự phát minh ra.

17
nealmcb

Bởi vì đó là cách các hàm băm mật mã hoạt động, chúng là các hàm toán học một chiều (từ đơn giản đến băm). Các thuật toán được thực hiện và kiểm tra cụ thể để tránh điều đó, và cũng tránh va chạm (2 văn bản đơn giản khác nhau tạo ra cùng một hàm băm).

Bạn có thể đọc thêm trên wikipedia , nhưng điểm chính của bài viết là:

Hàm băm mật mã lý tưởng có bốn thuộc tính chính hoặc quan trọng:

  • thật dễ dàng (nhưng không nhất thiết phải nhanh chóng) để tính giá trị băm cho bất kỳ thông điệp nào
  • không thể tạo ra một thông điệp có hàm băm nhất định
  • không thể sửa đổi tin nhắn mà không thay đổi hàm băm
  • không thể tìm thấy hai thông điệp khác nhau có cùng hàm băm

Hầu hết các cuộc tấn công vào các hàm băm đều dựa trên việc tìm kiếm các xung đột (vì vậy 2 văn bản đơn giản khác nhau sẽ khớp với cùng một hàm băm) hoặc tạo ra hàng triệu giá trị băm và so sánh chúng cho đến khi bạn tìm thấy đơn giản tạo ra nó.

Lịch sử dài: nếu thuật toán băm là có thể đảo ngược hoặc có thể bị tấn công theo cách đó, thì đó không phải là thuật toán băm tốt.

Đối với mật khẩu, điều tra bằng BCrypt, bài đăng này có rất nhiều thông tin về nó.

12
coredump

Hãy tưởng tượng một hàm băm sử dụng một bit cho hàm băm. Vì vậy, hàm băm của bạn có thể là 0 hoặc 1.

Và giả sử hàm băm cộng thêm mỗi byte dữ liệu và nếu dữ liệu là số chẵn thì giá trị băm là 0. Nếu dữ liệu là số lẻ, hàm băm là 1.

Bạn có thấy lý do tại sao bạn không thể khôi phục dữ liệu của mình bằng kỹ thuật đảo ngược hàm băm đó không?

Điều này cũng tương tự đối với các thuật toán băm thực tế, chỉ có các công thức tốt hơn đáng kể so với hàm tôi vừa mô tả.

Khó khăn của bạn có thể là bạn đang xem xét băm cho đến khi họ sử dụng mật khẩu. Không rõ ràng tại sao bạn không thể khôi phục mật khẩu 8 ký tự từ hàm băm 128 bit. Nhưng hàm băm mà bạn sử dụng cho mật khẩu cũng có thể được sử dụng để tính toán hàm băm của toàn bộ terabyte dữ liệu và hàm băm sẽ vẫn chỉ mất 128 bit dữ liệu. Rõ ràng, bạn không thể đảo ngược kỹ thuật băm 128 bit đó và khôi phục dữ liệu terabyte của bạn.

Ngoài ra, giả sử bạn có mọi hoán vị có thể của một terabyte dữ liệu, sẽ có một lượng lớn dữ liệu khác nhau tạo ra cùng một hàm băm. Rốt cuộc, nếu bạn có hơn 2 ^ 127 hoán vị dữ liệu khác nhau, bạn có khả năng gặp phải hai dữ liệu khác nhau có cùng hàm băm.

8
user1068775

Có những thuật toán vốn không thể đảo ngược; họ thay đổi đầu vào A thành đầu ra B theo cách mà ngay cả khi bạn biết các bước chính xác của thuật toán, bạn không thể khôi phục A từ B.

Một ví dụ rất đơn giản: chuyển đổi từng ký tự trong mật khẩu thành giá trị ASCII và tổng tất cả các giá trị. Không có cách nào bạn có thể khôi phục mật khẩu gốc từ kết quả.

4
Massimo

Có một khía cạnh của vấn đề mà mọi người đang thiếu trong các câu trả lời trước. Đó là bản chất nhiều-một của hàm băm. Vì (hầu hết) các hàm băm là đầu ra có độ dài cố định (ví dụ: 256 bit), về mặt kỹ thuật có vô số chuỗi mà tất cả các hàm băm có cùng giá trị.

Ví dụ: nếu bạn lấy tất cả các chuỗi 512 bit (trong đó có 2 ^ 512). Chỉ có 2 ^ 256 đầu ra của hàm băm. Do đó, đối với mỗi đầu ra của hàm băm, có khoảng 2 ^ 256 chuỗi 512 bit băm đến giá trị đó. Tôi nói đại khái bởi vì chúng ta không biết nếu hàm băm thực sự là một hàm ngẫu nhiên, nó có thể có những sai lệch nhỏ.

Do đó, được đưa ra một thông báo, có nhiều chuỗi băm đến cùng một giá trị. Do đó, nếu bạn định nghĩa "đảo ngược hàm băm" là xuất mật khẩu người dùng, thì chức năng đảo ngược của bạn sẽ xử lý như thế nào với số lượng chuỗi vô hạn có thể dẫn đến thông báo đã cho?

2
mikeazo

Bạn đang hỏi "tại sao điều quan trọng là các hàm băm là một chiều?" Đó là một tài sản bảo mật.

Có hai loại "băm" (hoặc "thông báo tiêu hóa" như chúng được gọi) ngày nay được sử dụng phổ biến. Một là một bản tóm tắt thông điệp đơn giản, mà bạn có thể quen thuộc với thuật toán tổng kiểm tra, chẳng hạn như CRC32. Thuật toán được thiết kế sao cho một thay đổi bit đơn trong đầu vào sẽ mang lại giá trị tiêu hóa khác nhau. Mục đích chính của việc này là để đảm bảo rằng một tin nhắn không bị hỏng do tai nạn. Tổng kiểm tra CRC32 có mặt trên mọi gói TCP/IP và kết quả khớp sai trong truyền lại để sửa lỗi.

Thông báo tin nhắn thường được sử dụng trong mật mã như là một phần của việc "ký" tin nhắn. Tin nhắn được mã hóa bởi người gửi bằng khóa riêng của anh ấy và bất kỳ ai cũng có thể sử dụng khóa chung để xác thực rằng nó chỉ được mã hóa bởi người gửi. Nhưng mật mã khóa công khai RSA chỉ có thể mã hóa các tin nhắn nhỏ hơn kích thước khóa (256 byte), ngắn hơn nhiều so với hầu hết các tin nhắn hữu ích. Các thuật toán thông báo tiêu hóa tạo ra các giá trị nhỏ hơn các khóa RSA. Vì vậy, bằng cách mã hóa thông báo thay vì tin nhắn, chữ ký RSA có thể được sử dụng trên bất kỳ tin nhắn kích thước nào.

Nhưng một thông báo thông thường không an toàn trước kẻ tấn công. Hãy xem xét một tổng kiểm tra rất đơn giản chỉ tính tổng các giá trị của các ký tự. Nếu bạn đã ký một tổng kiểm tra như vậy, tôi có thể trao đổi bất kỳ tin nhắn nào khác mang lại cùng một tổng kiểm tra và các chữ ký sẽ khớp, đánh lừa nạn nhân.

Một cách sử dụng phổ biến khác cho thông báo tiêu hóa là bảo vệ mật khẩu trong quá trình lưu trữ. Nếu bạn mã hóa mật khẩu trước khi lưu trữ chúng trong hệ thống, quản trị viên hệ thống biết khóa có thể giải mã tất cả. (Bạn có thể đã nhận thấy vấn đề này gần đây khi một số trang web bị hack.)

Để tránh những vấn đề này, một loại băm khác là cần thiết, một loại "an toàn về mặt mật mã". Một thuật toán băm an toàn có hai thuộc tính bổ sung, khả năng chống va chạmkhông thể đảo ngược.

Kháng va chạm có nghĩa là tôi sẽ không thể tìm thấy một thông điệp tạo ra cùng một thông báo. Bằng cách đó tôi không thể trao đổi thông điệp xấu xa của tôi cho thông điệp tốt của bạn.

Thuộc tính không thể đảo ngược có nghĩa là tôi không thể biến một bản tóm tắt thành bản rõ để tôi không thể giải mã tin nhắn gốc, như mật khẩu của người dùng.

Tạo một bản tóm tắt là một vấn đề rất giống với mã hóa, ở chỗ bạn phải xáo trộn dữ liệu theo cách mà nó không rò rỉ thông tin về dữ liệu gốc. Điều đó thậm chí còn khó hơn, bởi vì toán học tương tự phải không đưa ra bất kỳ manh mối nào về cách tạo thành công một vụ va chạm.

1
John Deters

Tôi nghĩ có nhiều lý do, nhưng một lý do rõ ràng: một bản tóm tắt được tạo ra bởi hàm băm không bao giờ có thể chứa thông tin vô hạn, vì bản tóm tắt có các bit hữu hạn. Nhưng hàm băm có thể được sử dụng để băm đầu vào của thông tin vô hạn. Đầu vào thực sự có thể là bất cứ điều gì.

Khó khăn để tìm ra một vụ va chạm không phải là câu trả lời. Khó khăn thực sự là chứng minh dữ liệu gốc của bạn thực sự là đầu vào khả dĩ duy nhất phù hợp với một thông báo nhất định. Tôi nghĩ rằng bạn có thể không bao giờ tính toán một đầu vào và tuyên bố đó là câu trả lời duy nhất cho thông báo.

0
Lucifer Orichalcum

Những người khác đã giải thích tại sao các hàm băm mật mã tốt rất khó đảo ngược - nhưng theo bài viết trên Wikipedia này , LanMan được thiết kế kém và có thể đảo ngược tương đối dễ dàng:

Mặc dù dựa trên DES, một mật mã khối được nghiên cứu kỹ lưỡng, hàm băm LM không phải là chức năng một chiều thực sự vì mật khẩu có thể được xác định từ hàm băm vì một số điểm yếu trong quá trình thực hiện ... Bằng cách cài đặt một cuộc tấn công vũ phu trên mỗi nửa riêng biệt, các máy tính để bàn hiện đại có thể bẻ khóa băm chữ số LM trong vài giờ ... Năm 2003, Ophcrack, một triển khai của kỹ thuật bảng Rainbow, đã được xuất bản. Nó đặc biệt nhắm vào các điểm yếu của mã hóa LM và bao gồm dữ liệu được tính toán trước đủ để bẻ khóa hầu như tất cả các băm LM chữ và số trong vài giây.

0
James