해시 함수 직접 만들기

세바님·2024년 4월 29일

해싱이란?

해싱은 수학적 알고리즘으로 데이터를 매핑하고 압축하는 기술을 말한다.

해싱의 보안 요구사항

속도: 계산이 용이하고 빨라야 함.
Deterministic: 동일한 입력에 여러 번 해시 함수를 적용해도 동일한 출력이 되야함.
Uniformity: 크기와 상관없이 데이터 전반에 걸쳐 동일한 양의 해싱 수행함.
Fixed-size: 출력은 고정 크기가 되도록 함.(너무 작으면 충돌)
not be reversible: 단방향 함수로 작용해야 함. 해시값으로부터 역으로 메시지를
알아낼 수 없다.(즉, 해시값으로 메시지를 찾기가 계산적으로 어려워야 한다.-역상
정항성)
Avalanche effect: 정보가 변경되면 단일 문자가 변경되더라고 크게 변함.
두 개의 메시지가 같은 해시값을 갖는 것을 충돌(collision)이라고 하는데 충돌이
발견되지 않도록 함.
최초 메시지가 확인된 상태에서 동일한 해시값이 나오는 다른 입력 메시지를 찾는
것이 불가능해야 함(제2역상저항성)., 같은 해시값을 생성하는 서로 다른 두 개의
입력 메시지 찾기가 어려워야한다.(충돌저항성)

이러한 요구사항을 충족시킬 수 있는 나만의 해싱 함수를 만들어보자.

으하하 실전돌입

그렇게 남은 수업시간동안 머리싸매면서 어떻게 만들어야 할지 고민을 해 보았다.

만들면서 생긴 고민

이러한 요구사항을 충족시키기 위해 생긴 고민은 다음과 같다.

해쉬값을 어떻게 구성할것인가
어떻게 64개의 문자로 표현할것인가
만약 변환했을때 256비트가 넘는다면 어떡할것인가
비슷한 문자열의 해쉬값을 어떻게 다르게 할것인가

먼저 1번은 받은 문자열을 아스키코드로 변환한 후 2진수로 포매팅 하는것으로 결정했다. (이것밖에 생각이 안남)
2~3번은 Fixed-size 조건을 만족하기 위해 16진수 64를 최대로 잡기로 결정한 후 생긴 고민이었다. 짧은 문자열이든 긴 문자열이든 해싱한 뒤 문자열의 길이를 고정적인 16진수 64로 해야하기 때문이다. 내가 내린 결론은 애초에 문자열을 한번에 해싱하지 말고 일정 길이의 문자열마다 해싱을 반복하는 것이다. 만약 빈 자리가 있다면 그부분은 길이가 256이 될때까지 0으로 채우는 방식을 선택했다.
4번은 not be reversible, Avalanche effect 조건을 만족하기 위해 생긴 고민이었다. 이를 만족하려면 특수한 값을 해싱할때 추가해줘야겠다고 생각했다. 나는 문자열의 첫 문자를 2진수 변환한 뒤 이를 뒤집은 값을 맨 뒤에 추가하였다. 사실 이 부분은 연속되는 값에 대해선 잘 될 것 같긴 하지만 다른 케이스에 대해서는 잘 작동할지 모르겠다.

1차 구현

위의 고민에 따라서 먼저 프로토타입을 만들었다.

def hash(string: str) -> str:
    hash_value: str = ""

    for char in string:
        hash_value += bin(ord(char))[2:]

    while len(hash_value) < 256 - len(bin(ord(string))[2:]):
        hash_value += "0"

    hash_value += bin(ord(string))[2:][::-1]

    hash_to_demical = int(f"0b{hash_value}", 2)

흠... 출력을 해 보면 문자열이 짧은 경우 생각보다 0이 너무 많았다. 그래서 문자열을 4등분하여 하기로 결정했다.

2차 구현

def hash(string: str) -> str:
    hash_value = ""

    for char in string:
        hash_value += bin(ord(char))[2:]

    if len(hash_value) > 256:
        half = round((len(hash_value) - 256) / 2)
        hash_value = hash_value[half : len(hash_value) - half]

    sliced_hash = [
        hash_value[i : i + round(len(hash_value) / 4)]
        for i in range(0, len(hash_value), round(len(hash_value) / 4))
    ]
    sliced_hash = sliced_hash[:4]

    for _ in range(10):
        for i in range(4):

            key = sliced_hash[i][:8:-1]

            while len(sliced_hash[i]) < 56:
                sliced_hash[i] += "0"

            sliced_hash[i] += key
            half = round((len(sliced_hash[i]) - 256) / 2)
            sliced_hash[i] = sliced_hash[i][:half]

            print(sliced_hash[i])

    hash_value = ""

    for quarter in sliced_hash:
        hash_value += quarter

    hash_to_demical = int(f"0b{hash_value}", 2)

    print("{0:x}".format(hash_to_demical))

이것저것 넣어보다 보니 코드가 엄청 길어졌다....
아무튼 실행을 해 보았다.

음... 뭔가 이상하긴 하지만 작동은 하는듯하다
그런데,, 문자열을 짧게 주면 에러가 난다.

콘솔을 찍어보니...? 빈칸으로 도배가 된것;;;;;

대차게 말아먹었다.

3차 구현

2차 구현한 코드를 잘 들여다 보니 그냥 내가 계산을 이상하게 해서 생긴 문제였다.

def hash(string: str) -> str:
    hash_value = ""

    for char in string:
        hash_value += bin(ord(char))[2:]

    if len(hash_value) > 256:
        half = round((len(hash_value) - 256) / 2)
        hash_value = hash_value[half : len(hash_value) - half]

    sliced_hash = [
        hash_value[i : i + round(len(hash_value) / 4)]
        for i in range(0, len(hash_value), round(len(hash_value) / 4))
    ]
    sliced_hash = sliced_hash[:4]

    for _ in range(10):
        for i in range(4):
            key = sliced_hash[i][:8:-1]

            while len(sliced_hash[i]) < 56:
                sliced_hash[i] += "0"

            sliced_hash[i] += key
            sliced_hash[i] = sliced_hash[i][:32]

            print(sliced_hash[i])

    hash_value = ""

    for quarter in sliced_hash:
        hash_value += quarter

    hash_to_demical = int(f"0b{hash_value}", 2)

    print("{0:x}".format(hash_to_demical))