[암호] 해시 함수

1. 일방향 해시 함수(One-way hash function)

• 입력과 출력이 1개씩 있다.
• 입력은 메시지(message) 출력은 해시값(hash value)로 부른다.
• 일정한 크기의 출력을 가지고 있다. 입력값이 어떤 값이든 출력값의 크기는 항상 정해져 있다.
• 일방향성을 갖는다. 해시 값으로부터 메시지를 계산할 수 없다.
• 메시지가 다르면 해시 값도 달라야 한다. 메시지가 1비트라도 변하면 해시 값은 높은 확률로 다른 값이 되어야 한다.
• 계산 속도가 빠른다.
• 정보보호의 3요소(기밀성, 무결성, 가용성) 중 무결성을 제공한다.

 

2. 해시 함수의 충돌

☞ 충돌 (Collision) 

: 2개의 다른 메시지가 같은 해시 값을 갖는 것으로 입력값의 길이가 정해져 있지 않기 때문에 충돌이 생길 수 있다.

 

☞ 충돌 내성 (Collision Resistance)

: 충돌을 발견하는 것이 어려운 성질이다.

 

2-1. 프리미이미지 저항성(역상 저항성)

y = h(M)에 대해 메시지 M을 찾는 것이 계산적으로 불가능하다.

어떤 해시 값에 대해서, 원래 입력 값을 찾는 어려워야 하며, 이를 일방향성(One-wayness)이라고 한다.

 

2-2. 제2 역상 저항성(약한 충돌 내성)

h(M) = h(M'), M≠M'을 만족하는 다른 입력 값 M'을 찾는 것이 어렵다.

어떤 입력 값에 대하여, 그 입력값의 해시값과 같은 해시값이 갖는 또다른 입력값을 찾는 것이 어려워야 한다.

 

2-3. 충돌저항성(강한 충돌 내성)

h(M) = h(M')과 같이 동일한 다이제스트를 가지는 2개의 메시지(M, M')를 구하는 것이 계산적으로 불가능하다.

 

3. 해시 함수 관련 용어

• 일방향 해시 함수 = 메시지 다이제스트 함수 = 메시지 요약 함수 = 암호적 해시 함수
• 입력값 = 일방향 해시 함수이 입력이 되는 메시지 = 프리-이미지(Pre-Image)
• 출력값 = 해시 값(Hash Value) = 메시지 다이제스트(Message Digest) = 핑거프린트(Fingerprint)

 

4. 해시 함수 응용

4-1. 소프트웨어의 변경 검출

자신이 입수한 소프트웨어가 변경 되었는지를 확인하기 위해 일방향 해시 함수를 사용한다.

다음 그림은 httpd.apache.org/download 사이트의 일부이다. SHA256, SHA512와 같이 소프트웨어에 대한 원본 해시값이 있다.

4-2. 패스워드를 시초로 한 암호화

PBE에서는 패스워드와 솔트(salt)를 섞은 결과의 해시 값을 구해 그것을 암호화 키로 사용한다.

패스워드 사전공격(Dictionary attack)을 방어한다.

(ex) 리눅스 패스워드(SHA512) -  솔트 값은 시간에 기반하여 생성된다. 암호는 해시 함수로 계산한다.

(ex) 윈도우 시스템(NTLM)의 encrypted password - 해시 함수를 여러번 돌린다.

 

4-3. 메시지 인증 코드( MAC, Message Authetication Code )

"송신자와 수신자만이 공유하고 있는 키"와 "메시지"를 혼합해서 그 해시 값을 계산한 값이다.

통신 중의 오류나 수정 그리고 "가장(spoofing)"을 검출 가능하다.

무결성과 인증을 제공한다. 송신자와 수신자가 공유하고 있는 키를 기반으로 인증하기 때문에 송신자가 수신자의 진위여부를 확인하거나 수신자가 송신자의 진위여부를 확인할 순 있어도(인증 제공), 송신자가 그 키를 가지고 나쁜 짓을 했을 때 수신자가 했다고 우길 수 있기 때문에  부인방지를 제공하지는 못한다.

SSL/TLS, ssh, https, IPsec 기반 VPN 통신 등에 쓰인다. 

 

4-4. 파일의 진위 확인

어제 만든 파일의 해시값과 오늘 만든 파일의 해시값을 비교하여 파일의 무결성을 조사한다.

ex) Tripwire

ex) 리눅스 시스템에서 파일의 해시값 비교 & 파일의 진위 여부 확인

# diff file1.txt file2.txt

# md5sum file1.txt; # md5sum file2.txt

 

4-5. 디지털 서명에 이용

처리시간 단축을 위해 일방향 해시 함수를 사용해서 메시지의 해시 값을 일단 구하고, 그 해시 값에 대해 디지털 서명을 수행한다.

 

4-6. 의사난수 생성기(PRNG)

"과거의 난수열로부터 미래의 난수열을 예측하는 것은 사실상 불가능"이라는 예측 불가능성을 보증하기 위해 일방향 해시 함수의 일방향성을 이용한다.

 

4-7. 일회용 패스워드, 원타임 패스워드(One-Time Password)

정당한 클라이언트인지 아닌지를 서버가 인증할 때에 사용한다.

일방향 해시 함수를 써서 통신 경로 상에 흐르는 패스워드를 1호(one-time)만 사용하도록 고안됐다.

패스워드가 도청되어도 악용될 위험성이 없다.

은행에서 발급하는 암호카드를 대신할 수 있는 OTP ( 금융거래(ex: 이체) => 개인 인증서(인증서암호), 암호카드(OTP))

 

5. 일방향 해시 함수 예

5-1. MD4

Rivest가 1990년에 만든 일방향 해시 함수로 128비트의 해시 값을 갖는다.

Dobbertin에 의해 충돌 발견 방법이 고안됐다.

현재는 안전하지 않다.

 

5-2. MD5

Rivest가 1991년에 만든 일방향 해시 함수로 128비트의 해시 값을 갖는다.

암호해독에 취약함을 보여주는 여러가지 암호 해독 방법들이 개발됐다.

MD5가 완전히 뚫린 것은 아니지만, MD5 내부 구조의 일부에 대한 공격 방법이 몇 개 발견됐다.

사용을 권장하지 않지만 출력값의 크기가 작기 때문에 비교(checksum)하는 용도로 쓰인다.

 

5-3. SHA

미국 국가안보국(NSA)이 1993년에 처음으로 설계했으며 미국 국가 표준으로 지정되었다. SHA 함수군에 속하는 최초의 함수는 공식적으로 SHA이지만 SHA-0라고도 불린다.

SHA-0는 얼마지나지 않아 표준이 폐기되었고, 1995년에 SHA-1이 새로 출판된다. SHA-1은 SHA-0의 압축 함수에 비트 회전 연산을 추가한 것이다. NSA에 따르면, 암호학적 보안을 감소시키는 문제점을 고쳤다고 한다.(실제 문제점을 공개하진 않음)

SHA-0와 SHA-1은 최대 264비트의 메시지로부터 160비트의 해시값을 만들어 낸다. 로널드 라이베스트가 만든 MD4와 MD5 해시함수에서 사용했던 것과 비슷한 방법에 기초한다.

이후, 4종류의 변형, 즉 SHA-224, SHA-256, SHA-384, SHA-512가 더 발표되었다. 이들을 통칭해서 SHA-2라고 하기도 한다. 2002년에 SHA-1과 함께 정식표준으로 지정되었다.

알고리즘	해시값 크기	내부상태 크기	블록 크기	길이 한계	워드 크기	과정 수	사용되는 연산	충돌
SHA-0	160	160	512	64	32	80	+,and,or,xor,rotl	발견됨
SHA-1	160	160	512	64	32	80	+,and,or,xor,rotl	발견됨
SHA-224 /256	224/256	256	512	64	32	64	+,and,or,xor,shr,rotl
SHA-384 /512	384/512	512	1024	128	64	80	+,and,or,xor,shr,rotl

※ 출처 : 위키백과

 

5-4. SHA(Advanced Hash Standard)와 SHA-3

NIST는 SHA-1을 대체하는 차세대 일방향 해시함수로 2007년에 "SHA-3" 선정 시작

AES와 같은 경쟁 방식으로 표준화됐다.

2012년 선정 완료됐다. - KECCAK(케챡)을 표준으로 선정

 

※  KECCAK(케챡)

SHA3-224, SHA3-256, SHA3-384, SHA3-512 4종류가 SHA-3으로 규정

SHAKE128과 SHAKE256이라는 임의 길이의 출력을 가진 함수(XOF, Extendable-Output Function)를 규정
* SHAKE = Secure Hash Algorithm + KECCAK

 

5-5. RIPEMD-160

1996년에 Hans Dobbertin, Antoon Bosselears, Bart Preneel이 제작한 European Union RIPE 프로젝트로 만들어진 RIPEMD 함수의 개정판이다. 160비트의 해시 값을 갖는다.

 

5-6. LSH(Lightweight Secure Hash)

TTA(한국정보통신기술협회)에 NSR에서 제안한 국내표준 해시함수(2015.12)이다.

개발연도: 2014년

알고리즘 구분: 해시 함수

출력 길이: 224비트, 256비트, 384비트 또는 512비트

구조: Wide-pipe Merkle Damgaard 구조

다양한 SW 환경에서 국제 표준(SHA2/3) 대비 2배 이상 성능을 가지고 있다.

메시지 인증, 사용자 인증, 전자서명 등 다양한 암호 응용 분야에 사용된다.

 

사용하면 안되는 해시 함수	현대 해시 함수
SHA-1 MD2 MD5 PIPEMD-160 Keccak	(SHA-2) SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256 (SHA-3) SHA3-224, SHA3-256, SHA3-384, SHA3-512 (BLAKE2) BLAKE2s, BLAKE2b (SHAKE) SHAKE128, SHAKE256

 

6.  해시 함수 공격

충돌 공격

역상 공격

생일 공격

무차별 대입 공격

레인보우 테이블

부채널 공격

 

7. 리눅스에서 사용할 수 있는 해시 함수

md5sum, shasum, sha1sum, sha224sum, sha256sum, sha384sum, sha512sum