ElGamal 서명의 기본 단점: Ciphertext Expansion

첫 번째 장 상단의 Remark 부분입니다.ElGamal 서명은 결과물로 $(r, s)$ 두 개의 값을 출력합니다. 따라서 원본 메시지 $x$에 비해 서명의 길이가 2배로 늘어나는 Ciphertext Expansion(암호문 확장) 문제가 발생합니다.

• 예: 모듈러 $p$가 2048 bits라면, 서명 $(r, s)$의 길이는 무려 4096 bits가 됩니다.

Weakness of Elgammal Signature

①: Ephemeral Key 재사용 (Reuse of the Ephemeral Key)

앞서 ElGamal 암호화(Encryption)에서 일회용 난수 $i$를 재사용하면 시스템이 뚫린다고 배웠죠? 서명(Signature)에서도 Ephemeral Key ($K_E$)를 재사용하면 아예 송신자의 Private Key ($d$)가 통째로 털리게 됩니다. 서술형 계산 문제로 아주 내기 좋은 파트입니다.

• 상황: Bob이 귀찮아서 똑같은 $K_E$를 사용해 두 개의 메시지 $x_1, x_2$에 서명했습니다.
• Trudy의 공격 (Known Plaintext Attack):
  Trudy는 네트워크를 도청해 두 개의 평문과 서명 쌍 $(x_1, r, S_1)$, $(x_2, r, S_2)$를 확보했습니다. ($K_E$가 같으므로 $r$ 값도 동일하게 나옵니다.)
• 수학적 해킹 과정:
  ElGamal 서명의 기본 공식은 다음과 같습니다.
  $S_1 \equiv (x_1 - d \cdot r) \cdot K_E^{-1} \pmod{p-1}$
  $S_2 \equiv (x_2 - d \cdot r) \cdot K_E^{-1} \pmod{p-1}$

1. $K_E$ 찾기:

위 식에서 아래 식을 빼버리면(Subtract), 골치 아픈 미지수 $d \cdot r$이 소거됩니다.$S_1 - S_2 \equiv (x_1 - x_2) \cdot K_E^{-1} \pmod{p-1}$
이를 $K_E$에 대해 정리하면, Trudy는 간단한 나눗셈으로 일회용 키 $K_E$를 알아낼 수 있습니다.
$K_E \equiv \frac{x_1 - x_2}{S_1 - S_2} \pmod{p-1}$

Why is the Elgamal signature scheme nondeterministic?

발생하는 취약점: 실존적 위조(Existential Forgery) 공격이 가능해집니다.

• 이유: 해시 함수 $h(x)$가 없으면 서명 공식의 수학적 조작이 가능해집니다. 해커는 송신자의 개인키($d$)를 전혀 몰라도, 임의의 수식을 조작하여 유효한 위조 서명 $(r', s')$을 만들고 이에 맞는 가짜 메시지 $x'$을 역산해 낼 수 있습니다.

[English Answer]

• Vulnerability: The system becomes vulnerable to Existential Forgery

• Reason: Without the hash function $h(x)$, the signature scheme is mathematically exploitable. An attacker can forge a valid signature pair $(r', s')$ and derive a corresponding fake message $x'$ without needing the sender's private key ($d$).

2. Private Key ($d$) 털기 (두 번째 장 상단):

이제 알아낸 $K_E$를 원래 1번 식에 다시 대입하고, 남은 미지수인 $d$($K_{pr}$)에 대해 식을 정리합니다.$d \equiv \frac{x_1 - S_1 \cdot K_E}{r} \pmod{p-1}$

결론: 일회용 키를 단 한 번이라도 재사용하면, 해커가 확장 유클리드 알고리즘(EEA)을 써서 Private Key를 완벽하게 계산해 냅니다. 교수님이 빨간 펜으로 "Do NOT reuse Ephemeral Key!!!"라고 강조하신 이유입니다.

3. 취약점 ②: 존재적 위조 공격 (Existential Forgery Attack)

이전에 본 RSA의 취약점과 완벽하게 동일한 맥락입니다. Trudy가 Bob의 Private Key($d$)를 몰라도, 서명 검증을 통과하는 가짜 $(x, r, s)$ 세트를 만들어낼 수 있습니다.

Trudy의 공격 과정 (수식 암기 필수):
1. Trudy는 조건 $\gcd(j, p-1) = 1$을 만족하는 임의의 정수 $i, j$를 고릅니다.
2. Bob의 공개키($\beta$, 여기서는 생성자 $\alpha$ 대신 $2$를 사용)를 이용해 가짜 서명 $(r, s)$를 먼저 만들어냅니다.

$r \equiv 2^i \cdot \beta^j \pmod p$
$s \equiv -r \cdot j^{-1} \pmod{p-1}$
3. 이 서명에 수학적으로 짝이 맞는 가짜 메시지 $x$를 역으로 계산합니다.
$x \equiv s \cdot i \pmod{p-1}$

Verification (검증 통과):
Alice가 이 가짜 세트 $(x, r, s)$를 받아서 검증 식 $t \equiv \beta^r \cdot r^s \pmod p$ 에 넣어보면, 놀랍게도 $2^x \pmod p$ 와 완벽하게 일치하게 되어 Valid signature로 판정됩니다.

ElGamal 위조 공격의 수학적 증명 (Why does the attack work?)

해커(Trudy)가 만든 가짜 서명 $(r, s)$가 어떻게 Alice의 검증(Verification)을 통과하는지 보여주는 수식 전개입니다. 기말고사에 "위조 서명이 검증식을 통과하는 과정을 증명하라"고 나오면 이 식을 쓰셔야 합니다.

• 검증식 시작: $t \equiv \beta^r \cdot r^s \pmod p$ (Alice는 Bob의 공개키 $\beta$를 이용해 검증을 시작합니다.)

• 수학적 트릭 (소거법):
  수식을 전개하다 보면, 해커가 모르는 Bob의 개인키 $d$가 포함된 항 $\mathbf{2^{dr}}$과 해커가 역원으로 교묘하게 세팅해 둔 항 $\mathbf{2^{-dr}}$이 곱해지면서 기가 막히게 소거(Cancel out)되어 날아갑니다. (분홍색 형광펜 부분)

• 검증 통과:
  결국 식은 $2^{s \cdot i} \pmod p$ 로 깔끔하게 정리됩니다. 해커가 애초에 가짜 메시지 $x$를 $s \cdot i \pmod{p-1}$ 로 세팅해 두었기 때문에, $2^{s \cdot i}$는 $2^x$와 완벽하게 일치하게 됩니다.
  $\rightarrow$ YES! Valid signature! (검증 시스템이 완벽하게 속았습니다.)

• Limitations (공격의 한계):
  맨 밑에 빨간 X표가 쳐진 부분입니다. 해커가 "100만 달러를 송금하라" 같은 특정 메시지 $x$를 원한 게 아니라, 수식에 의해 $x$ 값이 강제로 결정($x \equiv s \cdot i$)되어 버렸기 때문에 이 메시지는 아무 의미 없는 외계어(Garbage / Pseudorandom)일 뿐입니다.

왜 해시 함수(Hash Function)가 필수적인가?

ElGamal이든 RSA든, 순수하게 수학 공식만 쓰는 전자 서명 알고리즘들은 치명적인 실용적 문제점(Problem)들을 가지고 있습니다. 이를 해결하기 위해 등장하는 것이 Hash Function입니다.

• Auxiliary Functions (보조 함수): 해시 함수는 그 자체로 암호화가 아니라, 서명이나 MACs(메시지 인증 코드) 등을 돕는 필수적인 보안 보조 도구입니다.

• Problem 1: Length Restriction (길이 제한)
  RSA 연산을 하려면 메시지 $x$의 크기가 모듈러 $n$의 크기보다 작아야 합니다. (예: $|x| \le \mathbf{2048\ bits} \iff \mathbf{256\ Bytes}$). 현대의 메가바이트, 기가바이트 단위의 파일을 한 번에 서명하는 것은 불가능합니다.

• Problem 2: Message Overhead & Security Flaw (오버헤드 및 보안 결함)
  긴 문장을 256 Bytes씩 블록($x_1, x_2, \dots, x_n$)으로 쪼개서 각각 서명($S_1, S_2, \dots, S_n$)을 한다고 가정해 봅시다.

1. Overhead: 느려터진 RSA/ElGamal 서명 연산을 수천 번 반복해야 하므로 시스템이 마비됩니다.
2. Attacker (Trudy의 조작): 그림에서 보듯, 해커가 중간에 있는 블록($x_3, S_3$ 등)을 통째로 빼버리거나(Drop) 순서를 뒤섞어도(Reorder), 개별 블록의 서명은 Valid하기 때문에 수신자는 파일이 조작된 것을 알아채기 힘듭니다.

해시 함수의 도입 배경과 해결책 (The Solution)

• Problem 2: High Computation Load (과도한 연산량)
  256MB짜리 파일을 256 Bytes 단위로 쪼개서 서명하면, 무려 100만 번의 RSA 서명 연산이 필요합니다. RSA 서명은 거듭제곱 연산이라 굉장히 무겁기 때문에 시스템이 뻗어버립니다. (Really SLOW)

• Problem 3: Security Limitations (보안 취약점)
  블록 단위로 서명하면, 해커(Attacker)가 중간에 특정 블록을 빼버리거나(Drop), 순서를 바꾸거나(Exchange), 가짜 블록을 끼워 넣어도(Add) 수신자는 알아채기 힘듭니다.

• Solution: "Compress" prior to signing (서명 전 압축)
  수백만 개의 블록($x_1, x_2, \dots, x_n$)에 일일이 서명하지 말고, 해시 함수 $h$를 통과시켜 단 하나의 짧은 블록으로 "압축"한 뒤, 그 압축된 결과물에만 딱 한 번 서명($K_{pr}$)하자는 아이디어입니다. 이를 Hash-and-Sign 패러다임이라고 합니다.

해시를 이용한 서명 프로토콜 (Protocol with Hash)

송신자 (Bob):

1. 원본 메시지 $x$를 해시 함수에 넣어 해시값 $z$를 뽑아냅니다. ($z = h(x)$)
2. 이 해시값 $z$에 자신의 개인키($K_{pr}$)로 서명을 합니다. ($S = Sig_{K_{pr}}(z)$)
3. 원본 문서 $x$와 서명 $S$를 함께 보냅니다.

수신자 (Alice/Public):

1. 받은 원본 문서 $x$를 직접 해시 함수에 넣어 자신만의 $z'$를 계산합니다.
2. Bob의 공개키($K_{pub}$)로 서명 $S$를 검증하여 $z$ 값을 복원한 뒤, 자신이 계산한 $z'$와 일치하는지 비교합니다.

해시 함수의 6가지 필수 조건 ★기말 단골 문제★

아무 함수나 해시 함수로 쓸 수 없습니다. 암호학적으로 안전하려면 다음 6가지 요구조건(Requirements)을 반드시 만족해야 합니다

1. Arbitrary input length: 입력값(원본 파일)의 길이는 1KB이든 10GB이든 제한이 없어야 한다.
2. Fixed output length: 출력값(해시값)의 길이는 항상 고정되어 있어야 한다. (예: SHA-256은 무조건 256 bits 출력)
3. Efficient (Fast feeding): 계산 속도가 매우 빨라야 한다.
4. One-wayness (단방향성 / Preimage Resistance): 해시값 $y$를 보고 원본 $x$를 역산해 내는 것이 불가능해야 한다.
5. Weak collision Resistance (약한 충돌 내성 / Second Preimage Resistance): 주어진 원본 $x_1$이 있을 때, 이와 똑같은 해시값을 가지는 다른 가짜 메시지 $x_2$를 찾아내는 것이 불가능해야 한다. ($h(x_1) = h(x_2)$ 인 $x_2$ 찾기 불가)
6. Collision Resistance (강한 충돌 내성): 그냥 맨땅에서 해시값이 똑같이 나오는 임의의 쌍 $(x_1, x_2)$를 찾아내는 것조차 불가능해야 한다.

5,6번의 차이
Weak Collision Resistance: Computationally infeasible to find $x_2$ such that $h(x_1) = h(x_2)$ for a GIVEN $x_1$.
Collision Resistance: Computationally infeasible to find ANY distinct pair $(x_1, x_2)$ such that $h(x_1) = h(x_2)$.
간단히 말해, 6번(강한 충돌 내성)을 만족하는 해시 함수는 자동으로 5번(약한 충돌 내성)도 만족하게 됩니다. 타겟 없이 아무거나 두 개 찾는 것도 불가능한데, 하물며 타겟을 딱 정해주고 똑같은 걸 찾으라고 하면 더더욱 불가능하기 때문입니다.

Collision Attack

충돌 공격의 실제 시나리오 (Collision Attack)

• 공격 준비: Trudy는 해시값이 완벽하게 똑같이 나오는 두 개의 문서 $x_1$(예: "50달러 송금")과 $x_2$(예: "25K 달러 송금")를 미리 찾아냅니다. ($h(x_1) = h(x_2) = z$)
• 서명 가로채기: Trudy는 무해해 보이는 문서 $x_1$을 Alice에게 내밀어 서명 $S$를 받아냅니다. ($S = Sig_{K_{pr}}(z)$)
• 바꿔치기 (Swap): Trudy는 Alice가 서명한 $x_1$을 버리고, 악의적인 문서 $x_2$에 서명 $S$를 붙여서 Bob에게 보냅니다.
• 검증 통과: Bob이 문서 $x_2$를 해시 함수에 넣어보면 똑같은 해시값 $z$가 나옵니다. 따라서 서명 검증식은 True(합격)가 되고, Bob은 Alice가 25K 달러를 송금하라고 서명한 것으로 완벽하게 속게 됩니다.

비둘기집 원리: 충돌은 수학적으로 피할 수 없다

교수님의 핵심 질문: "충돌이 아예 없는 해시 함수를 만들 수 있는가? (NO!)"

• 이유: 원본 메시지(Input space)의 크기는 무한대($|X|$)인 반면, 출력되는 해시값(Hash space)의 크기는 고정되어 있습니다(예: 160 bits $\rightarrow$ $2^{160}$ 개).
• 결론: 입력값이 출력값보다 훨씬 크기 때문에($|X| \gg |Z|$), 해시값이 겹치는 충돌은 무조건 존재(MUST Exist)할 수밖에 없습니다.
• 보안의 목표: 충돌을 없애는 것이 아니라, "충돌을 찾아내는 것을 컴퓨터 연산 능력으로 도저히 불가능하게(Very hard to find) 만드는 것"이 암호학의 목표입니다.

Birthday Paradox (생일 역설) ★기말고사 출제 1순위★

그렇다면 충돌을 찾기 어렵게 하려면 해시 길이를 얼마나 늘려야 할까요? 여기서 직관을 완전히 벗어나는 통계학적 마법인 Birthday Paradox가 등장합니다.

• 생일 문제의 직관: 1년은 365일입니다. 방 안에 사람이 몇 명 모여야 생일이 같은 두 사람이 나올 확률이 50%가 될까요? 직관적으로는 365명의 절반인 180명쯤 필요할 것 같지만, 실제 수학 공식으로 계산해 보면 고작 23명만 있으면 확률이 50%를 넘습니다.

확률식 증명:

• 2명이 생일이 다를 확률: $1 - \frac{1}{365}$
• 3명이 모두 생일이 다를 확률: $(1 - \frac{1}{365}) \cdot (1 - \frac{2}{365})$
• $t$명일 때 충돌이 없을 확률 공식:
  $P = \prod_{i=1}^{t-1} \left(1 - \frac{i}{365}\right)$
• 여기에 $t=23$을 넣으면 확률이 약 50%로 뚝 떨어집니다.

암호학에의 적용 (Birthday Attack)

이 생일 역설을 365일 대신 해시 공간인 $2^n$ 에 대입해 봅시다.

• 해시 함수의 출력값이 $n$ bits라면, 전체 해시 공간은 $2^n$ 개입니다.

• 해커가 충돌하는 쌍$(x_1, x_2)$을 찾기 위해 $2^n$ 번을 다 시도할 필요가 없습니다. 생일 역설에 의해, 대략 $\sqrt{2^n} = 2^{n/2}$ 번만 무작위로 찍어보면 50% 이상의 확률로 충돌을 찾아냅니다.

• 결론 (보안 기준):
  만약 160 bits 길이의 해시 함수를 쓴다면, 해커는 $2^{160}$ 번이 아니라 고작 $2^{80}$ steps만 연산하면 충돌을 찾아낼 수 있습니다.
  $\implies$ "해시 함수의 실제 보안 수준(Security Level)은 출력 비트 길이의 정확히 절반($n/2$)밖에 되지 않는다."