MD5

위키백과 ― 우리 모두의 백과사전.

암호학에서 MD5(Message-Digest algorithm 5)는 128비트 해시를 제공하는 많이 사용되는 암호화 해시 함수이다. RFC 1321로 지정되어 있으며 많은 프로그램 및 파일의 무결성 검사에 사용된다.

1991년 로널드 라이베스트가 처음 고안했다. 예전의 MD4를 대체하기 위해 나왔다. 1996년 MD5의 설계상 결함이 발견되었다. 매우 치명적인 결함은 아니었지만, 암호학자들은 SHA-1 같은 다른 알고리즘을 사용할 것을 권장하기 시작했다. 2004년에는 더욱 심한 암호화 결함[1]이 발견되었고 2006년에는 노트북 컴퓨터 한 대의 계산 능력으로 1 분 내에 해시 충돌을 찾을 정도로 빠른 알고리즘이 발표[2] 되기도 하였다. 사람들은 MD5 알고리즘을 보안 관련 용도로 쓰는 것을 다분히 권장하고 있지 않다.

[편집] 알고리즘

그림 1. 단일 MD5 연산 - MD5는 이러한 연산 64개로 이루어진다. 16개의 연산을 그룹화한 4 라운드로 묶인다. F는 비선형 함수이다; 한 개의 펑션이 각 라운드에 각각 사용된다. Mi는 입력 메시지의 32-비트 블록을 말한다. s는 s칸 만큼의 레프트 로테이션을 말한다; s는 각 연산 후 값이 변한다.  은 모듈로 232 덧셈을 말한다.
그림 1. 단일 MD5 연산 - MD5는 이러한 연산 64개로 이루어진다. 16개의 연산을 그룹화한 4 라운드로 묶인다. F는 비선형 함수이다; 한 개의 펑션이 각 라운드에 각각 사용된다. Mi는 입력 메시지의 32-비트 블록을 말한다.

left shifts는 s칸 만큼의 레프트 로테이션을 말한다; s는 각 연산 후 값이 변한다. Addition 은 모듈로 232 덧셈을 말한다.

MD5는 임의의 길이의 메시지(variable-length message)를 입력받아, 128bit 짜리 고정 길이의 출력값을 낸다. 입력 메시지는 512-bit짜리 블록들로 쪼개진다; 메시지를 우선 패딩하어 512로 나누어 떨어질 수 있는 길이가 되게 한다. 패딩은 다음과 같이 한다: 우선 첫 단일 비트, 1을 메시지 끝부분에 추가한다. 512의 배수의 길이보다 64 bit가 적은 곳까지 0으로 채운다. 나머지 64 bit는 최초의(오리지날) 메시지의 길이를 나타내는 64-bit 짜리 정수(integer)값으로 채워진다.

메인 MD5 알고리즘은 A,B,C,D라고 이름이 붙은 32-bit 짜리 워드 네 개로 이루어진 하나의 128-bit 스테이트(state)에 대해 동작한다. A,B,C,D는 소정의 상수값으로 초기화된다. 메인 MD5 알고리즘은 각각의 512-bit 짜리 입력 메시지 블록에 대해 차례로 동작한다. 각 512-bit 짜리 입력 메시지 블록을 처리하고 나면 128-bit 스테이트(state)의 값이 변하게 된다.

하나의 메시지 블록을 처리하는 것은 4 단계로 나뉜다. 한 단계를 "라운드"(round)라고 부른다; 각 라운드는 비선형 함수 F, 모듈라 덧셈, 레프트 로테이션(left rotation)에 기반한 16개의 동일 연산(similar operations)으로 이루어져 있다. 오른쪽 "그림 1"은 한 라운드에서 이루어지는 한 연산(operation)을 묘사하고 있다.

함수 F에는 4가지가 있다; 각 라운드마다 각각 다른 F가 쓰인다:

F(X,Y,Z) = (X\wedge{Y}) \vee (\neg{X} \wedge{Z})
G(X,Y,Z) = (X\wedge{Z}) \vee (Y \wedge \neg{Z})
H(X,Y,Z) = X \oplus Y \oplus Z
I(X,Y,Z) = Y \oplus (X \vee \neg{Z})

\oplus, \wedge, \vee, \neg는 각각 XOR, 논리곱, 논리합 그리고 NOT 연산을 의미한다.

[편집] 슈도코드

MD5 알고리즘의 슈도코드는 다음과 같다:

//Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating
var int[64] r, k

//r specifies the per-round shift amounts
r[ 0..15] := {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22} 
r[16..31] := {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
r[32..47] := {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
r[48..63] := {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}

//Use binary integer part of the sines of integers as constants:
for i from 0 to 63
    k[i] := floor(abs(sin(i + 1)) × (2 pow 32))

//Initialize variables:
var int h0 := 0x67452301
var int h1 := 0xEFCDAB89
var int h2 := 0x98BADCFE
var int h3 := 0x10325476

//Pre-processing:
append "1" bit to message
append "0" bits until message length in bits ≡ 448 (mod 512)
append bit (bit, not byte) length of unpadded message as 64-bit little-endian integer to message

//Process the message in successive 512-bit chunks:
for each 512-bit chunk of message
    break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15

    //Initialize hash value for this chunk:
    var int a := h0
    var int b := h1
    var int c := h2
    var int d := h3

    //Main loop:
    for i from 0 to 63
        if 0 ≤ i ≤ 15 then
            f := (b and c) or ((not b) and d)
            g := i
        else if 16 ≤ i ≤ 31
            f := (d and b) or ((not d) and c)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            f := b xor c xor d
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            f := c xor (b or (not d))
            g := (7×i) mod 16
 
        temp := d
        d := c
        c := b
        b := b + leftrotate((a + f + k[i] + w[g]) , r[i])
        a := temp

    //Add this chunk's hash to result so far:
    h0 := h0 + a
    h1 := h1 + b 
    h2 := h2 + c
    h3 := h3 + d

var int digest := h0 append h1 append h2 append h3 //(expressed as little-endian)
  //leftrotate function definition
  leftrotate (x, c) 
      return (x << c) or (x >> (32-c)); 


주석: RFC 1321에 나온 공식 말고 다음과 같은 공식이 쓰일 수 있다. 다음과 같은 공식을 쓰면 퍼포먼스가 향상될 수 있다. (어셈블리 언어가 사용될 때 유용하다 - 다른 언어가 쓰일 경우에는 대개 컴파일러가 위의 코드를 최적화 해준다.):

(0  ≤ i ≤ 15): f := d xor (b and (c xor d))
(16 ≤ i ≤ 31): f := c xor (d and (b xor c))


이 문서는 암호학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.