CHƯƠNG 1: TONG QUAN VE HAM BAM. LLL Binh nghĩa về hàm băm. Him bm (hash fonction) ta giải thuật nhằm sinh ra các giá tr băm trơng cứng với mỗi khối đỡ liệ (có thể là một chuối kí ự, một đối tượng trong lập trình hướng đối tượng, vo.) Giá trị băm đồng vai g như một khôa để phân biệt các khối dỡ liệu, ty nhiên, người ta chấp nhận hiện tượng trồng khéa hay còn gọi là đọng độ và cổ gắng cải thiện giải thuật để giảm thiêu sự đụng độ. Hầm băm thường được đùng trong bảng băm nhằm gimm chỉ phí tính toán kh tim một khối đỡ lieu trong một tập hợp (chờ việc so sánh các giá trị bấm nhanh hơn việc so sãnh những hối dữ liệu có kích thước lổn) Trong ngành mật mã học, một hàm bấm mật mã học (iống Anh Cryptographic bash đuacion) là một hàm băm: với một số tính chất bảo mật nhất định để phù hợp tiệc sử dạng trong chiều ứng dung bảo mit thing tin da dang chẳng hạn như chimg the (authentication) va kiém tra tính nguyên vẹn của thông điệp (nessoge busgrlg).
Một hàm băm nhận đầu vào là một xâu kỹ tự dil ay thông đập) cỗ độ ity ý và tạo ra kết qu là một sâu ký tự có độ đãi cổ định, đãi khí được gọi là dồm tất thông điệp (message digest) hoke chit hi 36 (digital fingerprint) THình1.1 Hoạt động của một hàm bấm "Nôi rộng ra, một hàm băm mật mã học phải hoạt động càng giống với một hầm ngẫu nhiên cảng tế, trong khi vẫn cô tính chất đơn định và tỉnh toán cổ hiệu quả "Một hàm băm mật mã học được coi là không an toàn nếu một trong các việc sau là hả th về mặt tính toầm + Cho mt tim tit (digest), m một thông điệp (chưa biế) khóp tới tôm tits. Tim các "xung dét bim" (hash collision), trong đồ hai thông điệp khác nhau cổ tôm tất trồng nhan "Nếu có thể thực hiện một trong bai iệc tiên, một người cổ thể tấn công bằng cách đồng các cách tiên để thay một thông điệp không được xắc nhận (onanthorized mesease) vào chỗ của một thông điệp được xắc nhận `Về lý trởng, việc tìm bai thông điệp cô tôm tất rất giống nhau cũng nền không khả thủ; người ta không muốn một kẽ tấn công có thể tim hiểu được điều gì đồ hữu ích về một thông điệp nếu biết ôm tắt 1. Lịch sử phát triển cia hàm băm. Cac him băm mật mã học trên thục ế đã được chứng minh là công ov ding tin cây của mật mã họ hiện đạ.
Tầm quan trọng của chủng được công nhận lẫn đầu tiên khi PKC (Mật mã học với khốa phổ biến) được phất minh bởi Diffie va Hellman vio năm 1976, và từ diy nỗ trở thành 1 phần không thể thiếu của của ĐKC. Đăng tiếc, các tiến bộ gần đây trong lĩnh vực phá mã đã tìm ra nhiều khuyết điểm trong hầu hết céc him băm phổ biến, điều này đã thúc giọc các nhà nghiên cu quan tim đến lĩnh vực này. Đáp lại lời kêu gọi này, các nhà nghiên cứu đã phát triển 2 hướng nghiên cứu chính hoặc là chỉnh sửa lại các cấu trúc hiện 06 nay việc điều chỉnh chúng 1 chútđề xóa bố các nhóm khuyết điểm cụ thể, hoặc là thiết kế các hầm băm mới hoàn toàn tờ vạch xuất phát. Theo hướng thứ nhất, nu khẩm: phá ra được các khuyết điểm đang tên tại thì các quy định đề thiết kế hàm băm còn.
chưa được hoàn mỹ và nếu chúng không được chỉnh sốa lại 1 cch tổng thể thi những khuyết điểm này sẽ vẫn côn tẫn tại, mặc đồ cổ vẽ như chúng đã được chỉnh: sổa lại bằng 1 số biện phấp nhỏ. Trơng tp, theo hướng thứ 2, nếu 1 him bim được thiết kế lạ tờ đầu thì vẫn có thể còn tên tại nhiễu khuyết điểm, nhưng nỗ cũng bi ảnh hưởng ngầm từ các khuyết diém (có thể là các khuyết điểm lớn hơn nhiều) mà. “không được nhận ra từ thời kỹ đầu của phát triển. Mặt khác, các cấu trúc hiện thời lại cổ to điểm là đã được nghiền cứu và phân tích sâu rộng qua nhiều năm, do vậy, nếu các hàm băm mới không được thiết kế cần thân, chúng có thể sẽ bị tấn công nhiều hơn là chống lạ Các hàm băm thường là nhõng hằm nhiễu ứng do ching ảnh xạ các đầu vào có độ dai bất kỹ thành các đu ra có độ vào cổ định và đầu vào thường lớn hơn đều +e (hảm băm là các hàm nén).
Do đó, các vụ đọng độ (các thông điệp khác nha băm thành cùng 1 giá tr) ở bảm băm thường là không tránh được do quy luật ngăn hộc. Yoval fa nh nghiên cứu đầu tiên tảo luận về vấn đề làm thể nào để tìm ra những vụ đọng độ trong hàm băm bằng sự sử đọng Birthday Paradox, việc này din đến hiện trợng khả phổ biển hiện nay đổ là ự tấn côngngày nh nhất ở kiễu tấn công này, người tam ra Ì vụ đụng độ với xác suất là 42/2" sau khi q try vin đến 1 hầm băm cho ra các gi trị với độ đài với độ dai bít Dù khả năng chốnglại ar đọng độ chắc chấn là 1 thuộc tính rất quan trọng ma hàm băm nên cố nhưng đồ không phải là thuộc tỉnh duy abit, và thậm chỉ tong 1 số ứng đụng th thuộc tính này là không bắt buộc. Vĩ dụ như khả năng chẳng nghịch ảnh (inh bắt khả nghịch) là Ì thuậc tính khổ cổ được và mang tính thực hơn Trên thực tẾ ở hẳu hết các ting dung dé o6 thể nghịch đầo 1 giá trị băm tỉ sẽ tẫn thất hơn nhi là tìm ra 1 ve ta 2 thông điệp bắt kỷ. Do đô, chính ứng dụng mà sử dụng hằm băm sẽ định các thuậc tỉnh an toàn mà hằm bấm cần bão tổn.
Cuộc thí SHA-3. Trong 1 thời gian dai, SHA-1 va MDS là những hàm băm gần gối nhất với chuẫn băm khô chính thúc. Tuy nhiên điều này đã thay đổi từ năm 2004 và 2005 khi đó Wang và đồng sự chứ g tô rằng im ra các vụ đụng độ cho MDS sé df dàng khi giảm dẫn đều các công việc cần làm kài tìm các vụ đọng độ trên SHA-L xuống còn 2, nhé hơn nhiều so với con số dự đoán ban div 2° "Dù sự phá hủy với độ phức tạp 2*°tvẫn chỉ là lý thuyết, người ta còn chúng tô ring SHÀ-1 (ti thôi điểm đổ) vẫn chưa đỏ mạnh và chưa thể chống lại được các vụ đọng độ như vẫn được mong đợi. Do điều này mà vào tháng 11/2007 NIST (Viện Tiêu chuẩn và Công nghệ quốc gia Hoa Kÿ) đã công bổ 1 cuộc thỉ mở rộng để lựa chẹn 1 tiêu chuẫn hàm băm mới gọi là SHA-3.
NIST nhận được 64 đơn đăng ký, 51 don trong số đồ được lựa chọn vào vòng 1 của cuộc thỉ vào tháng 12 năm 2008 Thắng 7 nấm 2009, chỉ có 14 đơn dự thỉ lọt qua vòng 1 được vào tiếp vàng 2 Thing 12/2010, Š ứng cỡ viên cuối công được chọn ra (6ó là BLARE, GrOst, 7H, Xecode and Sken), và sẽ công bổ giải nhất vào Quý 2 năm 2012 1-1-4. Thuộc tính an toàn của hàm băm|4] Các thuộc tính an toàn cơ bản (truyền thống) mã 1 hàm băm nên có đồ là: được sự đụng độ, ngăn được sự nghịch ảnh và nghịch ảnh thứ 2. Hình 12 minh họa các thuộc tinh nay theo so đổ. Mặc đò đây là những thuộc tính an toàn.
phỗ biến mã 1 hàm băm nên cổ thì ở Ì 5 img dung cụ thể ví có thể cô 1 số thuộc tính phụ khác mà hằm băm cần phảicó nếu chúng được sở dụng trong Ì ông đọng cụ thể "Nhân chung, khi ta nôi rằng 1 cuộc tẫn công phá vỡ được 1 hàm băm cụ hể thi không nhất thiết nô có nghĩa rằng hâm băm đồ hoàn toàn bi pha hiy trong the tin. nếu cuộc tấn công có thể chứng mình được rằng 1 hâm băm có thể bị phá hồng bởi cuộc tấn công ngày sỉnh nhật hay tấn công bao Iyo(ci dy nh tim ra 1 ve đọng độ, bay nghịch ảnh, hay nghịch ảnh thứ 2) với khối lượng công việc ít hơn truy vẫn; hàm băm được gọi là bị phá vỡ, mặc đồ lược công việc truy vấn đễ phá vỡ nó vẫn chưa làm được trong thực tn (đầy được gọi là ự tắn công rên If thuy Thực vậy, tim ra các điểm chưa hoàn chỉnh như vậy ở 1 hàm băm là 1 bing ching cho các yếu điểm về cầu trúc mà có thé bi phá hủy ở phạm vi lớn hơn để biến sự tấn. công trên lý thuyết này trở thành thọc tố: mẫu đầu tiên là MDS, thuật toần này đầu tiên bị phá vỡ trên lý thuyết, sau đô các cuộc tấn công dẫn dẫn được cải biển và "gây nay các rụ đụng độ thật có thể được tìm thẤy ở MDS TỶ THình1. 2 Sơ đỗ biễu diễn các thuộc tính khả năng chống đụng độ, ngấn sự nghịch ảnh vã nghịch ảnh thứ 2 2).
Khả năng chống đụng độ (CR) XMết vụ đụng độ hàm bấm xây ra khỉ 2 thông điệp khác nhau bất kỳ băm thành công 1 giá tị, Tóc là với 1 hằm băm chống đụng độ I1, thì nỗ không thể tính toán để tìm ra 2 thông điệp M và M' bất kỹ sao cho HM) = HCM”) trong khi M. Điều này cũng có thể áp dụng cho ho him bm (tức là các hàm băm có khóa, ở đây các thành viên cũa họ bảm băm được thống kê bối các khôa khác nhan). Chính thức thì vo điểm của 1 kể thù À của việc tìm ra đụng độ trong Ì hàm băm HÍ được ắc định như sau Advi (A) = Pr [(0M) = AM # MAHO = HON N) an 9). Khả năng chống lại sy nghịch aah (Pre).
‘Vei mọi mục đích thực tiễn, các ham băm cần phấi là bất khả nghịch. Khi 1 thông điệp được băm, nó phấi không có khả năng khôi phục được thong điệp gốc tử. các giá tị băm lấy được, tốc a, với 1 hàm băm chống được sự nghịch ảnh H, giá tr "băm H(M) cho trade của 1 thông điệp cụ thể M thì nó phải không có khả năng khôi phục thông điệp gốc M, hoặc tạo ra bất kỹ thông điệp M’ # M sao cho H(M’) = HCM). Ngắn gọn hơn: Advg “T(A) = Pr [u Leary — HON ÈA@):H@3=v| d2 c)- Khả năng chống lạ sự nghich anh thi 2 (Sec).
Cho 1 ham băm H có khả năng chống sự nghịch ảnh và 1 thông điệp M. thì 1 kế tấn công A sẽ không thể tìm được 1 thông điệp M' khác sao cho M + M! và cả ‘Mva M’ đều băm thành cùng 1 giá trị, H(M) = H(M").