HMAC

February 10, 2020

간단한 하드웨어 디자인 관련 글은 블로그에 기록합니다. 그러나 조금 더 기술적인 글은 따로 모아두는 게 낫겠다 싶어, 블로그 포스트가 아닌 일반 페이지에 기록해 볼 생각입니다.

이번에 이야기 하고 싶은 내용은, OpenTitan을 개발하면서 설계한 하드웨어 모듈 중 HMAC (Hash-based Message Authentication Code)입니다. HMAC은 송신자, 수신자가 비밀키를 알고 있다는 가정에서 주어진 메세지가 실제로 상대방이 보냈는 지 알 수 있게 하는 서명 알고리즘입니다.

예를 들면 A라는 사람이 B라는 사람에게 편지를 쓴다고 생각해봅시다. 편지를 손글씨로 썼다면 편지를 쓴 사람의 독특한 필체가 보낸사람을 나타낼 수도 있습니다. 받는 사람이 그 사람의 글씨체를 안다면요. 아니면 보내는 사람이 편지 말미에 자신만의 서명(사인)을 할 수도 있습니다. 서명은 사람마다 제각각이지만 보통 한 사람이 서명은 한 종류만 쓰므로, 글씨체를 통해 알아내는 것 보다는 좀 더 수월합니다. 이 경우에도 상대방이 어떤 서명을 써왔는 지는 이미 알고 있어야겠죠.

HMAC도 이 상황과 비슷합니다. 다만 그것을 디지털세계에 옮겨온 것 뿐이죠. 말미에 자기만의 사인을 하듯이, 디지털 세계에서 데이터를 보낼 때 데이터 끝단에 메세지와 연동 된 나만의 서명을 붙여서 이 내용이 서로 알고 있는 서명으로부터 만들어 졌다는 것을 알려주는 용도입니다. 편지의 서명과 다른 점은, 텍스트가 아닌 어떤 디지털 데이터도 모두 가능하다는 점이고, 서명이 메세지와 따로 놀지 않고 (편지에서는 항상 서명은 똑같죠) 메세지 말미에 따라 붙는 서명은 메세지와 비밀키가 합쳐져서 쓰여진다는 점이죠.

Algorithm

HMAC은 정말 단순합니다. 주어진 메세지를 m이라고 하고, 서로 공유하고 있는 비밀키를 K라고 합시다. 이 때 상대방에게 전달 해 줄 서명은 아래의 순서로 만들어집니다.

  1. K가 일정크기 이상이면 이를 줄입니다 (줄이는 방법은 아래에 설명). 아니면 기존의 비밀키를 그대로 사용합니다.
  2. 키와 특정 값(inner pad)을 서로 더합니다 (XOR 연산).
  3. 이 값과 주어진 메세지 m을 합쳐서 하나의 메세지로 만듭니다.
  4. 이 메세지를 가지고 Hash값을 구합니다. 이 값을 m’이라고 합시다.
  5. 비밀키와 특정 값 (outer pad)을 서로 더합니다 (XOR 연산).
  6. 이 값과 앞에서 계산된 값 m’을 합쳐서 하나의 메세지로 만듭니다.
  7. 이 메세지를 가지고 Hash값을 구합니다.

이렇게 해서 나온 결과가 주어진 메세지에 대한 서명입니다.

복잡해 보이지만 Hash가 무엇인지만 안다면 간단하게 아래처럼 표현할 수 있습니다.

HMAC_SIGN = hash_func(opad_key, hash_func(ipad_key, m))
HMAC Dataflow from OpenTitan

Hash 자체가 메세지 데이터가 조금만 바뀌어도 결과 값이 매우 달라지는 구조라 메세지가 무엇인지 알아도 비밀키를 유추해 내는게 정말 어렵습니다. 이 것을 hash의 보안난이도 (Securiy Strength)라고 부르는데, 일반적인 SHA256/SHA512는 128bit/256bit의 난이도를 가집니다.

그래서 HMAC을 설계할 때 HMAC 자체는 큰 문제가 아니였고 Hash 알고리즘을 설계하는 데에 시간을 더 쏟을 수 밖에 없었습니다.

OpenTitan에서는 필요한 해시 알고리즘이 SHA2-256밖에 없어서 이것을 가정하고 설계하였습니다. 다만 추후에 SHA512나 SHA3 가 추가로 지원될 수도 있을 것 같네요.

자세한 해시 설계는 SHA2 페이지를 참고하여주세요.

Architecture

위의 내용을 바탕으로 간단한 데이터 패스를 아래처럼 설계하였습니다.

HMAC Block Diagram from OpenTitan

먼저 데이터를 임시 저장해 둘 버퍼 (FIFO)가 있구요. 이건 hash 알고리즘에 따라 다르지만 SHA256경우에는 512bit이 한번에 들어가므로 512bit FIFO를 넣었습니다. 그래서 소프트웨어나 다른 DMA엔진이, 다음 해시 계산을 위한 메세지 일부분을 미리 넣어두고 다른 일을 할 수 있습니다.

그 앞단에 packer라는 모듈은 사실 HMAC과는 큰 관련이 없지만 소프트웨어의 편의를 위해서 붙여둔 모듈입니다. 무슨 일을 하냐면, 소프트웨어가 어떤 순서대로 어느 바이트 위치에 값을 쓰던지 그걸 차곡차곡 32bit 하나로 모아서 FIFO에 넣어주는 역할을 합니다. 들어오는 데이터, 예를 들면 소프트웨어의 struct가 하나가 아니라 여러개 일 때에는 두번째, 세번째 struct는 앞 데이터에 맞춰서 shift 시켜줘야 하는데, packer가 있으면 그런거 무시하고 항상 byte0 부터 시작하게 넣어도 됩니다. :)

그리고 HMAC Core 안에서는 순서에 따라 ipad_key를 이용해 hash를 실행시키고, 들어오는 메세지를 이용해 그 다음 hash를 실행시키고, 모든 메세지가 다 들어왔으면 패딩하고 나온 해시값으로 두번째 해시 (opad_key, 1st_round_hash_result)를 실행시킵니다. 간단한 스테이트 머신으로 되어있고 SHA2에서 설명하겠지만 message length가 ipad_key, opad_key 길이만큼 추가되므로, 그 부분을 처리하는 로직이 있습니다.

영어로 된 문서에 조금 익숙하시다면 OpenTitan HMAC Spec 문서를 읽어보시는 것도 좋을 것 같습니다.

개선점

이 부분은 SHA2를 이해 한 후에 읽으면 좋을 것 같네요. 현재 HMAC/SHA256 구조에서는 들어온 데이터를 SHA engine에 넣는 것을 FIFO에서 하나씩 뽑아서 넣는 구조로 되어있습니다. 그런데 FIFO가 레지스터로 이루어져있다보니, 구지 그럴 필요가 없이 한방에 SHA engine으로 넘길 수도 있습니다. 그러면 메세지를 SHA engine 내부의 저장소로 옮기는 16사이클을 절약할 수 있죠. 아니면 SHA engine 내부에서 라운드가 끝나기 16사이클 전에 FIFO에서 하나씩 가져오는 방법도 있긴 하지만, 이 경우에 FIFO에 데이터가 없을 경우까지 고려해야 해서 좀 조건이 까다로워집니다.

만일 한번에 SHA engine으로 넘기는 것을 구현한다면 message padding은 SHA engine에서가 아니라 FIFO (이젠 FIFO라고 부르기도 에매한)에 넣을 때 padding을 해주는 게 padding logic의 크기를 줄이는 방법일 것 같네요. 그렇지 않다면 SHA256경우 512bit, 64byte의 각 바이트마다 padding을 추가해 주는 조건이 들어가야 하거든요. 그러면 mux가 엄청 들어가겠죠. FIFO 앞단에서만 padding을 한다면, 4byte에 대한 패딩만 필요하므로 로직이 현재 패딩로직과 동일할 것으로 예상됩니다.