[보안 프로토콜] Triple-DES, AES 소개 - Part 1

표준 블록암호인 Triple DES 및 AES 256에 관하여 공부한다. 

DES

• Data Encription Standard의 약어이다.
• 1977년도 미국 표준 블록 암호로 재정되었다.
• 전 세계적으로 차분 분석, 선형분석에 의해서 안전하지 않음이 밝혀졌다.
• 1999년도에 DES가 56bit 키를 사용하기 때문에 22시간 15분만에 뚫린다는 사실이 밝혀졌다.
• Single DES 시스템은 legacy 시스템에서만 사용해야하며 이후 Triple DES를 사용했다.
• DES를 대체할 표준 암호 공모전을 통해 AES가 미국 표준 암호로 지정되었다.

• NIST (National Institude Technology) 표준 암호로 AES와 TDES가 지정되어있다.
• ISO/IEC 에는 위와 같은 9종의 블록 암호가 있다. PRESENT와 CLEFIA는 경량 블록암호로 지정되어있다.

• DES는 Data Encryption Standard의 약어이다.
• 56비트 키와 64비트 평문을 입력받아서 64비트 암호문을 출력하는 함수 (대칭형 블록암호) 이다.
• DES 알고리즘에서 사용되는 함수로는 대체 역할의 S-box와 치환 역할을 하는 E 확장 함수와 P 테이블이 있다.
• 대다수가 claude shanon이 제시한 혼돈과 확산 두가지 개념에 기반하여 개발되었다.

• 위 이미지는 전체 DES에 대한 암호화 구조이다.
• 64비트 평문이 입력으로 들어온다.
• 왼쪽과 오른쪽에 32비트 단위로 짤려서 들어온다.
• IP는 간단한 함수인데 64개의 비트의 위치를 바꿔주는(꼬와준다) 역할을 한다.
• F함수를 거친 오른쪽 비트와 왼쪽 비트가 XOR 연산된다.
• 페이스텔 구조를 만족하여 암호문을 입력하여 평문을 찾아낼 때 FP는 IP의 역함수이기 때문에 같은 과정을 반대로 적용하여 복호화가 이루어진다.
• 결론은 암호화 칩 하나만 있으면 암/복호화 모두 구현할 수 있다.

• 키 스케줄은 키를 받아서 라운드 키를 만드는 함수이다.
• DES는 56비트 키를 입력으로 받아서 48비트 키 16개로 만든다.
• 매번 48키가 필요하기 때문에 16라운드가 필요하기 때문이다.
• 56비트 키가 64비트 키로 확장된다. 간단하게 56비트는 7비트 열로 8개로 쪼갤 수 있다.
• 7비트 모두를 XOR 해서 8비트를 만들어서 총 64비트를 추출한다.
• 이러한 방식으로 라운드 키를 뽑아낸다.

 

Triple DES

• DES를 3번 중첩해서 암호화 시킨다.

• 좌측(옵션1)의 경우 모두 다른 Key1, Key 2, Key 3 를 사용해서 암호문을 생성하는 버전이다. 56 * 3에 해당하는 비트를 키로 받음.
• 우측의(옵션2)의 경우 Key1, key3가 같기 때문에 56 * 2에 해당되는 112비트가 키로 사용된다.
• DES의 키 길이가 짧다는 문제로 인해 Triple DES를 사용하는 것이었다.
• 키가 길어져서 해독이 어려워 졌다.

• AES는 DES를 대신하여 1977~1999까지 표준으로 사용되었다.
• 공모전 할 때 전세계에서 16개의 대칭 암호 알고리즘을 제안하였다.
• 벨기에 산 Rijndael 대칭 암호 알고리즘이 선정되었다.
• 블록 길이가 128비트이고 키의 비트길이는 128, 192, 256으로 선택할 수 있으며 키 길이에 따라 라운드가 구분된다.
• 128비트와 192는 민간영역에서 256비트는 국방용으로 사용할 것을 권장한다.
• 키 비트열이 길어질수록 전수조사가 어려워지기 때문이다.

• Plane text (128비트)가 입력으로 들어오면 화이트닝 키라는 라운드 키를 사용한다.
• 다음과 같은 과정을 거친다.

 

블록암호 안전성 분석 방법

• 알고리즘 설계자가 자신이 만든 암호의 안전성을 보장하기 위해 사용된다
• 특적 암호의 안전성을 깨기 위해서도 사용된다.
• 사이퍼의 안전성을 보장할 수 있는 방법?
• RSA 암호의 경우 큰 소수 두개를 곱해둔 결과값이 주어졌을때 두 소수를 찾을 수 있는가? 의 어려움에 안전성이 보장된다.
• 즉, 수학적인 난제에 기반하여 설계된다.
• 대칭 암호는 현재까지 알려진 공격과 미래의 안전성까지도 포함할 수 있어야 한다.

• 코콘오프 학자는 강력한 암호는 어떠한 경우에도 안전해야 한다.
• 공격자가 키 정보만 빼고 모든 것을 다 알고 있을 때 안전하다면 강력한 암호라고 말할 수 있다.
• 암/복호화 칩이 있을 때 칩 안에 AES 혹은 DES가 탑재 되어 있다고 가정해보자!
• 공격자는 암호화 칩의 평문을 넣어보고 암호문을 뽑아낼 수 있을 것이다.
• 이런 환경에도 불구하고 키를 찾아낼 수 없다면 안전한 암호이다.

• 가능한 공격 시나리오는 다음과 같다.
• 흘러가는 암호문을 수집해서 키를 찾거나 평문을 복원하는 공격법
• 암호화 칩이 주어졌을 때, 평문을 랜덤하게 선택해서 암호문을 얻은 후 키를 찾음
• 선택된 평문에 대한 암호문을 얻어서 키를 찾음
• 평문을 선택해서 암호문을 얻고 암호문을 선택해서 평문을 얻음. 암/복호화 칩을 둘다 갖고 있는 경우 키를 찾을 수 있는가.
• 아래쪽으로 갈수록 비현실적이지만 이와 같은 상황에 대비되었다면 강력한 암호라고 말할 수 있다.

• 블록 암호의 분석방법은 크게 3가지가 있다.
• 키를 찾거나, 평문을 찾거나, 암호문이 어떤 암호 알고리즘을 통해 나왔는지 구분하거나
• 키 공격이 뚫리면 평문 복원은 시간 문제이다.
• 평문이 복원되면 구분 공격은 당연히 뚫린다.

공격법?

• 출력된 암호문이 난수열과 유사한 구조를 가져야 한다. 암호알고리즘이 어느정도 안전성을 확보했다.
• 일반적인 공격에는 키에 대한 전수조사, 사전 공격(모든 사전 자료에 대응되는 암호문을 찾는다), 시간과 메모리를 많이 사용하는 방법이다. 시간과 메모리에 적당히 trade-off하는 공격법도 존재한다.
• 블록암호의 대수적 성질을 활용한 공격법이 존재한다.
• side-channel attack은 부가적인 정보, 전력 사용량, 시간 등을 활용하여 키를 찾아내는 방법이다.
• 통계적인 수치를 활용하여 공격하는 방법이다.

• 차분 공격은 두 값의 차이를 활용하여 공격하는 방법이다. 두개의 평문에 차이점을 만들어 둔 후에 암호문에 차이가 어떻게 반영되는지 추적한다.
• 리니어 공격은 평문, 암호문, 라운드 키에 적당한 비트열을 뽑아서 전부다 XOR 연산한다. 0이 될 확률이 1/2보다 크거나 작으면 공격이 될 수 있다.
• 연관키 공격은 차분 공격에 연관된 키를 넣어서 공격하는 방법이다. 예를 들어 두개의 암호화 칩이 있을 때 서로다른 키를 사용하고 있다면 해당 키를 찾을 수 있는지에 관한 의문이다.

DES의 안전성 분석

• single des의 경우 차분 공격과 선형 공격에 이미 취약하는 것이 발견되었다.
• DES는 키 길이가 56비트여서 브루트 포스 공격에 취약하다.
• complementation property 성질을 갖고 있어서 평문의 비트열을 반전시킨다.

전수조사 양을 반으로 줄일 수 있다.

• triple des의 경우 3개의 키를 사용하는 경우 56비트 키 3개여서 168비트의 키를 사용한다.
• 키에 대한 전수조사를 위해 2^168번이 필요하다.
• in the middle attack이라는 공격법을 사용하면 2^113번을 통해 공격할 수 있다.
• 위와 같은 안전성을 갖고 있다.

AES의 안전성 분석

• AES의 경우 현재 까지 알려진 공격법이 있다.
• 그중 하나가 연관키 부메랑 공격이다.

• 연관키 부메랑 공격은 AES가 키스케줄을 느슨하게 사용하였기 때문에 키스케줄의 특성과 라운드 함수의 특성을 활용하여 풀라운드 공격이 가능해졌다.

• 128비트가 전체 14라운드를 사용하는데 타임라인을 보면 2^119로 떨어진다.

• 데이터량은 평문을 넣고 암호문을 획득하는 과정을 2^119번을 한다 (비현실적이다)

결론

• 현재까지 Triple DES 혹은 AES가 안전성에는 문제가 없으나 효율성 측면에서 보면 AES가 훨씬 좋다.