🧮 [최신] Reaction Attack on CKKS — 동형암호 수학은 멀쩡한데, '유효/무효' 한 비트가 비밀키를 넘긴다

논문 정보

한 줄 요약 — "RLWE도 IND-CPA도 깨지지 않았다. 깨진 것은 '클라이언트가 결과를 검사하고 반응한다'는 평범한 습관이다"

CKKS는 실수·복소수 벡터를 암호화한 채로 연산하는 동형암호다. 클라이언트는 서버가 돌려준 암호문을 복호화·디코딩한 뒤, 값이 허용 범위를 벗어나면 재요청하거나 중단한다. 이 논문은 그 1비트짜리 반응(valid / invalid)만 보고도 CKKS의 비밀키 전체를 되찾을 수 있음을 보인다. 열쇠는 두 가지 공개 자료뿐이다 — 공개 암호화 키와 부트스트래핑·계수↔슬롯 변환에 쓰이는 공개 회전키(Galois keys).

공격은 놀랄 만큼 단순하다. 공개키를 (a, b)에서 (a − Δ, b)로 Δ만큼 밀면, 이 암호문은 비밀키 없이도 평문이 Δ·s + e가 된다. 여기에 공개 C2S 변환을 한 번 적용해 비밀키 계수 하나를 슬롯 하나에 정확히 옮긴 뒤, 위상 마스크를 곱해 "이 계수가 0인가?"만 물으면 클라이언트의 유효/무효 응답이 곧 비밀키 계수 하나에 대한 1비트 오라클이 된다. 계수 N개를 훑어 지지집합(support)을 찾고, 0이 아닌 |S|개에 대해 부호를 한 번씩 더 물으면 끝 — 총 N + |S| ≤ 2N 질의, 복구율 100%.

"The attack does not break RLWE or CKKS IND-CPA security. Instead, it exploits the interaction between client-side validity reactions and public homomorphic linear transformations." — 초록

배경 — 왜 '검사하는 클라이언트'가 새로운 공격면인가

• 위협 모델이 IND-CCA도 IND-CPAD도 아니다: 기존 IND-CPAD 연구는 공격자에게 정당한 암호문(정직한 암호화·평가의 출력)만 준다. 이 논문의 공격자는 임의로 조작한 암호문을 복호화시키고, 그 결과에 따른 외부 관찰 가능한 반응을 본다. 두 모델 사이의 빈틈을 겨냥한다.
• 공격이 성립하는 세 조건(논문 3.1절): ① 클라이언트가 평가자가 준 암호문을 복호화·디코딩하고, ② 디코딩된 슬롯에 응용 수준의 허용 범위 검사(예: ‖slots‖∞ ≤ 1)를 적용하며, ③ 그 결과가 재시도·중단·에러·다음 라운드 메시지처럼 서버가 볼 수 있는 행동을 바꾼다. 셋이 동시에 성립할 때만 반응 오라클이 생긴다.
• 실제로 흔한 구성: 암호화 추론에서 로짓을 복호화해 범위 위반을 '잘못된 응답'으로 처리하는 워크플로, 복호화 값을 공개 후속 계산의 입력으로 쓰는 프로토콜, 그리고 이미 명시적 valid/invalid 응답을 모델링한 선행 연구들의 배포 형태.
• 왜 지금까지 안 알려졌나: TFHE·BGV/BFV에 대한 반응 공격은 있었지만, CKKS는 부트스트래핑 키가 비밀키의 암호문을 공개하지 않는다. 그래서 "계수별 누출"이 불가능하다고 여겨졌다. 이 논문은 그 장애물을 공개 C2S 변환으로 우회한다.

핵심 1 — 공개키를 Δ만큼 밀면, 비밀키가 평문이 된다

• 오프라인 1단계(키 시프트): 공개키 pk = (a, b = a·s + e)에서 ct(1) := (a − Δ, b)를 만든다. 복호화하면 b − (a − Δ)·s = Δ·s + e (mod q). 비밀키를 전혀 쓰지 않고, 정상적인 CKKS 암호문 형식을 유지한 채 비밀키 다항식이 그대로 평문 자리에 들어온다.
• 오프라인 2단계(C2S 국소화): 공개 회전키로 정규화 C2S 변환 C2S_Δ를 적용하면, 실수부 암호문의 k번째 슬롯에 s_k, 허수부의 k번째 슬롯에 s_{k+N/2}가 (슬롯 잡음 ≪ τ 범위로) 놓인다. 전형적 분해에서 곱셈 레벨 3~4단을 소모하며, 회전키만 있으면 된다 — 부트스트래핑 전용 키 묶음이 아니어도, 소수 개의 키로도 충분하다.
• 슬롯 마진 분석(Theorem 3.1): 이 공격의 진짜 기술적 기여는 "신호는 임계값을 넘고 잡음은 넘지 않는다"를 계수 영역과 슬롯 영역 사이의 노름 경계로 증명한 것이다. 측정된 C2S 잡음은 (12,35,30)에서 ≤ 2^-12.7, (16,55,50)에서 ≤ 2^-32.0이었고, 진폭 α=4일 때 마진 항은 ≤ 2^-10.7 ≪ τ = 1 — 여유가 크다.

핵심 2 — 한 계수씩 캐묻기: support N번 + sign |S|번

• Phase 1 · support (N회): 슬롯 k만 α로 채운 원-핫 마스크 π(k,α)를 국소화된 암호문에 곱한다. 대상 계수가 0이면 슬롯에는 잡음만 남아 ‖·‖∞ < τ → 클라이언트는 valid. 계수가 ±1이면 크기 α의 신호가 서서 > τ → invalid. 즉 질의 하나가 "이 계수가 0인가?"에 대한 정확한 답이 된다. k와 β∈{R,I}를 모두 훑으면 정확히 N번.
• Phase 2 · sign (|S|회): 0이 아님이 확인된 계수에 대해, 마스크를 한 번 더 빼면 슬롯 신호가 α(s−1)이 된다. s=+1이면 0(valid), s=−1이면 −2α(invalid). 부호가 한 번에 갈린다.
• 재사용 필터를 무력화: 매 질의마다 새로운 영(0) 암호화를 더해 재무작위화한다. 제출되는 암호문은 RLWE 가정 아래 새 암호문과 계산적으로 구분 불가능하고, 질의 간 상관도 없다. "고정 암호문을 조금씩 변형하는 패턴"을 잡는 방어가 통하지 않는다.
• 부호화 키도 필요 없다: 모든 질의의 곱셈은 평문 마스크와의 곱이라 relinearization key가 필요 없다. 공격 표면이 더 좁아진다.

핵심 3 — 숫자로 본 결과 (Lattigo v6.2.0, 단일 스레드)

• 100% 복구, 예외 없음: 160회 실행·총 300만 회 이상의 오라클 질의에서 모든 계수를 정확히 복구했고, 반응 오라클의 오탐/미탐은 0이었다. 질의 수는 이론값 N + |S| ≈ 1.667N을 그대로 따라간다.
• 하한에 거의 붙었다: 균등 삼진 키의 평균 엔트로피 H₂/₃(s) ≈ 1.585N 대비 1.05배. 즉 "정보이론적으로 가능한 최소 질의 수"의 5% 이내다. 초록의 O(H) 주장이 실측으로 확인된 셈.
• 키 분포를 바꿔도: 고정 해밍웨이트(h ∈ {128,192,256}), Bernoulli 희소(p ∈ {1/3,1/2,2/3,0.9}), 절단 이산 가우시안(σ=3.2, S=20)까지 515회 전부 복구. Bernoulli p=1/2는 하한 대비 1.000배로 사실상 tight.
• 희소 키는 더 빠르다: 이분 기반 교집합 탐색으로 support를 O(h log(N/h))에 찾고, 남은 부호는 2h+1 차원 LLL로 푼다. (log N, h) = (16,128)에서 1,801 질의 — 기준 공격의 65,664 질의 대비 36배 감소. LLL 시간은 h=32에서 0.4초, h=64에서 3.3초, h=128에서 25분.
• 남은 격자 난이도: Lattice Estimator 기준 축소된 인스턴스의 비트 비용은 h=32에서 33.1비트, h=1,024에서 43.2비트 — 표준 128비트 보안에 한참 못 미친다. "질의 수는 최적이지만 마지막 격자 문제는 원래 약했다"는 점이 이 공격을 실용적으로 만든다.

왜 중요한가 — '암호가 안전하다'와 '배포가 안전하다'는 다른 말이다

• 프리미티브는 무죄: RLWE도, CKKS의 IND-CPA도 깨지지 않았다. 무너진 것은 프로토콜 계층 — 복호화 결과를 검사하고 그 결과를 외부에 노출하는 인터페이스다. "수학적으로 안전하니 구현도 안전하다"는 추론이 성립하지 않는 전형적 사례.
• CKKS 고유의 새 경로: TFHE/BGV의 반응 공격은 부트스트래핑 키가 비밀키 비트의 암호문을 공개한다는 점을 이용했다. CKKS에는 그런 공개가 없지만, 공개 C2S 변환 + 1비트 유효성 응답만으로 같은 일이 가능함을 처음 보였다.
• 완화가 까다롭다: ① 응답 표준화 — 검사 결과와 무관하게 항상 같은 응답을 돌려주고 실패는 내부에서 처리(가장 실용적). ② 키 단위 반응 모니터링 — 공격은 질의마다 높은 확률로 거부를 유도하므로 질의량·거부율이 자연스러운 탐지 신호가 된다. ③ 노이즈 smudging은 α=4·τ=1 구조에서 정직한 출력까지 거부하게 되어 사실상 불가능하고, 링 교체도 성능만 잃을 뿐 근본 방어가 아니다.
• 한계: 세 조건이 모두 성립하는 배포에만 적용된다. 클라이언트가 정당한 암호문만 복호화하거나, 검사 결과가 외부에 전혀 드러나지 않으면 표면 자체가 없다. 또한 논문은 키 복구까지이며, 그 키로 무엇을 할 수 있는지는 응용·프로토콜에 달렸다. IND-CPAD식 노이즈 플러딩이 걸린 변형에 대한 완전한 분석은 향후 과제로 남겨두었다.
• 연구 윤리: 공격 코드는 Lattigo 기반 재현 아티팩트로 공개되어 있으나, 대상은 공개 라이브러리의 파라미터·프로토콜 계층이며 취약한 실서비스나 개인 키를 겨냥하지 않는다. 이 글은 방어 설계를 위한 분석으로만 읽어야 한다.

출처

• 논문: Song Bian, Hyeongmin Choe, Jiseung Kim, Changmin Lee, Reaction Attack on CKKS Deployments with Asymptotically Optimal Query Complexity, arXiv:2610.21127 (cs.CR), 2026-10-15 · IEEE S&P 2027 — arXiv abs · PDF
• 아티팩트: JiseungKim90/reaction-attack (Go 1.24 · Lattigo v6.2.0 · MIT) — 파라미터 스윕 스크립트 포함
• 함께 읽기:
  • 2026-09-21 On the Security of Public Key Protocols: Dolev–Yao 모델 — "암호 프리미티브가 아니라 프로토콜을 공격 대상으로 놓은" 최초의 형식화. 이 논문의 정확한 사상적 출발점.
  • 2026-08-31 Timing Attacks: 관측 가능한 응답 시간이 곧 오라클이 된 사례. 여기서는 응답 시간 대신 valid/invalid 1비트가 오라클이 된다.
  • 2026-10-07 Differential Power Analysis: 물리적 누출(전력)을 통계로 증폭해 키를 캐낸 고전. "구현·배포 계층의 누출"이라는 같은 계열.
  • 2026-09-04 Differential Cryptanalysis of DES: 암호 분석의 또 다른 축 — 수학적 구조를 공격하는 쪽과, 이 논문처럼 프로토콜의 반응을 공격하는 쪽의 대비.