SHA-1 알고리즘

1. SHA-1이란?
SHA는 미국 NIST에 의해 개발된 SHS(secure hash standard) 내에 정의된 알고리즘이다. SHA-1은 1994년에 발간된 SHA의 개정판으로서, SHA 내에 남아있던 결함들을 수정한 것이다. 이 설계는 Rivest가 개발한 MD4 계열의 해시 함수들과 매우 비슷하다. SHA-1은 ANSI X9.30 표준으로도 정의되어 있다.
이 알고리즘은 길이 264 비트 이하의 메시지를 160 비트 길이의 축약된 메시지로 만들어낸다. 이 알고리즘은 MD5보다는 다소 느리지만, 대규모 메시지 요약들이 폭력적 충돌 및 도치 공격을 받을 때, 좀더 안전하게 지켜준다.

2. 용도
가. 서명문 생성을 위한 해쉬알고리즘
- 현재 발표된 SHA-1 해쉬 알고리즘은 많은 인터넷 보안 프로토콜과 공개키 인증서에도 적용되고 있는 매우 중요한 암호 알고리즘이다. SHA-1 해쉬 알고리즘이 대표적인 인터넷 보안 프로토콜인 IPSec, 안전한 전자메일 보안 표준인 SMIME, 단대단 보안을 제공하는 TSL, 그리고 인증서 기반의 많은 보안 프로토콜에서 암호 프리미티브로 사용되고 있다.


3. 구현소스(JAVA)
/*
* A JavaScript implementation of the Secure Hash Algorithm, SHA-1, as defined
* in FIPS PUB 180-1
* Copyright (C) Paul Johnston 2000 - 2002.
* See http://pajhome.org.uk/site/legal.html for details.
*/

/*
* Convert a 32-bit number to a hex string with ms-byte first
*/
var hex_chr = "0123456789abcdef";
function hex(num)
{
var str = "";
for(var j = 7; j >= 0; j--)
str += hex_chr.charAt((num >> (j * 4)) & 0x0F);
return str;
}

/*
* Convert a string to a sequence of 16-word blocks, stored as an array.
* Append padding bits and the length, as described in the SHA1 standard.
*/
function str2blks_SHA1(str)
{
var nblk = ((str.length + 8) >> 6) + 1;
var blks = new Array(nblk * 16);
for(var i = 0; i < nblk * 16; i++) blks[i] = 0;
for(var i = 0; i < str.length; i++)
blks[i >> 2] |= str.charCodeAt(i) << (24 - (i % 4) * 8);
blks[i >> 2] |= 0x80 << (24 - (i % 4) * 8);
blks[nblk * 16 - 1] = str.length * 8;
return blks;
}

/*
* Add integers, wrapping at 2^32. This uses 16-bit operations internally
* to work around bugs in some JS interpreters.
*/
function safe_add(x, y)
{
var lsw = (x & 0xFFFF) + (y & 0xFFFF);
var msw = (x >> 16) + (y >> 16) + (lsw >> 16);
return (msw << 16) | (lsw & 0xFFFF);
}

/*
* Bitwise rotate a 32-bit number to the left
*/
function rol(num, cnt)
{
return (num << cnt) | (num >>> (32 - cnt));
}

/*
* Perform the appropriate triplet combination function for the current
* iteration
*/
function ft(t, b, c, d)
{
if(t < 20) return (b & c) | ((~b) & d);
if(t < 40) return b ^ c ^ d;
if(t < 60) return (b & c) | (b & d) | (c & d);
return b ^ c ^ d;
}

/*
* Determine the appropriate additive constant for the current iteration
*/
function kt(t)
{
return (t < 20) ? 1518500249 : (t < 40) ? 1859775393 :
(t < 60) ? -1894007588 : -899497514;
}

/*
* Take a string and return the hex representation of its SHA-1.
*/
function calcSHA1(str)
{
var x = str2blks_SHA1(str);
var w = new Array(80);

var a = 1732584193;
var b = -271733879;
var c = -1732584194;
var d = 271733878;
var e = -1009589776;

for(var i = 0; i < x.length; i += 16)
{
var olda = a;
var oldb = b;
var oldc = c;
var oldd = d;
var olde = e;

for(var j = 0; j < 80; j++)
{
if(j < 16) w[j] = x[i + j];
else w[j] = rol(w[j-3] ^ w[j-8] ^ w[j-14] ^ w[j-16], 1);
var t = safe_add(safe_add(rol(a, 5), ft(j, b, c, d)), safe_add(safe_add(e, w[j]), kt(j)));
e = d;
d = c;
c = rol(b, 30);
b = a;
a = t;
}

a = safe_add(a, olda);
b = safe_add(b, oldb);
c = safe_add(c, oldc);
d = safe_add(d, oldd);
e = safe_add(e, olde);
}
return hex(a) +" "+ hex(b) + hex(c) + hex(d) + hex(e);

// return hex(a) + hex(b) + hex(c) + hex(d) + hex(e);
}



4. 하지만
2005년 8월 미국 캘리포니아 산타바바라 대학에서 열린 CRYIPT2005에서 중국의 Wang 박사 등은 160비트 크기의 SHA-1 해쉬 알고리즘에 대한 충돌 탐색 공격에 대한 연구 결과를 발표했다.
SHA-1 해쉬 알고리즘은 깨질 수 있음이 증명되었다.
인터넷 대표 보안 프로토콜인 IPSec, SMIME, TSL, 인증서 기반 프로토콜이 SHA-1 해쉬알고리즘을 기반으로 하고 있어 보안 프로토콜 및 시스템의 재설계가 요구되고 있다.


<출처 - SHA-1 해쉬 함수의 충돌 탐색 공격과 파급효과 '염흥열-한국정보통신기술협회 연속간행물 >