[Crypto] NEAT, NES

NEAT (National Encryption AlgoriThm) 알고리즘 분석 요약

NEAT은 대한민국 국정원이 설계한 비공개 국가 표준 암호 알고리즘으로, 1997년에 국가기관용 표준 암호로 제정되었다. 이 알고리즘은 정부 기관에서 내부 데이터와 문서 암호화를 위해 사용되며, security through obscurity(암호화 원리를 숨김으로써 보안을 유지하는 방식)를 부분적으로 의존하고 있다. 128비트 블록 암호화 알고리즘으로, IDEA(International Data Encryption Algorithm)와 구조적으로 유사하다.

 

특징

• 암호 구조
  • Feistel 네트워크 기반: 암호화와 복호화 과정이 거의 동일
  • 12.5 라운드: 12번의 full-round 연산과 1번의 half-round 연산으로 구성됨
  • 각 라운드에서는 128비트를 64비트 두 개로 나누어 처리
• 연산 방식
  • XOR 연산: 기본 비트 연산 (⊕).
  • 모듈러 덧셈 연산: mod 2¹⁶의 덧셈 연산 (⊞).
  • 모듈러 곱셈 연산: mod 2¹⁶+1의 곱셈 연산 (⊙).
  • 데이터 의존 회전: 입력 데이터에 따라 가변적으로 비트를 회전(⋘).
• 키 크기
  • 128비트 키를 사용하며, 이 키를 기반으로 13개의 라운드 키를 생성
• 키 스케줄링
  • 암호화 키를 데이터로 간주하여 7라운드 연산을 수행해 라운드 키를 생성
  • 상수 키(Ks)를 사용하여 초기화된 라운드 키와 XOR을 수행해 라운드 믹스 값을 생성

 

주요 구성 요소

1. F 함수와 역함수(F⁻¹)
   • 64비트 입력을 4개의 16비트 데이터로 나눈 뒤, 각각에 다양한 연산(XOR, mod 덧셈, mod 곱셈, 회전)을 적용한다.
   • IDEA와 유사한 구조지만 입력 데이터 의존 회전 연산이 추가되어 차별화된다.
2. MIX 함수
   • 각 라운드의 결과를 라운드 믹스 상수 테이블을 사용해 XOR 연산으로 결합한다.
   • 이 MIX 구조는 다른 암호에서 보기 드문 독특한 방식
3. Half-round
   • 마지막 라운드는 MIX 함수 없이 F와 F⁻¹의 결과를 교환(swap)하여 암/복호화를 대칭적으로 만든다.

#include <stdint.h>
#include <stdio.h>

// 라운드 상수 테이블
const uint16_t Ks[] = {
    0xFD56,
    0xC7D1,
    0xE36C,
    0xA2DC
};

// MIX 함수 구현
void mixFunction(uint16_t *data, int dataSize) {
    for (int i = 0; i < dataSize; i++) {
        // 각 데이터와 라운드 상수를 XOR
        data[i] ^= Ks[i % 4];  // 상수 배열 순환적으로 적용
    }
}

int main() {
    // 암호화할 데이터 (16비트 데이터 배열)
    uint16_t data[] = {0x1234, 0x5678, 0x9ABC, 0xDEF0};
    int dataSize = sizeof(data) / sizeof(data[0]);

    // 원래 데이터 출력
    printf("Original data:\n");
    for (int i = 0; i < dataSize; i++) {
        printf("0x%04X ", data[i]);
    }
    printf("\n");

    // MIX 함수 적용
    mixFunction(data, dataSize);

    // 변환된 데이터 출력
    printf("After MIX function:\n");
    for (int i = 0; i < dataSize; i++) {
        printf("0x%04X ", data[i]);
    }
    printf("\n");

    return 0;
}

 

암호화 과정

1. 128비트 입력 데이터를 64비트 두 개로 나눔.
2. 각 라운드에서 F와 F⁻¹ 연산을 통해 데이터를 변환.
3. MIX 함수를 통해 각 라운드 결과를 결합.
4. 마지막 half-round에서 결과값을 스왑 후 출력.

 

복호화 과정

• 복호화는 암호화 과정과 거의 동일하지만, 라운드 키와 MIX 값이 반대 순서로 적용됨
• MIX 함수는 복호화 과정에서도 암호화와 동일한 방식으로 작동
• 마지막 라운드에서 스왑된 데이터를 다시 뒤집어 복호화를 완료

 

NEAT 리버싱 과정

리버싱은 공개되지 않은 암호 알고리즘을 분석하여 동작 원리를 파악하는 과정으로, 아래와 같은 단계를 통해 진행된다.

1. 사전 정보 수집
   • NEAT이 1997년에 제정되었으며, 주로 CBC 모드로 작동한다는 것을 확인했다.
   • NEAT의 구현체는 BUD-F라는 플랫폼과 연관이 있을 가능성이 있으며, 국정원의 설계로 추정된다.
2. 구현체 획득
   • GPKISecureWeb이라는 소프트웨어에서 NEAT의 흔적이 발견되었다.
   • libgpkiapi64.a라는 파일 안에서 EncryptNeatCBC, DecryptNeatCBC 등 NEAT 관련 함수 이름이 확인되었다.
3. 파일 분석
   • NEAT의 구현체는 XCOFF 포맷의 오브젝트 파일로 제공되었으며, 디컴파일이 어렵다.
   • 일부 어셈블리 코드와 함수명을 통해 NEAT의 라운드 함수 구조, 암호화 및 복호화 방식이 대칭적이라는 점을 유추했다.
4. Theori의 선행 연구
   • Theori라는 보안 연구 그룹이 NEAT의 동작 원리를 분석한 사례를 참고하였다.
   • Theori의 연구 결과에 따르면 NEAT의 마지막 라운드에 final swap이라는 구조가 포함되어 암/복호화가 대칭적으로 작동함을 확인했다.

 

NES (National Encryption Standard) 알고리즘 분석 요약

NES는 2003년 대한민국 국가기관용 표준 암호로 제정된 256비트 블록 암호 알고리즘이다. AES(Advanced Encryption Standard)의 설계 철학과 구조를 상당 부분 차용한 Substitution-permutation Network (SPN) 기반의 알고리즘으로, NEAT과는 다른 특성을 지닌다.
특히, AES와 유사하지만 Involutional SPN 구조를 채택하여 암호화와 복호화 루틴 간의 차이를 최소화한 점이 특징이다.

 

주요 특징

1. SPN 구조
   • NEAT의 Feistel 구조와 달리 SPN(Substitution-Permutation Network) 구조를 채택.
   • SPN 기반의 데이터 변환은 S-Box(Substitution)와 P-Box(Permutation)를 사용해 데이터의 혼돈(confusion)과 확산(diffusion)을 극대화.
2. 256비트 블록 및 키
   • AES가 최대 128비트 블록/키를 지원하는 것과 달리, NES는 256비트 블록과 256비트 키를 기본으로 합니다.
3. 4단계 연산
   • 암호화 과정은 13라운드로 구성되며, 각각의 라운드는 다음 4단계로 이루어진다.
     1. Substitution: S-Box를 사용한 비선형 변환.
     2. Transposition: 4×8 행렬로 변환 후 열 전치(transpose).
     3. Permutation: 라운드 별 P-Box를 사용해 데이터 섞기.
     4. AddRoundKey: 라운드 키와 XOR 연산.
   • 마지막 라운드(라운드 12)에서는 Permutation 단계가 생략된다.
4. Key Schedule
   • 초기 암호 키에서 13개의 32바이트 라운드 키를 생성한다.
   • 라운드 키 확장은 Substitution, Permutation 등을 사용하며, 암호화와 복호화 시 다른 키 순서를 사용.
5. Involutional SPN 구조
   • 암호화와 복호화 루틴이 동일한 구조를 사용.
   • 복호화 시 S-Box와 P-Box의 역함수를 적용하고, 라운드 키 순서만 반대로 조정.

 

NES 연산 과정

1. 초기 라운드 (Initial Round)
   • AddRoundKey: 입력 데이터를 첫 번째 라운드 키와 XOR.
2. 보통 라운드 (Rounds 1~11)
   • Substitution: S-Box로 데이터 비선형 변환.
   • Transposition: 행렬 전치 연산.
   • Permutation: P-Box를 통해 데이터 섞기.
   • AddRoundKey: 각 바이트를 라운드 키와 XOR.
3. 마지막 라운드 (Final Round)
   • Substitution과 Transposition 후 AddRoundKey.
   • Permutation 단계는 생략.

 

NES 키 스케줄링

• 초기 암호 키를 기반으로 각 라운드에 사용할 라운드 키를 생성.
• P-Box와 S-Box의 역함수를 사용하여 복호화용 키를 생성.
• 상수 테이블을 사용하지 않고, 암호 키 자체의 영향을 크게 받는 구조.

 

복호화

NES는 Involutional SPN 구조를 기반으로 설계되었기 때문에 암호화와 복호화가 같은 루틴을 공유한다.

• S-Box와 P-Box의 역함수를 적용.
• 라운드 키 순서만 반대로 적용하여 복호화를 수행.

 

NES의 보안성과 한계

1. 보안성
   • SPN 구조는 혼돈(confusion)과 확산(diffusion)을 극대화하여 차분 및 선형 공격에 강한 특성을 보임.
   • S-Box와 P-Box의 다양성이 보안을 강화.
2. 한계
   • 알고리즘 명세가 비공개이므로 학계 및 업계의 검증이 제한적.
   • 국내에서 제한적으로 사용되며, 국제적인 채택이나 표준화는 이루어지지 않음.

 

구현 및 검증

• NES 구현체는 국내 보안 솔루션 및 VPN 모듈에서 발견됨.
• 테스트 환경
  • NEAT: XecureWeb의 Linux 배포 버전 모듈을 사용.
  • NES: SecureWorks TRUiN 패키지 내 DLL 함수 후킹을 통해 검증.
• 구현 언어
  • C와 Python으로 알고리즘을 재구현하여 CBC 모드 테스트 수행.
  • 결과 검증: 공식 모듈과 동일한 암호화 및 복호화 결과 확인.

 

 

 

References

• https://github.com/theori-io/kr-crypto
• https://www.theteams.kr/teams/7316/post/71018
• https://spot.wooribank.com/pot/Dream?withyou=CQSCT0067
• ㅇㄹㅇㄹ