[암호공학] 12장. Cryptographic Hash Functions.

Keyword : hash function, Merkle-Damgard scheme, two categories of hash functions, SHA-512, Whirlpool

 

1. Introduction

: cryptographic hash function은 임의의 길이를 가진 message를 받아서 고정된 길이의(fixed length) message digest를 생성한다. 이번 챕터의 목표는 두가지의 가장 널리 쓰이는 hash algorithm에 대해 공부하는것이다. 그 둘은

SHA-512과 Whirlpool이다.

 

모든 crryptographic hash function은 고정된 사이즈의 digest를 생성해야 한다. compression function이 n-bit string을 압축해서 m-bits string을 만들어낸다. 이 때, n>m이다. 이 scheme을 iterated cryptographic hash function이라 한다.

 

위는 Merkle-Damgard scheme으로, 다음 step을 따른다.

1. message가 n bits 블록으로 분할될 수 있도록 padding한다.

2. message는 이제 t개의 block으로 분할되었다. 각각의 블럭을 M1,. M2,...Mt라고 하고, 그로부터 생성된 digest H를 H1,H2,...Ht라 한다.

3. iteration을 시작하기 전에, H0은 고정된 값으로, IV라 불린다.(Initial value or initial vectyor)

4. compression function이 H(i-1)과 Mi를 입력받아 새로운 Hi를 내놓는다. 즉, Hi = f(Hi-1, Mi)이다.

5. 마지막 단계에서 Ht는 cryptographic hash function of the original mesage, h(M)이 된다.

 

Compression Function에는 두 가지 종류가 존재한다.

1. Compression function is made from scratch

 : Message Digest(MD) : MD2,MD3,MD5

 MD5는 128 bit digest를 만들어내고, 128 bit digest는 collision attack에 약하다.

 : Secure Hash Algorithm(HSA)

 HSA는 Secure Hash Standard(SHS)라고 불리기도 한다.

2. Symmetric-key block cipher serves as a compression function.

 : Whirlpool

Rabin Scheme은 Merkle-Damgard scheme에 기초해 있다.

DES가 block cipher에 이용될 경우, digest의 크기는 64비트밖에 안된다.

위 scheme은 매우 심플하나, meet-in-the-middle-attack의 대상이 된다.

forward feedback을 추가해서 meet-in-the-middle attack에 저항성을 갖게 한 방식이다.

 

위의 scheme과 매우 유사하나 다른점인 여기서는 메시지 M이 평문이고, H0가 Key가 된다. 이 scheme은 data block과 cipher key가 같은 크기일 때 이용할 수 있다.

위의 scheme의 extended version이다. attack에 더 stronger하다.

 

2.SHA-512 

SHA-512는 512-bit message digest를 생성하는 SHA의 한 버전이다. 이 버전은 Merkle-Damgard scheme이 기초이다.

 

SHA-512는 multiple-block message로부터 512비트 digest를 생성한다. 각각의 message block은 1024비트 길이이다.

digest는 미리 정의된 512bits로 초기화되고, 이 initial value와 첫번째 block을 섞어서 first intermediate message digest of 512bits를 생성한다. 이 digest는 다시 두번째 블록과 mixed되고, 이를 반복해서 N-1번째 digest을 N번째 블록과 섞어 나온 결과가 message digest가 된다.

SHA-512를 할 때는 original message의 길이가 2^128보다 작아야 한다. 허나 2^128은 엄청나게 큰 수기 때문에 보통 문제가 되지 않는다.

message digest가 생성되기 전에, SHA-512는 128-bit unsigned-integer length field를 메시지에 달아줄 필요가 있다. 이 length field는 original message의 길이에 대한 정보를 담고 있다. 이 128비트 값은 0에서 2^128 -1 까지의 값을 저장 가능하다(이는 아까 봤던 SHA-512의 original message 리미트이다.) 블록을 맞춰주기 위해 10000(제일 앞에는 1, 그 뒤는 다 0)으로 패딩할 필요도 있다.

우리는 length field를 달아주기 전에, original message에 padding을 해야 하는데, 이 패딩과 length field의 길이가 총 1024비트가 되어야 한다. 이 padding field는 다음과 같이 계산된다.

(|M|+|P|+128) = 0 mod 1024, |P| = (-|M|-128)mod 1024

이 때 |M|은 original message 길이이고, |P|가 패딩을 얼마나 할지 결정하는 것이다.

예를들어, original message가 2590비트 길이라면, |P| = (-2718) mod 1024 = 354가 된다.

 

SHA-512는 words단위로 실행되며, word oriented이다. word는 64bits로 정의된다.

프로세싱 하기 전, each message block은 expanded되어야 한다. block은 16개의 16-bit words로 이루어져 있고, 우린 80 words가 processing phase에 필요하다. 따라서 16-word block이 80 words로 expanded되어야 한다. (W0부터 W79까지) 위 그림은 Word Expansion process를 보여준다. 1024-bit block이 처음의 16 words가 되고, 그 다음부터 오는 words는 위 연산을 통해 결정된다. 예를들어 W60은 어떻게 계산되냐면,

W60 = W44 + RotShift_(1-8-7) (W45) + W53 + RotShift_(19-61-6) (W58)

이제 Message Digest initalization이 어떻게 이뤄지는지 살펴보자.

Compression은 어떻게 이루어지는가?

compression에서 word 80개를 사용하는 것이었다.

message block은 1024bits이고, 총 80라운드를 거친다.

각각의 round는 8개의 words initial digest가 입력이다.

이 때의 1 words = 64bits, 즉 round는 512bits가 입력이다.

last round를 통과하고 final adding을 통해 initial digest를 수행한다.

그렇다면 이 안의 round에서는 어떤 동작이 일어나는가?

굉장히 복잡하다. A,B,C와 E,F,G는 단순히 한 비트를 오른쪽으로 옮겨주는데, A,E 계산이 복잡하다.

라운드마다 입력되는 word가 아닌 새로운 k라는 key를 이용한다. 80개의 k가 필요하고, k는 다음과 같다.

SHA-512는 resistant to all attacks(including collision attacks)하다고 평가받음.

하지만 more research 및 testing이 필요함.

 

3. WhirlPool

: iterated cryptographic hash function으로, Miyaguchi-Preneel scheme이 basis이다. 대칭 키 블록 암호화방식을 compression function으로 사용하며, 블록 암호화는 modified AES cipher를 쓴다. 

해시 알고리즘을 시작하기 전에 메시지는 preprocessing이 필요하다. whirlpool에서는 original message가 2^256bits보다 작아야 한다. 또한 message는 패딩되어야 하며, padding은 single 1-bit와 followed 0-bits이다. 패딩 이후, 256비트의 블록은 original message의 길이를 정의하고 메시지 마지막에 붙는다.

augment 된 message 크기는 even multiple of 256bits or a multiple of 512 bits이다. whirpool은 512 bits의 block message로부터 512bits의 digest를 생성한다. 512-bit digest, H0는 모두 0으로 initialized된다. 이 값은 첫번째 블록을 암호화하는 암호화 키로 사용된다. 이후 암호화된 암호문들은 이전의 암호 키와 평문과 exclusive OR 된 다음 다음 블럭의 cipher key로 이용된다. message digest는 마지막 512-bit 암호문이 된다.

 

 

Whirlpool cipher는 AES처럼 non-Feistel cipher이다. 여기서는 우리가 AES에 대해 알고 있다고 가정하고 설명한다. Whirlpool 암호화와 AES 암호화를 비교하고 차이점에 대해 설명한다.

1) Rounds : Whirlpool은 10 라운드를 쓰는 round cipher이다. 블록과 키 사이즈는 512bits이며, cipher는 11 round keys를 쓴다(K0~K10). 위 그림은 Whirlpool cipher을 보여준다.

2) States and Blocks : AES처럼, whirlpool cipher는 states와 blocks를 이용한다. 하지만 block or state 의 크기가 512bits이다. 블럭은 row matrix of 64bytes로 간주되고, state는 8*8 bytes의 square matrix로 간주된다. AES와 달리, block-to-sate or state-to-block 변환은 row by row로 행해진다. 아래 그림을 보자.

위 SubBytes 변환에서, state는 8*8 matrix of bytes로 취급된다. 변환은 one byte at a time으로 실행된다. 각각의 byte의 내용은 바뀌나, matrix의 byte 배열은 그대로이다. 이러한 과정을 통해 각각의 byte는 독립적으로 변환된다. 아래의 테이블은 substitution table로 SubBytes transformation에 이용한다.

이 변환은 분명히 confusion effect를 제공한다. 즉, 5A과 5B는 단지 한 비트 차이이지만 5B와 88로 각각 변환되어 5비트가 다르게 된다.

위 그림의 table은 GF(2^4)를 이용하여 대수적으로 계산되었다.(irreducible polynomial : x^4 + x + 1)

위 그림은 Whirlpool cipher에서 subBytes가 어떻게 이루어지는지 보여준다.

shift columns이다. state의 column이 shift column속으로 들어가면 shifting되는데, Column 0이 들어가면 0-byte shifting(no shifting)이 되고, Column 7이 들어가면 7-byte shifting이 이뤄지는 식이다.

이번엔 MixRows단계이다. Mixcolumns transformation in AES와 같은 효과이며, MixRows 변환은 multiplication of bytes in GF(2^8)을 수행한다. AES와는 다르게 modulus (x^8 + x^4 + x^3 + x^2 + 1)을 이용한다. 

Roundkey와 exclusive OR연산을 수행한다.

Key expansion 방식은 AES알고리즘과 다르다. round key를 생성하기 위해 알고리즘을 이용하는 대신, whirlpool에서는 encryption algorithm의 복사본을 쓴다.(without pre-round) 각 round마다의 출력이 roundkey가 되는 것이다. 하지만 Key generation을 할 때의 key는 어떻게 생성하는가?

Key generation할 때의 key는 RC인데, RCs는 key-expansion algorithm에서 가상 키이다. key-expansion 알고리즘은 constants값을 round key로 이용하고 encryption algorithm에서는 각 round의 output을 이용한다. key-generation 알고리즘에서 cipher key를 plaintext로 취급하고 이를 암호화한다. 

이 RC(Round constants)는 어디서 왔는가?

RC1은 SubBytes단계에서의 first eight entries를 이용한다. 

RC2는 SubBytes단계에서의  second eight entries를 이용하고... 다음과 같은 식이다.

위 그림은 RC3의 예제를 보여주는 것이다.

 

Whirlpool cipher의 특징

Block 크기 : 512비트

cipher key size : 512비트

round수 : 10개

Key expansion : cipher itself를 이용해서 round key 생성

Substitution : SubBytes 변환

Permutation : ShiftColumns 변환

Mixing : MixRows 변환

Round constant : cubic roots of the first eighty prime numbers

 

분석

Whirlpool은 아직 많이 연구되고 시험되지는 않았으나 robust scheme(Miyaguchi-Preneel)에 기초해 있으며  compression function이 AES를 쓰기 때문에, very resistant to attack이다.

게다가, size of the message digest가 SHA-512과 같기 때문에, very strong cryptographic hash function으로 평가된다.

whirlpool은 SHA-512만큼 효율적이지 않을 수 있다. 특히 하드웨어에서 구현될 때에는.