[Crypto Hacking] 해시함수와 Hash Collision Attack

해시함수란?

임의의 사이즈를 가진 데이터를 고정된 사이즈로 매핑하는 함수를 의미합니다.

One-way Hash : hash(m)=h 일때, h를 보고 m을 찾기 힘든 구조

 

 

해시함수의 성질

1. 제1역상저항성 : 해시값 h(x)을 알고있어도 원래의 입력값 x를 계산하기 어렵습니다
2. 제2역상저항성 : 해시값 h(x)가 주어졌을때 이와 동일한 해시값을 가지는 y를 찾기는 어렵습니다.
3. 충돌저항성 : 다른 입력 두개가 같은 해시값을 가지기는 어렵다는 성질입니다.

 

해시함수의 작동 과정

IV는 Initial Vector를 의미하며 M1~M4는 일정 비트 단위마다 메세지를 쪼갠 것을 말합니다.

해시를 위해서는 메세지가 일정 단위로 나누어 떨어져야 하므로 Padding을 추가할 수도 있습니다.

이러한 방식을 Merkle–Damgård construction 이라고 합니다. ****

https://en.wikipedia.org/wiki/Merkle–Damgård_construction

 

 

해시함수 적용 예시

1. 무결성 검증 : 파일 전송시 해시값을 같이 전달합니다. 이후 수신자가 파일로부터 해시값을 계산해서 전송 받은 해시와 같은지 비교하면서 무결성을 검증합니다.
2. 비밀을 공개하지 않으면서 커밋 : 해시함수의 성질을 이용한 방식으로, 해시 값만 미리 공개하고 나중에 원본 정보와 비교하는 형식입니다. 주식 시장 등에서 사용될 수 있습니다.
3. 비밀번호 검증 : 비밀번호는 아무도 알 수 없게 평문으로 저장하면 안되고 동시에 로그인시 비밀번호가 맞는지 비교할 수 있어야합니다. 이를 위해 One-Way Hash를 이용해 해시값으로 비교 Password Field는 아래와 같이 구성되어 있습니다. Password Field=algorithm+salt+password hash password hash = OneWayHashRound( password || salt ) salt : 같은 input이라도 다른 output을 만들어주는 역할을 한다. → salt, password 해시를 통해 미리 준비된 Dictionary, Rainbow Table 공격 등을 무효화 할 수 있습니다.
4. 타임스탬핑 : 문서가 특정 날짜 이전에 존재했음을 증명하기 위해 해시함수를 사용하는 경우입니다. 신문이나 잡지 등에 해시값을 게시하거나 TSA(타임스탬핑기관)을 통한 방법이 있습니다.

Hash Collision Attacks

암호학적 해시 함수를 공격하는 방식으로 해시 충돌이 일어나는 두 입력값을 찾는 방식이다

대표적으로 두가지 방식이 있다

• Classical Collision Attack : h(x)=h(y)인 x,y를 찾는 것입니다. 해당 공격으로 해시함수의 한 종류인 MD5, SHA-1 Collision-resistance(충돌저항성) 특성이 깨졌습니다.
• Chosen-prefix Collision Attack : 두개의 다른 메세지 m1,m2가 있을때 h(m1||x)=h(m2||y)인 x,y를 찾는 것입니다. 즉, 서로 다른 계산값을 뒤에 추가하면서 동일한 해시값을 갖게 만들도록 하는 방식입니다.

MD5

1991년 설계된 해시 알고리즘으로 128비트의 해시값을 출력합니다.

MD5는 충돌 저항성이 깨진 알고리즘으로 2004년 처음 그 충돌쌍이 발견되었습니다.

M1:
d131dd02c5e6eec4693d9a0698aff95c2fcab58 712467eab4004583eb8fb7f89
55ad340609f4b30283e48883257 1415a085125e8f7cdc99fd91dbdf 280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b 487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a 80d1ec69821bcb6a8839396f9652 b6ff72a70

M2:
d131dd02c5e6eec4693d9a0698aff95c2fcab5 0 712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325 f 1415a085125e8f7cdc99fd91dbd 7 280373c5b 
d8823e3156348f5bae6dacd436c919c6dd53e2 3 487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080 2 80d1ec69821bcb6a8839396f965 a b6ff72a70 

Hash: 79054025255fb1a26e4bc422aef54eb4

2008년에는 파일의 몇 비트만 달랐던 이전 공격 방법과는 달리 Chosen-Prefix 방식을 이용해서 완전히 다른 두 파일이 동일한 MD5 해시를 가질 수 있게 하는게 가능해졌습니다.

https://www.mscs.dal.ca/~selinger/md5collision/

이후 고속으로 collision attack이 가능해지게 되면서 현재는 MD5알고리즘을 보안 관련 용도로 권장하고 있지 않습니다.

 

 

SHA-1

임의의 길이의 입력을 160비트의 해시값을 생성하는 함수로, 이 알고리즘 역시 충돌 공격이 가능합니다.

2005년 중국 대학의 한 연구팀이 sha-1의 충돌 공격 가능성을 처음 제기하였습니다.

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=abc63b4e03c548830092b056a317bd7ac51e5a47

이후 구글이 sha1의 취약점을 입증하면서 여러 브라우저는 sha-1 인증서 사용을 철회하게 되었습니다. 

현재는 sha-1을 보안 용도로 사용하는 것을 권고하고 있지 않으며 2030년 12월 31일 부로 sha-1을 보안 해시 표준에서 삭제할 것이라는게 NIST의 입장입니다.

 

 

Hash Collision Attack으로 인한 위험 예시

공개키 인증서 위조 : 사이트 A, B가 동일 해시값을 가지고있다고 하자. 인증자가 A 해시에 사인을 한 경우 hash collsion이 되었기 때문에 B도 인증을 받는다. 따라서 공격자는 위조된 인증서를 획득 가능합니다.

프로그램 무결성 위조 : 공격자가 합법적인 소프트웨어에 고의로 충돌 공격을 해 악성 프로그램 생성할 수도 있습니다.

이외에도 해시함수의 안전성을 위협하는 방식에는 여러가지가 있습니다

생일 공격(Birthday Attack) : 생일 문제의 확률적 결과를 기반으로 한 것으로, 무차별 대입 공격보다 해시 충돌을 찾아낼 확률을 크게 만들 수 있습니다.

https://en.wikipedia.org/wiki/Birthday_attack

무차별 대입 공격 (BruteForce Attack) : 모든 값을 대입하는 방식으로, 충분한 시간이 존재할 때 사용할 수 있는 방식입니다. 일반적으로 어떤 암호가 깨졌다고 하면 무차별 대입 공격 방식보다 효율적인 방식이 있을 때를 의미하게 됩니다.

레인보우 테이블 (Rainbow Table) : 해시함수를 이용해서 변환 가능한 해시 값들을 표로 만들어 둔 것입니다.