Phân tích mật mã

Classical cryptanalysis

Mặc dù thực sự từ “cryptananlysis” mới xuất hiện gần đây ( được đặt bởi Willian Friedman vào năm 1920), nhưng các phương thức phá code và cipher đã có từ trước đó. Được biết đến đầu tiên vào thế ký thứ 9 được đưa ra bới nhà bác học người A rập, Al-Kindi, trong tác phẩm A Manuscript on Deciphering Cryptographic Messages.Trong cuốn này bao gồm một sự giải mã của phương thức frequency analysis được đưa ra bởi Ibrahim Al-Kadi vào năm 1992-1993. Frequency analysis là phương thức cơ bản để phá vỡ hâu hết các khối cổ điển. Trong ngôn ngữ tự nhiên, các chữ cái chính trong bảng chữ cái xuất hiện nhiều hơn những cái khác; trong tiếng Anh, E giống như chữ cái chung nhất trong bất kỳ mẫu plaintext. Tương tự, TH là cặp chữ cái dùng nhiều nhất trong tiếng Anh. Frequency analysis dựa trên các khối không ẩn đi những thông tin được biểu diễn bằng các con số này.

Trong thực tế, frequency analysis dựa nhiều vào kiến thức ngôn ngữ khi làm việc trên thông tin được biểu diễn bằng số. Nhưng khi các khối trở nên phức tạp hơn, Toán học trở nên quan trọng hơn trong cryptanalysis.Sự thay đổi này được cụ thể trong thế chiến II với những nỗ lực đầu tiên để bẻ gãy khối Axis đòi hỏi những cấp độ mới của tinh hoa toán học. Hơn nữa, sự tự động được ứng dụng đầu tiên tới cryptanalysis trong thời kỳ này với dịch vụ Bompa của Ba Lan dùng card đục lỗ, và trong Colossus, một trong những máy tính sớm nhất.

Mô hình cryptanalysis

Trong các học viện, các thiết kế mới xuất hiện thường xuyên, và nó cũng bị phá vỡ thường xuyên:

- Năm 1984, mã khối Madryga được tìm ra dễ bị phá bởi các sự tấn công chỉ nhắm vào ciphertext vào năm 1998.

- FEAL-4, được đề xuất để thay thế cho giải thuật mã hóa tiêu chuẩn DES, bị hạ gục bới sự tấn công dồn dập của cộng đồng giảng viên

- Trong công nghiệp cũng vậy, các khối cũng không tránh khỏi sai sót. VÍ dụ như các giải thuật A5/1,A5/2 và CMEA, được dùng trong kỹ thuật di động, có thể bị phá vỡ trong nhiều giờ, nhiều phút, hoặc thậm chí trong thời gian thực dùng các trang bị máy tính.

- Năm 2001, Wired Equivalent Privacy (WEP), một giao thức sử dụng sự bảo mật Wi-fi wireless networks, cũng bị phá bởi một sự tấn công các khóa có liên quan. Kết quả của cryptanalysis

Sự thành công của cryptanalysis có tác dụng chắc chắn trong lịch sử; khả năng đọc các suy nghĩa và kế hoạch bí mật giả định có thể là lợi thê quyết định. Ví dụ, trong thế chiến II, việc phá vỡ Zimmermann Telegram là phương tiện mang Mỹ vào chiến tranh. Trong thế chiến II, Sự giải mã khối German, bao gồm máy Enigma và khối Lorenz- được thừa nhận vào giữa cuối cuộc chiến tranh châu Âu trước khi xác định kết quả thật sự. Mỹ cũng được lợi từ sự giải mã mật mã code PURPLE của Nhật. Các chính phủ đã nhận ra được các lợi ích tiềm năng của cryptanalysis cho tin tức tình báo, cả quân sự và ngoại giao, và đã thành lập một tổ chưa chuyên phá code và các khối của các quốc gia khác, ví dụ các tổ chức GCHQ va NSA vẫn hoạt động đến ngày nay.

1. Kiến thức và khả năng nào là điều kiện tiên quyết?

2. Có bao nhiêu thông tin bí mật được suy luận ra?

3. Đòi hỏi bao nhiêu nỗ lực? ( Bản chất phức tạp của tính toán là gì?)

Kiến thức tiền đề: Chuỗi sự kiện cho analysis

Cryptanalysis có thể được thực hiện dưới nhiều giả thiết về bao nhiêu thứ cần quan sát và tìm ra về hệ thống dưới sự tấn công. Khi bắt đầu cơ bản thường giả sử rằng, cho mục đích phân tích, các giải thuật thông thường được biết; đây là nguyên lý “kẻ thù biết hệ thống” của Kerckhoff .

Các sự giả thiết khác bao gồm: • Ciphertext-only: người giải mã chỉ truy cập đến một tập các ciphertext hoặc codetext. • Known-plaintext: Người tấn công có một tập các ciphertext mà anh ta biết để đáp ứng các plaintext. • Chosen-plaintext (chosen-ciphertext): Người tấn công có thể nhận được ciphertext (plaintext) đấp ứng cho một tập các plaintext(ciphertext) bất kì cho sự lựa chọn của chính anh ta. • Adaptive chosen-plaintext: giống như là tấn công một khối plaintext được chọn, trừ việc các kẻ tấn công có thể chọn các plaintext tiếp theo dựa trên thông tin học được từ các sự mã hóa trước đó. Tương tựu cho Adaptive chosen ciphertext attack. • Related-key attack: Giống như tấn công chọn sẵn plaintext, trừ việc kẻ tấn công có thể nhận được ciphertext được mã hóa với hai khóa khác nhau. Các khóa không được biết đến, những mối quan hệ giữa chúng thì được biết; ví dụ hai kháo chỉ khác nhau 1 bit. Những kiểu tấn công này rõ ràng khác nhau trong cái cách hợp lý mà chúng được dùng trong thực tế. Mặc dù có một vài kiểu phù hợp hơn những kiểu khác, những người viết mật mã thường sẽ thận trọng để bảo mật và giả sử rằng trường hợp xấu nhất khi thiết kế các giải thuật, nếu một quy trình bảo mật thậm chí ngăn cản những đe dọa không có thực thì nó cũng chống lại sự giải mã trong thế giới thực tốt.

Phân loại thành công trong cryptanalysis Các kết quả của cryptanalysis có thể khác nhau trong sự hữu dụng. Ví dụ, người viết mật mã Lars Knudsen (1998) đã phân các loại tấn công khác nhau trên mã khối dựa vào số lượng và chất lượng thông tin bí mật bị khám phá.

• Total break — Kẻ tấn công tìm ra khóa bí mật.

• Global deduction — Kẻ tấn công tìm ra giải thuật tương đương cho sự mã hóa và giải mã nhưng không học về key.

• Instance (local) deduction — kẻ tấn công tìm ra khối plaintext (hoặc ciphertext) mà không được biết trước.

• Information deduction — Kẻ tấn công thu được một vài thông tin Shanon ve plaintext (hoặc ciphertext) không được biết trước.

• Distinguishing algorithm — Kẻ tấn công có thể nhận biết được khối từ một sự hoán vị ngẫu nhiên.

Complexity

Cuộc tấn công có thể được đặc trưng bới số lượng tài nguyên mà chúng đòi hỏi.

• Time — số “phép tính chính” được mô tả. Cái này không chặt chẽ, phép tính chính có thể là các chỉ dẫn máy tính cơ bản như cộng, XOR, luân phiên…,hoặc hoàn toàn là các phương thức mã hóa. Such as addition, XOR, shift, and so forth, or entire encryption methods.

• Memory —Sô lưu trữ đòi hỏi để mô tả tấn công the amount of storage required to perform the attack.

• Data — chất lượng của plaintext và ciphertext đòi hỏi.

Mật mã bất đối xứng (còn gọi là mã public key) là mật mã dựa trên việc sử dụng 2 khóa: 1 public, 1 private. Sự bảo mật của mật ãm 2 khóa dựa trên các câu hỏi toán học theo kiểu mà mã khóa đơn thông thường không làm được và leein kết cryptanalysis tới các nghiên cứu các thuật toán rộng hơn theo một cách mới.

Một quy trình bất đói xứng được thiết kê quanh việc giải quyết các vấn đề toán học khác nhau. Nếu một giải thuật tiến bộ có thể được tìm thấy để giải quyết vấn đề, thì hệ thống sẽ trở nên yếu đi. Ví dụ, sự bảo mật của quy trình đổi khóa Diffie-Hellman dựa trên sự khó khăn trong tính toán logarit hữu hạn. Năm 1983, Don Coppersmith đã tìm ra cách nhanh hơn để tìm logarit hữu hạn, do đó đòi hỏi các nhà làm mật mã phải sử dụng những nhóm lớn (hoặc các loại nhóm kahcs nhau). Đặc điểm khác biết của quy tình bất đối xứng không giống như tấn công các hệ thống mật mã đối xứng, bất kỳ cryptanalysis có cơ hội để sử dụng kiến thức thu được từ public key.

Methods of cryptanalysis

Classical cryptanalysis:

• Frequency analysis

• Index of coincidence

• Kasiski examination Symmetric algorithms:

• Boomerang attack

• Brute force attack

• Davies' attack

• Differential cryptanalysis

• Impossible differential cryptanalysis

• Integral cryptanalysis

• Linear cryptanalysis

• Meet-in-the-middle attack

• Mod-n cryptanalysis

• Related-key attack

• Slide attack

• XSL attack

Hash functions:

• Birthday attack

Attack models:

• Chosen-ciphertext attack

• Chosen-plaintext attack

• Ciphertext-only attack

• Known-plaintext attack

Side channel attacks:

• Power analysis

• Timing attack

Network attacks:

• Man-in-the-middle attack

• Replay attack

External attacks:

• Black-bag cryptanalysis

• Rubber-hose cryptanalysis