›
›

An toán thông tin - Chương 3: Toàn vẹn dữ liệu

pdf 69 trang vanle 4730
Download
Bạn đang xem 20 trang mẫu của tài liệu "An toán thông tin - Chương 3: Toàn vẹn dữ liệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfan_toan_thong_tin_chuong_3_toan_ven_du_lieu.pdf

Nội dung text: An toán thông tin - Chương 3: Toàn vẹn dữ liệu

  1. 3 PHẦN I: HÀM BĂM MẬT MÃ HỌC (CRYTOGRAPHIC HASH FUNCTIONS)
  2. Nội dung chính 1. Tính toàn vẹn và tính bí mật 2. Tổng quan về hàm băm (Hash Function) 3. Ứng dụng của hàm băm 4. Kiến trúc hàm băm 5. Hai hàm băm MD5 và SHA1 ( Cryptography and Network Security: Principles and Practices (3rd Ed.) – Chapter 11) (Cryptography & Network Security. McGraw- Hill, Inc., 2007., Chapter 12) Trần Thị Kim Chi 1-2
  3. Mục tiêu • Giới thiệu ý tưởng tổng quát của hàm băm mật mã học • Định nghĩa hàm băm • Tính chất hàm băm cần có • Bài toán ngày sinh • Nêu các ứng dụng của hàm băm • Chứng thực thông điệp • Chữ ký số • Các ứng dụng khác • Thảo luận cơ chế Merkle-Damgard như là kiến trúc cơ bản của hàm băm Trần Thị Kim Chi 1-3
  4. Mục tiêu • Thảo luận vầ hàm băm MD5 và SHA1 • Sơ lược vầ MD5 và SHA1 • Sơ đồ tổng thể • Cấu trúc hàm F tại mỗi bước • Cấu trúc của một vòng trong F • So sánh MD5 và SHA1 Trần Thị Kim Chi 1-4
  5. 1. Tính toàn vẹn và tính bí mật • Tình toàn vẹn (Integrity): người tấn công không thể can thiệp để sửa đổi nội dung thông điệp • Mã hóa chỉ nhằm đảm bảo tính bí mật, không giúp đảm bảo tính toàn vẹn thông tin • Người tấn công có thể sửa đổi nội dung thông điệp đã được mã hóa mà không cần biết nội dung thật sự của thông điệp • Ví dụ: Trong đấu giá trực tuyến, có thể thay đổi giá đặt của đối thủ mà không cần biết nội dung thật sự của giá đặt Trần Thị Kim Chi 1-5
  6. 2. Hash Function • Hàm băm là các thuật toán không sử dụng khóa để mã hóa, nó có nhiệm vụ băm thông điệp được đưa vào theo một thuật toán h một chiều nào đó, rồi đưa ra một bản băm – văn bản đại diện – có kích thước cố định. Do đó người nhận không biết được nội dung hay độ dài ban đầu của thông điệp đã được băm bằng hàm băm. • Giá trị của hàm băm là duy nhất, và không thể suy ngược lại được nội dung thông điệp từ giá trị băm này. Trần Thị Kim Chi 1-6
  7. 2. Hash Function • Input: M có kích thước bất kỳ • Output – giá trị h có kích thước cố định, ngắn. • H(x) – hàm một chiều (“Khó để tính nghịch đảo”) Trần Thị Kim Chi 1-7
  8. 2. Hash Function Trần Thị Kim Chi 1-8
  9. 2. Hash Function Hello, world. k NhbXBsZSBzZW50ZW5jZS A sample sentence to E B0byBzaG93IEVuY3J5cHR show encryption. pb24KsZSBzZ k Hello, world. NhbXBsZSBzZW50ZW5jZS D A sample sentence to B0byBzaG93IEVuY3J5cHR show encryption. pb24KsZSBzZ  Encryption is two way, and requires a key to encrypt/decrypt This is a clear text that can easily read without 52f21cf7c7034a20 h using the key. The 17a21e17e061a863 sentence is longer than the text above. • Hashing is one-way. There is noTrần 'deThị Kim- Chihashing’ 1-9
  10. 2. Hash Function x1 Thông điệp x2 y1 x3 Thông điệp rút gọn y2 Không gian thông điệp Không gian giá trị băm Không gian giá trị Băm nhỏ hơn rất nhiều so với Không gian thông điệp về mặt kích thước chắc chắn sẽ tồn tại đụng độ (trùng), nghĩa là có hai tin x và x” mà giá trị Băm của chúng là giống nhau, tức là h(x) = h(x”) Trần Thị Kim Chi 1-10
  11. Tính chất hàm băm 1. Tính chống tiền ảnh (Preimage resistant – one- way property): Cho trước giá trị băm h việc tìm x sao cho H(x)=h là rất khó 2. Tính chống tiền ảnh thứ hai (Second preimage resistant – weak collision resistant – Tính chống trùng yếu): Cho thông điệp đầu vào x, việc tìm một thông điệp x’ với (x’ x) sao cho h(x’)=h(x) là rất khó 3. Tính chống trùng mạnh (Strong Collision resistant): Không thể tính toán để tìm được hai thông điệp đầu vào x1 x2 sao cho chúng có cùng giá trị băm (Nghịch lý ngày sinh – Birthday paradox) Trần Thị Kim Chi 1-11
  12. Nghịch lý ngày sinh (birthday paradox) – Chứng minh trang 84 (BaiGiangATTT) Bài toán 1: Giả sử trong phòng có M sinh viên. Vậy xác suất để có hai SV có cùng ngày sinh là bao nhiêu phần trăm? (1 năm 365 ngày khác nhau) • Theo nguyên lý chuồng bồ câu Dirichlet: cần có 365+1 = 366 người để tìm thấy 2 người có cùng ngày sinh với xác suất 100%. Vì vậy với 30 người thì xác xuất này rất nhỏ. Rất nhỏ, đúng không • Tính theo xác suất thống kê toán học thì M(M-1) >=2 x 365 x loge2 (*) chỉ cần 23 người là đủ để xác suất hơn 50%. Vì vậy bài toán này gọi là nghịch lý ngày sinh Trần Thị Kim Chi 1-12
  13. Nghịch lý ngày sinh (birthday paradox) Điều này muốn nói lên rằng, trong nhiều trường hợp xác suất để hai mẩu tin có cùng bản Hash là không nhỏ như chúng ta nghĩ. Tính chống trùng mạnh Trần Thị Kim Chi 1-13
  14. Nghịch lý ngày sinh (birthday paradox) Bài toán 2: Giả sử bạn đang ở trong một lớp học với M sinh viên. Hỏi M tối thiểu là bao nhiêu để tồn tại một bạn khác có cùng ngày sinh với bạn với xác suất (XS) lớn hơn 50%? • XS để 1 người khác ngày sinh với bạn là 364/365. • XS để M người đều khác ngày sinh với bạn là (364/365)M. • XS để tồn tại ít nhất một người có cùng ngày sinh với bạn là: 1- (364/365)M • Để XS này >50% M>=253 người Tính chống trùng yếu Trần Thị Kim Chi 1-14
  15. Nghịch lý ngày sinh (birthday paradox) • Trần Thị Kim Chi 1-15
  16. Nghịch lý ngày sinh (birthday paradox) • Để tìm ra hai thông điệp có cùng giá trị băm (vét cạn) thì phải thử bao nhiêu thông điệp khác nhau? Phải thử khoảng 2n/2 thông điệp khác nhau (xác suất > 50%) • Ví dụ: Nếu n=128 thì phải thử 264 thông điệp (khá lớn), nghĩa là hàm hăm đạt được tính chống trùng mạnh (tương được tấn công vét cạn khóa của DES) Trần Thị Kim Chi 1-16
  17. Phân Loại hàm băm mật mã Cryptographic Hash Functions Không sử dụng khóa Message Authentication Manipulation Detection Codes Codes (MAC) (MDC) Sử dụng khóa Universal One-Way Collision Resistant One-Way Hash Functions Hash Functions Hash Functions (OWHF) (CRHF) (UOWHF) Trần Thị Kim Chi 1-17
  18. 3. Ứng dụng hàm băm • Chứng thực thông điệp (Message Authentication) • Chữ ký số (Digital Signatures) • Các ứng dụng khác (Other Applications) Trần Thị Kim Chi 1-18
  19. 3.1 Message Authentication • Là một cơ chế/dịch vụ được dùng để kiểm tra tính toàn vẹn của một thông điệp. • Đảm bảo rằng dữ liệu nhận được là chính xác như khi được gửi (không bị chỉnh sửa, chèn, hoặc thay thế) • Trong nhiều trường hợp, có một yêu cầu là cơ chế chứng thực phải hỗ trợ nhận dạng người gửi (sender) là hợp pháp. • Hàm băm dạng này, giá trị băm (h) được gọi là tóm tắt thông điệp (message digest) Trần Thị Kim Chi 1-19
  20. Integrity • to create a one-way password file • store hash of password not actual password • for intrusion detection and virus detection • keep & check hash of files on system Trần Thị Kim Chi 1-20
  21. Password Verification Store Hashing Password Verification an input password against the stored hash Iam#4VKU Iam#4VKU Password store h h 661dce0da2bcb2d8 661dce0da2bcb2d8 661dce0da2bcb2d8 2884e0162acf8194 2884e0162acf8194 2884e0162acf8194 Hash Matching Exactly? Password Yes No store Grant Deny Trần Thị Kim Chi 1-21
  22. Authentication • protects both a message's integrity as well as its authenticity , by allowing verifiers (who also possess the secret key) to detect any changes to the message content Trần Thị Kim Chi 1-22
  23. 3.1 Message Authentication • Ví dụ cơ chế chứng thực đơn giản Trần Thị Kim Chi 1-23
  24. 3.1 Message Authentication • Ví dụ cơ chế chứng thực đơn giản (tt) Trần Thị Kim Chi 1-24
  25. 3.2 Digital Signatures • Giá trị băm của thông điệp được mã hóa bằng private key của user, bất kỳ ai biết public key của user thì có thể thẩm tra thông điệp mà được gắn kết với chữ ký số. • Kẻ tấn công muốn hiệu chỉnh thông điệp thì sẽ cần phải biết private key của user. Trần Thị Kim Chi 1-25
  26. 3.2 Digital Signatures • Ví dụ: Trần Thị Kim Chi 1-26
  27. Hash Function Properties • Arbitrary-length message to fixed-length digest • Preimage resistant (One-way property) • Second preimage resistant (Weak collision resistant) • Collision resistant (Strong collision resistance) Trần Thị Kim Chi 1-27
  28. Properties : Fixed length Hello, world 661dce0da2bcb2d8 h 2884e0162acf8194 Fixed length Digest : L This is a clear text that can easily read without 52f21cf7c7034a20 using the key. The h 17a21e17e061a863 sentence is longer than the text above. • Arbitrary-length message to fixed-length digest Trần Thị Kim Chi 1-28
  29. Preimage resistant • This measures how difficult to devise a message which hashes to the known digest • Roughly speaking, the hash function must be one-way. Given only a message digest, can’t find any message (or preimage) that generates that digest. Trần Thị Kim Chi 1-29
  30. Exam Questions • Can we use a conventional lossless compression method such as zip as a cryptographic hash function? Answer : No, a lossless compression method creates a compressed message that is reversible.  Can we use a checksum function as a cryptographic hash function? Answer : No, a checksum function is not preimage resistant, Eve may find several messages whose checksum matches the given one. Trần Thị Kim Chi 1-30
  31. Second preimage resistant  This measures how difficult to devise a message which hashes to the known digest and its message • Given one message, can’t find another message that has the same message digest. An attack that finds a second message with the same message digest is a second pre-image attack. • It would be easy to forge newTrần digital Thị Kim Chi signatures from old signatures if the1-31 hash function used weren’t second preimage resistant
  32. Collision Resistant • Can’t find any two different messages with the same message digest • Collision resistance implies second preimage resistance • Collisions, if we could find them, would give signatories a way to repudiate their signatures Trần Thị Kim Chi 1-32
  33. 3.3 Other Applications Dùng lưu trữ mật khẩu (băm password): • Hàm băm được dùng để tạo one-way password file, trong cơ chế này giá trị băm của password được lưu, điều này tốt hơn là lưu chính bản rõ password. password không bị truy xuất bởi kẻ tấn công nơi chứa password. • Khi user nhập vào một password, thì giá trị băm của password được so với giá trị băm được lưu để kiểm tra. Trần Thị Kim Chi 1-33
  34. 3.3 Other Applications Dùng nhận diện xâm hại (intrusion detection) và nhận diện virus (virus detection). • Tính, lưu và bảo mật giá trị băm H(F) của các tập tin trong hệ thống (thể lưu trên CD-R) • Kẻ xâm hại cần phải hiệu chỉnh F mà không thay đổi H(F) Trần Thị Kim Chi 1-34
  35. 3.3 Other Applications • Dùng: Xây dựng hàm ngẫu nhiên giả (pseudorandom function - PRF) hoặc Phát sinh số ngẫu nhiên giả (pseudorandom number generator - PRNG) Trần Thị Kim Chi 1-35
  36. 4. Kiến trúc hàm băm an toàn ˗ Tác giả: Ralph Merkle, Ivan Damgård ˗ Hầu hết các hàm băm đều sử dụng cấu trúc này ˗ Ví dụ: SHA-1, MD5 Trần Thị Kim Chi 1-36
  37. 5. Hàm băm MD5, SHA1 • MD5 (Message Digest) • Phát minh bởi Ron Rivest (RSA) • Phát triển từ MD4, trước đó MD2 (không an toàn) • Kích thước giá trị băm là 128-bit • 1994 và 1998: một pp tấn công MD5 và một số thông điệp có cùng giá trị băm MD5 được chỉ ra (vi phạm tính chống trùng mạnh). Tuy nhiên MD5 vẫn còn sử dụng phổ biến Trần Thị Kim Chi 1-37
  38. 5.1 Hàm băm MD5 (128-bit, 264-bit) • Sơ đồ tổng thể H0 – 128-bit, chia thành 4 từ 32-bit, ký hiệu a,b,c,d – hằng số( thập lục phân) a=01234567; b=89abcdef; c=fedbca98; d=76543210 Trần Thị Kim Chi 1-38
  39. 5.1 Hàm băm MD5 (128-bit, 264-bit) Bước 1: nhồi dữ liệu • Nhồi thêm các bits sao cho dữ liệu có độ dài l ≡ 448 mod 512 hay l = n * 512 + 448 (n,l nguyên) • Luôn thực hiện nhồi dữ liệu ngay cả khi dữ liệu ban đầu có độ dài mong muốn. • Ví dụ, dữ liệu có độ dài 448 được nhồi thêm 512 bits để được độ dài 960 bits. • Số lượng bit nhồi thêm nằm trong khoảng 1 đến 512 • Các bit được nhồi gồm 1 bit “1” và các bit 0 theo sau Trần Thị Kim Chi 1-39
  40. 5.1 Hàm băm MD5 (128-bit, 264-bit) Bước 2: thêm vào độ dài • Độ dài của khối dữ liệu ban đầu được biểu diễn dưới dạng nhị phân 64-bit và được thêm vào cuối chuỗi nhị phân kết quả của bước 1 • Nếu độ dài của khối dữ liệu ban đầu > 264, chỉ 64 bits thấp được sử dụng, nghĩa là giá trị được thêm vào bằng K mod 264 • Kết quả có được từ 2 bước đầu là một khối dữ liệu có độ dài là bội số của 512. Khối dữ liệu được biểu diễn: • Bằng một d.y L khối 512-bit Y0, Y1, , YL-1 • Bằng một d.y N từ (word) 32-bit M0, M1, MN-1. Vậy N = L x 16 (32 x 16) = 512 Trần Thị Kim Chi 1-40
  41. 5.1 Hàm băm MD5 (128-bit, 264-bit) Bước 3: khởi tạo bộ đệm MD (MD buffer) • Một bộ đệm 128-bit được dùng lưu trữ các giá trị bămtrung gian và kết quả. Bộ đệm được biểu diễn bằng 4 thanh ghi 32-bit với các giá trị khởi tạo ở dạng little-endian (byte có trọng số nhỏ nhất trong từ nằm ở địa chỉ thấp nhất) như sau: • A = 67 45 23 01 • B = EF CD AB 89 • C = 98 BA DC FE • D = 10 32 54 76 • Các giá trị này tương đương với các từ 32-bit sau: • A = 01 23 45 67 • B = 89 AB CD EF • C = FE DC BA 98 • D = 76 54 32 10 Trần Thị Kim Chi 1-41
  42. 5.1 Hàm băm MD5 (128-bit, 264-bit) Bước 4: xử lý các khối dữ liệu 512-bit • Trọng tâm của giải thuật là hàm nén (compression function) gồm 4 “vòng” xử lý. Các vòng này có cấu trúc giống nhau nhưng sử dụng các hàm luận lý khác nhau gồm F, G, H và I • F(X,Y,Z) = X ˄ Y ˅ ̚ X ˄ Z • G(X,Y,Z) = X ˄ Z ˅ Y ˄ ̚ Z • H(X,Y,Z) = X xor Y xor Z • I(X,Y,Z) = Y xor (X ˅ ̚ Z) • Mảng 64 phần tử được tính theo công thức: T[i] = 232 x abs(sin(i)), i được tính theo radian. • Kết quả của 4 v.ng được cộng (theo modulo 232 với đầu vào CVq để tạo Trần Thị Kim Chi 1-42 CVq+1
  43. 5.1 Hàm băm MD5 (128-bit, 264-bit) Các giá trị trong bảng T Trần Thị Kim Chi 1-43
  44. 5.1 Hàm băm MD5 (128-bit, 264-bit) Bước 5: Xuất kết quả • Sau khi xử l. hết L khối 512-bit, đầu ra của lần xử l. thứ L là giá trị băm 128 bits. • Giải thuật MD5 được tóm tắt như sau: • CV0 = IV • CVq+1 = SUM32[CVq,RFI(Yq,RFH(Yq,RFG(Yq,RFF(Yq,CVq))))] • MD = CVL-1 • Với các tham số • IV: bộ đệm gồm 4 thanh ghi ABCD • Yq: khối dữ liệu thứ q gồm 512 bits • L: số khối 512-bit sau khi nhồi dữ liệu • CVq: đầu ra của khối thứ q sau khi áp dụng hàm nén • RFx: hàm luận l. sử dụng trong các “v.ng” (F,G,H,I) • MD: message digest – giá trị băm • SUM32: cộng modulo 232 Trần Thị Kim Chi 1-44
  45. 5.1 Hàm băm MD5 nén (128-bit, 232-bit) Trần Thị Kim Chi 1-45
  46. MD5 Overview 2. Append length (64bits) 1. Append padding bits (to 448 mod 512) 3. Initialize MD buffer Word A = 01 23 45 67 Word B = 89 AB CD EF Word C = FE DC BA 98 Word D = 76 54 32 10 Trần Thị Kim Chi 1-46
  47. Hash Algorithm Design – MD5 16 steps X[k] = M [q*16+k] (32 bit) Constructed from sine function Trần Thị Kim Chi 1-47
  48. The ith 32-bit word in matrix T, constructed from the sine function M [q*16+k] = the kth 32-bit word from the qth 512-bit block of the msg Single step Trần Thị Kim Chi 1-48
  49. 5. Hàm băm MD5, SHA1 • SHA (Secure Hash Algorithm) • Được phát triển bởi NIST 1993 (SHA-0) • 1995: SHA-1 - Chính phủ Mỹ chọn làm chuẩn quốc gia. Kích thước giá trị băm 160-bit • Hiện nay còn có SHA-224, SHA-256, SHA-384, SHA-512 Trần Thị Kim Chi 1-49
  50. 5.2 Hàm băm SHA-1 (160-bit, 264-bit) • Sơ đồ tổng thể của SHA1 cũng giống như MD5, kích thước của giá trị băm tại mỗi bước là 160-bit. H0 – 160-bit, chia thành 5 từ 32-bit, ký hiệu a,b,c,d,e – hằng số a=67452301; b=efcdab89; c=98badcfe; d=10325476; e=c3d2e1f0 Trần Thị Kim Chi 1-50
  51. 5.2 Hàm băm SHA-1 (160-bit, 264-bit) • Đầu vào: thông điệp với độ dài tối đa 264 bits • Đầu ra: giá trị băm (message digest) có độ dài 160 bits • Giải thuật gồm 5 bước thao tác trên các khối 512 bits Trần Thị Kim Chi 1-51
  52. 5.2 Hàm băm SHA-1 (160-bit, 264-bit) Bước 1: nhồi thêm dữ liệu • Thông điệp được nhồi thêm các bits sao cho độ dài l ≡ 448 mod 512 hay l = n * 512 + 448 (n,l nguyên) • Thông điệp luôn luôn được nhồi thêm dữ liệu • Số bits nhồi thêm nằm trong khoảng 1 đến 512 • Phần dữ liệu nhồi thêm bao gồm một bit 1 và theo sau là các bit 0 Trần Thị Kim Chi 1-52
  53. 5.2 Hàm băm SHA-1 (160-bit, 264-bit) Bước 2: thêm vào độ dài • Độ dài của khối dữ liệu ban đầu được biểu diễn dưới dạng nhị phân 64-bit và được thêm vào cuối chuỗi nhị phân kết quả của bước 1 • Độ dài được biểu diễn dưới dạng nhị phân 64-bit không dấu • Kết quả có được từ 2 bước đầu là một khối dữ liệu có độ dài là bội số của 512. Khối dữ liệu được biểu diễn: • Bằng một d.y L khối 512-bit Y0, Y1, , YL-1 • Bằng một d.y N từ (word) 32-bit M0, M1, MN-1. Vậy N = L x 16 Trần Thị Kim Chi 1-53
  54. 5.2 Hàm băm SHA-1 (160-bit, 264-bit) Bước 3: khởi tạo bộ đệm MD (MD buffer) • Một bộ đệm 160-bit được dùng lưu trữ các giá trị băm trung gian và kết quả. Bộ đệm được biểu diễn bằng 5 thanh ghi 32-bit với các giá trị khởi tạo ở dạng big-endian (byte có trọng số lớn nhất trong từ nằm ở địa chỉ thấp nhất) như sau: • A = 01 23 45 67 • B = 89 AB CD EF • C = FE DC BA 98 • D = 76 54 32 10 • E = C3 D2 E1 F0 • Các giá trị này tương đương với các từ 32-bit sau: • A = 01 23 45 67 • B = 89 AB CD EF • C = FE DC BA 98 • D = 76 54 32 10 • E = C3 D2 E1 F0 Trần Thị Kim Chi 1-54
  55. 5.2 Hàm băm SHA-1 (160-bit, 264-bit) Bước 4: xử lý các khối dữ liệu512 -bit • Trọng tâm của giải thuật bao gồm 4 vòng lặp thực hiện tất cả 80 bước. 4 vòng lặp có cấu trúc như nhau, chỉ khác nhau ở các hàm logic f1, f2, f3, f4 • Mỗi vòng có đầu vào gồm khối 512-bit hiện thời và một bộ đệm 160-bit ABCDE. Các thao tác sẽ cập nhật giá trị bộ đệm Mỗi bước sử dụng một hằng số Kt (0 ≤ t ≤79) • Kt = 5A827999 (0 ≤ t ≤ 19) • Kt = 6ED9EBA1 (20 ≤ t ≤ 39) • Kt = 8F1BBCDC (40 ≤ t ≤ 59) • Kt = CA62C1D6 (60 ≤ t ≤ 79) • Đầu ra của 4 v.ng (bước 80) được cộng với đầu ra của bước CVq để tạo ra CVq+Trần Thị1 Kim Chi 1-55
  56. 5.2 Hàm băm SHA-1 (160-bit, 264-bit) Bước 5: xuất kết quả • Sau khi thao tác trên toàn bộ L blocks. Kết quả của khối thứ L là bảng băm 160-bit • Giải thuật được tóm tắt như sau: • CV0 = IV • CVq+1 = SUM32(CVq, ABCDEq) • MD = CVL • Với • IV = giá trị khởi tạo của bộ đệm ABCDE • ABCDEq = đầu ra của hàm nén trên khối thứ q • L = số khối 512-bit của thông điệp • SUM32 = phép cộng modulo232 trên từng từ (32 bits) của đầu vào • MD = giá trị băm Trần Thị Kim Chi 1-56
  57. 5.2 Hàm băm SHA-1 (160-bit, 264-bit) Bước 5: xuất kết quả • Sau khi thao tác trên toàn bộ L blocks. Kết quả của khối thứ L là bảng băm 160-bit • Giải thuật được tóm tắt như sau: • CV0 = IV • CVq+1 = SUM32(CVq, ABCDEq) • MD = CVL • Với • IV = giá trị khởi tạo của bộ đệm ABCDE • ABCDEq = đầu ra của hàm nén trên khối thứ q • L = số khối 512-bit của thông điệp • SUM32 = phép cộng modulo232 trên từng từ (32 bits) của đầu vào • MD = giá trị băm Trần Thị Kim Chi 1-57
  58. 5.2 Hàm băm SHA-1 – Hàm Nén Trần Thị Kim Chi 1-58
  59. 5.2 Hàm băm SHA-1 – Hàm Nén Trần Thị Kim Chi 1-59
  60. So sánh giữa MD5 và SHA-1 • Khả năng chống lại tấn công brute-force: • Để tạo ra thông điệp có giá trị băm cho trước, cần 2128 thao tác với MD5 và 2160 với SHA-1 • Để tìm 2 thông điệp có cùng giá trị băm, cần2 64 thao tác với MD5 và 280 với SHA-1 • Khả năng chống lại thám mã: cả 2 đều có cấu trúc tốt • Tốc độ: • Cả hai dựa trên phép toán32 bit, thực hiện tốt trên các kiến trúc 32 bit • SHA-1 thực hiện nhiều hơn 16 bước và thao tác trên thanh ghi 160 bit nên tốt độ thực hiện chậm hơn • Tính đơn giản: cả hai đều được mô tả đơn giản và dễ dàng cài đặt trên phần cứng và phần mềm Trần Thị Kim Chi 1-60
  61. Một số ứng dụng MD5 và SHA-1 1. Lưu trữ mật khẩu Trần Thị Kim Chi 1-61
  62. Một số ứng dụng MD5 và SHA-1 1. Lưu trữ mật khẩu Trần Thị Kim Chi 1-62
  63. Một số ứng dụng MD5 và SHA-1 1. Lưu trữ mật khẩu Trần Thị Kim Chi 1-63
  64. Một số ứng dụng MD5 và SHA-1 2. Đấu giá trực tuyến (Trang 94) Trần Thị Kim Chi 1-64
  65. Một số ứng dụng MD5 và SHA-1 2. Đấu giá trực tuyến (Trang 94): Giả sử Alice, Bob và Trudy cùng tham gia đấu giá, họ sẽ cung cấp mức giá của mình cho trọng tài. • Giả sử mức giá của Alice là 100, mức giá của Bob là 110, nếu Trudy thông đồng với trọng tài và biết được giá của Alice và Bob, Trudy có thể đưa ra mức giá 111 và thắng thầu. • Có thể tránh những hình thức lừa đảo như vậy bằng cách sử dụng hàm băm. Từ mức giá bỏ thầu, Alice và Bob sẽ tính các giá trị băm tương ứng và chỉ cung cấp cho trọng tài các giá trị băm này. • Vì hàm băm là một chiều, nếu trọng tài và Trudy bắt tay nhau thì cũng • không thể biết được giá của Alice và Bob là bao nhiêu. Đến khi công bố, Alice, Bob và Trudy sẽ đưa ra mức giá của mình. Trọng tài sẽ tính các giá trị băm tương ứng và so sánh với các giá trị băm đã nộp để bảo đảm rằng mức giá mà Alice, Bob và Trudy là đúng với ý định ban đầu của họ. Vì tính chống trùng của hàm băm nên Alice, Bob và Trudy không thể thay đổi giá so với Trầný địnhThị Kim Chiban đầu. 1-65
  66. Một số ứng dụng MD5 và SHA-1 2. DownLoad File Trần Thị Kim Chi 1-66
  67. Câu hỏi và bài tập 1. Để bảo đảm tính chứng thực dùng mã hóa đối xứng hay mã hóa khóa công khai, bản rõ phải có tính chất gì? Tại sao? 2. Nếu bản rõ là một dãy bít ngẫu nhiên, cần làm gì để bản rõ trở thành có cấu trúc? 3. Sử dụng MAC để chứng thực có ưu điểm gì so với chứng thực bằng mã hóa đối xứng? 4. Về mặt lý thuyết, giá trị Hash có thể trùng không? Vậy tại sao nói giá trị Hash có thể xem là “dấu vân tay của thông điệp”? 5. Tại sao để chứng thực một thông điệp M, người ta chỉ cần mã hóa khóa công khai giá trị Hash của M là đủ? Thực hiện như vậy có lợi ích gì hơn so với cách thức mã hóa toàn bộ M 6. Tìm hiểu phương pháp sử dụng hàm băm MD5 và SHA trong thư viện .NET, viết chương trình mã hóa password lưu trữ và kiểm tra password. Trần Thị Kim Chi 1-67
  68. Câu hỏi và bài tập 1. Hãy xem xét hàm hash sau. Thông điệp có dạng là một dãy các số thập phân M = (a1, a2, , an). Hàm hash được tính bằng công thức: 2. Hàm hash trên có thỏa mãn các tính chất của một hàm hash như đã nêu trong phần 5.2 hay không? Giải thích lý do. 3. Giả sử Alice và Bob muốn tung đồng xu qua mạng (Alice tung và Bob đoán). Giao thức thực hiện như sau: i. Alice chọn giá trị X=0 hay 1. ii. Alice sinh một khóa K ngẫu nhiên gồm 256 bít iii. Dùng AES, Alice tính Y = E(X||R, K) trong đó R gồm 255 bít bất kỳ iv. Alice gửi Y cho Bob v. Bob đoán Z là 0 hay 1 và gửi Z cho Alice vi. Alice gửi khóa K cho Bob để Bob tính X||R = D(Y, K) vii. Nếu X=Z, Bob đoán trúng. Nếu không Bob đoán sai. Chứng tỏ rằng Alice có thể lừa Bob (chẳng hạn, Alice chọn X=1, thấy Bob đoán Z=1 thì Alice sẽ lừa như thế nào để Bob giải mã Y thì có X=0). Dùng hàm hash,hãy sửa đoạn giao thức trên để Alice không thể lừa được. Trần Thị Kim Chi 1-68