[CryptoHack] Diffusion through Permutation

개념 설명

---

순열(Permutation)을 통한 확산.

우리는 S-box 치환이 어떻게 혼란(confusion)을 일으키는지 보았다. Shannon(섀넌)이 설명한 다른 중요한 속성은 "확산(Diffusion)"이다. 이것은 암호 입력의 모든 부분이 어떻게 출력의 모든 부분으로 퍼져야 하는지와 관련이 있다.

 

치환(Substitution)은 그 자체로 비 선형성을 생성하지만 전체 상태에 걸쳐 비선형성을 분산시키지는 않는다. 확산이 없으면 같은 위치에 있는 같은 바이트는 각 라운드에 동일한 변환이 적용된다. 이를 통해 암호 분석가는 상태 행렬의 각 바이트 위치를 개별적으로 공격할 수 있다. 한 바이트에 적용된 치환이 다른 모든 바이트에 영향을 미치도록 상태 행렬을 스크램블링(scrambling)하여 (가역적인 방법으로) 치환을 교체해야 한다.

그러면 다음 S-box에 대한 각 입력은 여러 바이트의 함수가 되며, 이는 매 라운드마다 시스템의 대수 복잡도가 엄청나게 증가한다는 것을 의미한다.

 

! 이상적인 확산의 정도는 평문 텍스트에서 1비트를 변경하면 통계적으로 암호 텍스트 비트의 절반이 변경되는 결과를 초래한다. 이러한 바람직한 결과를 Avalanche effect(눈사태 효과)라고 한다. 

https://en.wikipedia.org/wiki/Avalanche_effect

 

ShiftRows와 MixColumns 단계를 결합하여 이를 달성한다. 이 두 단계는 함께 작동하며 모든 바이트가 단 두 라운드 이내에 상태 배열의 모든 바이트에 영향을 미치도록 한다.

 

ShiftRows는 AES에서 가장 간단한 변환이다. 상태 행렬의 첫 행을 동일하게 유지한다. 두 번째 행은 한 열 위로 이동하여 감싸준다. 세 번째 행은 두 열, 네 번째 행은 세 열 이동한다. 위키백과에 잘 설명되어 있다.

"이 단계의 중요성은 열이 독립적으로 암호화되는 것을 방지하는 것이며, 이 경우 AES는 4개의 독립적인 블록 암호로 변질된다."

 

MixColumns는 더 복잡하다. 상태 행렬의 열과 미리 설정된 행렬 사이에서 Rijndael(레인달)의 갈루아 필드 내에서 행렬 곱셈을 수행한다. 따라서, 각 열의 각 단일 바이트는 결과 열의 모든 바이트에 영향을 미친다. 구현 세부 사항은 미묘한 차이가 있으므로 해당 페이지(https://www.samiam.org/mix-column.html)와 위키피디아(https://en.wikipedia.org/wiki/Rijndael_MixColumns)에 잘 설명되어 있다.

우리는 MixComumns과 ShiftRows연산을 수행하는 코드를 제공했다.

inv_shift_rows를 구현한 후 상태 행렬을 가져와서 inv_mix_columns를 실행한 다음 inv_shift_rowsf를 실행하고 바이트 단위로 변경하면 플래그를 얻을 수 있다.

 

 

문제 풀이

---

def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]


def inv_shift_rows(s):
	s[0][1], s[3][1], s[2][1], s[1][1] = s[3][1], s[2][1], s[1][1], s[0][1]
	s[1][2], s[0][2], s[3][2], s[2][2] = s[3][2], s[2][2], s[1][2], s[0][2]
	s[2][3], s[1][3], s[0][3], s[3][3] = s[3][3], s[2][3], s[1][3], s[0][3]


# learned from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)


def mix_single_column(a):
    # see Sec 4.1.2 in The Design of Rijndael
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)


def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])


def inv_mix_columns(s):
    # see Sec 4.1.3 in The Design of Rijndael
    for i in range(4):
        u = xtime(xtime(s[i][0] ^ s[i][2]))
        v = xtime(xtime(s[i][1] ^ s[i][3]))
        s[i][0] ^= u
        s[i][1] ^= v
        s[i][2] ^= u
        s[i][3] ^= v

    mix_columns(s)


state = [
    [108, 106, 71, 86],
    [96, 62, 38, 72],
    [42, 184, 92, 209],
    [94, 79, 8, 54],
]

from Crypto.Util.number import *

inv_mix_columns(state)
inv_shift_rows(state)

for i in range(len(state)):
	for j in range(len(state[i])):
		print(chr(state[i][j]), end='')

mix columns에 대해서는 더 공부해봐야 할 것 같다.