it-swarm-vi.com

Mất bao lâu để thực sự tạo ra các bảng Rainbow?

Tôi đã đọc về các bảng Rainbow vì tôi nghĩ chúng khá thú vị vì chúng thực sự là một khái niệm khá đơn giản.

Dù sao, tôi đã tự hỏi, có ai đã tham gia vào việc thực sự tạo ra một? Làm thế nào nó có thể được thực hiện? Tôi chỉ không thấy làm thế nào thực sự có thể tạo ra mọi sự kết hợp của mọi nhân vật.

Nếu chúng tôi loại trừ các ký tự đặc biệt, có những lượng ký tự này.

ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz 1234567890

Nghe có vẻ như có 26 + 26 + 10 = 62 ký tự

Điều đó có nghĩa là mật khẩu có độ dài 8 có 62 ^ 8 kết hợp.

tương đương với 218340105584896

Điều đó một mình nghe có vẻ như sẽ mất nhiều thời gian để tạo ra. Thế còn khi chúng ta tăng số lượng ký tự lên 12 và thêm vào các ký tự đặc biệt (giả sử có 10 nhân vật khác chỉ bằng cách nhìn vào các ký tự mà bạn nhận được bằng cách nhấn shift - number) thì sao?

Chúng tôi sẽ nhận được 72 ^ 12 = 19408409961765342806016

đó là một con số đủ lớn để mất nhiều năm để có được.

27
stickman

Bảng Rainbow là "chỉ" một biểu diễn nhỏ gọn của bảng các giá trị băm được tính toán trước. Trong quá trình xây dựng bảng Rainbow, nhiều đầu vào có thể được thử và băm. Mỗi đầu vào gặp phải trong quá trình xây dựng bảng sẽ bị tấn công thành công với bảng đó và không có mục nào khác. Đánh giá băm tập trung hầu hết các chi phí xây dựng bảng.

Vì vậy, về cơ bản, chi phí xây dựng bảng Rainbow có thể đảo ngược mật khẩu [~ # ~] n [~ # ~] tương đương với chi phí về việc thử các mật khẩu [~ # ~] n [~ # ~] thông qua hàm băm - điểm của bảng Rainbow là bạn xây dựng nó một lần và sau đó có thể sử dụng nó để phá một số mật khẩu . (Nói chính xác, do va chạm chuỗi trong quá trình xây dựng bảng, chi phí thực tế gần với 1.7 * N , nhưng hãy bỏ qua điều đó vào lúc này. )

Tôi đã từng thực hiện một số kinh nghiệm với SHA-1. Băm mật khẩu đơn giản với SHA-1 có chi phí xử lý một "khối" duy nhất (SHA-1, như MD5, xử lý dữ liệu theo các khối 64 byte), cần khoảng 900 hoạt động logic hoặc số học 32 bit. Việc triển khai tối ưu hóa trên bộ xử lý Intel Core2 x86 có thể thực hiện điều đó trong khoảng 500 chu kỳ xung nhịp. Tuy nhiên, các cuộc tấn công bằng mật khẩu (dù trực tiếp hay để xây dựng bảng Rainbow, không thành vấn đề) là một công việc song song cao, do đó, người ta có thể sử dụng các hướng dẫn SSE2 cung cấp các thanh ghi 128 bit và trong đó một opcode có thể thực hiện bốn hoạt động 32 bit đồng thời. SSE2 có ít loại hoạt động khả dụng hơn (đặc biệt, nó không cung cấp các phép quay, chỉ thay đổi), do đó, số lượng hoạt động tăng lên khoảng 1200; nhưng, trong một số điều kiện, đơn vị SSE2 sẽ thực thi đồng thời một số opcodes. Vì vậy, chúng tôi kết thúc với 800 chu kỳ đồng hồ, cho bốn trường hợp SHA-1 song song. Điểm mấu chốt: PC của tôi là Intel Core2 Q6600, với bốn lõi chạy ở tốc độ 2,4 GHz. Mỗi lõi có thể chạy triển khai SSE2 của tôi, dẫn đến khoảng 48 triệu mật khẩu được băm mỗi giây.

Tôi cũng có một card đồ họa Nvidia không quá nhỏ và GPU có thể chạy mã tùy ý thông qua CUDA . Đây là 9800 GTX +, với 128 lõi chạy ở tốc độ 1,84 GHz. Mỗi lõi có thể thực hiện một hoạt động 32 bit cho mỗi chu kỳ (có độ trễ cao, nhưng nhờ có độ song song cao, thông lượng một hướng dẫn trên mỗi chu kỳ này có thể được duy trì). Các lõi không biết về phép quay, vì vậy mỗi mã sẽ sử dụng 1200 chu kỳ xung nhịp cho mỗi mật khẩu được băm. Tổng hiệu suất là 160 triệu mật khẩu băm mỗi giây.

PC và card đồ họa của tôi có từ đầu năm 2009 và không phải là hàng đầu. Ngày nay người ta có thể tìm thấy, với vài trăm đô la, một GPU sẽ băm mật khẩu nhanh hơn khoảng ba lần so với 9800 GTX + của tôi. Vì vậy, hãy giả sử rằng một kẻ tấn công với một PC thông thường (có giá dưới 1000 đô la) có thể băm nửa tỷ mật khẩu mỗi giây.

Với tốc độ đó, tất cả mật khẩu có 8 ký tự chữ và số (chữ hoa và chữ thường và chữ số) được thực hiện trong khoảng 5 ngày . Với một PC $ 1000. Nếu bạn sử dụng MD5, mọi thứ sẽ nhanh hơn khoảng 30% (MD5 sử dụng ít thao tác hơn SHA-1). Các lược đồ băm mật khẩu tốt không sử dụng một cách gọi hàm băm đơn giản, mặc dù: chúng sử dụng hàm băm lặp với 2000 lời gọi hàm băm lồng nhau: điều này nhân chi phí cho kẻ tấn công bằng cùng một yếu tố 2000 (vì vậy nó biến "5 ngày" thành khoảng 28 năm, nghĩa đen là "lứa tuổi" như bạn đặt nó).

30
Thomas Pornin

Mất bao lâu để tạo một bảng Rainbow cho một hàm băm rất đơn giản, chỉ sử dụng một lần lặp duy nhất? Mất một giờ! Hoặc ít hơn, nếu bạn muốn.

Mặc dù các câu trả lời ở trên là hoàn toàn chính xác, có một sự phát triển quan trọng mà họ không đề cập đến. Amazon EC2 và các nhà cung cấp máy chủ 'điện toán đám mây' khác.

Ngày nay, tất cả mọi người có thẻ tín dụng đều có thể truy cập aws <azon.com và tìm kiếm một số ít các trường hợp tại chỗ EC2 , với ít hơn một trăm đô la. Hoặc nếu bạn có sẵn mã CUDA tốt, hãy thuê 50 phiên bản "Cluster Cluster" đắt tiền hơn của Amazon với hai bộ xử lý đồ họa NVIDIA Tesla M2050.

. . Nếu bạn sẵn sàng mua cùng một ví dụ như giấy phép cung cấp vượt mức trong giờ nghỉ, thì bạn có thể lấy nó với mức hoàn tiền 40% -50% .)

Tạo các bảng Rainbow có thể được thực hiện song song với hiệu suất tăng tuyến tính, tức là với 100 máy tính hoạt động, nó nhanh hơn 100 lần so với một máy tính.

Amazon không tính phí cho bạn mỗi phiên bản, nó tính phí mỗi giờ. Do đó, việc chạy 1.000 máy chủ cho một giờ có cùng chi phí như một máy chủ trong 1.000 giờ.

Bản chất song song của việc tạo bảng Rainbow, được thực hiện cùng với các dịch vụ như Amazon EC2, có nghĩa là không còn câu hỏi "mất bao lâu nữa". Có một "bạn sẵn sàng trả bao nhiêu để có được nó nhanh, so với trả ít hơn và nhận được trong vài ngày?". Sự khác biệt về chi phí & thời gian chủ yếu đến từ sự khác biệt về giá của Amazon giữa 'phiên bản EC2 thông thường so với' trường hợp giao ngay 'rẻ hơn.

18
Jesper M

Sử dụng một lần chạy thử 26 ^ 5 đơn giản, tôi có thể tạo một bảng ascii hex trong Ruby tạo ra 228488 đầu ra MD5 mỗi giây. Tất cả 11881376 mục nhập mất 52 giây trên Core i7 1,5 năm tuổi của tôi. Nếu tôi không thực hiện bất kỳ cải tiến nào cho chương trình của mình, tôi hy vọng nó sẽ chạy trong 26 tuần để tạo danh sách 62 ^ 8 của bạn.

Tôi có thể có thể cải thiện chương trình của mình bằng cách chạy tám chương trình riêng biệt, mỗi chương trình cho một siêu phân luồng, để phân vùng không gian vấn đề. Nếu mỗi chương trình lưu đầu ra vào ổ đĩa của riêng nó, chúng sẽ không cạnh tranh cho IO băng thông. Tôi sẽ mong đợi hệ số tăng tốc từ bốn đến sáu so với chương trình đơn luồng ngu ngốc của tôi cho 4 - 6 tuần chạy. Nếu tôi viết lại bằng C, tôi có thể mong đợi một yếu tố tăng tốc 1,5 khác. (Có thể nhiều hơn? Một mặt, đó là một chương trình đơn giản, mặt khác, một mảng C dài 13 byte, được sửa đổi khi chạy, có lẽ sẽ chạy trong bộ nhớ ít hơn nhiều và tất nhiên không có bộ sưu tập rác so với việc tạo và hủy các đối tượng chuỗi Ruby.)

Tôi mong đợi một buổi chiều làm việc và một vài trăm đô la thiết bị mới sẽ cho phép tôi hoàn thành 62 ^ 8 bảng hai tuần trên phần cứng hàng hóa.

Và chắc chắn, không ai sử dụng MD5 chạy đơn trên mật khẩu; chỉ cần chia tỷ lệ kết quả cuối cùng của tôi bằng cách băm một chiều đắt hơn nhiều so với MD5. :)

6
sarnold

Xem các tính toán tỷ lệ băm mạng khai thác bitcoin của tôi tại Làm thế nào để băm mật khẩu an toàn? - Bảo mật CNTT để biết những người xác định với thẻ GPU hiện đại hơn có thể thực hiện về mặt băm thô. Cộng đồng đang hoạt động ở mức 11 Thash/s (11 * 10 ^ 12 hash/s) vào đầu tháng 7 năm 2011 ....

1
nealmcb