기술 포스트
체크섬 계산 방법
체크섬은 다양한 유형으로 데이터 통신 프로토콜에서 널리 활용되며, 메시지 수신자가 전송 중 데이터 손상 여부를 신속하고 간편하게 확인할 수 있도록 합니다. 예를 들어, 메시지의 모든 바이트를 더했을 때 그 합이 (오버플로를 무시하고) 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진수 입력값을 두 자리(니블 2개) 단위로 분리합니다. 이 정규식은 "임의의 문자 다음에 임의의 문자가 오는" 패턴(점 두 개의 의미)을 전체 문자열에 걸쳐 전역적으로 검색(g의 의미)합니다. 결과는 배열로 반환되며, s, 두 자리 16진수 값으로 구성됩니다.
5번째 줄에서는 루프를 시작합니다( forEach 반복 구문 사용). 이 루프에서 두 니블(nibble)로 구성된 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(Longitudinal Redundancy Check)는 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) 해시 함수를 사용해야 합니다. 흔히 SHA-1이나 MD5와 같은 암호화 해시가 사용되지만, 이러한 알고리즘은 연산 부하가 크며 많은 상황에서 과도한 수준의 방법으로 간주될 수 있습니다.
연산 오버헤드와 신뢰성 간의 적절한 균형점은 순환 중복 검사(Cyclic Redundancy Check, CRC)에서 찾을 수 있습니다. CRC는 다양한 버전이 존재하지만, 아래에 설명된 16비트 CRC는 짧은 메시지(약 4킬로바이트 이하)에 충분하며 널리 사용됩니다.
CRC는 흥미로운 주제이지만, 여기서 포괄적으로 다루기에는 지면이 부족합니다. (Google을 참고하시기 바랍니다.) 실용적인 관점에서 간략히 설명하자면, 2바이트 CRC는 데이터 내 무작위 비트 오류에 대한 민감도가 매우 높으며, 다수의 비트 오류가 포함된 데이터에서 오탐(false positive)이 발생할 가능성도 낮습니다. 이러한 특성 덕분에, 그리고 하드웨어 및 소프트웨어로 구현하기 쉽고 매우 적은 메모리에서 빠르게 실행된다는 장점으로 인해, CRC는 스토리지 디스크 드라이버(디스크 오류 감지에 흔히 사용), 모뎀, 소형 전자 기기 등 다양한 데이터 통신 환경에서 폭넓게 활용됩니다. ID TECH의 ViVOpay 시리즈 신용카드 리더기도 여기에 포함됩니다.
아래 JavaScript 코드는 16비트 CRC 값(16진수 ASCII의 4개 니블로 반환)을 계산하는 방법을 보여줍니다.
CRC는 다음과 같이 설명할 수 있는 해시 알고리즘을 구현합니다.
- 시작 crc 값을 0xFFFF로 설정합니다 — 10번째 줄
- 입력 데이터에서 1바이트(8비트 숫자)를 가져옵니다 — 13번째 줄
- 기존 crc 값을 오른쪽으로 8비트 시프트합니다 — 14번째 줄
- 오른쪽으로 시프트된 crc와 입력 바이트를 XOR 연산합니다 — 14번째 줄
- 결과값 j(하위 8비트만 사용)를 테이블 오프셋으로 활용하여, crcTable — 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개의 영(null) 바이트로 구성된 문자열을 예로 들어 보겠습니다. 이 문자열의 LRC 값은 0이 되고, 체크섬 역시 당연히 0이 됩니다. 그러나 CRC 값은 E139가 됩니다.
입력값을 역순으로 바꾸면 원래 순서의 입력값과 전혀 다른 CRC가 산출된다는 사실은 어렵지 않게 납득할 수 있을 것입니다. (LRC나 체크섬에서는 그렇지 않았습니다.) CRC는 교환 법칙이 성립하지 않는데, 이는 모든 것을 왼쪽으로 시프트하기 전에 CRC의 상위 8비트를 입력 바이트와 XOR 연산하는 방식 때문입니다. 이는 암호 블록 체이닝(cipher block chaining) 의 동작 방식과 유사하지만, 이 경우에는 "암호 블록" 크기가 8비트입니다.
CRC는 단방향 해시이지만, 엄밀한 의미에서 암호화 해시는 아닙니다. 데이터에 덧붙이면 변조된 데이터가 원하는 최종 CRC를 산출하게 만드는 "보정값"을 비교적 쉽게 계산할 수 있기 때문입니다. (이른바 암호화 해시에서는 변조된 데이터 블록을 원하는 해시로 역보정할 "보정 인수"를 계산하기가 매우 어렵습니다.) 따라서 CRC는 의도치 않은 데이터 손상을 감지하는 용도에 적합합니다.
데이터 패킷의 손상 여부를 모니터링하는 데 사용할 수 있는 "무결성 검사" 알고리즘은 다양합니다. 경우에 따라서는 단순한 체크섬이나 LRC로 충분할 수도 있습니다. 그러나 상당한 양의 데이터를 처리하면서 데이터 무결성에 대한 엄격한 요건이 요구되는 상황에서는 "선형 합동 생성기(linear congruential generator)" 방식의 해시를 검토하는 것이 사실상 불가피합니다. CRC 계열 알고리즘은 우수한 무결성 판별력과 함께 구현 용이성, 빠른 실행 속도, 낮은 메모리 요구사항을 균형 있게 갖추도록 오랜 기간 정밀하게 조율되고 최적화되어 왔습니다. 이 덕분에 CRC는 하드 드라이브부터 신용카드 리더기에 이르기까지 다양한 데이터 검증 시나리오에서 폭넓게 활용되고 있습니다.