Message authentication codes

froajnzd·2024년 12월 5일

Cryptography

real world cryptography

목록 보기

3/12

이번 장에선 메세지 인증 코드, 즉 MAC에 대해서 알아보겠다. MAC는 데이터를 보호하기 위해 해시 함수와 비밀 키를 결합한 암호학적 원시 함수이다. 이를 통해 데이터의 무결성과 인증을 보장할 수 있다.

Stateless cookies

보통 쿠키는 아래 그림과 같이 사용자의 정보를 저장하고 서버와의 상태를 유지하기 위하여 사용된다.

그러나 악성 공격자가 쿠키의 내용을 원하는 대로 수정하여 서버와 통신할 수도 있다. 왜냐하면 여기서 쓰인 hash 함수는 누구나 아는 공개 알고리즘이기 때문이다.

이런 문제점으로 인해 MAC을 사용하는 방법을 고안해볼 수 있다.

MAC

해시함수와 비슷한 primitive이다.
secret key를 받고, 고유한 출력(authentication tag)을 생성한다.
동일한 secret key와 동일한 메세지가 있다면, MAC은 동일한 인증 태그를 생성한다.
즉, 공격자가 쿠키를 변조하여도 유효한 authentication tag를 위조할 수는 없다.

Security properties of a MAC

MAC이 제공하는 보안 속성과 올바르게 사용하는 방법에 대해 기술하겠다.

1. Forgery of authentication tag(인증 태그 위조)

일반적으로 MAC의 보안 목표는 새 메세지에서 authentication tag의 위조를 방지하는 것이다.
즉, secret key k에 대해 모르면, 메세지 m에 대한 인증 태그 t = MAC(k, m)을 계산할 수 없다.

2. Lengths of authentication tag

보안을 위하여 충돌이 일어나지 않게 해야한다.
birthday bound에 따라 알고리즘의 출력 길이가 짧을 경우에 collision을 찾을 수 있는 가능성이 높아진다.

64 bit authentication tag인 경우 > 232번의 요청으로 충돌을 찾을 수 있다.
$2^{64}$ authentication tag인 경우 > 초당 1Gbps 속도로 요청하더라도 $2^{64}$ 번 시도를 하기 위해 25만년이 걸린다.
128 bit authentication tag를 많이 사용한다.

128 bit authentication tag를 사용하면, hash 함수에서 256 bit의 출력을 낸다. 뭔가 직관적이지 않지 않은가?
해시 함수는 오프라인에서 계산할 수 있는 공개 알고리즘이므로 오프라인에서 병렬로 연산하여 공격 속도를 높일 수 있다.
그러나 MAC은 비밀 키를 사용하므로, 공격자가 태그를 생성하려면 반드시 서버에 직접 요청해야 한다. 이는 오프라인 공격보다 훨씬 느리다.

128 bit MAC은 $2^{64}$ 번의 요청이 필요하다.(충분히 안전하다)
더 높은 보안을 원한다면 256 bit를 사용할 수도 있음

3. Replay attacks

replay attack은 공격자가 이전에 전송된 데이터를 가로챈 후 이를 나중에 그대로 다시 전송하여 공격하는 방식이다.

예로,
a. Alice가 은행 서버에 "Bob에게 $200 송금" 메세지를 보낸다
b. 공격자가 이 메세지를 가로챈다.
c. 나중에 공격자가 같은 메세지를 서버에 다시 보낸다. 서버는 새 요청으로 간주하고 Bob에게 $200을 또 송금한다.

MAC은 왜 재전송 공격을 막을 수 없나?

MAC은 중복된 메세지인지 여부를 판단할 수 없다. 메세지가 올바르게 서명되었는지 확인하는데만 사용한다.

추가 대책

sequence numbers : 메세지에 순번을 포함하여, 서버는 순번이 예상 값과 일치하는지 확인하여 요청의 중복 여부를 판단한다.

4. verifying authentication tags in constant time

: 일정시간 내에 authentication tag 검증

위 그림에서, authentication tag로 0X XX XX를 보냈을 때 첫자리가 틀렸기 때문에 1t 시간만에 검증이 끝났지만
A0 00 00로 보냈을땐 첫 자리는 맞았기에 검증에 걸리는 시간이 2t가 되었다.
따라서, authentication tag 검증 시 수신한 authentication tag와 새롭게 계산된 tag의 비교가 constant time 내에 이뤄져야 한다.

상수 시간 내에 비교하려면 코드를 이처럼 작성해야 한다. 분기(branch)를 가지면 안된다.

for i := 0; i < len(x); i++ {
	v |= x[i] ^ y[i]
}

MAC in the real world

사람들이 실제 환경에서 MAC을 어떻게 사용할까?

1. Message authentication(메세지 인증)

두 기계(사용자) 간 통신이 변조되지 않기 위해 사용된다
통신이 'cleartext(일반텍스트)'로 이루어지거나 통신이 암호화되는 경우 모두에 필요하다.

2. deriving keys(키 파생)

MAC의 특징 중에 '해시 함수처럼 무작위로 보이는 바이트를 생성'하도록 설계됐다는 특징이 있다.
이를 통해 '단일 키를 구현'하여 '난수를 생성'하거나 '더 많은 키를 생성'할 수 있다

PRF (The pseudorandom function)
슈도코드 함수.
랜덤 함수처럼 보이도록 설계된 함수.
(완전히 랜덤하지는 않지만, 랜덤함수처럼 작동하고, 랜덤처럼 보인다.)
실제로는 알고리즘과 키로 정의된 '결정론적인 함수'다

PRF를 기반한 MAC = HMAC

3. integrity of cookies(쿠키의 무결성)

사용자의 브라우저 세션을 추적하려면 무작위 문자열(메타데이터와 연결됨)을 보내거나 인증 태그가 첨부된 메타데이터를 직접 보내 수정할 수 없도록 한다.

4. Hash Tables(해시 테이블)

대부분의 프로그래밍 언어는 비암호학적(noncryptographic) 해시 함수를 사용한다

이 함수는 빠르고 간단하지만, 보안 목적으로 설계된 것은 아니다.

공격자가 해시 테이블에 입력 값을 조작하여 DoS(서비스 거부) 공격을 일으킬 수 있다.

예) 공격자가 입력 데이터를 정교하게 설계하면, 해시 함수가 동일한 해시 값을 반환하도록 유도합니다(충돌 발생).
결과적으로, 해시 테이블이 효율적으로 동작하지 않아 프로그램 성능이 급격히 저하되거나 멈출 수 있습니다.

해결 :

Rust, Python, Ruby 언어, Linux kernel은 SipHash라는 MAC을 해시 함수로 사용한다.
프로그램이 시작될 때 무작위 키를 생성하여 해시 계산에 사용
DoS 공격을 방지하기 위한 최적화된 선택