Cryptographic Hash Functions
암호화 해시함수
- 해시 함수를 통해 암호화하는 방식으로, Plaintext(평문)가 입력값, Ciphertext(암호문)가 해시 함숫값에 해당된다.
- 입력되는 Plaintext를 n-bit Sequence로 간주하고 n-bit Hash Value를 출력한다.
- Random Function을 이용한 암호화 메커니즘이다. (Any Size Input → Fixed Size Output)
- 아래는 암호화 해시함수가 사용되는 분야이다.
- 메시지 암호화
- 메시지 무결성 보장(MAC)
- 경매 입찰가 비밀 보장
- Challenge-Response Spam Filtering (스팸 메일 절감 기술)
- 아래는 대표적인 암호화 해시함수들이다.
- RSA
- MD5
- SHA-1
- SHA-2 Family
- SHA-3 Family
Properties of Cryptographic Hash Functions (암호화 해시함수의 성질)
- Compression (압축)
- 해시 함숫값(출력)의 크기는 평문(입력)의 크기보다 작다. - Efficiency (효율성)
- 해시 함숫값은 빠르게 계산된다.
- 즉, 암호화가 빠르다. - One-Way Property (단방향성)
- \(h(x) = y\) 일 때, \(y\) 를 통해서 \(x\) 가 얼마인지를 알아낼 수 없다. (\(h\)는 해시함수이다.)
- Weak Collision Resistance (약한 충돌 저항성)
- \(h(x) = h(y)\) 일 때, \(x\)와 \(h(x)\)를 알고 있다 하더라도, \(x \neq y\)인 \(y\)가 얼마인지를 알아낼 수 없다.
- 즉, Hash Collision을 발생시키는 값(해시함숫값이 같은 값)을 알아낼 수 있을 확률이 충분히 작은 경우,
"약한 충돌 저항성을 가졌다."라 표현한다. - Strong Collision Resistance (강한 충돌 저항성)
- \(h(x) = h(y)\) 일 때, \(x \neq y\)인 어떠한 \((x, y)\) Pair를 알아낼 수 없다.
- 즉, Hash Collision을 발생시키는 값들(해시함숫값이 같은 값들)을 하나라도 찾아낼 수 없는 경우,
"강한 충돌 저항성을 가졌다."라 표현한다.
(Hash Collision이 발생되지 않음을 보장하는 것은 아니다.)
Types of Attack on Cryptographic Hash Functions (암호화 해시함수에 대한 공격 방법)
- 근본적으로, 암호화 해시함수를 사용한 암호화 메커니즘의 공격은
해시 함숫값을 발생시키는 "해당값"을 찾아내는 것이 아닌,
동일한 해시함숫값을 발생시키는 "어떠한 값"을 찾아내는데 주력한다.
(애초에, 해시 함수는 단방향 함수로, \(h(x)\)값을 통해 \(x\)값이 얼마인지를 찾기가 거의 불가능에 가깝기 때문이다.)
- 즉, Collision이 발생되는 경우를 찾아내는데 초점을 맞춘다.
- 같은 해시값 h(x)를 갖는 x와는 다른 값을 찾기가 직관적으로 굉장히 힘들 것으로 예상되지만,
의외로 해시 충돌(같은 해시값)을 일으키는 값들은 찾는데 생각만큼 그리 오래 걸리지 않는다.
- 이에 대한 이론은 The Birthday Problem(생일 문제)를 참고하자.
* The Birthday Problem (생일 문제) (URL)
[Probability Theory] The Birthday Problem | 생일 문제
The Birthday Problem 생일 문제 - \(n\)명으로 이루어진 모임에서 생일이 같은 두 명의 사람이 있을 확률을 구하는 문제이다. - 이 문제가 갖는 의의는 아래와 같다. "꽤 많은 사람이 모여야 생일이 같은
dad-rock.tistory.com
- 즉, 생일 문제(생일 역설)를 기반으로, 해시 충돌을 일으키는 값들을 찾아내는 비용을 낮출 수 있다.
- 해시 함숫값이 \(n\) Bits일 때, 해시 함숫값의 경우의 수는 \(2^n\) 개이지만,
생일 문제를 통해 우리는 \(\sqrt2^n\) 개의 Random Value만을 탐색해도
50%에 가까운 확률로 충돌을 일으키는 값을 찾아낼 수 있다.
- 암호학에서 생일 문제가 암시하는 바는 아래와 같다.
\(N\) Bit로 구성된 Symmetric Key를 알아내기 위해서는 \(2^{N-1}\) 개의 경우를 조사해야 하지만,
\(N\) Bit로 구성된 Hash Value를 알아내기 위해서는 \(\sqrt {2^{N}}\) 개의 경우만 조사해도 충분하다.
- 그러므로, 해시값의 크기(Bit)를 충분히 크게 확보해놓아야 Break를 방지할 수 있다.
Message Authentication Code (MAC; 메시지 인증 코드)
- Sender가 보낸 메시지가 Receiver가 수신하기 전까지 무단 수정되지 않았음을 보장하는 메커니즘이다.
(즉, 메시지의 무결성을 보장하는 메커니즘이다.)
- 메시지뿐만 아니라, API 호출에 대한 인증, 서버 로그인에도 사용된다.
- Sender는 Receiver에게 메시지와 함께 해당 메시지의 해시값을 함께 전송하고,
Receiver는 메시지를 수신하면 해당 메시지를 해싱하여 동봉된 해시값과 같은지를 비교하는 방식이다.
- MAC이 이행되려면, Sender와 Receiver가 사용할 해시함수 혹은 Key가 사전 협의되어 있어야 한다.
Types of Attack to MAC (MAC 체계에 대한 공격 방법)
- Replay Attack (재전송 공격)
- 가짜 메시지들을 반복적으로 전송하는 공격 방식이다.
- 메시지에 Timestamp 값도 함께 전송하게 하여
허용된 시간 이외에 전송된 메시지는 바로 폐기하는 방식으로 방어할 수 있다.
Challenge-Response Spam Filtering (스팸 메일 절감 기술) (URL)
- 이메일을 전송할 때 발생하는 Cost를 높여 대량 메일 전송을 불가능하게 만든다.
- 이때, 메일 발송인은 메시지(\(M\)), 특정값(\(R\)), 시간값(\(T\))을 해싱한 결과가
지정된 값과 일치할 때까지 반복하며 \(R\)값을 찾아내야 한다.
(이 과정은 오랜 시간이 소요된다.)
- 이때, \(R\)값은 해시값의 앞부분의 0의 개수이다.
- Sender는 해시값의 앞부분이 전부 \(N\)개의 0으로 채워진 수가 나올때 까지 해시함수를 계속 계산해야 하고,
Receiver는 해시값의 앞부분에 \(N\)개의 0으로 채워져있는지만 확인하면 된다.
- Sender는 \(2^N\)에 비례하는 해싱을 수행해야 하고, Receiver는 상수시간에 비례하는 해싱만 수행하면 된다.
(즉, Sender에게만 엄청 힘든 작업이다.)
- \(N\)값을 적절히 설정하는 것이 중요하다.
RSA (Rivest Shamir Adleman)
- 수학자 Rivest, Shamir, Adleman이 개발한 비대칭 암호화 알고리즘을 사용하는 암호 체계이다.
- Plaintext를 두 개의 소수로 변환한 후 이들을 연산하여 Public Key와 Private Key로 구성한다.
- 암호화·복호화에 많은 계산양이 요구되어 Confidentiality(기밀성)를 보장하기에 용이하나
많은 계산량이 요구되는 만큼 암호화·복호화에 많은 시간이 소요된다.
MD5 (Message-Digest Algorithm 5; RFC 1321) (DEPRECATED)
- 1991년에 Ronald Rivest가 개발한 128비트 암호화 해시 함수이다.
- 512비트의 Plaintext를 128비트로 암호화한다.
- 프로그램 혹은 파일이 원본 상태인지를 확인하는 무결성 검사에 사용된다.
- Collision Pair(충돌 쌍; 해시값이 같은 두 값)를 찾는 방법이 공개되어 사용하지 않는 것이 권장된다.
SHA-1 (Secure Hash Algorithm-1; 안전한 해시 알고리즘 1) (DEPRECATED)
- 미국 정부에서 표준으로 지정한, 160-bit 암호화 방식이다.
- RFC 3174 (URL)에 명세되어 있다.
- MD5와 내부 동작 방식이 유사하며,
Modular Arithmetic Operation과 Logical Binary Operation을 사용하여 Hashing한다.
- 2017년에 Break 되어 사용하지 않는 것이 권장된다.
SHA-2 Family (Secure Hash Algorithm-2; 안전한 해시 알고리즘 2)
- SHA-224, SHA-256, SHA-384, SHA-512가 속하는 암호화 방식 군이다.
(뒤에 붙는 숫자는 출력 값의 비트수를 의미한다.)
- 기본 알고리즘은 SHA-1와 동일하다.
- 일반적으로 사용되는 그룹이며, 특별히 높은 보안성이 요구되는 서비스에서는 SHA-3가 사용된다.
* SHA-256 String Hashing Service (URL)
SHA-3 Family (Secure Hash Algorithm-3; 안전한 해시 알고리즘 3)
- SHA3-224, SHA3-256, SHA3-384, SHA3-512가 속하는 암호화 방식군이다.
(뒤에 붙는 숫자는 출력값의 비트수를 의미한다.)
- SHA-2 Family, SHA-3 Family와 다른 방식의 알고리즘으로 동작한다.
- 특별히 높은 보안성이 요구되는 서비스에 사용되는 그룹이며, 일반적인 경우에는 SHA-2가 사용된다.
Reference: Information Security: Principles and Practice 2nd Edition
(Mark Stamp 저, Pearson, 2011)
Reference: 2022학년도 1학기 홍익대학교 네트워크 보안 강의, 이윤규 교수님
