« 2025/01 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

※ 본 프로젝트는 offensive research가 아닌 defensive 관점에서 진행한 학술적인 연구입니다.

✉ 윤형준 encrypt@kakao.com

[목차]

Overview

본 (2) 리버싱 파트에서는 NEAT 구현체를 리버싱하여 알고리즘을 분석하는 과정의 일부를 정리한다.

사실 중간중간 (3) 알고리즘 분석 파트에 어울리는 내용이 들어가 있기도 하고, 굳이 리버싱한 내용을 한 파트로 나누는 것이 의미가 있는지 의문이 들 수도 있다.

리버싱 파트를 따로 분리한 것은 구현체로부터 비공개 암호 알고리즘을 분석하는 방법론을 정리하기 위함이다.

획득한 바이너리

NEAT 구현체를 꽤 많이 획득했다.

AnySign은 OS X와 Linux는 더 이상 지원하지 않아서 공식 홈페이지에서는 구할 수 없다.

리눅스는 .deb와 .rpm 설치 파일을 제공한다.

(파일을 공유하려 했으나 문제의 소지가 있어서 파일명만 남깁니다.)

[Android]

전체 파일 : iccsmWebNew

NEAT 구현체 : libgpkiapi64.a

[Linux]

설치 파일 : anysign4pc_i386_x86_64.zip

[MAX OS X]

설치 파일 : anysign4pc_v1.1.1.0.pkg, certsharexfree_v1.0.0.6.pkg

NEAT 구현체 : AnySign4PC.zip, CertShareX.zip

[Windows]

전체 파일 : AnySign.zip

NEAT 구현체 : XecureAcCrypto.dll

어떤 바이너리를 분석할까?

iccsmWebNew는 object module이고 assembly만으로 분석하고 싶지는 않다.

그리고 티오리에서 NEAT를 리버싱할 때 사용한 구현체가 Linux 버전인 것 같다. 이왕이면 다른 바이너리를 리버싱해보고 싶다.

Windows의 dll을 살짝 봤는데 자료형이 가장 심각하게 박살나 있었다.

OS X의 두 응용프로그램 AnySign4PC, CertShareX에서 NEAT 구현체를 살짝 봤는데 그나마 상태가 온전했다. 게다가 libXecureCrypto.dll라는 라이브러리만 제공하는 윈도우와 달리, 맥 버전에서는 libXecureNEAT.dylib라는 라이브러리도 제공해 준다. 크기가 겨우 25KB 밖에 안된다!

따라서 AnySign4PC 맥 버전의 libXecureNEAT.dylib를 분석할 것이다.

분석 대상 : libXecureNEAT.dylib

설치 후 파일 위치

❯ grep -r "NEAT" ./
/Applications/SoftForum/AnySign4PC.app/Contents/MacOS/libXWClientSM.dylib
/Applications/SoftForum/AnySign4PC.app/Contents/MacOS/libXecurePKCS7.dylib
/Applications/SoftForum/AnySign4PC.app/Contents/MacOS/integrity.dat
/Applications/SoftForum/AnySign4PC.app/Contents/MacOS/libXecureCrypto.dylib
/Applications/SoftForum/AnySign4PC.app/Contents/MacOS/libXecureNEAT.dylib

❯ grep -r "NEAT" ./
/Applications/CertShareXFree/CertShareXFree.app/Contents/MacOS/libXecurePKCS7.dylib
/Applications/CertShareXFree/CertShareXFree.app/Contents/MacOS/libXecureCrypto.dylib
/Applications/CertShareXFree/CertShareXFree.app/Contents/MacOS/libXecureNEAT.dylib

이제부턴 정말 리버싱 뿐이야

바이너리에 8개의 함수가 있다.

sub_630
sub_6C0
sub_720
sub_800
_KeySchedule
_DeKeySchedule
_Encrypt
_Decrypt

바이너리 크기가 작고 함수가 적은 대신 cross reference를 보기 힘들다는 단점이 있다. 윈도우의 dll 파일도 봤는데 거기도 xref가 다 끊어져있었다. 그래서 함수 인자를 정확히 알 수 없었다.

자료형은 unsigned __int16을 사용하고 있었으며, 리버싱은 대체로 컴파일러 최적화 등으로 인해 아주 고된 작업이었다.

IDA를 통해 디컴파일한 결과 자료형이 unsigned __int16으로 나타나는데 이는 MSVC++ 컴파일러에서 사용 가능한 자료형이라고 한다. 그런데 이 바이너리는 OS X의 dylib이므로 uint16_t 자료형을 컴파일하는 과정에서 이와 같이 표현된 것 같다.

$2^{16}$ 상의 연산을 위해 16-bit 크기의 레지스터를 이용할 것이라고 추측해 볼 수 있다.

우선 함수명 심볼이 없는 sub_xxx() 함수들부터 분석했다.

sub_630() - Modular Multiplicative Inverse

첫 번째 함수인 sub_630()을 디컴파일 한 코드는 아래와 같다.

sub_630() decompiled code

__int64 __fastcall sub_630(int a1)
{
  int v1; // esi
  __int64 result; // rax
  __int64 v3; // rax
  __int64 v4; // rdx
  signed int v5; // er8
  int v6; // edi
  int v7; // ecx
  int v8; // eax
  unsigned __int16 v9; // r10
  int v10; // eax
  unsigned __int16 v11; // r10

  v1 = a1;
  result = (unsigned __int16)a1;
  if ( (unsigned __int16)a1 > 1u )
  {
    v3 = 0x10001 / (signed __int128)(unsigned __int16)a1;
    v4 = 0x10001 % (signed __int128)(unsigned __int16)a1;
    v5 = 1;
    v6 = 0x10001 / (signed __int128)(unsigned __int16)a1;
    v7 = v4;
    if ( (_WORD)v4 == 1 )
    {
      result = (unsigned __int16)(v4 - v3);
    }
    else
    {
      while ( 1 )
      {
        HIWORD(v8) = HIWORD(v1);
        LOWORD(v8) = (unsigned __int16)v1 / (unsigned __int16)v7;
        v9 = (unsigned __int16)v1 % (unsigned __int16)v7;
        v1 = (unsigned __int16)((unsigned __int16)v1 % (unsigned __int16)v7);
        v5 += v6 * v8;
        if ( v9 == 1 )
          break;
        HIWORD(v10) = HIWORD(v7);
        LOWORD(v10) = (unsigned __int16)v7 / v9;
        v11 = (unsigned __int16)v7 % v9;
        v7 = v11;
        v6 += v5 * v10;
        if ( v11 == 1 )
          return (unsigned __int16)(1 - v6);
      }
      result = (unsigned __int16)v5;
    }
  }
  return result;
}

$\text{modular}\ 2^{16}+1$ 상의 연산이며 extended euclidean algorithm을 이용해 modular multiplicative inverse를 찾는 함수라는 것을 알 수 있다.

따라서 아래와 같이 파이썬으로 간단히 나타낼 수 있다.

InvMul function python code

def inv_mul(a):
	if gcd(a, 0x10001) != 1:
		print("[-] gcd(a, 0x10001) != 1")
		return None
	an, bn = a, 0x10001
	ua, va, ub, vb = 1, 0, 0, 1
	while bn != 0:
		q = an // bn
		an, bn = bn, an - bn * q
		ua, va, ub, vb = ub, vb, ua - ub * q, va - vb * q
	return (ua % 0x10001)

위 코드는 단순히 extended euclidean algorithm을 이용했는데, 이때 0x10001이 fermat number이므로 fermat's little theorem 이용해 최적화할 수 있다.

sub_6C0() - Multiplication

다음은 두 번째 함수인 sub_6C0() 함수를 디컴파일한 결과다.

sub_6C0() decompiled code

__int64 __fastcall sub_6C0(unsigned __int16 a1, unsigned __int16 a2)
{
  unsigned __int64 v2; // rdx

  v2 = a2 * (unsigned __int64)a1;
  if ( v2 )
    return (unsigned __int16)(((unsigned __int16)v2 < WORD1(v2)) + v2 - WORD1(v2));
  if ( a1 )
    return (unsigned __int16)(1 - a1);
  return (unsigned __int16)(1 - a2);
}

이 함수는 $\text{modular}\ 2^{16}+1$ 상의 곱 셈을 수행한다.

계속해서 $2^{16}$ 상의 연산이 등장한다. 만약 값이 0인 경우 0x10000으로 연산해야 하며, 결과가 0x10000인 경우 다시 0으로 세팅해야 한다. 따라서 아래와 같이 나타낼 수 있다.

Mul function python code

def mul(self, a, b):
		if a == 0:
			a = 0x10000
		if b == 0:
			b = 0x10000
		return (((a * b) % 0x10001) & 0xFFFF)

sub_720() - F function

드디어 암호화 함수 같은 코드가 나왔다.

sub_720() decompiled code

__int64 __fastcall sub_720(unsigned __int16 *a1, unsigned __int16 *a2)
{
  unsigned __int16 *v2; // r13
  unsigned __int16 v3; // r12
  unsigned __int16 v4; // bx
  unsigned __int16 v5; // r15
  unsigned __int16 v6; // di
  unsigned __int16 v7; // bx
  unsigned __int16 v8; // r12
  unsigned __int16 v9; // ax
  unsigned __int16 v10; // r14
  int v11; // eax
  char v12; // cl
  int v13; // edi
  __int64 result; // rax
  int v15; // edx

  v2 = a1;
  v3 = a1[3];
  v4 = *a1;
  v5 = v3 ^ a1[2];
  v6 = *a1 ^ a1[1];
  v7 = v5 + v4;
  v2[2] = v5;
  v8 = v6 + v3;
  v2[1] = v6;
  *v2 = v7;
  v2[3] = v8;
  v9 = sub_6C0(v6, *a2);
  v2[1] = v9;
  v10 = v9;
  v11 = sub_6C0(v5, a2[1]);
  v12 = v11 & 0xF;
  v13 = ((signed int)v7 >> (16 - (v10 & 0xF))) | (v7 << (v10 & 0xF));
  result = (unsigned int)(v13 + v11);
  *v2 = v13;
  v2[2] = result;
  v15 = ((signed int)v8 >> (16 - v12)) | (v8 << v12);
  v2[3] = v15;
  v2[1] = v10 + v15;
  return result;
}

이 함수에서는 앞서 살펴본 곱셈 연산인 sub_6C0() 함수 외에도 XOR, 덧셈 연산을 포함한다.

함수 파라미터인 unsigned __int16 a[4]가 입력이고, unsigned __int16 v2[4]가 출력이다.

중간 state들을 모두 제거하고 16-bit 4개의 입출력을 각각 $\{x_0, x_1, x_2, x_3\}$ 와 $\{y_0, y_1, y_2, y_3\}$ 으로 나타내면 아래와 같다.

이 함수에서 사용하는 연산은 1991년에 디자인된 국제 표준 암호인 블록암호 알고리즘인 IDEA와 유사하다. 둘 다 오래된 표준 암호이므로 IDEA에서 차용한 것 같다.

sub_720()와 IDEA에서 공통으로 사용하는 연산은 다음과 같다.

Bitwise XOR on 16-bit ( $\oplus$ )

Addition on $2^{16}$ ( $\boxplus$ )

Multiplication on $2^{16}+1$ ( $\odot$ )

NEAT에는 IDEA에서 사용하지 않은 rotation 연산을 사용한다.

Data-dependent Rotation on 16-bit ( $\lll$ )

이는 differential cryptanalysis와 linear cryptanalysis에 저항성을 가지고 있다고 알려져 있는데, MARS나 RC5, RC6와 같은 암호 알고리즘에서 사용한다.

정확히는 $a \lll b$ 일 때, $b$ 의 $\text{least signicant}$ $lg(w)$ (low-order bits)인 $w$ -bit 만큼 rotate한다.

NEAT가 디자인된 시기를 고려하면 RC5의 rotation을 차용한 것 같다.

sub_800() - Inverse F function

sub_800() 함수는 F 함수인 sub_720() 함수의 역원이다.

sub_720() decompiled code

__int64 __fastcall sub_800(unsigned __int16 *a1, unsigned __int16 *a2)
{
  unsigned __int16 *v2; // r13
  int v3; // edx
  int v4; // eax
  unsigned __int16 v5; // r8
  unsigned __int16 v6; // di
  unsigned __int16 v7; // r15
  int v8; // er14
  int v9; // er12
  unsigned __int16 v10; // ax
  unsigned __int16 v11; // bx
  unsigned int v12; // eax
  __int64 result; // rax

  v2 = a1;
  v3 = a1[3];
  v4 = *a1;
  v5 = a1[2];
  v6 = a1[1] - v3;
  v2[1] = v6;
  v7 = v5 - v4;
  v2[2] = v5 - v4;
  v8 = (v4 << (16 - (v6 & 0xF))) | (v4 >> (v6 & 0xF));
  *v2 = ((_WORD)v4 << (16 - (v6 & 0xF))) | (v4 >> (v6 & 0xF));
  v9 = (v3 << (16 - (v7 & 0xF))) | (v3 >> (v7 & 0xF));
  v2[3] = ((_WORD)v3 << (16 - (v7 & 0xF))) | (v3 >> (v7 & 0xF));
  v10 = sub_6C0(v6, *a2);
  v2[1] = v10;
  v11 = v10;
  LOWORD(v9) = v9 - v10;
  v12 = sub_6C0(v7, a2[1]);
  LOWORD(v8) = v8 - v12;
  result = v9 ^ v12;
  v2[3] = v9;
  *v2 = v8;
  v2[2] = result;
  v2[1] = v8 ^ v11;
  return result;
}

아래처럼 구조도를 그릴 수 있다.

F 함수의 연산 순서를 반대로 수행하면서 덧셈 연산은 뺄셈으로, left rotation은 right rotation으로 치환한 형태다.

이 함수는 $(k_1 \odot k_3) = (k_2\odot k_4) = e$ 인 경우 $F^{-1}\cdot F = I$ 가 성립한다.

( $e$ : multiplicative identity, $I$ : identity function)

즉, k값에 따라 F 함수와 inverse F 함수는 역함수 관계가 될 수 있다.

_Encrypt()

_Encrypt() 함수는 NEAT 암호 알고리즘의 메인 암호화 알고리즘이다.

다음은 _Encrypt() 함수를 어느 정도 리버싱을 한 상태의 코드다.

unsigned __int64 __fastcall Encrypt(unsigned __int16 *L, unsigned __int16 *Key, __int64 a3)
{
  __int64 _a3_addr; // r15
  __int64 idx_main_round; // r14
  unsigned __int16 *KeyL; // r13
  __int64 idx_x_2; // rbx
  unsigned __int8 *XCon; // rbx
  unsigned __int16 *KeyR; // rsi
  unsigned __int16 *A; // rdx
  unsigned __int16 *B; // rdx
  unsigned __int16 *C; // rdx
  __int64 idx_final_swap; // rcx
  unsigned __int16 L_tmp; // dx
  unsigned __int64 R_tmp; // rax
  unsigned __int16 *Key_; // [rsp+0h] [rbp-40h]
  unsigned __int16 *R; // [rsp+8h] [rbp-38h]

  _a3_addr = a3;
  idx_main_round = 0LL;
  KeyL = Key;
  Key_ = Key;
  R = L + 4;
  do                                    // 12 round
  {
    idx_x_2 = *(unsigned __int16 *)(_a3_addr + 2 * idx_main_round++);
    XCon = (unsigned __int8 *)&XBox + 8 * idx_x_2;
    F(L, KeyL);                                 // F
    KeyR = KeyL + 2;
    KeyL += 4;
    InvF(R, KeyR);                      // F inv
    L[*XCon] ^= L[XCon[2] + 4];         // L[XCon[0]] ^= L[XCon[2] + 4]
    A = &L[XCon[1]];                    // L[XCon[1]] ^= L[XCon[3] + 4]
    *A ^= L[XCon[3] + 4];
    B = &L[XCon[4]];                    // L[XCon[4]+4] ^= L[XCon[6]]
    B[4] ^= L[XCon[6]];
    C = &L[XCon[5]];                    // L[XCon[5]+4] ^= L[XCon[7]]
    C[4] ^= L[XCon[7]];
  }
  while ( idx_main_round != 12 );
  F(L, Key_ + 48);                      // half round
  InvF(R, Key_ + 50);
  idx_final_swap = 0LL;
  do                                    // final swap L(64-bit) <-> R(64-bit)
  {
    L_tmp = *L;
    R_tmp = L[4];
    ++idx_final_swap;
    *L = R_tmp;
    L[4] = L_tmp;
    ++L;
  }
  while ( idx_final_swap != 4 );
  return R_tmp;
}

NEAT 암호의 전체적인 구조와 라운드 함수를 알 수 있다.

NEAT는 128-bit의 입력을 암호화하는 블록암호다. 또한 round 함수를 12번 반복한 뒤 마지막에 half round 함수와 final swap을 수행한다.

라운드 함수

먼저 NEAT 암호의 라운드 함수는 아래와 같다.

암호화하려는 128-bit의 입력을 64-bit의 L(Left)과 R(Right)로 나눈다. L, R을 각각 F, InvF의 입력으로 사용한 뒤 XL(Xor Layer)를 거친다.

Xor Layer

XL(Xor Layer)은 블록암호 알고리즘에서 처음 보는 아주 독특한 구조였다.

XL과 비슷한 구조를 찾기 위해 블록암호 알고리즘들를 전수조사했다.

먼저 NEAT가 디자인된 연도를 고려하여 2000년대 이전에 만들어진 블록암호 약 100개를 조사했다.

이후 블암호의 survey book인 A Salad of Block Ciphers에 등장하는 약 70개의 블록암호 알고리즘을 조사했다.

하지만 XL과 비슷한 동작 과정이나 설계 사상을 갖는 블록암호 알고리즘을 찾을 수 없었다. 따라서 XL 함수의 이름이나 관련 파라미터들은 모두 필자가 임의로 명명하였다.

XL(Xor Layer)은 먼저 $0,1,2,3$ 중 하나의 값으로 이루어진 $1024(8 \times 124)$ 개의 상수 값들(이하 XBox)에서 일련의 8개 값을 읽어온다. 이때 읽어온 8개의 값을 XCon(XL Constant)라고 명명했다.

이후 XCon의 값들인 $c(0\le c\le3)$ 또는 $c+4$ 를 XL 함수의 입력 $\{x_1,x_2,\dots,x_8\}$ 의 index로 사용하여 $x_i$ 들을 XOR한다.

NEAT는 F, InvF, XL로 이루어진 하나의 라운드 함수를 총 12번 반복한다.

12번의 반복 후에는 아래와 같은 half Round를 진행한다.

[그림7] A structure of half round function

half Round 함수에서는 Xor Layer가 포함되어 있지 않고, 대신 final swap을 수행한다.

이는 암복호화 구조를 통일하려는 블록암호 알고리즘에서 흔히 볼 수 있는 구조다.

암복호화 구조를 통일할 수 있었는지 그리고 NEAT 암호 알고리즘이 Involution인지는 차후 다룰 예정이다.

_Decrypt() 함수나 _KeySchedule(), _DeKeySchedule() 함수는 모두 _Encrypt() 함수와 닮아있기 때문에 리버싱 과정은 따로 정리하지 않았다.

Conclusion

화려한 리버싱 기술을 이용해 암호 알고리즘을 분석할 수 있었다면 좋았겠지만 사실 그런거 할 줄 모른다.

게다가 리버싱이 생각보다 어렵지 않았다.

물론 컴파일러 최적화 등으로 인해 자료형이 많이 망가져 있었지만 다행히 바이너리 크기가 작았다. 게다가 현대 블록암호 알고리즘의 일반적인 모델을 알고있는 상태에서 리버싱을 했기 때문에 생각보다 난이도가 높지 않았던 것 같다.

약 2주간의 리버싱과 동작 원리 분석을 동시에 진행했다. 퇴근 후 저녁이나 주말에 조금씩 해서 그런지 속도가 영 안 난다...

이만 글을 줄이고 분석한 암호 알고리즘을 정리해보려 한다.

Uploaded by Notion2Tistory v1.1.0

NEAT 암호 (4) 동작 원리와 설계 사상 (0)	2021.02.08
NEAT 암호 (3) 알고리즘 분석 (0)	2021.02.08
NEAT 암호 (1) 개요 (0)	2021.02.08
정수론 (9) The Quadratic Reciprocity Law (0)	2021.02.07
정수론 (8) Primitive Roots and Indices (0)	2021.02.07

topcue