취약한 암호화 알고리즘이 보안에 취약한건 알고 있다. 그런데 갑자기 궁금해졌다.
1. 왜 취약한 암호화 알고리즘을 쓰면 안돼?
2. 그럼 어떤 암호화 알고리즘을 써야 해?
알아보자.
1. 왜 취약한 암호화 알고리즘을 쓰면 안돼?
소프트웨어 보안약점 진단가이드(2021)에는 아래와 같이 나와있다.
가이드 링크 (https://www.kisa.or.kr/2060204/form?postSeq=9&page=1)
취약한 암호화 알고리즘은 아래와 같다.
base64, RC2, RC4, RC5, RC6, MD4, MD5, SHA1, DES
쉽게 뚫리니까 위험하다. 그렇다면 얼마나 간단하게 복호화 될까?
를 알기 위해 DES 암호화 알고리즘에 대해 아주 간략하게 알아보았다.
쉬운 결론으로부터 역으로 정확한 이유를 도출해 보자.
DES 암호화 알고리즘은 취약하다. 왜? => 짧은 키 길이를 사용하기 때문이다.
왜 짧은 키 길이를 사용하는게 위험할까? => DES 암호화 알고리즘 중, 비선형 방식과 선형 방식 로직이 존재한다. 선형 방식은 XOR, 자리바꿈, 순환이동, 등으로, 역으로 계산할 수 있다.
선형 방식은 역을 구할 수 있다. 고정된 표를 사용하기 때문이다.
엥? 그러면 그냥 표를 보고 나도 역으로 찾을 수 있다는 거면 쉬운거 아닌가요? 아니다. 이런 기준으로 쉽게 계산 할 수 있다는 말은 아니다.
예를 들어. DES 알고리즘 과정 중, 초기 순열 변환(초기 치환, initial permutation)은 P-BOX를 사용해 이루어지는데,
전치(Transpose)에 사용되는 P-BOX
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
이 P-BOX를 사용해 32비트의 출력 비트를 섞는다.
초기 순열을 위해 사용하는 P-BOX
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
초기 순열 변환 과정에서 위의 P-BOX를 사용한다.
즉, 16번 라운드에서 초기 순열 변환 시, 동일한 P-BOX를 사용한다.
선형적 방식은 연산 결과의 역을 구하는 방법이 존재하고, 쉽진 않지만(표 보고 하나씩 찾기) 가능은 하다.
따라서 암호화 단계인 얼마나 이 암호를 풀기 어려운가? 에 대해 적용되는 것은 비선형적인 방식을 어떻게 사용하느냐가 중점인 것이다.
치환은 S-BOX를 사용한다. 이는 비선형적인 방법이다.
비선형 방식은 역으로 계산하기 까다롭다.
여기서, 역으로 계산하는 게 까다로운 이유를 알아보자.
S-BOX의 특성이 뭘까?
- 입력과 출력 비트의 비선형적인 관계: 하나의 입력 비트 변경이 출력 비트에 대하여 복잡하고 예측하기 어려운 변화를 일으킵니다.
- 암호학적 안전성 강화: 비선형성은 암호화 알고리즘의 안전성을 높입니다. 간단한 선형 관계가 존재한다면, 암호화를 해독하는 데 사용될 수 있는 패턴이나 구조가 생길 수 있습니다.
- 키와 결합하여 보안 강화: S-Box는 키 일부와 결합하여 사용되어, 키 일부의 변화가 최종 출력에 미치는 영향이 큽니다. 이는 전체 DES 알고리즘에서 키 일부와 라운드 함수 등이 결합되어 보안성을 강화하는 구조 중 하나입니다
S-Box은 아래 방식으로 비선형성을 달성한다.
- 비트 치환 표: S-Box는 비트 치환 표를 사용하여 입력 비트의 특정 패턴에 대해 미리 정의된 출력 값을 반환합니다. 이 표는 수학적인 공식이나 선형 관계를 피하기 위해 특별히 구성되어 있습니다.
- 비트 조합: S-Box는 입력 비트를 여러 부분으로 나누고, 각 부분에 대해 복잡한 비트 연산을 수행합니다. XOR, AND, OR 등의 비트 연산을 조합하여 복잡한 비선형성을 만듭니다.
- 퍼뮤테이션(Permutation): S-Box의 출력은 입력 비트의 특정 순서로 재배열될 수 있습니다. 이렇게 함으로써 입력과 출력 간의 관계를 더욱 복잡하게 만듭니다.
- 키와의 결합: DES에서는 S-Box에 대한 입력 중에서 일부 비트가 특정 키와 결합되어 입력됩니다. 이렇게 하면 동일한 입력이라도 키에 따라 출력이 크게 바뀌게 됩니다.
... 솔직히 뭔소린지 모르겠다.
그러나 비 선형성이 입/출력 결과가 예측할 수 없다고 한다.
위의 비선형성을 만족하기 위해 사용하는 비트 치환 표는 입/출력에서 사용되는 비트 수가 다르다고 한다. 이 말은 단순히 4비트가 나왔으니 8비트를 썻을꺼야! 이걸 찾아내는 게 아니라, 어떤 8비트를 사용했는지를 찾아내야 하므로 선형적인 방식보다는 더 어렵다.
잠깐! 이게 선형적인 방식에 비해 역을 찾아내는 것이 어렵다는 것이지, 불가능하다는 게 아닐 것 같다. 왜냐하면 S-BOX는 고정된 표를 사용한다고 알고 있기 때문이다. 물론 얼마나 시간과 노력을 들여(자원을 사용해) 역을 찾을 수 있느냐가 관건일 것이다.
S-BOX가 각 단계마다 고정된 S-BOX 표를 사용한다면, 이 S-BOX 표를 알아낸다면, 역을 찾아내는게 쉽지 않을까?
=> S-BOX는 키 일부와 결합되어 사용된다. 따라서 키 마다 다른 S-BOX가 사용되므로 역을 찾는 자원(시간과 노력)이 더 배가 될 것이다.
아니 그럼 키를 찾으면 S-BOX 표를 알아 낼 수 있지 않을까?
=> 맞다. 키가 유출된다면 S-BOX 표를 알아내, 암호문을 해독할 수 있다. 그러나, 이 과정도 매우 어렵다.
1. 16번의 라운드에서 키의 일부가 S-BOX 생성에 관여한다.
=> 키 값을 알아낸다고 해도, 16번 중, 어떤 라운드에서 키 가 사용됬는지 알아내야 한다. (자원 사용 + )
2. DES 라운드 함수에 의해 동적으로 DES 키 일부와 S-BOX간의 관계가 결정된다.
그럼에도 불구하고, 컴퓨터 계산 능력이 향상되면서 무차별 대입 공격등으로 이러한 계산을 적절한 수준의 자원을 사용해 계산이 가능하다.
결론
DES 암호화 알고리즘이 취약한 이유?
해당 알고리즘에서 사용하는 암호 로직 중, 선형적인 방식(DES 암호화 알고리즘의 핵심)은 키 값을 사용한다. 그러나 이 키 값이 유출된다면, 또는 이 키 값을 유추할 수 있다면, DES 암호화 알고리즘의 로직을 파악할 수 있을 것이다. 따라서 DES 암호화 알고리즘에서 사용하는 키 값의 길이가 56bit이다. 이는 현대 컴퓨터 능력(해독에 필요한 많은 자원이 필요하지 않다)으로 적절한 자원으로 해독 가능하다. 따라서 DES 암호화 알고리즘 취약한 알고리즘이다.
암호화 로직은 얼마나 역으로 계산 하는게 어려운가가 해당 로직의 안전성을 나타내는 척도이다. 그러나 컴퓨터 계산 능력의 발전으로 56bit의 키 길이를 사용하는 DES 암호화 알고리즘은 이제 계산이 더 쉬워졌기 때문(컴퓨터 성능 발전, 새로운 공격 기술)에 취약한 암호화 알고리즘으로 변모된 것이라고 본다.
높은 안전성을위해 훨씬 큰 키 공간을 사용해야할 것이다.
출처
2022 정보보안기사(임호진 저), 네이버 지식백과, Chat GPT 3.5, 네이버 블로그 등..
