차분 암호 분석

차분 암호 분석은 주로 블록 암호뿐만 아니라 스트림 암호 및 암호화 해시 함수에도 적용할 수 있는 일반적인 암호 분석 형식입니다.가장 넓은 의미에서, 정보 입력의 차이가 출력의 결과 차이에 어떻게 영향을 미칠 수 있는지에 대한 연구이다.블록 암호의 경우, 변환 네트워크를 개입시켜 차이를 추적해, 그 암호에 랜덤하지 않은 동작이 나타나는 장소를 검출해, 그러한 속성을 이용해 비밀 키(암호화 키)를 회복하는 일련의 기술을 참조한다.

역사

차분 암호 분석의 발견은 일반적으로 1980년대 후반 Eli Biham과 Adi Shamir에 기인합니다.그는 Data Encryption Standard(DES; 데이터 암호화 표준)의 이론적인 약점을 포함한 다양한 블록 암호 및 해시 함수에 대한 공격을 발표했습니다.Biham과 Shamir는 DES가 차분 암호화에 놀라울 정도로 내성이 있지만 알고리즘을 조금만 수정하면 훨씬 더 ^[1]취약해진다는 것을 알게 되었습니다.

1994년 IBM DES 팀의 Don Coppersmith는 차등 암호화가 1974년 IBM에 이미 알려져 있었으며 차등 암호화에 대한 방어가 설계 ^[2]목표였다는 논문을 발표했습니다.저자 Steven Levy에 따르면 IBM은 자체적으로 차등 암호 분석을 발견했으며 NSA는 분명히 이 기술을 ^[3]잘 알고 있었다.Coppersmith가 설명하듯이 IBM은 몇 가지 비밀을 지켰습니다. "NSA와 논의한 결과, 설계 고려 사항을 공개하면 많은 암호에 대해 사용할 수 있는 강력한 기술인 차등 암호화 기술이 공개될 것으로 결정되었습니다.이는 결국 암호학 ^[2]분야에서 미국이 다른 나라에 비해 누려온 경쟁 우위를 약화시킬 것입니다."IBM 내에서 차등 암호 분석은 "T-attack"^[2] 또는 "Tickle 공격"^[4]으로 알려져 있습니다.

DES는 차분 암호 해석에 대한 내성을 염두에 두고 설계되었지만 다른 현대의 암호는 취약한 것으로 판명되었습니다.공격의 초기 타깃은 FEAL 블록 암호였습니다.4라운드가 포함된 원래 제안 버전(FEAL-4)은 선택한 8개의 플레인텍스트를 사용하여 파괴할 수 있으며 31라운드의 FEAL 버전도 공격에 취약합니다.이와는 대조적으로, 이 스킴은 선택된 2개의⁴⁷ 평문 정도의 노력으로 DES를 성공적으로 암호화할 수 있습니다.

어택 메카니즘

차분 암호 분석은 보통 선택된 평문 공격입니다.즉, 공격자는 자신이 선택한 평문 세트에 대해 암호문을 얻을 수 있어야 합니다.단, 기존의 플레인텍스트 또는 암호문만의 공격을 허용하는 확장기능이 있습니다.기본 방법에서는 일정한 차이에 따라 관련된 평문 쌍을 사용합니다.차이는 여러 가지 방법으로 정의할 수 있지만 eXclusive OR(XOR) 연산은 일반적입니다.그런 다음 공격자는 해당 암호 텍스트의 차이를 계산하고 분포에서 통계 패턴을 탐지하려고 합니다.결과적으로 발생하는 차이 쌍을 미분이라고 합니다.이러한 통계 속성은 암호화에 사용되는S 상자의 특성에 따라 다르므로 공격자는 차분 $(\Delta _{x},\Delta _{y})$ δ x $(\Delta _{x},\Delta _{y})$ $(\Delta _{x},\Delta _{y})$ y $(\Delta _{x},\Delta _{y})$ )을 분석합니다.\ $display$ style ( \ $Delta$ _ { $x$ , \ $Delta$ _ { $y$ } ) 。

\displaystyle \Delta _{y}=S(x\oplus \Delta _{x}\oplus S(x)}

(및 denotes는 이러한 S박스 S 각각에 대해 배타적 또는 를 나타낸다.)기본 공격에서는 특정 암호문 차이가 특히 자주 발생할 것으로 예상됩니다.이와 같이 암호는 랜덤과 구별할 수 있습니다.더 정교한 변형으로 전체 검색보다 키를 더 빨리 복구할 수 있습니다.

차분 암호 분석을 통한 가장 기본적인 키 회복 형식에서 공격자는 다수의 평문 쌍에 대해 암호문을 요구한 후 차분이 최소 r - 1라운드 동안 유지된다고 가정합니다.여기서 r은 라운드의 총수입니다.그런 다음 공격자는 최종 라운드가 확정되기 전에 블록 간의 차이를 가정하여 가능한 라운드 키(최종 라운드)를 추론합니다.라운드 키가 짧을 경우, 이것은 가능한 라운드 키별로 한 라운드씩 암호문 쌍을 완전히 복호화하는 것만으로 달성할 수 있습니다.하나의 라운드 키가 다른 키보다 상당히 자주 잠재적인 라운드 키로 간주될 경우 올바른 라운드 키로 간주됩니다.

공격이 성공하려면 특정 암호에 대해 입력 차이를 신중하게 선택해야 합니다.알고리즘의 내부 분석을 실시합니다.표준적인 방법은 차분 특성이라고 불리는 암호화의 다양한 단계를 통해 가능성이 높은 차이의 경로를 추적하는 것입니다.

차분 암호 해독은 공공의 지식이 된 이후 암호 설계자들의 기본 관심사가 되었다.새로운 설계에는 알고리즘이 이 공격에 내성이 있다는 증거가 수반될 것으로 예상되며 Advanced Encryption Standard를 포함한 많은 설계에서는 공격에 ^{[citation needed]}대한 안전성이 입증되었습니다.

상세 공격

공격은 주로 특정 입력/출력 차이 패턴이 특정 입력 값에 대해서만 발생한다는 사실에 의존합니다.일반적으로 공격은 비선형 컴포넌트가 솔리드 컴포넌트인 것처럼 기본적으로 적용됩니다(보통 실제로는 룩업테이블 또는 S박스입니다).원하는 출력 차이(선택된 두 개의 평문 입력 또는 알려진 평문 입력 간)를 관찰하면 가능한 키 값을 알 수 있습니다.

예를 들어 1 = > 1의 차이(입력 최하위 비트(LSB)의 차이가 LSB의 출력 차이로 이어지는 경우)가 4/256의 확률(예를 들어 AES 암호의 비선형 함수와의 차이)로 발생할 경우 4개의 값(또는 2쌍)에 대해서만 차이가 가능합니다.평가 전에 키를 XOR하고 미분을 허용하는 값이 {2,3} 및 {4,5}인 비선형 함수를 사용한다고 가정합니다.공격자가 {6, 7} 값을 전송하고 올바른 출력 차이를 관찰하는 경우 키는 6 k K = 2 또는 6 ⊕ K = 4 중 하나이며, 키 K는 2 또는 4입니다.

본질적으로, n비트 비선형 함수의 경우, 미분 균일성을 달성하기 위해 가능한 한 2에 가까운^{−(n − 1)} 함수를 찾는 것이 이상적입니다.이 경우 차동 공격은 단순히 키를 강제하는 것만큼 키를 판별하는 데 많은 작업이 필요합니다.

AES 비선형 함수의 최대 차분 확률은 4/256입니다(다만, 대부분의 엔트리는 0 또는 2 중 하나입니다).즉, 이론적으로는 무차별적인 힘의 절반으로 키를 판별할 수 있지만 AES의 높은 브랜치에서는 여러 라운드에 걸쳐 높은 확률의 트레이스가 존재하지 않게 됩니다.실제로 AES 암호는 비선형 함수가 훨씬 약한 차분 및 선형 공격에도 동일하게 영향을 받지 않습니다.4R보다 브랜치(액티브 S박스 수)가 25로 매우 높기 때문에 8라운드 이상에서는 비선형 변환이 50개 미만으로 이루어지지 않으며, 이는 성공 확률이 Pr[공격] pr Pr[ ⁵⁰S박스에 대한 최고의 공격]을 초과하지 않음을 의미합니다.예를 들어 현재의 S박스에서는 AES는 ⁵⁰(4/256) 또는⁻³⁰⁰ 128비트블록 암호에 필요한 임계값 2보다⁻¹²⁸ 훨씬 낮은2보다 높은 확률로 고정차분을 방출하지 않습니다.이렇게 하면 S박스가 16일지라도 공격 가능성은 여전히 2가⁻²⁰⁰ 될 수 있기 때문에 보다 효율적인 S박스를 만들 수 있습니다.

2-균일성이 있는 균일한 크기의 입력/출력에는 분사가 없습니다.이들은 큐빙 또는 반전 중 하나를 사용하여 홀수 필드(GF⁷(2) 등)에 존재합니다(다른 지수들도 사용할 수 있습니다).예를 들어, 모든 홀수 이진 필드의 S(x) = x는³ 미분 및 선형 암호 해석의 영향을 받지 않습니다.이것이 MISTY 설계에서 16비트 비선형 함수에 7비트 및 9비트 함수를 사용하는 이유이기도 합니다.이러한 함수는 미분 및 선형 공격에 대해 면역력을 얻으며 대수적 ^[why?]공격에 의해 손실됩니다.즉, SAT 솔버를 통해 기술하고 해결할 수 있습니다.이것이, AES(예를 들면)가 반전 후에 아핀 매핑을 가지는 이유의 일부입니다.

특화된 타입

「」를 참조해 주세요.

레퍼런스

^ Biham and Shamir, 1993, 8-9페이지
^ ^a ^b ^c Coppersmith, Don (May 1994). "The Data Encryption Standard (DES) and its strength against attacks" (PDF). IBM Journal of Research and Development. 38 (3): 243–250. doi:10.1147/rd.383.0243. (설명 필요)
^ Levy, Steven (2001). Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age. Penguin Books. pp. 55–56. ISBN 0-14-024432-8.
^ Matt Blaze, sci.crypt, 1996년 8월 15일 Re: Reverse Engineering and the Clipper Chip"

일반

Eli Biham, Adi Shamir, Differential Crypton Analysis of the Data Encryption Standard, Springer Verlag, 1993년ISBN 0-387-97930-1, ISBN 3-540-97930-1.
Biham, E., A.샤미르.(1990).DES 유사 암호 시스템의 차분 암호 분석암호학의 진보— CRYPTO '90.스프링거-벨라그.2–21.
Eli Biham, Adi Shamir, "풀 16라운드 DES의 차분 암호 분석", CS 708, CRYPO '92, 컴퓨터 사이언스 강의 노트 제740권, 1991년 12월. (Postscript)

외부 링크

차분(및 선형) 암호 분석에 대한 튜토리얼
미분암호해석에 관한 Helger Lipma의 링크
Wayback Machine에서 DES에 적용된 공격에 대한 설명(2007년 10월 19일 아카이브)

[1] Biham and Shamir, 1993, 8-9페이지

[coppersmith-2] Coppersmith, Don (May 1994). "The Data Encryption Standard (DES) and its strength against attacks" (PDF). IBM Journal of Research and Development. 38 (3): 243–250. doi:10.1147/rd.383.0243. (설명 필요)

[3] Levy, Steven (2001). Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age. Penguin Books. pp. 55–56. ISBN 0-14-024432-8.

[4] Matt Blaze, sci.crypt, 1996년 8월 15일 Re: Reverse Engineering and the Clipper Chip"

[1]

[2]

[3]

[4]

Search

차분 암호 분석

네임스페이스

더

목차

역사

어택 메카니즘

상세 공격

특화된 타입

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

차분 암호 분석

역사

어택 메카니즘

상세 공격

특화된 타입

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.