바이클리크 공격

바이클리크 공격은 암호 분석의 MITM(Meet-in-the-Middle) 방식의 변형입니다.MITM 공격에 의해 공격될 가능성이 있는 라운드의 수를 늘리기 위해 바이클릭 구조를 사용합니다.바이클리크 암호 분석은 MITM 공격을 기반으로 하기 때문에 블록 암호와 (반복) 해시 함수 모두에 적용할 수 있습니다.바이클리크 공격은 완전한^[1] AES와 완전한 ^[2]IDEA를 모두 파괴한 것으로 알려져 있지만, 무차별적인 공격보다 약간 우위에 있을 뿐입니다.또한 Skin-512 및 SHA-2 해시 ^[3]함수의 KASUMI 암호 및 프리이미지 저항에도 적용되고 있습니다.

이 양면 공격은 여전히(2019년 4월^[update] 현재) AES에 대한 가장 널리 알려진 단일 키 공격이다.공격의 계산 복잡도는 $2^{126.1}$ 1 $($ 2 $^{126.$ 1 $2^{126.1}$ $2^{189.7}$ 7 $($ 2 $^{189.7$ }) $2^{254.4}$ $($ 2 $^{254})$ 입니다. $4$ AES128, AES192 및 AES256의 경우 각각이것은 AES에 대해 공식적으로 알려진 유일한 단일 키 공격이며 전체 ^[1]라운드를 공격합니다.이전 공격에서는 축소된 원형 변형(일반적으로 7 또는 8 라운드로 감소)을 공격했습니다.

공격의 계산 복잡도는 2 $.$ 1({ $displaystyle$ 2 $^{126.$ 1 $2^{126.1}$ 이므로 이론적인 공격이며, 이는 AES의 보안이 깨지지 않았으며 AES의 사용은 비교적 안전한 상태를 유지하고 있음을 의미합니다.그럼에도 불구하고 바이클리 공격은 흥미로운 공격이며 블록 암호에 대한 암호 해독을 수행하기 위한 새로운 접근 방식을 제안합니다.이 공격은 또한 AES에 대한 더 많은 정보를 제공했는데, AES에 사용된 라운드의 안전성에 의문을 제기했기 때문이다.

역사

최초의 MITM 공격은 1977년 Diffie와 Hellman이 ^[4]DES의 암호학적 특성에 대해 논의했을 때 처음 제안되었습니다.키 사이즈가 너무 작아서 다른 키를 사용하여 DES를 여러 번 재적용하는 것이 키 사이즈의 해결책이 될 수 있다고 주장했습니다.다만, MITM 공격(MITM 공격을 더블 DES에 적용하여 보안을 $({$ )에서 $2^{56*2}$ 할 수 있기 때문에, 적어도 더블 DES를 사용하지 말아 주세요). $playstyle$ 2 $^{56*2}}$ 에서 $2^{{56*2}}$ $2*2^{56}$ 2 $2*2^{56}$ 56 $({$ 2 $*2^{56$ 으로 변경합니다.플레인 텍스트와 암호 텍스트가 있는 경우 첫 번째 및 두 번째 DES 암호화를 독립적으로 브루트 포스할 수 있기 때문입니다.

Diffie 및 Hellman이 MITM 공격을 제안한 이후 기본적인 MITM 공격을 적용할 수 없는 상황에서 유용한 다양한 종류가 등장했습니다.바이클리 공격 변종은 Dmitry Khovratovich, Rechberger 및 Savelieva가 해시 함수 암호 해독에 ^[5]사용하기 위해 처음 제안했습니다.그러나 Bogdanov, Khovratovich, Rechberger는 AES에 대한 공격을 발표하면서 블록 암호 해독을 포함한 비밀키 설정에 바이클릭 개념을 적용하는 방법을 보여주었다.그 이전에는 AES와 다른 많은 블록 암호에 대한 MITM 공격은 거의 주목을 받지 못했습니다.이는 주로 AES와 같은 많은 최신 키 일정으로는 달성하기 어려운 사항인 MITM 공격을 용이하게 하기 위해 두 개의 'MITM 서브 암호' 사이에 독립된 키 비트가 필요했기 때문입니다.

양각선

양면 구조의 일반적인 설명은 양면 구조의 문서를 참조하십시오.

MITM 공격에서는 첫 번째 서브암호 및 두 번째 서브암호기에 속하는 $K_{1}$ $(\$ K_ ${1})$ 과 $K_{1}$ $(\$ 는 독립적이어야 합니다.즉, 서로 독립적이어야 합니다.그렇지 않으면 플레인 텍스트와 암호 텍스트의 일치 중간값을 MITM 공격에서 독립적으로 계산할 수 없습니다.(MITM 공격에는 다양한 종류가 있습니다.여기서 블록은 공유 키비트를 가질 수 있습니다.3 서브셋의 MITM 공격을 참조해 주세요).공격받은 암호의 확산으로 인해 이 속성은 많은 라운드에 걸쳐 이용하기 어렵습니다.
간단히 말하면:더 많은 라운드를 공격할수록, 더 큰 서브사이퍼를 갖게 될 것이다.서브시퍼가 클수록 서브시퍼 간의 독립된 키비트는 적어집니다.물론 각 서브시퍼의 실제 독립 키 비트 수는 키 스케줄의 확산 특성에 따라 달라집니다.

바이클리크는 예를 들어 MITM 공격을 사용하여 AES의 7라운드를 공격할 수 있도록 한 후 길이 3의 바이클리 구조(즉, 암호의 3라운드를 커버)를 이용하여 7라운드의 시작부터 마지막 라운드의 종료까지의 중간 상태를 매핑할 수 있습니다(예: 10(AES THU128).는 기본 MITM 공격으로는 그 정도의 라운드를 공격할 수 없는 경우에도 암호의 전체 라운드를 공격합니다.

따라서 바이클라이프의 의미는 MITM 공격 종료 시 중간값을 마지막 암호문에 매핑할 수 있는 구조를 효율적으로 구축하는 것입니다.중간 상태가 마지막에 매핑되는 암호문은 물론 암호화에 사용되는 키에 따라 달라집니다.상태를 바이클리크로 암호문에 매핑하기 위해 사용하는 키는 MITM 공격의 첫 번째 서브사이퍼와 두 번째 서브사이퍼로 강제된 키비트를 기반으로 합니다.

따라서 바이클리크 공격의 본질은 MITM 공격 외에도 $K_{1}$ $(\$ K_ ${1$ $K_{2}$ $(\$ 에 $K_{2}$ 따라 특정 중간 상태를 대응하는 암호 텍스트에 매핑할 수 있는 바이클리크 구조를 효과적으로 구축할 수 있는 것입니다.

바이클라이프 작성 방법

브루트포스

$중간$ 상태 $2^{d}$ 2개와 $텍스트$ 를 가져와서 $2^{d}$ 그 사이에 매핑되는 키를 계산합니다 $.$ 각 중간 상태를 모든 암호 텍스트에 링크해야 하므로 여기에는 $2^{2d}$ 의 $2^{2d}$ 복구 $2^{2d}$ (\distermediate $style$ 2 $^{2d}$ 개 $2^{2d}$ 합니다.

독립적인 관련 키 차이

(이 방법은 Bogdanov, Khovratovich 및 Rechberger의 논문: Biclique Cryptanalysis of the Full^[1] AES에서 제안되었습니다.)

예비:
바이클라이프의 기능은 $K[i,j]$ 과 같이 키 $K[i,j]$ K [ $]({displaystyle$ K $[i,j])$ 에 $K[i,j]$ 따라 중간값 $(\displaystyle$ S $S$ 를 암호문 $값$ C(\ $displaystyle$ C $C$ 에 매핑하는 것입니다.
$(\displaystyle\foralli,j:S_{j}{\xright 화살표[{f}}{K[i,j]}}C_{i}}$

순서:
순서 1: $S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}$ 0 $S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}$ $S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}$ K [ $S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}$ , $S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}$ $K[0,0]$ ] $S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}$ $S_{0}$ \ $displaystyle$ S $_$ $C_{0}$ { 0 } $S_{0}$ $C_{0}$ 、 C 、 \ $displaystyle$ S _ 0 _ { 0 $K[0,0]$ } 、 $K[0,0]$ （ $S_{0}$ $K[0,0]$ , $0$ ） {\ $texttext$ an an an an {\ {\ {\ {\ （ 0 , 0 , 0 $K[0,0]$ ） $。$ $}C_{$ o $S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}$ $f$ 서 $f\displaystyle$ f는 $f$ 지정된 키를 사용하여 중간 상태를 암호문에 매핑하는 함수입니다 $.$ 이를 기본 계산으로 나타냅니다.

순서 2: $2^{d}$ 2 $(\$ 2 $^{d})$ 의 $2^{d}$ 관련 키 세트가 2개 선택됩니다.키는 다음과 같이 선택됩니다.

첫 번째 키 세트는 기본 계산과 관련하여f {\ $displaystyle$ f $}$ 에 $f$ 대한 다음 차분 요건을 충족하는 키입니다. $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}$ $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}$ $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}$ $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}$ K $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}$ i { \ $displaystyle$ 0 { \ x $rightarrow$ [ { $f$ } { \ $Delta$ _ { $i$ } { i } } \ $Delta$ _ { $i$ }
두 번째 키 세트는 기본 계산과 $\nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0$ 하여 f $\displaystyle$ f $\$ \ $displaystyle$ _ ${j}{\xrightarrow[{f$ }{\ $displaystyle _{$ 에 $대한$ 다음 차분 조건을 충족하는 키입니다 $\nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0$
키는 $\Delta _{i}$ i \ $displaystyle$ $\$ $Delta$ _ { $i$ $\nabla _{j}$ {\ $\nabla _{j}$ {\ {\ {\ ${\$ j \ $displaystyle$ \ $nabla _$ { j } differentialsialsialsialsialsialsials의 $\nabla _{j}$ 트레일이 독립적이 되도록 선택됩니다.즉, 액티브한 비선형 컴포넌트를 공유하지 않습니다.

즉, 다음과 같습니다.
An input difference of 0 should map to an output difference of $\Delta _{i}$ under a key difference of $\Delta _{i}^{K}$ . All differences are in respect to the base computation.
입력차이 $\nabla _{j}$ $\nabla _{J}^{K}$ $\nabla _{j}$ j \ $display style$ \ $nabla$ _ $\nabla _{j}$ { j $\nabla _{j}$ } $\nabla _{J}^{K}$ an diffe diffe under under under under under under under J $\nabla _{J}^{K}$ K \ $display$ style \ $nabla _$ { $J$ }^{ K $\nabla _{J}^{K}$ a a under under under under under under under under under under under0에 매핑됩니다.모든 차이는 기본연산에 관한 것입니다.

순서 3:트레일은 비선형 구성요소(예: S박스)를 공유하지 않으므로 트레일을 결합하여 다음을 얻을 수 있습니다.
$0$ $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ i $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ i $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ j $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ f $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ j K $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ j $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ f $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ i K $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ ⊕ j K ⊕ j j $k$ j K $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ j $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}$ j 、 \ $display$ 0 { \ \ $delta _$ { $i }$ 、 \ $delta _$ { i { i } $}$
이는 2단계에서 나온 두 차이의 정의를 모두 준수합니다.
기본 계산의 태플 $(S_{0},C_{0},K[0,0])$ 0 $(S_{0},C_{0},K[0,0])$ $(S_{0},C_{0},K[0,0])$ 0 $(S_{0},C_{0},K[0,0])$ $(S_{0},C_{0},K[0,0])$ [ $(S_{0},C_{0},K[0,0])$ $(S_{0},C_{0},K[0,0])$ ) $(S_{0},C_{0},K[0,0])$ { $display$ style ( $S_{0$ }, $C_{0}, K[0,$ 0])도 $(S_{0},C_{0},K[0,0])$ 기본 계산과 관련하여 정의상 양쪽 차분에 적합함을 알 수 있습니다. $\Delta _{0}=0,\nabla _{0}=0$ $S_{0},C_{0}$ $S_{0},C_{0}$ $({$ }, $C_{0})$ K $K[0,0]$ $S_{0},C_{0}$ $]({$ $displaystyle$ K $[0,0])$ 를 $K[0,0]$ 두 정의 중 하나로 치환하면 0 $({displaystyle$ 0) $0{\xrightarrow[{f}]{0}}0$ $({$ $f}{$ 0 $})$ 이 $0{\xrightarrow[ {f}]{0}}0$ $0{\xrightarrow[{f}]{0}}0$ 됩니다. $elta$ _ ${0}^{K}=0$ 입니다.
즉, 기본 계산의 태플은 결합된 추적에도 XOR할 수 있습니다. $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ 0 $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ K [ $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ , $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ ] $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ ⊕ $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ i K $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ J $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ C 0 $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ δ 、 $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ i $S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}$ \ $display style$ S _ $0$ \ $o$ plus $_ la$ { $right }$

순서 4:다음과 같은 것을 알 수 있습니다.
$(\displaystyle S_{j}=S_{0}\oplus \sysla _{j})$
$\displaystyle K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \displayla _{j}^{K}$
$\displaystyle C_{i}=C_{0}\oplus\Delta_{i}$
이것을 위의 조합된 차분 트레일로 치환하면, 그 결과는 다음과 같습니다.
$S_{j}{\xright 화살표[{f}}{K[i,j]}}C_{i}$
위의 정의와 동일한 것은 앞서 언급한 바이클라이프입니다.
$(\displaystyle\foralli,j:S_{j}{\xright 화살표[{f}}{K[i,j]}}C_{i}}$

따라서 첫 번째 키 세트의 모든 $2^{d}$ 키(\ $displaystyle 2^{$ d $2^{d}$ })와 두 번째 키 세트의 $2^{d}$ 키(\ $displaystyle$ 2 $^{d$ })를 조합할 수 있기 때문에 $2^{2d}$ 크기 $2^{2d}$ $(\$ 2 $^{$ $2^{2d}$ $2^{d}$ }) $2^{2d}$ 의 바이클라이크를 작성할 수 있습니다.즉 $,$ $\Delta _{i}\neq \nabla _{j}$ $2^{2d}$ $2*2^{d}$ $2^{2d}$ $2*2^{d}$ $d$ 의 바이클라이프를 작성할 수 있는 것은 $displaystyle$ $\Delta _{i}\neq \nabla _{j}$ $^{d}$ 의 $2^{{2d}}$ $2*2^{d}$ $\Delta _{i}$ 차분 $(\$ }) 및 $\nabla _{j}$ $(\$ $displaystyle$ $\$ $\Delta _{i}\neq \nabla _{j}$ _ ${j$ $\Delta _{i}\neq \nabla _{j}$ 의 $\nabla _{j}$ $2*2^{d}$ 입니다. $_{i}\neq \nabla$ _ ${j}($ $i+j>0$ $i+j>0$ j > $i+j>0$ { $displaystyle$ i + $j$ > $0$ ） all all 、 $K[i,j]$ 키 $K$ [ $K[i,j]$ , j $K[i,j]$ ](i, j $K[i,j]$ > \ $display style$ K [ i, $j$ ])도 $K[i,j]$ 바이클릭으로 바뀝니다.

이렇게 해서 AES에 대한 선두적인 바이클릭 공격에서 바이클릭이 구축됩니다.이 기술로 바이리크를 구성하는 데는 몇 가지 실질적인 제한이 있습니다.바이클라이프가 길수록 차등 트레일이 더 많은 라운드를 커버해야 합니다.암호의 확산 특성은 따라서 바이클라이크 구성의 효율성에 중요한 역할을 합니다.

바이클라이프를 구성하는 다른 방법

Bogdanov, Khovratovich 및 Rechberger는 또한 "Biclique Cryptanalysis of the Full^[1] AES"라는 기사에서 'Interleaving Related-Key Differential Trails'라고 불리는 바이클리크를 구성하는 또 다른 방법을 설명합니다.

바이클리크 암호 분석 절차

순서 1:공격자는 $d$ 한 모든 키를 $2^{2d}$ $2$ $2^{2d}$ 의키 서브셋으로 그룹화합니다.여기서 그룹 내의 키는 $2^{d}\times 2^{d}$ d × $2^{d}\times 2^{d}$ 의 매트릭스 $K[i,j]$ 2 $^{$ d $d$ 의 $2^{{2d}}$ $K[i,j]$ K [ $i,$ $displaystyle$ $K[i,j]$ 2 $^{d}\times$ 2 $^{d$ 로 인덱싱됩니다.공격자는 일반 MITM 공격과 마찬가지로 $f$ 를f\ $displaystyle$ $g$ 와 $f$ g $\displaystyle$ g $($ $E=f\circ g$ $E=f\circ g$ $E=f\circ g$ g \ $displaystyle$ E $= f$ \ $circ$ g $E=f\circ g$ )의 2개의 서브 암호로 분할합니다.각 서브사이퍼의 키 세트는 $2^{d}$ $({$ 2 $^{d$ 로 $K[i,0]$ K $i,0]$ 및 $]({$ $displaystyle$ K $[0,j$ 라고 $K[i,0]$ .서브사이퍼의 조합 키는 전술한 $K[i,j]$ K[ $]$ 로 표현됩니다.

순서 2:공격자는 $2^{2d}$ 의 $(\$ 2 $^{2d})$ $2^{2d}$ 의 $2^{{2d}}$ 각 그룹에 대해 바이클라이프를 작성합니다. $2^{d}$ 의 $2^{d}$ $d_displaystyle$ 2 $^{d}$ $2^{2d}$ 를 $2^{d}$ 사용하여 $S_{j}$ 의 $S_{j}$ $^{$ $d$ }개의 내부 상태 $S_{j}$ ${$ j $S_{j}$ 를 $2^{2d}$ 의 $2^{d}$ $d_displaystyle$ $2^{d}$ 2 $^{$ d $}$ 개의 $2^{d}$ 암호 $C_{i}$ 에 $2^{d}$ 때문에 $C_{i}$ $2^{d}$ 의 dimension-d입니다."쌍곡선 작성 방법" 절에서는 "독립 관련 키 차이"를 사용하여 쌍곡선을 작성하는 방법을 제안합니다.이 경우 바이클릭은 서브사이퍼에 속하는 키 $K[i,0]$ K [ $K[i,0]$ , 0 $K[i,0]$ ] { $displaystyle K$ [ i , 0 $K[i,0]$ ] 및 $K[i,0]$ $K[0,j]$ [ $K[0,j]$ , $]{$ $displaystyle$ K [ 0 , j $K[0,j]$ displaystyle K [ 0 , $j$ }의 차분을 사용하여 작성됩니다.

순서 3:공격자는 $2^{d}$ 의 $2^{d}$ 암호문( $\$ 을 $2^{d}$ 취득하여 복호화 오라클에 $P_{i}$ 하는 $P_{i}$ $($ $Pi$ \displaystyle P_ ${i$ 을 $P_{i}$ 하도록 요구합니다.

순서 4:공격자는 내부 상태 $(\$ 와 $S_j$ 대응하는 $P_{i}$ Pi(\ $displaystyle P_{$ i $P_{i}$ 를 선택하고 내부 상태 및 플레인텍스트에서 공격함으로써 f $(\displaystyle$ f $)$ $g$ g(\ $displaystyle$ g $)$ 에 $g$ 대해 통상적인 MITM 공격을 수행합니다.

순서 5: $S_{j}$ j $S_{j}$ {\ $displaystyle S_{$ j $S_{j}$ } $P_{i}$ {\ $displaystyle$ P_ ${i$ 에 $S_{j}$ 하는 키 후보가 발견되면 해당 키는 다른 플레인/암호 텍스트 쌍으로 테스트됩니다.키가 다른 쪽 쌍으로 확인되면 키가 올바른 키일 가능성이 높습니다.

공격 예시

다음 예시는 문서 "Biclique Cryptanalysis of the Full^[1] AES"의 AES에 대한 이중 공격에 기초하고 있습니다.
이 예의 설명에서는 공격 작성자가 사용한 것과 같은 용어(변수명 등)를 사용하고 있습니다.
간단하게 하기 위해서, 다음에 설명하는 것은 AES128 배리언트에 대한 공격입니다.
공격은 7라운드의 MITM 공격과 마지막 3라운드를 커버하는 바이클리크로 구성됩니다.

키 파티셔닝

키 공간은 $2^{112}$ 의 112 $({$ 2 $^{112})$ 키 $2^{112}$ 그룹으로 $2^{112}$ 되며 각 그룹은 $2^{16}$ 의 16 $({$ 2 $^{16})$ 키로 $2^{16}$ $2^{16}$ 됩니다.
$2^{112}$ 의 $({$ 2 $^{112})$ 그룹 $2^{112}$ 각각에 대해서, 베이스 계산용의 일의의 베이스 $K[0,0]$ K $]({displaystyle$ K $[0,0])$ 가 $K[0,0]$ 선택됩니다.
base-key에는 다음 표에 나타나듯이2개의 특정 바이트가0으로 설정되어 있습니다(이것은 AES128의 4x4 매트릭스에서 AES와 같은 방법으로 키를 나타냅니다).

(\displaystyle {bmatrix}-&-&-&-&-\\displaystyle {bmatrix}-&-&-&-&-&-end {bmatrix})

그 후 키의 나머지 14바이트(112비트)가 열거됩니다.이를 통해 각 키 그룹에1개씩 2개의 ${$ 2 $^{112}$ 개의 $2^{112}$ 고유한 기본 키가 $2^{112}$ 됩니다.
$2^{16}$ 그룹의 일반적인 $2^{16}$ 의 16 $(\$ 2 $^{16})$ 키는 $2^{16}$ 기본 키에 따라 선택됩니다.기본 키와 거의 동일하도록 선택됩니다.다음 4바이트 중 2바이트( $\displaystyle$ i $i$ 또는 $\displaystyle$ j $j$ 만 다릅니다.

(\displaystyle {bmatrix}-&-&-j&-\displaystyle {bmatrix}-&-&-&-end {bmatrix})

이로써 $]({displaystyle$ 2 $^{8}K$ 및 $]({$ $displaystyle$ 2 $^{8}K$ $2^{16}$ $[0,j$ 가 $2^{8}K[i,0]$ 됩니다. $2^{16}$ 에 의해, $2^{16}$ 의 16 $({$ $displaystyle$ 2 $^{16})$ 의 다른 키 $K[i,j]$ $[i,j$ 가 $2^{16}$ 됩니다 $.$ 기본 키

바이클리시공

$2^{112}$ 112 $({$ 2 $^{112})$ 바이클릭은 $2^{112}$ "쌍곡선 구성 방법" 섹션에 설명된 대로 "독립 관련 키 차등" 기술을 사용하여 구성됩니다.
이 기법을 사용하기 위한 요건은 결합해야 하는 전진 및 후진 미분 궤적이 활성 비선형 요소를 공유하지 않는다는 것이었다.이것이 사실이라는 것을 어떻게 알 수 있을까요?
스텝 1의 키가 기본 키에 대해 선택되는 방법 때문에 $K[i,0]$ [ $K[i,0]$ , $K[i,0]$ 0 $K[i,0]$ ](\ $display$ $\Delta _{i}$ style $K$ [ $i$ , 0 ]) $K[i,0]$ 를 $K[i,0]$ 사용하는 차등트레일은 $\Delta _{i}$ 박스(AES에서 $유일한 비선형$ 컴포넌트 $\Delta _{i}$ )를 공유하지 않습니다 $\nabla _{j}$ $la style$ \ \ $delta$ _ { i } $K[0,j]$ 키 $K[0,j]$ [ 0 , $j$ ] { $displaystyle$ K [ 0 , $j$ ]}을 $\nabla _{j}$ (를) 사용하여 차분 트레일을 XOR하고 바이클라이프를 생성할 수 있습니다 $.$

MITM 공격

바이클리크가 생성되면 MITM 공격이 거의 시작될 수 있습니다.MITM 공격을 실행하기 전에 플레인텍스트로부터의 $2^{d}$ $\$ 2 $^{d}:$
$displaystyle P_{i}{\xrightarrow[{}}{$ $K[i,0]}}{\xright$ 화살표 $[{v_{i$
암호문으로부터의 $(\$ 2 $^{d})$ $2^{d}$ :
${\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}$ $}S_{$ j ${\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}$
단, 대응하는 중간 상태와 $K[i,0]$ K $K[i,0]$ [ i $K[i,0]$ , $]{$ $displaystyle$ K [ i , 0 $]또는$ $K[0,j]$ [ 0 $K[0,j]$ , $]{$ $displaystyle$ K [ $0$ , j ]{ displaystyle K [ $K[0,j]$ , j $K[0,j]$ 는 사전에 계산되어 저장됩니다.

이것으로 MITM 공격을 실행할 수 있게 되었습니다. $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ $K[i,j]$ K [ $K[i,j]$ , $]$ { $displaystyle K$ [ i , j $K[i,j]$ ] $K[i,j]$ $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ v $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ i \ $displaystyle P_{i$ } { \ x $rightarrow$ [ $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ } { } { } ,,, , in in in in in in in of of of of of of of of of of of of of of of of of of of → $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ [ $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ K [ $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ i , $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ , 0 $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ → K [ $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ ][ i ][ i , 0 ][ i ] p p p p [ i ]로 변화하고 있습니다. $K[i,0]}}{\xrightarrow[{v_{$ i}}{}} $P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}$ $P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}$ $P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}$ $P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}$ j]→ $vi$ {\ $style P_{$ i}{\ $xrightarrow[{}}}{K[i,$ j]}}{\ $xrightarrow[{i$ }}}}}{\x}}}}{\xrightarrow[i $J$ 의 후방 $S_{j}$ 디스플레이. $.$ S}}.표시.J.J.S.평판이 나다 $(\$ })에서 $P_{i}$ ${\xrightarrow[{v_{i}}]{}}$ $displaystyle {xrightarrow[{v_{i$ 로의 전송 연산의 경우, 3(재계산의 필요량에 대한 자세한 설명은 이 예에서 인용한 "Biclique Crypt Analysis of full^[1] AES"에서 확인할 수 있습니다).

중간값이 일치하면 $({$ 와 $P_{i}$ $({$ }) $P_{i}$ 의 $S_j$ 키 $K[i,j]$ K $[i,j](i$ j $)$ 가 $K[i,j]$ 검출됩니다.다음으로 키와 후보는 다른 플레인/암호문 쌍으로 테스트됩니다.

결과.

이 공격은 AES128의 계산 복잡성을 2126. $({$ 2 $^{126.18$ 로 낮춥니다.이는 브루트포스 접근법보다 3~5배 빠른 속도입니다.공격의 데이터 복잡도는 $({$ 2 $^{88}),$ 메모리 복잡도는 $({$ 2 $^{8$ 입니다 $2^{{88}}$ .

레퍼런스

^ ^a ^b ^c ^d ^e ^f Bogdanov, Andrey; Khovratovich, Dmitry; Rechberger, Christian. "Biclique Cryptanalysis of the Full AES" (PDF). Archived from the original (PDF) on 2012-06-14.
^ "Narrow-Bicliques: Cryptanalysis of Full IDEA". 2012: 392–410. CiteSeerX 10.1.1.352.9346. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ 프리이미지용 바이클릭:Skin-512 및 SHA-2 패밀리에 대한 공격
^ Diffie, Whitfield; Hellman, Martin E. "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" (PDF).
^ Khovratovich, Dmitry; Rechberger, Christian; Savelieva, Alexandra. "Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family" (PDF).

[BKR-1] ^ ^a ^b ^c ^d ^e ^f Bogdanov, Andrey; Khovratovich, Dmitry; Rechberger, Christian. "Biclique Cryptanalysis of the Full AES" (PDF). Archived from the original (PDF) on 2012-06-14.

[2] "Narrow-Bicliques: Cryptanalysis of Full IDEA". 2012: 392–410. CiteSeerX 10.1.1.352.9346. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[3] 프리이미지용 바이클릭:Skin-512 및 SHA-2 패밀리에 대한 공격

[4] Diffie, Whitfield; Hellman, Martin E. "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" (PDF).

[5] Khovratovich, Dmitry; Rechberger, Christian; Savelieva, Alexandra. "Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family" (PDF).

[1]

[2]

[3]

[4]

[5]

Search