해시값은 복호화가 불가능한데.. 이게 무슨소린가
아래와 같은 사이트에서 해준다고 하니 참;; 이게 무슨소리 인가 했다.
http://tools.web-max.ca/encode_decode.php
결론적으로 위같은 사이트는 사용자들이 등록한 표본이 되는 값들을 레파지토리에 가지고 있다가 사용자가 요청한 결과중에 일차하는 해시값이 있으면 표본 값을 돌려주기만 하는 그런 사이트인거 같았다.
이에대해 잘 정리되어있고 이해하기 쉬운 블로그 글을 발견! 글을 퍼와 정리하였다!
어떤 값을 해시함수에 넣어 해시값을 만드는 과정을 해싱(hashing)이라고 하는데, 엄밀하지 않은 일상 대화에서는 해시함수로 "함호화"를 한다고 표현하기도 한다.
이 표현이 때로는 큰 오해를 불러 일으키곤 하는데, 암호화라는 말을 들으면 마치 복호화도 될 것 같은 느낌이 들기 때문이다.
1. 함호화, 복호화, 해싱
MD5는 취약하다거나, SHA1도 취약점이 발견되었다거나 하는 뉴스를 접하고 나면, 위에서 말한 "복호화"에 대한 오해와 합쳐져서 취약한 해시 알고리즘으로 만든 해시값은 복호화가 될 것 처럼 생각하거나, MD5나 SHA1는 어떤 상황에서도 쓰지 말아야할 대단히 안좋은 알고리즘인 것으로 생각하게 되는 것 같다.
하지만 해싱(hashing)과 암호화(encyrption)/복호화(decryption)은 대단히 다른 개념이고, 해시함수의 취약점이라는 것은 좀 더 미묘한 이야기이며, 거의 모든 상황에서 해시값은 복호화를 할 수 없다.
2. 비둘기집 원리 (복호화가 불가능한 이유)
왜 해시값은 복호화를 할 수 없는지 이해하려면 해시의 정의와 작동 방식을 알아야 한다.
"임의의 길이를 갖는 비트열을 입력으로 받아서 정해진 길이의 비트열을 반환하는 함수"를 해시함수라고 한다. 예를 들어 아래와 같이 이름을 넣었을 때 성을 반환하는 함수는 해시함수이다.
- 강규영 -> 강
- 홍길동 -> 홍
- 이몽룡 -> 이
일단, 해시함수도 함수이기 때문에 입력이 같으면 출력이 같다. 어제 hash("강규영")을 수행한 결과가 "강"이었다면 오늘 hash("강규영")을 수행하도 결과는 "강"이다.
그런데 그 반대의 경우가 항상 성립하지는 않는다. 수학에서의 예를 들자면 와 같은 함수가 있을 때 와 는 둘 다 4이다.
그렇다면 해시함수는?
정의상 모든 해시함수는 치역의 크기(cardinality)가 고정되어 있고 대체로 정의역에 비해 작다. 정의역보다 치역이 작으면 입력값은 다르지만 결과값은 같은 경우가 반드시 생길 수 밖에 없다. 이를 비둘기집 원리(pigeonhole principle)라고 부른다. 비둘기집 수보다 비둘기 개체수가 더 많은 상황에서 비둘기들을 모두 비둘기집에 넣으면 최소한 한 개 이상의 비둘기집에는 최소한 두 마리 이상의 비둘기가 있을 수 밖에 없다. 이 비유에서 비둘기는 정의역, 비둘기집은 치역이다.
위의 이름 해시함수에서 예를 들자면, "강규영"의 해시값도 "강"이지만, "강감찬"의 해시값 또한 "강"이다.
제곱함수에 어떤 값을 넣었을 때 그 결과가 4라는 것을 알더라도, 처음에 넣은 값이 -2였는지 2였는지 알 방법이 없는 것과 마찬가지로, 해시값 "강"으로부터 원래의 값을 복원할 방법은 없다. 해시함수는 정의역과 치역을 1:1로 매핑하지 않으며, 해싱을 하면 정보 자체가 줄어들기 때문이다.
위 예시에서는 -2 혹은 2 중에 하나일테니 상대적으로 찍기가 쉬워 보이는데, 다른 함수를 생각해보자. 예를 들면 나머지(modulo)함수. 어떤 수를 넣으면 그 수를 3으로 나눈 나머지를 반환하는 함수 가 있다. 이 함수에 어떤 수를 넣었더니 결과가 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
'일하다가??' 카테고리의 다른 글
| samba 설정후 마운트시 문제발생할때. (0) | 2017.01.17 |
|---|---|
| OSX : NFS Mount (NFS 마운트) (0) | 2016.10.31 |
| 암호화 알고리즘 종류 (1) | 2016.10.08 |
| Servlet 이란? 서블릿 이란? (4) | 2016.05.12 |
| 자바 어노테이션 (Java Annotation) (0) | 2016.04.30 |
댓글