[crypto] Hash

1. Hash의 정의

 

Hash : 단방향 암호화 기법이다. 해시 알고리즘은 SHA-256, SHA-512를 사용한다. 또 해시 알고리즘은 특정 입력에 대해 항상 같은 해시 값을 return 한다.

 

* pigeonhole principle(비둘기 집의 원리) :n+1 마리 이상의 비둘기를 n개의 집에 넣으려고 할 때, 적어도 하나의 집에는 두 마리 이상의 비둘기가 들어가게 된다. 이를 Hash Crypto에 적용해 보면,
M -> h(M) = h(M’)  <- M’ (같은 해시값에 다른 값을 가리킬 수있음 , Hash의 맹점, Collision) , 해시는 원본 메시지가 담고 있는 정보에 손실을 가져온다. 

 

Hash 가 보장 되기 위해서는

1) Compression 보장

2) Efficiency 보장

3) One – way 보장

4) Weak collision resistance 보장 : 공격 난이도 어렵고, 방어가 쉽다

5) Strong collision resistance 보장 : 공격 난이도 쉽고 , 방어가 어렵다

 

해시함수는 attacker가 brute-force 방식으로 비밀번호를 알아낼 수 있기 때문에 비밀번호에 salt값을

넣거나 해시 함수를 여러번 돌리는 방식으로 attack을 방지 할 수 있다.

 

* Salt

Hash password와 함꼐 사용한다. (y = h(password,salt))

password 파일에 함께 저장 되고 salt는 secret 하지 않다. Hash 값은 salt로 인해 Randomness를 추가 됨.

 

 

2. Hash의 허점을 이용한 attack 및 AccessControl

* Brute-Force - Attack(무차별 대입 공격)

* Birthday problem와  Hash

Birthday Problem : k명 중에 2명 이상이 같은 생일을 가질 확률을 뜻한다.

한 집단에 23명 이상의 사람이 모이면 그 중 생일이 같은 사람이 적어도 한 쌍 이상 있을 확률이 50%를 넘어간다..

이것을 이용해 충분히 큰 숫자 M과 (Mi , Mj)의 쌍이 해시값이 충돌할 확률을 가지고 해시 충돌을 일으키는 것이 생일 공격이다.  따라서 Collision을 막으려면 암호키의 길이보다 hash size는 2배가 되어야 한다.

 

ex) 64bit Hash code가 있을 때 -> 2^32번 계산을 하면 중복되는 해시값이 50%가 넘는다 .

-> 중복되는 Hash 값을 통해 birthday attack 가 발생함

 

 

*Dictionary Attack

원문에 대해 미리 계산된 해시값들을 모아서 사전 형태로 만들고 대입해보는 공격방법. 공격자는 hash password에 대한 password 파일을 가지고 있다고 가정한다. Dictionary - Attack을 방지하기 위해서는 인명, 전화번호 같은 character가 드러나는 정보로 비밀번호를 만들지 말아야 한다. 그리고 최대한 암호문을 유추해내지 못하게 길게 , 복잡하게 만드는 것도 하나의 방법이 될 수 있다.

* Rainbow Table Attack

 

 

brute-force attack과 dictionary attack을 합친듯한 공격 기법이다. 무한적으로 대입을 하는 것보다 미리 만들어진 해시 테이블에서 해시 값만 추출하여 해시 계산하는 시간이 절약되어서 brute-force attack 보다 빠르다. rainbow-table attack은 해시 함수를 사용하여 만들어 낼 수 있는 값들을 대량으로 저장한 표이다.  해시 함수를 통한 패스워드 크래킹이 가능하지만 테이블 생성에 많은 시간이 소요된다는 단점이 있다.