전부 아니면 전무 변환 (All or Nothing Transform, AONT)

전부 아니면 전무 변환(All or Nothing Transform, AONT)은 혼합된 출력 블록 가운데 하나만 빠져도 원래 입력 블록의 어떤 값도 알아낼 수 없도록 설계된 블록 혼합 함수의 개념입니다. 1997년 로널드 리베스트(Ronald Rivest)가 제안했습니다. 기존 블록 암호와 함께 쓰면 무차별 대입 공격의 비용을 메시지의 블록 수만큼 늘리는 효과가 있습니다.

핵심 성질

AONT 자체는 키가 없는 공개된 변환이며, 출력 전체를 가진 사람은 누구나 원래 데이터로 되돌릴 수 있습니다. 그러나 출력 블록을 하나라도 모르면 입력에 대해 사실상 아무 정보도 얻을 수 없습니다. 자물쇠가 여러 개 달린 금고처럼, 하나만 빼고 모두 열어도 내용물은 꺼낼 수 없습니다.

패키지 변환(package transform)

리베스트가 제시한 대표적인 구성은 다음과 같습니다.

1. 무작위 키 K′를 새로 만듭니다.
2. 각 평문 블록 m_i를 c_i = m_i ⊕ E(K′, i)로 바꿉니다.
3. 공개된 고정 키 K₀로 h_i = E(K₀, c_i ⊕ i)를 계산합니다.
4. 마지막 블록으로 K′ ⊕ h₁ ⊕ … ⊕ h_s를 덧붙입니다.

모든 c_i를 알아야 h_i를 모두 계산해 K′를 되찾을 수 있고, K′가 있어야 평문을 복원할 수 있습니다. 이렇게 만든 출력을 다시 일반 블록 암호로 암호화합니다.

무차별 대입 공격에서의 역할

보통의 블록 암호에서는 공격자가 키 후보마다 암호문 블록 하나만 복호화해 보고 맞는지 확인할 수 있습니다. AONT를 거친 데이터에서는 블록 하나만 복호화해서는 아무것도 확인할 수 없으므로, 키 후보마다 모든 블록을 복호화해야 합니다. 그 결과 공격 비용은 메시지의 블록 수만큼 배로 늘어납니다. 이는 키 길이를 늘리는 것과는 다른, 선형적인 강화입니다.

공격자가 출력 블록 일부만 얻은 경우에도 마찬가지입니다. 빠진 블록이 하나라도 있으면 K′를 복원할 수 없으므로, 나머지 블록에서는 원래 평문에 대한 정보를 얻지 못합니다.

응용

• 키 길이가 제한된 환경에서의 보강: 리베스트의 원래 동기는 짧은 키를 써야 하는 환경에서 무차별 대입 비용을 높이는 것이었습니다.
• 분산 저장: 데이터를 AONT로 변환한 뒤 조각을 여러 서버에 나누어 저장하면, 일부 조각만 손에 넣은 쪽은 내용을 알 수 없습니다.
• 공개 키 암호의 패딩: RSA에 쓰이는 OAEP 패딩도 AONT의 성질을 갖는 것으로 분석되었습니다.

한계

• 데이터 크기 증가: 추가 블록(K′ 정보)만큼 출력이 길어집니다.
• 추가 연산: 암호화 전에 변환을 한 번 더 거치므로 처리량이 줄어듭니다.
• 기밀성은 별도: AONT는 키가 없는 변환이므로 그 자체로는 데이터를 숨기지 않으며, 반드시 암호화와 함께 써야 합니다.