HMAC

0. Intro
HMAC은 "The Keyed-Hash Message Authentication Code(Checksum)"을 의미하는 약어입니다.
즉, 해시를 통한 MAC인데 Key를 사용한다는 거죠.

MAC은 Message Authentication Code의 약자로 정보의 무결성을 검증하는 방법입니다.
정보가 변조되었는지 알아보기 위한 것이죠.
앞으로 말씀드리겠지만, 표준이 되는 문서인 FIPS-PUB 198에 나오는 문구를 그대로 사용하자면
"the method to check the integrity of information"입니다.

HMAC은 "MAC that uses a cryptographic hash function in conjunction with a secret key."입니다.

우리나라에는 암호 알고리즘을 구현하면, 이 구현이 올바른지 또는 구현 이외의 부분, 즉 암호의 사용에서 가장 중요한 Key의 관리 방식이 적절한지를 검증해 주는 제도가 있습니다.
국가정보원에서 하는 암호검증제도인데요.
이 제도는 국가에서 사용하는, 필요한 알고리즘에 대해서만 검증을 해 줍니다.
HMAC도 그 중 하나로 포함되어 있습니다.

IT 보안인증사무국에 가시면 보실 수 있고, 검증대상은 다음과 같습니다.
NIST FIPS PUB 198, The Keyed-Hash Message Authentication Code(HMAC), NIST, 2002

그럼 왜 비밀키(Secret key)를 사용하는 걸까요?

저는 중국집에 짜장면과 탕수육을 시켰습니다. ( 요즘 폭풍 다이어트 중이라 정말 땡기는군요. ㅡㅡ;;)
시키면서 제가 한 주문에 Hash("짜장면1, 탕수육1"에 대한)를 붙여서 보냈죠.

그런데 제 옆자리 팀원은 저를 정말 미워합니다. (예시는 예시일뿐 오해하지 말자..!!)
그 녀석은 절 엿멕일 궁리를 하다가 제가 주문하는 걸 발견하고, 데이터를 캡쳐하여  "짜장면 10, 탕수육 20"으로 변조한 후 재발송합니다.
아.. 전 정말 큰일 났습니다...

하지만 똘똘한 중국집 주인은 주문과 해시값을 비교해 보는군요.
그리곤 이건 누군가의 농간이라는 걸 알아내고 저에게 확인을 하겠죠..

이젠 절 미워하는 팀원도 학습효과라는 게 있기때문에 중국집 주인과 저의 주문 mechanism을 눈치챈 것 같습니다.

제가 짬뽕과 팔보채를 시켰는데..(아.. 정말.. 배가 고픕니다.. ㅜㅜ)
그걸 "짬뽕 100, 팔보채 50"으로 변조하고 해시값도 변조한 값에 대한 해시로 바꿔치기 합니다.

중국집 주인은 주문과 해시를 비교하고 정확한 주문이라고 판단한 후, 저 많은 걸 다 만들어서 저에게 가져옵니다.

물론 전자서명이라는 훌륭한 방법이 있지만, 지금은 HMAC에 대한 설명을 하는 중이니 그 부분은 빼고 예를 들다보니 좀 억지스러운 면도 없지 않습니다만, 그냥 그러려니 이해해 주세요.. ㅜㅜ

이런 일을 겪은 후, 중국집 주인과 저는 다시 mechanism 을 변경합니다.
해시할 때, 당신과 나만 알고 있는 어떤 값을 붙여서 함께 해시하자고..

이젠 제가 주문할 때, 짜장 하나와 군만두 하나를 주문하면 "짜장면1, 군만두1"이라는 주문 데이터와 "짜장면1, 군만두1,소녀시대카라포미닛레인보우짱"이라는 데이터에 대한 해시를 함께 붙입니다.

악질 팀원은 같은 방식으로 데이터와 해시를 변조하지만, 중국집 주인은 저와 한 약속대로 주문에 "소녀시대카라포미닛레인보우짱"이라는 데이터를 덧붙여 해시를 해 보곤 변조된 데이터라는 걸 눈치채는 거죠.

이게 HMAC에 대한 전부입니다.

알고리즘 Spec을 보시면 더욱 확실히 아실 수 있을 겁니다.
아래의 내용은 FIPS-PUB 198의 내용을 나름대로 정리한 것입니다.
(사실은 팀원들 교육? 용으로 대충 끄적였던 거 이 기회에 정리하는 겁니다. ㅡㅡ;;)

1. Cryptographic keys
  - 키의 길이(이하 "K")는 해시 알고리즘의 출력 길이(이하 "L")의 절반보다 커야 합니다.
    즉, 해시 알고리즘으로 SHA1을 사용한다면 SHA1의 결과는 20 byte이므로 10 byte 이상의 키를 사용해야 합니다.
  - K가 L보다 크다고 해서 보안 강도가 주목할 정도로 증가하진 않습니다.
  - K가 해시 알고리즘의 내부 블럭 사이즈(이하 "B")보다 클 경우엔, 해시한 값을 키로 사용합니다.
    즉, SHA1의 내부블럭 사이즈는 512(64 byte)이고 키가 64byte 보다 길다면 키를 해시한 값(20 byte가 되겠죠?)을 키로 사용한다는 것이죠.
  - 키는 검증된(Approved) 키 생성 방식을 사용한 난수에서 선택되어야 합니다.
    인증과 맞물리면, 아주 중요한 얘기입니다.
    대개 난수 생성기를 사용하여 난수를 만들고, 그 중에서 적당하게 키를 선택하게 되는데, 이 때 사용되는 난수 생성기도 검증필 암호모듈, 즉 국가정보원의 암호검증을 필한 모듈을 사용해야 합니다.
    검증 대상은 위의 IT 보안인증사무국 링크를 따라가 보시면 찾을 수 있습니다.
  - 키는 주기적으로 변경되어야 합니다.
  - 키는 데이터와 같이 중요하게 보호되어야 합니다.

2. Truncated output
HMAC을 수행한 결과를 사용할 때, 네트워크의 상태라든가 시스템 자원 사용에 대한 제한 등의 이유로 그 결과를 잘라서 사용할 수 있습니다.
이 때, HMAC이 의미를 가지려면(극한 상황이라면) 4byte 이상의 값을 사용해야 합니다.
그리고, 실제로 사용하기 위해서는 L/2 ≤ t ≤ L 이어야 합니다.
여기에서, t는 HMAC의 결과로 좌측으로부터 자른 값입니다.

3. Specification
a. if K = B, then K0 = K
b. if K > B, then
  - H(K)
  - append (B-L) zeros.
    ie. K0 = H(K) || 00..00
c. if K < B, then K0 = K || 00..00
d. K0 ^ ipad
e. [d] || [text] : ie. (K0 ^ ipad) || [text]
f. H([e]) : ie. H((K0 ^ ipad) || [text]))
g. K0 ^ opad
h. [g] || [f] : ie. (K0 ^ opad) || H((K0 ^ ipad) || [text]))
i. H([h]) : ie. H((K0 ^ opad) || H((K0 ^ ipad) || [text])))
j. select t bytes as the MAC
where, B : Block size (in bytes) of the input to the Approved hash function
    H : An approved hash function
    ipad : Inner pad; the byte x'36' repeated B times
    K : Secret key shared between the originator and the intended redciver
    K0 : the key K after andy necessary pre-processing to form a B byte key
    L : Block size (in bytes) of the output of the approved hash function
    opad : Outer pad; the byte x'5C' repeated B times
    t : The munber of bytes of MAC
    text : The data ou which the HMAC is calculated; text does not include the padded key.
    || : Concatenation

4. Implementation note
  - HMAC은 임의의 검증된 해시 알고리즘에 따라 특정지워집니다.
    즉, 잘만 구성하면 해시 알고리즘을 다른 해시 알고리즘으로 교체하는 것으로 HMAC을 변경할 수 있습니다.
  - K0 ^ ipad 와 K0 ^ opad 는 한 번만 계산한 후, 계속 사용할 수 있습니다.
    이 때, 미리 계산된 값은 비밀키와 같은 강도로 보안되어야 합니다.

5. 구현
구현은 대략적인 알고리즘만 C를 이용한 Pseudo Code로 표현하겠습니다.
즉, 그대로 가져가서 Compile하면 사용할 수 있는 코드가 아닙니다.
참고하세요.

// input으로 const char* key와 const int key_len이 들어오겠죠..

#define HASHED_OUTPUT 20 ;  // 해시된 결과의 길이입니다. SHA-1을 사용한다면 20이겠죠?
#define DATA_BUFFLEN  1024 ;  // 예를 들려고 잡아놓은 버퍼 길이입니다. 실제로 이렇게 사용하면.. 망하는 겁니다.. 정확하게 길이를 계산하여 동적으로 할당하여 사용하세요.
int input_blocksize = 64 ;  // B
unsigned char Ki[HASH_BLOCK_SIZE] = {0, } ;  // K0 ^ ipad
unsigned char Ko[HASH_BLOCK_SIZE] = {0, } ; // K0 ^ opad
char data[DATA_BUFFLEN] = {0, } ;  // 중간 계산값을 저장하기 위한 버퍼입니다.
char hashed_data[HASHED_OUTPUT + 1] = {0, } ;  // 마찬가지로 해시된 값을 저장하기 위한 버퍼입니다.

// 키 길이가 B보다 크면 해시합니다. (3.b 참조)
// 키 길이는 물론 해시 함수의 출력길이가 되겠죠.
if(key_len > input_blocksize)
{
    Ki = Hash(key) ;
    key_len = HASHED_OUTPUT ;
}
else
    memcpy(Ki, key, key_len) ;

memcpy(Ko, Ki, key_len) ;

// 이후 B만큼 나머지 길이를 0으로 채웁니다. (3.c 참조)
for(i=key_len ; i<input_blocksize ; i++)
{
    Ki[i] = 0x00 ;
    Ko[i] = 0x00 ;
}

// ipad와 opad를 이용하여 K0를 미리 계산합니다. (3.d & 3.g)
for(i=0 ; i<input_blocksize ; i++)
{
    Ki[i] ^= 0x36 ;
    Ko[i] ^= 0x5C ;
}

// 위에서 계산한 Ki ^ ipad 와 HMAC의 대상인 text를 연접합니다. (3.e 참조) 
memcpy(data, Ki, input_blocksize) ;
memcpy(data + input_blocksize, text, text_size) ;

// 해시합니다. (3.f 참조)
hashed_data = Hash(data) ;

// Ko ^ opad와 위의 해시한 결과를 다시 연접합니다. (3.h 참조)
memset(data, 0x00, DATA_BUFFLEN) ;
memcpy(data, Ko, input_blocksize) ;
memcpy(data + input_blocksize, hashed_data, HASHED_OUTPUT) ;

// 위의 값을 다시 해시합니다. (3.i 참조)
hashed_data = Hash(data) ;

// 이제 끝입니다.