* 해쉬함수
- 데이터를 작은 크기의 데이터로 제가공하는 것
- 암호해쉬함수 : 해쉬함수에 보안적 특성을 추가한 것
- 암호해쉬 함수의 특징/성질
ⓐ 압축(Compression) : 메세지의 길이는 입력 메세지의 길이보다 작다.
ⓑ 효율성(Efficiency) : 어떠한 메세지라도 쉽게 해쉬값을 계산해야 한다.
ⓒ 단방향(One-way) : 해쉬값이 주어졌을 때, 이를 이용해 본래의 값을 찾는 것은 불가능(일정 시간내에 불가능)해야한다.
- 긴 문장을 짧게 고친 만큼 해쉬함수에서는 충돌이 발생하게 된다. 이 충돌은 해쉬함수의 안전성과 연관이 깊다.
~ 공격자가 같은 해쉬값을 출력해주는 2개의 문장을 안다면, 바꿔치기 공격이 가능하다.
- 충돌 방지 법에는 2가지 종류로 나눠서 생각한다.
ⓐ 약한 충돌방지
~ 특정 메세지(M)과 이 메세지를 해쉬한 결과값(H(M))이 주어졌다.
~ 이 경우 메세지(M) 이외에 H(M)값을 갖는 또다른 메세지 N을 구하는 것이 힘들어야 한다.
ⓑ 강한 충돌방지
~ 특정 해쉬값을 보고, 2가지 이상의 본래의 문장을 찾아내기는 힘들어야 한다.
* 생일문제
- 한 방에 있는 사람들 중에 2명 또는 그 이상이 같은 생일일 확률이 50%보다 크기 위해서는 얼마나 사람이 있어야 하는가?
> 1 - {모두다 생일이 다른 확률} = 1 - 365/365*364/365*...*(365-N+1)/365 >= 1/2
> n = 23이 된다. 즉, 23명만 있어도 2명 또는 그 이상이 같은 생일을 같을 수 있다는 것이다.
> 이는, 365의 제곱근에 근사값을 보인다.
- 이 결과는 해쉬에서 충돌이 일어날 확률에 적용 시킬 수 있다.
> 해쉬된 결과값이 N비트라면 서로다른 2^N개의 해쉬 값을 생성할 수 있다.
> 이는 2^(N/2)개의 랜덤값들을 해쉬하면 충돌이 발생한다는 의미이다.
> 안전한 N비트의 대칭키를 깨기 위해서는 2^(N-1)번이 필요한 반면,
안전한 N비트의 해쉬를 깨기 위해서는 2^(N/2)번의 작업이 필요. 이는 해쉬를 사용할 경우 고려해야할 값(해쉬 길이)이다.
* 비암호 해쉬
ⓐ 데이터 X : (X0,X1,X2,...,Xn-1), hash(X) = X0+X1+X2+...+Xn-1 mod 256
- 이 결과는 안전하지 않다.쉽게 충돌을 발견할 수 있다.(데이터 Xn의 순서만 바꺼도 충돌이 발생)
ⓑ 데이터 X : (X0,X1,X2,...,Xn-1), hash(X) = nX0+(n-1)X1+(n-2)X2 + .. + 1Xn-1 mod 256
- 이 해쉬는 적어도 ⓐ번처럼 단순히 순서만 바꾼다고 충돌이 발생하지는 않는다.
- 비록, 안전하지는 않지만 비암호 응용분야에서는 ⓑ번의 해쉬를 많이 사용한다.
ⓒ 중복검사
- 에러검출 또는 정정을 위해서 압축된 메세지(해쉬 메세지)를 같이 보내기도 한다.
- ex) parity check, check sum, CRC(순환 중복 검사)
- 이는, 데이터가 에러가 있는지를 발견할 수는 있지만, 100% 찾아내지는 못한다.
* 암호해쉬(Crypto hash) 설계
ⓐ 충돌방지 : 입력값의 변화는 출력값과는 상관 없게 만들어야 한다. 충돌을 최대한 방지할 수 있다면 해쉬 함수는 안전하다.
ⓑ 눈사태 효과 : 입력값이 1비트라도 차이가 날때, 출력값은 반 이상 다른 값이 나와야 한다.
- 이는 반복적인 행동이 없어도 나타나는 것이 바람직하다.
ⓒ 효율성 : 암호를 목적으로 하기 때문에 시간의 효율성은 중요하다.
ⓓ 암호 해쉬는 블럭암호화와 비슷하게 여러번 반복적인 행동을 한다.
- 해쉬 함수의 예: MD5, SHA-1
* HMAC
- MAC : 메세지 무결성을 위해서 사용
- message과 H(message)값을 동시에 전송할 수 없다.
> 공격자가 message'과 H(message')을 생성하여 바꿔치기가 가능하다.
- HMAC : Hash시 송신자와 수신자만 아는 값(shared key)값을 넣어 같이 hash를 한다.
- 표현 : MD = H(S||M) , 전송 값 : M || MD
- shared key값의 위치 : M||S 인가 S||M인가?
> 두 가지 모두 잠재적인 문제를 갖고 있다.
> 실사용 : HMAC(M,K) = H(K xor opad, H(k xor ipad, M)) // 참고로만 알아 둘것
- HMAC의 역할
> 무결성, 송신자 인증을 가능하게 한다.
* 전자서명
- 전자서명은 무결성과 부인방지, 송신자 인증 역할을 한다고 앞에서 설명하였다.
- But, 메세지 전체에 서명하기에 시간이 오래 걸리게 된다.
- Message digest를 사용한다. Message digest는 메세지의 축소형으로 H(M)값을 의미한다.
* 해쉬의 응용
1) 인증
2) 메세지 무결성
3) 효율적인 전자서명
4) 메세지 지문
5) 데이터 회손 발견
eg1) 온라인 경매
- 경매에서는 다른사람이 제출한 입찰가를 비밀로 지키길 원한다.
- 입찰가를 Hash한 값을 보낸다.(One way) 한번 제출된 입찰가는 변경이 불가능하다.
- 경매 종료후 입찰가를 보낸다. 경매 진행자는 받은 입찰가를 Hash하여 무결성 판단을 실시한다.
eg2) 스팸 감소(Spam reduction)
- 메세지를 보낼때 메세지를 생성하는 cost를 증가시킨다.
- H(M,R,T)
> T는 현재 시간이며, R을 찾는 과정에 수고를 필요하게 한다.
- R값을 찾는 기준 : H(M,R,T)결과에서 앞의 N bits가 0이 되게 하는 R 값
- 받는 사람은 H(M,R,T)에서 N bits가 0이 아니면 버리게 된다.
eg3) 온라인 동전 던지기 문제
- 이 게임은 다음의 단계를 다르며 진행된다.
Step 1. Alice choose X, X = 1 or 0
Step 2. Alice sends Y to bob.
Y = E(X,R,K)
> R : random value, K : 대칭키
Step 3. Bob choose Z, Z = 1 or 0
Step 4. Bob sends Z to Alice.
Step 5. Alice sends R and K to bob.
Step 6. Check the result
- 이 게임은 Step 2에서 Alice가 사기를 칠 수 있게 해준다.
Alice는 각각 X값(0과 1)에 대해서 같은 Y값을 생성하는 Key값을 2개 생성한다.
Y = E(0,R,K0) = E(1,R,K1)
Step 4에서 Bob이 보낸 값을 보고, 5단계에서 보낼 key를 바꿔가며 보낸다.
- 이를 방지하기 위해 Step 2에서 Y값과 hash(key)값을 같이 보낸다.