[Python] PBKDF2-HMAC-SHA256

목차

0. 해시함수란

1. 단방향 해시함수를 패스워드 저장에 사용시 발생가능한 취약점

2. Adaptive key derivation function

3. PBKDF2

4. HMAC

5. Code

6. Reference

0. 해시함수란

해시함수란 입력받은 데이터를 일정한 길이의 출력으로 반환시키는 함수로 다음과 같은 조건을 따른다.

• 입력값의 길이가 달라도 출력값의 길이는 고정적이다.
• 동일한 값이 입력되면 언제나 동일한 출력을 보장한다.

1. 단방향 해시함수를 패스워드 저장에 사용시 발생가능한 취약점

단방향 = 복호화 불가능

• 1) 해시함수는 패스워드 저장을 위해 설계된 것이 아니라 데이터의 위변조 여부를 "빠르게" 판별하고 무결성을 검증하기 위해 설계되었다.
• 2) 다시 말해, 해시함수의 "빠른 처리속도"로 인해 공격자 또한 "빠른 속도로" 임의의 문자열 다이제스트와 해킹할 대상의 다이제스트를 비교할 수 있다.
• 3) 반면, 사용자는 웹 사이트에서 패스워드를 인증하는 데 걸리는 시간에 민감하지 않다.
• 4) 따라서, 잘 설계된 패스워드 저장 시스템에서는 하나의 다이제스트를 생성할 때 키 스트레칭을 통해 어느 정도(일반적으로 0.2초 이상)의 시간이 소요되도록 설정한다.
• 5) 이를 통해, 일반적인 장비로 1초에 50억개 이상의 다이제스트를 비교할 수 있던 것을 동일 장비에서 1초에 5번 정도만 비교할 수 있게 만들 수 있다.

2. Adaptive key derivation function

Adaptive key derivation function은 다이제스트를 생성할 때 솔팅과 키 스트레칭을 반복하여 공격자가 쉽게 다이제스트를 유추할 수 없도록 하고 보안의 강도를 설정할 수 있게 한다.

Salt : 패스워드에 추가하는 임의의 문자열로, 최소 128bits 정도는 되어야 안전하다.
솔팅된 다이제스트로는 해커가 패스워드 일치 여부를 알기 매우 어려우며, 사용자마다 다른 salt를 사용한다면 패스워드가 같더라도 다이제스트가 다르게 생성된다.

Key Stretching : 해시를 여러 번 반복하여 계산 시간을 충분히 늘려 Brute force attack에 대비할 수 있다.

3. PBKDF2

PBKDF2는 NIST(미국표준기술연구원)에 의해서 승인된 알고리즘으로, 미국 정부 시스템에서도 사용자 패스워드와 암호화된 다이제스트를 생성할 때 사용한다.
ISO-27001의 보안 규정을 준수하고, 서드파티의 라이브러리에 의존하지 않으면서 사용자 패스워드의 다이제스트를 생성하려면 PBKDF2-HMAC-SHA-256/SHA-512을 사용하면 된다.

DIGEST = PBKDF2(PRF, Password, Salt, c, DLen)

• PRF: 난수(예: HMAC)
• Password: 패스워드
• Salt: 암호학 솔트 (32비트 이상 추천)
• c: 원하는 iteration 반복 수 (1000회 이상 추천)
• DLen: 원하는 다이제스트 길이

def PRF(key, content): #PseudoRandomFunction
	pass
    
def pbkdf2(pwd, salt, iter):
    U = PRF(pwd, salt+b'\x00\x00\x00\x01')
    T = bytes(U) # copy
    for _ in range(1, iter):
        U = gethmac(pwd, U)
        T = bytes(a^b for a,b in zip(U,T))
    return T

4. HMAC (keyed-Hash Message Authentication Code)

HMAC의 목적은 암호화가 아닌, 무결성 검사에 있다.
송신자는 수신자와 공유하는 비밀키를 가지고 MAC을 계산하여 메세지와 함께 수신자에게 보낸다.
수신자는 마찬가지로 MAC을 계산하여 전달받은 MAC과 일치하는지 확인한다.
avalanche effect에 의해 통신 간에 해커가 메세지의 내용을 조금이라도 수정한 경우 MAC의 내용이 크게 달라진다.

Avalanche effect 예시
hello --> ac427d69ffff891d4aa07d9ddf56e465752b44ee2ba88c4fb02228ce519a7c4d
hello. --> 1325168ae33226d3b0c4d7d99744b86950ac0274f7bd5e29aa6fa8d90b52a050

def gethmac(key, content):
    okeypad = bytes(v ^ 0x5c for v in key.ljust(64, b'\0'))
    ikeypad = bytes(v ^ 0x36 for v in key.ljust(64, b'\0'))
    return sha256(okeypad + sha256(ikeypad + content))

4. Code

import hashlib

sha256 = lambda b: hashlib.sha256(b).digest()

def gethmac(key, content): # PRF
    okeypad = bytes(v ^ 0x5c for v in key.ljust(64, b'\0'))
    ikeypad = bytes(v ^ 0x36 for v in key.ljust(64, b'\0'))
    return sha256(okeypad + sha256(ikeypad + content))

def pbkdf2(pwd, salt, iter):
    U = gethmac(pwd, salt+b'\x00\x00\x00\x01')
    T = bytes(U) # copy
    for _ in range(1, iter):
        U = gethmac(pwd, U)
        T = bytes(a^b for a,b in zip(U,T))
    return T

pwd = b'password'
salt = b'salt'

print(pbkdf2(pwd, salt, 1).hex())

hashlib 라이브러리조차 사용하고 싶지 않다면...
https://github.com/keanemind/python-sha-256/blob/master/sha256.py

"""This Python module is an implementation of the SHA-256 algorithm.
From https://github.com/keanemind/Python-SHA-256"""

K = [
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
]

def generate_hash(message: bytearray) -> bytearray:
    """Return a SHA-256 hash from the message passed.
    The argument should be a bytes, bytearray, or
    string object."""

    if isinstance(message, str):
        message = bytearray(message, 'ascii')
    elif isinstance(message, bytes):
        message = bytearray(message)
    elif not isinstance(message, bytearray):
        raise TypeError

    # Padding
    length = len(message) * 8 # len(message) is number of BYTES!!!
    message.append(0x80)
    while (len(message) * 8 + 64) % 512 != 0:
        message.append(0x00)

    message += length.to_bytes(8, 'big') # pad to 8 bytes or 64 bits

    assert (len(message) * 8) % 512 == 0, "Padding did not complete properly!"

    # Parsing
    blocks = [] # contains 512-bit chunks of message
    for i in range(0, len(message), 64): # 64 bytes is 512 bits
        blocks.append(message[i:i+64])

    # Setting Initial Hash Value
    h0 = 0x6a09e667
    h1 = 0xbb67ae85
    h2 = 0x3c6ef372
    h3 = 0xa54ff53a
    h5 = 0x9b05688c
    h4 = 0x510e527f
    h6 = 0x1f83d9ab
    h7 = 0x5be0cd19

    # SHA-256 Hash Computation
    for message_block in blocks:
        # Prepare message schedule
        message_schedule = []
        for t in range(0, 64):
            if t <= 15:
                # adds the t'th 32 bit word of the block,
                # starting from leftmost word
                # 4 bytes at a time
                message_schedule.append(bytes(message_block[t*4:(t*4)+4]))
            else:
                term1 = _sigma1(int.from_bytes(message_schedule[t-2], 'big'))
                term2 = int.from_bytes(message_schedule[t-7], 'big')
                term3 = _sigma0(int.from_bytes(message_schedule[t-15], 'big'))
                term4 = int.from_bytes(message_schedule[t-16], 'big')

                # append a 4-byte byte object
                schedule = ((term1 + term2 + term3 + term4) % 2**32).to_bytes(4, 'big')
                message_schedule.append(schedule)

        assert len(message_schedule) == 64

        # Initialize working variables
        a = h0
        b = h1
        c = h2
        d = h3
        e = h4
        f = h5
        g = h6
        h = h7

        # Iterate for t=0 to 63
        for t in range(64):
            t1 = ((h + _capsigma1(e) + _ch(e, f, g) + K[t] +
                   int.from_bytes(message_schedule[t], 'big')) % 2**32)

            t2 = (_capsigma0(a) + _maj(a, b, c)) % 2**32

            h = g
            g = f
            f = e
            e = (d + t1) % 2**32
            d = c
            c = b
            b = a
            a = (t1 + t2) % 2**32

        # Compute intermediate hash value
        h0 = (h0 + a) % 2**32
        h1 = (h1 + b) % 2**32
        h2 = (h2 + c) % 2**32
        h3 = (h3 + d) % 2**32
        h4 = (h4 + e) % 2**32
        h5 = (h5 + f) % 2**32
        h6 = (h6 + g) % 2**32
        h7 = (h7 + h) % 2**32

    return ((h0).to_bytes(4, 'big') + (h1).to_bytes(4, 'big') +
            (h2).to_bytes(4, 'big') + (h3).to_bytes(4, 'big') +
            (h4).to_bytes(4, 'big') + (h5).to_bytes(4, 'big') +
            (h6).to_bytes(4, 'big') + (h7).to_bytes(4, 'big'))

def _sigma0(num: int):
    """As defined in the specification."""
    num = (_rotate_right(num, 7) ^
           _rotate_right(num, 18) ^
           (num >> 3))
    return num

def _sigma1(num: int):
    """As defined in the specification."""
    num = (_rotate_right(num, 17) ^
           _rotate_right(num, 19) ^
           (num >> 10))
    return num

def _capsigma0(num: int):
    """As defined in the specification."""
    num = (_rotate_right(num, 2) ^
           _rotate_right(num, 13) ^
           _rotate_right(num, 22))
    return num

def _capsigma1(num: int):
    """As defined in the specification."""
    num = (_rotate_right(num, 6) ^
           _rotate_right(num, 11) ^
           _rotate_right(num, 25))
    return num

def _ch(x: int, y: int, z: int):
    """As defined in the specification."""
    return (x & y) ^ (~x & z)

def _maj(x: int, y: int, z: int):
    """As defined in the specification."""
    return (x & y) ^ (x & z) ^ (y & z)

def _rotate_right(num: int, shift: int, size: int = 32):
    """Rotate an integer right."""
    return (num >> shift) | (num << size - shift)

if __name__ == "__main__":
    print(generate_hash("Hello").hex())

5. Reference

• symmetric ciphers
  https://www.hypr.com/security-encyclopedia/symmetric-cipher (Symmetric Key)
• message digests
  https://www.solanara.net/solanara/digestsolaris (Hash)
• PBKDF2
  https://en.wikipedia.org/wiki/PBKDF2
• other references
• 1 https://d2.naver.com/helloworld/318732 (Adaptive Key Derivation Functions)
• 2 https://gist.github.com/aJchemist/f2d08f328f0458be8ee8 (Cryptography Keywords & Definitions)
• 3 https://www.crypto101.io/ (Crypto 101)
• 4 https://cryptopals.com/ (Cryptopals Crypto Challenge)
• 5 https://ko.wikipedia.org/wiki/%EC%87%84%EB%8F%84_%ED%9A%A8%EA%B3%BC (Avalanche Effect)
• 6 https://www.beyondidentity.com/glossary/rainbow-table-attack (Rainbow Table Attack)
• 7 https://whiteglass.tistory.com/3 (ljust, rjust)
• 8 https://en.wikipedia.org/wiki/List_of_Unicode_characters (List of Unicode characters)
• 9 http://cactus.io/resources/toolbox/decimal-binary-octal-hexadecimal-conversion (Type conversion)
• 10 https://huskdoll.tistory.com/988 (ASCII Code Table)