정리정리정리

해시값의 복호화 ?? 본문

일하다가??

해시값의 복호화 ??

_JSPark 2016. 10. 8. 22:18

해시값은 복호화가 불가능한데.. 이게 무슨소린가


아래와 같은 사이트에서 해준다고 하니 참;; 이게 무슨소리 인가 했다.

http://tools.web-max.ca/encode_decode.php


결론적으로 위같은 사이트는 사용자들이 등록한 표본이 되는 값들을 레파지토리에 가지고 있다가 사용자가 요청한 결과중에 일차하는 해시값이 있으면 표본 값을 돌려주기만 하는 그런 사이트인거 같았다.


이에대해 잘 정리되어있고 이해하기 쉬운 블로그 글을 발견! 글을 퍼와 정리하였다!





어떤 값을 해시함수에 넣어 해시값을 만드는 과정을 해싱(hashing)이라고 하는데, 엄밀하지 않은 일상 대화에서는 해시함수로 "함호화"를 한다고 표현하기도 한다.

이 표현이 때로는 큰 오해를 불러 일으키곤 하는데, 암호화라는 말을 들으면 마치 복호화도 될 것 같은 느낌이 들기 때문이다.




1. 함호화, 복호화, 해싱


MD5는 취약하다거나, SHA1도 취약점이 발견되었다거나 하는 뉴스를 접하고 나면, 위에서 말한 "복호화"에 대한 오해와 합쳐져서 취약한 해시 알고리즘으로 만든 해시값은 복호화가 될 것 처럼 생각하거나, MD5나 SHA1는 어떤 상황에서도 쓰지 말아야할 대단히 안좋은 알고리즘인 것으로 생각하게 되는 것 같다.


하지만 해싱(hashing)과 암호화(encyrption)/복호화(decryption)은 대단히 다른 개념이고, 해시함수의 취약점이라는 것은 좀 더 미묘한 이야기이며, 거의 모든 상황에서 해시값은 복호화를 할 수 없다.





2. 비둘기집 원리 (복호화가 불가능한 이유)


왜 해시값은 복호화를 할 수 없는지 이해하려면 해시의 정의와 작동 방식을 알아야 한다.

"임의의 길이를 갖는 비트열을 입력으로 받아서 정해진 길이의 비트열을 반환하는 함수"를 해시함수라고 한다. 예를 들어 아래와 같이 이름을 넣었을 때 성을 반환하는 함수는 해시함수이다.


  • 강규영 -> 강
  • 홍길동 -> 홍
  • 이몽룡 -> 이

일단, 해시함수도 함수이기 때문에 입력이 같으면 출력이 같다. 어제 hash("강규영")을 수행한 결과가 "강"이었다면 오늘 hash("강규영")을 수행하도 결과는 "강"이다.

그런데 그 반대의 경우가 항상 성립하지는 않는다. 수학에서의 예를 들자면 f=x2와 같은 함수가 있을 때 f(2) f(2)는 둘 다 4이다.


그렇다면 해시함수는?

정의상 모든 해시함수는 치역의 크기(cardinality)가 고정되어 있고 대체로 정의역에 비해 작다. 정의역보다 치역이 작으면 입력값은 다르지만 결과값은 같은 경우가 반드시 생길 수 밖에 없다. 이를 비둘기집 원리(pigeonhole principle)라고 부른다. 비둘기집 수보다 비둘기 개체수가 더 많은 상황에서 비둘기들을 모두 비둘기집에 넣으면 최소한 한 개 이상의 비둘기집에는 최소한 두 마리 이상의 비둘기가 있을 수 밖에 없다. 이 비유에서 비둘기는 정의역, 비둘기집은 치역이다.


위의 이름 해시함수에서 예를 들자면, "강규영"의 해시값도 "강"이지만, "강감찬"의 해시값 또한 "강"이다.

제곱함수에 어떤 값을 넣었을 때 그 결과가 4라는 것을 알더라도, 처음에 넣은 값이 -2였는지 2였는지 알 방법이 없는 것과 마찬가지로, 해시값 "강"으로부터 원래의 값을 복원할 방법은 없다. 해시함수는 정의역과 치역을 1:1로 매핑하지 않으며, 해싱을 하면 정보 자체가 줄어들기 때문이다.


위 예시에서는 -2 혹은 2 중에 하나일테니 상대적으로 찍기가 쉬워 보이는데, 다른 함수를 생각해보자. 예를 들면 나머지(modulo)함수. 어떤 수를 넣으면 그 수를 3으로 나눈 나머지를 반환하는 함수 f=xmod3가 있다. 이 함수에 어떤 수를 넣었더니 결과가 2였다. 원래의 수는 무엇일까? 그런 수는 무한하게 많다. 정확히는 자연수 집합의 크기와 같다(countably infinite).





3. 해시함수의 취약성


복호화가 안된다면 해시함수가 취약하다는 것은 대체 뭘 말하는건가? 이걸 이해하려면 해시함수의 일반적인 용도에 대해 알아야 한다.

사용자의 아이디와 비밀번호를 저장해둔 데이터베이스 테이블이 있다고 치자. 이 테이블이 털리면 사용자의 비밀번호가 유출된다. 테이블이 털리지 않게 잘 관리하는 것도 중요하지만, 만에 하나 테이블이 털리더라도 비밀번호가 유출되지 않을 수 있다면 좋을 것이다. 어떻게 할까? 비밀번호를 그냥 저장하는 대신, 비밀번호를 해싱하여 해시값을 저장하면 된다.


사용자가 로그인을 하기 위해 비밀번호를 입력하면, 입력받은 비밀번호를 해싱하여 해시값을 구하고, 이 값이 데이터베이스에 있는 (이미 해싱된) 해시값이랑 동일한지 맞춰보면 사용자의 비밀번호를 그대로 저장하지 않고도 로그인을 처리할 수 있다.


이 상태에서 데이터베이스가 털렸다고 가정하자. 해커는 비밀번호 대신 비밀번호의 해시값을 얻게 된다. 이 상황에서 비밀번호를 얻어내려면 어떻게 해야하나? 해시값 자체만을 보고 비밀번호를 알아낼 방법은 없고 몇 가지 꼼수들이 있다.


예를 들면 사람들이 비밀번호로 많이 쓸만한 문자열을 표로 만들어놓고, 각각을 해싱을 해본 후 여기에 맞는 비밀번호 해시값이 있는지 맞춰보는 방법이 있다. 이렇게 해서 맞는 값이 발견되면 아마도 그 사람은 그 비밀번호를 쓰는 것일 가능성이 높을 것이다. (확실하다고 하지 않고 가능성이 높다고 한 이유는 위에서 설명한 비둘기집 원리에 의한 것) 이런 방식의 공격을 사전 공격(dictionary attack)이라고 한다.


또다른 꼼수로는 애초에 사용자의 비밀번호를 찾아내는 것을 목적으로 할 게 아니라, 사용자의 비밀번호 해시값과 동일한 해시값을 만들어내는 입력 문자열을 찾는 것을 목적으로 두는 것이다. 이 값을 찾기만 하면, 사용자의 진짜 비밀번호를 모르더라도 해당 시스템 혹은 해당 시스템과 동일한 해시함수를 쓰는 다른 시스템들에 해당 사용자의 계정으로 로그인을 할 수 있게 되기 때문이다. 


이러한 공격을 막으려면(정확히 말하면 대단히 어렵게 만들려면) collision resistance, preimage resistance 등의 성질을 가지는 해시 알고리즘을 써야 한다.


이런 식으로 여러 종류의 공격에 대비하여 해시함수에 몇 가지 수학적인 특성들을 더 부가한 것을 cryptographic hash function 혹은 secure hash function 등으로 부른다. 


예를 들어 SHA 계열의 해시함수들. 또는 해시함수 자체는 그대로 두고, 각 사용자별 비밀번호를 해싱하기 전에 부가적인 값(salt)을 붙여서(소금을 친다고 표현한다) 해싱을 함으로써 공격의 효율을 크게 저하시키는 방법(rainbow table 류에 대한 카운터)도 대단히 유효하다.

중요한건, 어떤 공격이건 간에 해시값 자체로부터 원래의 데이터를 얻어낼 수 있는 방법은 없다는 점이다. 왜냐하면 앞에서도 이야기한 바와 같이 정보 자체가 줄어들었기 때문이다.





4. 취약한 해시 알고리즘을 써도 되나 안되나.


그래서 취약한 해시 알고리즘을 써도 되는건가, 안되는건가? 뭔 용도로 쓰느냐에 따라 다르다.


예를 들어, 위에서 설명한 방식의 비밀번호 저장 및 검사 용도라면 해시 알고리즘의 resistance 특성이 대단히 중요하다. 그렇지 않을 경우 해시값을 취득한 해커가 해시충돌이 일어나는 값을 쉽게 찾을 수 있기 때문이다. 글 초반에 설명한 이름 해시함수("홍길동"을 넣으면 "홍"이 나오는 해시함수)는 그러한 특성이 전혀 없기 때문에 이 맥락에서 사용하면 망한다. (비밀번호가 "hello"인 경우 해시값은 "h"가 되는데, 해커는 해시값이 "h"가 되는 문자열을 수없이 나열할 수 있기 때문: "hi", "hey", "how" ...)


한편, PII(personally identifiable information)에 해당하는 정보를 익명화하기 위한 용도로 해시함수를 사용한다면 위와 같은 특성이 중요하지 않아진다. 사용자 ID(일반적으로 PII에 해당되는 것으로 본다)를 익명화하기 위해 이름 해시함수를 사용한다고 가정해보자. "alankang"의 해시값은 "a"가 되는데, 해커가 "a"를 취득한 후 할 수 있는 일이 무엇인지 생각해보자. 해시값이 "a"인 임의의 값들("all", "aha", "away"...)을 나열해봤자 아무 의미가 없다.


이 맥락에서 문제가 생기려면 "a"가 "alankang"임을 알아낼 수 있어야 하는데 이런식의 "복호화"는 앞에서 설명한 이유(해싱을 하면서 정보 자체가 줄어들었기 때문)로 인해 불가능하다.


물론 해커가 사용자 아이디 목록의 일부 혹은 전부를 미리에 취득하고 있는 경우 사전 공격(dictionary attack)을 통해 해시값이 일치하는 아이디를 찾아낼 수 있을텐데, 그 조차도 소금을 치지 않았을 때의 이야기다.

결국 어떤 해시함수를 써도 되는지 잘 결정하려면 (다른 모든 알고리즘 선택과 마찬가지로) 해당 함수가 어떤 특성을 갖는지 알고, 내가 응용하려는 상황이 어떤 상황인지 잘 이해할 필요가 있다. 이러한 이해가 부족한 상황이라면 (다른 모든 알고리즘과 마찬가지로) 아무리 좋은 해시함수를 가져다가 쓰더라도 문제가 생기기 쉽다.





5. 복호화 가능한 해시함수 == 압축률이 무한대인 압축 알고리즘


복호화 가능한 해시함수라는 것이 어떤 의미인지 조금만 생각해보자.


임의의 크기의 정보를 고정된 크기의 정보로 줄여주는 것이 해시함수이다. 그리고 고정된 크기의 해시값을 다시 원래 정보로 되돌리는 것이 복호화다. 이런 해시함수 및 복호화 알고리즘이 존재한다면 이는 곧 압축률이 무한대인 기적의 압축 알고리즘이 탄생한 것과 같다.













참조.


http://www.ecogwiki.com/%ED%95%B4%EC%8B%9C%EA%B0%92%EC%9D%98_%EB%B3%B5%ED%98%B8%ED%99%94

18 Comments
  • 프로필사진 진우 2018.01.04 17:49 기가 막히게 정리해주셨네요!! 정말 감사합니다ㅎㅎ 가려운 등을 누가 긁어준 기분이었어욯ㅎ
  • 프로필사진 _JSPark 2018.01.10 23:38 신고 ㅋㅋㅋ 굳
  • 프로필사진 ㅈㅇ 2018.02.26 13:07 정말 감사합니다. 이렇게 잘 풀어주신 글은 처음 보네요
  • 프로필사진 _JSPark 2018.03.22 21:27 신고 감사합니다
  • 프로필사진 inho 2018.03.21 15:24 감사합니다!!! 너무 잘 봤습니다.
  • 프로필사진 _JSPark 2018.03.22 21:27 신고 감사합니다~
  • 프로필사진 지나가다 2018.03.26 14:35 필력이 굉장히 좋으시네요 ㅎㅎ 단숨에 읽어지네요 ㅎㅎ
  • 프로필사진 _JSPark 2018.03.27 22:52 신고 ㅋㅋ감사합니다
  • 프로필사진 frontDev 2018.06.27 12:16 안녕하세요 궁금한 점이 있는데 여쭤봐도 될까요?
    로그인 페이지에서 비밀번호 같은 정보를 서버로 전달할 때 암호화를 해야하는데, PBKDF2라는 알고리즘?이랑 SHA-256 해싱 알고리즈이랑 어떤 관계가 있는지 궁금증을 지울 수가 없습니다ㅜ. pbkdf가 해싱 함수에 salt, itreation을 해주는 건가요?
  • 프로필사진 _JSPark 2018.06.27 23:01 신고 일반적으로 사용자가 입력한 비밀번호는 발씀하신 SHA-256등의 해시 함수를 이용해서 단방향으로 해싱을 진행하고 이런 수학적인 연산을 통해 생성된 암호화된 메시지를 다이제스트라고 합니다.
    해시 함수를 여러가지방법으로 사용할수있는데
    1. 솔팅 : 솔트+평문 -> 해시함수 -> 다이제스트 과정을 거치는 방법을 솔팅이라합니다.

    2. 키 스트레칭 : 평문 -> 해시함수 -> 다이제스트 아웃풋을 다시 해시함수의 입력값으로 하여 반복해주는 과정을 거치는 방법이 기본적이 키 스트레칭을 이용한 방법인니다.

    3. Adaptive Key Derivation Functions : 다이제스트를 생성할때 위 1번과 2번을 반복하며 여러 값을 추가하여 쉽게 다이제스트를 유추할수 있도록 도와주는 일종의 기능을 가진 함수를 말합니다. ex) PBKDF2, bcrypt ..
    그중하나가 PBKDF2 입니다.
    자바로도 라이브러리들을 이용해 간단히 구현가능합니다.

    잘정리되있는 링크가 있습니다.
    https://d2.naver.com/helloworld/318732
  • 프로필사진 Algo 2018.09.14 16:27 안녕하세요 글 잘읽었습니다.
    의문이 있는데요. 비둘기집 원리에 의하면 해시 충돌은 일어날 수 밖에 없으니깐 충돌하는 값을 알게되면 복호화한 것으로 되는 것아닌가요?
  • 프로필사진 _JSPark 2018.09.14 21:30 신고 취약한 해시 알고리즘을 사용했을때는 충돌하는 값은 확률적으로 충분히 있을수 있는 일입니다.
    그렇지만 그게 복호화의 의미는 아닙니다.
    hash(x) == hash(y) 라 하여도 그것이 실제 x == y 를 의미하는것은 아닙니다.
    A = encrypt(a), a = decrypt(A) 가 암복호화입니다.
  • 프로필사진 Nowuyk 2018.10.22 21:45 저는 저런 MD5, SHA-1 복호화가 second preimage resistance를 깨는건줄 알았는데 그냥 레인보우 테이블이었군요 -_- 함부로 저런데서 민감한 정보를 해쉬화하지 말아야겠네요
  • 프로필사진 엽기토끼이요 2019.10.23 20:04 신고 감사합니다. 웹은 반 이상이 똥인데 여기는 보석이 반 이상 이네요.
  • 프로필사진 라에 2019.12.16 18:07 안녕하세요. 해시와 암복호화 관련된 글을 보다가 우연히 발견한 글인데, 도움이 많이 되었습니다! 정말 감사합니다아!!
    그런데 제가 해시부분의 이해도가 좀 떨어져서 그런지 글을 보고도 좀 궁금해진 부분이 있어요. 가능하시면 답변해주시면 너무나 감사할것같습니다..!
    예를 들어주셨던 부분에 hash("강감찬"), hash("강규영")의 해시값이 둘다 "강"으로 나온다는 이야기가 있는데
    그렇다면 어떻게 해시함수로 메시지의 무결성을 보장할 수 있는건가요? (해시값이 정해진 길이인경우를 기준으로 생각했습니다)
    abcd -> !94jfjsk
    pdxa -> !94jfjsk
    좋은 해시함수는 위 예제처럼 해시값이 중복되지 않겠지만
    저렇게 중복이 날 수 있는가능성이 있는게 해시함수인 것 같은데.. 어떻게 해시함수가 메세지의 무결성에 대해 검증을 할 수 있는것인지 모르겠어요..
    전송하는 메세지에 대해 압축을 전혀 하지않은 해시값 그대로를 비교하는것인가요?
  • 프로필사진 dd 2021.03.03 09:59 해시값 복구 관련으로 검색하다 우연히 보게 되었는데
    설명이 아주 깔끔하네요
    비둘기집 원리에서 함수로 예를 든 부분에서 감탄했습니다
  • 프로필사진 코린이 2021.09.06 11:21 21년 9월에도, 새로운 배움을 얻어갑니다..와...5년전 글인데 이렇게 가려운 곳을 시원하게 긁어주다니요.. 설명감사합니다!
  • 프로필사진 꿈코더 2021.10.22 14:05 감사합니다.
댓글쓰기 폼