비트 균형 (Bit Balance)

비트 균형(bit balance)은 비트열이나 불 함수의 출력에서 1과 0이 같은 개수로 나타나는 성질입니다. 암호학에서는 특히 n비트 입력의 모든 경우 2ⁿ개 가운데 정확히 절반(2ⁿ⁻¹개)에서 1을 내는 불 함수를 균형 함수(balanced Boolean function)라고 부르며, 이것이 S-box와 키 스트림 설계의 기본 조건입니다.

자세히 알아보기

출력이 0 쪽이나 1 쪽으로 치우친 함수는 공격자에게 단서를 줍니다. 예를 들어 어떤 함수가 입력의 75%에서 0을 낸다면, 공격자는 출력을 보지 않고도 0이라고 추측해 맞힐 확률이 높아지고, 그 치우침을 통계적으로 이용해 키를 좁혀 갈 수 있습니다. 균형은 이런 가장 단순한 통계적 편향을 없애는 최소 조건입니다. 다만 균형만으로 안전해지지는 않으며, 비선형성·상관 면역성 같은 다른 성질과 함께 평가합니다.

블록 암호의 S-box는 여러 출력 비트를 내는 매핑입니다. S-box가 전단사(입력과 출력의 수가 같고 겹치지 않음)이면 출력 비트 하나하나와 그 (0이 아닌) 선형 결합이 모두 균형 함수가 됩니다. 그래서 AES처럼 가역 S-box를 쓰는 설계는 이 조건을 자동으로 만족합니다.

의사난수 수열에서도 같은 개념을 씁니다. n단 선형 되먹임 시프트 레지스터(LFSR)가 만드는 최대 주기 수열(m-수열)은 한 주기 2ⁿ−1비트 안에 1이 2ⁿ⁻¹개, 0이 2ⁿ⁻¹−1개 들어 있어 거의 완벽하게 균형을 이룹니다. 난수 생성기를 검사하는 NIST SP 800-22의 첫 번째 시험인 빈도(모노비트) 시험도 수열 전체에서 1과 0의 비율이 절반에 충분히 가까운지를 봅니다.

균형이 잘 맞은 무작위 데이터는 정보량(엔트로피)이 최대에 가깝기 때문에 오히려 압축이 잘 되지 않습니다. 비트 균형은 압축률을 높이는 기법이 아닙니다. 통신 분야에는 별도로 8b/10b 같은 선로 부호가 1과 0의 개수를 맞추어 직류 성분을 없애는 DC 균형이 있는데, 목적은 신호를 안정시키는 것으로 암호학의 균형과는 다릅니다.

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

지갑의 개인키와 시드 구문은 난수 생성기에서 나옵니다. 생성기 출력이 한쪽으로 치우치면 가능한 키의 범위가 줄어들어 추측 공격에 약해지므로, 하드웨어 지갑과 라이브러리는 표준 난수 검사로 이런 편향을 점검합니다. 해시 함수와 블록 암호 내부의 S-box·혼합 함수도 균형 조건을 바탕으로 설계됩니다.

쉽게 말하면

동전을 던질 때마다 앞면과 뒷면이 반반씩 나와야 공정한 동전입니다. 열 번 중 일곱 번 앞면이 나오는 동전으로는 내기를 하면 안 되듯이, 출력이 한쪽으로 기우는 함수는 비밀을 지키는 데 쓰기 어렵습니다.

예시

두 비트의 XOR 함수 x₁ ⊕ x₂는 입력 00, 01, 10, 11에 대해 0, 1, 1, 0을 내므로 1과 0이 각각 두 번씩인 균형 함수입니다. AND 함수 x₁ · x₂는 0, 0, 0, 1을 내어 1이 한 번뿐이므로 균형 함수가 아닙니다.