눈사태 효과
1. 소개
Avalanche Effect
암호학 용어. 원문(Plaintext)의 한 비트의 변화가 최종 암호문(Ciphertext)에 큰 변화를 주는 효과이다. 모든 암호에서 핵심적으로 요구되는 암호학적 특성이다. 특히 블록 암호나 단방향 해시 함수에서 주로 요구한다.
'눈사태 효과'라는 단어는 유명 암호학자 호르스트 파이스텔(Horst Feistel)이 처음 사용했으나, 개념 자체는 클로드 섀넌까지 거슬러 올라가는 꽤 오래된 개념이다.
2. 역사
통상적인 고대 암호는 카이사르 암호나 초창기 암호는 특정 패턴이 있으며 그 패턴을 뚫는 순간 암호 그 자체가 뚫리는게 단점인데, 일일이 사람이 계산을 해야 하는 고대 시기와는 달리 현대 컴퓨터의 계산 능력이 상상을 초월하기에 현대에는 이 암호를 푸는데 별로 시간이 들지 않는다. 따라서 암호를 만들 때 모든 경우의 수를 다 계산해보지 않는 이상 결과를 알 수 있다는 보장을 할 수 없게 해야 하며 이를 위하여 눈사태 효과 개념이 도입되었다.
단적인 예로 단방향 함수인 SHA-1을 예시로 들어보자면 아래와 같다.
원문은 1비트만 바뀌었지만 암호문은 총 86비트가 바뀌었으며, 전체 160비트의 53.75%이다. 하지만 이를 카이사르 암호나 다른 초창기 암호를 이용하여 암호문을 만들었다면 앞 부분이 같기에 반드시 동일한 부분이 있을 것이며, 평문과 이런 암호로 짠 암호문 모두를 누군가가 알 수 있다면 암호 체계가 너무나도 무기력하게 뚫릴 수 있다. 눈사태 효과는 이런 상황을 막기 위한 것이다.
3. 구현법
사실 정형화된 구현법은 존재하지 않는다. 눈사태 효과는 그저 효과 그 자체만을 의미할 뿐 알고리즘등을 제시하지는 않는다. 다만 개념적으로는 평문을 암호화 하는 과정에서 블럭 암호를 이용할 경우 블럭단위를 자르고, xor연산을 하고 이를 key에 사용한 다음에 OFB나 CBC, CFB 등의 암호 운용 방식을 통하여 이런식으로 암호화 된 문장을 다시 일정한 패턴을 통하여 위치를 교환하는 등의 방식을 통하는 경우나 Substitution Box(통칭 S-box)를 통하여 값을 변화시키는 등의 방식을 사용하여 눈사태효과를 발생시킨다. 2000년대에 들어서는 새로운 암호학 알고리즘을 개발하기 보다는 기존의 암호 방식에 취약점을 찾고 이러한 눈사태효과를 극대화 시켜 보안성을 높이는 연구나 운용 방식의 변화 등에 대한 연구와 논문이 활발하게 나오는 중이다.
4. 대표적인 암호 알고리즘
눈사태 효과를 단적으로 볼 수 있는 암호 알고리즘으로는
등이 있다. 사실상 암호 알고리즘이나 현실에서 사용되는 암호 알고리즘은 대부분 눈사태 효과가 디폴트 옵션이라고 생각하고 봐도 무방하다.
5. 관련 문서
[1] Sponge구조라면서 text를 늘였다 줄였다 하면서 정말로 난 단방향 해시다! 를 외치는중.