해시 함수 (Hash Function)#
임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
특징:
일방향성: 해시 값으로부터 원본 데이터를 복구하는 것이 계산상 불가능하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
| def demonstrate_one_way():
"""해시 함수의 일방향성을 보여주는 함수"""
class PasswordManager:
def __init__(self):
self.password_hash = None
def set_password(self, password):
# 비밀번호는 해시값으로만 저장
self.password_hash = create_hash(password)
def verify_password(self, password):
# 입력된 비밀번호의 해시값과 저장된 해시값 비교
return create_hash(password) == self.password_hash
|
결정성: 같은 입력에 대해 항상 같은 해시 값을 생성한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
| def demonstrate_deterministic():
"""해시 함수의 결정성을 보여주는 함수"""
message = "Hello, World!"
# 같은 메시지로 여러 번 해시 생성
hash1 = create_hash(message)
hash2 = create_hash(message)
hash3 = create_hash(message)
# 모든 해시값이 동일함을 확인
print(f"Hash 1: {hash1}")
print(f"Hash 2: {hash2}")
print(f"Hash 3: {hash3}")
|
고정 길이 출력: 입력 데이터의 크기와 관계없이 항상 고정된 길이의 해시 값을 생성한다.
눈사태 효과: 입력 데이터가 조금만 변경되어도 해시 값이 크게 변화한다.
1
2
3
4
5
6
7
8
9
10
11
| def demonstrate_avalanche():
"""해시 함수의 눈사태 효과를 보여주는 함수"""
message1 = "Hello, World!"
message2 = "Hello, World" # 느낌표 하나만 제거
hash1 = create_hash(message1)
hash2 = create_hash(message2)
print(f"메시지 1 해시: {hash1}")
print(f"메시지 2 해시: {hash2}")
print(f"변경된 비트 수: {count_different_bits(hash1, hash2)}")
|
구현 예시:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| import hashlib
def create_hash(data):
"""
데이터로부터 SHA-256 해시를 생성합니다.
입력: 문자열 데이터
출력: 16진수 형태의 해시값
"""
# 문자열을 바이트로 변환하고 해시 생성
hasher = hashlib.sha256()
hasher.update(data.encode())
return hasher.hexdigest()
# 사용 예시
message = "Hello, World!"
hash_value = create_hash(message)
print(f"원본 메시지: {message}")
print(f"해시값: {hash_value}")
|
해시 충돌과 해결 방법#
해시 충돌은 서로 다른 입력 값이 같은 해시 값을 생성하는 현상
해결하기 위한 방법#
체이닝#
충돌이 발생한 데이터를 연결 리스트로 저장한다.
장점:
- 테이블이 가득 차도 계속 항목을 추가할 수 있음
- 클러스터링 문제가 없음
단점:
- 추가 메모리가 필요함
- 연결 리스트 탐색에 시간이 걸릴 수 있음
구현 예시:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class HashNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class HashTableChaining:
def __init__(self, size=10):
self.size = size
# 각 버킷에 None을 초기값으로 설정
self.table = [None] * size
def _hash_function(self, key):
"""
간단한 해시 함수
문자열의 각 문자 ASCII 값의 합을 테이블 크기로 나눈 나머지
"""
if isinstance(key, str):
total = sum(ord(c) for c in key)
else:
total = key
return total % self.size
def insert(self, key, value):
"""항목 삽입"""
# 해시값 계산
index = self._hash_function(key)
# 새로운 노드 생성
new_node = HashNode(key, value)
# 버킷이 비어있는 경우
if self.table[index] is None:
self.table[index] = new_node
return
# 충돌이 발생한 경우 - 연결 리스트의 끝에 새 노드 추가
current = self.table[index]
while current.next:
# 키가 이미 존재하면 값 업데이트
if current.key == key:
current.value = value
return
current = current.next
current.next = new_node
def get(self, key):
"""항목 검색"""
index = self._hash_function(key)
current = self.table[index]
# 연결 리스트를 순회하며 키를 찾음
while current:
if current.key == key:
return current.value
current = current.next
raise KeyError(f"Key '{key}' not found")
|
개방 주소법#
다른 빈 공간을 찾아 데이터를 저장한다.
장점:
단점:
- 테이블이 가득 차면 더 이상 항목을 추가할 수 없음
- 클러스터링 현상이 발생할 수 있음
구현 예시:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| class HashTableOpenAddressing:
def __init__(self, size=10):
self.size = size
self.table = [None] * size
self.keys = [None] * size # 키 저장을 위한 별도 배열
def _hash_function(self, key):
"""기본 해시 함수"""
if isinstance(key, str):
total = sum(ord(c) for c in key)
else:
total = key
return total % self.size
def _probe(self, index):
"""
선형 탐사
다음 가능한 위치를 찾아 반환
"""
return (index + 1) % self.size
def insert(self, key, value):
"""항목 삽입"""
index = self._hash_function(key)
original_index = index
while self.table[index] is not None:
# 키가 이미 존재하면 값 업데이트
if self.keys[index] == key:
self.table[index] = value
return
# 다음 위치 탐사
index = self._probe(index)
# 테이블이 가득 찬 경우
if index == original_index:
raise Exception("Hash table is full")
# 빈 공간에 저장
self.keys[index] = key
self.table[index] = value
def get(self, key):
"""항목 검색"""
index = self._hash_function(key)
original_index = index
while self.table[index] is not None:
if self.keys[index] == key:
return self.table[index]
index = self._probe(index)
# 전체 테이블을 순회했는데 못 찾은 경우
if index == original_index:
break
raise KeyError(f"Key '{key}' not found")
|
주요 용도#
데이터 무결성 검증: 파일이나 메시지의 변조 여부를 확인한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class FileIntegrityChecker:
def __init__(self):
self.file_hashes = {}
def calculate_file_hash(self, filepath):
"""파일의 해시값 계산"""
hasher = hashlib.sha256()
with open(filepath, 'rb') as f:
# 파일을 청크 단위로 읽어서 메모리 효율성 확보
for chunk in iter(lambda: f.read(4096), b''):
hasher.update(chunk)
return hasher.hexdigest()
def store_file_hash(self, filepath):
"""파일의 해시값 저장"""
self.file_hashes[filepath] = self.calculate_file_hash(filepath)
def verify_file_integrity(self, filepath):
"""파일의 무결성 검증"""
if filepath not in self.file_hashes:
return False
current_hash = self.calculate_file_hash(filepath)
return current_hash == self.file_hashes[filepath]
|
비밀번호 저장: 비밀번호를 해시 값으로 저장하여 보안을 강화한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class SecurePasswordStorage:
def __init__(self):
self.password_database = {}
def register_user(self, username, password):
"""
사용자 등록 - 비밀번호는 해시하여 저장
솔트를 추가하여 보안성 강화
"""
salt = os.urandom(16).hex()
password_hash = create_hash(password + salt)
self.password_database[username] = {
'hash': password_hash,
'salt': salt
}
def verify_password(self, username, password):
"""저장된 해시값과 비교하여 비밀번호 검증"""
if username not in self.password_database:
return False
user_data = self.password_database[username]
password_hash = create_hash(password + user_data['salt'])
return password_hash == user_data['hash']
|
데이터 구조: 해시 테이블에서 빠른 데이터 검색을 위해 사용된다.
디지털 서명: 메시지의 인증과 무결성을 보장하는 데 활용된다.
블록체인에서의 활용:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class SimpleBlock:
def __init__(self, data, previous_hash):
self.timestamp = time.time()
self.data = data
self.previous_hash = previous_hash
self.nonce = 0
self.hash = self.calculate_hash()
def calculate_hash(self):
"""블록의 해시값 계산"""
block_content = (
str(self.timestamp) +
str(self.data) +
str(self.previous_hash) +
str(self.nonce)
)
return create_hash(block_content)
def mine_block(self, difficulty):
"""작업증명(PoW) 구현"""
while self.hash[:difficulty] != '0' * difficulty:
self.nonce += 1
self.hash = self.calculate_hash()
|
해시 함수 사용 시 고려해야 할 보안 사항들#
적절한 해시 알고리즘 선택:
- MD5, SHA-1은 취약점이 발견되어 사용을 피해야 함
- SHA-256 이상의 안전한 알고리즘 사용 권장
솔트(Salt) 사용:
암호 저장 시 무작위 솔트를 추가하여 레인보우 테이블 공격 방지
키 스트레칭:
1
2
3
4
5
6
7
8
9
| def stretch_hash(password, iterations=100000):
"""
키 스트레칭을 통한 해시 강화
여러 번 해시를 수행하여 무차별 대입 공격을 어렵게 만듦
"""
result = password
for _ in range(iterations):
result = create_hash(result)
return result
|
솔트 (Salt)#
패스워드에 추가하는 랜덤한 값으로, 같은 패스워드라도 다른 해시값을 생성하게 만드는 기술
솔트를 사용하는 이유:
- 동일한 패스워드가 다른 해시값을 가지게 됨
- 레인보우 테이블 공격 방지
- 패스워드 크래킹의 어려움 증가
장점:
- 같은 패스워드도 다른 해시값을 가짐
- 사전 공격과 레인보우 테이블 공격 방지
- 패스워드 크래킹의 어려움 증가
구현 예시:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| import os
import hashlib
import base64
class PasswordWithSalt:
def __init__(self):
self.users = {} # 사용자 정보를 저장할 딕셔너리
def create_salt(self):
"""
안전한 랜덤 솔트 생성
32바이트(256비트)의 랜덤 값을 생성합니다
"""
return os.urandom(32)
def hash_password(self, password, salt):
"""
패스워드와 솔트를 결합하여 해시 생성
"""
# 패스워드(문자열)를 바이트로 변환하고 솔트와 결합
salted_password = password.encode() + salt
# SHA-256 해시 생성
hash_obj = hashlib.sha256(salted_password)
return hash_obj.digest()
def register_user(self, username, password):
"""
새로운 사용자 등록
각 사용자마다 고유한 솔트 사용
"""
salt = self.create_salt()
password_hash = self.hash_password(password, salt)
# 해시와 솔트를 함께 저장
self.users[username] = {
'hash': password_hash,
'salt': salt
}
# 저장된 값 출력 (16진수로 변환하여 보기 쉽게)
print(f"저장된 해시: {password_hash.hex()}")
print(f"사용된 솔트: {salt.hex()}")
def verify_password(self, username, password):
"""
패스워드 검증
저장된 솔트를 사용하여 해시를 재생성하고 비교
"""
if username not in self.users:
return False
stored_salt = self.users[username]['salt']
stored_hash = self.users[username]['hash']
# 입력된 패스워드를 저장된 솔트로 해시
verify_hash = self.hash_password(password, stored_salt)
return verify_hash == stored_hash
|
키 스트레칭 (Key Stretching)#
해시 함수를 여러 번 반복적으로 적용하여 패스워드의 보안성을 높이는 기술
장점:
- 해시 계산에 필요한 시간 증가
- 무차별 대입 공격의 효율성 감소
- 컴퓨터 성능 향상에 대응 가능
구현 예시:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| import time
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.pbkdf2 import PBKDF2HMAC
class KeyStretching:
def __init__(self):
self.users = {}
def stretch_password(self, password, salt, iterations=100000):
"""
PBKDF2를 사용한 키 스트레칭
iterations: 반복 횟수
"""
# PBKDF2 설정
kdf = PBKDF2HMAC(
algorithm=hashes.SHA256(),
length=32, # 출력 키의 길이 (bytes)
salt=salt,
iterations=iterations,
)
# 키 스트레칭 수행
key = kdf.derive(password.encode())
return key
def register_user(self, username, password, iterations=100000):
"""
사용자 등록 - 키 스트레칭 적용
"""
start_time = time.time()
salt = os.urandom(16)
stretched_key = self.stretch_password(password, salt, iterations)
end_time = time.time()
self.users[username] = {
'key': stretched_key,
'salt': salt,
'iterations': iterations
}
print(f"키 스트레칭 소요 시간: {end_time - start_time:f}초")
print(f"생성된 키: {stretched_key.hex()}")
|
솔트(Salt)와 키 스트레칭(Key Stretching)을 적용한 예시#
두 기술을 결합한 안전한 패스워드 관리 시스템
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class SecurePasswordManager:
def __init__(self):
self.users = {}
def secure_hash(self, password, salt=None, iterations=100000):
"""
솔트와 키 스트레칭을 모두 적용한 해시 생성
"""
if salt is None:
salt = os.urandom(32)
# PBKDF2로 키 스트레칭
kdf = PBKDF2HMAC(
algorithm=hashes.SHA256(),
length=32,
salt=salt,
iterations=iterations,
)
key = kdf.derive(password.encode())
return {
'key': key,
'salt': salt,
'iterations': iterations
}
def register_user(self, username, password):
"""
새로운 사용자 등록
"""
result = self.secure_hash(password)
self.users[username] = result
print("사용자 등록 완료:")
print(f"솔트: {result['salt'].hex()}")
print(f"스트레칭된 키: {result['key'].hex()}")
print(f"반복 횟수: {result['iterations']}")
def verify_password(self, username, password):
"""
패스워드 검증
"""
if username not in self.users:
return False
stored = self.users[username]
verify_result = self.secure_hash(
password,
stored['salt'],
stored['iterations']
)
return verify_result['key'] == stored['key']
|
참고 및 출처#