Brain085. AES 키 스케줄 (Key Schedule)
⚠️ 이 문서는 AES 암호 알고리즘이 10~14바퀴의 라운드를 돌 때, 사용자가 입력한 단 하나의 '마스터 비밀키(Master Key)'를 믹서기에 갈고 쪼개어 각 라운드마다 쓸 여러 개의 독립적인 '라운드 키(Round Key)'로 증식시키는 마법의 알고리즘인 '키 스케줄'을 다룹니다.
핵심 인사이트 (3줄 요약)
- 본질: AES 키 스케줄(Key Schedule)은 암호화의 핵심인 AddRoundKey 단계에서 쓰기 위해, 최초의 짧은 비밀키(예: 128비트)를 엑스오어(XOR)와 비선형 치환(S-Box)을 통해 길게 늘리고 변형하여 11개의 128비트 서브 키(라운드 키)로 팽창시키는 알고리즘이다.
- 가치: 만약 10번의 라운드 내내 똑같은 마스터 키를 더한다면 해커가 패턴을 찾아내기 매우 쉽다. 매 라운드마다 전혀 다르게 생긴 라운드 키를 들이부음으로써, 해커가 라운드 키 하나를 운 좋게 훔치더라도 원래의 마스터 키를 절대 역산할 수 없게 만드는 철벽을 세운다.
- 융합: 이 과정 자체도 AES의 SubBytes(대치)와 Shift(이동) 아이디어를 축소판으로 활용하며, 암호화 프로세스(Data Path)와 병렬로 동시에 라운드 키를 척척 찍어내도록 설계되어 하드웨어 구현 시 극한의 효율(Throughput)을 자랑한다.
Ⅰ. 개요 및 필요성 (Context & Necessity)
AES-128 알고리즘은 128비트(16바이트) 평문을 10라운드 동안 돌리면서 암호화한다. 매 라운드의 마지막 4단계인 'AddRoundKey'에서는 평문과 128비트의 키를 XOR 연산으로 버무려야 한다.
사용자가 비밀번호로 설정한 마스터 키는 딱 128비트 하나뿐인데, 10번의 라운드(그리고 최초 진입 전 1번의 덧셈까지 총 11번)에 더하려면 총 $128 \times 11 = 1,408$ 비트 분량의 키가 필요하다. 똑같은 마스터 키 128비트를 11번 우려먹으면 어떻게 될까? 해커가 수학적 패턴(슬라이드 공격 등)을 찾아내어 시스템을 뚫어버린다. 따라서 **"하나의 마스터 키를 밀가루 반죽처럼 길게 늘이되, 잘라낸 각 조각(라운드 키)들이 서로 아무런 연관성이 없어 보이게 마구 섞어주는 기계"**가 필요한데, 이것이 바로 **키 스케줄(Key Schedule, 키 확장 알고리즘)**이다.
📢 섹션 요약 비유: 요리사(AES)가 10층짜리 샌드위치를 만들 때, 한 통의 마요네즈(마스터 키)만 계속 바르면 맛이 뻔해서 들킵니다. 그래서 마요네즈에 매 층마다 고추장, 머스터드, 꿀을 복잡한 순서표(키 스케줄)에 맞춰 섞어버려, 매 층마다 전혀 다른 맛(라운드 키)의 소스를 발라버리는 작전입니다.
Ⅱ. 키 확장의 동작 원리 (Key Expansion)
AES-128의 마스터 키는 4개의 워드(Word, 1워드 = 4바이트 = 32비트)로 쪼개어 배열(W[0], W[1], W[2], W[3])에 담는다. 이 4개의 워드가 합쳐져 최초의 라운드 키(Key 0)가 된다.
이후 다음 공식을 통해 44개의 워드(W[4] ~ W[43])를 도미노처럼 꼬리에 꼬리를 물고 찍어낸다. 4개의 워드가 모일 때마다 하나의 128비트 라운드 키 세트가 완성된다.
생성 규칙 (Domino Effect)
기본적으로 새로 만들 워드 W[i]는 **바로 앞의 워드 W[i-1]**와 **4칸 앞의 워드 W[i-4]**를 XOR ⊕ 해서 만든다.
W[i] = W[i-1] ⊕ W[i-4]
🚨 하지만 이것만 쓰면 규칙이 너무 단순하다 (선형성 취약점).
그래서 4개의 워드 주기마다 한 번씩(즉, W[4], W[8], W[12]... 를 만들 때) 단순히 앞엣것을 가져오는 게 아니라, 앞의 워드를 갈아 마시는 특수 함수인 g() 함수를 거친 뒤에 엑스오어를 한다.
특수 믹서기: g() 함수의 3단계 마법
- RotWord (위치 이동): 워드 4바이트
[a, b, c, d]를 왼쪽으로 1칸 밉니다 $\rightarrow$[b, c, d, a] - SubWord (S-Box 치환): 위치가 바뀐 바이트들을 AES 본체에서 쓰는 무자비한 사전을 보고 아예 다른 글자로 치환해 버린다 (엄청난 비선형성/혼돈 추가).
- Rcon 더하기 (라운드 상수): 매 라운드마다 고유하게 정해진 상수(Round Constant, Rcon)를 더한다. 이 상수가 있기 때문에 라운드 1의 키와 라운드 10의 키가 수학적인 쌍둥이(대칭)가 되는 것을 방지한다.
┌───────────────────────────────────────────────────────────────────────────┐
│ AES-128 키 스케줄 (라운드 키 1개 생성) 시각화 도해도 │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ [ 마스터 키 (Key 0) ] │
│ W[0] W[1] W[2] W[3] │
│ │ │ │ │ │
│ │ │ │ │ ───▶ [ 특수 함수 g() ] ──┐ │
│ │ │ │ │ 1. 한 칸 옆으로 밀기 │ │
│ │ │ │ │ 2. S-Box로 글자 바꿈 │ │
│ │ │ │ │ 3. 라운드 상수 더하기 │ │
│ ▼ ▼ ▼ ▼ │ │
│ (⊕) ◀──(⊕) ◀──(⊕) ◀──────────────────────────────┘ │
│ │ │ │ │ │
│ ▼ ▼ ▼ ▼ │
│ W[4] W[5] W[6] W[7] │
│ [ 라운드 키 1 (Key 1) 완료! ] │
│ │
│ * 핵심: W[4]를 만들 때 평범하게 섞지 않고 g() 함수라는 독약(S-Box)을 │
│ 타버렸기 때문에, 튀어나온 Key 1은 마스터 키와 닮은 구석이 하나도 없다. │
└───────────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] 앞의 워드와 4칸 앞의 워드를 섞어 다음 워드를 만드는 전형적인 피드백(Feedback) 연쇄 구조다. 이 구조의 묘미는 해커가 10라운드 키 하나를 어쩌다 빼내더라도, S-Box와 상수라는 강력한 방해물 때문에 식을 거꾸로 돌려 원래의 마스터 키를 유추하기가 수학적으로 극도로 어렵다는 점이다.
- 📢 섹션 요약 비유: 마법의 지팡이(마스터 키)를 복사 기계에 넣으면, 기계가 지팡이를 똑같이 복사하지 않고, 칼을 달거나 망치를 달아버리는(g함수) 요상한 짓을 10번 해서 10개의 완전히 다르게 생긴 무기(라운드 키)를 뱉어내는 훌륭한 대장간 시스템입니다.
Ⅲ. 체급(128 vs 192 vs 256)에 따른 키 스케줄의 변화
키가 길어지면 이 스케줄 규칙도 조금씩 바뀐다.
- AES-128: 마스터 키가 4워드(16바이트)이므로, 4개 단위로 g() 함수 독약을 탄다. (가장 촘촘함)
- AES-256: 마스터 키가 8워드(32바이트)다. 너무 길어서 8워드를 채울 때마다 g() 함수를 타면 중간에 섞이는 빈도가 떨어진다. 그래서 **"4번째 워드마다 g() 함수 대신 가벼운 SubWord(S-Box 치환)만 한 번 더 쳐주는 추가 규칙"**이 들어간다.
이렇게 아키텍처를 변형함으로써, AES-256은 14라운드를 도는 동안 엄청나게 긴 마스터 키를 뼛속까지 고르게 버무려 15개의 강력한 라운드 키를 뽑아낸다.
Ⅳ. 키 스케줄 취약점과 연관 키 공격 (Related-Key Attack)
어떤 암호학자들은 AES의 키 스케줄이 상대적으로 '너무 단순하다'고 지적한다.
- 연관 키 공격 (Related-Key Attack): 해커가 마스터 키를 모르더라도, "첫 번째 키와 두 번째 키가 단 1비트만 다르다"는 사실을 안다면, 이 단순한 XOR 도미노 구조(키 스케줄)를 분석하여 마스터 키를 유추할 수 있다는 수학적 공격 이론이다.
- 실무적 방어: 하지만 다행히도 이 공격은 해커가 "서로 1비트만 다른 키로 암호화된 데이터를 무한정 수집할 수 있다"는 비현실적인 환경(현실의 은행이나 TLS에서는 불가능함)을 가정하기 때문에, 실생활에서 AES가 이 공격으로 뚫린 적은 단 한 번도 없다.
Ⅴ. 결론
AES가 완벽한 암호 시스템으로 찬사받는 이유는, 단순히 평문을 섞는 SPN 본체뿐만 아니라, "키를 섞어서 보급해 주는 병참 기지(Key Schedule)"조차도 본체의 마법(S-Box)을 공유하며 극한의 효율로 설계되었기 때문이다. 이 영리한 도미노 믹서기 덕분에, 우리는 128비트라는 짧은 암호 하나만 기억해도 10번의 암호화 라운드 내내 해커에게 단 한 줌의 패턴도 허용하지 않는 완벽한 난수의 방패를 휘두를 수 있다.
📌 관련 개념 맵
- 소속 시스템: AES (Advanced Encryption Standard)
- 내부 사용 도구: S-Box (치환), XOR 덧셈, Round Constant (Rcon)
- 방어하는 공격 기법: 슬라이드 공격 (라운드 상수로 방어)
- 이론적 취약점: 연관 키 공격 (Related-Key Attack)
👶 어린이를 위한 3줄 비유 설명
- 내가 다이어리에 건 자물쇠의 원래 비밀번호는 "1234" (마스터 키) 하나뿐이에요.
- 하지만 자물쇠 안에 있는 '키 스케줄'이라는 똑똑한 기계가 1234를 마구 꼬고 섞어서 "9876", "4321", "5678" 같은 10개의 완전히 다른 가짜 비밀번호(라운드 키)를 만들어내요.
- 그리고 도둑이 훔쳐 갈 때마다 이 10개의 번호를 번갈아 가며 자물쇠에 채워버리니까, 도둑이 "9876"이라는 번호를 어쩌다 알아내도 다음 자물쇠는 "4321"이라서 절대 일기장을 열 수 없는 마법이랍니다!