Introduction
이전 글에서 equals() 메서드를 오버라이딩 하면 반드시 hashCode() 메서드도 오버라이딩 해줘야 된다고 했다. 그렇다면 hashCode()는 왜 오버라이딩 해야 하는지 알아보기 전에 해시(Hash)에 대해서 정확히 알고 있어야 된다는 생각이 들어 따로 해시 함수에 대해서만 정리하려고 한다.
근데 해시 함수가 왜 중요한데?
해시 함수에 대해서는 개발자라면 어디선가라도 들어봤을 것이고 논란의 여지가 없는 주제이기도 하다. 하지만 실제 해시 함수를 사용하는 상황이 오게 되면 어떤 상황에서 어떻게 사용해야 하는지 헷갈리기도 하고 암호화와 사용해야 될 상황을 혼동하는 경우도 많이 보았다. 다음은 실제 회사에서 동료 개발자들과 했던 대화 내용이다.
개발자 A : 백엔드에서 유저에 대한 정보를 저장할 때 비밀번호를 해시화를 해야 할까요? 아니면 암호화를 해야할까요?
개발자 B : 당연히 암호화를 해야죠! 비대칭암호화 방법을 사용해서 비밀번호를 암호화 한 뒤에 DB에 저장해야 합니다!
개발자들이 나눴던 대화는 올바른가? 암호화를 해서 비밀번호를 저장하는 것이 맞는가? 관련된 답변은 해시 시리즈를 통해 천천히 풀도록 하자!
해시 함수란?
해시 함수의 정확한 정의는 임의의 크기를 가진 값을 "고정 크기"의 값에 대응시키는 함수이다. 가끔 얘기하다 보면 hashCode() 라는 java의 함수와 정의를 헷갈려 하는 경우를 보았다.(이번 포스트를 쓰게 된 이유이기도 하다.) "해시 함수"는 우리가 말하는 "수학적인 함수"이다.
예전 기억을 떠올려보면 함수의 성질? 정의? 부분에서 하나의 입력값은 항상 하나의 출력값을 내야한다라는 부분이 있다. 따라서 해시 함수도 하나의 입력값을 항상 하나의 출력값을 낸다. 하나의 입력값이 때에 따라서 A, B로 나뉘지 않는다.
입력값이 같다면 언제나 출력값도 같은 성질을 프로그래밍 관점에서는 결정론적 작동을 한다라고 말한다. 결정론적 작동의 경우 P vs NP 문제에서 P문제와 NP문제를 구분하는 기준과 관련이 있다. 관련되서는 다른 포스트에서 더 자세히 다뤄보겠다.
해시 함수 용도
해시 자료구조
Hash하면 떠오르는 것이 바로 해시테이블, 해시맵이다. 당연하게도 두 자료구조는 해시 함수를 사용한다.
그렇다면 해당 자료구조의 어떤 부분에서 해시 함수를 사용하는 것일까?
이 부분을 잘 이해하기 위해서는 자료 구조(Data Structure)를 조금만 이해하면 더 쉽게 받아들일 수 있다. 알고리즘을 공부하며 배열부터 시작하여 그래프까지 공부하면 말 그대로 자료구조는 "어떻게 데이터를 알아서 잘 딱 깔끔하게 센스(알잘딱깔센)있게 저장 + 조회 + 수정 + 삭제를 할까?" 라는 질문에서 나온 대답의 결과이다.
데이터를 내가 "쉽게 찾는 위치"에 잘 두면 저장, 조회, 수정, 삭제가 쉬워진다!
예를 들어 설명하면 배열은 내가 쉽게 찾을 수 있는 위치를 순서에 맞춰 0번 위치, 1번 위치, 2번 위치에 맞게 저장하여 찾는다. 연결 리스트는 내가 갖고 있는 데이터 뭉치의 첫번째 위치를 알면 연결되어 있어 순서대로 다음 위치까지 찾을 수 있다.
해시 자료구조는 지금까지 얘기했던 "쉽게 찾는 위치"를 해시 함수를 통해서 결정한다. 해시 함수의 모든 성질들이 우리가 원하는 조건을 만족한다.
- 내가 입력한 값이 항상 같은 곳을 가르키는가? [Yes] - 해시함수의 결정론적 작동
- 내가 입력한 값의 길이나 타입은 상관없는가? [Yes] - 해시함수는 고정 크기의 값에 대응 시킴
내 기준에 맞춰 데이터를 쉽게 찾을 수 있는 위치에 저장할 수 있으니 빠르겠네?
이상 | 현실
조회 : O(1) | O(logN)
저장 : O(1) | O(logN)
삭제 : O(1) | O(logN)
수정 : O(1) | O(logN)이상과 현실은 다르듯 하드웨어적인 문제로 인해 성능의 타협점을 찾을 수 밖에 없지만 그래도 훌륭한 자료구조임에는 틀림없다. 왜 이렇게 성능의 타협점을 찾을 수 밖에 없는지 다른 포스트에서 다루기로 하고 해시 함수를 통해 해시 테이블은 "쉽게 찾는 위치"를 결정한다.
데이터의 동등성 비교
이전에 살펴봤던 동등성/동일성 포스트와 연결하여 생각하면 데이터가 같음을 비교하는 것은 프로그래밍에서 매우 중요한 이슈이다. 특히 숫자의 같음보다 문자열의 같음을 비교하는 것은 쉽지 않다. 다음과 같은 문자열 2개가 같은지 어떻게 프로그램을 작성할 수 있을까? 예시는 두 사람의 이름이 같은지 판단한다.
String myName = "Captain Fantastic Faster Than Superman Spiderman Batman Wolverine The Hulk And The Flash Combined";
String yourName = "The former Mrs McManus is now called Red Wacky League Antlez Broke the Stereo Neon Tide Bring Back Honesty Coalition Feedback Hand of Aces Keep Going Captain Let's Pretend Lost State of Dance Paper Taxis Lunar Road Up Down Strange All and I Neon Sheep Eve Hornby Faye Bradley AJ Wilde Michael Rice Dion Watts Matthew Appleyard John Ashurst Lauren Swales Zoe Angus Jaspreet Singh Emma Matthews Nicola Brown Leanne Pickering Victoria Davies Rachel Burnside Gil Parker Freya Watson Alisha Watts James Pearson Jacob Sotheran Darley Beth Lowery Jasmine Hewitt Chloe Gibson Molly Farquhar Lewis Murphy Abbie Coulson Nick Davies Harvey Parker Kyran Williamson Michael Anderson Bethany Murray Sophie Hamilton Amy Wilkins Emma Simpson Liam Wales Jacob Bartram Alex Hooks Rebecca Miller Caitlin Miller Sean McCloskey Dominic Parker Abbey Sharpe Elena Larkin Rebecca Simpson Nick Dixon Abbie Farrelly Liam Grieves Casey Smith Liam Downing Ben Wignall Elizabeth Hann Danielle Walker Lauren Glen James Johnson Ben Ervine Kate Burton James Hudson Daniel Mayes Matthew Kitching Josh Bennett Evolution Dreams";
System.out.println(myName.equals(yourName));myName과yourName 은 실제로 기네스북에 오른 긴 이름 2개를 찾아왔다. 지금은 직관적으로 두 이름이 다르다는 것을 알 수 있지만 한 글자만 다른 두 이름을 비교하려면 어떻게 해야될까? 의사 코드로 표현해보면
두 이름의 길이만큼 반복하며
한글자씩 비교하고
같으면 다음 문자를 비교
다르다면 두 문자열은 다른 문자결국 두 문자열의 길이에 연산이 영향을 받는다. 문자열의 길이를 k라고 한다면 O(k)만큼 걸릴 것이다. 그렇다면 우리가 아는 논문 표절(Plagiarism)을 검사하는 프로그램을 만든다고 할 때 직관적으로 생각해보면 논문의 글자수만큼 비교해야 되는 것인가? 하는 의문이 들 수도 있다.
이런 부분을 해시 함수의 성질을 사용하면 더 빠른 시간내로 비교가 가능하다.
- 해시 함수 성질[2] : 임의의 길이의 값을 고정된 크기의 값에 대응
String myName = "Captain Fantastic Faster Than Superman Spiderman Batman Wolverine The Hulk And The Flash Combined";
String yourName = "The former Mrs McManus is now called Red Wacky League Antlez Broke the Stereo Neon Tide Bring Back Honesty Coalition Feedback Hand of Aces Keep Going Captain Let's Pretend Lost State of Dance Paper Taxis Lunar Road Up Down Strange All and I Neon Sheep Eve Hornby Faye Bradley AJ Wilde Michael Rice Dion Watts Matthew Appleyard John Ashurst Lauren Swales Zoe Angus Jaspreet Singh Emma Matthews Nicola Brown Leanne Pickering Victoria Davies Rachel Burnside Gil Parker Freya Watson Alisha Watts James Pearson Jacob Sotheran Darley Beth Lowery Jasmine Hewitt Chloe Gibson Molly Farquhar Lewis Murphy Abbie Coulson Nick Davies Harvey Parker Kyran Williamson Michael Anderson Bethany Murray Sophie Hamilton Amy Wilkins Emma Simpson Liam Wales Jacob Bartram Alex Hooks Rebecca Miller Caitlin Miller Sean McCloskey Dominic Parker Abbey Sharpe Elena Larkin Rebecca Simpson Nick Dixon Abbie Farrelly Liam Grieves Casey Smith Liam Downing Ben Wignall Elizabeth Hann Danielle Walker Lauren Glen James Johnson Ben Ervine Kate Burton James Hudson Daniel Mayes Matthew Kitching Josh Bennett Evolution Dreams";
int myNameHash = hashing(myName);
int yourNameHash = hashing(yourName);
System.out.println(myNameHash == yourNameHash);이전에 O(k)만큼 걸렸던 비교연산이 O(1)밖에 걸리지 않는다. Wow! 이 부분에서 의문이 들수도 있다.
해시 함수를 수행하는 시간은 왜 포함 안시키지? 해시 함수를 통해 나온 두 값이 진짜 다른가?
맞다! 포함시켜서 계산해야 한다. 같을 수도 있다.
이 부분은 해시 함수의 속성(효율성, 균일성)에서 더 다뤄보자.
데이터의 원본을 저장하지 않기
예전 뉴스에 사용자들의 정보가 유출되어 피해가 막심하다는 소식을 접한 적이 있을 것이다.
[웹호스팅 업체 해킹에 또 당했다…아이네임즈 랜섬웨어 '감염']
https://www.techm.kr/news/articleView.html?idxno=71545
현재 사이버 보안이 강조되는 이유는 한번의 해킹만으로 너무나 많은 개인 정보들이 유출되고 이로 인해 받을 수 있는 피해가 상상이기 때문이다. 그렇다면 우리는 이것을 막기 위해 어떻게 해야할까?
모순 : 사물의 앞뒤가 서로 맞지 않음. 모든 것을 뚫는 창과 모든 것을 막는 방패
사용자들의 정보를 탈취하려는 사람들과 그것을 어떻게든 막아야되는 관계를 설명하기에 너무 적절한 단어같아서 인용해봤다. 우리가 웹 서비스를 운영하기 위해서는 당연히 네트워크에 연결되어 있어야 하고 지속적으로 해킹하는 방법은 발전하기 때문에 그에 발맞춰 해킹하는 사람을 해킹하는 방법(?)을 익혀야 하는 것일까?
그러기에 우리는 서비스를 개발과 디버깅하기에도 너무 바쁘다.
게다가 현실적으로 "소잃고 외양간 고치는 방식"의 접근만 할 수 있다.(왜냐하면 해커들은 전혀 알려지지 않은 항상 기상천외한 방법을 사용하기 때문에)
이제 앞서 개발자 두 명이 대화했던 것에 대한 설명이 시작된다!
그렇다면 해킹이 이루어져 우리들이 저장했던 데이터들이 해커들에게 넘어갔었을 때 암호화된 데이터를 갖고 간다면 괜찮지 않을까? 결국 암호화된 데이터를 볼 수 없으니까라며 행복 회로를 돌릴 수도 있다.
[New Chainshot Malware Found By Cracking 512-Bit RSA Key]
https://www.bleepingcomputer.com/news/security/new-chainshot-malware-found-by-cracking-512-bit-rsa-key/
앞서 말했듯 해커들은 기상천외한 방법으로 해킹을 시도한다. 암호화 기법 또한 예외가 아니다. 512-Bit RSA 방식의 암호화도 파훼되었다.
소를 비밀 금고에 넣고 외양간에 넣어놨다고 안심하면 안된다. 훔쳐간 도둑들은 비밀 금고를 풀 방법을 알고 있을 수도 있다. 혹은 찾아낼 것이다. 그렇기 때문에 우리는 다른 방식으로 문제를 해결할 필요가 있다. 결국 우리가 필요한 것은 해커가 데이터를 갖고 갔을때 사용자의 민감한 정보를 알 수 없게 만들지만 우리 서비스에는 사용할 수 있게 해야한다.
예를 들어 앞서 보았던 "비밀번호"를 예시로 들어보자! 우리가 사용하는 비밀번호의 역할은 요청하는 사람이 진짜 해당 유저인지 알고 싶은 것이다. 코드로 보면,
public boolean login(String id, String password) {
User user = getUser(id); // 저장되어 있는 User의 정보를 id를 통해 있는지 조회
if (user.getPassword().equals(password)) { // password가 같다면 해당 유저가 맞으므로 로그인 완료
return true;
}
return false;
}password의 역할은 신원을 확인하는 수단일 뿐 비밀번호가 서비스에서 특별한 의미를 가지지 않는다. 그렇다면 비교만 잘되면 되는 것이네라고 생각할 수 있다! 그렇다면 회원가입할 때 password를 비교할 수 있는 무엇인가로 저장한다면 로그인도 성공적으로 수행할 수 있을 것이다.
public boolean signUp(String id, String password) {
String passWordConverted = convert(password)
User user = new User(id, passWordConverted); // 새로운 유저 생성 id는 key, password는 변환된 무엇인가?
Database.save(user); // 데이터 베이스에 유저를 저장
return false;
}
// User | id | password
// 1 | key | ?????이런 방식으로 저장하면 login() 에서 변환된 password와 비교한다면 우리가 원하는 로그인 과정을 그대로 수행할 수 있다. 그래서 여기서 말하는 convert()는 어떤 변환을 수행해야 할까에 대한 적합한 답변은 바로 암호학적 해시다.
public boolean login(String id, String password) {
User user = getUser(id); // 저장되어 있는 User의 정보를 id를 통해 있는지 조회
if (user.getPassword().equals(convert(password))) { // password가 같다면 해당 유저가 맞으므로 로그인 완료
return true;
}
return false;
}해시는 다 같은 해시 아닌가라고 생각할 수 있지만 해시는 두 가지 방식으로 분류할 수 있고 이 중에서 암호학적 해시로 password로 저장하면 앞서 설명했던 문제들을 해결할 수 있는 실마리를 얻게 된다.
그러면 암호학적 해시를 사용하면 안전한가?
답은 아니오다...
개발자 B : 아니, 그러면 결국 암호화 써도 되네
개발자 A : 아직 끝나지 않았어요... 근데 이것만으로는 설명이 부족해요, 해시의 속성을 알아야 해요
여기서 해시 함수의 추가적인 성질이 언급되야 한다.
- 해시 함수 성질[3] : 해시 함수는 단방향이다.
해시 함수는 위의 그림과 같이 단방향이다. 앞서 언급했듯이 수학 함수에서 결과(치역)를 통해 정의역을 알 수 없는 것과 같다. 그렇기 때문에 암호학적 해시 함수를 사용하여 DB에 저장하는 것이 암호화를 통해 저장하는 것보다 안전하다. 그렇다고 해킹으로부터 완전 해방될 수 없다.
비밀번호의 해시화를 통한 저장은 추가 포스트를 통해 추가적으로 알아볼 예정이다😄
이어서...
다음 포스트에서는 순서에 맞게 Hash 함수를 활용한 Data Structure부터 알아보려고 한다. 마치 드라마에서 내일 회차에 나올 법한 얘기가 그 다음주에 나오는 느낌이지만 자료구조와 관련하여 나오는 해시 함수의 속성을 알면 최종적으로 말할 비밀번호의 해시화를 통한 저장에 대한 이해가 더 쉬워질 것 같다.
REF
Revision Hisotory
[2022.04.10]
암호학적 해시를 사용하여 Password를 바뀐 뒤 저장해야 된다고 말했으나 결론이 없어서 왜 그런지 이유를 추가했다.
