암호화 해시 함수

3. 암호화 해시 함수의 응용

암호화 해시 함수는 정보 보안 분야에서 다양하게 활용된다. 디지털 서명, 메시지 인증 코드(MAC), 기타 인증 기술 등이 대표적인 예시이다.

앨리스가 밥에게 어려운 수학 문제를 제시하고 자신은 답을 알고 있다고 주장하는 상황을 가정해 보자. 밥은 앨리스가 허세를 부리는지 확인하기 위해 앨리스에게 해답에 임의의 문자열(nonce)을 붙여 계산한 해시 값을 요구한다. 며칠 후 밥이 문제를 풀면 앨리스는 자신의 해답과 nonce를 공개하여 증명할 수 있다. 이는 커밋먼트 스키마의 간단한 예시이다.

이 외에도 데이터 무결성 검증, 파일 식별, 비밀번호 해시(키 유도 함수#비밀번호 해시) 등에 사용된다. 비밀번호는 유출을 막기 위해 평문이 아닌 다이제스트 형태로 저장되며, 디지털 서명 알고리즘에서도 메시지 자체 대신 메시지의 다이제스트에 서명하는 방식으로 보안 및 성능상의 이점을 얻는다.

P2P 파일 공유 네트워크에서는 MD4 해시와 파일 크기를 조합하는 ed2k 링크나 Magnet 링크와 같이 파일 식별을 위해서도 해시가 사용된다.

3. 1. 데이터 무결성 검증

3. 2. 디지털 서명

3. 3. 메시지 인증 코드 (MAC)

3. 4. 비밀번호 저장

3. 5. 작업 증명 (Proof-of-Work)

3. 6. 파일 또는 데이터 식별

4. 암호화 해시 함수 설계

암호화 해시 함수는 주로 블록 암호를 사용하여 만들어진다. 특히 일방향 압축 함수를 구축하는 데 여러 방법이 사용되며, 이러한 방법들은 암호화에 사용되는 블록 암호 운용 방식과 유사하다.

MD4, MD5, SHA-1, SHA-2 등 잘 알려진 해시 함수들은 블록 암호와 유사한 구성 요소로 만들어졌으며, 결과 함수가 되돌릴 수 없도록(일방향성) 피드백을 제공한다. SHA-3 결선 진출자에는 Skein, BLAKE와 같이 블록 암호와 비슷한 구성 요소가 있는 함수들이 포함되었지만, 최종 선택된 Keccak은 암호화 스펀지를 기반으로 만들어졌다.

AES와 같은 표준 블록 암호를 사용할 수도 있다. 이는 임베디드 시스템처럼 코드 크기나 하드웨어 영역을 최소화하여 암호화와 해싱을 모두 구현해야 할 때 유용할 수 있다. 그러나 이 방식은 효율성과 보안에 영향을 줄 수 있는데, 해시 함수용 암호는 큰 키와 블록을 사용하고, 블록마다 키를 효율적으로 변경하며, 관련 키 공격에 강하도록 설계되기 때문이다. 반면 범용 암호는 다른 설계 목표를 갖는다.

4. 1. 머클-담고르(Merkle–Damgård) 구조

5. 암호화 해시 알고리즘 종류

암호화 해시 알고리즘에는 여러 종류가 있으며, 각각은 보안 강도, 속도, 출력 길이 등에서 차이를 보인다.

MD5와 SHA-1은 한때 널리 사용되었으나, 현재는 안전하지 않은 것으로 알려져 있다. 2008년 미국 US-CERT는 MD5를 사용하지 말 것을 권고했고,^[37] 미국 국립표준기술연구소(NIST)는 SHA-1 사용 중단을 발표하고 SHA-2 사용을 권장했다.^[38] NIST는 2008년에 SHA-3 공모전을 열었고, 2012년에 최종 후보를 선정할 예정이었다.^[39]

여러 해시 함수의 출력을 연결하면 연결된 결과에 포함된 가장 강력한 알고리즘만큼의 충돌 저항성을 제공한다. 예를 들어, 이전 버전의 TLS/SSL은 연결된 MD5와 SHA-1 합을 사용했다. 그러나 메르클-담고르드 구조 해시 함수의 경우, 연결된 함수는 가장 강력한 구성 요소만큼 충돌 저항성이 있지만 그 이상은 아니다.

다음은 널리 알려진 암호화 해시 함수 알고리즘의 일부 목록이며, 아래의 표에 있는 알고리즘을 포함한 더 자세한 목록은 암호화 해시 함수 비교에서 확인할 수 있다.

5. 1. 안전하지 않은 알고리즘

5. 2. 널리 사용되는 알고리즘

6. 암호화 해시 함수에 대한 공격

MD5와 SHA-1은 널리 사용되던 해시 함수였으나, 안전하지 않다는 것이 알려져 더 이상 사용되지 않는다. 미국 US-CERT는 2008년에 MD5 사용 중단을 권고했고^[37], 미국 국립표준기술연구소(NIST)는 2008년에 SHA-1 사용 중지 및 SHA-2 사용을 발표했다.^[38]

2008년 미국 국립표준기술연구소(NIST)는 SHA-3라는 새로운 안전한 암호화 해시 함수 공모전을 개최했다. 2012년 8월에는 5개의 최종 후보가 선정되었으며, 2012년 중 최종 후보가 결정될 예정이었다.^[39]

SHA-0과 RIPEMD는 이미 더 강화된 버전으로 대체되어 사용되지 않고 있다. 2004년 8월에는 당시 자주 사용되던 해시 함수(SHA-0, RIPEMD, MD5 등)의 약점이 발견되어, 이들로부터 파생된 알고리즘, 특히 SHA-1(SHA-0의 강화 버전)과 RIPEMD-128 및 RIPEMD-160(RIPEMD의 강화 버전)의 장기적인 보안에 의문이 제기되었다.

2009년 현재 가장 널리 사용된 암호화 해시 함수는 MD5와 SHA-1이었으나, MD5는 이미 깨졌고, 2008년에는 SSL에 대한 공격에 그 취약성이 이용되었다.^[27]

SHA-1은 미국 국가 안보국(NSA)가 개발한 SHA 패밀리에 속한다. 2005년 2월에는 SHA-1에 대해 2⁸⁰회보다 적은 2⁶⁹회의 해시 생성으로 충돌을 찾는 공격법이 보고되었고, 8월에는 2⁶³회로 충돌을 찾는 공격법이 보고되었다. SHA-1에는 이론적인 약점도 지적되고 있으며^[28][29], 수년 안에 해독될 것이라는 예측도 있었다. 2009년 6월에는 2⁵²회로 SHA-1에서 충돌을 찾을 수 있는 공격법이 보고되었다.^[30] 최근에는 SHA-2와 같은 더 새로운 SHA 패밀리로 이전하거나, 충돌 저항성이 필요하지 않은 무작위 해시^[31][32] 등의 기법을 사용하여 문제를 회피하고 있다.

해시 함수의 장기적인 안정성 보장을 위해 SHA-2의 후속으로 SHA-3 공모가 이루어졌고^[33], 2015년에 FIPS 규격으로 발행되었다.

다음은 널리 알려진 암호화 해시 함수 알고리즘의 목록과 공격 가능성에 대한 표이다.

6. 1. 충돌 공격

6. 2. 원상 공격

6. 3. 제2 원상 공격

6. 4. 길이 확장 공격

6. 5. 암호화 해시 알고리즘에 대한 공격

SHA-0과 RIPEMD는 이미 더 강화된 버전으로 대체되어 사용되지 않고 있다. 2004년 8월에는 당시 자주 사용되던 해시 함수(SHA-0, RIPEMD, MD5 등)의 약점이 발견되어, 이들로부터 파생된 알고리즘, 특히 SHA-1(SHA-0의 강화 버전)과 RIPEMD-128 및 RIPEMD-160(RIPEMD의 강화 버전)의 장기적인 보안에 의문이 제기되었다.

2009년 현재 가장 널리 사용된 암호화 해시 함수는 MD5와 SHA-1이었으나, MD5는 이미 깨졌고, 2008년에는 SSL에 대한 공격에 그 취약성이 이용되었다.^[27]

SHA-1은 미국 국가 안보국(NSA)가 개발한 SHA 패밀리에 속한다. 2005년 2월에는 SHA-1에 대해 2⁸⁰회보다 적은 2⁶⁹회의 해시 생성으로 충돌을 찾는 공격법이 보고되었고, 8월에는 2⁶³회로 충돌을 찾는 공격법이 보고되었다. SHA-1에는 이론적인 약점도 지적되고 있으며^[28][29], 수년 안에 해독될 것이라는 예측도 있었다. 2009년 6월에는 2⁵²회로 SHA-1에서 충돌을 찾을 수 있는 공격법이 보고되었다.^[30] 최근에는 SHA-2와 같은 더 새로운 SHA 패밀리로 이전하거나, 충돌 저항성이 필요하지 않은 무작위 해시^[31][32] 등의 기법을 사용하여 문제를 회피하고 있다.

해시 함수의 장기적인 안정성 보장을 위해 SHA-2의 후속으로 SHA-3 공모가 이루어졌고^[33], 2015년에 FIPS 규격으로 발행되었다.

6. 6. 해시된 비밀번호에 대한 공격

참조

_[1] 웹사이트 Cryptanalysis of MD5 and SHA: Time for a New Standard https://www.schneier[...] 2016-04-20
_[2] 웹사이트 Flickr's API Signature Forgery Vulnerability http://vnhacker.blog[...] 2012-12-07
_[3] 간행물 Use MD5 hashes to verify software downloads http://www.techrepub[...] 2007-12-05
_[4] 논문 Design Principles for Iterated Hash Functions https://eprint.iacr.[...] 2004
_[5] 간행물 A Framework for Iterative Hash Functions – HAIFA https://eprint.iacr.[...] 2006-08-24
_[6] 보고서 Security Evaluation of SHA-224, SHA-512/224, and SHA-512/256 http://www.cryptrec.[...] 2015-02
_[7] 웹사이트 More Problems with Hash Functions http://article.gmane[...] 2016-05-25
_[8] 웹사이트 Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition https://nvlpubs.nist[...] 2018-06-05
_[9] 웹사이트 Collisions for Hash Functions MD4, MD5, HAVAL-128, and RIPEMD https://eprint.iacr.[...] 2004-12-20
_[10] 서적 Cryptographic Hash Function IGI Global 2015
_[11] 웹사이트 Finding Collisions in the Full SHA-1 http://people.csail.[...] 2017-07-15
_[12] 웹사이트 Cryptanalysis of SHA-1 http://www.schneier.[...] 2005-02-18
_[13] 뉴스 Google Just 'Shattered' An Old Crypto Algorithm – Here's Why That's Big For Web Security https://www.forbes.c[...] 2017-02-24
_[14] 웹사이트 Randomized Hashing and Digital Signatures http://webee.technio[...]
_[15] 웹사이트 MD5 considered harmful today: Creating a rogue CA certificate http://www.win.tue.n[...] Department of Mathematics and Computer Science of Eindhoven University of Technology 2009-03-29
_[16] 뉴스 The 15 biggest data breaches of the 21st century https://www.csoonlin[...] CSO Magazine 2020-11-25
_[17] 웹사이트 25-GPU cluster cracks every standard Windows password in <6 hours https://arstechnica.[...] Ars Technica 2020-11-23
_[18] 웹사이트 Use an 8-char Windows NTLM password? Don't. Every single one can be cracked in under 2.5hrs https://www.theregis[...] 2020-11-26
_[19] 웹사이트 Mind-blowing development in GPU performance https://improsec.com[...] Improsec 2020-01-03
_[20] 서적 SP 800-63B-3 – Digital Identity Guidelines, Authentication and Lifecycle Management NIST 2017-06
_[21] 문서 0, 1, 00, 01, 10, 11, ... のようにして、1ビットずつメッセージの長さを伸ばしながら辞書順で探索するなどすればよい。強衝突耐性については探索に必要な時間に上界があることが[[鳩の巣原理]]によって言えるが、原像計算困難性については言えない。
_[22] 문서 ''h'' が誕生日に相当する。誕生日のパラドックスにあっても、重複する誕生日は任意に選んで構わない。
_[23] 문서 証明は自明である。連結されたハッシュ関数での衝突を探すアルゴリズムは、明らかに個々の関数での衝突も見つけることができる。
_[24] 문서 さらに一般には、1つのハッシュ関数の「内部状態」での衝突を見つけられれば、全体への攻撃は単に個々の関数への[[誕生日攻撃]]と同程度の難しさでしかない。
_[25] PDF 全文 https://link.springe[...] LNCS 2004
_[26] Wayback More problems with hash functions http://article.gmane[...] 20160409095104
_[27] 웹사이트 MD5 considered harmful today: Creating a rogue CA certificate http://www.win.tue.n[...] 2009-03-29
_[28] 웹사이트 Finding Collisions in the Full SHA-1 http://people.csail.[...] 2023-09-02
_[29] 웹사이트 Cryptanalysis of SHA-1 http://www.schneier.[...] 2023-09-02
_[30] 웹사이트 Differential Path for SHA-1 with complexity O(2⁵²) https://eprint.iacr.[...]
_[31] Wayback Update on Randomized Hashing http://csrc.nist.gov[...] 20080917181920
_[32] Wayback Randomized Hashing and Digital Signatures http://www.ee.techni[...] 20061114153938
_[33] Wayback CRYPTOGRAPHIC HASH ALGORITHM COMPETITION] NIST.gov - Computer Security Division - Computer Security Resource Center http://csrc.nist.gov[...] 20170910142727
_[34] 논문 New message difference for MD4 http://www.iacr.org/[...]
_[35] Wayback Cryptographic Algorithms and Protocols for Network Security http://www.nis-summe[...] 20090319174448
_[36] 서적 Handbook of Applied Cryptography
_[37] 웹인용 Vulnerability Note VU#836068: MD5 vulnerable to collision attacks http://www.kb.cert.o[...]
_[38] 간행물 NIST Brief Comments on Recent Cryptanalytic Attacks on Secure Hashing Functions and the Continued Security Provided by SHA-1 https://web.archive.[...] 2012-08-11
_[39] 웹인용 Tentative Timeline of the Development of New Hash Functions http://csrc.nist.gov[...] 2012-08-12
_[40] 문서 Merkle-Damgård 방식에서 각 라운드 시 생성되는 내부 해시의 크기.
_[41] 문서 라운드 수가 표시되지 않은 경우 전체 라운드에 대한 공격을 의미한다.