CHƯƠNG 1: CƠ SỞ LÝ THUYẾT VỀ HÀM BĂM MẬT MÃ VÀ CHỮ KÝ SỐ 1. Định nghĩa hàm băm Các hàm băm đóng vai trò cơ bản trong mật mã hiện đại. Hàm băm H là một hàm toán học chuyển đổi các xâu bit có độ dài hữu hạn tùy ý thành các xâu bit có độ dài n cố định. Đầu ra này được gọi là mã băm (hay kết quả băm, giá trị băm, vết hay tóm lược thông báo).
Có nhiều định nghĩa khác nhau về hàm băm. Tuy nhiên tất cả các định nghĩa đều chỉ ra cùng một dạng hàm giống nhau. Dưới đây là một số định nghĩa về hàm băm [13].1, [13]): Hàm băm là một hàm có dạng: 𝐻 ∶ Σ∗ → Σ𝑛 Trong đó: H là một hàm toán học ánh xạ xâu nhị phân có độ dài bất kỳ vào xâu có độ dài cố định. Đầu vào của H gọi là thông điệp và đầu ra gọi là giá trị băm của thông điệp.
Định nghĩa trên là mô tả chung cho một hàm băm, nhưng không đưa ra những yêu cầu để hàm băm là an toàn trong mật mã hay nói cách khác là những yêu cầu để hàm băm để trở thành hàm băm mật mã. Có 6 yêu cầu không chính thức cho một hàm băm để trở thành hàm băm mật mã [13, 10]. Tính kháng tiền ảnh – Với tất cả các đầu ra cho trước, không thể tính toán để tím được đầu vào bất kỳ mà khi băm cho ra đầu ra đó, tức là cho trước một giá trị băm y bất kỳ, không thể tìm ra được một tiền ảnh 𝑥 ′ thỏa mãn ℎ(𝑥 ′ ) = 𝑦. Tính kháng tiền ảnh thứ 2 – Không thể tính toán để tìm được đầu vào thứ hai bất kỳ mà có cùng đầu ra với đầu vào cho trước, tức là cho trước x không thể tìm được tiền ảnh thứ hai 𝑥′ ≠ 𝑥 thỏa mãn ℎ(𝑥 ′ ) = ℎ(𝑥).
Tính kháng va chạm – Không thể tính toán để tìm được hai đầu vào khác nhau x và x' bất kỳ mà có cùng đầu ra, tức là thỏa mãn ℎ (𝑥 ′ ) = ℎ(𝑥). Tính không tương quan – Các bit đầu vào và đầu ra không tương quan với nhau. Tính khánh va chạm gần – Khó tìm ra được hai đầu vào x, x' thỏa mãn ℎ(𝑥 ) và ℎ(𝑥 ′ ) chỉ khác nhau một số lượng nhỏ bit. Tính kháng tiền ảnh từng phần – Khó có thể tìm ra xâu con bất kỳ của x cũng như tìm toàn bộ đầu vào của x, khi cho trước ℎ (𝑥 ′ ).
Ngoài ra, biết trước một phần đầu vào thì khó có thể tìm phần còn lại (ví dụ: nếu còn lại t bit đầu vào chưa biết, thì trung bình cần thực hiện 2𝑡−1 phép tính giá trị băm để tìm những bit còn lại). Ngoài ra, trong ứng dụng thực tế, hàm băm mật mã phải thỏa mãn yêu cầu dễ tính toán và tốc độ nhanh. Để các định nghĩa không chính thức về kháng tiền ảnh, kháng tiền ảnh thứ hai và kháng va chạm trở thành chính thức thì trước tiên chúng ta phải định nghĩa được họ hàm băm. Với một hàm băm cụ thể thì người ta có thể xây dựng được thuật toán tính va chạm trong thời gian đa thức.
Tuy nhiên, việc định nghĩa một họ hàm là họ vô hạn của các tập hữu hạn các hàm băm giúp ngăn cản thuật toán như vậy thực hiện thành công đối với tất cả các hàm băm trong họ vì tồn tại nhiều vô hạn. Cho 𝐷 = ∑𝑙 là miền xác định và 𝑅 = ∑𝑛 là miền giá trị của hàm. Cho 𝒦 là tập hợp tất cả các khóa có thể (về mặt lý thuyết tập này là vô hạn nhưng trong thực tế nó là hữu hạn). Do đó, với một họ hàm băm H, thì mỗi hàm băm có dạng 𝐻: 𝒦 × 𝐷 → 𝑅 hay 𝐻𝒦 : 𝐷 → 𝑅.1, [13]): Một họ hàm băm h là một tập hợp vô hạn các hàm băm trong đó mỗi hàm trong họ được gắn chỉ số bởi một khóa K, và mỗi hàm băm có dạng: 𝐻𝐾 : ∑𝑙 → ∑𝑛 Có ba yêu cầu đối với họ hàm băm H: 1.
H có thể sử dụng được, tức là tồn tại một thuật toán thời gian đa thức xác suất khi cho đầu vào K thì cho ra một 𝐻𝐾. D dễ lấy mẫu, tức là tồn tại một thuật toán thời gian đã thức xác suất khi chọn một phần tử phân bố đều từ D. 𝐻𝐾 có thể tính trong thời gian đa thức, tức là tồn tại một thuật toán thời gian đa thức (theo l) khi cho đầu vào 𝑀 ∈ 𝐷 thì tính được 𝐻𝐾 (𝑀). Định nghĩa các tính chất an toàn 1.
Mô hình tấn công Mô hình tấn công được xây dựng trước khi định nghĩa các tính chất an toàn của một hàm băm mật mã. Nếu không có mô hình tấn công phù hợp thì không thể nói rằng một hàm băm có tính chất an toàn hay không. Mô hình tấn công sử dụng để định nghĩa các tính chất an toàn của hàm băm mật mã ở đây là mô hình RAM [13] (Random Access Machine). Trong mô hình này, đối phương là một chương trình, với một ngôn ngữ lập trình cho trước và chạy trên mô hình RAM.
Đối phương hay chương trình tấn công có thể lấy số lượng đầu vào tùy ý. Có ba dặc điểm quan trọng trong mô hình RAM. Thứ nhất, mô hình RAM có các con trỏ. Các con trỏ này cho phép đối phương truy vấn bit thứ i của tham số x bằng biểu diễn (𝑖, 𝑥) trong một số thanh ghi riêng biệt.
Kết quả truy vấn này được trả về trong đơn vị thời gian. Điều này loại bỏ trường hợp đối phương bị chậm khi đọc thông điệp dài, ví dụ khi cần đọc một dữ liệu đầu vào quá dài nhưng chỉ lấy bit cuối cùng. Thứ hai, mô hình RAM có các bit ngẫu nhiên mà đối phương có thể truy cập. Nó gần giống với một máy Turing xác suất truyền thống sử dụng trong mật mã.
Các bit ngẫu nhiên cho phép đối phương có thể là một thuật toán ngẫu nhiên hóa. Truy cập tới một số nguyên ngẫu nhiên trong khoảng [1, 𝑛] cần thời gian 𝒪(𝑙𝑜𝑔𝑛). Thứ ba, đối phương có quyền truy cập tới hàm băm được thiết kế để phá trong đơn vị thời gian. Ví dụ, nếu đối phương cần tính giá trị băm của một thông điệp cho trước thì nó được thực hiện bởi mô hình RAM trong đơn vị thời gian.
Điều này chống việc xây dựng một hàm băm "an toàn" bằng cách yêu cầu hàm băm thực hiện thời gian hàm mũ khi tính một giá trị băm đơn. Tài nguyên sử dụng để mô tả sự thành công của một tấn công là thời gian, gọi là t. Một tấn công được gọi là thành công nếu trả về kết quả đúng, được xác định bởi một số thực nghiệm, trong khoảng thời gian cho phép. Để chống lại sự thỏa hiệp thời gian và bộ nhớ, đây là một cách phổ biến sử dụng để phá các hàm mật mã, thời gian thực hiện của tấn công được tính là thời gian thực hiện của chương trình, cộng với kích cỡ của chương trình.
Điều này ngăn cản đối phương lưu trữ các giá trị tính trước của mọi điểm trong miền xác định và miền giá trị của một hàm cho trước. Trong mô hình này thời gian cần để tấn công xây dựng bằng thời gian cần để lưu trữ nó trong chương trình. Phương pháp định nghĩa tính chất an toàn Với một mô hình tấn công đã chọn, việc tiếp theo là xác định một phương pháp để định nghĩa các tính chất an toàn. Phương pháp định nghĩa các tính chất an toàn được sử dụng dưới đây được thực hiện dựa trên cơ sở tham số cố định, tức là các tham số về thời gian và lợi thế tấn công được cho trước.
Theo phương pháp này, các tính chất an toàn của hàm băm được mô tả theo hai phần: Mô tả thực nghiệm và mô tả tấn công thành công [13]. Mô tả thực nghiệm trình bày các bước mà đối phương thực hiện và môi trường với tính chất an toàn cụ thể tác động tới hàm băm. Ký hiệu 𝐸𝑥𝑝𝐻𝑋𝑋𝑋 (𝐴) biểu diễn thực nghiệm mô tả tính chất XXX sử dụng hàm băm H và tấn công A. Mỗi bước trong mô tả thực nghiệm được tiến hành tuần tự.
Nếu một bước nào đó không liên hệ với tấn công thì cho rằng bước đó được thực hiện bởi môi trường. Tấn công chỉ biết rõ về các giá trị đầu vào. Kết quả của thực nghiệm là giá trị nhị phân. Nếu tấn công có thể thỏa mãn đầu vào của thực nghiệm thì trả về giá trị 1, tức là đối phương có thể tấn công thành công với tính chất thực nghiệm đang xét.
Ngược lại tấn công không thỏa mãn điều kiện thì trả về giá trị 0, tức là tấn công thất bại đối với tính chất đó. Khi định nghĩa không được phát biểu tường minh, thì thực nghiệm phải thực hiện nhiều lần tấn công đó. Xác suất là giá trị trung bình của kết quả thực nghiệm. Mô tả tấn công thành công được phát biểu như sau: Mọi tấn công thực thi với thời gian không quá t, lợi thế tấn công 𝐴𝑑𝑣𝐻𝑋𝑋𝑋 (𝐴) phải nhỏ hơn ε đối với hàm có tính chất XXX mô tả bởi thực nghiệm 𝐸𝑥𝑝𝐻𝑋𝑋𝑋 (𝐴).
Trong đó, lợi thế tấn công là lợi thế vượt trội hơn tấn công vét cạn. Với một tấn công A, một họ hàm băm H, và một tính chất XXX thì lợi thế tấn công được ký hiệu là 𝐴𝑑𝑣𝐻𝑋𝑋𝑋 (𝐴). Định nghĩa hình thức về các tính chất an toàn a) Kháng tiền ảnh Họ hàm băm là kháng tiền ảnh nếu với một giá trị băm cho trước, thì khó có thể tìm được đầu vào bất kỳ mà khi băm cho ra giá trị băm đó. Định nghĩa hình thức về một họ hàm băm kháng tiền ảnh được xây dựng qua thực nghiệm trong Hình 1.1 và Định nghĩa 1.
$ 𝐾← 𝒦 $ 𝑀1 ← 𝑀 $ 𝑌← 𝐻𝐾 (𝑀1 ) $ 𝑀2 ← 𝐴(𝐾, 𝑌) if (𝑌 = 𝐻𝐾 (𝑀2 )) return 1 else return 0 Hình 1. Thực nghiệm kháng tiền ảnh Định nghĩa 1.1, [13]): Một họ hàm băm H là (t, ε) – kháng tiền ảnh nếu 𝐴𝑑𝑣𝐻𝑃𝑟𝑒 (𝐴) < 𝜀 với mọi tấn công A thực hiện thời gian nhỏ hơn t, trong đó: 𝐴𝑑𝑣𝐻𝑃𝑟𝑒 (𝐴) = 𝑃𝑟[𝐸𝑥𝑝𝐻𝑃𝑟𝑒 (𝐴) = 1] và xác suất được lấy trên toàn bộ K 𝒦, M ℳ và các lựa chọn ngẫu nhiên của A. Định nghĩa trên phát biểu chính xác độ khó "tính ngược đối với tất cả các đầu ra định trước".