Kỹ thuật lập trình - Tuần 14: Hàm băm (Hash function)

12/1/2016 1 Tuần 14 - Hàm băm (Hash function) Giáo viên: Hà Đại Dương duonghd@mta.edu.vn Kỹ thuật lập trình 12/1/2016 1 Nội dung 1. Giới thiệu 2. Các hàm băm và tính toàn vẹn của dữ liệu 3. Tấn công ngày sinh nhật 4. Trao đổi và thoả thuận khoá 5. Chữ kí số Giới thiệu • Một số khái niệm: – Xác thực mẩu tin liên quan đến các khía cạnh sau khi truyền tin trên mạng • Bảo vệ tính toàn vẹn của mẩu tin: bảo vệ mẩu tin không bị thay đổi hoặc có các biện pháp phát hiện nếu mẩu tin bị thay đổi trên đường truyền. • Kiểm chứng danh tính, nguồn gốc: xem xét mẩu tin có đúng do người xưng tên gửi không hay một kẻ mạo danh nào khác gửi. • Không chối từ bản gốc: trong trường hợp cần thiết, bản thân mẩu tin chứa các thông tin chứng tỏ chỉ có người xưng danh gửi, không một ai khác có thể làm điều đó => Người gửi không thể từ chối hành động gửi, thời gian gửi và nội dung của mẩu tin. 12/1/2016 2 • Các yêu cầu bảo mật khi truyền mẩu tin: – Tìm các biện pháp cần thiết để chống đối lại các hành động phá hoại như sau: • Để lộ bí mật: giữ bí mật nội dung mẩu tin, chỉ cho người có quyền biết. • Thám mã đường truyền: không cho theo dõi hoặc làm trì hoãn việc truyền tin. • Giả mạo: lấy danh nghĩa người khác để gửi tin. • Sửa đổi nội dung: thay đổi, cắt xén, thêm bớt thông tin. • Thay đổi trình tự các gói tin nhỏ của mẩu tin truyền. • Sửa đổi thời gian: làm trì hoãn mẩu tin. • Từ chối gốc: không cho phép người gửi từ chối trách nhiệm của tác giả mẩu tin. • Từ chối đích: không cho phép người nhận phủ định sự tồn tại và đến đích của mẩu tin đã gửi. • Hàm băm (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. • Đặc trưng: – Hàm băm h là hàm một chiều (one-way hash) với các đặc tính: • Với thông điệp đầu vào x thu được bản băm z = h(x) là duy nhất. • Nếu dữ liệu trong thông điệp x thay đổi để thành thông điệp x’ thì h(x’)  h(x) => Hai thông điệp hoàn toàn khác nhau thì giá trị hàm băm cũng khác nhau. • Nội dung của thông điệp gốc không thể bị suy ra từ giá trị hàm băm => Với thông điệp x thì dễ dàng tính được z = h(x), nhưng lại không thể (thực chất là khó) suy ngược lại được x nếu chỉ biết giá trị hàm băm h 12/1/2016 3 • Vai trò hàm băm trong mật mã hiện đại: – Được dùng để xác thực tính nguyên vẹn dữ liệu – Được dùng trong quá trình tạo chữ kí số trong giao dịch điện tử. • Các hàm băm lấy một thông báo đầu vào và tạo một đầu ra được xem như là: – Mã băm (hash code), – Kết quả băm (hash result), – Hoặc giá trị băm (hash value). • Vai trò cơ bản của các hàm băm mật mã là một giá trị băm coi như ảnh đại diện thu gọn, đôi khi gọi là một dấu vết (imprint), vân tay số (digital fingerprint), hoặc tóm lược thông báo (message digest) của một xâu đầu vào, và có thể được dùng như là một định danh duy nhất với xâu đó. • Các hàm băm thường được dùng cho toàn vẹn dữ liệu kết hợp với các lược đồ chữ kí số. • Một lớp các hàm băm riêng được gọi là mã xác thực thông báo (MAC) cho phép xác thực thông báo bằng các kĩ thuật mã đối xứng. Phân loại 12/1/2016 4 Hàm băm và tính toàn vẹn của dữ liệu – Việc sử dụng các hệ mật mã và các sơ đồ chữ ký số, thường là mã hóa và ký số trên từng bit của thông tin, sẽ tỷ lệ với thời gian để mã hóa và dung lượng của thông tin. – Thêm vào đó có thể xảy ra trường hợp: Với nhiều bức thông điệp đầu vào khác nhau, sử dụng hệ mật mã, sơ đồ ký số giống nhau (có thể khác nhau) thì cho ra kết quả bản mã, bản ký số giống nhau (ánh xạ N-1: nhiều – một). Điều này sẽ dẫn đến một số rắc rối về sau cho việc xác thực thông tin. Hàm băm và tính toàn vẹn của dữ liệu – Với các sơ đồ ký số, chỉ cho phép ký các bức thông điệp (thông tin) có kích thước nhỏ và sau khi ký, bản ký số có kích thước gấp đôi bản thông điệp gốc • Ví dụ: với sơ đồ chữ ký chuẩn DSS chỉ ký trên các bức thông điệp có kích thước 160 bit, bản ký số sẽ có kích thước 320 bit. – Trong khi đó trên thực tế, ta cần phải ký các thông điệp có kích thước lớn hơn nhiều, chẳng hạn vài chục MB. Hơn nữa, dữ liệu truyền qua mạng không chỉ là bản thông điệp gốc, mà còn bao gồm cả bản ký số (có dung lượng gấp đôi dung lượng bản thông điệp gốc), để đáp ứng việc xác thực sau khi thông tin đến người nhận. Hàm băm và tính toàn vẹn của dữ liệu • Một cách đơn giản để giải bài toán (với thông điệp có kích thước vài chục MB) này là chia thông điệp thành nhiều đoạn 160 bit, sau đó ký lên các đoạn đó độc lập nhau. Nhưng biện pháp này có một số vấn đề trong việc tạo ra các chữ ký số: – Thứ nhất: với một thông điệp có kích thước a, thì sau khi ký kích thước của chữ ký sẽ là 2a (trong trường hợp sử dụng DSS). – Thứ hai: với các chữ ký “an toàn” thì tốc độ chậm vì chúng dùng nhiều phép tính số học phức tạp như số mũ modulo. – Thứ ba: vấn đề nghiêm trọng hơn đó là kết quả sau khi ký, nội dung của thông điệp có thể bị xáo trộn các đoạn với nhau, hoặc một số đoạn trong chúng có thể bị mất mát, trong khi người nhận cần phải xác minh lại thông điệp. Ta cần phải bảo vệ tính toàn vẹn của thông điệp 12/1/2016 5 Hàm băm và tính toàn vẹn của dữ liệu • Giải pháp cho các vấn đề vướng mắc đến chữ ký số là dùng “hàm băm” để trợ giúp cho việc ký số • Các thuật toán băm với đầu vào là các bức thông điệp có dung lượng, kích thước tùy ý (vài KB đến vài chục MB ) – các bức thông điệp có thể là dạng văn bản, hình ảnh, âm thanh, file ứng dụng v.v - và với các thuật toán băm: MD2, MD4, MD5, SHA cho các bản băm đầu ra có kích thước cố định: 128 bit với dòng MD, 160 bit với SHA1. • Như vậy, bức thông điệp kích thước tùy ý sau khi băm sẽ được thu gọn thành những bản băm – được gọi là các “văn bản đại diện” – có kích thước cố định (128 bit hoặc 160 bit). Hàm băm và tính toàn vẹn của dữ liệu • Với mỗi thông điệp đầu vào chỉ có thể tính ra được một văn bản đại diện – giá trị băm tương ứng – duy nhất • Hai thông điệp khác nhau chắc chắn có hai văn bản đại diện khác nhau. Khi đã có văn bản đại diện duy nhất cho bức thông điệp, áp dụng các sơ đồ chữ ký số ký trên văn bản đại diện đó Hàm băm và tính toàn vẹn của dữ liệu • Giả sử A muốn gửi cho B thông điệp x. A thực hiện các bước sau: – (1) A băm thông điệp x, thu được bản đại diện z = h(x) – có kích thước cố định 128 bit hoặc 160 bit. – (2) A ký số trên bản đại diện z, bằng khóa bí mật của mình, thu được bản ký số y = sig(z). – (3) A gửi (x, y) cho B. 12/1/2016 6 Hàm băm và tính toàn vẹn của dữ liệu • Khi B nhận được (x, y). B thực hiện các bước sau: – (4) B kiểm tra chữ ký số để xác minh xem thông điệp mà mình nhận được có phải được gửi từ A hay không bằng cách giải mã chữ ký số y, bằng khóa công khai của A, được z. – (5) B dùng một thuật toán băm – tương ứng với thuật toán băm mà A dùng – để băm thông điệp x đi kèm, nhận được h(x). – (6) B so sánh 2 giá trị băm z và h(x), nếu giống nhau thì chắc chắn rằng thông điệp x – mà A muốn gửi cho B – còn nguyên vẹn, bên cạnh đó cũng xác thực được người gửi thông tin là ai. Hàm băm và tính toàn vẹn của dữ liệu 12/1/2016 7 Hàm băm và tính toàn vẹn của dữ liệu • Hàm băm trợ giúp cho các sơ đồ ký số nhằm giảm dung lượng của dữ liệu cần thiết để truyền qua mạng – Ví dụ: lúc này chỉ còn bao gồm dung lượng của bức thông điệp gốc và 256 bit (sử dụng MD) hay 320 bit (sử dụng SHA) của bức ký số được ký trên bản đại diện của thông điệp gốc, tương đương với việc giảm thời gian truyền tin qua mạng. • Hàm băm thường kết hợp với chữ ký số để tạo ra một loại chữ ký điện tử vừa an toàn hơn (không thể cắt/dán) vừa có thể dùng để kiểm tra tính toàn vẹn của thông điệp. • Hàm băm được ứng dụng rất mạnh trong vấn đề an toàn thông tin trên đường truyền. Các ứng dụng có sử dụng hàm băm không chỉ đảm bảo về mặt an toàn thông tin, mà còn tạo được lòng tin của người dùng vì họ có thể dễ dàng phát hiện được thông tin của mình có còn toàn vẹn hay không, họ biết rằng thông tin của mình chắc chắn được bí mật với phía các nhà cung cấp. Tấn công ngày sinh nhật – Nghịch lý ngày sinh nhật: • Trong lớp có ít nhất bao nhiêu sinh viên, để xác suất có ít nhất 2 sinh viên trùng ngày sinh nhật là lớn hớn 0.5? • Theo lý thuyết xác suất thống kê gọi số sinh viên ít nhất trong lớp là k, khi đó xác suất q để không có 2 người nào trùng ngày sinh là tỷ số giữa cách chọn k ngày khác nhau trong 365 ngày trên số cách chọn k ngày bất kỳ trong 365 ngày. Vậy: q = Ck365/ 365k • Do đó, xác suất p để có ít nhất 2 người trùng ngày sinh là: p = 1 – q = 1 – Ck365/ 365k Các hàm băm và tính toàn vẹn của dữ liệu • Để p > 0.5 thì k > 22 hay k =23, cụ thể khi đó p = 0.5073 • Khi chưa tính toán chi tiết chúng ta nghĩ là trong lớp phải có ít nhất khoảng 365/2 tức là 184 sinh viên. Nhưng trên thực tế con số đó ít hơn rất nhiều chỉ cần 23 sinh viên, chính vì vậy ta gọi đây là nghịch lý ngày sinh nhật. • Điều đó 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ĩ. 12/1/2016 8 Hoạt động tấn công ngày sinh nhật • Kẻ thám mã tạo ra 2^(m/2) biến thể của mẩu tin đúng mà tất cả đều có bản chất ngữ nghĩa như nhau, với m ở đây là độ dài của bản mã hash • Kẻ thám mã cũng có thể tạo ra 2^ (m/2) biến thể khác nhau của mẩu tin lừa dối,tức là có ngữ nghĩa ngược lại. • Hai tập tin được so sánh với nhau để tìm cặp có cùng bản hash (xác suất >=0.5 dựa vào nghịch lý ngày sinh nhật) • Người dùng ký vào mẩu tin đúng, sau đó bị thay thế bằng mẩu tin giả mà cũng có chữ ký đúng. Trao đổi và thoả thuận khoá Diffie -Hellman • Giả sử A và B muốn liên lạc sử dụng hệ mật khoá bí mật. Để thoả thuận mật khoá K chung cho cả hai bên qua một kênh không an toàn mà không ai khác có thể biết được, A và B có thể dùng thủ tục thoả thuận khoá Diffie -Hellman sau: – (1) Chọn trước một số nguyên tố p thích hợp và một phần tử sinh  của Zp* (2   p – 2) . Các giá trị p và  được công khai. Diffie -Hellman – (2) Thực hiện các bước sau mỗi khi cần có khóa chung: • (a) A chọn một số nguyên bí mật x: 1  x  p – 2 và gửi cho B thông báo x mod p • (b) B chọn một số nguyên bí mật y: 1  y  p – 2 và gửi cho A thông báo y mod p • (c) B thu được x và tính khoá chung k: k = (x)y mod p • (d) A thu được y và tính khoá chung k: k = (y)x mod p 12/1/2016 9 Trao đổi và thoả thuận khoá • Ví dụ: – Giả sử A và B chọn p = 11 và  = 2. z={i, i = 0, , 9 } = {1, 2, 4, 8, 5,10, 9, 7, 3, 6}. Các phần tử sinh của nhóm này bao gồm các phần tử sau:  = 2, 3 = 8, 7 = 7, 9 = 6. – Giả sử A chọn giá trị ngẫu nhiên x = 4 và gửi cho B giá trị 24 mod 11 = 5. – Giả sử B chọn giá trị ngẫu nhiên y = 7 và gửi cho A giá trị 27 mod 11 = 7. – B nhận được 5 và tính khoá chung k = 57 mod 11 = 3 – A nhận được 7 và tính khoá chung k = 74 mod 11 = 3 Chữ kí số – Một ứng dụng điển hình trong máy tính thể hiện một nhu cầu thông thường: lệnh chuyển tiền từ một người này tới một người khác. – Về văn bản đây là một dạng séc đã được “máy tính hóa”. – Giao dịch ở dạng giấy tờ được thực hiện như sau: • Séc là một đối tượng xác định có tư cách giao dịch thương mại • Chữ kí trên séc xác nhận tính xác thực bởi vì chắc chắn rằng chỉ có người kí hợp pháp mới có thể tạo được chữ kí này • Trong trường hợp bất hợp pháp thì sẽ có một bên thứ 3 có thể được gọi vào để phán xét tính xác thực. • Séc bị hủy để nó không được sử dụng lại • Séc giấy không thể thay đổi được, hay hầu hết các kiểu thay đổi đều có thể dễ dàng phát hiện được • Xét mô hình giao dịch trên máy tính: – Tuấn gửi cho ngân hàng của mình một thông báo ủy quyền ngân hàng chuyển 100$ cho Bình. – Ngân hàng của Tuấn phải làm những việc sau: • Kiểm tra và chứng tỏ được rằng thông báo này thực sự tới từ Tuấn (đề phòng sau đó Tuấn không nhận là mình đã gửi nó). • Phải biết chắc rằng toàn bộ thông báo này là của Tuấn và nó đã không bị sửa đổi – Tuấn cũng muốn biết chắc rằng ngân hàng của mình không thể giả mạo những thông báo tương tự. – Cả hai bên đều muốn đảm bảo rằng thông báo đó là thông báo mới, không phải là một thông báo trước đó được sử dụng lại và nó không bị sửa đổi trong khi truyền 12/1/2016 10 • Chữ kí số là một giao thức tạo ra một hiệu quả tương tự như chữ kí thực: – Nó là một dấu hiệu mà chỉ có người gửi mới có thể tạo ra nhưng những người khác có thể nhận thấy được rằng nó là của người gửi. – Giống như chữ kí thực, chữ kí số dùng để xác nhận nội dung thông báo • Chữ kí số phải thỏa mãn điều kiện: – Không thể giả mạo: Nếu P kí thông báo M bằng chữ kí S(P, M) thì không một ai có thể tạo được cặp [M, S(M,P)] – Xác thực: Nếu R nhận được cặp [M, S(M,P)] được coi là của P thì R có thể kiểm tra được rằng chữ kí có thực sự là của P hay không. Chỉ P mới có thể tạo được chữ kí này và chữ kí được “gắn chặt” với M. – Không thể thay đổi: sau khi được phát M không thể bị thay đổi bởi S, R hoặc bởi một kẻ thu trộm nào – Không thể sử dụng lại: Một thông báo trước đó đã được đưa ra sẽ ngay lập tức bị R phát hiện Sơ đồ chữ ký RSA 12/1/2016 11 • Sơ đồ kí số RSA – n = p.q với p, q là các số nguyên tố lớn có kích thước tương đương – Với K = {(n, e, d): d  Zp*, ed  1 mod (n)} – Ta có D = d là khóa bí mật, E = (n, e) là khóa công khai, m là bản tin cần kí • Tạo chữ kí: S = sigD(m) = md mod n • Kiểm tra chữ kí: verE(m, S) = TRUE m  Se mod n • Trường hợp bản tin m không cần bí mật: – A ký bản tin m và gửi cho B. – B kiểm tra chữ ký của A 12/1/2016 12 • Trường hợp bản tin m cần giữ bí mật: – A ký bản tin rõ m để được chữ ký SA. – Sau đó A dùng khoá mã công khai EB của B để lập bản mã M = EB(m, SA) rồi gửi đến B Bài tập 12/1/2016 35 Bài tập về nhà 1. Thử nghiệm 1 số hàm băm cài đặt sẵn như MD5 12/1/2016 36