Đề tài Mã hóa khối chuẩn mã hóa dữ liệu

Việc thực hiện chính xác của một mạng Feistel phụ thuộc vào sự lựa chọn của các tham số và đặc điểm thiết kế sau đây :

o Kích cỡ khối: khối kích thước lớn hơn có nghĩa là bảo mật cao hơn (tất cả những thứ khác bằng nhau), nhưng giảm đi tốc độ mã hóa/giải mã của một thuật toán cho trước.Việc bảo mật cao hơn đạt được bằng cách truyền bá tốt hơn. Theo truyền thống, một kích thước khối 64 bit đã được coi là một sự cân bằng hợp lý và đã được phổ cập trong thiết kế gần mật mã khối. Tuy nhiên, AES mới sử dụng một kích thước khối128-bit.

o Kích thước khóa: kích thước lớn hơn có nghĩa là an ninh tốt hơn, nhưng có thể làm giảm tốc độ mã hóa/giải mã. Việc bảo mật cao hơn đạt được bằng cách chống tấn công brute-force tốt hơn và rắc rối hơn. Kích thước khóa của 64 bit hoặc ít hơn bây giờ nhiều người xem là không đủ,và 128 bit đã trở thành một kích thước thông thường.

o Số vòng: Bản chất của mật mã Feistel là một vòng duy nhất cung cấp bảo mật không đầy đủ nhưng nhiều vòng cung cấp sẽ tăng cường bảo mật hơn.Một kích thước điển hình là 16 vòng.

o Thế hệ thuật toán khóa phụ: phức tạp lớn hơn trong thuật toán này nên dẫn đến khó khăn lớn hơn của phân tích mật mã.

o Hàm vòng: Một lần nữa, phức tạp hơn thường có nghĩa chống phân tích mật mã tốt hơn .Có hai quan tâm khác trong thiết kế của một mã hóa Feistel:

o Tốc độ phần mềm mã hóa/giải mã: Trong nhiều trường hợp, mã hóa được nhúng trong các ứng dụng hoặc các chức năng tiện ích theo cách như vậy là để ngăn cản một thực hiện phần cứng. Theo đó, tốc độ thực hiện của thuật toán sẽ trở thành một mối quan tâm.

o Dễ dàng trong việc phân tích: Mặc dù chúng ta muốn làm cho thuật toán của chúng ta là khó khăn nhất có thể để phân tích mật mã, có lợi ích rất lớn trong việc đưa ra các thuật toán dễ dàng để phân tích. Đó là, nếu thuật toán có thể được giải thích ngắn gọn và rõ ràng, nó được dễ dàng hơn để phân tích rằng thuật toán để giảm rủi ro và do đó chống phân tích mật mã phát triển một mức độ cao hơn để đảm bảo sức mạnh của nó.DES,ví dụ, không có một chức năng dễ dàng dễ dàng phân tích.

 

docx46 trang | Chia sẻ: netpro | Lượt xem: 4772 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu Đề tài Mã hóa khối chuẩn mã hóa dữ liệu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ghép các LDi và RDi. Bây giờ chúng ta muốn cho thấy rằng kết quả của vòng đầu tiên của quá trình giải mã bằng một hoán đổi 32-bit của đầu vào đến vòng thứ mười sáu của quá trình mã hóa.Trước tiên, hãy xem xét quá trình mã hóa. Chúng ta thấy rằng: LE16 = RE15 RE16 = LE15 x F(RE15, K16) Về phía giải mã LD1 = RD0 = LE16 = RE15 RD1 = LD0 x F(RD0, K16) = RE16 x F(RE15, K16) = [LE15 x F(RE15, K16)] x F(RE15, K16) XOR có các thuộc tính sau đây: [A x B] x C = A x [B x C] D x D = 0 E x 0 = E Vì vậy chúng ta có LD1= RE15 và RD1 = LE15. Do đó, đầu ra của vòng đầu tiên của quá trình giải mã là LE15 | RE15, trong đó là hoán đổi 32-bit của đầu vào đến vòng thứ mười sáu của mật mã.Cách thức này nắm giữ tất cả các cách thông qua 16 lần lặp lại, như vậy có thể dễ dàng hiển thị. Chúng ta có thể bỏ quá trình này một cách chung chung. Đối với các lần lặp thứ i của thuật toán mã hóa, LEi = REi-1 REi = LEi-1 x F(REi-1, Ki) Sắp xếp lại các luật ta có REi-1 = LEi LEi-1 = REi x F(REi-1, Ki2 = REi x F(LEi, Ki) Vì vậy, chúng tôi đã mô tả các đầu vào cho các lần lặp thứ i là một chức năng của các đầu ra, và những phương trình này xác nhận các nhiệm vụ được hiển thị ở phía bên phải của Hình 3.3 Cuối cùng, chúng ta thấy rằng kết quả của vòng cuối của quá trình giải mã được RE0 ||LE0. Một trao đổi 32-bit phục hồi các bản rõ ban đầu, chứng tỏ tính hợp lệ của quá trình giải mã Feistel. Lưu ý rằng các dẫn xuất không yêu cầu F là một hàm đảo ngược.Để thấy điều này, có một trường hợp hạn chế, trong đó F tạo ra một đầu ra không đổi không phụ thuộc vào giá trị của hai đối số của nó.Các phương trình vẫn giữ nguyên. 3.2 Chuẩn Mã Hóa Dữ Liệu Các chương trình mã hóa được sử dụng rộng rãi nhất là dựa trên các chuẩn mã hóa dữ liệu (DES) được thông qua vào năm 1977 của Cục Tiêu chuẩn Quốc gia,nay là Viện Tiêu Chuẩn và Công nghệ (NIST),như là chuẩn xử lý thông tin liên bang 46 (FIPS PUB46). Các thuật toán tự này được gọi là các thuật toán mã hóa dữ liệu (DEA). [6] Đối với DES, dữ liệu được mã hóa trong khối 64-bit bằng cách sử dụng một khóa 56-bit.Thuật toán chuyển đổi 64-bit đầu vào trong một loạt các  bước vào một đầu ra 64-bit. Các bước tương tự, với cùng một khóa, được sử dụng để đảo ngược những mã hóa. [6]Thuật ngữ này có hơi khó hiểu. Cho đến gần đây, các từ ngữ DES và DEA có thể được sử dụng thay thế cho nhau. Tuy nhiên, ấn bản mới nhất của các tài liệu DES bao gồm một đặc điểm kỹ thuật của DEA mô tả ở đây cộng thêm ba lần DEA (TDEA) được mô tả trong Chương 6. Cả DEA và TDEA là một phần của Chuẩn Mã hóa Dữ Liệu. Hơn nữa, cho đến khi việc thông qua gần đây của các thuật ngữ chính thức TDEA,thuật toán DEA 3 lớp thường gọi là ba DES và viết là 3DES. Để tiện lợi, chúng ta sử dụng thuật ngữ 3DES. DES được sử dụng rộng rãi.Nó cũng là chủ đề của nhiều tranh cãi liên quan đến các vấn đề an toàn của DES. Để đánh giá đúng bản chất của tranh cãi này, chúng ta hãy nhanh chóng xem xét lại lịch sử của DES. Trong cuối những năm 1960, IBM thiết lập một dự án nghiên cứu  mật mã máy tính dẫn dắt bởi Horst Feistel.Dự án được ký kết vào năm 1971 với việc phát triển một thuật toán với các tên gọi Lucifer [FEIS73],được bán cho Lloyd của London để sử dụng trong hệ thống phân phát tiền mặt, cũng được phát triển bởi IBM. Lucifer là một mã hóa khối Feistel hoạt động trên các khối 64 bit, bằng cách sử dụng một khóa kích thước 128 bit. Bởi vì các kết quả đầy hứa hẹn sản xuất bởi các dự án Lucifer, IBM bắt tay vào một nỗ lực để phát triển có sản phẩm mã hóa với thị trường thương mại lý tưởng có thể được thực hiện trên một chip duy nhất. Nỗ lực này đã được lãnh đạo bởi Walter Tuchman và Carl Meyer,và nó không chỉ liên quan đến các nhà nghiên cứu của IBM mà còn có các tư vấn bên ngoài và tư vấn kỹ thuật của NSA. Kết quả của nỗ lực này là có phiên bản cải tiến của Lucifer có khả năng chống thám mã,nhưng đã có một kích thước giảm  khóa là 56 bit, để vừa trên có chip duy nhất. Năm 1973,Cục Tiêu chuẩn Quốc gia (NBS) đã đưa ra một yêu cầu đề xuất cho tiêu chuẩn mã hóa quốc gia. IBM đã đưa ra kết quả của dự án Tuchman-Meyer.Cho đến nay đây là thuật toán tốt nhất được đề xuất và đã được thông qua vào năm 1977 như là Chuẩn Mã hóa Dữ liệu. Trước khi chấp nhận nó như là một chuẩn, các đề xuất của DES đã bị chỉ trích dữ dội, mà vẫn không hề giảm bớt cho đến ngày nay.Hai lĩnh vực thu hút  của các nhà phê bình.Thứ nhất, chiều dài khóa trong thuật toán Lucifer gốc của IBM là 128 bit nhưng mà của hệ thống đề xuất là chỉ 56 bit, một sự cắt giảm rất lớn trong kích thước khóa của 72bit.Các nhà phê bình lo ngại rằng chiều dài khóa quá ngắn để chống lại các cuộc tấn công brute-force. Lĩnh vực thứ hai đáng quan tâm là các tiêu chuẩn thiết kế cho các cấu trúc bên trong của DES, các S-box, đã được phân loại.Vì vậy,người dùng có thể không được đảm bảo rằng các cấu trúc bên trong của DES được tự do ẩn đi bất kỳ điểm yếu nào mà sẽ cho phép NSA giải mã thông điệp mà không có lợi cho khoá. Các sự kiện tiếp theo, đặc biệt là công việc gần đây về phân tích mật mã khác biệt, dường như để chỉ ra DES có một cấu trúc rất mạnh bên trong.Ngoài ra, theo đại biểu IBM, những thay đổi chỉ được thực hiện để đề nghị được thay đổi cho các S-box, được đề xuất bởi NSA, loại bỏ các lỗ hổng được xác định trong quá trình quá trình đánh giá. Dù tác dụng trong trường hợp này, DES vẫn phát triển và được dùng rộng rãi, đặc biệt là trong các ứng dụng tài chính.Năm 1994, NIST DES tái khẳng định sử dụng của liên bang cho 5 năm khác; NIST khuyến cáo sử dụng DES cho các ứng dụng khác hơn là bảo vệ thông tin mật.Năm 1999,NIST đã ban hành phiên bản mới các tiêu chuẩn của nó (FIPS PUB 46-3) mà chỉ ra rằng DES chỉ nên được sử dụng cho các hệ thống cũ và  DES 3 lớp (mà trong bản chất liên quan đến việc lặp đi lặp lại các thuật toán DES ba lớp trên các bản gốc bằng cách sử dụng hai hay ba khóa khác nhau để tạo ra bản mã) được sử dụng.Chúng ta nghiên cứu DES 3 lớp trong chương 6.Vì các thuật toán mã hóa và giải mã cơ bản là như nhau cho DES và DES 3 lớp, nó vẫn quan trọng để hiểu các thuật toán mã hóa DES. Mã Hóa DES Đề án tổng thể mã hóa DES được minh họa trong hình 3.4. Như với bất kỳ chương trình mã hóa nào,có hai đầu vào cho các chức năng mã hóa: những bản gốc sẽ được mã hóa và khóa.Trong trường hợp này, các bản gốc phải có độ dài 64 bits  và khoá có chiều dài 56 bit.[7] [7] Trên thực tế, các hàm dự kiến có một khóa 64-bit như đầu vào. Tuy nhiên, chỉ có 56 của các bit này được sử dụng; ​​ 8 bit khác có thể được sử dụng làm bit chẵn lẻ hay đơn giản là đặt tùy tiện. Hình 3.4.  Mô tả toàn bộ thuật toán mã hóa DES Nhìn bên trái bên hình vẽ, chúng ta có thể thấy rằng quá trình xử lý của văn bản gốc thu được trong ba giai đoạn. Trước tiên, văn bản gốc 64 bit đi qua phép hoán vị ban đầu ( IP ) đã được sắp đặt lại bit để tạo ra đầu vào thay đổi trật tự. Kèm theo đó là giai đoạn bao gồm 16 vòng của hàm tương tự, bao gồm cả phép hoán vị lẫn hàm thay thế.Đầu ra của vòng cuối cùng ( thứ mười sáu ) bao gồm 64 bit đó là hàm của đầu vào văn bản gốc và khóa.Nữa bên trái và nửa bên phải của đầu ra được thay đổi để tạo ra đầu vào trước đó. Cuối cùng, đầu vào trước đó được đi qua phép hoán vị ( IP-1 ) đó là điều ngược lại của chức năng phép hoán vị ban đầu, để tạo ra văn bản mã hoá 64 bit. Ngoại trừ phép hoán vị ban đầu và cuối cùng, DES có cấu trúc chính xác của mật mã Feistel, như đã nêu trong hình 3.2. Phần bên phải của hình 3.4 cho thấy cách thức mà các khóa 56-bit được sử dụng. Ban đầu, khóa được truyền qua một hàm hoán vị.Sau đó,với mỗi trong số 16 vòng,một khóa con (Ki) được tạo ra bởi sự kết hợp của một sự thay đổi vòng tròn trái và một hoán vị. Các hàm hoán vị là như nhau cho mỗi vòng,nhưng một khóa phụ khác được tạo ra vì những thay đổi lập lại của các bit khóa. Hoán Vị Khởi Tạo Các hoán vị khởi tạo và các nghịch đảo của nó được xác định bởi các bảng, như trong bảng 3.2a và 3.2b,tương ứng. Các bảng sẽ được giải thích như sau.Các đầu vào cho một bảng gồm 64 bit được đánh số từ 1 đến 64. 64 mục trong bảng hoán vị có chứa một hoán vị của các số từ 1 đến 64. Mỗi mục trong bảng hoán vị cho thấy vị trí của một số bit đầu vào trong sản xuất, mà còn bao gồm 64 bit. Bảng 3.2. Bảng hoán vị cho DES Để thấy rằng hai hàm hoán vị có thực sự là nghịch đảo của nhau,hãy xem xét  những điều sau đây 64-bit đầu vào M: Chỗ Mi là một chữ số nhị phân. Sau đó, hoán vị X = IP (M) như sau: Nếu sau đó chúng ta lấy các hoán vị nghịch đảo Y = IP-1 (X) = IP-1 (IP (M), có thể thấy rằng vị trí ban đầu của các bit được phục hồi. Thông tin chi tiết của vòng đơn Hình 3.5 cho thấy cấu trúc bên trong của một vòng đơn. Một lần nữa,bắt đầu bởi tập trung ở phía bên tay trái của biểu đồ. Các nửa trái và phải của mỗi giá trị trung gian 64-bit đang được coi là riêng biệt với số lượng 32-bit, được gán nhãn L (trái) R(phải). Như trong bất kỳ mã hóa Feistel cổ điển, việc xử lý tổng thể ở mỗi vòng có thể được tóm tắt trong các công thức sau đây: Li = Ri-1 Ri = Li-1 x F(Ri-1, Ki) Hình 3.5. Vòng đơn của thuật toán DES Khóa Ki của vòng là 48 bit. Đầu vào R là 32 bit. Đầu vào R đầu tiên mở rộng đến 48 bit bằng cách sử dụng bảng định nghĩa phép hoán vị cộng mở rộng liên quan sẽ sao chép của 16 trong số R bit ( bảng 3.2 c ).Kết quả 48 bit được XOR với Ki.Kết quả 48 bit này qua hàm thay thế tạo ra đầu ra 32 bit, được hoán đổi theo định nghĩa của bảng 3.2 d Vai trò của các S-box trong hàm F được minh họa trong hình 3.6. Phép thế bao gồm một bộ 8 S-box, mỗi S-box nhận 6 bit ở đầu vào và tạo ra 4 bit ở đầu ra. Những biến đổi được xác định trong Bảng 3,3 được hiểu như sau: Các bit đầu tiên và cuối cùng của đầu vào ô Si là một số nhị phân 2-bit để chọn một trong bốn thay thế được xác định bởi bốn dòng trong bảng cho các Si.Bốn bit giữa chọn một trong mười sáu cột. Giá trị thập phân ở các ô được lựa chọn bởi các hàng và cột sau đó được chuyển đổi thành 4-bit đại diện của nó để tạo đầu ra. Ví dụ, trong S1  cho đầu vào 011001, hàng này là 01(dòng 1) và cột là 1100 (cột 12).Giá trị trong hàng 1,cột12 là 9, vì thế đầu ra là 1001. Hình 3.6. Cách tính của F (R, K) Bảng 3.3 Cách xác định các S-box của DES  Mỗi hàng của một S-box xác định một phép thế  đảo ngược chung.Hình 3.1 có thể hữu ích trong việc tìm hiểu bản đồ.Hình này cho thấy sự thay thế cho các hàng 0 trong S-box1. Các hoạt động của S-box là lời giải thích có ích hơn.Bỏ qua cho các thời điểm tham gia của khóa (Ki). Nếu bạn kiểm tra bảng mở rộng, bạn sẽ thấy rằng 32 bit đầu vào được chia thành các nhóm 4 bit, và sau đó trở thành nhóm của 6 bit bằng cách lấy các bit bên ngoài từ hai nhóm liền kề.Ví dụ, nếu một phần của từ đầu vào là : ... efgh ijkl mnop ... Biến đổi thành : ... defghi hijklm lmnopq ... Hai bit bên ngoài của mỗi nhóm chọn một trong bốn sự thay thế có thể (một hàng của một S-box).Sau đó một giá trị 4-bit đầu ra thay thế cho đầu vào 4-bit riêng (bốn bit giữa đầu vào).Đầu ra 32-bit từ tám S-box sau đó được hoán đổi, do đó trên vòng tiếp theo đầu ra từ mỗi S-box ngay lập tức ảnh hưởng như nhiều bit có thể. Quá trình tạo khóa Quay trở lại với hình 3.4 và 3.5, chúng ta thấy rằng một khóa 64-bit được sử dụng làm đầu vào cho thuật toán. Các bit của khoá được đánh số từ 1 đến 64; mỗi bit thứ tám là bỏ qua,như đã nêu trong bảng 3.4a.Các khóa đầu tiên được hoán vị trong một bảng có gắn nhãn Permuted Choice One (bảng 3.4d).Kết quả là khóa 56-bit sau đó coi như là hai khối 28-bit, có nhãn C0 và D0.Tại mỗi vòng Ci-1 và Di -1 sẽ bị dịch trái theo vòng riêng biệt, hoặc luân chuyển, trong 1 hoặc 2 bit,như những điều chỉnh của Bảng 3.4d.Những giá trị  thay đổi được dùng như là đầu vào cho  các vòng tiếp theo.Chúng cũng được dùng như là đầu vào cho Permuted Choice Two (Bảng 3.4c), trong đó tạo ra một đầu ra 48-bit mà phục vụ như đầu vào cho hàm F (Ri-1, Ki). Bảng 3.4 Bảng biểu tính toán DES Giải mã DES Như với bất kỳ mã hóa Feistel, giải mã sử dụng thuật toán tương tự như mã hóa, ngoại trừ việc áp dụng các khóa con được đảo ngược. Hiệu ứng tuyết lở Một thuộc tính mong muốn của bất kỳ thuật toán mã hóa nào đó là một thay đổi nhỏ trong văn bản gốc hoặc khóa sẽ tạo ra một thay đổi đáng kể trong văn bản mã hóa. Đặc biệt, thay đổi một bit của văn bản gốc hoặc  một bit của khóa sẽ tạo ra sự  thay đổi nhiều bit trong văn bản mã hóa.Nếu sự thay đổi rất nhỏ, điều này có thể tạo ra một cách để giảm kích thước của không gian để tìm kiếm văn bản gốc hoặc khóa. DES thể hiện rõ hiệu ứng tuyết lở. Bảng 3.5 cho thấy một số kết quả được lấy từ [KONH81]. Trong bảng 3.5A, hai văn bản gốc khác nhau với một bit đã được sử dụng: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 Với khóa là : 0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010 Bảng 3.5 Hiệu ứng tuyết lở trong DES Bảng 3.5A cho thấy, chỉ sau ba vòng, có 21 bit khác nhau giữa hai khối.Sau khi hoàn thành, hai vẳn bản gốc  khác nhau trong 34 vị trí bit. Bảng 3.5b cho thấy một thử nghiệm tương tự, trong đó một văn bản gốc duy nhất là đầu vào: 01101000 10000101 00101111 01111010 00010011 01110110 11101011 10100100 Với 2 khóa khác nhau chỉ bởi vị trí của 1 bit: 1110010 1111011 1101111 0011000 0011101 0000100 0110001 11011100 0110010 1111011 1101111 0011000 0011101 0000100 0110001 11011100 Một lần nữa,kết quả cho thấy rằng khoảng một nửa số các bit trong các bản mã khác nhau và các hiệu ứng tuyết lở được thể hiện chỉ sau một vài vòng. 3.3. Sức mạnh của DES Kể từ khi DES được thông qua như là một chuẩn của liên bang, còn sót lại mối quan tâm về mức độ an ninh được cung cấp bởi DES.Những mối quan tâm,được chia thành hai hướng: kích thước khóa và bản chất của thuật toán. Cách sử dụng khóa 56 bit Với chiều dài khóa là 56 bit, có thể có 256 khóa, xấp xỉ 7,2 x 1016. Như vậy,  một cuộc tấn công brute-force dường như là không thực tế.Giả sử, trung bình, một nửa không gian khóa đã được tìm kiếm, một máy tính thực hiện một mã hóa DES mỗi micro giây sẽ mất hơn một ngàn năm (xem bảng 2.2) để phá vỡ mật mã. Tuy nhiên, giả thiết của một mã hóa cho mỗi micro giây là quá bảo thủ. Cách đây gần năm 1977, Diffie và Hellman mặc nhiên công nhận rằng công nghệ tồn tại để xây dựng một máy song song với 1 triệu thiết bị mã hóa, mỗi máy trong đó có thể thực hiện một mã hóa cho mỗi micro giây [DIFF77]. Điều này sẽ mang lại thời gian tìm kiếm trung bình xuống khoảng 10 giờ. Các tác giả ước tính rằng chi phí sẽ là khoảng 20 triệu USD vào năm 1977. Cuối cùng  DES đã bị chứng minh là không an toàn vào tháng 7 năm 1998, khi  Electronic Frontier Foundation (EFF) đã thông báo rằng nó đã bị bẻ khóa, một mật mã DES sử dụng một mục đích đặc biệt đó là máy "DES cracker" được xây dựng với chi phí ít hơn 250,000 $.Vụ tấn công tốn ít hơn ba ngày. Các EFF đã xuất bản một mô tả chi tiết của máy, cho phép người khác để xây dựng riêng cách bẻ khóa của họ [EFF98].Và,tất nhiên,giá phần cứng sẽ tiếp tục giảm như tăng tốc độ, làm cho DES hầu như vô giá trị. Điều quan trọng cần lưu ý rằng có nhiều hơn một cuộc tấn công vét cạn khóa(key-search) thay vì chỉ đơn giản là đi qua tất cả khóa có thể.Trừ khi biết bản gốc được cung cấp,nhà phân tích phải có khả năng nhận biết văn bản gốc giống như văn bản gốc.Nếu thông điệp chỉ là vẳn bản đơn giản trong tiếng Anh, thì sau đó kết quả sẽ hiện ra một cách dễ dàng, mặc dù các cách nhận ra tiếng Anh sẽ phải được tự động. Nếu các thông điệp văn bản đã được nén trước khi mã hóa, thì sau đó công việc sẽ khó khăn hơn.Và nếu thông điệp này là một số loại dữ liệu tổng quát hơn, chẳng hạn như một tập tin số,và nó đã được nén,vấn đề trở nên khó khăn hơn khi để tự động hoá.Vì vậy, để bổ sung cho phương pháp brute-force, một vài kiến thức về các văn bản gốc dự kiến là cần thiết, và một số phương tiện tự động phân biệt văn bản gốc từ việc lựa chọn cũng cần thiết.EFF tiếp cận địa chỉ của vấn đề này khá tốt và cũng giới thiệu một số kỹ thuật tự động mà có thể có hiệu quả trong nhiều ngữ cảnh. May mắn thay, có một số lựa chọn thay thế cho DES, quan trọng nhất trong số đó là AES và 3DES, thảo luận trong chương 5 và 6, tương ứng. Bản chất của thuật toán DES Mối quan tâm khác là khả năng thám mã,có thể bằng cách khai thác các đặc tính của các thuật toán DES. Trọng tâm của mối quan tâm đã được thể hiện trên tám bảng thay thế, hay các S-box, được sử dụng trong mỗi lần lặp. Bởi vì các tiêu chuẩn thiết kế cho các box, thực sự cho các thuật toán đầy đủ, đã không được công khai, có một nghi ngờ rằng các box được xây dựng theo cách mà phân tích mật mã có thể dành cho đối thủ - những người biết những điểm yếu trong S-box. Sự khẳng định này là trêu ngươi, trong những năm qua một số qui luật và hành vi không mong muốn của S-box đã được phát hiện. Mặc dù vậy, không một ai cho đến nay đã thành công trong việc phát hiện các điểm yếu chết người trong S-box.[8] [8] Ít nhất, không một ai đã công khai thừa nhận như một khám phá. Thám mã thời gian (Timing Attacks) Chúng ta thảo luận về thám mã thời gian chi tiết hơn trong phần hai, khi chúng liên quan đến thuật toán khóa công khai.Tuy nhiên, vấn đề cũng có thể liên quan đến mã hóa đối xứng.Về bản chất, một cuộc thám mã thời gian là trong đó thông tin về khóa hay văn bản gốc đạt được bằng thực hiện quan sát mất bao lâu để thực hiện sự giải mật mã vào văn bản mã hoá khác nhau.Thám mã thời gian khai thác việc mã hoá hay sự giải mã thuật toán thường lấy khoảng thời gian trên đầu vào khác nhau [HEVI99] báo cáo về một phương pháp chỉ ra khối lượng Hamming (số bit bằng một) của khóa bí mật.Đây là một chặng đường dài tới khi biết khóa thực tế, nhưng nó là một bước đầu tiên thú vị.Các tác giả kết luận rằng DES có vẻ là có khả năng chịu được một cuộc thám mã thời gian thành công nhưng họ đề xuất một số con đường tìm hiểu.Mặc dù đây là một cách thú vị của cuộc tấn công, nhưng từ khi xuất hiện cho đến nay không chắc rằng kỹ thuật này bao giờ sẽ thành công với DES hoặc mạnh hơn thuật toán mã hóa đối xứng như 3DES và AES. 3.4. Thám mã vi phân và tuyến tính  Đối với phần lớn sự tồn tại của nó, mối quan tâm chính với DES là nhược điểm của nó để tấn công brute-force vì chiều dài khóa của nó tương đối ngắn (56 bit). Tuy nhiên, cũng có những quan tâm trong việc tìm kiếm các cuộc tấn công thám mã về DES.Với sự phổ biến tăng lên của thuật toán mã hóa khối với chiều dài của khóa tăng lên, bao gồm  3DES, kiểu tấn công brute-force ngày càng trở nên không thực tế.Vì vậy, đã có sự nhấn mạnh tăng lên trên các cuộc tấn công thám mã về DES và mã hóa khối đối xứng khác.Trong phần này,chúng tôi cung cấp một  tổng quan ngắn gọn về hai cách tiếp cận mạnh mẽ nhất và đầy triển vọng : thám mã vi phân và thám mã tuyến tính. Thám mã vi phân Một trong những tiến bộ quan trọng nhất trong thám mã trong những năm gần đây là thám mã vi phân.Trong phần này, chúng ta thảo luận về kỹ thuật và ứng dụng của nó cho DES. Lịch sử Thám mã vi phân không được báo cáo trong các tài liệu mở cho đến năm1990.  Những nỗ lực đầu tiên được công bố xuất hiện đã trở thành thám mã của một  mã hóa khối được gọi là FEAL của Murphy [MURP90]. Nó đã được theo sau bởi một số tài liệu của Biham và Shamir, người đã chứng minh hình thức tấn công vào một loạt các thuật toán mã hóa và hàm băm, kết quả của họ được tổng kết trong [BIHA93]. Hầu hết các kết quả công bố công khai cho phương pháp này đã trở thành các ứng dụng cho DES. Thám mã vi phân là hình thức tấn công đầu tiên được công bố có khả năng phá vỡ DES trong vòng hơn 255 độ phức tạp.Đề án này,theo báo cáo trong [BIHA93], có thể thành công trong việc giải mã DES với một nỗ lực với trình tự là 247 mã hóa, đòi hỏi 247 văn bản gốc được chọn. Mặc dù 247 chắc chắn là ít hơn đáng kể so với 255 nhưng sự cần thiết của các đối thủ để tìm 247 văn bản gốc chọn làm cho cuộc tấn công này chỉ được nêu về mặt lý thuyết. Mặc dù thám mã vi phân là công cụ mạnh, nhưng nó vẫn không chống lại DES tốt cho lắm. Lý do, theo thành viên của nhóm IBM thiết kế DES [ COPP94 ], là thám mã vi phân đã được biết đến ngay từ năm 1974. Nhu cầu làm vững mạnh DES (Chuẩn mã hoá dữ liệu) để chống lại tấn công sử dụng thám mã vi phân đóng vai trò lớn trong thiết kế S-box và phép hoán vị P. Bằng chứng về sư ảnh hưởng của những thay đổi này, xem xét kết quả có thể so sánh được những báo cáo trong BIHA93 [ ]. Thám mã vi phân của tám-vòng thuật toán LUCIFER chỉ đòi hỏi 256 văn bản gốc được chọn, trong khi tấn công vào tám - vòng phiên bản DES đòi hỏi 214 văn bản gốc được chọn Tấn công thám mã vi phân Những cuộc tấn công thám mã vi phân rất phức tạp;  [BIHA93] cung cấp một mô tả đầy đủ.Lý do đằng sau thám mã vi phân là quan sát hành vi của các cặp khối văn bản phát triển dọc theo mỗi vòng của thuật toán, thay vì quan sát sự phát triển của một khối văn bản duy nhất.Ở đây, chúng tôi cung cấp một tổng quan ngắn gọn để bạn có thể cảm nhận được hình thức của cuộc tấn công. Chúng ta bắt đầu với một thay đổi về ký hiệu cho DES. Xem xét khối văn bản gốc ban đầu m bao gồm hai nửa m0, m1. Mỗi vòng của sơ đồ DES  đầu vào bên phải đưa vào đầu ra tay trái và đặt ra các đầu ra bên phải là một chức năng của các đầu vào tay trái và khóa phụ cho các vòng này.Vì vậy, ở mỗi vòng, chỉ có một khối mới 32-bit được tạo ra. Nếu chúng ta gán nhãn cho mỗi khối mới mi (2i17) sau đó là nửa thông báo trung gian có liên quan như sau: mi+1 = mi-1 f(mi, Ki), i = 1, 2, ..., 16 Trong thám mã vi phân, chúng ta bắt đầu với hai thông báo, m và m', với một sự khác biệt của phép XOR đã biết ∆m = mm', và xem xét sự khác biệt giữa hai nửa thông báo trung gian: mi = mimi' Sau đó chúng ta có: ∆mi+1 = mi+1 m’i+1 = [mi-1 f(mi,Ki)] [m’i-1 f(m’i,Ki)] = ∆mi-1 [f(mi,Ki) f(m’i,Ki)] Bây giờ, giả sử rằng nhiều cặp đầu vào cho F với cùng một lượng khác biệt cùng có đầu ra khác nhau và cùng một khóa con được sử dụng. Để mô tả này chính xác hơn, chúng ta nói rằng X có thể gây ra Y với khả năng p, nếu cho một phần nhỏ p trong số các cặp trong đó đầu vào XOR là X, các đầu ra XOR bằng Y. Chúng ta muốn giả sử rằng có một số giá trị của X có khả năng cao gây ra một sự khác biệt đầu ra cụ thể. Do đó, nếu chúng ta biết ∆mi-1và ∆mi với khả năng cao,sau đó chúng ta biết ∆mi+1 với khả năng cao.Hơn nữa, nếu một  số sự khác biệt đó được xác định, việc xác định khóa được sử dụng trong hàm f sẽ khả thi. Chiến lược tổng thể của thám mã vi phân được dựa trên những nhận xét này cho một vòng duy nhất. Thủ tục này là để bắt đầu với hai thông điệp văn bản gốc m và m' với một sự khác biệt nhất định và theo dõi thông qua một mô hình có thể của sự khác biệt sau mỗi vòng để mang lại một sự khác biệt có thể xảy ra cho bản mã này. Trên thực tế,có hai mô hình có thể của sự khác biệt cho hai nửa 32-bit: (Δm17 || m16). Tiếp theo, chúng ta mã hóa m và m' để xác định sự khác biệt thực tế theo các khoá chưa biết và so sánh kết quả với sự khác biệt có thể xảy ra. Nếu có một trùng lặp : E(K, m) E(K, m') = (∆m17||m16) sau đó chúng tôi nghi ngờ rằng tất cả các mô hình có thể xảy ra ở tất cả các vòng trung gian là chính xác.Với giả định rằng, chúng ta có thể làm một vài suy đoán về các bit khóa.Thủ tục này phải được lặp đi lặp lại nhiều lần để xác định tất cả các bit khóa. Hình 3.7 dựa trên một hình trong [BIHA93], minh họa sự lan truyền của những khác biệt thông qua ba vòng của  DES.Các khả năng thể hiện ở bên phải đề cập các khả năng mà một tập trung gian khác biệt sẽ xuất hiện như là một hàm của sự khác biệt đầu vào.Nhìn chung, sau ba vòng khả năng rằng sự khác biệt đầu ra là như được hiển thị  bằng 0,25 x 1 x 0,25 = 0,0625. Hình 3.7. Sự lan truyền vi phân qua ba vòng của DES (các số ở hệ thập lục phân) Thám mã tuyến tính Một phát triển gần đây hơn là thám mã tuyến tính, mô tả trong [MATS93]. Kiểu tấn công này được dựa trên tìm tính xấp xỉ tuyến tính để mô tả biến đổi thực hiện trong DES (Chuẩn mã hoá dữ liệu). Phương pháp này có thể tìm khóa DES cho 243 văn bản gốc đã biết, so với 247 văn bản gốc đã chọn cho thám mã vi phân. Mặc dù đây là cải tiến nhỏ, vì nó có thể là dễ có được hơn văn bản gốc đã biết thay vì văn bản gốc đã chọn, nhưng thám mã tuyến tính vẫn không thể thực hiện được một tấn công vào DES. Cho đến nay, công việc nhỏ đã được thực hiện do nhóm khác để xác nhận phương pháp thám mã tuyến tính. Bây giờ chúng ta cho một bản tóm tắt ngắn gọn về nguyên tắc mà thám mã tuyến tính dựa trên đó. Đối với một mã hóa với khối văn bản gốc n-bit và khối văn bản mã hóa và một khóa m-bit, gán nhãn cho các khối văn bản gốc  là P [1], ... P [n], và các khối văn bản mã hóa là C [1], ...C [n], và khóa K [1], ...  K [m]. Sau đó, ta định nghĩa : A[i, j, ..., k] = A[i] A[j] ... A[k] Mục tiêu của thám mã tuyến tính là tìm một phương trình tuyến tính có hiệu quả có dạng: P[α1, α2, ..., αa] C[β1, β2, ..., βb] = K[γ1, γ2, ..., γc] (X = 0 hoặc 1, 1 a, b n, 1 c m, và α, β và γ là những đại lượng giới hạn cố định, vị trí của các bit khác biệt) Giữ với xác xuất p 0.5 Các p tiếp theo là từ 0,5 phương trình càng có hiệu quả hơn.Khi một quan hệ đề nghị được xác định, thủ tục là để tính toán các kết quả của phía bên tay trái của phương trình trước cho một số nhiều các cặp văn bản gốc-văn bản mã hóa. Nếu kết quả là 0 hơn một nửa thời gian, giả sử K 

Các file đính kèm theo tài liệu này:

  • docxBan Dich Tieng Viet.docx
  • docxBia Chuong 3.docx
  • pptSlide Bao Cao.ppt
Tài liệu liên quan