리바운드 공격

리바운드 공격은 암호화 해시함수의 암호해석을 위한 도구입니다.이 공격은 2009년 플로리안 멘델, 크리스티안 레흐버거, 마틴 슐래퍼, 쇠렌 톰슨에 의해 처음 발표되었다.Wolpool 및 Gröstl과 같은 AES와 유사한 기능을 공격하는 것으로 생각되었지만, 나중에 Keccak, JH 및 Skin과 같은 다른 설계에도 적용할 수 있는 것으로 나타났습니다.

공격

리바운드 공격은 해시 함수에 대한 통계적 공격의 일종으로 회전 및 차등 암호 분석 등의 기술을 사용하여 충돌 및 기타 흥미로운 특성을 찾습니다.

공격의 기본 개념은 블록 암호(또는 그 일부), 치환 또는 다른 유형의 프리미티브에서 특정 미분 특성을 관찰하는 것입니다.특성을 만족시키는 값을 찾으려면 $원시$ $E를$ $E=E_{\text{fw}}\circ E_{\text{in}}\circ E_{\text{bw}}$ $E=E_{\text{fw}}\circ E_{\text{in}}\circ E_{\text{bw}}$ bw의 $E=E_{\text{fw}}\circ E_{\text{in}}\circ E_{\text{bw}}$ $=$ E $E=E_{\text{fw}}\circ E_{\text{in}}\circ E_{\text{bw}}$ $E=E_{\text{fw}}\circ E_{\text{in}}\circ E_{\text{bw}}$ 로 $분할합니다({\displaystyle$ $E_{\text{fw$ $}}\$ $circ$ E_ ${\text{in$ }}\ $E_{\text{in}}$ E_ ${\text{w$ $displaystyle E_{\text{fw}}$ $E_{\text{bw}}$ E $E_{\text{fw}}$ $E_{\text{bw}}$ ${$ 를 $E_{\text{bw}}$ 함께 발신 단계라고 부릅니다.그런 다음 공격자는 인바운드 단계에서 차분 특성의 일부를 결정적으로 실현하고 나머지 특성을 확률론적 방법으로 충족하는 값을 선택합니다.

따라서 리바운드 공격은 2단계로 구성됩니다.

인바운드(또는 중간 일치) 단계는 확률론적 방법으로 충족하기 어려운 미분 특성 부분을 포함한다.여기서의 목표는 평균 복잡도가 낮은 특성의 이 부분에 대한 많은 해결책을 찾는 것입니다.이를 달성하기 위해서는 이 단계의 특성을 설명하는 해당 방정식 시스템을 충분히 결정하지 않아야 합니다.해결책을 찾을 때는 자유도가 높아 많은 해결책을 얻을 수 있습니다.인바운드 단계를 여러 번 반복하여 아웃바운드 단계가 성공할 수 있도록 충분한 수의 시작 지점을 얻을 수 있습니다.
아웃바운드 단계에서는 인바운드 단계의 각 솔루션이 양방향으로 외부로 전파되는 동시에 특성이 이 단계에서도 유지되는지 여부를 확인합니다.발신 국면의 특성의 확률은 가능한 한 높아야 합니다.

착신 단계와 2개의 발신 단계를 사용하는 이점은 착신 단계에서 미분 특성의 어려운 부분을 효율적으로 계산할 수 있다는 것입니다.또, 발신 국면에서 높은 확률을 보증합니다.따라서 미분 특성을 찾을 수 있는 전체 확률은 표준 미분 기법을 사용하는 것보다 높아집니다.

AES 유사 압축 함수를 사용한 해시 함수에 대한 공격에 대한 자세한 설명

AES와 같은 치환 변환 블록 암호를 압축 함수로 사용하는 해시 함수를 생각해 보십시오.이 압축 함수는 S박스와 선형 변환으로 구성된 여러 라운드로 구성됩니다.공격의 일반적인 개념은 계산 비용이 가장 많이 드는 부분이 중간에 있는 미분 특성을 구성하는 것입니다.그 후, 이 부분은 착신 국면에서 커버됩니다만, 특성의 실현이 용이한 부분은 발신 국면에서 커버됩니다.착신 단계의 특성을 설명하는 방정식 시스템은 발신 단계의 많은 시작점을 생성할 수 있도록 충분히 결정되지 않아야 합니다.특성 중 더 어려운 부분이 인바운드 단계에 포함되기 때문에 여기서 표준 차분을 사용할 수 있는 반면, 잘린 차분은 더 높은 확률을 달성하기 위해 아웃바운드 단계에서 사용됩니다.

착신 단계에는 일반적으로 처음에 몇 개의 액티브스테이트 바이트(차이가 0이 아닌 바이트)가 있으며, 이후 라운드 중간에 다수의 액티브바이트로 전파된 후 단계 종료 시 적은 수의 액티브바이트로 돌아갑니다.이 아이디어는 위상 중간에 S박스의 입출력 시 많은 액티브바이트를 갖는 것입니다.그런 다음 인바운드 단계의 시작과 끝의 차이에 대한 값을 선택하고, 중간을 향해 전파하고, S 상자의 입출력에서 일치하는 값을 찾아냄으로써 특성을 효율적으로 계산할 수 있습니다.AES와 같은 암호의 경우 일반적으로 행 또는 열 단위로 수행할 수 있으므로 절차가 비교적 효율적입니다.다른 시작 값과 종료 값을 선택하면 착신 단계에서 많은 차이 특성이 발생합니다.

아웃바운드 단계에서는 인바운드 단계에서 발견된 특성을 앞뒤로 전파하고 원하는 특성을 따르는지 여부를 확인하는 것이 목표입니다.여기서, 잘린 미분은 더 높은 확률을 제공하기 때문에 일반적으로 사용되며, 차이의 구체적인 값은 충돌을 찾는 목적과 무관하다.발신 단계의 원하는 패턴을 따르는 특성의 확률은 활성 바이트의 수와 특성 내에서의 배치 방법에 따라 달라집니다.콜리젼을 달성하려면 , 발신 국면의 차분 타입이 특정의 것이 아니고, 특성의 개시와 종료의 액티브한 바이트도, 피드 전송 조작이 취소되도록 값을 설정할 필요가 있습니다.따라서 특성을 설계할 때는 발신 단계의 시작과 끝의 액티브바이트 수가 같은 위치에 있어야 합니다.이러한 바이트가 취소될 확률은 발신 특성의 확률을 높입니다.

전체적으로, 발신 국면에서 1보다 큰 올바른 특성을 예상 수만큼 취득하기 위해서는, 착신 국면에서 충분한 수의 특성을 생성할 필요가 있습니다.또한 취소되지 않는 여러 활성 바이트로 아웃바운드 단계를 시작하고 종료하면 더 많은 라운드에서 거의 충돌할 수 있습니다.

소용돌이 공격 예시

Rebound Attack은 해시함수 Wallepool에 대해 압축함수(AES 유사 블록 암호, W)가 4.5 라운드 또는 5.5 라운드로 감소된 변형에서 충돌을 찾기 위해 사용할 수 있습니다.근접 충돌은 6.5 라운드와 7.5 라운드에서 찾을 수 있습니다.다음은 4.5라운드 공격에 대한 설명입니다.

사전 계산

솔루션 수	빈도수.
0	39655
2	20018
4	5043
6	740
8	79
256	1

리바운드 공격을 효과적으로 하기 위해 공격 전에 S박스 차이에 대한 룩업 테이블을 계산한다. $S:\{0,1\}^{8}\to \{0,1\}^{8}$ : $S:\{0,1\}^{8}\to \{0,1\}^{8}$ { $S:\{0,1\}^{8}\to \{0,1\}^{8}$ 0 , $S:\{0,1\}^{8}\to \{0,1\}^{8}$ $S:\{0,1\}^{8}\to \{0,1\}^{8}$ $S:\{0,1\}^{8}\to \{0,1\}^{8}$ $S:\{0,1\}^{8}\to \{0,1\}^{8}$ { $S:\{0,1\}^{8}\to \{0,1\}^{8}$ , $S:\{0,1\}^{8}\to \{0,1\}^{8}$ $S:\{0,1\}^{8}\to \{0,1\}^{8}$ { { { $displaystyle$ S : \ { $0$ , 1 \ }^ $8}$ \ $to$ \ { $0$ , 1 \ }^ $8}$ 은 $S:\{0,1\}^{8}\to \{0,1\}^{8}$ S-box를 나타냅니다.다음으로 $(a,b)\in \{0,1\}^{8}$ 각 $(a,b)\in \{0,1\}^{8}$ b) $(a,b)\in \{0,1\}^{8}$ { $(a,b)\in \{0,1\}^{8}$ , $(a,b)\in \{0,1\}^{8}$ $(a,b)\in \{0,1\}^{8}$ 8 {{ $displaystyle$ ( $a,$ b)\ $in$ \{ $0,1\}^$ 8 $}}$ 에 대해 방정식의 해 $x$ (있는 $경우$ )를 찾습니다. $x}($ 있는 경우)를 찾습니다.

S(x)\oplus S(x\oplus a)=b

(

S(x)\oplus S(x\oplus a)=b

)

S(x)\oplus S(x\oplus a)=b

(

S(x)\oplus S(x\oplus a)=b

)

S(x)\oplus S(x\oplus a)=b

\

displaystyle

S (

x

) \

oplus S

( x \

oplus

a ) =

b

} ,

$a$ 서\ $displaystyle$ a는 입력 차이를 $b$ b $\displaystyle$ b는 S 상자의 출력 차이를 나타냅니다 $b$ .이 256 x 256 테이블(차분포 테이블, DDT라고 불립니다)을 사용하면 S박스를 통과하는 특정 입력/출력 쌍의 특성을 따르는 값을 찾을 수 있습니다.오른쪽 표에는 방정식에 대한 가능한 솔루션 수와 발생 빈도가 나와 있습니다.첫 번째 행은 불가능한 차분을 나타내며 마지막 행은 0-차분을 나타냅니다.

공격의 실행

Wolpool 4.5 라운드에서 충돌을 찾으려면 아래 표와 같은 유형의 차동 특성을 찾아야 합니다.이 특성에는 빨간색으로 표시된 최소 활성 바이트(차이가 0이 아닌 바이트)가 있습니다.특성은 각 라운드의 활성 바이트 수로 설명할 수 있습니다(예: 1 → 8 → 64 → 8 → 1 → 1).

4.5라운드의 월풀 해시함수에서 잘린 미분특성.
$E_{\text{bw}$
$\displaystyle E_{\text{in}}$
$\displaystyle E_{\text{fw}}$

착신 단계

인바운드 단계의 목표는 활성 바이트 8 → 64 → 8의 시퀀스로 설명되는 특성의 일부를 충족하는 차이를 찾는 것입니다.이것은, 다음의 3개의 순서로 실행할 수 있습니다.

라운드 3의 MixRows 연산 출력에서 8개의 활성 바이트에 대해 0이 아닌 임의의 차이를 선택합니다.다음으로 이러한 차이는 라운드3의 서브바이트 조작의 출력으로 역방향으로 전파됩니다.MixRows 작업의 속성으로 인해 완전히 활성 상태가 됩니다.이 작업은 각 행에 대해 독립적으로 수행할 수 있습니다.
라운드 2의 MixRows 연산 입력에서 각 활성 바이트에 대한 차이를 선택하고 이러한 차이를 라운드 3의 SubBytes 연산 입력으로 전파합니다.각 바이트의 255가지 차이 모두에 대해 이 작업을 수행합니다.이 작업은 각 행에 대해 독립적으로 수행할 수 있습니다.
match-in-the-middle 스텝에서는 DDT 테이블을 사용하여 라운드3의 SubBytes 연산과 일치하는 입력/출력 차이(스텝1과 2에서 확인)를 찾습니다.각 행은 독립적으로 확인할 수 있으며 예상되는 솔루션 수는 S박스당 2개입니다.미분 특성을 따르는 예상 값의 수는 총 2개입니다⁶⁴.

이러한 스텝은 스텝1에서 2개의 다른⁶⁴ 시작값을 사용하여 반복할 수 있습니다.그 결과, 착신 단계의 차분 특성을 따르는 실제 값은 합계 2개가 됩니다¹²⁸.2개의⁶⁴ 값의 각 세트는 계산 전 단계로 인해 2개의 라운드로 이루어진 복잡한⁸ 변환으로 찾을 수 있습니다.

발신 단계

아웃바운드 단계는 확률론적 방법으로 미분 특성을 완성한다.아웃바운드 단계는 인바운드 단계가 아니라 잘린 차분을 사용합니다.착신 국면에서 발견된 각 시작점은 전방 및 후방으로 전파됩니다.원하는 특성을 따르려면 8개의 액티브바이트가 양방향으로 단일 액티브바이트로 전파되어야 합니다.이러한 8:1 전환 중 하나는 ^[1]2의⁻⁵⁶ 확률로 발생하므로 특성을 충족하면 2의 확률이⁻¹¹² 있습니다.충돌을 방지하려면 특성 시작 및 끝 값이 피드포워드 작업 중에 취소되어야 합니다.이것은 약 2의⁻⁸ 확률로 발생하며, 따라서 아웃바운드⁻¹²⁰ 단계의 전체 확률은 2입니다.

충돌을 찾으려면 인바운드¹²⁰ 단계에서 2개의 시작 지점을 생성해야 합니다.이것은 ^[2]시작점당 평균 1의 복잡도로 실행할 수 있기 때문에 공격의 전체 복잡도는¹²⁰ 2입니다.

공격의 확장

기본 4.5라운드 공격은 착신 국면에서2개의 완전 액티브스테이트를 사용함으로써 5.5라운드 공격까지 확장할 수 있습니다.이것에 의해, 복잡도는 약¹⁸⁴ ^[3]2로 증가합니다.

발신 단계를 8개의 활성 바이트로 시작하여 종료하도록 확장하면 Wilpool에서 52바이트의 충돌이 7.5라운드로 감소하며 복잡도는 ^[4]2가¹⁹² 됩니다.

공격자가 체인 값을 제어하고 이에 따라 월풀의 키 스케줄에 대한 입력을 제어한다고 가정하면 공격이 복잡도 ^[5]2의¹²⁸ 52바이트에 대한 세미 프리 스타트 근접 충돌로 9.5라운드까지 확장될 수 있습니다.

메모들

^ Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 18
^ Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 22
^ Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 25
^ Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 25
^ Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 31

레퍼런스

리바운드 공격: Florian Mendel, Christian Rechberger, Martin Schlaffer 및 Soren S에 의한 소용돌이 감소 및 그뢰스틀 암호 분석.Thomsen (고속 소프트웨어 암호화 2009: 260-276)
Florian Mendel, Christian Rechberger, Martin Schlaffer 및 Soren S에 의한 감소된 Gröstl 해시 함수에 대한 리바운드 공격.Thomsen (RSA Conference 2010 암호 기술자 트랙: 350-365)
Unaligned Rebound Attack - Alexandre Duc, Zian Guo, Thomas Peirin, Lei Wei에 의한 Kecak에 대한 신청 (ICR 암호학 ePrint 아카이브 2011년 / 420년)
스위스 Windisch, Maria Naya-Plasencia FHNW의 리바운드 공격을 개선하는 방법 (제31회 암호학 발전 연례회의 188-205페이지)
The Rebound Attack and Subspace Distinguishers: Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen 및 Martin Schléffer(IACC 암호학 ePrint Archive, Year)의 월풀 응용 프로그램.2010 /198).
AES 기반 해시함수의 암호해석 Martin Schléffer 박사논문

[1] Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 18

[2] Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 22

[3] Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 25

[4] Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 25

[5] Lamberger, Mendel, Rechberger, Rijmen, Schléffer, 2010, 페이지 31

[1]

[2]

[3]

[4]

[5]

Search