충돌회피성
-
[12] 해시 함수, 메시지 다이제스트2018.12.11
[12] 해시 함수, 메시지 다이제스트
2018. 12. 11. 19:56
반응형
해시 함수는 임의의 길이를 가지고 있는 메시지를 고정된 길이의 값으로 바꾸어주는 함수로서, 이 때 출력되는 고정된 길이의 값을 해시 값 혹은 메시지 다이제스트(message digest)라고 한다. 해시 함수는 단방향으로 일정한 크기의 메시지 다이제스트를 생성한다. 암호 알고리즘에서는 키가 사용되지만, 해시 함수는 키를 사용하지 않으므로 같은 입력에 대해서는 항상 같은 출력이 나오게 된다. 해시 함수를 사용하면 같은 해시 값(해시 값 충돌)을 갖는 두 개의 다른 입력 메시지를 알아내는 것이 불가능하다. 즉, 하나의 해시 값을 가지고 원래의 메시지를 알아낼 수가 없다. 따라서 해시 함수를 이용하면, 데이터 전송 도중에, 송신자 외의 제3자가 데이터를 변조했는지 혹은 메시지가 전송되다가 오류가 생겼는지 탐지해서 무결성을 확보할 수 있다.
이전 글에서 설명했듯이, 공개키 암호 시스템을 이용해서 전자 서명을 제공할 수 있다. 송신자가 본인의 프라이빗키로 서명을 작성해서 보내고, 수신자는 그것을 송신자의 공개키로 복호화해서 서명을 검증함으로서 해당 메시지가 제3자가 아닌 송신자로부터 제대로 온 것을 알 수 있게 된다. 이때, 해시함수가 전자 서명과 함께 사용되면 효율적으로 서명 생성이 가능해진다. 예를 들어, 전체 메시지에 대해서 서명을 하는 경우, 전체 메시지를 공개키 길이의 블록 단위로 나누어서 모든 블록을 서명하게 되면 많은 계산량이 필요해지므로 비효율적이다. 따라서 메시지의 일부를 입력받아 짧은 해시 값을 계산하고 이 해시 값에 대해서 한 번의 서명을 하는 것이다. 이 서명은 원래의 메시지에 대한 서명으로 인정된다. 왜냐하면 같은 해시 값을 갖는 다른 메시지를 찾아내는 것이 매우 어렵기 때문이다. 같은 해시 값을 갖는 다른 메시지를 알아내는 것이 가능하다면 서명자는 자신의 서명에 대해서 다른 메시지에 대한 서명이라고 우길 수 있다. 이렇게 되면 전자 서명의 신뢰도가 떨어지고 사용할 수 없게 된다. 따라서 전자 서명으로 사용 가능한 해시 함수는 해시 충돌을 찾아내기 어려워야한다.
만약 인증이 필요 없고 데이터가 전송 중에 변조되지 않았다는 무결성만 필요할 경우에는 해시 함수 메시지 인증 코드(Message Authentication Code)로 쓸 수 있다. 송신자와 수신자가 동일한 비밀키를 가지고 있고, 송신자가 자신이 보내려는 메시지와 해당 비밀키를 가지고 해시 값을 만들어낸다. 이렇게 만들어진 값이 메시지 인증 코드로 사용된다. 송신자는 메시지와 이 메시지 인증 코드를 함께 보내고, 수신자는 이렇게 받은 메시지를 송신자와 동일한 비밀키와 함께 해시 값을 만들어낸다. 그 결과 값을 송신자가 보낸 메시지 인증 코드와 비교하여 메시지의 무결성을 확인하는 것이다.
해시 함수에는 MD-5, SHA-1, SHA-2 등이 있다. 이 중, MD-5, SHA-1은 보안성이 깨진 해시 함수로서 더 이상 사용 권장이 되지 않는다. 암호학적 해시 함수란, 암호학에서 사용될 수 있는 안전하다고 여겨지는 해시 함수를 의미한다. 다른 것들은 비암호학적 해시 함수라고 칭한다. 암호학적 해시 함수의 필요 조건들이 몇 가지 있다. 먼저 가변 길이의 입력에 대해 일정한 크기의 값을 출력해야 하는 것이다. 또한 어떤 입력 값에 대해서도 해시 값을 구하는데 계산 속도가 빨라야 한다. 그리고 해시 값으로부터 입력 값을 얻어내는 것은 불가해야 한다. 이것을 Computationally infeasible 하다고 한다. 마지막으로 충돌 회피성(collision resistance) 성질을 만족해야 한다. 충돌 회피성에는 약한 충돌 회피성과 강한 충돌 회피성이 있다. 약한 충돌 회피성이란, 입력 값과 해시 값을 알고 있을 때, 동일한 해시 값을 갖는 다른 입력 값을 찾는 것이 불가해야 한다는 것이다. 강한 충돌 회피성이란 동일한 해시 값을 갖는 서로 다른 입력 값 두 개를 찾는 것이 불가해야 한다는 것이다.
해시 함수에는 MD-5, SHA-1, SHA-2 등이 있다. 이 중, MD-5, SHA-1은 보안성이 깨진 해시 함수로서 더 이상 사용 권장이 되지 않는다. 암호학적 해시 함수란, 암호학에서 사용될 수 있는 안전하다고 여겨지는 해시 함수를 의미한다. 다른 것들은 비암호학적 해시 함수라고 칭한다. 암호학적 해시 함수의 필요 조건들이 몇 가지 있다. 먼저 가변 길이의 입력에 대해 일정한 크기의 값을 출력해야 하는 것이다. 또한 어떤 입력 값에 대해서도 해시 값을 구하는데 계산 속도가 빨라야 한다. 그리고 해시 값으로부터 입력 값을 얻어내는 것은 불가해야 한다. 이것을 Computationally infeasible 하다고 한다. 마지막으로 충돌 회피성(collision resistance) 성질을 만족해야 한다. 충돌 회피성에는 약한 충돌 회피성과 강한 충돌 회피성이 있다. 약한 충돌 회피성이란, 입력 값과 해시 값을 알고 있을 때, 동일한 해시 값을 갖는 다른 입력 값을 찾는 것이 불가해야 한다는 것이다. 강한 충돌 회피성이란 동일한 해시 값을 갖는 서로 다른 입력 값 두 개를 찾는 것이 불가해야 한다는 것이다.
반응형
'컴퓨터 · IT > 정보보안기사' 카테고리의 다른 글
| [14] 전자서명, 디지털서명, 공개키 기반 구조(PKI), CA (0) | 2018.12.12 |
|---|---|
| [13] 암호학적 해시 함수 추가 정리 (0) | 2018.12.11 |
| [11] 비대칭키(공개키) 암호 :: RSA, 하이브리드 암호시스템 (0) | 2018.12.10 |
| [10] 비대칭키(공개키) 암호 :: 개요 및 탄생 배경 (0) | 2018.12.10 |
| [9] 암호 분석, 암호 해독, 암호 알고리즘 평가 (0) | 2018.12.09 |