기술 포스트
체크섬 계산 방법
다양한 종류의 체크섬은 데이터 통신 프로토콜에서 널리 사용되며, 메시지 수신자가 전송 과정에서 데이터가 손상되었는지 여부를 신속하고 간편하게 확인할 수 있도록 합니다. 메시지의 모든 바이트를 더한 합이 (오버플로를 무시할 경우) 96이라면, 해당 숫자를 메시지 끝에 추가하여 전송합니다. 수신자는 메시지의 첫 N-1바이트에 대해 동일한 합산을 수행한 후, 그 결과를 마지막 바이트와 비교하여 96인지 확인합니다. 결과가 일치하면, 수신자는 전송 과정에서 메시지가 변조되지 않았을 것이라고 판단할 수 있습니다.
실무에서는 다양한 체크섬 기법이 사용되고 있습니다. 그중 가장 널리 쓰이는 세 가지는 일반 체크섬, LRC(종방향 중복 검사), 그리고 CRC(순환 중복 검사)입니다. CRC는 엄밀히 말해 일반적인 의미의 체크섬은 아니며, "선형 합동 생성기" 계열에 속하는 단방향 해시 의 한 예입니다.
앞서 언급했듯이, 이러한 데이터 무결성 검증 기법은 데이터가 손상되었을 "가능성"을 판단하는 데 활용됩니다. 임의 길이의 데이터를 대상으로 하는 경우, 어떤 체크섬 기법도 100% 완벽하게 오류를 검출한다고 보장할 수 없습니다. 다만, 일부 기법이 다른 기법보다 확실히 더 우수한 것은 사실입니다.
JavaScript를 사용하여 LRC, 체크섬, CRC를 계산하는 방법을 살펴보겠습니다.
일반적인 8비트 체크섬은 이름 그대로, 입력값의 모든 바이트를 합산하고 캐리 연산에서 발생하는 오버플로를 버린 결과입니다. JavaScript로 구현하면 다음과 같습니다.
이 함수의 입력값은 "48656C6C6F20776F726C6421"과 같은 형식의 16진수 문자열(헥스 문자열)이어야 합니다. 이 예시에서 해당 값은 ASCII 문자열 "Hello world!"의 16진수 표현입니다. "48656C6C6F20776F726C6421"을 위 함수에 입력하면, 최종 8비트 합산값의 16진수인 "5d"가 출력됩니다.
코드는 매우 간단합니다. 먼저 (3번째 줄에서) 정규 표현식 /../g를 사용하여 16진수 입력을 두 니블 단위로 파싱합니다. 이 정규 표현식은 "임의의 문자 다음에 임의의 문자가 오는" 패턴(두 개의 점이 의미하는 것)에 일치하는 부분 문자열을 전체적으로(g의 의미) 찾습니다. 결과는 배열로 반환되며, s는 두 자리 16진수 값들로 구성됩니다.
5번째 줄에서는 루프를 시작합니다( forEach 반복 구문 사용). 이 루프에서 두 니블로 된 16진수 문자열을 실제로 연산할 수 있는 숫자로 변환합니다. 7번째 줄에서 실제 합산이 이루어집니다. 내부적으로 sum 은 기본적으로 32비트 정수이므로, 최종 값이 255보다 훨씬 커질 수 있습니다. 루프가 끝나면 합계를 8비트 값으로 제한해야 합니다. 이는 9번째 줄에서 255와의 논리적 AND 연산으로 처리됩니다. 동시에, toString() 메서드를 인수 16과 함께 사용하여 16진수로 다시 변환합니다(숫자를 기수 16, 즉 "16진법"으로 표현하겠다는 의미).
10번째 및 11번째 줄에서는 최종 16진수 값이 두 니블인지 확인해야 합니다. JavaScript의 toString(16) 연산은 10 미만의 값에 대해 한 자리 값을 반환합니다. 이 경우 결과 앞에 '0'을 추가해야 합니다.
코드를 직접 테스트해 보려면, 위 코드를 복사하여 JS 콘솔에 붙여넣으세요(Chrome에서는 Shift-Cmd-J로 콘솔을 열 수 있습니다). 그런 다음 함수 외부 맨 아래에 CHECKSUM("48656C6C6F20776F726C6421") 줄을 추가하세요. Enter 키를 누르면 콘솔에 '5d'가 반환값으로 표시되어야 합니다.
LRC를 활용한 체크섬 계산 방법
종방향 중복 검사(LRC)는 8비트 체크섬의 변형으로, 수치 덧셈 대신 XOR 연산을 사용하여 합산을 수행한다는 점에서만 차이가 있습니다.
6번째 줄에서 XOR 자리 대입 연산자(^=)를 확인할 수 있습니다.
XOR 연산은 오버플로가 발생하지 않으므로, AND 연산으로 최종 결과를 8비트로 제한할 필요가 없습니다. 두 니블 길이 여부를 확인한 후 최종 값을 반환하면 됩니다.
위에 제시된 문자열을 사용하여 콘솔에서 코드를 실행하면 '21'이라는 결과값을 얻을 수 있습니다.
체크섬 및 LRC의 한계
체크섬과 LRC 모두 메시지 손상에 대한 강력한 방어 수단으로 볼 수 없습니다. 예를 들어, 원본 메시지("48656C6C6F20776F726C6421")에서 마지막 두 바이트를 6421에서 6520으로 변경한다고 가정해 보겠습니다. 이 경우 LRC와 체크섬 모두 변하지 않습니다. 이는 상위 바이트에서 특정 비트를 ON으로 설정하고, 하위 바이트에서 동일한 위치의 비트를 OFF로 설정함으로써 두 변경사항이 체크섬 계산 시 서로 상쇄되기 때문입니다.
마찬가지로, 메시지를 바이트 단위로 역순으로 뒤집어 21로 시작하고 48로 끝나도록 변경하더라도 LRC와 체크섬은 원본 메시지와 동일하게 유지됩니다. 이는 XOR과 덧셈이 교환 법칙을 따르기 때문입니다. A + B는 항상 B + A와 같습니다.
또한, 8비트 LRC 또는 체크섬이 가질 수 있는 값은 256가지에 불과하므로, 임의로 선택한 다른 메시지와 동일한 LRC(또는 체크섬) 값이 나올 확률이 256분의 1에 달한다는 점도 고려해야 합니다.
일반적으로 체크섬 및 LRC 알고리즘은 쉽게 무력화될 수 있어 메시지 무결성 검사 수단으로서의 신뢰성이 높지 않습니다.
다행히 무결성 검사에 있어 LRC나 체크섬보다 우수한 알고리즘이 존재하지만, 그만큼 연산 오버헤드가 증가한다는 비용이 따릅니다.
CRC를 활용한 체크섬 계산 방법
무결성 검사가 중요한 경우, 일반적으로 비가환 해시(non-commutative hash)를 사용해야 합니다. 흔히 SHA-1이나 MD5와 같은 암호화 해시가 사용되지만, 이는 연산 부하가 크고 많은 상황에서 과도한 방법으로 여겨질 수 있습니다.
연산 부하와 신뢰성 사이의 적절한 균형을 제공하는 방법으로 순환 중복 검사(Cyclic Redundancy Check, CRC)가 있습니다. CRC는 다양한 버전으로 제공되며, 아래에서 설명하는 16비트 CRC는 짧은 메시지(약 4킬로바이트 이하)에 충분하고 널리 사용됩니다.
CRC는 흥미로운 주제이지만, 여기서 포괄적으로 다루기에는 지면이 부족합니다. (자세한 내용은 Google을 참조하십시오.) 실용적인 관점에서 말씀드리자면, 2바이트 CRC는 데이터의 무작위 비트 반전에 매우 민감하게 반응하며, 여러 비트가 동시에 반전되더라도 오탐(false positive)이 발생할 가능성이 낮습니다. 이러한 특성과 더불어 하드웨어 및 소프트웨어로 쉽게 구현할 수 있고, 매우 적은 메모리로 빠르게 동작한다는 장점 덕분에, 스토리지 디스크 드라이버(디스크 오류 감지에 CRC 활용), 모뎀, 소형 전자 기기(ID TECH의 ViVOpay 시리즈 신용카드 리더기 포함) 등 다양한 데이터 통신 환경에서 폭넓게 활용됩니다.
다음 JavaScript 코드는 16비트 CRC 값을 계산하는 방법을 보여줍니다(결과는 4개의 16진수 ASCII 니블로 반환됩니다).
CRC는 다음과 같이 설명할 수 있는 해시 알고리즘을 구현합니다.
- 시작 crc 값을 0xFFFF로 설정합니다 — 10번째 줄
- 입력 데이터에서 1바이트를 가져옵니다(8비트 숫자로) — 13번째 줄
- 기존 crc 값을 오른쪽으로 8비트 시프트합니다 — 14번째 줄
- 오른쪽으로 시프트된 crc 값과 입력 바이트를 XOR 연산합니다 — 14번째 줄
- 결과값 j(하위 8비트만 사용)를 테이블 오프셋으로 활용하여 crcTable 이라는 테이블에서 "대체 바이트(substitution byte)"를 조회합니다 — 15번째 줄
- 현재 crc 값을 왼쪽으로 8비트 시프트한 후, "대체 바이트"와 XOR 연산을 수행합니다 — 15번째 줄
- 다음 입력 바이트를 사용하여 13번째 줄부터 이 과정을 반복합니다
- 모든 입력 처리가 완료되면, 결과값을 0과 XOR하고 CRC의 하위 16비트를 유지합니다 — 17번째 줄
최종 숫자를 정수에서 16진수 문자열로 변환하기 위해 소규모 유틸리티 루틴을 사용합니다:
두 함수(numToHex 및 CRC)를 브라우저의 JS 콘솔에 로드한 후 CRC( "48656C6C6F20776F726C6421" )를 실행하면, "Hello world!" 입력 데이터에 대한 CRC 값으로 'BD22'가 출력되어야 합니다.
연습 삼아, 입력값의 비트 하나를 변경하면 출력이 어떻게 달라지는지 확인해 보시기 바랍니다. 예를 들어, "Hello world!" 문자열을 입력으로 사용하면서 데이터의 마지막 바이트를 21에서 20으로 변경하면, CRC는 'AD03'으로 바뀌며 이는 'BD22'와 전혀 무관한 값입니다. 마지막 두 바이트를 '6520'으로 변경하면 CRC는 '9E32'가 됩니다. (참고로, 이와 동일한 변경은 LRC나 체크섬에는 영향을 미치지 않았습니다.)
10바이트의 제로(널) 값으로 구성된 문자열을 예로 들어 보겠습니다. 이 문자열의 LRC 값은 0이 됩니다. 체크섬도 당연히 0입니다. 그러나 CRC 값은 E139가 됩니다.
입력 데이터의 순서를 뒤집으면 원래 방향의 입력과 전혀 다른 CRC 값이 나온다는 것을 쉽게 확인할 수 있습니다. (LRC나 체크섬에서는 이런 차이가 발생하지 않습니다.) CRC가 교환 법칙을 따르지 않는 이유는, CRC 상위 8비트를 입력 바이트와 XOR 연산한 후 전체를 왼쪽으로 시프트하는 방식 때문입니다. 이는 암호 블록 체이닝(cipher block chaining) 방식과 유사하지만, 이 경우 "암호 블록"의 크기가 8비트라는 점에서 차이가 있습니다.
CRC는 단방향 해시이긴 하지만, 엄밀한 의미의 암호학적 해시는 아닙니다. 특정 데이터를 변조했을 때 원하는 최종 CRC 값이 나오도록 데이터 뒤에 덧붙일 "보정값"을 비교적 쉽게 계산할 수 있기 때문입니다. (암호학적 해시에서는 변조된 데이터 블록을 원하는 해시 값으로 역보정하는 "보정 인자"를 계산하는 것이 매우 어렵습니다.) 따라서 CRC는 의도치 않은 데이터 손상을 탐지하는 용도로 적합합니다.
데이터 패킷의 손상 여부를 모니터링하는 데 사용할 수 있는 "무결성 검사" 알고리즘은 다양합니다. 경우에 따라서는 단순한 체크섬이나 LRC로 충분할 수 있습니다. 그러나 데이터 양이 적지 않고 데이터 무결성에 대한 요구 사항이 엄격한 상황에서는 "선형 합동 생성기(linear congruential generator)" 방식의 해시를 사용하는 것이 거의 필수적입니다. CRC 계열 알고리즘은 우수한 무결성 판별 능력과 구현 용이성, 빠른 실행 속도, 낮은 메모리 요구 사항을 겸비하도록 충분히 검증되고 최적화되어 있습니다. 덕분에 CRC는 하드 드라이브부터 신용카드 리더기에 이르기까지 다양한 데이터 검사 시나리오에서 폭넓게 활용되고 있습니다.