구별자 (Distinguisher)

구별자(distinguisher)는 어떤 암호나 해시 함수의 출력을 이상적인 무작위 객체(무작위 순열, 무작위 함수, 균일한 난수열)와 무작위 추측보다 높은 확률로 구별해 내는 알고리즘입니다. 구별자가 존재한다는 것은 그 암호가 이론적으로 기대되는 '무작위처럼 보이는' 성질을 완전히 갖추지 못했다는 뜻입니다.

자세히 알아보기

현대 암호학의 안전성 정의는 대부분 '구별 불가능성'으로 표현됩니다. 예를 들어 블록 암호가 안전하다는 것은 다음 게임에서 공격자가 이기지 못한다는 뜻입니다. 공격자는 상자 하나에 질의를 보낼 수 있는데, 그 상자는 무작위 키로 설정된 실제 암호이거나 진짜 무작위 순열입니다. 공격자(구별자)는 응답을 보고 어느 쪽인지 맞혀야 합니다.

구별자의 성능은 이점(advantage)으로 잽니다. 실제 암호일 때 '암호'라고 답할 확률과 무작위 순열일 때 '암호'라고 답할 확률의 차이의 절댓값입니다. 이점이 현실적인 계산량에서 무시할 만큼 작으면 그 암호는 의사난수 순열(PRP)로서 안전하다고 봅니다.

구별자는 키를 찾아내는 공격보다 약한 결과처럼 보이지만 중요한 경고 신호입니다. 다만 구별자 자체는 암호가 이상적 모델과 다르게 동작한다는 증거일 뿐, 곧바로 키나 평문을 빼낼 수 있다는 뜻은 아니라는 지적(테리 리터 등)도 함께 기억해야 합니다. 많은 키 복구 공격이 구별자에서 출발하며, 구별자가 있으면 그 암호를 쓰는 상위 프로토콜의 안전성 증명이 깨집니다. 차분·선형 암호 분석도 라운드를 줄인 암호에 대한 통계적 구별자를 만든 뒤 마지막 라운드 키를 추측하는 방식으로 작동합니다.

실제 사례

스트림 암호 RC4는 키스트림의 두 번째 바이트가 0이 될 확률이 1/256의 약 두 배라는 편향이 알려져 있어, 출력만 보고 RC4임을 구별할 수 있습니다. 이런 편향들이 누적되어 결국 TLS에서 RC4 사용이 금지되었습니다(RFC 7465, 2015년). AES 같은 현대 블록 암호의 경우, 알려진 구별자는 라운드 수를 줄인 버전에만 존재하고 전체 라운드에 대해서는 현실적인 구별자가 없습니다.

블록체인·암호화폐에서는

지갑의 키 생성, 서명용 논스, 해시 기반 주소 등은 모두 출력이 무작위와 구별되지 않는다는 가정 위에 있습니다. 난수 생성기의 출력에 구별 가능한 편향이 있으면 개인 키나 ECDSA 논스가 예측되어 자금이 탈취될 수 있습니다.

쉽게 말하면

진짜 동전 던지기 기록과 사람이 '무작위인 척' 지어낸 기록을 섞어 놓고, 어느 쪽인지 맞히는 감별사와 같습니다. 감별사가 반반 확률보다 잘 맞힌다면 지어낸 기록에 흔적이 있다는 뜻입니다.