일방향 해시함수

• 일방향 해시함수

  • 해시함수는 임의의 길이를 갖는 메시지를 입력으로 하여 고정된 길이의 해시 값 또는 해시 코드라 불리는 값을 출력하는 함수
  • 해시함수 h는 임의의 길이의 문자열을 고정된 길이를 갖는 n비트 문자열로 대응
    • h: D(정의역) -> R(치역) 다대일 대응 함수 (충돌이 반드시 존재함 의미)

• 특징

  • 고정길이의 해시값 계산
  • 해시값 고속 계산
  • 일방향성
  • 메시지에 따라 해시값 달라짐
    • 충돌(collision) : 2개의 다른 메시지가 같은 해시값을 갖는 것
    • 일방향 해시함수를 무결성 확인에 사용하기 위해서는 충돌이 발견되어서는 안됨

• 해시함수의 보안 요구사항

• 해시 값 h = H(x) : x는 함수 H를 사용한 해시함수 결과가 h인 데이터 블록

  • 프리이미지(입력되는 이미지) 저항성(역상 저항성)
    • 어떠한 코드 h에 대해서도 H(x)=h인 x를 찾는 것은 계산적으로 실행 불가능
  • 제2프리이미지 저항성(두 번째 역상 저항성, 약한 충돌 내성)
    • 메시지를 쉽게 위조할 수 없도록 하는 성질
    • 어떠한 블록 x에 대해서도, H(y)=h(x)인 y=/x인 것을 찾는 것이 계산적으로 실행 불가능
  • 충돌 저항성(강한 충돌 내성)
    • 동일한 다이제스트를 가지는 2개의 메시지를 구하지 못하도록 하는 것
    • H(x)=h(y)인 어떤(x,y)짝을 찾는 것이 계산적으로 실행 불가능

• 키가 없는 해시함수

  • 전용함수(새로 만드는 해시함수)
    • 메시지 다이제스트(Message Digest)(MD2 -> MD4 -> MD5)
      • MD5는 메시지를 512비트로 된 블록들로 나누고 128비트 다이제스트 출력
        • 128비트 메시지 다이제스트는 충돌 공격에 내성을 갖기에 길이가 너무 짧다고 알려짐
    • SHA(Secure Hash Algorithm)
      • MD4 모델 기반, MD5보다 조금 느리지만 좀더 안전
  • 블록암호 기반 해시함수
    • 반복 암호학적 해시함수 안에 사용되는 압축함수 자리에 대칭피 블록암호 사용
    • 새로운 압축함수 생성 필요 없이 DES나 AES처럼 검증된 여러 개의 대칭키 알고리즘을 일방향 함수로 사용 가능
  • 모듈 연산에 기반을 둔 해시함수
    • 압축 함수의 기반을 모듈 연산의 반복적인 수행에 두고 있는 해시함수
    • 장점 : 하드웨어나 소프트웨어 자체에 내장된 모듈 연산 사용 가능
    • 단점 : 속도가 빠르지 않고 안전성 연구에 대한 역사가 짧음

• 키를 사용하는 해시함수

  • 메시지 인증 기능을 가진 함수
  • 함수 자체의 안정성과 키의 비밀성에 안전성 둠
  • 블록 암호에 기반을 둔 메시지 인증 알고리즘
    • CBC(Cipher Block Chaining) 모드 이용

메시지 인증코드(MAC)

• 메시지 인증코드(MAC)

  • 무결성을 확인하고 메시지에 대한 인증을 하는 기술
  • 임의 길이의 메시지와 송신자 및 수신자가 공유하는 키라는 2개의 입력을 기초로 해서 고정 비트길이의 출력(MAC 값)을 계산하는 함수
  • 블록 암호나 해시 함수에 기반을 두기 때문에 전자 서명보다 훨씬 빠름

• MAC의 키 배송 문제

  • MAC에서는 송신자와 수신자가 키를 공유할 필요가 있다
  • 송신자와 수신자가 키를 공유할 필요가 있다는 것은 대칭키 암호 때의 키 배송 문제와 같은 문제가 메시지 인증코드에서도 일어남을 의미

• 변경 감지 코드(MDC, Modification Detection Code)

  • 메시지의 무결성을 보장하는 메시지 다이제스트