it-swarm-vi.com

Bảng Rainbow là gì và chúng được sử dụng như thế nào?

Tôi có thể tìm thấy ở đâu? Có một nồi vàng ở cuối?
[.__.] Làm thế nào để tôi bảo vệ chống lại họ?


Từ đề xuất Area51

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

149
AviD

Bảng Rainbow thường bị nhầm lẫn với một kỹ thuật khác, đơn giản hơn, tận dụng sự đánh đổi lưu trữ thời gian tính toán trong phục hồi mật khẩu: bảng băm.

Các bảng băm được xây dựng bằng cách băm từng Word trong một từ điển mật khẩu. Các cặp băm mật khẩu được lưu trữ trong một bảng, được sắp xếp theo giá trị băm. Để sử dụng bảng băm, đơn giản lấy hàm băm và thực hiện tìm kiếm nhị phân trong bảng để tìm mật khẩu gốc, nếu có.

Bàn cầu vồng phức tạp hơn. Xây dựng bảng Rainbow đòi hỏi hai điều: hàm băm và hàm khử. Hàm băm cho một bộ Rainbow Table đã cho phải khớp với mật khẩu băm mà bạn muốn khôi phục. Hàm khử phải biến đổi một hàm băm thành một thứ có thể sử dụng làm mật khẩu. Một hàm rút gọn đơn giản là Base64 mã hóa hàm băm, sau đó cắt nó thành một số ký tự nhất định.

Các bảng cầu vồng được xây dựng từ "chuỗi" có độ dài nhất định: 100.000 chẳng hạn. Để xây dựng chuỗi, chọn một giá trị hạt ngẫu nhiên. Sau đó áp dụng các hàm băm và khử cho hạt giống này, và đầu ra của nó, và tiếp tục lặp lại 100.000 lần. Chỉ hạt giống và giá trị cuối cùng được lưu trữ. Lặp lại quá trình này để tạo ra nhiều chuỗi như mong muốn.

Để khôi phục mật khẩu bằng Bảng cầu vồng, hàm băm mật khẩu trải qua quá trình trên với cùng độ dài: trong trường hợp này là 100.000 nhưng mỗi liên kết trong chuỗi được giữ lại. Mỗi liên kết trong chuỗi được so sánh với giá trị cuối cùng của mỗi chuỗi. Nếu có sự trùng khớp, chuỗi có thể được xây dựng lại, giữ cả đầu ra của từng hàm băm và đầu ra của từng hàm khử. Chuỗi được xây dựng lại đó sẽ chứa hàm băm của mật khẩu được đề cập cũng như mật khẩu đã tạo ra nó.

Điểm mạnh của bảng băm là việc khôi phục mật khẩu nhanh như chớp (tìm kiếm nhị phân) và người xây dựng bảng băm có thể chọn những gì đi vào nó, chẳng hạn như 10.000 mật khẩu hàng đầu. Điểm yếu so với Rainbow Table là các bảng băm phải lưu trữ mỗi cặp mật khẩu băm duy nhất.

Bảng Rainbow có lợi ích cho người xây dựng các bảng đó có thể chọn dung lượng cần thiết bằng cách chọn số lượng liên kết trong mỗi chuỗi. Càng nhiều liên kết giữa hạt giống và giá trị cuối cùng, càng có nhiều mật khẩu được nắm bắt. Một điểm yếu là người xây dựng chuỗi không chọn mật khẩu họ nắm bắt để Bảng Rainbow không thể được tối ưu hóa cho các mật khẩu phổ biến. Ngoài ra, phục hồi mật khẩu liên quan đến việc tính toán chuỗi băm dài, làm cho phục hồi trở thành một hoạt động đắt tiền. Chuỗi càng dài, mật khẩu càng bị bắt trong đó, nhưng cần nhiều thời gian hơn để tìm mật khẩu bên trong.

Bảng băm tốt cho các mật khẩu phổ biến, Rainbow Table tốt cho các mật khẩu khó. Cách tiếp cận tốt nhất sẽ là khôi phục càng nhiều mật khẩu càng tốt bằng cách sử dụng bảng băm và/hoặc bẻ khóa thông thường với một từ điển của mật khẩu N hàng đầu. Đối với những người còn lại, sử dụng Bàn Rainbow.

180
Crunge

Có nhiều cách giải thích tốt về bảng Rainbow là gì, cái này Cách Rainbow Rainbow hoạt động đặc biệt tốt. Ngoài ra bài viết Wikipedia cũng có một lời giải thích rất tốt. Để hiểu sâu hơn một chút, hãy đọc bài viết dứt khoát về chủ đề này là Tạo ra sự đánh đổi bộ nhớ thời gian mã hóa nhanh hơn .

Một lời giải thích đơn giản về Rainbow Table là họ sử dụng kỹ thuật đánh đổi bộ nhớ thời gian. Có nghĩa là thay vì lấy một giá trị băm mục tiêu và một từ điển các từ sau đó băm từng Word và thực hiện so sánh nhanh chóng (phương pháp tiếp cận bạo lực bằng cách sử dụng một cái gì đó như John ), thay vào đó, bạn băm tất cả các giá trị trong từ điển trước (điều này có thể mất một thời gian rất dài tùy thuộc vào kích thước từ điển). Nhưng một khi đã xong, bạn có thể so sánh bao nhiêu giá trị băm mà bạn muốn so với các giá trị được băm trước trong các bảng Rainbow, điều này nhanh hơn đáng kể so với việc tính lại các giá trị băm.

Lời giải thích tôi đã viết ở đây trước đây trong một nỗ lực ngắn gọn là sai lệch, vì nó không giải thích việc sử dụng các mức giảm mà các bảng Rainbow sử dụng. Để giải thích rõ hơn cho đến khi tôi viết lại bit này, hãy xem @ Crunge answer .

Bạn có thể tự tạo bảng Rainbow bằng một ứng dụng như RainbowCrack hoặc bạn có thể tải xuống từ các nguồn như Nhóm Shmoo , Bảng Rainbow miễn phí dự án website, Ophcrack dự án và nhiều nơi khác tùy thuộc vào loại băm bạn cần bảng.

Để bảo vệ chống lại cuộc tấn công dựa trên Bảng Cầu vồng, phương pháp chống lại hiệu quả nhất là đảm bảo rằng mọi hàm băm trong một hệ thống là muối . Điều này làm cho các bảng Rainbow được tạo trước trở nên vô dụng và có nghĩa là kẻ tấn công sẽ phải tạo một bộ bảng tùy chỉnh để sử dụng để chống lại các bảng băm được nhắm mục tiêu, điều này chỉ có thể xảy ra nếu chúng biết muối.

15
Mark Davidson

Mục đích và sự liên quan

Các bảng cầu vồng giúp bẻ khóa các mật khẩu khó, tức là những mật khẩu thậm chí không thể tìm thấy trong một từ điển lớn. Mật khẩu được lưu trữ trong lịch sử dưới dạng băm đơn giản trong cơ sở dữ liệu và đó là những gì bảng Rainbow có hiệu quả chống lại: tạo một bảng Rainbow duy nhất (chậm) và chạy bất kỳ số lượng cơ sở dữ liệu nào có băm đối với nó (nhanh).

Ngày nay, ngày càng có nhiều hệ thống sử dụng các thuật toán lưu trữ mật khẩu thích hợp như Bcrypt, Scrypt hoặc Argon2. Xem: Cách bảo mật [lưu trữ] mật khẩu? Các thuật toán đó không còn "dễ bị tổn thương" đối với các bảng Rainbow: vì mỗi hàm băm là duy nhất, ngay cả khi mật khẩu bằng nhau, các bảng Rainbow không còn hoạt động.

Đó là lý do tại sao các bảng Rainbow không phổ biến ngày nay. Ngay cả khi thứ gì đó hiện đại như Argon2 không được sử dụng, các nhà phát triển ngày nay thường biết rằng ít nhất họ nên sử dụng một loại muối. Điều đó đã đủ để làm cho một bàn Rainbow trở nên vô dụng.

Chúng hoạt động như thế nào

Tạo bảng

Hãy tưởng tượng chúng ta tạo một bảng Rainbow chỉ với hai chuỗi, mỗi chuỗi dài 5. Bảng Rainbow dành cho hàm băm hư cấu MD48, tạo ra 48 bit (chỉ có 12 ký tự thập lục phân). Khi xây dựng chuỗi, chúng ta thấy điều này:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj
Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD

Chúng tôi bắt đầu với 0 bởi vì đó là chuỗi đầu tiên (chúng tôi chỉ cần một số giá trị để bắt đầu). Khi chúng ta băm cái này bằng MD48, nó biến thành cfcd208495d5. Bây giờ chúng tôi áp dụng chức năng "rút gọn" về cơ bản định dạng hàm băm này thành mật khẩu và chúng tôi kết thúc bằng "z". Khi chúng tôi băm nó một lần nữa, chúng tôi nhận được fbade9e36a3f, sau đó giảm lại lần nữa và nhận renjaj820. Có một số chu kỳ nữa và kết quả cuối cùng là WLgOSj.

Tương tự cho chuỗi thứ hai. Chúng tôi chỉ bắt đầu với một giá trị khác và làm điều tương tự. Điều này kết thúc bằng 0uUoAD.

Bảng Rainbow hoàn chỉnh của chúng tôi là đây:

WLgOSj => 0
0uUoAD => 1

Đó là tất cả những gì bạn phải lưu trữ.

Tra cứu hàm băm

Giả sử chúng ta đã tìm thấy một hàm băm trực tuyến, 7668b2810262. Hãy bẻ khóa nó bằng cách sử dụng bảng của chúng tôi!

Looking for hash '7668b2810262', reduced to 'aL'.
hashed=>reduced 'aL' to ieioB
hashed=>reduced 'ieioB' to WLgOSj
Found a match, 'WLgOSj' is in our Rainbow table:
    WLgOSj => 0
The chain starts with '0'. Let's walk that chain and look for the hash.
hashed '0' to cfcd208495d5
hashed 'z' to fbade9e36a3f
hashed 'renjaj820' to 7668b2810262
That hash matches! Found the password: renjaj820

Để tự mình giải quyết, các ví dụ trên đã được tạo bằng cách sử dụng Python script: https://Gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Thuộc tính tỷ lệ

Nói ngắn gọn:

  • Tra cứu nhanh có nghĩa là các bảng lớn hơn, giả sử phạm vi bảo hiểm giữ nguyên.
  • Bảo hiểm tốt hơn có nghĩa là tra cứu chậm hơn hoặc bảng lớn hơn.
  • Bảng nhỏ hơn có nghĩa là tra cứu chậm hơn hoặc phạm vi bảo hiểm kém hơn.

Các phần sau đây giả sử thời gian cho mỗi lần băm + giảm là 1 Lời nói và không tính đến các va chạm. Đây là tất cả các số của sân bóng, có nghĩa là ví dụ và không phải là giá trị chính xác.

Thời gian tra cứu

Nếu thao tác băm + giảm mất một phần triệu giây, thì việc tạo bảng có một triệu chuỗi và giảm 10 000 cho mỗi chuỗi sẽ mất khoảng 3 giờ:
[.__.] chain_length × chain_count / reductions_per_second / seconds_per_hour
[.__.] = 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 giờ.

Thực hiện tra cứu trong bảng đó mất trung bình 10 mili giây. Điều này là do chúng ta thường sẽ phải trải qua chain_length/2 giảm trước khi chúng tôi tìm thấy chuỗi nào chứa hàm băm. Ví dụ: chúng ta có thể phải thực hiện 3000 lần giảm trên hàm băm trước khi tìm thấy giá trị trong bảng. Tiếp theo, chúng ta phải thực hiện lại chuỗi đó từ đầu cho đến khi tìm thấy giá trị khớp. Nếu chúng ta chỉ phải thực hiện 3000 để tìm thấy nó trong bảng của mình, thì chúng ta phải thực hiện giảm 7000 từ đầu để đến đúng điểm trong chuỗi. Về cơ bản, chúng tôi thực hiện nhiều thao tác khi tìm kiếm như khi tạo một chuỗi đơn. Do đó, thời gian tra cứu là 10 000 lần một micro giây, tức là mười mili giây (hoặc một phần trăm giây, nếu bạn muốn).

Yêu cầu lưu trữ

Khi bạn muốn tạo một bảng tra cứu đầy đủ, nhanh chóng cho hàm băm, thậm chí MD5, bạn vẫn cần một bộ lưu trữ hàng trăm tỷ tỷ terabyte. Điều đó không hữu ích lắm. Nhưng nếu chúng ta chỉ muốn bao gồm mật khẩu chữ thường cho đến 10 ký tự thì sao?

Nếu chúng ta muốn dành tối đa 30 giây để tìm kiếm một hàm băm và giả sử chúng ta cần 1 micro giây (một phần triệu giây) cho mỗi hàm băm + giảm chu kỳ, thì chúng ta có thể có độ dài chuỗi: 1 million × 30 = 30 triệu. Có 2610 (hoặc 1014) mật khẩu chữ thường có thể có 10 ký tự và mỗi chuỗi chúng tôi bao gồm 30 triệu giá trị. Điều đó để lại cho chúng tôi 4 triệu chuỗi. Chúng tôi biết rằng mỗi chuỗi chỉ có một giá trị bắt đầu và kết thúc được lưu trữ và mỗi giá trị là 10 ký tự. Vì thế 2 × 10 × 4 million = 76 dữ liệu MiB.

Tạo bảng bằng cách lặp qua tất cả mật khẩu 10 ký tự mất nhiều thời gian: 30 giây cho mỗi chuỗi, thời gian 4 triệu chuỗi là khoảng 91 năm. Tuy nhiên, rất nhiều người sẽ quan tâm đến một bảng như vậy, do đó, bằng cách gộp 1092 CPU (= 91 × 12), chỉ mất 1 tháng. Điều này cho thấy một bảng nhỏ như vậy có thể được so sánh với không gian mật khẩu mà nó bao gồm: việc tra cứu chỉ mất 30 giây và bạn chỉ phải lưu trữ dữ liệu 76MiB.

Phần kết luận

Các bảng cầu vồng có thể được coi là một đánh đổi bộ nhớ thời gian : một cửa hàng chỉ lưu một phần nhỏ của bảng và phục hồi nó thông qua một số tính toán bổ sung về thời gian tra cứu. Đây là một phần lý do tại sao muối, hay đúng hơn, một thuật toán lưu trữ mật khẩu tốt như Scrypt hoặc Argon2 rất quan trọng để giữ mật khẩu an toàn. Bảng Rainbow chỉ có thể khôi phục mật khẩu đã được muối nếu bảng chứa mục nhập đủ lớn để chứa cả muối và mật khẩu, đó sẽ là cực kỳ không hiệu quả và đánh bại toàn bộ mục đích.

Lưu ý rằng một điều tương tự áp dụng với mã hóa: khi mọi người mã hóa các tệp bằng mật khẩu, có thể xây dựng bảng Rainbow để bẻ khóa các tệp. Giả sử phần mềm sử dụng AES và khối đầu tiên của tệp sẽ giải mã thành "mật khẩu không chính xác" bằng mật khẩu do người dùng cung cấp, sau đó bảng Rainbow sẽ sử dụng AES thay vì hàm băm.

Bất cứ khi nào bạn xử lý mật khẩu (một bí mật không rõ ràng và đặc biệt là nếu người dùng có thể sử dụng lại nó), hãy luôn chạy nó thông qua thuật toán lưu trữ mật khẩu (chậm) thích hợp để làm cho nó chậm và duy nhất để bẻ khóa.

7
Luc