Hashing

Hashing

What is Hashing?

우리는 plain text를 암호화 해두면 나중에 누군가가 그 데이터를 빼가더라도 key가 없으면 풀 수 없기 때문에 안전성이 더 높아졌다고 생각한다. 하지만 또 다른 alternative technique들이 존재하는데 그 중 하나가 Hashing이다. Hashing은 encryption과 비슷하지만 양방향으로 암호화가 가능한 encryption과 달리 hashing은 한방향(encrypt)으로만 가능하다.

Hashing은 key를 없애고 원래의 plain text로 돌아갈 수 없도록 만들었다. 단방향의 함수는 table이 compromised되어 hashes들이 유출되더라도 hash를 원래의 텍스트로 되돌릴 수 없기 때문에 우리의 위험을 제거한다.

보편적인 hashing function에는 bcrypt, scrypt, SHA-1, MD5가 있다. 하지만 모든 해쉬들이 동일하게 만들어지는 것은 아니다. 좀 더 퀄리티가 높은 hash인 bcrypt, scrypt를 사용하도록 한다.
함수를 통과해서 나온 산출물을 Hash 또는 Message Digest라고 한다. 만약 같은 original string을 input으로 넣는다면 항상 같은 jumbled up output을 얻게 될 것이다. jumgled up output을 다시 original text로 되돌릴 방법은 없다.

Using Hashing to Secure Our User Tables

우리는 우리의 database table에 비밀번호를 저장할때 encryption을 사용했던 것과 비슷한 방법으로 hash를 사용할 수 있다. 이것은 우리의 database에 대해 bad actors를 포함한 key의 위험성으로부터 어느 정도 지켜줄 것이다.

사용자가 가입을 통해 새로운 계정을 생성하면 user name과 함께 message digest를 user table에 저장한다. Sequence diagram을 살펴보면, 이제 user lookup을 수행할때 plain text를 제공하는 것 대신 message digest를 제공한다.

패스워드가 맞는지 비교할때, 사용자 가입 form에서 제출된 패스워드를 hashing function에 통과시킨다. 그리고 hash와 바로 비교한다. 이 경우에는 데이터베이스는 실제 사용자의 패스워드를 절대 알 수 없다.

만약 유출된 비밀번호를 sign-in form을 통해 전송을 시도한다면 그 사람은 훔친 hash를 가지고 있을 뿐이다. 만약 그 해시가 전송된다면 그 데이터는 다시 해쉬 함수를 지나가게 되고 전혀 다른 message digest를 만들어내게 된다. 만약 해시 값이 일치하지 않는다면 우리는 시스템에 접근을 허용하지 않는다.

이로써 우리가 database에 존재하는 대부분의 위험을 해결했다고 생각할 수도 있다. data table이 유출되어도 아무도 원래의 패스워드로 되돌릴 수 없다. 하지만 Rainbow Tables라는 공격이 존재하는데 이 방법은 그 과정을 우회할 수 있도록 한다.

목표를 달성할 수 있는 방법은 아무거나 해싱하는 것이다. common words의 리스트를 돌려서 rainbow table을 만들 수 있고 우리의 hashing 함수를 적용하여 output을 dictionary object에 저장할 수 있다. 만약 hash function이 매우 계산하기 쉽다면 이것은 꽤 다루기 쉬운 문제가 된다. Hash word pairs 목록을 만들기위해 수천만개의 단어를 거치는 것은 그렇게 어려운 일이 아니다.

만들기만 하면, 우리의 해시 리스트들을 검토하여 rainbow table 내에 있는 hash에 대응하는 것을 찾아 원래의 패스워드를 추적할 수 있다. bcrypt나 scrypt와 같이 계산하기 빡센 알고리즘 대신 SHA-1이나 MD5 알고리즘을 사용하지 말라는 이유이다. 이렇게 복잡한 함수들이 hash를 만드는데 더 시간이 오래 필요하므로 쉽게 규모로 생성될 수 없다(?)(at scale as easily)
충분한 계산만 가능하다면 어느 hashing function을 사용하여 누구나 rainbow table을 만들 수 있다.

Rainbow table 때문에 모든 위험이 제거되지는 않는다. 해시가 유출되면 해시를 원래 암호로 추적한 다음 일반 텍스트 암호 인 것처럼 시스템 전체에서 사용할 수 있다. 하지만 이 방법은 우리의 위험을 훌륭하게 최소화한다.

Practice - Rainbow Tables

# Load the NIST list of 10,000 most commonly used passwords
with open('nist_10000.txt', newline='') as bad_passwords:
    nist_bad = bad_passwords.read().split('\n')
print(nist_bad[1:10])

# The following data is a normalized simplified user table
# Imagine this information was stolen or leaked
leaked_users_table = {
    'jamie': {
        'username': 'jamie',
        'role': 'subscriber',
        'md5': '203ad5ffa1d7c650ad681fdff3965cd2'
    }, 
    'amanda': {
        'username': 'amanda',
        'role': 'administrator',
        'md5': '315eb115d98fcbad39ffc5edebd669c9'
    }, 
    'chiaki': {
        'username': 'chiaki',
        'role': 'subscriber',
        'md5': '941c76b34f8687e46af0d94c167d1403'
    }, 
    'viraj': {
        'username': 'viraj',
        'role': 'employee',
        'md5': '319f4d26e3c536b5dd871bb2c52e3178'
    },
}

# import the hashlib
import hashlib 
# example hash
word = 'blueberry'
hashlib.md5(word.encode()).hexdigest()

# RAINBOW TABLE SOLUTION
rainbow_table = {}
for word in nist_bad:
    hashed_word = hashlib.md5(word.encode()).hexdigest()
    rainbow_table[hashed_word] = word
    
# Use the Rainbow table to determine the plain text password
for user in leaked_users_table.keys():
    try:
        print(user + ":\t" + rainbow_table[leaked_users_table[user]['md5']])
    except KeyError:
        print(user + ":\t" + '******* hash not found in rainbow table')

jamie:	hello1
amanda:	qweasdzxc
chiaki:	******* hash not found in rainbow table
viraj:	PASSWORD