3.1K 232 111

Đã đăng vào thg 2 25, 6:37 SA 3 phút đọc

124

Tấn công hàm băm (hash attack) - Tấn công xung đột băm (hash collision attack)

I. Hash attack

Về việc đưa ra một thuật toán băm "ngược" $H^{-1}$ nhằm tìm ra chính xác thông điệp $x$ từ $y=H(x)$ là không thể. Nguyên lý của hàm băm chính là đưa các thông điệp với độ dài tùy ý trở về "khuôn khổ" một chuỗi có cấu tạo và độ dài cố định, tức kết quả băm nằm trong một không gian có độ lớn giới hạn. Chúng ta không thể dựa vào một không gian giới hạn tìm ngược lại thông điệp - thuộc một không gian vô hạn. Nếu thực sự có thể làm được, thì đó chắc hẳn là một thuật toán nén dữ liệu tuyệt vời nhất, do mọi thông điệp có độ dài tùy ý đều có thể "nén" về chuỗi có độ dài cố định, mà còn có thể giải nén trở lại!

Việc tấn công hàm băm không có nghĩa là đi tìm một thuật toán băm ngược, mà chúng ta đang xem xét tới vấn đề làm sao từ $y$ có thể tìm ra $x$ . Ở đây tôi sẽ trình bày một số dạng tấn công cơ bản.

1. Brute force attack

Rõ ràng, phương pháp vét cạn là ý tưởng có thể nghĩ tới và đơn giản nhất, mặc dù nó yêu cầu một khối lượng tính toán khổng lồ. Chẳng hạn, chúng ta cần tìm ra bản rõ của một mật khẩu dài $n$ ký tự, cấu tạo bởi các chữ cái in hoa, in thường và chữ số, thì số lượng chuỗi có thể tạo thành là:

$(26 + 26 + 10) ^ n = 62^n$

Khi cho băm lần lượt tất cả trường hợp trên, sẽ chắc chắn tìm ra được mật khẩu gốc. Điều này yêu cầu một khối lượng tính toán lớn và dẫn đến hao tốn về thời gian. Chương trình Python3 sau ví dụ cho hash MD5:

import hashlib
import itertools

def md5_hash(input_string):
    md5 = hashlib.md5()
    md5.update(input_string.encode())
    return md5.hexdigest()

def crack_md5_hash(target_hash, charset, max_length):
    for length in range(1, max_length + 1):
        for candidate in itertools.product(charset, repeat=length):
            candidate_password = ''.join(candidate)
            candidate_hash = md5_hash(candidate_password)
            if candidate_hash == target_hash:
                return candidate_password
    return None

# Ví dụ: Crack một hash MD5 cụ thể
# Đây là hash MD5 của mật khẩu "123456"
target_md5_hash = "e10adc3949ba59abbe56e057f20f883e"
character_set = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
max_password_length = 6

cracked_password = crack_md5_hash(target_md5_hash, character_set, max_password_length)

if cracked_password:
    print(f"Cracked password: {cracked_password}")
else:
    print("Password not cracked.")

Trong thực tế, vét cạn không phải là phương pháp hiệu quả để crack mật khẩu, đặc biệt là khi mật khẩu có độ dài lớn và sử dụng các ký tự đặc biệt.

2. Tấn công vét cạn theo từ điển

Phương pháp tấn công sẽ chịu "tổn thất" về không gian lưu trữ để đổi lại giảm về thời gian tính toán. Tức là sẽ lưu bản rõ và kết quả hash tương ứng của nó ánh xạ trong một không gian lưu trữ, sau đó chỉ cần tìm kiếm hash cần crack có tồn tại trong không gian đó hay không. Không gian từ điển hash cần tạo sẽ là các mật khẩu "có nghĩa", mật khẩu yếu, mật khẩu thường xuyên sử dụng.

Thực tế phương thức tấn công này ban đầu vẫn cần tính toán vét cạn một lần các khả năng mật khẩu xảy ra, nhưng sẽ lưu trữ lại kết quả để giảm lượng tính toán về sau. Đây cũng chính là nguyên lý hoạt động ở các nền tảng crack hash online hay sử dụng.

3. Bảng cầu vồng - Rainbow table

Hai phương thức tấn công trên đều có nhược điểm của riêng mình là không gian lưu trữ và thời gian thực thi. Phương pháp rainbow table thực hiện kết hợp hài hòa hai phương pháp trước, đưa thời gian tính toán và không gian lưu trữ về dạng cân bằng hơn.

Cụ thể, xây dựng một thuật toán $R()$ sao cho giá trị input của $R$ lấy từ không gian giá trị output của $H$ , giá trị output của $R$ nằm trong không gian giá trị input của $H$ . Sau đó, với thông điệp $x_0$ , tạo chuỗi bằng cách sử dụng $H$ và $R$ đan xen:

$x_0\rightarrow y_0=H(x_0)\rightarrow x_1 = R(y_0)\rightarrow y_1=H(x_1)\rightarrow ... \rightarrow x_{n-1}=R(y_{n-2})\rightarrow y_{n-1}=H(x_{n-1})\rightarrow x_n=R(y_{n-1})\ (*)$

Chỉ cần lưu trữ cặp giá trị $(x_0,x_n)$ . Thực hiện tính toán như trên với các $x_0$ khác, thu được nhiều cặp giá trị $(x_0,x_n)$ lưu vào bảng.

Khi cần tìm bản rõ của chuỗi hash $y$ , chúng ta tính $z=R(y)$ , và tìm trong bảng các cặp giá trị thỏa mãn $x_n=z$ , lúc này $x_{n-1}$ có khả năng là bản rõ cần tìm. Để xác nhận, chúng ta tính lại các chuỗi (*) với các $x_0$ , sau khi tính tới $x_{n-1}$ tính tiếp bước $y_{n-1}=H(x_{n-1})$ , nếu bằng $y$ thì $x_{n-1}$ chính là kết quả cần tìm.

Khi giá trị $n$ càng lớn, tức độ dài chuỗi (*) càng lớn, tỉ lệ tìm kiếm thành công "đuôi" của các chuỗi trùng với $z=R(y)$ sẽ càng cao. Việc lưu trữ cặp giá trị "đầu - cuối" của chuỗi (*) thay cho cả chuỗi đã làm giảm đáng kể không gian lưu trữ, khi tìm thấy các cặp thỏa mãn sẽ chỉ cần tính lại chuỗi để tìm ra thông điệp gốc, thời gian tính toán cũng không quá lớn. Phương pháp rainbow table đã kết hợp hài hòa giữa không gian và thời gian, sử dụng không gian đổi lấy thời gian, sử dụng thời gian đổi lấy không gian - Space and Time Tradeoffs.

II. Hash collision attack

1. Hash collision

Nhắc lại khái niệm về xung đột băm ở bài trước: xét hàm băm $H()$ , khi tồn tại $x\ne y$ sao cho $H(x)=H(y)$ thì ta nói đây là hiện tượng xung đột băm (hash collision).

Trên lý thuyết thì xung đột băm luôn tồn tại với mỗi thuật toán hash, các hàm băm hiện tại đều đang đảm bảo xác suất xảy ra xung đột ở mức thấp nhất, chứ không thể giảm xuống $0$ . Thật vậy, giả sử hàm hash $H()$ có đầu ra là một chuỗi nhị phân $256$ bit, thì không gian giá trị có độ lớn $2^{256}$ , khi đưa $2^{256}+1$ thông điệp đầu vào khác nhau thực hiện băm, thì chắc chắn tồn tại hai thông điệp trả về cùng một kết quả (Theo nguyên lý Dirichlet).

2. MD5 hash collision

Hiện nay, MD5 là thuật toán băm được sử dụng rộng rãi. Tuy nhiên, với sự tiến bộ vượt bậc của khả năng tính toán và nỗ lực không ngừng của các nhà nghiên cứu, MD5 đã sớm không "giữ" được tính an toàn của nó, đã có nhiều ý tưởng thực hiện tạo ra hash collision trong MD5.

Vào năm $2005$ , Xiaoyun Wang và Hongbo Yu tới từ Shandong University, China đã đưa ra phương thức tấn công hash collision MD5. Bằng cách tìm ra khoảng $290$ điều kiện cần thỏa mãn dẫn tới tăng xác suất đụng độ trong MD5, khi input thỏa mãn số lượng điều kiện càng lớn, tỷ lệ xảy ra đụng độ sẽ càng cao. Kết quả cuối cùng đạt được là chỉ cần kiểm tra $2^{37}$ input khác nhau sẽ hoàn toàn có thể tìm ra hash collision trong MD5. Mặc dù input dẫn tới sự đụng độ này là sinh ngẫu nhiên, nhưng phương pháp đã giúp mỗi người bất kỳ chỉ cần sở hữu một máy tính cá nhân đã có thể tính toán để tìm ra một cặp input dẫn tới hash collision trong MD5. Bạn đọc có thể tìm hiểu thêm phương pháp tấn công và các điều kiện cần thỏa mãn tại https://www.iacr.org/archive/eurocrypt2005/34940019/34940019.pdf.

Ví dụ, cặp chuỗi sau có cùng một giá trị MD5 hash 008ee33a9d58b51cfeb425b0959121c9

4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2

Bạn đọc có thể thử sức với các challenge CTF chủ đề COLLISIONS tại https://cryptohack.org/challenges/hashes/ để hiểu thêm về MD5 hash collision:

Tài liệu tham khảo