Cơ sở mật mã học - Chương 7: Các hàm hash

Z) = (XÙY) Ú(XÙZ) Ú(YÙZ)
	h(X,Y,Z) = XÅ YÅ Z
Các hình 7.8-7.10 sẽ mô tả đầy đủ các vòng 1,2 và 3 của MD4.
MD4 được thiết kế chạy rất nhanh và quả thực phần mềm chạy trên máy Sun SPARC có tốc độ 1.4 Mbyte/s. Mặt khác, khó có thể nói đIều gì cụ thể về độ mật của hàm hash, chẳng hạn như MD4 vì nó không dựa trên vàI toán khó đã nghiên cứu kĩ (ví dụ như phân tích nhân tử trên bàI toán logarithm rời rạc). Vì thế trong trường hợp Dé sự tin cậy vào độ an toàn của hệ thống chỉ có thể đạt được về thời gian và như vậy có thể hi vọng hệ thống vừa được nghiên cứu và không tìm thấy sự không an toàn nào.
	Hình 7.8 : Vòng 1 của MD4 .(round 1)
A = (A+ f(B,C,D) + X[0]) << 3
D = (D + f(A,B,C) +X[1]) << 7
C = (C + f(D,A,C) +X[2]) << 11
B = (B + f(C,D,A) +X[3]) << 19
A = (A + f(B,C,D) +X[4]) << 3
D = (D + f(A,B,C) +X[5]) << 7
C = (C + f(D,A,C) +X[6]) << 11
B = (B + f(C,D,A) +X[7]) << 19
A = (A + f(B,C,D) +X[8]) << 3
D = (D + f(A,B,C) +X[9]) << 7
C = (C + f(D,A,C) +X[10]) << 11
B = (B + f(C,D,A) +X[11]) << 19
A = (A + f(B,C,D) +X[12]) << 3
D = (D + f(A,B,C) +X[13]) << 7
C = (C + f(D,A,C) +X[14]) << 11
B = (B + f(C,D,A) +X[15]) << 19
Mặc dù MD4 vẫn chưa bị phá song các phiên bản yếu cho phép bỏ qua hoặc vòng thứ nhất hoặc thứ ba dều có thể bị phá không khó khăn gì. nghĩa là dễ dàng tìn thấy các va chạm đối với các phiên bản chỉ có hai vòng. Phiên vản mạnh của MD5 là MD5	 được công bố năm 1991. MD5 dùng vòng thay cho ba và chậm hơn 30% so với MD4 (khoảng 0.9 Mbyte/s trên cùng máy).
	Chuẩn hàm hash an toàn phức tạp và chậm hơn. Ta 	sẽ không mô tả đầy đủ song sẽ chỉ ra một vàI cảI tiến trên nó.
SHS được thiết kế để chạy trên máy kiến trúc endian lớn hơn là trên máy endian nhỏ.
SHA tạo ra các bản tóm lược thông báo 5 thanh ghi (160 bit).
SHS xử lí 16 từ của bức đIện cùng một lúc như MD4. Tuy nhiên, 16 từ trước tiên được ”mở rộng” thành 80 từ ,sau đó thực hiện một dãy 80 phép tính ,mỗi phép tính trên một từ.
Hình 7.9 Vòng 2 củaMD4.
A = (A +g(B,C,D) + X[0] + 5A827999) <<3
D = (D +g(A,B,C) + X[4] + 5A827999) <<5
C = (C +g(D,A,B) + X[8] + 5A827999) <<9
B = (B +g(C,D,A) + X[12] + 5A827999) <<13
A = (A +g(B,C,D) + X[1] + 5A827999) <<3
D = (D +g(A,B,C) + X[1] + 5A827999) <<5
C = (C +g(D,A,B) + X[5] + 5A827999) <<9
B = (B +g(C,D,A) + X[13] + 5A827999) <<13
A = (A +g(B,C,D) + X[2] + 5A827999) <<3
D = (D +g(A,B,C) + X[6] + 5A827999) <<5
C = (C +g(D,A,B) + X[10] + 5A827999) <<9
B = (B +g(C,D,A) + X[14] + 5A827999) <<13
A = (A +g(B,C,D) + X[3] + 5A827999) <<3
D = (D +g(A,B,C) + X[7] + 5A827999) <<5
C = (C +g(D,A,B) + X[11] + 5A827999) <<9
B = (B +g(C,D,A) + X[15] + 5A827999) <<13
Dùng hàm mở rộng sau đây: Cho trước 16 từ X[0] ...X[15], ta tính thêm 64 từ nữa theo quan hệ đệ quy.
	X[j] = X[j-3]Å X[j-8]Å X[j-14]Å X[j-16], 79 ³ j ³ 16	7.1
Kết quả của phương trình (7.1) là mỗi một trong các từ X[16]...X[79] được thiết lập bằng cách cộng Å với một tập con xác định nào đó của các từ X[0]...X[15].
	Ví dụ: Ta có:
	X[16] = X[0] ÅX[2]ÅX[8]ÅX[13]
	X[17] = X[1] ÅX[3]ÅX[9]ÅX[14]
	X[18] = X[2] ÅX[4]ÅX[10]ÅX[15]
	X[19] = X[0] ÅX[2]ÅX[3]ÅX[5]ÅX[8]ÅX[11]ÅX[13]
	X[79] = X[1] ÅX[4]ÅX[15]ÅX[8]ÅX[12]ÅX[13].
Một đề xuất đòi hỏi sửa lại SHS liên quan đến hàm mở rộng trong đó đề nghị đặt lại phương trình 7.1 như sau:
X[j] = X[j-3] ÅX[j-8]ÅX[j-14]ÅX[j-16] <<1; 79³ j ³ 16	(7.2)
Hình 7.10 : Vòng ba của MD4.
A = (A + h(B,C,D) + X[0] + 6ED9EBA1) <<3
D = (D + h(A,B,C) + X[8] + 6ED9EBA1) <<9
C = (C + h(D,A,B) + X[4] + 6ED9EBA1) << 11
B = (B + h(C,D,A) + X[12] + 6ED9EBA1) << 15
A = (A + h(B,C,D) + X[2] + 6ED9EBA1) <<3
D = (D + h(A,B,C) + X[10] + 6ED9EBA1) <<9
C = (C + h(D,A,B) + X[6] + 6ED9EBA1) << 11
B = (B + h(C,D,A) + X[14] + 6ED9EBA1) << 15
A = (A + h(B,C,D) + X[1] + 6ED9EBA1) <<3
D = (D + h(A,B,C) + X[9] + 6ED9EBA1) <<9
C = (C + h(D,A,B) + X[13] + 6ED9EBA1) << 11
B = (B + h(C,D,A) + X[13] + 6ED9EBA1) << 15
A = (A + h(B,C,D) + X[3] + 6ED9EBA1) <<3
D = (D + h(A,B,C) + X[11] + 6ED9EBA1) <<9
C = (C + h(D,A,B) + X[7] + 6ED9EBA1) << 11
B = (B + h(C,D,A) + X[15] + 6ED9EBA1) << 15
Như trước đây , toán tử ’’<<1’’ là phép dịch vòng trái một vị trí.
7.8 nhãn thời gian (timestamping).
	Một khó khăn trong sơ đồ chữ kí là thuật toán kí có thể bị tổn thương. Chẳng hạn, giả sử Oscar có khả năng xác định số mũ mật a của Bob trên bất kì bức điện nào mà anh ta muốn. Song còn vấn đề khác (có thể nghiêm trọng hơn )là : từ đây người ta sẽ đặt câu hởi về tính xác thực của tất cả các bức điện mà Bob kí, kể cả những bức điện mà anh ta kí trước khi Oscar đánh cắp được thuật toán.
	Từ đây lại có thể nảy sinh tình huống không mong muốn khác : giả sử Bob kí một bức điện và sau đó từ chối là đã không kí nó. Bob có thể công khai thuật toán kí của mình sau đó công bố rằng chữ kí của anh ta trên bức điện đang nói trên là giả mạo.
	Lí do có các kiểu sự kiện này là do không có các nào các định bức điện được kí khi nào. Nhãn thời gian có thể cung cấp bằng chứng rằng, bức điện đã được kí vào thời điểm cụ thể nào đó. Khì đó nế thuật toán kí của Bob có nhược điểm (bị tổn thương) thì bất kì chữ kí nào anh ta kí trước đó sẽ không còn hợp lệ. ĐIều này giống với kiểu thực hiên các thẻ tín dụng: Nếu ai đó làm mất thẻ tín dụng và thông báo cho nhà băng đã phát hành thì thẻ mất hiệu lực. Song các cuộc mua bán thực hiện trước khi mất nó thì vẫn không bị ảnh hưởng.
	Trong phần này sẽ mô tả một vàI phương pháp gắn nhãn thời gian. Trước hết,nhận xét rằng, Bob có thể tạo ra một nhãn thời gian có sức thuyết phục trên chữ kí của anh ta. Đầu tiên, Bob nhận được một thông tin “hiện thời “ có sẵn công khai nào đó, thông tin này không thể dự đoán được trước khi nó xảy ra. Ví dụ thông tin chứa tất cả các lợi thế về môn bóng chày của các liên minh chính từ ngày trước đó, hay các giá trị của tất cả cổ phần đwocj lên danh sách trong sở giao dịch chứng khoán NewYork. Ta kí hiệu thông tin này bằng chữ pub.
	Bây giờ giả sử Bob muốn dán nhãn thời gian trên chữ kí của mình trên bức điện x. Giả thiết rằng, h là hàm hash công khai biết trước. Bob sẽ thực hiện theo thuật toán trong hình 7.11.Sau đây là cách sơ đồ làm việc : sự có mặt của thông tin pub có nghĩa là bob không thể tạo ra được y trước ngày đang nói đến. Còn một thực tế là y công bố trong một tờ báo ra ngày tiếp theo chứng tỏ rằng bob đã không tính y sau ngày được nói đến. Vì thế chữ kí y của bob bị hạn chế trong thời hạn một ngày. Cũng nhận xét thấy rằng, bob không để lộ bức điện x trong sơ đồ này vì chỉ có x được công bố ... Nếu cần bob có thể chứng minh rằng x là bức điện mà anh ta đã kí và dán nhãn thời gian một cách đơn giản là làm lộ nó.
	Cũng không khó khăn tạo ra tạo ra các nhãn thời gian nếu có một cơ quan dịch vụ dán nhãn đáng tin cậy. Bob có thể tính z = h(x) và y = sigk (z) và sau đó gửi (z và x ) đến cơ quan làm dịch vụ dán nhãn thời gian (TSS). TSS sau đó sẽ gắn ngày D và kí (đánh dấu)bộ ba (z,y,D). Công việc này sẽ hoàn hảo miễn là thuật toán kí của TSS an toàn và TSS không thể bị mua chuộc để lùi ngày dãn nhãn của thời gian. (chú ý rằng phương pháp này chỉ được thiết lập khi bob đã kí một bức điện trước một thời gian nào đó. Nếu bob muốn thiết lập cáI anh ta đã kí nó sau ngày nào đó ,anh ta có thể kết hợp thông tin công khai pub nào đó như phương pháp trước đó).
	Hình 7.11 :Dán nhãn thời gian lên chữ kí trên bức điện x.
Bob tính z = h(x).
Bob tính z’ = h(z ||pub).
Bob tính y = sigk(z’).
Bob công bố (z,pub,y) trên tờ báo ra ngày hôm sau.
	Nếu như không muốn tin vô điều kiện vào TSS thì có thể tăng độ an toàn lên bằng cách liên kết các thông báo đã dán nhãn thời gian. Trong sơ độ như vậy, bob sẽ gửi một bộ ba được xếp thứ tự (z,x,ID)(Bob) cho TSS. ở đây, z là bản tóm lược thông báo của bức điện x,y là chữ kí của bob trên z ,còn ID(Bob) là thông tin định danh của Bob. TSS sẽ dãn nhãn thời gian một chuỗi bộ ba có dạng này. Kí hiệu (zn,yn,IDn) là bộ ba thứ tự n được TSS dán nhãn thời gian và cho tn là kí hiệu thời gian lúc thực hiện yêu cầu thứ n.
	Hình 7.12: Dán nhãn thời gian (zn,yn,IDn).
TSS tính Ln = (tn-1,IDn-1,Zn-1yn-1,h(Ln-1))
 TSS tính Cn = (n, tn, zn, IDn, Ln)
 TSS tính Sn = sigTSS (h (Cn))
 TSS gửi (Cn, Sn, IDn ) cho IDn. 
TSS sẽ dán nhãn thời gian lên bộ ba thứ n bằng fthuật toán nêu trên hình 7.12. Ln là “thông tin liên kết để nối yêu cầu thứ n vào yêu cầu trước đó. (L0 được chọn làm thông tin gia nào đó (được xác định trước đây)để quá trình được bắt đầu)”.
	Bây giờ nếu được yêu cầu (challenge). Bob có thể để lộ bức điện xn của mình, và sau đó có thể xác minh yn. Tiếp theo , các minh chữ kí sn của TSS. Nếu muốn thì có thể đòi IDn-1 hoặc IDn+1 để tạo ra nhãn thời gian (Cn-1, Sn-1, IDn) và (Cn+1, Sn+1, IDn+2) tương ứng của chúng. Các chữ kí của TSS có thể được kiểm tra theo nhãn thời gian này. Dĩ nhiên , quá trình này có thể tiếp tục tới mức mong muốn, trước hay sau đó.
7.9.các chú ý về tài liệu dẫn
Hàm hash log rời rạc được mô tả trong mục 7.4 là của chaum , van heijst và pfitzmann [CvHP92]. Còn hàm hash có thể chứng mình đwocj là an toàn liễn là hợp số n không thể phân tích thành nhân tư là do gibson [Gib91] đưa ra (bài tập 7.4 có mô tả sơ đồ này).
	Cơ sở cho việc m mở rộng hàm hash trong mục 7.5 là của Damgard [DA90] Merkle cũng đưa ra các phương pháp tương tự [ME90].
	Các thông tin liên qua tới việc xây dựng các hàm hash dựa trên các hệ thông mã khoá bí mật. Bạn đọc có thể xem trong [PGV94] của Preneel, Govaerts và Vandewalle.
Thuật toán MD4 được đưa ra trong [Ri91] của Rivest, còn tiêu chuẩn hash an toàn được mô tả trong [NBS93]. Tấn công hai trong ba vòng MD4 là của Boer và Bossalaer [DBB92]. Các hàm hash gần đây kể cả N-hash là của [MOI90] và Snefru [ME90A].
	Ngoài ra có thể tìm thấy tổng quan về kĩ thuật băm trong Preneel, Govaerts, Vandewalle [PGV93].
Bài tập