[정보보호] Message Authentication Codes

Message Authentication

<기본 목적>

1) 메시지의 integrity 보호

2) Originator의 identity validate (발신자의 신원 확인)

3) non-repudiation of origin(dispute resolution): 발신자가 메시지를 보냈다는 사실을 부인하지 못하도록 한다. 

 

<Message Authentication Functions: Authenticator을 위한 Alternative functions>

1) Hash function

2) Message Encryption: Encryption 자체가 authenticator로 사용될 수 있다. 

3) Message Authentication Code(MAC)

 

<Requirements>

 

 

Symmetric Encryption for Message Authentication

Symmetric Encryption은 동일한 키를 사용하여 메시지를 암호화, 복호화 하는 방식이다. Symmetric Encryption으로 생성된 ciphertext 자체가 authenticator로써 작용하기 때문에, encryption은 authentication을 제공할 수 있다. 하지만 Symmetric encryption은 Data signature을 만드는데에는 사용하지 못한다. 

 

Symmetric Encryption 이 사용되면, receiver은 두 가지 사실을 알 수 있다. 

1) receiver과 동일한 키를 가진 sender만이 이 ciphertext를 만들 수 있기 때문에, ciphertext의 존재 자체만으로 sender이 encrypt 했다는 것을 알 수 있다. 그렇기 때문에 ciphertext 자체가 authentication 할 수 있는 것이다. 

2) 만약 decrypt 했을 때 plaintext에 random bits와 다른 internal structure이 존재한다면, (즉 plaintext가 well-formed 되어있다면) 메시지 내용이 바뀌지 않았다는 것을 알 수 있다. 

 

 

 

Public Encryption for Message Authentication

Public Encryption에서는 모두가 public key를 알고 있기 때문에, encryption 자체가 sender에 대한 confidence를 주지는 않는다. 하지만 만약 sender이 private-key를 이용하여 메시지를 sign 한다면, 이는 authentication과 signature을 동시에 가질 수 있다. 

 

메시지의 Confidentiality, Authentication, Signature을 유지하기 위해서는 public key를 두 번 사용해야 한다. 첫째로는 public key를 이용해 암호화하여 메시지의 confidentiality를 유지하는 것이고, 둘째로는 (발신자가 자신의 private key로 디지털 서명을 한 후) 수신자가 이 서명을 확인하기 위해 발신자의 public key를 사용하는 것이다. 

 

 

 

---

Message Authentication Code(MAC)

MAC은 small fixed-sized block을 생성하는 알고리즘에 의해 만들어지며, 이 알고리즘은 메시지와 키에 depending 된다.

 

이는 encryption 과정과 비슷하지만 reversible 하지 않고 one-way operation 이므로 encryption 보다 빠르게 만들어진다.  MAC은 메시지에 append 되어 authenticator로써 작용하며, receiver은 수신한 메시지에 동일한 computation을 적용하여 received MAC과 calculated MAC이 일치하는지를 살펴봄으로써 1) 메시지가 unaltered 되었는지를 확인하고 2) 메시지를 alleged sender이 보냈음을 확신하며 3) 메시지에 sequence number이 포함되어 있는 경우 receiver이 올바른 sequence로 메시지를 받았는지를 확신할 수 있다. 

 

efficiency: (b) > (c)&nbsp; // security: (b) < (c)

- (a)를 통해 MAC이 authentication을 생성한다.

- (b),(c)의 경우 secrecy를 위해 encryption을 이용한다. 이 때 MAC과 encryption 과정에는 각각 다른 키를 사용한다. 

(b)의 경우 MAC을 encryption 이전에, (c)의 경우 MAC을 encryption 이후에 compute 한다. 

- 일반적으로 MAC before encryption이 선호되는데, 그 이유는 메시지의 confidentiality를 검증하는 과정에서 암호화의 영향을 받지 않기 때문이다. 하지만 MAC after encryption만이 CCA(Chosen Ciphertext Attack)에 대한 보안을 제공할 수 있다. MAC after encryption이 CCA-secure 하기 위해서는 1) arbitrary CPA(Chosen-Plaintext Attack) Encryption 2) unique tag를 가진 arbitrary secure MAC 두 가지 조건 충족해야 한다. 

 

 

<Encryption 대신 MAC을 사용하는 이유?>

1) Authentication 만 필요한 경우가 존재

2) Encryption보다 Authentication이 길게 유지되어야 하는 경우가 존재 (e.g. archival use - 보안 용도)

3) Flexibility

 

 

<MAC과 Digital Signature의 차이>

Digital Signature은 public key 방식"만" 가능하며, signature을 생성하는 키와 확인하는 키가 다르다. 이는 public key를 공유하는 사람 모두가 특정 인물이 signature을 했다는 것을 확인할 수 있다. 

하지만 MAC은 sender, receiver이 동일한 키를 공유한다. 예를 들어 A와 B가 키를 공유하고 A가 B에게 메시지를 보낸 경우, 메시지가 올바르게 decryption 된다면 B는 A가 메시지를 보냈다고 확인할 수 있다. 즉 이는 키를 공유하고 있는 A와 B만 할 수 있고 public 한 인증은 불가능하다.

 

 

<MAC Properties>

1) MAC은 Cryptographic checksum

variable-length 메시지 M을 비밀키 K를 이용하여 고정된 크기의 authenticator로 condense 한다. 

 

2) Many-to-One Function: MAC은 다대일 함수로, 여러 메시지가 동일한 MAC을 가질 수 있는 가능성이 있지만 이를 찾는 것은 굉장히 어렵다. 

 

 

<Requirements for MACs>

MAC은 taking into the types of attacks(공격의 다양한 유형을 고려해야 한다.)

1) message replacement attack 방지: message replacement attack은 공격자가 특정 메시지와 그에 해당하는 MAC을 가지고 있을 때, 이와 동일한 MAC을 가지는 다른 메시지를 찾는 것을 의미하므로, 보내고자 하는 메시지의 MAC과 동일한 MAC을 가지는 다른 MAC을 찾기 어렵도록 하는 것이 중요하다.  

2) Brute-force Attack 방지: MAC 값이 가능한 모든 메시지에 대해 균일하게 분포되어야 한다. (즉 중복되는 MAC 값이 적어야 한다.)

3) MAC은 메시지의 모든 비트에 골고루 의존해야 한다. 즉 "특정 비트에 대한 변화가 MAC에 영향을 주는 정도"가 모든 비트가 유사해야 한다는 것이다. 

 

 

<Security of MACs>

1. Brute-force attack 시, 해시함수의 보안은 주로 해시 코드의 길이에 달려있다. 예를 들어 strong collision resistance 해시는 푸는데 2^(m/2)의 cost가 든다. (따라서 128bits에서는 취약해보이지만 160bits는 더 강력한 보안을 가진다.) 

MAC을 brute-force attack 하기 위해서는 known message - MAC pair을 필요로 한다. 이는 두 가지 방식으로 brute-force 공격이 가능하다. 보안을 위해서는 최소 128-bit의 MAC이 필요하다. 

 

1) key space를 공격하는 경우: key 길이가 k일 때 , 어떤 key가 주어진 메시지를 주어진 MAC으로 변환하는지 2^k 번의 시도를 통해 찾을 수 있다. 

2) MAC 값을 직접 공격하는 방식: 공격자가 메시지-MAC 쌍을 안다고 하자. MAC의 길이가 n bit일 때, 저 메시지-MAC 쌍을 통해 공격자가 대체하려는 메시지에 해당하는 MAC이 정당한지를 2^n번의 시도를 통해 알아낼 수 있다. 

∴  level of effort : min(2^k, 2^n)

 

2. Cryptanalytic attacks는 암호의 structure exploitation(구조를 악용) 하고자 한다. 

암호 체계가 안전하다는 것은, block cipher과 같이 brute-force 공격이 최선(best alternative)이라는 것이다. 

MAC은 block cipher과 다르게 다양한 MAC 알고리즘이 존재하므로 구조적 다양성을 가진다. 

즉 MAC은 다양한 구조를 통해 보안성을 유지하고, 따라서 cryptanalytic attacks에 대비할 수 있다. 

---

HMAC

<Hash Function에 기반한 MAC>

MAC 생성 시 해시 함수를 사용하는 이유는 빠르고, 간단하며 crypto hash function code는 널리 공개되어 있어 사용하기 편리하다.

 

초기 MAC에서는 key를 메시지에 함께 넣어 해싱하는 방법이 사용되었다. 

MAC의 Original proposal

하지만 이 방법에는 몇몇 약점이 존재했기 때문에, 이는 HMAC의 발전으로 이어졌다. 

 

<HMAC의 설계 목적>

1) HMAC은 새로운 해시 함수를 개발할 필요 없이 기존의 해시 함수를 수정하지 않고도 적용할 수 있어야 한다. 

2) 새로운 기술이 등장하거나 보안 요구사항이 생길 경우, HMAC은 내장된 해시 함수를 쉽게 교체할 수 있어야 한다. (easy replaceability)

3) HMAC을 사용하여 메시지를 인증할 때 원래 해시 함수의 성능이 크게 저하되지 않아야 한다. 

4) HMAC은 키를 간단하게 처리하고 사용할 수 있어야 한다.

5) HMAC은 강력한 cryptographic analysis 를 통해 authentication 메커니즘의 강도를 신뢰할 수 있도록 보장해야 한다.

 

<특징>

1) internet standard RFC2104로 지정됨

2) HMAC은 메시지에 해시 함수를 적용한다. 이 때 어떠한 해시 함수라도 사용될 수 있다. (e.g. MD5, SHA-1, RIPEMD-160, whirlpool)

- K+: 비트 크기 b를 맞추기 위해 왼쪽에 0으로 패딩된 key이다. 

- opad와 ipad는 특정한 패딩 상수로, 각각 00110110과 01011100이 비트 크기 b/8만큼 반복된 값이다. 

 

HMAC Security

HMAC의 보안은 주로 underlying 하는 해시 알고리즘의 보안성과 관련이 있다. 

HMAC을 공격할 때는 1) Key를 Brute force 하거나(2^n 소요) 2) Birthday attack(해시 collision을 찾아내는 공격: 2^(n/2) 시간 필요)를 해야 한다. 그러나 HMAC은 key를 사용해 메시지를 처리하기 때문에, 공격자가 성공적으로 공격을 하기 위해서는 동일한 키로 암호화 된 2^n개의 block을 관측해야 한다. 따라서 보안에 취약하다고 알려진, 128 bit의 MD5 또한 HMAC에서 사용된다면 키를 사용하고 메시지를 추가적으로 해싱하기 때문에 충분한 보안을 제공할 수 있다. 

---

Block Ciphers에 기반한 MAC

어떤 Cipher Block Chaining mode(CBC)든지 쓰고, final block을 MAC으로써 쓸 수 있다. 

1) DAA → 이제 obsolete(구식)이라 여겨짐  2) Cipher-based message authentication code(CMAC): DAA의 단점 보완

DAA(Data Authentication Algorithm)

DAA는 DES-CBC에 기반한 widely used MAC으로, MAC으로써 final block만 보낸다. 이는 Ⅳ(initialization verctor)을 0으로 설정하고, 마지막 block에는 zero-padding을 사용하는데 이것은 마지막 block을 채우기 위해 0을 사용하는 것을 뜻한다. 

final block의 왼쪽에서부터 M bit(16~64 사이)를 사용하거나 final block 전체를 MAC으로 쓰는데, 충분한 비트 수를 사용하지 않으면 final MAC이 너무 작아져 보안에 취약할 수 있다. 

증명 : E(K, [T ⊕ (X ⊕ T) ] ) = E (K, ??? T?

 

이는 정부&산업에서 널리 사용되지만, 메시지 크기 제한이 있다. (mn bits: m - fixed positive integar / n: cipher block size)

또한 DAA가 사용하는 CBC-MAC에는 보안 취약점이 존재한다. 

예를 들어 one-block으로 구성된 메시지 X와, 그 X에 대한 CBC-MAC 값이 T로 주어졌다고 하자. ( T=MAC(K,X) )

adversary가 다음과 같은 two-block message에 대한 CBC-MAC 값을 안다면, 이 말은 이 정보를 이용하여 보다 큰 메시지에 대한 MAC을 유도할 수 있다는 것을 말한다. 

two-block message

 

CMAC

CMAC은 3개의 key를 사용하며 DAA의 한계점을 극복할 수 있다. 이는 NIST SP800-38B에서 채택되었다. 

---

Authenticated Encryption

Authenticated Encryption은 통신의 confidentiality와 authenticity를 동시에 보호할 수 있다. 이 때 confidentiality와 authenticity는 주로 동시에 필요하지만, 이 둘을 보호하는 메커니즘은 대체로 따로 다루어진다. 

 

Authenticated Encryption에는 두 가지 모드의 operation이 있는데, 1) CCM(Counter with Cipher Block Chaining - Message Authentication Code) 2) GCM (Galois/Counter Mode)이다. 

 

CCM(Counter with CBC-MAC)

CCM은 NIST에서 제정한 표준인 SP 800-38C로 정의된 암호화 및 인증 모드로, 이는 주로 Wi-Fi와 같은 무선 네트워크에서 사용되지만 모든 네트워크에서 authentication encryption을 위해 사용될 수 있다. 

 

<특징>

1. encrypt-and-MAC approach의 변형: data integrity, confidentiallity 제공

2. 알고리즘 구성 요소

1) AES encryption  2) CTR mode of operation: block cipher 사용  3) CMAC(cipher-based MAC) authentication 알고리즘

3. encryption, MAC에 동일한 single key가 사용

4. Input elements

1) data block의 Plaintext message P: authenticated, encrypted

2) associated data A: authenticated, not encrypted. 메시지와 관련된 부가 정들

3) Nonce N: 모든 instance에서 다르게 사용되어, replay attack을 방지한다. 

 

 

GCM(Galois/Counter Mode)

GCM은 NIST에서 제정한 SP 800-38D 표준에 따른 암호화 모드로, 높은 처리량(high throughput)에서 병렬로 처리 가능하여(parallelizable)  고속으로 동작한다. 이는 무선통신, TLS, IPsec와 같은 프로토콜에서 채택되어 안전한 통신을 제공한다.

 

GCM은 CTR의 variant를 사용하여 메시지를 encrypt 하는데, CTR은 block 단위로 메시지를 나누어, 카운터 값을 사용하여 encrypt를 한다. 그렇게 만들어진 ciphertext는 G(2^128) 상에서 key와 메시지 길이와 곱해져 authenticator tag를 생성한다.

 

이렇게 encryption & authentication 을 동시에 제공하는 모드 이외에도, GCM은 GMAC이라고 하는 MAC-only mode 또한 지원한다. 

 

GCM이 쓰는 두 가지 function에는 다음이 있다.

1) GHASH: keyed hash function - ciphertext를 G(2^128) 상에서 키, 메시지 길이와 곱하여 authenticator tag 생성

2) GCTR: CTR mode의 variant로, 증가된 카운터 값을 사용하여 블록을 암호화

 

 

 

 

---

해시함수, MACs를 사용한 Pseudorandom Number Generation

PRNG에 있어서 필수적으로 필요한 요소는 다음과 같다. 

1) Seed value: 초기값으로, 이 seed는 생성되는 pseudorandom number의 예측을 막기 위해 필요한 사용자만 알아야 한다. (e.g. PRF, stream encryption function)

2) Pseudorandom bit generation을 위한 Deterministic 알고리즘

 

<Implementation>

이러한 PRNG는 여러 방식으로 구현될 수 있다. 

1) Encryption Algorithm

2) 해시 함수(ISO 18031 & NIST SP 800-90)

 

3) MAC (NIST SP 800-90)

 

---

Multi-user Security of GCM in TLS

 

TLS에서 GCM은 통신의 confidentiality와 integrity를 보장하기 위해 사용되며, 이는 Multi-user 환경에서도 안전하게 사용될 수 있도록 설계되었다. MU security는 하나의 공격자가 여러 통신 세션에 접근하여 적어도 한 세션의 보안을 침해하려는 상황을 다루며, 구체적으로 여러 user 중 하나의 GCM 키를 찾아내려는 공격을 의미한다. TLS 1.3에서는 여러 세션 간 키를 안전하게 유지하고 각 세션의 보안성을 보호하는데 중점을 둔 설계가 이루어졌다. 

 

논문) The Multi-user Security of Authenticated Encryption: AES-GCM in TLS 1.3

 

Lucky Thirteen Attack

 

Lucky thirteen attack은 timing-side channel attack(암호화 통신에서 발생하는 응답시간의 차이를 이용하여 키 또는 메시지를 추측하는 공격)을 이용한 MAC implementation에 대한 공격이다. 이는 padding oracle attack(암호화된 메시지의 padding의 오류에 대한 서버의 응답을 분석하는 공격기법)의 variant로, TLS(Transport Layer Security) 및 DTLS(Datagram Transport Layer Security)의 record protocol을 break 하는데 사용된다.  

 

Lucky Thirteen: Breaking the TLS and DTLS Record Protocols (IEEE S&P 2013)