해시 함수?(feat.computer science)

 긴 글이 되지는 않을 것 같습니다. 어쩌다 운이 좋게도 IT 대기업 면접을 보게 되었습니다. 그러나 아직 준비되지 않은 인재였던 탓인지 질문에 대한 대답이 많이 부족했었습니다. 그 중 하나가 해시 함수에 대한 정의를 제대로 알고 있냐는 것이었는데, 사실 이 질문은 제가 이력서에 적어둔 내용과 관련해서 나왔던 질문이었습니다.(사실 제 무덤을 제가 판 셈인거죠...)

 해시 함수는 무엇일까요. 해시 함수의 정의는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.(정의는 위키백과에 잘 나와 있네요.)

 해시 함수는 함수의 특성인 특정 값을 함수 f(x)에 대입했을 때 결과 값이 동일하게 나온다는 특성을 가지고 있습니다.(제가 이 한줄짜리 대답을 제대로 하지 못해 해시라는 주제를 모르고 아는 척 하는 사람이 되어버렸네요.) 덕분에 임의의 데이터를 특정 데이터로 매핑하는 것이 가능한 것입니다.

 

 해시 함수에 들어가는 원 데이터(임의의 길이의 데이터) = key 값

 해시 함수를 지나쳐 나온 고정된 길이의 데이터 = 해시값

 데이터를 해시함수에 넣고 해시 값을 추출하는 과정 = 해싱

 

 이러한 해시함수는 특정 값을 입력하면 항상 특정한 값을 전달해준다는 특징과, 입력값의 변화가 적어도 출력값의 변화가 해시함수가 무엇이냐에 따라 크게 변할 수 있다는 특징이 존재합니다. 또한, 특정 키 값에 대해 항상 일정한 해시값을 얻을 수 있으므로 데이터의 인덱싱에 유리합니다. 해시의 특성을 이용한 데이터 저장 방식인 해시 테이블을 이용하면 효율적인 데이터 처리 구조를 생성할 수 있습니다.

 이러한 해시 함수는 해시 맵과 같은 빠른 데이터 처리 방식과 암호화에 사용할 수 있습니다. 그 중 먼저 암호화에 사용되는 해시함수의 특징에 대해서 살펴보겠습니다.

 보안에서 사용되는 암호화 해시 함수의 제일 중요한 점은 입력값과 그에 상응되는 해시값에 대해 입력값에 따른 해시값이 일정한 것은 보장되나, 해시값의 임의적인 수정으로부터 안전하게 보호할 수 있어야 합니다. 그래야 입력과 해시가 대응되는 특성을 유지할 수 있고, 다른 특정 해시값으로의 변경을 막아 다른 입력값이 들어와도 원하는 값이 도출되는 사태를 막야아 하기 때문입니다. 이러한 조건을 만족하기 위해 필요한 성질에 대해서 알아보겠습니다.

 

 역상 저항성: 해시값만 주어진 경우, 그 해시값을 생성하는 입력값을 찾아내는 것이 불가능하다는 것을 의미하는 성질

 제 2 역상 저항성: 입력값과 해시값이 주어졌을 때, 해시값의 변경 없이 입력값을 찾아내는 것이 불가능하다는 것을 의미하는 성질. 즉, 2개의 다른 입력값에서 동일한 해시값이 추출되면 이 성질에 위배

 충돌 저항성: 2개의 다른 입력값에서 동일한 해시값을 찾는 것(충돌되는 해시)이 계산적으로 불가능한 성질. 제 2 역상 저항성을 만족하면 자동으로 만족하는 성질

 

 여기서 알아두면 좋은 것은 '충돌'이라는 단어인데, 충돌은 말 그대로 다른 입력값을 통해 해싱을 했으나, 결과값이 동일한 값이 나오는 것을 의미합니다.

 

 만약 i like programming 이라는 단어와 i hate programming이라는 단어가 있다면 이 두 단어는 분명 다른 해시값이 도출되어야 합니다. 그러나 두 문장 모두 해시값 0044를 호출한다면 어떻게 될까요. 만약 이 두 문장 중 앞의 문장이 제 구글 비밀번호였다고 생각해봅시다. 구글은 특정 해시함수를 사용해서 0044라는 값을 테이블에 저장해두고 제가 로그인할 때 마다 해시값을 이용해 비밀번호의 일치를 확인한다면, i hate programming을 입력해도 로그인이 가능할 것입니다. 이것을 충돌이라고 하는데, 이러한 충돌이 일어나게 되면 보안 문제가 발생할 것입니다. 그래서 보안을 위해 사용하는 해시 함수에는 충돌에 민감하게 됩니다.

 또한 암호화 해시 함수는 눈사태 효과를 적용해야 하는데(적용되지 않는다고 해서 암호화 해시 함수가 아닌 것은 아닙니다.), 눈사태 효과는 입력값이 아주 조금만 달라져도 (apple -> epple로의 변화처럼) 해시값이 전혀 다른 결과가 도출되는 것을 의미합니다. 이를 만족하게 되면, 비슷한 해시값이 도출되는 입력값을 찾더라도 그 입력값과 비슷한 입력값이 찾고자 하는 해시값이라는 것을 보증해줄 수 없게 되어, 해시 함수를 조금 더 안전하게 만들어주는 역할을 합니다.

 이러한 암호화 해시 함수에는 여러가지 함수가 있는데 그 중 하나가 SHA-로 정의되는 시리즈입니다.

 SHA 시리즈는 Secure Hash Algorithm라는 단어이고, 안전한 해시 알고리즘이라고 해석됩니다. 이러한 알고리즘은 여러가지 비트 연산과 자르기를 통해 이루어지며, 해시값의 길이가 항상 일정하게 도출됩니다. 예전 SHA 시리즈인 SHA-0이나 SHA-1로 대표되는 알고리즘은 이미 충돌되는 해시값이 발견된 적이 있어 안전하지 않아 거의 사용되지 않고 있습니다. 현재 SHA-256부터는 아직 뚫리지 않은 안전한 해시 함수로 많은 곳에서 사용되고 있다고 합니다.

 

---

침조: https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

https://ko.wikipedia.org/wiki/%EC%95%94%ED%98%B8%ED%99%94_%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98