Monday, June 13, 2011

Cách tính số tổ hợp mật khẩu cần phải so khớp khi Brute Force password

Công thức:

(số kí tự bảng chữ cái) ^ (chiều dài mật khẩu)

Đây là một kiến thức cơ bản bắt nguồn từ một kiến thức toán học rất cơ bản: "Hoán vị và Tổ hợp"

Tôi sẽ không giải thích lý thuyết toán học dài dòng của công thức tổ hợp rất cơ bản mà ta sẽ dùng để xác định số tổ hợp có thể có của của một mật khẩu bất kỳ. Đây là bài toán rất cơ bản mà một hacker cần phải thực hiện khi anh ta có ý định "Brute Force" một chuỗi mật khẩu bất kỳ. Anh ta cần phải biết là anh ta sẽ phải so khớp bao nhiêu mật khẩu, rồi tiếp theo đó anh ta đo đạc xem máy tính của anh ta ( hoặc hệ thống máy tính của anh ta ) có khả năng so khớp bao nhiêu mật khẩu một giây, rồi cuối cùng tính ra thời gian anh ta cần có để so khớp tất cả mật khẩu có thể có đã đề cập ở trên.


Ta lấy ví dụ với một mật khẩu có độ dài 5 kí tự như sau: a3G5h

Bây giờ ta coi như password trên kia là "bí ẩn" tức ta không biết nội dung password, nhưng ta biết dc password này dài 5 kí tự.

Nhận định đầu tiên là mật khẩu trên ta thấy gồm có kí tự latin viết thường, chữ số ả-rập, và kí tự latin viết hoa. Khi crack password cũng vậy, ta cần dự trù xem người chủ của password đó, sử dụng những kí tự gì để tạo password. Số kí tự tối đa mà một người có thể dùng để tạo password của anh ta, hiện nay có thể lên tới 250 kí tự, do các mật khẩu đa phần được tạo từ các kí tự gõ được trong bảng mã ASCII. Thế nhưng may mắn là người dùng thường chỉ sử dụng các kí tự thông dụng trên bàn phím, do đó độ lớn của bảng kí tự giảm đi nhiều, chuỗi kí tự thường dùng để tạo pass là :


abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789

Vậy bảng kí tự trên có tất cả 62 kí tự

Bây giờ tới phần so khớp password, ta sẽ làm như trong mấy phim Mỹ ngày xưa, bọn trộm ngồi mò mật khẩu mấy cái két sắt ấy :))

Ta cứ tưởng tượng password 5 kí tự trên là 5 cái ô trống

  OOOOO
  1 2 3 4 5

Để crack password, bạn phải thế từng kí tự trong bảng kí tự trên vào 5 ô trống một cách lần lượt, như sau.

Lượt 1: Kí tự đầu ta lấy kí tự a thế vô ô 1, xong lại lấy kí tự a thế vô ô 2,xong lại lấy kí tự a thế vô ô 3,xong lại lấy kí tự a thế vô ô 4,xong lại lấy kí tự a thế vô ô 5. Ta được tổ hợp đầu tiên là aaaaa

Lượt 2: Đổi ô đầu thành kí tự b, giữ nguyên các ô còn lại, ta sẽ có tổ hợp thứ 2 là baaaa

Cứ thế, ta thay thế bảng kí tự trên vào một cách lần lượt.

Vậy giờ câu hỏi bật ra. Ta cần làm như trên tất cả bao nhiêu lượt, tức là ta sẽ tạo ra bao nhiêu tổ hợp mật khẩu từ bảng kí tự dài 62 kí tự ở trên ? Từ đó tính ra số mật khẩu ta phải so khớp.

Ta sẽ dùng công thức ở đầu bài 

(số kí tự bảng chữ cái) ^ (chiều dài mật khẩu)


Ta đã có bảng chữ cái có 62 kí tự, và mật khẩu có chiều dài 5 kí tự.

Vậy ta có tất cả: 62^5 = 916.132.832 ( Chín trăm mười sáu triệu, một trăm ba mươi hai ngàn, tám trăm ba mươi hai ) tổ hợp

Quá xá nhiều, nếu không muốn nói là nhiều khủng khiếp :)) , người bình thường mà ngồi viết mớ mật khẩu trên chắc sẽ tới già :D

Do đó ta sẽ dùng đến máy tính, tôi sẽ không nói sâu về thuật toán dùng để crack password, vì nó cũng dựa trên cách đã trình bày ở trên mà thôi.

Máy tính Core 2 Duo hiện nay thực hiện được 850 phép so khớp 1 giây tức nó cần 299 giờ hay khoảng 12 ngày chạy liên tục để crack chuỗi password có độ dài 5 kí tự ở trên.

Còn với siêu máy tính Titan mới nhất của Hoa Kỳ tức máy tính nhanh nhất cho đến thời điểm này ( vượt qua cái của nợ rởm của tàu khựa lâu rồi ) tính được 20.000 tỷ ( 20.000 trillion - dịch theo nghĩa mỹ ) một giây. Thì  password trên chỉ mất chưa đến một giây để crack

Dĩ nhiên tôi cần lưu ý rằng, số tổ hợp trên là tổng số tổ hợp có thể phải tra, chớ không phải số tổ hợp cần phải tra, do điều này còn phụ thuộc vào nội dung password, ví dụ nếu password là tổ hợp đầu tiên aaaaa ,thì rất có thể chỉ cần một giây để crack password trên ( tùy vào thuật toán tạo tổ hợp để crack pass )

Thế nên, mấy bạn nào muốn liều con CPU để chơi trò brute force kiểu vét cạn như trên thì nên tính toán trước khi thử, chứ yếu mà ra gió thì có khi trúng gió :D

xnohat

5 comments:

  1. Nếu được anh NoHat chịu khó viết thêm bằng Java để anh em "thưởng thức" nhé. Không biết ý tưởng này tích hợp vào virus hay cho một trình duyệt xử lý được không anh? Thanks anh!

    Again: Bài viết quá hay!

    ReplyDelete
  2. Chuyện này anh đã thử lâu rồi em, khá hiệu quả khi bruteforce bằng "điện toán phân tán"

    Tham khảo cái này:
    http://blog.andlabs.org/
    http://www.andlabs.org/tools/ravan.html

    Chú ý dùng trình duyệt Firefox 4 hay Chrome 12 trở lên mới coi được. Anh thì làm vụ này từ thời các javascript engine còn cũ kĩ kìa, nhưng nghiên cứu chơi chứ chả để làm gì :D

    ReplyDelete
  3. có chương trình nào tổ hợp với list pass ko a

    ReplyDelete

Quí đọc giả đọc xong, nếu thấy chút thú vị thì tác giả cũng mong được chút comment lấy làm kích lệ