한국통신학회 KICS

AI 기반 암호 분석 기술 소개 

대구경북과학기술원 문인규 교수

  인공지능 (AI) 기술의 발전은 사물인터넷 (Internet of things) 기반 통신으로 인해 대량의 데이터 수집이 가능해진 환경에서 데이터 학습을 용이하게 하기에 다양한 환경에서 AI 기반 플랫폼이 활용되고 있다. 이러한 신기술의 등장은 사이버 공격 기법을 한층 다양화하고 있으며, 이 중 최근 암호설계 및 분석 분야로도 그 응용 범위가 확장되어가고 있다. 특히, 암호분석 (Cryptanalysis) 기술이란 암호 알고리즘에 대한 안전성 분석을 수행하는 기술로써, 암호 알고리즘의 특성 및 패턴을 분석하고 이를 통해 비밀키를 보유하고 있지 않은 상태에서도 암호문에 대응하는 평문 혹은 비밀키 값을 복구하려는 일련의 시도들을 의미한다. 이러한 암호분석 기술은 암호 알고리즘의 구조를 분석하고 비밀키 후보군 (Key candidate) 리스트를 생성하여 공격하는 기술로서 단순 전수조사 (Brute-force attack) 에 비해 작은 연산량으로 비밀키를 복구할 수 있게 한다. 그러나 이러한 기존의 수학적 논리 기반의 암호분석 기술은 알려지지 않은 다양한 암호문 공격 발생 시 이를 대처하기 위해서는 현실적인 큰 어려움이 존재한다. 특히, 상기 언급한 AI 기술은 이미지, 음성인식 등의 특정 데이터에 대한 자동분석을 통해 실제와 거의 동일한 가상 데이터 생성 등을 가능하게 하고 있다. 이러한 AI 기술의 발전은 어느 순간 갑자기 기존의 암호체계에 큰 위협으로 다가올 수 있기 때문에, 수학적 논리에만 의존하는 것이 아닌 AI 기반 암호분석 기술에 대한 연구가 필요하다.

그림1. 암호문 단독 공격과 기지 평문 공격 상에서의 공격자의 관점 및 능력
​

  암호시스템 (Cryptosystem) 의 약점을 찾아내고 파악하여 암호문 (Ciphertext) 의 특성을 분석하고, 이를 통해 해당 암호문에 대응하는 평문 (Plaintext) 또는 암호키 (Encryption key) 를 추출하는 암호분석 기술은 다음과 같이 크게 4가지로 나눌 수 있다; 1) 암호문 단독 공격 (Ciphertext only attack), 2) 기지 평문 공격 (Known plaintext attack), 3) 선택적 평문 공격(Chosen plaintext attack), 4) 선택적 암호문 공격 (Chosen ciphertext attack). 아래 그림 1은 암호문 단독 공격과 기지 평문 공격의 예시를 나타낸다. 이처럼 공격자가 암호문 일부만 알고 있는 상태인지, 일부 평문을 알고 있는 상태에서 이에 대응하는 암호문을 알고 있는 상태인지 등 일련의 한정된 능력을 보유하고 있을 때를 가정하여 공격 시나리오를 구성한다.

1. 암호분석 방법론 소개

1.1 전수조사 방법

  기지 평문 공격 등을 기반으로 해당 암호문에 대응하는 모든 비밀키 값에 대한 평문 혹은 암호문 비교 조사 후 일치하는 비밀키 값을 찾아내는 방식이다. 암호 알고리즘의 안전성은 Kerckhoffs 원리에 의해 비밀키에만 의존하게 된다. 즉, 암호 알고리즘의 구조가 공개되더라도 비밀키를 안전하게 보관한다면 주어진 암호 알고리즘은 안전성을 보장할 수 있게 된다. 이를 기반으로 현대암호는 실제 컴퓨팅 연산량으로는 비밀키값 예측을 어렵게 하기 위해 충분한 크기의 비밀키 길이를 갖게 된다.

1.2 수학적 논리 기반의 암호분석 방법

  현대블록암호기술은 정보이론의 창시자인 Claude Shannon 에 의해 정립된 혼돈 (Confusion) 및 확산 (Diffusion)의 원리를 기반으로 암호 알고리즘을 설계한다. 대표적인 기존 암호분석 기술인 차분분석 (Differential cryptanalysis) 및 선형분석 (Linear cryptanalysis) 기술은 평문 및 암호문의 차분 값 또는 선형 근사 값을 기반으로 암호 알고리즘이 보유한 혼돈 및 확산 성질을 만족하기 위한 비선형성 등의 성질을 수학적으로 분석하는 기술이다. 그러난 이러한 수학논리 기반의 차분분석 및 선형분석 기법 등은 암호 알고리즘의 라운드 수 및 비밀키 길이가 길어질수록 성능이 대폭 저하되는 근본적인 기술적 한계를 가지고 있다.

1.3 AI 기반 암호분석 기술

  AI 기반 암호분석 기술은 앞의 수학적 기반 암호분석기술과는 다르게 CNN (Convolutional neural network), GAN (Generative adversarial network), RNN (Recurrent neural networks) 등과 같은 딥러닝 모델을 기반으로 암호문 또는 평문/암호문 쌍을 기반으로 자동분석을 수행하여 암호문에 대응하는 평문 또는 비밀키 값을 찾아내는 방식이다. 이에 대해 보다 나은 평문 및 비밀키 복원을 목적으로 국내외적으로 여러 연구가 진행 중에 있다.

2. AI 기반 암호분석 기술 연구동향

2.1 AI 기반 평문 복원 기술

◾Gomez 등이 제안한 CipherGAN[1]은 암호 알고리즘이 갖는 비선형성에 대한 자동분석을 수행하기 위해 GAN 기반의 암호분석을 수행하였다. Ian Goodfellow에 의해 제안된 GAN 모델은 특정 목표 데이터의 분포를 학습하여 이와 유사한 위조 데이터 (Fake data)를 생성하는 모델로써, 컴퓨터 비전 분야에서의 이미지 분석 및 생성 등에 주로 사용되어 왔으나, 최근에는 자연어 처리, 기계 번역, 합성 의료데이터 등 수 많은 분야에서 널리 사용되고 있다. 디지털 암호체계 자동분석을 위해 제안된 CipherGAN은 안정적인 학습을 위해 와서스타인 거리 (Wasserstein distance) 및 최소제곱(Least square) 기반의 손실함수를 이용하여 Vigenere와 같은 고전암호에 대해 암호문 단독 공격을 기반으로 평문 완전 자동분석이 가능함을 입증하였다. 물론 Vigenere와 같은 고전암호 기술은 현대암호에 비해 상대적으로 낮은 비선형성을 보이고 있으나, CipherGAN은 이러한 암호특성을 AI 기술로 완전 자동분석이 가능함을 보여주는 기초 결과물이라 할 수 있다.

그림2. Attention-based LSTM 모델 기반 암호문 평문 복구 개념도 [2]
​

◾Ezat 등이 제안한 기술[2]은 CipherGAN과는 다르게 순차 데이터 (Sequential data) 분석에 용이한 RNN 계열 모델에 해당하는 LSTM (Long short term memory) 기반의 암호분석을 수행하였다. 이 LSTM 모델에서는 이산 변수에 해당하는 암호문 데이터를 원-핫 인코딩 (One-hot encoding)을 기반으로 워드임베딩 (Word embedding)을 수행하였으며, 이후 전처리된 암호문을 입력받은 LSTM 계층은 토큰 (Token) 단위를 기준으로 각각 히든 상태 (Hidden state)의 입력 값으로 구성한 후, t번째 토큰에 대한 히든 값을 t+1번째 히든 값 및 결과 값의 입력으로 사용하여 순차적인 학습 구조를 갖는다. 이때, 기존의 RNN 모델은 히든 상태만을 보유하고 있어 메시지의 길이가 길면 길수록 그래디언트 소실 (Gradient vanishing) 문제로 인하여 이전의 토큰 값에 대한 정보를 얻기 어려우나 LSTM 모델은 셀 상태 (Cell state)를 추가하여 기존의 RNN 모델이 겪던 문제를 일부 해결하게 되었다. 하지만, LSTM 모델 역시 단순히 직전 상태의 정보만을 받아 학습을 수행하기 때문에 여전히 가변 길이를 가짐과 동시에 긴 길이를 갖는 데이터에 대한 학습의 어려움이 존재한다. 이러한 문제점을 해결하기 위해, 제안된 기술[2]은 어텐션 메커니즘에 기반하는 Attention-based LSTM을 도입하였다. 어텐션 메커니즘은 기존에 직전 정보만을 받는 LSTM 구조를 개선시키기 위해 일련의 가중치(Weight) 개념을 도입하여 직전의 모든 값으로 부터 일부분의 정보를 받게 된다. 따라서 본 기술은 Attention-based LSTM 모델 도입 결과, 긴 길이를 가짐과 동시에 가변 길이를 갖는 암호문 문장에 대해서도 암호문에 대응하는 평문 자동분석이 가능함을 실험적으로 입증하였다. [그림 2 참조].

◾Xiao 등이 제안한 기술[3]은 앞의 두 기술과 마찬가지로 암호문에 대응하는 평문 복구를 위한 모델을 제시하였다. 해당 기술은 현대블록암호인 DES (Data standard encryption) 암호해독을 목표로 연구를 진행하였으며, 다수의 실험 결과, 순차 데이터 분석에 용이한 RNN, 지역적 특성(Local feature) 추출에 용이한 CNN 모델에 비해 전역적 특성(Global feature) 추출에 용이한 단순한 Feed-forward Network가 가장 좋은 복원 효율성을 가짐을 보였다. 그러나 DES를 기준으로 최대 3라운드까지만 실험 결과를 보여주었으며, 그 외 라운드 수에는 복원이 불가능함을 볼 수 있다. 그러므로 앞으로 보다 고도화된 AI 기반 평문 복구 기술에 대한 연구가 필요한 상황이다.

2.2 AI 기반 비밀키 복구 공격 기술

◾Gohr에 의해 제안된 기술[4]은 암호문과 난수를 구별하고 분류 (Classification) 하는 학습 모델로서, 이 암호분석 기법에서는 Residual network 기반의 CNN을 통해 암호문과 난수를 구별하는 신경망 구분자 (Neural distinguisher) 기술을 제시하였다. 그 결과, SPECK32/64 암호 알고리즘을 기준으로, 차분 구분자 (Differential distinguisher) 보다 신경망 구분자가 더 우수한 분류 정확성을 보임을 발견하였으며, 또한 제한된 라운드 수에서 비밀키 복구 공격이 가능함을 제시하였다. 이는 현대암호체계 자동분석을 위해 AI 기술이 가장 효율적으로 개발되고 사용된 대표적인 사례로 간주되고 있으며, 이후 해당 기술을 기반으로 고도화된 신경망 구분자를 사용하여 다양한 구조 (Feistel 구조, SPN 구조 및 ARX 구조) 의 암호 알고리즘 분석하는 연구가 현재 진행 중에 있다.

◾상기 제안된 암호분석 기술[4]이 목표로 하는 SPECK 암호 알고리즘은 ARX 구조로 64비트의 비밀키 길이와 32비트의 블록 사이즈를 가진다. SPECK과 같은 암호 알고리즘은 현재 암호표준기술인 AES 알고리즘과는 다르게 경량암호 (Lightweight cryptography) 에 해당한다. 경량암호란 IoT 환경에서의 무선 환경 등 자원제약적인 상태에서도 사용할 수 있는 암호를 말한다. 따라서 경량암호는 저전력 및 저용량 환경에서도 안전하고 효율적으로 구동되어야 하므로 하드웨어 또는 소프트웨어 측면에서 가장 효율적인 구현이 가능하게끔 알고리즘이 설계되어야 한다. 이러한 이유로 전 세계적으로 다양한 경량암호들이 연구되고 있으며, 또한 해당 암호들을 구조적인 측면으로 분류하여 해당 구조에 대한 암호분석 연구도 현재 진행 중에 있다. 이러한 시대적 변화의 흐름에 맞추기 위해, NIST에서는 2015년부터 Lightweight Cryptography Competition[5]를 개최하여 진행 중에 있으며, 그 결과, 총 57개의 후보군을 받았으며, 2019년 4월에 56개의 알고리즘이 Round 1 후보로 선정, 2019년 8월에 32개의 알고리즘이 Round 2 후보로 선정되었고, 이후, 2021년 3월에 10개의 최종후보가 선정되어 현재 최종심사 중에 있다. Baksi 등에 의해 제안된 기술[6]은 기존의 Gohr가 제안한 기술[4]을 기반으로하여 Round 2 및 최종후보에 선정된 GIMLI, ASCON, KNOT에 대한 신경망 구분자 기술을 제안하였다. 또한, 해당 문헌은 AI 모델이 어떻게 설계되는지에 따라 신경망 구분자의 분류 능력이 어떻게 달라지는지를 실험적으로 입증하였다. 결국 암호문의 특성에 맞추어 AI 학습모델 구조를 변화시키고 진화시킨다면 더 성능이 우수한 신경망 기반 구분자를 개발 할 수 있을 것으로 기대되며, 이러한 이유로 암호분석용 신경망 구분자 기술이 현재 활발히 연구 중에 있다[7-13].

2.3 AI 기반 암호 Application 기술

◾최근 IoT 기술의 발전은 사용자 단말 기기의 소형화 및 종류의 다양화가 이루어지고 있음과 동시에 해당 기기로부터 다수의 개인 데이터 수집 및 처리가 가능한 시대로 변화하고 있다. 이로 인해, Google, Amazon 및 Microsoft 등 사용자들에게 일련의 서비스를 제공하는 기업들은 이러한 개인 데이터를 수집한 후 클라우드 스토리지 서비스의 안전성에 의존을 하게 되며, 이러한 클라우드 서비스는 데이터의 보관, 처리 등의 문제점을 해결하게 되므로 IoT 환경에 수 많은 이로움과 편리성을 주게 된다. 하지만, 이러한 데이터는 개인의 취미, 취향 또는 질병내용 등 대부분 개인의 민감한 정보를 담은 데이터로 구성이 되어 있기 때문에, 해당 데이터에 대한 데이터 기밀성을 만족하는 암호 기술은 필수이다. 따라서 암호화된 채로 클라우드 스토리지에 저장이 된다면 개인정보는 더 이상 누출되지 않게 된다. 그러나 이렇게 암호화된 데이터는 기존의 AI 기술을 이용한 데이터 분석 및 예측 서비스 측면에서 활용성이 낮아지기 때문에, 최근에는 암호화된 데이터에 바로 머신러닝 및 딥러닝 등과 같은 AI 기술을 적용하여 원본 데이터 노출 없이 암호데이터를 분석 및 예측하는 기술에 대한 연구가 진행되고 있다.

◾Lidkea 등에 의해 제안된 기술[14]은 CNN을 기반으로 암호화된 이미지 데이터를 분류하는 AI 기술을 제안하였다. 해당 기술은 차량의 번호판과 같은 민감할 수 있는 정보의 데이터 기밀성을 보존하기 위해 암호화를 수행하였으며, 이렇게 암호화 된 상태에서도 해당 이미지가 어떠한 레이블(예를 들어, 승용차/트럭 등의 차량 종류를 판별)을 갖는 지를 판별할 수 있는 기술을 제안하였다.

◾Podschwadt 등에 의해 제안된 기술[15]은 RNN을 기반으로 암호화된 텍스트 데이터에 대한 분류 기술을 제안하였다. 상기 기술과 마찬가지로 해당 기술 역시 데이터 기밀성 보존을 위해 데이터 암호화를 수행하였으며, 암호화된 텍스트 데이터에 대해서도 해당 데이터가 어떠한 레이블을 갖는지를 판별할 수 있는 기능을 갖게 된다. 이 때 사용된 암호화 기술은 동형암호(Homomorphic Encryption)을 사용하였으며, 해당 암호 기술은 기존의 블록암호와는 다르게 암호화된 상태에서도 일종의 연산이 가능한 암호 기술에 해당한다.

◾Ezat 등에 의해 제안된 기술[16]은 마찬가지로 RNN을 기반으로 암호화된 텍스트 데이터에 대한 분류 기술을 제안하였다. 특히, 보다 우수한 암호문 분류성능을 얻기 위해 BLSTM (Bidirectional LSTM) 및 GRU (Gated recurrent unit)를 융합하는 분류모델을 설계하였으며, 그 결과 CNN, LSTM 혹은 GRU 단독 사용 모델에 비해 약 2~10% 우수한 분류성능을 보임을 입증하였다. [그림 3 참조].

그림 3. BLSTM-GRU-LSTM 기반 암호문 분류 기술 개념도 [16]​

참고문헌

[1] Gomez et al. “Unsupervised cipher cracking using discrete gans,“ arXiv preprint arXiv:1801.04883 (2018).

[2] Ezat et al. “A Novel Dynamic Attack on Classical Ciphers Using an Attention-Based LSTM Encoder-Decoder Model,” IEEE Access, 9 (2021).

[3] X. Ya, Q. Hao, and D. Yao. “Neural cryptanalysis: Metrics, methodology, and applications in cps ciphers,” IEEE Conference on Dependable and Secure Computing (2019).

[4] A. Gohr, “Improving attacks on round-reduced Speck32/64 using deep learning,” Crypto 2019.

[5] https://csrc.nist.gov/projects/lightweight-cryptography

[6] Baksi et al., “Machine learning assisted differential distinguisher for lightweight ciphers,” Classical and Physical Security of Symmetric Key Cryptographic Algorithms, Springer (2022).

[7] Z. Hou, “Cryptanalysis of Round-reduced SIMON32 based on deep learning,” IACR (2021).

[8] T. Yadav, “Differential-ML distinguisher: machine learning based generic extension for differential cryptanalysis,” IACR (2020).

[9] A Benamira, “A deeper look at machine learning-based cryptanalysis,” Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer (2021).

[10] Botao et al. “Linear attack on round-reduced DES using deep learning,” European Symposium on Research in Computer Security, Springer (2020).

[11] Kimura et al., “Output prediction attacks on SPN block ciphers using deep learning,” IACR (2021).

[12] Yi et al., “Neural aided statistical attack for cryptnalaysis,” IACR (2020).

[13] Chen et al., “A new neural distinguisher model considering derived features from multiple ciphertext pair,” IACR (2021).

[14] V. Lidkea et al., “Convolutional neural network framework for encrypted image classification in cloud-based ITS,” IEEE Open Journal of Intelligent Transportation Systems, 1 (2020).

[15] R. Podschwadt and D. Takabi, “Classification of encrypted word embeddings using recurrent neural networks,” in PrivateNLP, WSDM (2020).

[16] Ezat et al., “A Deep Bidirectional LSTM-GRU network model for automated ciphertext classification,” IEEE Access, 10 (2022).