SHA-1(Secure Hash Algorithm 1) 분석

 이 글은 SHA1의 원리와 소스코드 그리고 충돌, 취약점을 다룬다.

 (충돌 및 취약점은 정리 중 입니다. 완료되는 대로 업데이트 하겠습니다.)

개요

 암호학적 해시 함수로 데이터를 160bit의 해시 값으로 나타낸다. 해시 함수를 간단히 설명하면 서로 다른 데이터로 만든 해시 값 2개가 달라야 한다. 해시 값의 bit 수가 정해져있기 때문에 서로 다를 확률이 0일 수는 없지만, 0에 가깝도록 그리고 공격자가 같은 해시 값이 나오는 서로 다른 문서들을 만들 수 없도록 하는 것이 목적이다. NSA에서 창안하여 만들어진 함수이며 TLS, SSL, SSH, HTTP 인증서, GIT 커밋 등 많은 애플리케이션 및 프로토콜에서 사용 중이다. SHA-1은 1993년 SHA-0가 발표된 후 2년 뒤인 1995년에 취약점을 보완하여 만들었다.(아래 해시 값 생성에서 이 둘의 차이 설명) 하지만 현재 이 둘 모두 취약점 및 충돌이 발표되어 대부분 기업, 단체 등에서 SHA-2, SHA-3를 사용한다.

해시값 생성

 해시값 생성과정 및 코드는 wikipedia SHA-1_pseudocode를 c++로 구현함.

 (전체 소스코드: https://github.com/JangTaeHwan/AlgorithmTraining/blob/master/Mathematical/sha/sha1.cpp)

  ① 초기화

var = 32bit, var64 = 64bit 의미

Data m = 암호화 할 데이터,

var64 ml = m.size()*8; // m의 원래 크기, bit size로 나타냄

// SHA1의 해시 값이 되는 5개의 digest (computer science에서 digest는 output이 되는 해시 값을 의미)

// 초기 값은 아래와 같이 상수로 정해져 있으며 데이터를 읽어가면서 해시 값을 바꾸는 작업을 한다.

var h[DIGEST_NUMS] = {

    0x67452301,

    0xEFCDAB89,

    0x98BADCFE,

    0x10325476,

    0xC3D2E1F0,

};

  ② padding

// m에 '1' 비트 1개 추가 (실제론 0b10000000 추가)

m += (char)0x80;

       // m.size() + ml이 64bytes(512bit)로 나누어 떨어질 때까지 '0'비트를 계속 추가

       // input데이터가 byte단위로 나누어 떨어짐을 가정하고 모든 과정에서 byte단위로 추가 함

m += (char)0x00;

// ml을 big endian 순서로 m에 추가 (실행환경을 little endian로 가정, big endian 환경에서 실행시 0번 index부터 추가)

for (int i=7; i>=0; i--) {

   char byte = (ml >> 8*i) & 0xff;

   m += byte;

}

// 이제 m은 64bytes(512bit)로 나누어 떨어진다.

   ③ 64bytes(512bit)는 m을 chunk로 나누는 기준이며 각각의 chunk데이터는 ④ ~ ⑦ 과정을 반복한다.

   ④ chunk를 16개의 words로 나눈다. 각각의 word는 32bit이다.

// big endian 순서로 data를 읽어온다.

for (unsigned int i = 0; i < WORDS_NUMS; i++) {

    words[i] = (chunk[4*i+3] & 0xff)

               | (chunk[4*i+2] & 0xff)<<8

               | (chunk[4*i+1] & 0xff)<<16

               | (chunk[4*i+0] & 0xff)<<24;

}

   ⑤ 16...79 index words는 아래 식에 따라 순차적으로 채운다.

var word = w[i-3] xor w[i-8] xor w[i-14] xor w[i-16];

word = BYTE_ROTATE_LEFT32(word, 1);

* 여기서 word의 bit들을 한 칸씩 왼쪽으로 옮기는데 이 부분이 SHA0과 SHA1의 차이이다.

   ⑥ main loop

// k값은 h의 초기값과 마찬가지로 정해진 상수 값이다.

var a = h[0];

var b = h[1];

var c = h[2];

var d = h[3];

var e = h[4];

var f, k;

for (unsigned int i = 0; i <= 79; i++) {

    if (0 <= i && i <= 19) {

        f = (b bitand c) bitor (~b bitand d);

        k = 0x5A827999;

    }

    else if (20 <= i && i <= 39) {

        f = b xor c xor d;

        k = 0x6ED9EBA1;

    }

    else if (40 <= i && i <= 59) {

        f = (b bitand c) bitor (b bitand d) bitor (c bitand d);

        k = 0x8F1BBCDC;

    }

    else if (60 <= i && i <= 79) {

        f = b xor c xor d;

        k = 0xCA62C1D6;

    }

    var temp = BYTE_ROTATE_LEFT32(a, 5) + f + e + k + w[i];

    e = d;

    d = c;

    c = BYTE_ROTATE_LEFT32(b, 30);

    b = a;

    a = temp;

}

   ⑦ digest 값에 ⑥에서 구한 값 더하기

h[0] = h[0] + a;

h[1] = h[1] + b;

h[2] = h[2] + c;

h[3] = h[3] + d;

h[4] = h[4] + e;

   ⑧ 최종 해시 값 hh(20bytes, 160bit)는 h[0]부터 h[4]를 나열한 값이다.

충돌

 작업 중...