[정보보호] Cryptographic Hash Functions

Hash Function

해시 함수는 arbitrary 메시지를 fixed size로 condense 하는 함수로, ( h = H(M) ) data integrity를 위해 사용되며 메시지에 변화가 생기면 이를 감지할 수 있다. 좋은 해시 함수란 1) 균등하게 distributed 되고 2) random 한 함수를 말하며, 이러한 해시 함수는 주로 public에 공개되어 있다. 

 

Cryptographic Hash Function

<특징>

암호학적으로 해시 함수는 두 가지 중요한 특징을 갖는다.

1) One-way property: 이는 원본 데이터(preimage)에서 해시 값(image)을 찾기는 쉽지만, 주어진 해시 값에서 원래 데이터를 역으로 찾기는 어렵다는 것이다. 

2) Collision-free property: 이는 서로 다른 두 input에 대해 동일한 해시 값이 생성되는 collision 이 어렵다는 것이다. 하지만 해시 함수는 condensed function 이므로 collision 발생은 무조건 할 수 밖에 없다. 따라서 이 특성은 collision을 발생 시키는 input(preimage)을 찾을 수 있냐 없냐와도 같다. 

 

<적용>

1) Message Authentication: 송신자는 메시지를 해싱하여 해시값을 생성하고, 수신자는 받은 메시지를 해싱하여 생성된 해시 값이 일치하는지를 확인한다. 일치하지 않으면 메시지가 손상되었을 가능성이 있다. 

2) Digital Signature: 해시 함수를 이용해 private key로 메시지에 서명하고, public key로 서명을 확인하여 메시지의 출처를 인증한다. 

3) One-way Password File: 사용자의 비밀번호 저장 시 실제 비밀번호 값이 아닌 비밀번호의 해시 값을 저장하여 보안 강화

4) Intrusion Detection: 시스템에서 이상 행동을 감지하기 위해 데이터의 해시값을 생성하여 변경 여부 모니터링

5) Pseudorandom Function: 특정 input에 대해 랜덤한 결과를 생성하는 함수로, 비밀 키와 input을 조합하여 pseudorandom number을 생성하는데 사용 가능

6) Pseudorandom Generator: 일련의 pseudorandom number을 생성하는 장치

7) Intrusion(침입), Virus Detection: 시스템의 해시값을 지속적으로 유지, 확인

 

---

Hash Function & Message Authentication

일반적으로 message authentication은 MAC(Message Authentication Code)를 사용하여 이루어지며, 이는 keyed hash function E(K, H(M))이라고도 한다. 

 

 

 

Hash Functions & Digital Signatures

 

 

---

Two Simple Insecure Hash Functoins

함수가 XOR 연산으로 구성된 경우, 홀수 개의 error bits 생성 시 vertical parity check처럼 오류를 탐지할 수 있지만, 짝수 개의 error bits 생성 시 오류를 탐지할 수 없다. 

 

1. Bit-by-Bit XOR (= longitudinal redundancy check)

 

Ci는 각 block의 동일한 위치에 있는 비트들을 XOR 해서 얻는다. 

이는 random data에서 data integrity check를 하는 경우 효과적이지만, predictably formatted data에서는 덜 효과적이다. 

 

2. Rotated XOR

1) 초기화: n-bit hash 값을 0으로 초기화 한다.

2) 현재 해시 값을 왼쪽으로 1비트 rotate하고 

3) block을 해시값에 XOR 한다. 

이 방법은 input을 randomize 하여 regularities가 나타나는 것을 방지한다. 이는 data integrity를 확인하는데에는 효과적이지만, 보안의 측면에서는 취약한데 왜냐하면 Rotated XOR로 만들어진 해시값은 원본 메시지를 추적하기 쉽기 때문이다. 

---

Security Requirements

Hash function h = H(x) 일 때, x는 h의 preimage라고 한다. 

collision은 x≠y 이지만 H(x) = H(y)일 때 발생한다. 

예를 들어 해시 값이 n bits이고 input data가 b bits 일 때 (b>n) 각 해시 값은 2^(b-n)개의 preimage와 correspond 한다. 

 

1) Variable input size: 해시 함수 H는 어떤 사이즈의 block of data에도 적용될 수 있다. 

2) Fixed output size: H는 fixed-length output을 생성한다. 

3) Efficiency: H(x)는 어떠한 x에 대해서도 compute 하기 상대적으로 쉽고, 따라서 하드웨어와 소프트웨어의 implementation을 practical 하게 만든다. 

4) Preimage resistant(one-way property): x가 주어지면 H(x)를 computation 하는 것은 쉽지만, H(x)가 주어졌을 때 x 값을 compute 하는 것은 어렵다. 

5) Second preimage resistant(weak collision resistant): x가 주어졌을 때, H(x) = H(y) 이지만 x ≠ y인 y를 찾기가 어렵다. 

6) Collision resistant(strong collision resistant): H(x) = H(y)인 (x,y) 쌍을 찾기가 computationally infeasible 하다. 

7) Pseudorandomness: pseudorandomness를 인정받기 위해서 해시 함수의 output이 randomness test를 통과해야 한다. 

 

해시 함수 특징들 간의 관계

 

 

---

Attacks on Hash Functions

1) Brute Force, Cryptanalysis

2) Preimage 또는 Second Preimage attack

: 주어진 해시 값 H(y)에 대해 y를 찾기 위해서는, 만약 해시값이 m-bit 인 경우 adversary는 평균적으로 2^(m-1)회를 시도하여야 한다. 

3) Collision resistance

H(x) = H(y)인 (x,y) 쌍을 찾기가 computationally infeasible 하다는 것이다. 

 

birthday paradox란 사람이 여러 명 모였을 때 그 중 생일이 같은 두 명이 존재할 확률을 구하는 문제로, 23명 이상의 사람이 모인다면 그 중 생일이 같은 사람 두 명이 존재할 확률은 1/2를 넘는다는 것이다.

이를 응용하여, 만약 uniform distribution을 한 [0, N-1]에서 random variable을 고를 때, 루트 N번의 선택 이후로는 같은 값이 선택될 확률이 0.5 이상으로 증가한다. 또한 m bit 해시값에서 data blocks를 랜덤하게 고른다면, 우리는 같은 해시 값을 가진 서로 다른 2개의 data blocks를 2^(m/2)번의 시도를 통해 고를 수 있다. 

 

 

 

collision attack(=birthday attack)은 birthday paradox를 근거로 한 공격으로, 동일한 해시값을 갖는 데이터의 쌍을 찾는 공격법이다.

1) 메시지 x에 m-bit hash code를 추가해서 서명을 생성한다.  2) opponent는 x에 대한 2^(m/2)개의 variation x'를 만들고 이 메시지와 해시값을 저장한다.  3) opponent는 desired fraudulent 메시지 y에 대해 2^(m/2)개의 variation y'를 만든다.  4) 두 세트의 메시지 x', y'를 비교하여 hash collision이 발생하는 쌍을 찾는다. birthday paradox에 의해 이 확률은 0.5 이상이다.  5) opponent는 user에게 유효 메시지 x에 대한 서명을 요구하고, 그 서명을 위조하고자 하는 메시지 y에 대입하여 valid signature을 생성한다.

 

 

Collision Attack을 방지하기 위해 더 큰 MAC, Hash 함수를 사용해야 한다. 

Collision resistance가 필요한 경우, 2^(m/2) 값이 brute-force attack으로부터 해시 함수의 strength를 결정한다. 

128 bits는 너무 짧아서 불충분하고(ex MD5), 160 bits는 suspect 하다. 

strength를 결정하는 지표

---

Hash Function Cryptanalysis

Cryptanalytic attack은 해시함수 알고리즘의 특성을 이용하기 때문에 exhaustive search보다 빠르다. 

해시 함수는 iterative structure을 가지며, block 단위로 메시지를 처리한다. 이는 Merkle and Damgard의 observation으로부터 기인하는데, 이는 compression function이 collision resistant 하다면, 그 결과로 얻은 resultant iterated 해시 함수 또한 collision resistant 하다는 것이다. 

attack은 함수 f의 collision에 초점을 둔다.

 

Block Ciphers as Hash Functions

block cipher을 해시 함수로 쓸 수 있다.  메시지 M을 M1, M2, ... Mn의 block으로 나누고, 해시값 G를 compute 하기 위해 symmetric encryption E를 하는 것이다.  이는 CBC(Cipher Block Chaining) 과 유사하지만, key가 없다.  만약 해시값 결과가 너무 작다면, 이는 direct한 1) birthday attack 2) meet-in-the-middle attack으로 발생하는 것이다. 이는 다른 attack들에도 취약할 수 있다.

 

 

---

Secure Hash Algorithm (SHA)

<특징>

1) 1993년 NIST와 NSA에서 설계되었다.

2) 1995년 SHA-1로 개정되었다. 

3) DSA signature scheme과 함께 사용하기 위한 US standard

    - standard는 FIPS 180-1 1995, Internet RFC3174 

4) MD4의 디자인에 기반하지만, MD4와 key diffrence

5) 160-bit 해시 값 생성

6) SHA-1에서 발견된 몇가지 보안 문제가 future application에 몇 가지 우려를 제기했다. 2005년에 두 개의 다른 메시지가 동일한 SHA-1 해시값을 가지며, 이를 수행하는데 필요하는 연산 횟수가 생각보다 적다는 것이 발견되었기 때문이. 

 

<revised된 secure hash standard>

1) NIST는 2002년에 FIPS 180-2 개정판 발행 

 : SHA의 3가지 버전 추가 - SHA-256, SHA-384, SHA-512 (통틀어 SHA-2라고 한다.)

2) AES cipher을 통해 보안성 향상

3) 구조와 detail은 SHA-1과 유사하므로, analysis 또한 유사하지만 보안은 향상되었다. 

 

<SHA versions>

 

 

SHA-3

SHA-1은 아직 broken 되지 않았지만, 이와 유사한 MD5와 SHA-0은 broken 된 적이 있으므로 insecure 하다고 여겨진다. 

SHA-2의 경우 (특히 SHA-512)는 SHA-1보다 더 큰 해시값을 가져서 현재까지는 secure 한 것으로 평가받는다. 하지만 SHA-2는 SHA-1과 공통된 구조, 수학적 연산을 가지기 때문에 새로운 보안 취약성이 발견될 수 있고, 따라서 새로운 해시 함수가 필요하다. 그렇게 해서 2007년 NIST는 새로운 세대의 해시 함수인 SHA-3에 대한 competition을 공표했고, 2012 Keccak에 의해 SHA-3이 선정되었다. 

 

<SHA-3 Requirements>

1) SHA-3은 SHA-2를 대체하기 위해 설계되었기 때문에, SHA-2와 동일한 해시 크기인 224, 256, 384, 512 비트의 해시 값을 생성할 수 있어야 한다. 

2) SHA-2의 online nature 유지: online nature은 작은 블록 단위로 메시지를 처리할 수 있는 능력을 의미한다. 따라서 SHA-3은 작은 블록(예: 512 또는 1024 bit)을 효과적으로 처리할 수 있어야 한다.

3) 평가 기준: 

- Security: SHA-3는 SHA-2에 대한 성공적인 공격에 대처할 수 있어야 한다. 
- Cost: SHA-3는 시간 및 메모리 효율성을 유지해야 한다. 
Characteristics: SHA-3는 flexibility, simplicity과 같은 특성을 가지고 있어야 한다. 

---

TLS에서 Hash Collision Attacks

Sloth attack이란 TLS(Transport Layer Security), IKE(Internet Key Exchange), SSH(Secure Shell)과 같은 키 교환 프로토콜에서 발생할 수 있는 Transcript collision Attacks이다. 

 

- K. Bhargavan, “Transcript Collision Attacks: Breaking Authentication in TLS, IKE, and SSH”, NDSS 2016.

 

해시의 Counter-Cryptanalysis

 

Counter-Cryptanalysis는 weak cryptographic primitives를 강화하여 cryptanalytic attack에 대해 강력한 방어를 제공하는 것을 말한다. 강력한 방어 기법의 제공하는 동시에 이는 full backwards compatibility (이전 버전과의 호환성)을 유지하여 MD5, SHA-1처럼 취약한 해시 함수들을 계속해서 안전하게 사용할 수 있게 한다. 

 

- Marc Stevens, “Counter-cryptanalysis”, Crypto 13