선형 암호 분석과 근사 테이블

선형 암호분석(Matsui, 1993)은 확률 p ≠ 1/2로 성립하는 암호의 선형 근사(특정 비트의 XOR)를 찾는 알려진 평문 공격입니다. 많은 평문-암호문 쌍을 사용하면 통계적 편향으로 키 비트를 알아낼 수 있습니다.

S-상자에 대한 선형 근사는 선택한 입력 비트의 합 XOR 선택한 출력 비트의 합 = 0 (mod 2)가 확률 p로 성립하는 관계입니다. P[a·x XOR b·y = 0] = 1/2 + ε로 나타내며, a와 b는 비트 마스크이고 ε은 편향입니다(|ε| >> 0이면 바람직합니다).

LAT는 각 입력 마스크 a와 출력 마스크 b에 대해 (a·x) XOR (b·S(x)) = 0을 만족하는 입력 x의 개수를 셉니다. 여기서 2^{n-1}을 빼면 편향을 얻습니다. 좋은 S-상자의 |max_bias|는 1이며(확률 1/2 ± 1/2^{n/2}), 가능한 한 평평해야 합니다.

여러 라운드에 걸친 독립적인 선형 근사의 경우 편향이 곱해집니다. ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r입니다. 각 라운드의 근사는 유효 편향을 절반으로 줄입니다. 많은 라운드를 거치면 전체 편향은 0에 가까워지므로, 이를 감지하려면 지수적으로 더 많은 쌍이 필요합니다.

r라운드 암호를 공격하려면 r-1라운드를 통과하는 선형 경로 ε을 찾습니다. N = 1/ε^2개의 알려진 평문을 수집합니다. 각 후보 마지막 라운드 키 바이트 k'에 대해 마지막 라운드를 부분적으로 XOR 복호화하고, 선형 근사가 N/2번보다 많이 성립하는지 확인합니다. 올바른 k'는 올바른 편향을 보여 줍니다.

마쓰이는 1993년에 편향이 2^{-21.4}인 14라운드 선형 근사를 사용해 16라운드 DES를 공격했습니다. 알려진 평문 2^{43}개가 필요했습니다. 1단계에서 키 비트 26개를 복구하고, 나머지 30개는 전수 검색으로 복구했습니다. 전체 DES에 대한 전수 대입보다 빠른 최초의 실용적 공격이었습니다.

AES S-상자의 LAT 항목 최댓값은 S-상자 하나당 |ε| = 4/256 = 1/64입니다. 광폭 경로 전략은 모든 4라운드 경로에서 활성 S-상자의 수가 최소 25개가 되도록 제한합니다. 전체 편향은 (1/64)^{25/2} ≈ 2^{-75} 이하입니다. 알려진 평문 2^{150}개가 필요하므로 현실적으로 불가능합니다.

차분 분석: 알려진 평문 또는 선택 평문 쌍을 사용하며 출력 차이를 이용합니다. 선형 분석: 알려진 평문을 사용하며 통계적 선형 근사를 이용합니다. 실제 공격에서는 둘 다 선택 평문 공격으로 수행할 수 있습니다. 둘 다 설계 기준입니다. S-상자는 두 공격 모두에 강해야 하며(낮은 DDT 최댓값과 낮은 LAT 최댓값),

데이터 복잡도를 줄이기 위해 여러 선형 근사를 동시에 사용합니다. Nyberg와 Leander는 Matsui의 방법을 확장하여 M개의 근사를 결합하면 필요한 데이터가 log(M) 배만큼 줄어들도록 했습니다. PRESENT, SIMON 및 기타 경량 암호에 적용됩니다.

스트림 암호에 선형 근사를 적용하여 키스트림과 LFSR 출력의 선형 함수 사이의 상관관계를 찾습니다. 이 상관관계가 0이 아니면 전수 검색보다 빠르게 키를 복구할 수 있습니다. 이 연구는 스트림 암호에서 비선형 결합 함수를 설계하는 데 영향을 주었습니다.

적분 암호분석(Knudsen-Wagner)은 특정 바이트가 256가지 값을 모두 가지면서 나머지 바이트는 고정된 평문 집합을 선택합니다. 여러 라운드 후 특정 위치의 모든 출력에 XOR을 적용하면 0이 됩니다(균형 상태). 이 공격은 AES의 구조를 이용해 축소 라운드 AES를 효율적으로 무너뜨립니다.

누적 보조정리는 선형 근사를 결합할 때 무엇을 말합니까?

선형 암호분석은 S-상자의 편향된 선형 근사를 찾습니다. AES는 LAT에 최적화된 S-상자와 광폭 경로 설계를 통해 이에 대응합니다. 마쓰이는 14라운드 경로와 알려진 평문 2^43개를 사용해 DES를 무너뜨렸습니다. 다음 주제: 생일 공격과 충돌 찾기.