🔐 SHA-3와 SHAKE 완벽 해부: SoC 하드웨어 구현 전략

차세대 해시 표준 Keccak 알고리즘의 구조 분석부터 SoC 가속기 설계까지 — 초심자도 이해할 수 있는 종합 리서치

SHA-3는 단순한 해시 함수의 업그레이드가 아닙니다. 기존 머클-담가드 구조를 버리고 완전히 새로운 스폰지 구조(Sponge Construction)를 채택한 패러다임 전환입니다. 본 리포트는 알고리즘 이론부터 실제 SoC 하드웨어 가속기 설계까지, 설계자가 알아야 할 모든 핵심 사항을 정리했습니다.

1️⃣ SHA-3의 탄생 배경

SHA-3는 NIST(미국 국립표준기술연구소)가 2012년 공모를 통해 선정한 차세대 해시 표준으로, 2015년 FIPS 202로 공식 제정되었습니다. SHA-2가 여전히 안전하다고 평가받지만, 구조적 유사성 때문에 "만약 SHA-2가 깨진다면?"이라는 위기 상황에 대비한 대체 표준(Backup Standard)의 성격이 강합니다.

Keccak 알고리즘은 벨기에 암호학자 Guido Bertoni, Joan Daemen(AES 공동 설계자), Michaël Peeters, Gilles Van Assche가 설계했으며, 51개 경쟁작을 물리치고 최종 선정되었습니다. 가장 큰 차별점은 길이 확장 공격(Length Extension Attack)에 대한 근본적 면역성입니다.

📚 핵심 용어 정리

용어	정의	SHA-3 표준값
State	내부 연산 데이터 덩어리 (5×5 행렬)	1600비트
Rate (r)	한 라운드에서 처리되는 데이터 양	1088/1344비트
Capacity (c)	보안 강도를 결정하는 내부 영역	512/256비트
Lane	5×5 행렬의 한 칸 (64비트 데이터)	64비트
Round	Keccak-f 순열 함수 반복 횟수	24회

2️⃣ Keccak-f[1600] 라운드 함수 5단계

SHA-3의 심장은 24라운드 반복되는 Keccak-f[1600] 순열 함수입니다. 각 라운드는 θ → ρ → π → χ → ι 다섯 단계를 순차적으로 거칩니다. 각 단계의 역할과 하드웨어 복잡도는 아래와 같습니다.

⚙️ 단계별 하드웨어 복잡도 (상대 게이트 비용)

θ (Theta)

높음

ρ (Rho)

배선만

π (Pi)

배선만

χ (Chi)

중간

ι (Iota)

매우 낮음

🔄 각 단계의 역할

▶ θ (Theta) — 확산 단계: 각 열(Column)의 비트 패리티(XOR 합)를 계산하고 이를 이웃 열에 혼합합니다. 입력 1비트의 변화가 출력 전체에 퍼지도록 하는 눈사태 효과(Avalanche Effect)의 핵심이며, 한 비트 변화 시 평균 11개 비트가 영향을 받습니다.

▶ ρ (Rho) — 레인 내 비트 회전: 각 64비트 레인을 미리 정의된 삼각수(triangular number) 기반 상수만큼 순환 시프트합니다. 하드웨어에서는 단순 배선(re-wiring)으로 구현되어 게이트 없이 구현됩니다.

▶ π (Pi) — 레인 위치 재배치: 5×5 행렬 내에서 레인 위치를 (x,y) → (y, 2x+3y) 규칙으로 섞습니다. ρ와 마찬가지로 배선만으로 처리됩니다.

▶ χ (Chi) — 비선형 혼합: 유일한 비선형 연산 단계입니다. AND·NOT·XOR 조합으로 S-Box 역할을 수행하며, 전체 보안성의 핵심입니다. 공식은 A[x][y] = A[x][y] XOR ((NOT A[x+1][y]) AND A[x+2][y]).

▶ ι (Iota) — 라운드 상수 주입: 각 라운드마다 고유한 RC 상수를 좌표 (0,0) 레인에 XOR하여 라운드 간 대칭성을 파괴합니다. 이 단계가 없다면 모든 라운드가 동일해져 공격자가 축약 공격을 가할 수 있습니다.

3️⃣ SHAKE — 가변 길이 출력의 마법

SHAKE(SHAKE128, SHAKE256)는 Extendable-Output Function(XOF)으로, 출력 길이를 사용자가 원하는 만큼 추출할 수 있는 특별한 함수입니다. SHA-3가 고정 길이(224/256/384/512비트) 출력만 지원한다면, SHAKE는 무한대 길이까지 출력을 짜낼 수 있습니다.

🧠 쉬운 비유 — "스폰지와 주스"

마른 스폰지에 주스(입력 데이터)를 붓습니다. 스폰지 내부의 깊은 공간(Capacity)이 클수록 주스가 깊숙이 스며들어 보안이 강해집니다. 이제 스폰지를 짜서 주스(출력)를 얻습니다. 더 많이 필요하면? 스폰지를 한 번 흔든 뒤(Keccak 순열 재호출) 다시 짭니다. 이 과정을 원하는 만큼 반복할 수 있습니다.

🏗️ 스폰지 구조 개념도

4️⃣ SoC 하드웨어 구현 전략

⚖️ 아키텍처 선택 — Throughput vs Area

전략	Throughput	면적(Area)	전력	적합 용도
Iterative (반복형)	낮음	매우 작음	낮음	임베디드 SoC, IoT
Partial Unrolling (부분 언롤)	중간	중간	중간	모바일 AP, 보안 가속기
Full Unrolling (완전 언롤)	매우 높음	매우 큼	높음	고성능 서버, HSM

🔢 라운드 상수 RC[i] (64비트, Keccak-f[1600])

각 라운드의 ι 단계에서 좌표 (0,0) 레인에 XOR되는 24개의 상수입니다. 하드웨어 구현 시 ROM 또는 LUT로 고정하며, LFSR 기반으로 생성할 수도 있습니다.

// Round Constants (hex)

RC[00] = 0x0000000000000001 RC[12] = 0x000000008000808B

RC[01] = 0x0000000000008082 RC[13] = 0x800000000000008B

RC[02] = 0x800000000000808A RC[14] = 0x8000000000008089

RC[03] = 0x8000000080008000 RC[15] = 0x8000000000008003

RC[04] = 0x000000000000808B RC[16] = 0x8000000000008002

RC[05] = 0x0000000080000001 RC[17] = 0x8000000000000080

RC[06] = 0x8000000080008081 RC[18] = 0x000000000000800A

RC[07] = 0x8000000000008009 RC[19] = 0x800000008000000A

RC[08] = 0x000000000000008A RC[20] = 0x8000000080008081

RC[09] = 0x0000000000000088 RC[21] = 0x8000000000008080

RC[10] = 0x0000000080008009 RC[22] = 0x0000000080000001

RC[11] = 0x000000008000000A RC[23] = 0x8000000080008008

🔁 비트 회전 상수 ρ[x][y] (mod 64)

각 레인의 순환 시프트 값을 히트맵으로 표현했습니다. 값이 클수록 진한 색으로 표시되며, 모두 64의 나머지(modulo 64)로 정규화되어 있습니다.

x \ y	y=0	y=1	y=2	y=3	y=4
x=0	0	36	3	41	11
x=1	1	44	10	45	2
x=2	62	6	43	61	15
x=3	28	55	25	21	8
x=4	27	20	39	56	14

🛡️ 부채널 공격 방어 (Side-Channel Attack Mitigation)

SoC 내 보안 모듈(SE, TEE)로 SHA-3를 사용할 때는 DPA(Differential Power Analysis)와 EM 방출 공격이 주요 위협입니다. 방어 기법으로는:

✓ Threshold Implementation(TI): χ 단계의 AND 게이트를 3-share 이상으로 분할하여 중간값 노출 방지

✓ Domain-Oriented Masking(DOM): 최신 마스킹 기법으로 면적 오버헤드 약 2~3배에서 1차 DPA 방어 가능

✓ Shuffling: 25개 레인 처리 순서를 매 실행마다 랜덤화하여 공격자의 시간적 정렬 방해

5️⃣ 실전 활용 사례

응용 분야	사용 변형	용도
🔐 Post-Quantum 암호	SHAKE256	Kyber, Dilithium의 의사난수 생성
⛓️ 블록체인	Keccak-256	Ethereum 주소 생성, 스마트컨트랙트
🔑 키 유도	SHAKE128	가변 길이 대칭키 파생(KDF)
🎲 난수 생성	SHAKE256-DRBG	TRNG 후처리, CSPRNG 구성
📱 보안 부팅	SHA3-256	펌웨어 무결성 측정, Secure Boot

6️⃣ 결론 및 설계자 가이드

💡 핵심 메시지

SHA-3는 SHA-2 대비 소프트웨어 성능은 다소 떨어지지만, 하드웨어에서는 규칙적인 순열 구조 덕분에 매우 효율적으로 구현됩니다. SHAKE의 가변 출력 특성은 Post-Quantum 암호 시대의 필수 컴포넌트로, 차세대 SoC 설계자에게는 "선택" 이 아닌 "필수" 가속기입니다. 특히 χ 단계의 비선형 혼합과 θ 단계의 확산을 어떻게 최적화하느냐가 전체 성능과 보안을 결정합니다.

🎯 SoC 설계자 체크리스트

✓ 타겟 throughput 정의 (Gbps 단위) → 언롤 정도 결정

✓ 1600비트 State 레지스터 → Flip-Flop 또는 SRAM 선택 (면적/속도 트레이드오프)

✓ ρ·π 단계는 반드시 배선으로 구현 — 레지스터·플립플롭 사용 금지

✓ 라운드 상수 RC[i] → 24엔트리 ROM 또는 LFSR 온더플라이 생성

✓ χ 단계 → DOM 마스킹 고려 (보안 요구 시)

✓ AXI/AHB 버스 인터페이스 → DMA 연동으로 CPU 오버헤드 최소화

✓ NIST CAVP 테스트 벡터로 검증 (FIPS 202 공식 KAT)

📖 참고 자료

▶ NIST FIPS 202 — SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions

▶ Keccak Team 공식 사이트 (keccak.team) — 참조 구현 및 최신 연구 자료

▶ Cryptology ePrint Archive — SHA-3 하드웨어 구현 논문 및 부채널 방어 기법

본 자료는 기술 교육 및 SoC 설계 참고용으로 작성되었습니다. 실제 제품 구현 시에는 NIST FIPS 202 표준 문서와 최신 보안 권고사항을 직접 확인하시기 바랍니다.

📄 Raw Data

# [종합 리서치] SHA-3 및 SHAKE 알고리즘의 구조와 SoC 하원 하드웨어 구현 가이드

## 1. 개요 및 배경 (Foundation)

### 1.1 SHA-3(Secure Hash Algorithm 3)의 탄생
SHA-3는 NIST(미국 국립표준기술연구소)가 SHA-2를 대체하기 위해 공모를 통해 선정한 차세대 해시 표준입니다. 기존 SHA-1, SHA-2가 머클-담가드(Merkle-Damgård) 구조를 사용하는 것과 달리, SHA-3는 **Keccak(케착)** 알고리즘을 기반으로 한 **스폰지 구조(Sponge Construction)**를 채택했습니다. 이는 SHA-2에서 발견될 수 있는 구조적 취약점(길이 확장 공격 등)에 대한 근본적인 방어 기제를 가집니다.

### 1.2 주요 용어 정의
- **State (상태):** 알고리즘 내부에서 연산이 수행되는 데이터 덩어리입니다. SHA-3의 표준 크기는 1600비트(5x5 행렬의 64비트 레인)입니다.
- **Rate (r, 전송률):** 한 번의 연산 단계에서 처리되는 데이터의 양입니다.
- **Capacity (c, 용량):** 보안 강도를 결정하는 내부 상태의 나머지 부분입니다. 외부에서는 직접 접근할 수 없습니다.
- **Sponge Construction:** 데이터를 '흡수(Absorbing)'하고 결과를 '짜내는(Squeezing)' 과정을 통해 가변 길이를 처리하는 구조입니다.

---

## 2. 알고리즘 내부 동작 (Sequential Flow)

SHA-3의 핵심은 `Keccak-f[1600]`이라 불리는 순열(Permutation) 함수입니다. 이 함수는 총 24라운드의 반복 연산으로 구성됩니다.

### 2.1 상태 행렬(State Matrix) 구조
1600비트의 데이터는 $5 \times 5$ 행렬로 관리되며, 각 칸(Cell)은 64비트(Lane)의 크기를 갖습니다.
- 좌표: $x, y \in \{0, 1, 2, 3, 4\}$, $z \in \{0, \dots, 63\}$

### 2.2 라운드 함수 5단계 (Step-by-Step)
각 라운드는 다음의 5가지 매핑 과정을 순차적으로 거칩니다.

1.  **$\theta$ (Theta): 확산(Diffusion) 단계**
    - 각 열(Column)의 패리티를 계산하여 주변 레인에 혼합합니다. 한 비트의 변화가 전체로 퍼지게 하는 핵심 단계입니다.
2.  **$\rho$ (Rho): 레인 내 비트 회전**
    - 각 64비트 레인 내의 비트들을 정해진 상수만큼 순환 시프트(Circular Shift)합니다.
3.  **$\pi$ (Pi): 레인 위치 재배치**
    - $5 \times 5$ 행렬 내에서 레인들의 위치를 섞습니다. ($x, y$ 좌표 변경)
4.  **$\chi$ (Chi): 비선형 혼합**
    - 논리 연산(AND, NOT, XOR)을 통해 비선형성을 주입합니다. S-Box 역할을 수행합니다.
5.  **$\iota$ (Iota): 라운드 상수 추가**
    - 라운드마다 고유한 상수($RC$)를 XOR 하여 대칭성을 파괴합니다.

---

## 3. SHAKE (Extendable-Output Functions) 개념 이해

SHAKE(SHAKE128, SHAKE256)는 결과값의 길이를 사용자가 원하는 대로 정할 수 있는 함수입니다.

### 3.1 초심자를 위한 "주스 짜기" 비유
SHAKE의 동작을 이해하기 위해 **'스폰지'**와 **'주스'**를 상상해 봅시다.

1.  **흡수 단계 (Absorbing):** 마른 스폰지에 주스(입력 데이터)를 붓습니다. 스폰지의 용량(Capacity)이 크면 주스가 더 깊숙이 스며들어 보안이 강해집니다.
2.  **짜내기 단계 (Squeezing):** 이제 스폰지를 짭니다. 
    - 한 번 꽉 짜서 컵 하나 분량(Rate)을 얻었습니다. 
    - 그런데 주스가 더 필요하다면? **스폰지를 다시 한번 흔든 뒤(Keccak 순열 호출)** 또 짭니다.
    - 원하는 만큼의 주스가 나올 때까지 이 과정을 반복합니다.

### 3.2 도식화 (Conceptual Diagram)
```text
입력 데이터(M) -> [패딩] -> [ 흡수(Absorbing) Phase ]
                            |
                     +---->(XOR)----[ Keccak-f ]----+
                     |      | r비트       |         |
                     |      +-------------+         |
                     +------------------------------+
                            |
                     [ 짜내기(Squeezing) Phase ]
                            |
              +------ r비트 추출 ----> [결과물 Part 1]
              |             |
        [ Keccak-f ] <------+
              |             |
              +------ r비트 추출 ----> [결과물 Part 2] ... (무한 반복 가능)
```

---

## 4. SoC 하드웨어(HW) 구현을 위한 기술 정보

SoC 설계 시 SHA-3/SHAKE 가속기를 구현할 때 고려해야 할 핵심 요소들입니다.

### 4.1 하드웨어 아키텍처 전략
1.  **Throughput 중심 (High Performance):** 24라운드를 모두 언롤링(Unrolling)하거나 파이프라인으로 구성합니다. 면적(Area)은 커지지만 클럭당 처리량이 극대화됩니다.
2.  **Area 중심 (Low Power/Small Size):** 라운드 함수 하나만 구현하고 레지스터를 통해 24번 순환(Iterative)시킵니다. 대부분의 임베디드 SoC에서 선호하는 방식입니다.

### 4.2 주요 상수 데이터 (Raw Technical Data)
하드웨어 구현 시 LUT(Look-Up Table)나 로직으로 고정되어야 하는 값들입니다.

**[라운드 상수 $RC[i]$ - Keccak-f[1600] 기준]**
이 값들은 64비트 레인의 0번 좌표($x=0, y=0$)에 XOR 됩니다.
```text
RC[0]  = 0x0000000000000001    RC[1]  = 0x0000000000008082
RC[2]  = 0x800000000000808A    RC[3]  = 0x8000000080008000
RC[4]  = 0x000000000000808B    RC[5]  = 0x0000000080000001
RC[6]  = 0x8000000080008081    RC[7]  = 0x8000000000008009
RC[8]  = 0x000000000000008A    RC[9]  = 0x0000000000000088
RC[10] = 0x0000000080008009    RC[11] = 0x000000008000000A
RC[12] = 0x000000008000808B    RC[13] = 0x800000000000008B
RC[14] = 0x8000000000008089    RC[15] = 0x8000000000008003
RC[16] = 0x8000000000008002    RC[17] = 0x8000000000000080
RC[18] = 0x000000000000800A    RC[19] = 0x800000008000000A
RC[20] = 0x8000000080008081    RC[21] = 0x8000000000008080
RC[22] = 0x0000000080000001    RC[23] = 0x8000000080008008
```

**[비트 회전 상수 $\rho(x, y)$]**
각 좌표 $(x, y)$에 해당하는 레인의 비트를 좌측으로 시프트하는 값입니다.
- (0,0): 0, (1,0): 1, (2,0): 190, (3,0): 28, (4,0): 91
- (0,1): 36, (1,1): 44, (2,1): 6, (3,1): 55, (4,1): 20
- (0,2): 3, (1,2): 10, (2,2): 171, (3,2): 61, (4,2): 105
- (0,3): 105, (1,3): 45, (2,3): 15, (3,3): 21, (4,3): 8
- (0,4): 75, (1,4): 2, (2,4): 61, (3,4): 56, (4,4): 14
*(참고: 실제 구현 시 64로 나눈 나머지 값(modulo 64)을 사용합니다.)*

### 4.3 하드웨어 최적화 팁
- **$\theta$ 단계의 병렬화:** 패리티 계산($C[x]$)을 병렬로 수행하여 지연 시간을 줄일 수 있습니다.
- **$\rho$와 $\pi$의 결합:** 하드웨어에서는 이 두 단계가 단순한 **'배선(Wiring)'**에 불과합니다. 별도의 클럭 소모 없이 데이터 경로를 연결하는 것만으로 연산이 완료되므로, 로직 설계 시 $\theta$와 $\chi$ 사이에 배선으로 끼워 넣습니다.
- **부채널 공격(Side-Channel Attack) 방어:** SoC 내부 보안 모듈로 사용될 경우, 전력 분석 공격을 방어하기 위해 '마스킹(Masking)' 기법을 적용해야 합니다. 특히 $\chi$ 연산의 AND 게이트에 대한 마스킹이 핵심입니다.

---

## 5. 결론 및 시사점

SHA-3와 SHAKE는 기존 해시 함수보다 유연하고 강력한 보안성을 제공합니다. 특히 SHAKE의 확장 가능한 출력 기능은 현대 암호학에서 난수 생성기(DRBG), 가변 길이 키 유도(KDF) 등에 필수적으로 사용됩니다. SoC 설계자 입장에서는 SHA-3가 SHA-2에 비해 연산 복잡도는 높지만, 순열 기반의 규칙적인 구조 덕분에 하드웨어 가속기 구현 시 매우 높은 효율성을 달성할 수 있다는 장점이 있습니다.
---

## References

- [NIST FIPS 202 Standard](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf)
- [Keccak Team Official Website](https://keccak.team/keccak.html)
- [Cryptology ePrint Archive - HW Implementation of SHA-3](https://ia.cr/2012/064)