3중간 미트 인 더 미들

3-subset Meet-in-the-middle 공격(이후 줄임말 MITM)은 해시 및 블록 암호 해독을 위한 암호학에서 사용되는 일반적인 중간 미트 인 더-더-미들 공격의 변형입니다.3 서브셋 배리언트에서는 암호에 대해 MITM 공격을 적용할 수 있습니다.MITM 공격에 따라 키비트를 2개의 독립된 키공간으로 분할하는 것은 간단한 일이 아닙니다.

3-subset 변형은 키 공간의 교차 부분을 두 키 공간 간에 공통되는 키 비트를 포함하는 하위 집합으로 이동함으로써 키 공간이 독립적일 수 있는 제한을 완화합니다.

역사

최초의 MITM 공격은 1977년 Diffie와 Hellman이 DES의 ^[1]암호 해석적 특성에 대해 논의한 기사에서 처음 제안되었습니다.그들은 DES의 키 사이즈가 너무 작아서 다른 키를 사용하여 여러 번 DES를 다시 적용하는 것이 키 사이즈의 해결책이 될 수 있다고 주장했습니다.다만, MITM 공격에 의해, 최소한 더블 DES를 사용하지 말아 주세요(DES는 2개의 서브시페로 분할되기 쉽기 때문에, 더블 DES는 2개의 서브시페로 분할될 가능성이 매우 높아집니다).rs(제1 및 제2의 DES 암호화)는 서로 독립된 키를 사용하여 기본적인 MITM 공격을 가능하게 하고 계산 복잡성을 ${\displaystyle {212}^{}}$$(=$$2$× $)$에서 $2$$$${\displaystyle \times }$ $56$로 줄입니다$.$

Diffie와 Hellman이 MITM 공격을 제안한 이후 많은 변형이 나타났습니다.이러한 변형에 의해 MITM 공격이 보다 효과적이 되거나 기본 변형으로는 사용할 수 없는 상황에서 사용할 수 있습니다.3서브셋 변종은 ^[2]2011년 Bogdanov와 Rechberger에 의해 제시되었으며, 경량 블록 암호 패밀리 KTANTAN과 같은 암호 해독에 사용되고 있습니다.

절차.

일반적인 MITM 공격과 마찬가지로 공격은 다음 두 단계로 나뉩니다.키 절감 단계 및 키 검증 단계.첫 번째 단계에서는 MITM 공격을 적용함으로써 키 후보의 도메인을 줄입니다.두 번째 단계에서는 발견된 키 후보가 다른 플레인/암호 텍스트 쌍으로 테스트되어 잘못된 키를 필터링합니다.

키 감소 단계

키 감소 단계에서는 공격된 암호는 MITM 공격과 마찬가지로$$f\$displaystyle$$f$와 g$\displaystyle$$g$의$$2개의 서브시퍼로 분할됩니다.3 서브셋 공격에서는 2개의 서브시퍼의 키비트가 독립되어 있어야 한다는 제한에 준거할 필요가 없는 대신 2개의 서브시퍼로 암호를 분할할 수 있습니다.여기서 일부 비트는 양쪽 서브시퍼에서 사용할 수 있습니다.

대신 키를 3개의 서브셋으로 분할합니다.즉, 다음과 같습니다.

• ${\displaystyle {A\mathrm{}}_{}}$ 0$(\$ =$$ 두 서브시퍼의 공통 키비트.
• ${\displaystyle {A\mathrm{}}_{}}$ 1$({$ =$$ 첫 번째 서브암호 f$.\displaystyle$ f$.$$와{\displaystyle }$ 구별되는 키비트.$}$
• ${\displaystyle {A\mathrm{}}_{}}$ 2$({$ =$$ 두 번째 서브암호기와 $구별$되는 키비트$$g({$displaystyle$g})

이 시점에서 MITM 공격을 실행하기 위해 다음 절차에 따라 3개의 서브셋이 개별적으로 강제됩니다.

1. $A$ 0$(\$style $A_{0$
   1. ${\displaystyle {A\mathrm{}}_{}}$ 1$${ $display$ style A$_$ {$1$} } $の{\displaystyle {}_{}}$ ----비트의 모든 조합에 대해 플레인텍스트에서 $중간값{\displaystyle }$i { $displaystyle$ i$$}를$$ 계산합니다.
   2. $({$displaystyle $A_{2})$의 모든 키 비트 조합에 대한 중간 값 ${displaystyle$ j$\}$를 계산합니다.
   3. $i{\displaystyle }$$$와$$$j$ 를 $비교$합니다.$일치$가 있을 때$.$저장해두면 핵심 후보입니다.

키 테스트 단계

이제 키 감소 단계에서 발견된 각 키와 후보는 다른 플레인/암호 텍스트 쌍을 사용하여 테스트됩니다.이는 단순히 평문 P의 암호화가 기존의 암호문 C를 생성하는지 확인하는 것만으로 이루어집니다.일반적으로 여기에서는 몇 개의 다른 쌍만 필요하기 때문에 3개의 서브셋으로 이루어진 MITM 공격은 데이터의 복잡성이 거의 없습니다.

예

다음 예시는 KTANTAN 암호 패밀리에 대한 Rechberger 및 Bogdanov의 공격에 기초하고 있습니다.이 예에서는 백서에 사용된 명명 규칙도 사용됩니다.이 공격에 의해 KTANTAN32의 계산 복잡도는 ${\displaystyle {\mathrm{무차별}}^{}}$ ${\displaystyle {\mathrm{공격}}^{}}$과 비교하여 $280$({$displaystyle 2^{$75.170$\})$에서 ${\displaystyle {275.}^{}}$170$({$$displaystyle$ 2$^{80})$으로 감소합니다.계산 복잡도 $({$ 2$^{75.170})$은 2014년의 경우 여전히 깨기 어려우며, 따라서 현재로선 공격이 계산적으로 가능하지 않습니다.KTANTAN48 및 KTAN64도 마찬가지이며, 이 예제의 마지막 부분에서 복잡함을 알 수 있습니다.

공격은 KTANTAN의 비트 단위 키 스케줄에 악용된 취약성으로 인해 발생할 수 있습니다.KTANTAN32, KTAN48, KTANTAN64 모두 동일한 키 스케줄을 사용하기 때문에 해당됩니다.KTANTAN과 KANTAN 간 키 스케줄의 변동으로 인해 관련 KANTAN 계열의 블록사이퍼에는 적용되지 않는다.

KTANTAN의 개요

KTANTAN은 RFID 태그와 같은 제약이 있는 플랫폼용으로 설계된 경량 블록 암호입니다.이 플랫폼에서는 AES와 같은 암호화 프리미티브는 (하드웨어에 의해) 불가능하거나 구현 비용이 너무 많이 듭니다.그것은 2009년에 ^[3]Canniere, Dunkelman, 그리고 Knezevic에 의해 발명되었다.32비트, 48비트 또는 64비트의 블록사이즈를 사용하여 254라운드에 걸쳐 80비트키를 사용하여 암호화합니다.각 라운드는 키의 2비트(키 스케줄에 의해 선택됨)를 라운드 키로 사용합니다.

공략

준비

공격에 대비해 3subset MITM 공격을 허용하는 KTANTAN의 주요 일정의 약점을 파악했다.각 라운드마다 2개의 키 비트만 사용되므로 라운드당 키의 확산은 작습니다. 안전성은 라운드 수에 있습니다.이러한 키 스케줄 구조 때문에 특정 키비트를 전혀 사용하지 않는 연속 라운드를 다수 찾을 수 있었습니다.

더 정확히 말하면, 공격의 작성자는 다음과 같은 사실을 발견했습니다.

• 1~111라운드에서는 k ${\displaystyle {32}_{}}$ ${\displaystyle {\mathrm{k}}_{}}$ 39${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{k}}_{}}$ 44${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{k}}_{}}$61, ${\displaystyle {\mathrm{k}}_{}}$ 66${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {75}_{}}${ $display$ style $k_{32}, k_{39}, k_{44}, k_{611,$k_${75$}의 키 비트는 사용되지 $않습니다.$
• ${\displaystyle {}_{}}$ ~ 254는 k ${\displaystyle {3\mathrm{}}_{}}$,${\displaystyle {}_{}{\mathrm{k}}_{}}$ 20${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}{}_{}}$ k ${\displaystyle {47}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {63}_{}}$ ${\displaystyle {\mathrm{k}}_{}}$ 74$({$}, $k_{63, k_{74})$의 $키{\displaystyle {}_{}}$ 비트를 사용하지 않습니다.

key-schedule의 이 특성은 3서브셋의 MITM 공격을 스테이징하기 위해 사용됩니다.이는 독립된 키비트를 사용하여 암호를 2개의 블록으로 분할할 수 있기 때문입니다.공격 파라미터는 다음과 같습니다.

• ${\displaystyle {A\mathrm{}}_{}}$ 0$(\$ =$$ 두 블록에서 사용되는 키 비트(즉, 위에 언급하지 않은 나머지 68비트)
• ${\displaystyle {A\mathrm{}}_{}}$ 1$({$ =$$ 첫 번째 블록에서만 사용되는 키 비트(라운드 1-프로세서 정의)
• ${\displaystyle {A\mathrm{}}_{}}$ 2$${\$displaystyle A_{2}}$ =$$ 두 번째 블록에서만 사용되는 키 비트(라운드 131-254로 정의)

키 감소 단계

키 감소 단계에서 스텝 1.3에 문제가 발생할 수 있습니다.$i는$111라운드 종료 시 $계산$되고$j$는 131라운드 시작 시 $계산$되므로$$$i$와$j$의$$$값$을 직접 비교할 수 없습니다.이것은, 부분 매칭이라고 불리는 다른 MITM 기술에 의해서 경감됩니다.저자들은 $중간값 i$에서$$전방$,$ $중간값 j$에서 후방으로 계산한 결과 127라운드에서는$$$i$와$j$에서 $모두{\displaystyle }$ 8비트가 변하지 않았으며 확률은$$1이었다.따라서 이들 8비트를 비교하여 상태의 일부만을 비교했습니다(KTANTAN32의 경우 라운드 127에서는 8비트였습니다).123라운드에서는 10비트, 131라운드에서는 47비트(KTANTAN48, KTAN64)였다.이렇게 하면 더 많은 false positive가 생성되지만 공격의 복잡성이 눈에 띄게 증가하는 것은 없습니다.

키 테스트 단계

KTANTAN32는 중간값의 일부 상태에서만 일치하는 폴스 포지티브를 위해 키 후보를 찾기 위해 현재 평균2개의 페어가 필요합니다.KTANTAN48 및 KTAN64는 테스트 및 올바른 키 후보 검색 시 평균 1개의 플레인/암호화 쌍만 필요합니다.

결과.

대상:

• KTANTAN32, 위 공격의 계산 복잡도는 $($디스플레이 스타일 2$^{75.170$인데 반해 철저한 키 검색을 통한 $($ 2$^{80})$입니다.데이터의 복잡성은 3개의 플레인/암호화 쌍입니다.
• KTANTAN48의 계산 복잡도는 $({$ 2$^{75.044})$이며, 2개의 플레인/암호 텍스트 쌍이 필요합니다.
• KTANTAN64는 $({$ 2$^{75.584})$이며, 2개의 플레인/암호 텍스트 쌍이 필요합니다.

결과는 Rechberger와 Bogdanov의 기사에서 가져온 것이다.

더 이상 KTANTAN에 대한 최고의 공격이 아니다.2011년 현재 최고의 공격은 KTANTAN ^[4]패밀리에 대한 MITM 공격을 개선한 Wei, Rechberger, Guo, Wu, Wang 및 Ring에 기여하고 있습니다.계산 $복잡도$는 2 $($ 2$^{72)$에 도달했습니다.$9}}:$ 간접$$ 부분 매칭 및 스플라이스 & 컷 MITM 기술을 사용하여 선택한 4개의 플레인/암호 텍스트 쌍 포함.

메모들