SHA / SHAKE / Keccak은 대표적인 HASH함수이다.
오늘은 차이점과 내부 함수등을 알아보려고 한다.
What different SHA-Keccak-SHAKE
- SHA (Secure Hash Algorithm)
- Keccak을 기반으로 하는 NIST 표준 HASH 함수
- Keccak
- Sponge 함수 구조 사용 알고리즘
- SHAKE (Secure Hash Algorithm with KEccak)
- SHA-3 표준의 일부로 유연한 출력 길이를 제공하는 확장 가능한 출력 함수(XOF)
SHA-3 / SHAKE 모두 Keccak 함수를 기반으로 만들어진 해시함수이다.
따라서 Keccak의 내부를 살펴본다.
Keccak and Sponge Structure
- Process 1 : Padding
- Keccak에서 사용하는 Padding은 101 Padding으로 앞뒤를 1로 채우고 중간을 0으로 채우는 방식을 취한다. 하지만 SHA-3나 SHAKE에서는 해시함수일때는 01 Padding, 그리고 XOF의 경우 또 다른 패딩 방식을 사용한다.
- 아래 1088Bit를 기준으로 서술한 이유는 Keccak-256 기준이고 이는 r/c의 값에 따라 결정된다.
- Process 2: Absorbing
- HASH 함수라면 기본적으로 어느 길이의 입력이 들어와 정해진 출력의 길이를 보장해준다.
- 또한 Keccak, 그리고 이걸 사용하는 SHA-3/ SHAKE의 경우에는 블록암호와 같이 Padding 방식을 사용해 긴 길이의 입력에 대해서도 일정한 출력을 보장할 수 있다. 다만 한 함수의 끝으로 출력하는 것이 아닌 연쇄적으로 사용해 단일의 output을 뽑아낸다.
- 따라서 블록암호와 운용모드와 같이 어떤 암호화 함수와 같은 F 혹은 permutation이라고 불리는 함수를 사용한다.
- 이 Absorbing 함수의 경우가 해당 함수이다.
- Permutation 함수의 경우 밑에 설명을 하였다.
-
- r/c는 위의 표의 값에 따라 결정되는 값이다.
- 처음의 r/c의 자리에는 필요 비트만큼의 0이 들어간다.
- 이후 패딩을 한 input값이 r과 XOR을 통해 연산되며 f 함수를 통해 permutation이 일어난다.
- 이를 Sponge 구조라고 한다.
- Process 3 : Squeezing
- 최종 출력값을 뽑아내기 위해 Squeezing을 한다.
- Absorbing과 동일한 f 함수를 사용해 출력을 제시한다.
- SHAKE에서는 이 과정을 많이 해 원하는 만큼의 output을 뽑을 수 있는 것이다.
Permutation Function of SHA/Keccak/SHAKE
- f 함수에는 r/c (Keccak256 기준 1600Bits)가 들어간다.
- 이를 5*5*64의 육면체로 나타낸다.
- 따라서 A[x][y]는 64비트를 지칭하는 것이다.
- 해당 도형을 펼쳐본다면 아래와 같이 볼 수 있다.
- f 함수 내부는 이렇게 동작한다.
- 24번의 Round로 구성이 되며 한 Round는 위의 슈도코드와 같다.
신지드같이 섞고 돌리고 더하고 섞고 돌리고...