"MD5"의 두 판 사이의 차이

위키원
이동: 둘러보기, 검색
(알고리즘 구현)
27번째 줄: 27번째 줄:
 
==알고리즘 구현==
 
==알고리즘 구현==
 
* Step1 : Append Padding Bits
 
* Step1 : Append Padding Bits
입력받은 메시지의 길이가 512비트의 배수가 되게 [[패딩]]해야 하지만 첫 번째 단계에서는 512비트의 배수보다 64비트 모자라게(-64bit) 패딩해야 한다. 이때 마이너스 해 준 64비트는 패딩 전의 원래의 서명문 길이를 의미한다.
+
: 입력받은 메시지의 길이가 512비트의 배수가 되게 [[패딩]]해야 하지만 첫 번째 단계에서는 512비트의 배수보다 64비트 모자라게(-64bit) 패딩해야 한다. 이때 마이너스 해 준 64비트는 패딩 전의 원래의 서명문 길이를 의미한다.
  
 
* Step2 : Append Length
 
* Step2 : Append Length
Step1에서 제외시켰던 64비트를 채워준다. 패딩 전의 원래의 서명문 길이를 64비트로 표시하여 붙여준다. 이때 메시지의 길이가 2^64보다 클 경우, 낮은 64비트만 사용된다. 패딩이 완료되었다면 완료된 메시지를 16word단위로 M[0,,,,,,N-1]에 할당시킨다. 이때 M은 워드 단위를 의미하고, N은 16의 배수가 된다.
+
: Step1에서 제외시켰던 64비트를 채워준다. 패딩 전의 원래의 서명문 길이를 64비트로 표시하여 붙여준다. 이때 메시지의 길이가 2^64보다 클 경우, 낮은 64비트만 사용된다. 패딩이 완료되었다면 완료된 메시지를 16word단위로 M[0,,,,,,N-1]에 할당시킨다. 이때 M은 워드 단위를 의미하고, N은 16의 배수가 된다.
  
 
* Step3 : Initialize MD Buffer
 
* Step3 : Initialize MD Buffer
MD 버퍼를 초기화한다. 128비트 버퍼는 해시 함수의 중간 값 그리고 최종 값을 저장할 때 쓰여지는데, 32비트의 레지스터 A, B, C, D로 표시한다. 메모리에 저장 시 MD5는 [[Little-endian]] 방식을 사용하길 규정하기 때문에 low order bytes를 먼저 저장해야 한다.
+
: MD 버퍼를 초기화한다. 128비트 버퍼는 해시 함수의 중간 값 그리고 최종 값을 저장할 때 쓰여지는데, 32비트의 레지스터 A, B, C, D로 표시한다. 메모리에 저장 시 MD5는 [[Little-endian]] 방식을 사용하길 규정하기 때문에 low order bytes를 먼저 저장해야 한다.
 
초기화한 형태는 이러하다.
 
초기화한 형태는 이러하다.
 
  word A: 01 23 45 67
 
  word A: 01 23 45 67
41번째 줄: 41번째 줄:
  
 
* Step4 : Process Message in 16-Word Blocks===
 
* Step4 : Process Message in 16-Word Blocks===
16 word(512bit) block 단위로 Message Disgest를 수행한다.
+
: 16 word(512bit) block 단위로 Message Disgest를 수행한다.
4라운드에 걸쳐 작업하는데
+
: 4라운드에 걸쳐 작업하는데
 
  '''1Round''' F(x,y,z) == (x∧y)∨(~x∧z)
 
  '''1Round''' F(x,y,z) == (x∧y)∨(~x∧z)
 
  '''2Round''' F(x,y,z) == (x∧z)∨(y∧~z)
 
  '''2Round''' F(x,y,z) == (x∧z)∨(y∧~z)
48번째 줄: 48번째 줄:
 
  '''4Round''' F(x,y,z) == y⊕(x∧~z)
 
  '''4Round''' F(x,y,z) == y⊕(x∧~z)
 
  (∧,∨,~,⊕는 논리 연산자이다. )
 
  (∧,∨,~,⊕는 논리 연산자이다. )
이러한 형태의 함수로 3개의 32비트 워드(x, y, z)를 입력하여 32비트 워드의 출력을 생성하도록 정의한다.
+
: 이러한 형태의 함수로 3개의 32비트 워드(x, y, z)를 입력하여 32비트 워드의 출력을 생성하도록 정의한다. 각각의 라운드마다 16단계의 처리를 하는데, 4번의 라운드의 구조는 비슷하나 서로 다른 논리 함수로 구성된다. 각 라운드는 현재의 512비트 블록과 128비트 버퍼값인 A, B, C, D, 입력 메시지의 i번째의 32비트 내용의 입력으로 처리되는데 입력 메시지의 i번째의 32비트 내용은 총 64개로 1/4씩 각각의 라운드마다 입력된다.
각각의 라운드마다 16단계의 처리를 하는데, 4번의 라운드의 구조는 비슷하나 서로 다른 논리 함수로 구성된다. 각 라운드는 현재의 512비트 블록과 128비트 버퍼값인 A, B, C, D, 입력 메시지의 i번째의 32비트 내용의 입력으로 처리되는데 입력 메시지의 i번째의 32비트 내용은 총 64개로 1/4씩 각각의 라운드마다 입력된다.
 
  
 
* Step5 : Output
 
* Step5 : Output
4번의 과정을 통해 나온 A, B, C, D의 값을 연결해 준다. 이때 A, B, C, D는 word이며 결과적으로 출력은 128bit(16byte)가 된다.
+
: 4번의 과정을 통해 나온 A, B, C, D의 값을 연결해 준다. 이때 A, B, C, D는 word이며 결과적으로 출력은 128bit(16byte)가 된다.
 
앞서 말했듯 [[Little-endian]]방식의 사용을 규정하기 때문에 low order bytes 순서대로 저장되어야 하며 ABCD의 순서 역시 어긋나면 안 된다.<ref name="Message Digest Algorithm: MD5> Dr Vikas Thada,〈[https://www.youtube.com/watch?v=-uRpRMpvdm0 ]〉, 2018-04-24 </ref> <ref name="MD5 알고리즘"> kimsumin75,〈[https://kimsumin75.blog.me/20056897254 ]〉, 2018-11-11</ref>
 
앞서 말했듯 [[Little-endian]]방식의 사용을 규정하기 때문에 low order bytes 순서대로 저장되어야 하며 ABCD의 순서 역시 어긋나면 안 된다.<ref name="Message Digest Algorithm: MD5> Dr Vikas Thada,〈[https://www.youtube.com/watch?v=-uRpRMpvdm0 ]〉, 2018-04-24 </ref> <ref name="MD5 알고리즘"> kimsumin75,〈[https://kimsumin75.blog.me/20056897254 ]〉, 2018-11-11</ref>
  

2019년 7월 2일 (화) 17:33 판

MD5(message digest 5)는 입력 데이터로부터 128 비트 메시지 축약을 만듦으로써 데이터 무결성을 검증하는데 사용되는 알고리즘이다.[1] 프로그램이 수정되었는지, 원본과 같은지를 확인하는 무결성 검사에 사용된다. 입력받은 메시지를 128비트로 압축하는 방식이며, 이전 버전으로는 MD2, MD4가 있다. 현재에는 1996년에 보안상의 결함이 발견되어 보안용으로 쓰는 것은 권장하지 않는다.

개요

MD5는 미국 MIT의 교수 로날드 리베스트(Ronald Rivest)가 개발한 전자서명, 응용 프로그램 등 정보보호를 목적으로 개발한 해시 알고리즘이다. 큰 파일들은 RSA와 같은 공개키 암호 사용법하에서 개인키와 함께 암호화되기 전에 안전한 방법으로 압축되어야만 한다. MD5 규격은 현재 IETF RFC 1321에 명시되어 있다. MD5 규격에 따르면, MD5 알고리즘에 입력된 어떤 두 개의 메시지가 동일한 메시지 축약을 결과로 내거나, 또는 어떤 메시지 축약을 통해 엉뚱한 메시지가 만들어지는 것은 "계산적으로 불가능"하다고 한다. [2]

등장배경

1991년 미국 MIT의 교수 로날드 리베스트가 이전 버전인 MD4의 결함을 보안하기 위해 개발했다.

특징

  • 임의의 길이로 입력받은 메시지를 512비트 단위로 처리해 128비트로 암호화한다.
  • 입력 메시지의 길이 제한이 없다.
  • 해시값 길이 : 128 비트
  • 패딩 처리 : 메시지 길이를 512 비트 정수배로 만든다
  • 해싱 충돌 방지 확률 : 약 2^64 [3]

비교

MD2

미국 MIT의 교수 로날드 리베스트가 만든 MD2는 8비트 컴퓨터에 최적화되어있는 반면 MD5는 32비트 컴퓨터에 최적화되어있다.

MD4

MD4는 3라운드에 걸쳐 처리하지만 MD5는 4라운드에 걸쳐 처리한다. MD4보다 MD5가 더 느리지만 더 안정적이다.

SHA-1

SHA-1로널드 리베스트가 개발한 MD 해시 함수와 비슷한 방법을 사용하지만 SHA-1이 MD5보다 속도가 더 빠르며 더 안정적이다.

알고리즘 구현

  • Step1 : Append Padding Bits
입력받은 메시지의 길이가 512비트의 배수가 되게 패딩해야 하지만 첫 번째 단계에서는 512비트의 배수보다 64비트 모자라게(-64bit) 패딩해야 한다. 이때 마이너스 해 준 64비트는 패딩 전의 원래의 서명문 길이를 의미한다.
  • Step2 : Append Length
Step1에서 제외시켰던 64비트를 채워준다. 패딩 전의 원래의 서명문 길이를 64비트로 표시하여 붙여준다. 이때 메시지의 길이가 2^64보다 클 경우, 낮은 64비트만 사용된다. 패딩이 완료되었다면 완료된 메시지를 16word단위로 M[0,,,,,,N-1]에 할당시킨다. 이때 M은 워드 단위를 의미하고, N은 16의 배수가 된다.
  • Step3 : Initialize MD Buffer
MD 버퍼를 초기화한다. 128비트 버퍼는 해시 함수의 중간 값 그리고 최종 값을 저장할 때 쓰여지는데, 32비트의 레지스터 A, B, C, D로 표시한다. 메모리에 저장 시 MD5는 Little-endian 방식을 사용하길 규정하기 때문에 low order bytes를 먼저 저장해야 한다.

초기화한 형태는 이러하다.

word A: 01 23 45 67
word B: 89 AB CD EF
word C: FE DC BA 98
word D: 76 54 32 10
  • Step4 : Process Message in 16-Word Blocks===
16 word(512bit) block 단위로 Message Disgest를 수행한다.
4라운드에 걸쳐 작업하는데
1Round F(x,y,z) == (x∧y)∨(~x∧z)
2Round F(x,y,z) == (x∧z)∨(y∧~z)
3Round F(x,y,z) == x⊕y⊕z
4Round F(x,y,z) == y⊕(x∧~z)
(∧,∨,~,⊕는 논리 연산자이다. )
이러한 형태의 함수로 3개의 32비트 워드(x, y, z)를 입력하여 32비트 워드의 출력을 생성하도록 정의한다. 각각의 라운드마다 16단계의 처리를 하는데, 4번의 라운드의 구조는 비슷하나 서로 다른 논리 함수로 구성된다. 각 라운드는 현재의 512비트 블록과 128비트 버퍼값인 A, B, C, D, 입력 메시지의 i번째의 32비트 내용의 입력으로 처리되는데 입력 메시지의 i번째의 32비트 내용은 총 64개로 1/4씩 각각의 라운드마다 입력된다.
  • Step5 : Output
4번의 과정을 통해 나온 A, B, C, D의 값을 연결해 준다. 이때 A, B, C, D는 word이며 결과적으로 출력은 128bit(16byte)가 된다.

앞서 말했듯 Little-endian방식의 사용을 규정하기 때문에 low order bytes 순서대로 저장되어야 하며 ABCD의 순서 역시 어긋나면 안 된다.[4] [5]

문제점

MD5는 원래 공인인증서, MySQL, DB Password 알고리즘 등 다방면에서 사용됐으나 암호화의 방식이 MD5라는 것을 안다면 복호화가 쉽다는 문제점이 있다. 2008년 독일 베를린에서 개최된 해커 컨퍼런스 Chaos communication Congress에서 국제 보안 연구팀이 MD5를 이용한 피싱 공격 기술에 관해 발표했으며 SSL의 인증서 변조가 가능한 것이 발표되었다. [6]

각주

  1. 제3장 DBMS_CRYPTO〉, 《데이터 전문가 지식포털》
  2. MD5, MD-5, MD4, MD-4 Message Digest 5, Message Digest 4〉, 《정보통신기술용어해설》, 2016-04-04
  3. MD5, MD-5, MD4, MD-4 Message Digest 5, Message Digest 4〉, 《정보통신기술용어해설》, 2016-04-04
  4. Dr Vikas Thada,〈[1]〉, 2018-04-24
  5. kimsumin75,〈[2]〉, 2018-11-11
  6. https://eprint.iacr.org/2005/067

참고자료

같이 보기