해시 : SHA-1 해시 구조

 

OTP 알고리즘의 동작원리에 대해 기술하려 하였으나,

 

그 속에 HOTP, TOTP, HMAC, 등등 배경지식을 요구하는 것이 많아 글을 분리하여 작성하도록 하였다.

 

이 글은 그 첫번째 OTP의 기본이 되는 HASH 알고리즘을 분석하고자한다.

 

 

HASH는 암호화 기법으로서, 임의의 데이터에 대해 고정된 길이의 데이터로 반환한다.

 

해시는 단방향 알고리즘이다.

 

평문(Plain Text) 에서  암호문(Cipher Text)으로 변환하는 과정은 가능하지만, 암호문에서 평문으로 되돌리는 과정은 어렵다

이러한 특성에 힘입어 다양한 목적에 맞게 설계된 해시 함수가 존재하며 자료구조, 캐시, 중복 레코드 검색, 오류 검출 등 다양한 분야에서 유용하게 사용된다.

 

 

해시함수의 종류로는 MD5, SHA계열 해시함수 등이 있는데, 그중 가장 흔히 사용되는 SHA-1 해시에 대해 알아보고자 한다.

 

 

 

Step 1. Preprocessing

 

임의의 문자열을 입력받아 그 각각의 문자열을 아스키코드 값으로 인코딩후 32비트 단위로 분리한다.

ex) input() = 'Hello Wolrd!' => 48656C6C 6F20576F 6C726421

 

이후 1을 추가하고 남은 자리를 0으로 채워 32비트를 맞춘다.

ex) 48656C6C 6F20576F 6C726421 80000000

 

512로 나누어 떨어질때 까지 0을 채워넣어 패딩한다.

ex) 48656C6C 6F20576F 6C726421 80000000

     00000000 00000000 00000000 00000000

     00000000 00000000 00000000 00000000

 

처음 입력받은 문자열의 길이를 최하위 비트에 더한다.

ex) 'Hello world!' => 12 * 8(bytes) => 96(dec) = 60(hex)

 

     48656C6C 6F20576F 6C726421 80000000

     00000000 00000000 00000000 00000000

     00000000 00000000 00000000 00000060

 

 

아래의 알고리즘으로 위 16 개의 값을 80개로 추가 생성한다.

 

pseudocode)

for i from 16 to 79

    w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

    # w는 위에서 정의한 16개의 헥사 값 배열

 

 

 

Step 2. Main loop

    

SHA-1 해시는 사전의 고정된 값과 k(상수 값) 을 가지고 해싱을 시작한다.

 

a = 0x67452301          
b = 0xEFCDAB89
c = 0x98BADCFE
d = 0x10325476
e = 0xC3D2E1F0

 

pseudocode)

for i from 0 to 79
    if 0 ≤ i ≤ 19 then

        f = (b and c) or ((not b) and d) 

        k = 0x5A827999

    else if 20 ≤ i ≤ 39 
        f = b xor c xor d

        k = 0x6ED9EBA1

    else if 40 ≤ i ≤ 59
        f = (b and c) or (b and d) or (c and d) 
        k = 0x8F1BBCDC

    else if 60 ≤ i ≤ 79
        f = b xor c xor d
        k = 0xCA62C1D6

 

    temp = (a leftrotate 5) + f + e + k + w[i]

    e = d

    d = c

    c = b leftrotate 30

    b = a

    a = temp

 

<<< 는 비트 좌로 순환

 

 

Step 3

해싱이 끝난 이후 사전 정의된 고정 값과 a,b,c,d,e를 각각 더한다.

 

a = 0x67452301 + a           
b = 0xEFCDAB89 + b
c = 0x98BADCFE + c
d = 0x10325476 + d
e = 0xC3D2E1F0 + e

 

이후 a b c d e 를 각각 순서대로 이어 붙여 SHA-1 해시 값을 완성한다.

 

ex)

#만약 a, b, c, d, e 가 아래와 같다면

a = 0X3FF78D6F         h0 + a = 0XA73CB070

b = 0XB8E773D6         h1 + b = 0XA8B51F5F

c = 0X2B3B54DA         h2 + c = 0XC3F631D8

d = 0XA67A6DD6        h3 + d = 0XB6ACC24C

e = 0XC8525823         h4 + e = 0X8C253A13

    

 

hash 값 => A73CB070A8B51F5FC3F631D8B6ACC24C8C253A13

 

 

 

Acknowledge

 

https://ko.wikipedia.org/wiki/SHA#

https://starbirds.tistory.com/11

https://nobilitycat.tistory.com/entry/c-SHA1-%EA%B5%AC%EC%A1%B0-%EB%B0%8F-%EC%BD%94%EB%93%9C

http://www.ktword.co.kr/abbr_view.php?m_temp1=2941

https://chocolate-life.tistory.com/5