SHA-256 프로세스 정리

SHA-256 씨리이즈

 

1. SHA-256 Hash Algorithm 2. SHA-256 프로세스 정리 3. SHA-256 By Hand - Message Expansion Function 4. SHA-256 By Hand - Round Function 5. SHA-256 Bitcoin

잡담

 

그리 똑똑한 머리가 아니라, SHA-256 을 손으로 계산하는게 어렵지만은 않다는 이야기에

시도하다가 막히고, 포기하려다 조금 더볼까를 며칠 반복하였다.

구글링을 해도 한글로 된 자료도 없더라. 추측해본바

 

1) 애써 이거 다 이해할 필요도 없는데 그냥 개념만 이해하고 써먹자는 사람들이 있을꺼고,

2) 휘리릭 이해해버렸는데, (그 사람 입장에서) 이리 쉬운걸 애써 정리할 필요를 못느끼기도 했을거고,

3) (나처럼), 겨우겨우 이해했는데, 지치고 정리까지 할 엄두나 시간이 안나서 안한게 아닐까 싶다.

 

SHA-256 은 구글링에서 나온 다양한 포스팅과 유튜브를 들여다 보면서도

막히는 부분이 많았고, 전체적인 그림을 그리기 쉽지 않았다.

 

풀어나는 방법

 

SHA-256 은 크게 Pre-processing (전처리) 와 실제적인 Algorithm 으로 나뉘는데,

개인적인 판단으로 Algorithm 에서 부터 풀어나가며 중심을 잡고,

곁다리로 필요한 항목을 붙여나가보겠다.

 

* 전체적인 그림을 그리는데는 아래 링크의 그림들이 큰 도움이 되었다.

여기에 올리는 많은 그림들의 출처도 이 링크이다.

 

- 링크: https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml

- 검색해보니 로체스터 공과대학으로 나온다.

 

 

Algorithm

 

함수란 y = f(x) 이다. x 를 넣으면, y 가 나온다.

SHA-256 은 y = f(H, W, K) 이다. H의 초기값은 상수이고, K도 상수이다.

 

 

512 bit 메시지 덩어리

 

나중에 좀더 설명하겠지만,  SHA-256 을 먹일 메시지 M 은 padding 과 parsing 을 거쳐 512 bit의 블록이 되는데,

이 블록 하나당 아래와 같은 연산이 이루어지며, 그 결과는 맨 아래쪽의 Hi+1 (= a, b, c, d, e, f, g, h) 가 된다.

만약 메시지 M 에서 만들어지는 블록이 10개라면 아래 그림의 연산이 10번 일어나는 것이다.

 

 

 

 

그림에서 H, W, K 는 아래와 같다.

 

- H (= a, b, c, d, e, f, g, h) 는 총 256 비트이다.

- a, b, c, d, e, f, g, h 는 각각 4 바이트 = 32 비트이며, 16진수로 치면 8 자리 숫자이다.

- H0 은 상수값이고, 이후의 블럭에 적용될 Hi 값은 이전 블럭에서 생성된 Hi-1 값이 된다.

 

- K 는 32 비트 짜리 값이 64개인 상수값들이다.

- 총 64번의 Round Function 에 각각 하나씩의 K값이 순서대로 적용된다.

 

- W 는 32 비트 짜리 값이 64개 이며

- 총 64번의 Round Function 에 각각 하나씩의 W값이 순서대로 적용된다.

- W 는 메시지 블록 Mi 에서 만들어지는데 Mi 는 32비트 짜리 값이 16개이다.

- 이 16개를 4배로 부풀려서 64개의 W 값을 만들어내는 것이다. (Message Expansion Function)

 

 

 

H 만드는 법

 

- H는 초기값 H0 또는 이전 블럭에서 만들어진 Hi-1 값이 들어와

- 64번의 round function 을 거쳐 Hi 값이 생성된다. (그림에서는 Hi, Hi+1 로 명시되어 있지만 적당히 이해해주시라)

- 그러면 맨 처음 블럭의 맨 처음 W0, K0 와 함께 Round Function 에 쓰일 H0는 무얼까?

 

H0 는 상수값이다.

1) 2부터 시작하는 소수 8개를 루트를 씌운 후

2) 소수점 아래자리 32 비트를 추려낸 것이다.

 

아래는 소수인 2, 3, 5, 7, 11, 13, 17, 19 로 만들어낸 H0 값 8개 이다.

실제 계산 코드 snippet: https://goo.gl/pFq6Dp

 

 

 

K 만드는 법

 

- K 는 64개의 32 바이트 (= 16진수 8개) 상수값이며

- 하나의 블럭 계산시 총 64개가 쓰인다.

- 최초의 H0 만 상수값이고, 이후에는 계산된 값이 쓰이는 H 와는 달리

- K는 64개의 상수값이 항상 변함없이 쓰인다.

 

K 만드는법은 H가 제곱근을 쓰는 것과 달리 세제곱근을 사용하는 것만이 다르다.

실제 계산 코드 snippet: https://goo.gl/pFq6Dp

 

 

W 만드는 법 (+ Pre-Processing)

 

순서와 글의 Level 이 뒤죽박죽이긴 하지만 W 만드는 법은 Algorithm 과 Pre-Processing 이 겹쳐 있어서 하나 상위로 빼낸다.

 

 

하나의 블럭을 계산하는데 사용되는 아래 그림의 입력값 중에서

H 와 K 는 알아보았다. 이제 W 를 알아보자.

 

 

 

Pre-processing - Padding

 

1. SHA-256 을 먹이고픈 메시지 M에

2. 마지막 64 비트에 메시지 M 의 크기정보 (=bits)를 넣어주고

3. 512 로 나눠떨어지게 1 하나와 0 들로 채워주는 작업이다.

 

아래 그림을 예로 들어보자.

 

1. 메시지 M은  a, b, c 이다.

2. 맨 뒤쪽 64비트에 M 의 크기 (= bits) 값인 24 를 넣어주자

3. 메시지 바로 뒤에는 1을 하나 써주고, 남은 공백 423 개는 모두 0으로 채워준다.

4. 우리는 방금 메시지 M 을 padding 하여 512 로 나누어 떨어지는 메시지인 M' 를 만들었다.

 

 

< 출처: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf >

 

참고1. 위 예시에서 메시지 M 은 "abc" 이지만, 메시지 M 이 동영상이라면? M' 는 512 배수인 크기를 가진 매우 긴 메시지일것이다. 

참고2. 마지막에 왜 길이정보를 넣을까? 이걸 넣지 않으면 메시지 "00" 과 "000" 과 "00000" 의 padding 값이 같아질 것이다.

 

 

Pre-processing - Parsing

 

이제 padding 을 통해 512 의 배수만큼의 길이를 가진 메시지 M' 가 만들어졌다.

1) 이를 512 비트로 나누고, 

2) 다시 512 비트를 32비트씩 16개로 나누는 것이 parsing 이다.

 

 

W 만들기

 

padding 과 parsing을 거쳐 만들어진 M' 의 블럭들의 개수만큼 아래 프로세스가 이루어지게 된다.

 

 

 

M'의 한 블럭은 512 바이트이니 하나의 Round function 에서 쓰이는 32바이트씩 나누면 512/32 = 16 개 이다.

그런데 위 그림에는 W 64개가 보인다.

 

1) 첫 16개는 M' 의 블럭 하나를 그대로 가져다 쓰지만

2) 나머지 64 - 16 = 48 개는 그림의 MEXP (=Message Expansion Function) 으로 만들어낸다.

 

작은 함수들을 따로 묶어서 정리하려 하였는데 잠깐만 언급하자면

 

1) W0 - W15 는 M' 의 한 블럭을 32 비트씩 나눈 16개의 값이다.

2) W16 만 보면 아래와 같은 값들의 연산으로 만들어내는 것이다.

- W16-2 = W14

- W16-7 = W9

- W16-15 = W1

- W16-16 = W0

3) 이후에 적용되는 σ0, σ1, + 함수는 따로 설명하겠다.

 

 

 

전체 큰그림 다시보기

 

- 컴팩트하게 정리하려 하면서도 이해가 쉽게 하려다보니 글이 너무 늘어지는 것 같다. (능력의 한계)

- 지금까지의 내용을 정리해보면 아래 그림과 같다.

 

1) 2) H의 초기값 H0 와 K 값은 각각 소수들의 제곱근, 세제곱근의 소수점 아래 값들에서 만들어낸 상수값이다.

3) SHA-256 으로 해싱할 메시지 M 은 padding 되고 parsing 된다.

4) padding, parsing 된 메시지 M' 의 각 블럭들은 다시 Message Expansion Function 을 통해 64개의 W 값들로 만들어진다

5) 이렇게 만들어진 재료인 H, K, W 값들을, 한 블럭당 64번의 Round Function 연산을 하는데 집어넣게 되고, 최종적으로 이 블럭의 H 값이 계산되어 나온다.

 

* Round function 에는 시그마0, 시그마1, Maj, Choose, + 등의 연산이 사용된다.

 

 

 

< 짜집기한 그림 출처들 >

- https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf

- https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml

- https://medium.com/biffures/part-5-hashing-with-sha-256-4c2afc191c40

 

 

기타 함수들

 

- 설명이 빠진 함수들이 있다.

- 여기서는 간략한 소개만 하고, 다음 포스팅에서 실제로 하나의 Round function 을 따라가보면서 이해해보도록 하자

 

Round Function

 

- 다음 포스팅에는 실제 연산을 다룰 예정이니, 좀더 이해를 도울 수 있겠다.

 

0 <= i  <=63 일때 i번째 Round Function은 아래와 같이 이루어진다.

 

1) 입력값은 Ki, Wi 와 H에서 만들어진 값 a, b, c, d, e, f, g, h 2) Round Function 의 출력값은 다음 단계의 입력이 되는 a, b, c, d, e, f, g, h 가 된다. 3) 출력값 b, c, d, f, g, h 는 각각 입력값 a, b, c, e, f, g 가 그대로 전달되며 4) 출력값 a 와 e 는 다양한 연산을 거쳐서 만들어진다.

 

 

 

조그만 함수들

 

포스팅에서 언급된 utility 와 같이 사용되는 작은 연산들은 아래와 같다.

< 출처: https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml >

Message Expansion Function 에 쓰임 - σ0(X) = (X right-rotate 7) xor (X right-rotate 18) xor (X right-shift 3) - σ1(X) = (X right-rotate 17) xor (X right-rotate 19) xor (X right-shift 10)   Round Function 에 쓰임 Σ0(X) = (X right-rotate 2) xor (X right-rotate 13) xor (X right-rotate 22) Σ1(X) = (X right-rotate 6) xor (X right-rotate 11) xor (X right-rotate 25) Ch(X,Y,Z) = (X and Y) xor ((not X) and Z) Maj(X,Y,Z) = (X and Y) xor (X and Z) xor (Y and Z)

 

아래 설명은 엑셀로 SHA-256 을 구현한  구글시트 ( https://goo.gl/Sn8x2r )의 round 1 sheet 에서 가져왔다.

* Message Expansion Function 부분은 생략.

 

 

Σ0(X) = (X right-rotate 2) xor (X right-rotate 13) xor (X right-rotate 22)

 

- X 를 A 라고 보면

- A의 비트를 각각 2번, 13번, 22번 오른쪽으로 옮기고, 넘어가는 비트는 다시 왼쪽에 채워넣는다

- 그리고, 같은 자리의 비트값을 XOR 해준다. 결과적으로는 모두 더해준 다음 첫번째 자리의 비트값만 적어도 된다.

 

 

 

Σ1(X) = (X right-rotate 6) xor (X right-rotate 11) xor (X right-rotate 25)

 

- X 를 E 라고 보면

- E의 비트를 각각 6번, 11번, 25번 오른쪽으로 옮기고, 넘어가는 비트는 다시 왼쪽에 채워넣는다.

- 그리고, 같은 자리의 비트값을 XOR 해준다. 결과적으로는 모두 더해준 다음 첫번째 자리의 비트값만 적어도 된다.

 

 

 

Ch(X,Y,Z) = (X and Y) xor ((not X) and Z)

 

- Ch 는 Choose 이다.

- X, Y, Z 를 E, F, G 라고 보면

- E의 비트가 1이면 F의 값을 취하고, 0이면 G의 값을 취하는 것이다.

 

 

Maj(X,Y,Z) = (X and Y) xor (X and Z) xor (Y and Z) 

 

- Maj 는 Majority 로 보인다. 과반수? 다수결?

- X, Y, Z 를 A, B, C 라고 보면

- A, B, C 의 비트들이 0이 많으면 0, 1이 많으면 1이 되는 것이다.

 

 

다음 포스팅에는 한 라운드만 실제로 구글시트에 써가면서 계산해보겠다.