Hash function (Training WCO2)

Phần tiếp theo trong khóa training này chính là hash function (hàm băm). Bài viết này nhằm để giúp các bạn có cái nhìn tổng quan nhất vể hàm băm trong crypto.

Định nghĩa

• Hàm băm là một hàm trong toán học dùng để chuyển đổi dữ liệu đầu vào thành một chuỗi cố định, được gọi là giá trị băm. Đây là hàm một chiều, tức là không tồn tại một hàm giúp tìm được x khi biết giá trị của
  $f(x)$.
• Hàm băm có ứng dụng rất nhiều trong thực tế (chữ kí số, lưu trữ mật khẩu, xác thực thông tin, …) nhờ vào sự thuận tiện về mặt tính toán cũng như chi phí thấp.

Tính chất

• Một hàm băm an toàn sẽ có những tính chất sau:
  • Đầu ra cố định: Kích thước của giá trị băm không thay đổi dựa trên kích thước của dữ liệu đầu vào.
  • Định mức: Cùng một dữ liệu đầu vào sẽ luôn tạo ra cùng một giá trị băm (*)
  • Nhạy cảm với sự thay đổi: Thậm chí một sự thay đổi nhỏ trong dữ liệu đầu vào cũng sẽ tạo ra một giá trị băm hoàn toàn khác.
  • Chống đảo ngược: Rất khó (thậm chí không thể) tìm lại dữ liệu gốc từ giá trị băm.
• Ví dụ về cách sử dụng hàm băm trong python:

import hashlib

data = b"em yeu crypto"
hashed_data = hashlib.sha256(data).hexdigest()

print(f"Original data: {data}")
print(f"Hashed data: {hashed_data}")

Collision

• Về bản chất, hàm băm cũng chỉ là một ánh xạ
  $f:X\to Y$, với X là tập vô hạn (đầu vào là dữ liệu bất kì), Y là tập hữu hạn (do hàm băm cho đầu ra có kích thước cố định). Do đó chắc chắn sẽ tồn tại 2 phần tử x1,x2 thuộc X sao cho
  $f(x1)=f(x2)$ (tức 2 dữ liệu khác nhau cho giá trị băm giống nhau). Vấn đề này được gọi là đụng độ trong hàm băm, hay còn gọi là hash collision.
• Một hàm băm được xem là an toàn khi nó có thể chống lại các cuộc tấn công sau:
  • Pre-image attacks: Khi biết được hash(m) thì ta không thể tìm được m.
  • Second pre-image resistance: Cho một message m1, ta không thể tìm được m2 khác m1 sao cho hash(m1) = hash(m2)
  • Collision resistance: ta không thể tìm 2 giá trị m1 và m2 (m1 khác m2) sao cho hash(m1) = hash(m2)
• 1 số thuật toán hash phổ biến có thể kể đến là:
  • MD5 (cái này đã bị loại do khả năng chống collision yếu)
  • SHA-1 (same as MD5)
  • SHA-2
  • SHA-3
  • SHAKE
  • …
• Trong bài viết này, mình sẽ giới thiệu về một vài phương pháp tấn công thường thấy:
  • Birthday attack
  • Length extension attack
  • Rainbow table attack
  • Preimage attack
  • Collision attack

Attack models

Birthday attack

• Kĩ thuật tấn công này xuất phát từ 1 nghịch lý về ngày sinh nhật: Xác suất để tồn tại 2 người trùng ngày sinh nhật trong nhóm 23 người là 50%, và với 70 người sẽ lên tới 99,9%.
• Có 1 công thức để tính ra xác suất xảy ra collision trong 1 nhóm, nhưng để dễ hình dung thì đây là 1 con số cụ thể mình hay sử dụng: xét 1 nhóm có
  $N$ giá trị hash khác nhau, số lượng phần tử tối thiểu sao xác xuất để tồn tại collision trong nhóm đó là 50% là
  $\sqrt{N}$. Đây chính là ý tưởng để xây dựng birthday attack tìm collision:
  • B1: Chọn tập
    $\sqrt{N}$ phần tử ngẫu nhiên
  • B2: Kiểm tra xem trong tập đó có tồn tại 2 phần tử trùng hash hay không
  • B3: Nếu tồn tại collision (2 phần tử trùng hash), output và kết thúc thuật toán, ngược lại quay lại B1
• Chi tiết về kiểu tấn công này các bạn có thể xem tại đây: https://viblo.asia/p/nghich-ly-birthday-paradox-4P856RjG5Y3

Length extension attack

• Đây là một loại attack dùng để tấn công vào các loại mã MAC (message authentication code) có công thức MAC = hash(secret||message) (|| là phép nối chuỗi). Các hàm hash bị tấn công bởi cách thức này là những hàm được xây dựng dựa trên Merkle–Damgård construction, bao gồm MD5, SHA1, SHA2.
  
• Có thể thấy, chuỗi message + padding sẽ được chia thành các block có độ dài bằng nhau. Giả sử ta biết được một mã MAC được tạo ra bởi công thức hash(secret||message) (secret chưa biết), khi đó bằng phương pháp length extension attack, ta có thể tính được mã MAC mới hash(secret||message||padding||malicious_data) mà không cần biết giá trị của secret.
• Chi tiết cách tấn công các bạn có thể tham khảo link sau: https://manhhomienbienthuy.github.io/2015/09/30/hash-length-extension-attacks.html
  Ngoài ra, các bạn có thể xem 2 video này để hiểu rõ hơn và xem cách bug này được exploit thực tế: link1 vs link2 (nên xem hết nhé :v)
• Về tool thì mình hay dùng tool này (được viết bởi anh vnc trong clb, uy tín nhé :)

Dictionary attack

• Như có nhắc ở trên, một trong những ứng dụng của hàm hash là lưu trữ mật khẩu. Khi lưu mật khẩu trên database, bao giờ server cũng sẽ lưu giá trị hash của chúng (vì database là một nơi rất dễ bị tấn công, nếu ta không hash thì nhỡ khi database bị tấn công thì sẽ lộ hết tài khoản người dùng). Đó là lý do mà lúc ta nhấn quên mật khẩu thì server yêu cầu set mật khẩu mới chứ không đưa lại mật khẩu cũ.

• Tuy nhiên, nếu ta đặt mật khẩu yếu (kiểu như những cụm từ dễ đoán như ngày sinh, tên ny,"helloword" …) thì vẫn bị lộ như thường dù server vẫn lưu hash trên database. Khi đó attacker sẽ tấn công bằng một phương pháp gọi là dictionary attack. Cụ thể, sẽ có một "dictionary" gồm các mật khẩu thường dùng thường được sử dụng và giá trị hash tương ứng. Nhiệm vụ của attacker chỉ là chạy hết dictionary đó và tìm mật khẩu ứng với giá trị băm ban đầu. Trên mạng cũng có khá nhiều tool hỗ trợ cách tấn công này như

  • https://hashes.com/en/decrypt/hash
  • https://crackstation.net/
  • …
    

• Vì vậy để chống lại kiểu này chỉ còn cách là đặt password mạnh lên nhé ^_~ (try this game)

Preimage attack, Collision attack

• Đối với các hàm hash yếu như MD5, SHA1, việc tìm collision không hề khó. Các bạn có thể dùng tool hashclash để tạo collision.
• Đối với các hàm hash an toàn hơn như SHA2, SHA3, … thì việc tấn công này được xem như bất khả thi. Tuy nhiên đôi khi trong các bài CTF, người ra để sẽ tự tạo ra các hàm hash của chính họ, sau đó bắt chúng ta tìm collision hay gì đó. Cách tấn công là chúng ta phải phân tích và khai thác trực tiếp lỗi trong hàm hash đó.

Bài tập:

Các bạn làm và viết chi tiết write-up cho mình các bài sau (deadline là 7 ngày từ ngày release nhé):

• Bắt buộc:
  • jack's birthday hash (Cryptohack)
  • jack's birthday confusion
  • collider
  • hash stuffing
  • md0
  • primemd5
  • Secure signing - HTB
• Không bắt buộc:
  • https://hackropole.fr/en/challenges/crypto/fcsc2023-crypto-le-hash-qui-rit/
  • https://hackropole.fr/en/challenges/crypto/fcsc2021-crypto-hashy-parmentier/
  • https://app.hackthebox.com/challenges?keyword=protein cookie&sort_type=asc