해시

thsamajiki·2022년 10월 25일

알고리즘

목록 보기

3/8

1. 해시란

해시란 임의의 크기를 가진 데이터를 해시함수를 이용하여 고정된 길이의 비트열로 변환하는 것을 말한다.

해시를 만들기 위해선 해시 함수가 필요한데 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터를 출력하는 함수이다. 말 그대로 해시 함수는 해시를 만드는 함수이다. 이때 매핑 전 원래 데이터의 값을 키, 매핑 후 데이터의 값을 해시 값, 매핑하는 과정을 해싱, 해시 값 + 데이터 색인 주소를 해시 테이블이라고 한다.

2. 해시 함수의 특징

입력값이 일부만 변경되어도 전혀 다른 해시 값을 출력한다. [눈사태 효과]
입력값 상관없이 고정된 길이의 해시값을 출력한다.
복호화 불가능하다. [단방향 암호화 기법의 특징]
복잡하지 않은 알고리즘으로 구현되기 때문에 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모한다.
같은 입력값에 대해서는 같은 출력값을 보장한다.

2.1 해시 함수의 문제점

해시함수의 특징 중 자원소모가 적어 처리 속도가 빠르다고 했지만, 이건 장점이자 단점이다. 무차별 대입 공격을 받을 수 있기 때문이다.
레인보우 테이블 공격 (7번 확인)

2.2 해시 함수 문제점 해결

솔팅 : 패스워드에 임의의 문자열 salt를 추가하여 다이제스트 생성, 레인보우 테이블 공격을 무의미하게 한다. 솔트는 최소 128bit 정도 되어야 안전하다.
키 스트레칭 : 해시를 여러 번 반복하여 시간을 늘림으로써 Brute force attack에 대비한다.

3. 사용 목적

해시 함수의 가장 큰 특징은 입력값이 일부만 변경되어도 전혀 다른 값을 출력한다는 것이다. 이러한 특징으로 인하여 해시 함수를 사용하는 목적은 메시지의 오류나 변조를 탐지할 수 있는 무결성이다. 이 기술을 사용하는 대표적인 예로는 블록체인이 있다. 그 외에 비밀번호, 전자서명, 전자투표, 전자상거래 등에 사용된다.

4. 해시함수 알고리즘 종류

대표적인 해시 알고리즘의 종류로는 SHA(SHA-0, SHA-1, SHA-3, SHA-256, SHA-512, SHA-3), MD5 등이 있고, 그 외에도 많은 알고리즘이 있다.

4-1. SHA

처음 SHA-0으로 정의되어 발표되었지만 바로 위험성이 발견되어 이를 개선한 SHA-1이 발표되었고, 널리 사용되었다.
SHA-1 역시 충돌을 이용한 위험성이 발견되어 SHA-2가 발표되었다.
SHA-2는 해시 길이에 따라 SHA-224, SHA-256, SHA-384, SHA-512 비트를 선택해서 사용한다. 해시 길이가 길수록 더 안전하다.
- ( "ABC" 문자열을 SHA-512로 변환 397118FDAC8D83AD98813C50759C85B8C47565D8268BF10DA483153B747A74743A58A90E85AA9F705CE6984FFC128DB567489817E4092D050D8A1CC596DDC119 )
- ( "ABC" 문자열을 SHA-256으로 변환 B5D4045C3F466FA91FE2CC6ABE79232A1A57CDF104F7A26E716E0A1E2789DF78 )
2012년에는 안정성이 높은 SHA-3이 발표되었다.

4-2. MD5 (Message-Digest algorithm 5)

임의의 길이를 입력받아 128bit 길이의 해시 값을 출력한다.
단방향 알고리즘
현재는 심각한 보안 문제로 인하여 MD5를 보안 관련 용도로 사용하지 않는다.
2008년에는 MD5의 결함을 이용해 SSL 인증서를 변조하는 것이 발견되었다.

4-3. 레인보우 테이블

해시 함수(MD-5, SHA-1, SHA-2)를 사용하여 만들어낼 수 있는 값들을 대량으로 저장한 표이다.
MD5가 쉽게 복호화될 수 있다는 것을 보여준 해킹 방법 중 하나이다.

5. key에 따라 활용할 수 있는 해시 함수의 종류 및 예제 적용 코드

해시 테이블의 크기가 $m$ 이라면 좋은 해시 함수는 임의 키 값을 임의의 해시값에 매핑할 확률이 $\frac{1}{m}$ 이 될 것이다. 다시 말해 특정 값에 치우치지 않고 해시 값을 고르게 만들어내는 해시 함수가 좋은 해시함수라는 것이다.

5-1. Division method

나눗셈법은 간단하면서도 빠른 연산이 가능한 해시 함수이다. 숫자로 된 키를 해시 테이블 크기 $m$ 으로 나눈 나머지를 해시 값으로 반환한다. $m$ 은 대개 소수(prime number)를 쓰며 특히 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다. 다시 말해 해시 함수의 특성 때문에 해시 테이블의 크기가 정해진다는 단점이 있다.

// 저장
public void add(int key, int value) {       
    hashTable[divide(key)] = value;
}
    
// 나눗셈법
public int divide(int key) {
    return key % this.hashTable.length;
}

5-2. Multiplication method

숫자로 된 키가 $k$ 이고 A는 0과 1 사이의 실수일 때, 곱셈법은 다음과 같이 정의된다. $m$ 이 얼마가 되는 크게 중요하지는 않으며 보통 2의 제곱수로 결정한다. 나눗셈법보다는 다소 느리다. 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해시 함수이다.

h(k) = (kA\ mod\ 1) \times m

int multiply(double key){
		double d = (double)((int)key);
		return (int)((key - d) * this.hashTable.length);
}

5-3. Universal hashing

다수의 해시 함수를 만들고, 이 해시 함수의 집합 H 에서 무작위로 해시 함수를 선택해 해시값을 만드는 기법이다. H 에서 무작위로 뽑은 해시 함수가 주어졌을 때 임의의 키 값을 임의의 해시값에 매핑할 확률을 $\frac{1}{m}$ 으로 만드는 것이 목적이다. 다음과 같은 특정 조건의 해시 함수 집합 H 는 $\frac{1}{m}$ 으로 만드는 것이 가능하다.

해시 테이블의 크기 $m$ 을 소수로 정한다.
키 값을 다음과 같이 $r + 1$ 개로 쪼갠다: $k_0, k_1, ..., k_r$
$0$ 부터 $m - 1$ 사이의 정수 가운데 하나를 무작위로 뽑는다. 분리된 키 값의 개수( $r + 1$ )만큼 반복해서 뽑는다. 이를 $a = [a_0, a_1, ..., a_r]$ 로 둔다. 따라는 $a$ 의 경우의 수는 모두 $m^(r + 1)$ 가지 이다.
해시함수를 다음과 같이 정의한다. $ha(x) = Σri=0\ (a_ik_i\mod\ m)$
$a$ 가 $m^(r + 1)$ 가지 이므로 해시함수의 집합 H 의 요소 수 또한 $m^(r + 1)$ 이다.