44. 재생 방지 슬라이딩 윈도우 비트맵의 시프트·경계 결함 (C#)
난이도 상해설 — 재생 방지 슬라이딩 윈도우 비트맵의 시프트·경계 결함 (C#)
난이도: 상
요약
anti-replay 비트맵의 두 경계가 잘못됐다. (A) 윈도우를 64칸 이상 전진시킬 때 << 의 시프트 카운트가 64 이상이면 C#은 이를 mod 64 로 마스킹하므로, "비트맵을 통째로 밀어 비운다"는 의도와 달리 예전 비트가 엉뚱한 위치에 남는다. (B) 윈도우보다 오래된 seq 를 재생 판별 없이 무조건 수용한다 → 오래된 패킷 재생 공격이 그대로 통과한다.
문제점
분류 태그: 시프트 카운트 범위 초과(정의된-그러나-틀린 동작) / 경계 판정 반전 (재생 취약점)
결함 (B) — 오래된 패킷 무조건 수용 (요구사항 3 위반, 보안 취약점)
diff = _highest - seq >= 64 이면 그 seq 는 윈도우 밖이라 "이미 받았는지"를 알 수 없다. 안전한 정책은 거부다(중복일 수도 있으므로). 그런데 코드는 return true 로 수용한다.
- 증상: 공격자가 오래 전 캡처한 유효 패킷(seq 가 현재보다 64 이상 뒤처짐)을 재전송하면 매번 통과한다. 이동/공격/결제 커맨드 재생으로 상태 조작 가능.
- 재현: 현재
_highest = 1000. 공격자가 과거 seq=100 패킷을 반복 전송 → 매번diff=900>=64→ 매번true.
결함 (A) — 64칸 이상 전진 시 비트맵 미클리어 (요구사항 4 위반)
shift = seq - _highest 가 64 이상일 때 _bitmap << (int)shift 는 C# 명세상 shift & 63 만큼만 시프트한다(64비트 피연산자의 시프트 카운트는 하위 6비트만 사용).
- 예:
_highest=10, _bitmap=..., 새 seq=100 →shift=90. 의도는 "윈도우가 90칸 전진했으니 예전 비트는 전부 윈도우 밖 → 비트맵을 0으로 밀고 비트0만 세팅". 그러나90 & 63 = 26이므로 26칸만 시프트되어, 실제로는 새 윈도우 밖이어야 할 옛 수신 기록이 새 윈도우 안 비트로 둔갑한다. - 증상: 큰 점프 이후, 새 윈도우 범위 안의 어떤 seq 들이 "이미 받았다"고 잘못 판정되어 정상 패킷이 재생으로 오탐 거부된다(요구사항 1의 역방향 오류). 게임에서는 점프 직후 일부 입력이 조용히 씹힌다.
수정안
시프트가 64 이상이면 비트맵을 통째로 비우고, 오래된 패킷은 거부한다.
public bool CheckAndUpdate(ulong seq)
{
if (!_init) { _init = true; _highest = seq; _bitmap = 1UL; return true; }
if (seq > _highest)
{
ulong shift = seq - _highest;
if (shift >= 64) _bitmap = 0; // 윈도우 통째 이동: 전부 클리어
else _bitmap <<= (int)shift; // 안전한 범위 시프트
_bitmap |= 1UL; // 새 최고 seq 표시
_highest = seq;
return true;
}
else
{
ulong diff = _highest - seq;
if (diff >= 64) return false; // 윈도우 밖은 판별 불가 → 거부(안전)
ulong mask = 1UL << (int)diff;
if ((_bitmap & mask) != 0) return false; // 재생/중복
_bitmap |= mask;
return true;
}
}
두 가지 원칙: (1) 시프트 카운트가 워드 폭 이상이면 언어가 "0으로 민다"고 보장하지 않으므로 명시적으로 분기한다. (2) 재생 판별이 불가능한 구간은 수용이 아니라 거부가 안전한 기본값이다.
더 나은 설계
- 윈도우 폭을 워드로 파라미터화:
1UL << diff계산 전 항상diff < WINDOW를 확정. 폭을 256/1024로 키우려면ulong[]배열 비트맵으로 확장(워드/비트 인덱스 분리). - seq 래핑 처리: 실제로는 64비트 seq도 세션이 극히 길면 랩할 수 있고, 32비트 seq라면 시리얼 산술(RFC 1982)로 대소를 판정해야 한다.
- 암호 계층과 결합: AEAD nonce 로 seq 를 쓰면 재생 방지와 무결성이 함께 온다. anti-replay 는 복호화·인증 성공 이후에만 갱신해야 위조 seq 로 윈도우가 오염되지 않는다.
- 트레이드오프: 윈도우가 넓을수록 재정렬 허용폭↑, 메모리·검사비용↑. 게임 트래픽의 실제 재정렬 분포에 맞춰 폭을 정한다.
면접 포인트
- C#/C++에서
x << n의 n 이 피연산자 폭 이상일 때 각각 어떻게 되는가(마스킹 vs UB)와, 왜 명시 분기가 필요한가. - anti-replay 에서 "판별 불가 구간"의 안전한 기본값이 왜 거부인가.
- 재생 검사를 복호화·인증 성공 뒤로 미뤄야 하는 이유.
해설 — 재생 방지 슬라이딩 윈도우 비트맵의 시프트 UB·경계 결함 (C++)
난이도: 상
요약
anti-replay 비트맵의 두 결함. (A) 윈도우를 64칸 이상 전진시킬 때 bitmap_ << shift 에서 shift >= 64 는 정의되지 않은 동작(UB) 이다(부호 없는 정수라도 시프트 카운트 ≥ 폭이면 UB). (B) 윈도우보다 오래된 seq 를 재생 판별 없이 무조건 수용해 재생 공격이 통과한다.
문제점
분류 태그: 시프트 카운트 ≥ 비트폭 UB / 경계 판정 반전(재생 취약점)
결함 (A) — shift >= 64 시 UB
C++ 표준: E1 << E2 에서 E2 >= (E1 의 폭) 이면 동작이 정의되지 않는다. bitmap_ 는 64비트이므로 shift >= 64 는 UB.
- 실제 x86-64에서
shl은 카운트를& 63하지만(그래서 C#과 비슷한 증상으로 보일 수 있음), 이는 이식성 없는 우연이다. 다른 아키텍처/최적화에서는 0, 원래값 유지, 임의값 등 무엇이든 될 수 있고, 컴파일러가 UB를 가정해 코드를 제거·재배열할 수도 있다(-O2에서 분기 삭제 등). - 의도는 "윈도우가 64칸 이상 전진 → 예전 비트는 전부 윈도우 밖 → 비트맵 0으로". UB 경로에서는 옛 수신 기록이 새 윈도우 안 비트로 남아 정상 패킷을 재생으로 오탐 거부한다.
결함 (B) — 오래된 패킷 무조건 수용 (보안 취약점)
diff = highest_ - seq >= 64 인 윈도우 밖 seq 는 중복 여부를 알 수 없으므로 거부가 안전하다. 코드는 return true 로 수용 → 공격자가 과거 캡처 패킷(seq 가 64+ 뒤처짐)을 반복 재전송하면 매번 통과한다.
- 재현:
highest_=1000, 공격자가 seq=100 반복 →diff=900>=64→ 항상true. 이동/스킬/거래 커맨드 재생.
1ULL << diff 는 else 분기에서 diff < 64 가 보장되므로 그 자체는 UB가 아니지만, (B)의 조기 return 때문에 정작 재생 검사에 도달하지 못한다.
수정안
bool checkAndUpdate(std::uint64_t seq)
{
if (!init_) { init_ = true; highest_ = seq; bitmap_ = 1ULL; return true; }
if (seq > highest_)
{
std::uint64_t shift = seq - highest_;
if (shift >= 64) bitmap_ = 0; // UB 회피 + 윈도우 통째 클리어
else bitmap_ <<= shift; // shift ∈ [1,63] 안전
bitmap_ |= 1ULL;
highest_ = seq;
return true;
}
else
{
std::uint64_t diff = highest_ - seq;
if (diff >= 64) return false; // 판별 불가 → 거부(안전)
std::uint64_t mask = 1ULL << diff; // diff ∈ [0,63] 안전
if (bitmap_ & mask) return false; // 재생/중복
bitmap_ |= mask;
return true;
}
}
C++에서는 shift >= 64 분기가 "성능 최적화"가 아니라 UB 제거를 위한 필수다. -fsanitize=undefined 로 시프트 UB를 잡을 수 있다.
더 나은 설계
- 폭 확장 시 배열 비트맵:
std::array<uint64_t, N>로 워드 인덱스(diff / 64)와 비트 인덱스(diff % 64)를 분리. 각 워드 시프트에서 여전히 카운트 범위를 검사. - 32비트 seq 는 시리얼 산술(RFC 1982) 로 대소 비교해 랩어라운드 처리.
- AEAD 통합: seq 를 nonce 로 사용하고, 복호화·인증(태그 검증) 성공 후에만 윈도우를 갱신 — 위조 seq 로 윈도우를 오염시키지 못하게.
- 트레이드오프: 윈도우 폭↑ → 재정렬 허용폭↑·비용↑. UBSan/정적 분석을 CI에 넣어 시프트·오버플로 UB를 상시 차단.
면접 포인트
- C++에서 시프트 카운트 ≥ 비트폭이 왜 UB이며, x86의
& 63동작에 의존하면 안 되는 이유(이식성·최적화 상호작용). - anti-replay 의 "판별 불가 구간" 기본값이 왜 거부여야 하는가.
- 재생 방지 갱신을 인증 성공 이후로 미뤄야 하는 보안적 이유.