- 암호학 분야 - Brute Force Attack 처럼 모든 값을 대입하는 방식보다 효율적으로 공격을 수행하기 위해 개발
어떠한 두 값 a, b가 있을 때 a와 b를 xor 연산한 결과 값을 차분이라고 한다. 같은 값을 xor 하면 결과는 0이다. 하지만 다른 값을 xor 하면 결과값에 변화가 생긴다 입력값의 변화에 출력값은 변화한다
평문을 작은 부분으로 나누어서 Substitution과 Permutation을 반복 적용한다. 만약 Substitution이 취약하게 설계되었을 경우 Key의 XOR 여부와 관계없이 차분은 유지된다는 성질에서 키를 Brute Force보다 효과적으로 유추할 수 있는 방식
S-box : Substitution 수행 Key(n) : XOR 연산을 수행
S_box
차분 분석 = 차분 공격을 하기 위한 일련의 과정들
- DDT (Differential Distribution Table) 구하기 - Propagation Ratio 구하기 - 차분 경로 구성 (Differential Trace) - 키복구 알고리즘
DDT (Differential Distribution Table)
- 차분 분산 표 (16 x 16 형태)
x ^ x* = x' [입력 차분] S_box(x) ^ S_box(x*) = y' [출력 차분] 일 때,
ex) 16 x 16 표에서 행과 열이 0, 0인 부분은 16이다. 16 x 16 표에서 입력차분이 0이고 출력 차분이 0이 될 수 있는 (x, x*)값이 16개라는 의미
입력 차분과 출력 차분의 관계에 따른 빈도수표 (DDT)
입력차분 값이 1 일때, 출력 차분값들은 3, 7, 9, 10, 12, 13 이 될 수 있다
하지만 균등하지 않으며, 출력되지 않는 수들도 있다
차분 공격은 이 점을 이용한다
특정 입력 차분에는 특정 출력차분이 출력될 확률이 높다 라고 판단할 수 있기 때문이다
신기한 점은, Key와 XOR한 이후의 평문 (x^key)와 (x*^key)가 XOR 하면
Key 값은 사라진다.
그럼 결국 Key에 대해서 입력차분과 출력차분이 일치해진다
즉 모든 라운드에서의 출력 차분은 현재 라운드의 입력차분과 일치하기 때문에 Key값에 영향을 받지 않는다고 볼 수 있다.
Propagation Ratio - 특정 입력차분에 대해서 특정 출력차분이 나올 확률
a' = 입력차분, b' = 출력차분 ( a', b' ) 쌍을 차분이라고 하자 그러면 아래와 같다
입력차분이 ( 0000 1011 0000 0000 ) 라면, 출력차분이 ( 0000 0101 0101 0000 ) 이 될 확률이 27/1024 이다. = 입력차분이 0x0b00 인 평문쌍 1024개를 준비한다면 그 중 27개가 출력차분이 0x0550 이 될 확률이다. => 1024개의 평문쌍을 준비하면 27개의 원하는 출력값을 구할 수 있다
참고 자료
Cryptography Theory and Practice fourth edition - Douglas R. Stinson http://www.secmem.org/blog/2019/04/08/%EC%B0%A8%EB%B6%84-%EA%B3%B5%EA%B2%A9%EC%9D%98-%EC%9D%B4%ED%95%B4/ : 차분 공격의 이해
