해시함수와 응용

일방향 해시함수

  1. 일방향 해시함수의 개요
    • 기본 개념
      • 일방향 해시함수(one-way hash function)에는 입력으로 메시지(message)와 출력으로 해시값(hash value)가 각각 1개씩 있다.
      • 일방향 해시함수는 어떤 메시지든 간에 단지 비트열로 취급하며 그 비트열을 기초로 해시값을 계산한다.
    • 일방향 해시함수의 성질
      • 임의 길이의 메시지로부터 고정 길이의 해시값을 계산한다.
      • 해시값을 고속으로 계산할 수 있다.
      • 일방향성을 갖는다.
        • 일방향성이란 해시값으로부터 메시지를 역산할 수 없는 성질이다.
      • 메시지가 다르면 해시값도 다르다.
        • 메시지가 1비트라도 다르면 해시값은 매우 높은 확률로 달라야 한다.
        • 2개의 다른 메시지가 같은 해시값을 갖는 것을 충돌(collision)이라고 한다.
        • 충돌을 발견하기 어려운 성질을 충돌 내성(collision resistance)라고 하며 충돌 내성을 가져야 해시함수를 무결성 확인에 사용할 수 있다.
  2. 메시지 무결성
    • 무결성 점검
      • 암호학적 해시함수를 사용하여 이전의 해시값(메시지 다이제스트)와 새로운 해시값(메시지 다이제스트)가 동일하다면 메시지가 변경되지 않았다는 메시지의 무결성을 확인할 수 있다.
    • 암호학적 해시함수 기준
      • 프리이미지 저항성(preimage resistance), 역상 저항성
        • 프리이미지 저항성이란 주어진 해시함수 h와 해시값에 대응하는 메시지를 찾아내는 것이 매우 힘들어야 하는 성질이다.
      • 제2프리이미지 저항성(second preimage resistance), 두 번째 역상 저항성, 약한 충돌 내성
        • 제2프리이미지 저항성이란 주어진 메시지와 해시값에 대해 동일한 해시값을 가지는 메시지를 찾아내는 것이 매우 힘들어야 하는 성질이다.
      • 충돌 저항성(collision resistance), 강한 충돌 내성
        • 충돌 저항성이란 같은 해시값을 가지는 2개의 메시지를 찾는 것이 매우 힘들어야 하는 성질이다.
    • 전자서명에 이용되는 해시 함수의 특성
      • 해시 값을 고속으로 계산할 수 있다.
      • 약 일방향성(Weak onewayness)
        • 해시값이 될 수 있는 메시지를 찾는 것이 계산상 불가능해야 한다.
      • 강 일방향성(Strong onewayness)
        • 주어진 메시지와 해시값에 대해서 동일한 해시값을 가지는 메시지를 찾는 것이 계산상 불가능해야 한다.
      • 충돌 회피성(collision freeness)
        • 해시값이 동일한 2개의 메시지를 찾는 것이 계산상 불가능해야 한다.
  3. 일방향 해시함수의 응용
    • 소프트웨어 변경 검출
      • 소프트웨어의 해시값을 비교해 원본 소프트웨어가 변조되었는지 검사한다.
    • 패스워드를 기초로 한 암호화(PBE, password based encryption)
      • PBE에서 패스워드와 솔트(의사난수 생성기로 생성한 랜던 값)을 섞은 결과의 해시값을 암호화키로 사용한다.
      • 패스워드에 대한 사전공격(Dictionary attack)을 막을 수 있다.
    • 메시지 인증코드
      • 메시지 인증코드란 송신자와 수시자만이 공유하고 있는 키와 메시지를 혼합해서 생성한 해시값을 말한다.
      • SSL/TLS 에서 이용된다.
    • 전자서명
      • 전자서명이란 현실 사회의 서명이나 날인에 해당하는 행위를 디지털 세계로 가져온 것이다.
    • 전자입찰 시스템
      • 독립성 : 전자입찰 시스템의 각 구성요소들은 자신들의 독자적인 자율성을 보장받아야 한다.
      • 비밀성 : 네트워크상에서 개별 정보는 각 구성요소 간에 누구에게도 노출되어서는 안 된다.
      • 무결성 : 입찰 시 입찰자 자신의 정보를 확인 가능하게 함으로써 누락 및 변조 여부를 확인할 수 있어야 한다.
      • 공평성 : 입찰이 수행될 때 모든 정보는 공개되어야 한다.
      • 안전성 : 각 입찰 참여자 간의 공모는 방지되어야 하고 입찰 공고자와 서버의 독단이 발생해서는 안 된다.
  4. 랜덤 오라클모델과 해시함수에 대한 공격
    • 랜덤 오라클 모델
      • Bellare와 Rogaway가 1993년에 소개한 랜덤 오라클 모델(Random Oracle Model)은 해시함수에 대한 이상적인 수학적 모델이다.
      • 비둘기집 원리
        • n+1마리의 비둘기가 n개의 비둘기집에 들어가 있다면 적어도 한 집에는 두 마리의 비둘기가 들어있다는 뜻이다.
      • 생일 문제(생일 공격)
        • 생일 공격(birthday paradox)은 일방향 해시함수의 강한 충돌 내성을 깨고자 하는 공격이다
        • 생일 패러독스는 랜덤으로 선택한 N명 중 2명의 생일이 일치할 확률이 1/2 이상이 되도록 하기 위해서는 최저 23명만 있어도 되는 점처럼 적은 수로 매우 높은 확률을 가지는 것을 말한다.
    • 일방향 해시함수에 대한 공격
      • 무차별 공격
        • 약한 충돌 내성을 깨고자 하는 공격으로 SHA-1의 경우 해시값이 160비트 이므로 2^160회 시행하면 원하는 메시지가 발견될 것이라고 기대할 수 잇다.
      • 일치블록 연쇄공격
        • 새로운 메시지에 대한 해시값을 다양하게 만들어 놓았다가 공격하고자 하는 메시지의 해시값과 같은 해시값을 갖는 것을 골라 사용하는 공격이다.
      • 중간자 연쇄공격
        • 전체 해시값이 아니라 해시 중간의 결과에 대한 충돌쌍을 찾는다.
      • 고정점 연쇄공격
        • 압축함수에서 고정점이란 연쇄변수가 발생하는 특정한 점에서 임의의 수의 동등한 블록을 메시지 중간에 삽입해도 전체 해시값이 변하지 않는 것을 이용한 공격이다.
      • 차분 연쇄공격
        • 다중 라운드 블록암호 공격에서 입력값과 출력값의 차이의 통계적 특성을 조사하는 기법을 사용한다.
    • 일방향 해시함수로 해결할 수 없는 문제
      • 조작과 변경을 검출할 수 있지만 거짓행세(부인방지)를 검출하지 못한다.
      • 파일의 무결성을 검사하는 것뿐만아니라 파일의 소유자를 확인하고 싶을 떄는 인증이라는 절차가 필요하다.
      • 인증을 수행하기 위해서는 메시지 인증코드와 전자서명이 사용된다.

암호학적 해시함수의 예

  1. 개요

    • 압축함수의 두 가지 유형

      • 압축함수를 아무런 기초 없이 처음부터 새로 만드는 것인데 목적에 맞추어 특별하게 제작한다.
      • 압축함수 자리에 대칭키 블록암호를 사용하는 것이다.

    • 새로 만드는 해시함수

      • 메시지 다이제스트(Message Digest)(MD2 -> MD4 -> MD5)

        • 공개키 기반 구조를 만들기 위해 Rivert에 의해 RSA와 함께 개발되었다.
        • MD5는 메시지를 512비트로 된 블록들로 나누고 128비트의 다이제스트를 출력하는데 128비트 다이제스트는 충돌 공격에 내성을 갖기 어렵다.

      • SHA(Secure Hash Algorithm)

        • SHA는 안전 해시 알고리즘(SHA, secure hash Algorithm)이다.

        • SHA-1은 강한 충돌 내성이 깨졌기 때문에 SHA-3를 이용한다.

          구분 SHA-1 SHA-224 SHA-256 SHA-384 SHA-512
          MD 길이 160 224 256 384 512
          최대 메시지 길이 2^64 - 1 2^64 - 1 2^64 - 1 2^128 - 1 2^128 - 1
          블록 길이 512 512 512 1024 1024
          워드 길이 32 32 32 64 64
          단계수 80 64 64 80 80

      • RIPEMD(Race Integrity Primitives Evaluation Message Digest)

        • 여러 길이의 메시지 다이제스트를 생성하는 해시 알고리즘

      • HAVAL

        • 128, 160, 192, 224, 및 256 비트의 메시지 다이제시트를 생성하는 해시 알고리즘

      • HAS160(Hash Function Algorithm Standard 160)

        • 한국형 전자서명 표준(KCDSA)에서 사용할 목적으로 개발된 160비트 메시지 다이제스트를 생성하는 해시 알고리즘이며 Little endian 구조로 이루어져 있다.

    • 블록암호 기반 해시함수

      • 반복 암호학적 해시함수 안에 사용되는 압축함수 대신에 검증된 DES나 AES 같은 대칭키 알고리즘을 일방향 함수처럼 사용하는 해시함수 알고리즘

  2. SHA-512

    • SHA-512는 다중-블록 메시지로부터 512비트 다이제스트를 생성하며 각 블록은 1024비트 길이를 가진다.
    • 메시지 다이제스트를 생성하기 전에 메시지의 끝에 128비트의 부호없는 정수 길이 필드를 추가한다.
    • 128비트의 부호 없는 정수부호 필드에는 메시지의 길이가 적히게 되는데, 따라서 메시지의 최대 길이는 2^128 - 1이다.

메시지 인증코드(MAC)

  1. MAC의 개요
    • 메시지 인증(데이터 출원 인증)을 위해 메시지 인증코드(MAC, message authentication code)를 사용한다. 송수신자간의 공유키와 임의의 메시지로부터 고정 비트길이의 출력을 계산하는 함수이며, 이 결과물을 MAC이라 하고 인증에 사용한다.
    • 변경 감지 코드(MDC, modification detection code)
      • 변경감지 코드는 메시지의 무결성을 보장하는 메시지 다이제스트이다. 수신한 메시지의 MDC와 수신받은 MDC가 같으면 메시지가 변경되지 않았음을 뜻한다.
    • 메시지 인증 코드(MAC)
      • 메시지의 무결성은 송신자가 메시지의 원래 전송자이며 다른 사람이 송신자를 대신하여 메시지를 보낸 것이 아니라는 것을 말해주는 데이터 출원지 인증을 보장하기 위한 방법이다.
      • MDC와의 차이점은 송수신간의 공유하는 비밀키가 관여한다는 점이다.
    • MAC의 키 배송 문제
      • 대칭키 암호 떄의 키 배송 문제와 같이 송수신자간의 키 공유필요성이 문제가 된다.
  2. MAC의 구현 사례
    • 축소 MAC(nested MAC)
      • 키와 메시지를 해시하여 나온 메시지 다이제스트에 다시 키를 붙여 두번쨰 메시지 다이제스트를 MAC으로 사용하는 방법이다.
    • HMAC
      • H는 Hash를 의미하며, 일방향 해시함수를 이용하여 메시지 인증코드를 구성하는 방법이다.
    • CMAC(Cipher-based Message Authentication Code)
      • 암호 블록체인(CBC)모드와 유사하지만 마지막 암호 블록 n-bit를 CMAC으로 이용하는 방법이다.
  3. MAC의 이용 예
    • IPSec
      • IPSec은 IP(Internet Protocol)에 보안 기능을 추가한 것으로 통신 내용의 인증과 무결성 확인을 위해 MAC을 이용한다.
    • SSL/TLS
      • 통신내용의 인증과 무결성확인을 위해 MAC을 이용한다.
  4. MAC에 대한 공격
    • 재전송 공격, 리플레이 공격
      • 메시지와 그에 해당하는 메시지 다이제스트를 반복해서 보내는 공격을 뜻한다.
      • 순서 번호(sequence number)를 붙여 순서번호가 포함된 MAC을 계산하지 못하도록 하여 방지한다.
      • 타임스탬프(timestamp)를 추가하여 MAC값이 바르더라도 시간이 맞지않다면 오류라고 판단하여 방지한다.
      • 비표(nonce)라는 일회용 랜던한 값을 포함하여 MAC값을 계산하게 하여 재전송 공격을 방지한다.
  5. MAC으로 해결할 수 없는 문제
    • 제3자에 대한 증명
      • 송수신자간에는 공유하는 비밀키를 가지고 MAC값을 통해 인증을 할 수 있지만 제 3자에게는 전자서명을 통해서만 인증이 가능하다.
    • 부인방지(nonrepudiation)
      • MAC에서는 송수신에 대한 부인(repudiation)을 확인할 수 없기에 전자서명을 통해 부인방지가 가능하다.

메시지 인증

  1. 개요
    • 메시지 인증은 관용 암호화 방식, 공개키 암호화 방식, 해시 함수, MAC을 통해 송수신되는 메시지 내용 변경, 순서 변경, 삭제 및 훼손 등 불법행위에 대해서 확인하는 기술이다.
  2. 메시지 인증 방법
    • 관용(대칭키) 암호방식을 이용한 메시지 인증 방식
      • 송수신자간의 공유하는 비밀키로 메시지를 암복호화하여 메시지의 변경 여부를 확인하는 방법이다.
    • 공개키 암호화 방식을 이용한 메시지 인증 방식
      • 송신자의 개인키로 평문을 암호화하여 수신자에게 전송하면 수신자는 송신자의 공개키로 복호화하여 인증을 확인하는 방법이다. 누구나 메시지 인증을 확인할 수 있으나 제3자가 송신자를 가장하여 메시지를 전송할 수 없다.
    • 해시 함수를 이용한 메시지 인증 방식
      • 해시 함수(Hash Function)를 이용한 방식으로 메시지 다이제스트를 비교하여 메시지의 무결성을 검사하는 방식이다. 해시 함수는 공개함수이기 떄문에 송수신자간의 비밀 정보를 메시지에 추가하여 무결성을 검사해야한다.
    • MAC을 이용한 메시지 인증 방식
      • MAC(Message Authentication Code)는 관용 암호방식을 이용하여 간단한 무결성 검증 코드를 만들어 메시지에 부가시키는 방법이다.