체크섬

3. 산출 방법

인터넷과 같은 통신 시스템에서 데이터 전송 중 발생하는 오류를 검증하는 중요한 방법으로 사용된다. 특히 TCP/IP, 이더넷 프레임의 MAC 계층 등 여러 통신 계층에서 오류 검증을 위해 체크섬을 활용한다. 데이터 송신 측에서는 미리 정해진 방식(예: 특정 다항식)에 따라 체크섬 값을 계산하여 데이터의 헤더 부분에 포함시켜 전송한다. 데이터를 수신한 측에서는 동일한 방식으로 체크섬을 다시 계산한 후, 수신된 체크섬 값과 비교하여 데이터의 무결성을 확인한다.

체크섬 계산은 필요에 따라 하드웨어를 이용하거나 소프트웨어적으로 구현할 수 있다. 어떤 방식을 사용할지는 개발자가 시스템의 특성과 요구 사항에 따라 결정한다. 일반적으로 TCP/IP와 같이 상대적으로 상위 계층의 프로토콜에서는 소프트웨어적인 방법이 주로 사용되며, 물리 계층이나 데이터 링크 계층과 같은 하위 계층으로 갈수록 하드웨어적인 구현에 의존하는 경향이 있다.

가장 기본적인 체크섬 계산 방법은 데이터를 일정한 크기의 단위인 '워드(word)'로 나누어, 각 워드의 값을 모두 더하는 것이다. 이 총합(sum)의 특정 부분, 예를 들어 가장 하위 비트들로 구성된 1워드를 체크섬 값으로 사용한다. 여기서 1워드를 몇 비트로 정의할지는 구현 방식에 따라 달라질 수 있다 (예: 8비트, 16비트 등).

예를 들어, 1워드를 8비트로 사용하는 경우를 생각해보자. 다음과 같은 16진법으로 표현된 8비트 워드 데이터 열이 있다고 가정한다.

:00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

이 워드들의 총합은 16진수로 78₁₆이다. 이 경우, 가장 단순한 방식으로는 이 합계 값 "78" 자체를 체크섬으로 사용할 수 있다.

이 기본 방식 외에도, 총합에서 어떤 비트 그룹을 최종 체크섬 값으로 선택할지, 또는 계산된 값을 어떻게 추가적으로 처리할지(예: 보수 사용) 등에 따라 다양한 변형된 체크섬 알고리즘이 존재한다.

네트워크를 통해 데이터를 전송할 때, IP 패킷의 헤더 무결성을 검사하기 위한 체크섬 산출 과정은 대표적인 예시이며, 주로 다음과 같은 단계로 이루어진다.

# IP 헤더 내의 체크섬 필드 값을 일단 0으로 설정한다.

# IP 헤더 전체를 16비트 단위로 나누어 각 단위의 값을 모두 더한다. 만약 덧셈 과정에서 자리올림(carry)이 발생하면, 그 자리올림 값을 결과에 다시 더해준다 (1의 보수 덧셈).

# 이렇게 얻어진 합계 값에 대해 1의 보수를 취한다. 이 보수 값이 최종 체크섬 값이 된다.

# 계산된 체크섬 값을 IP 헤더의 체크섬 필드에 기록한 후 패킷을 전송한다.

# 패킷을 수신한 측에서는 IP 헤더 전체(수신된 체크섬 값 포함)를 16비트 단위로 나누어 위의 2단계와 동일한 방식(1의 보수 덧셈)으로 모두 더한다.

# 모든 헤더 정보가 오류 없이 올바르게 수신되었다면, 최종 합계 값은 모든 비트가 1인 값(16진법으로 FFFF)이 되어야 한다. 이는 체크섬 필드에 '체크섬 필드를 0으로 간주하고 계산한 나머지 헤더 합계의 1의 보수'가 들어있기 때문에, 전체 헤더(체크섬 필드 포함)를 1의 보수 덧셈으로 합산하면 이론적으로 모든 비트가 1이 되기 때문이다. (또는 이 합계에 다시 1의 보수를 취하면 0이 된다.)

Intel HEX 형식과 같이 ROM 데이터를 표현하거나 전송할 때 사용되는 체크섬 방식도 있다. 이 경우, 보통 데이터를 8비트 단위로 모두 더한 후, 그 합계의 특정 비트(예: 하위 8비트 또는 32비트)를 사용하거나, 합계의 2의 보수를 사용하는 등 다양한 방식이 적용된다. 예를 들어 데이터가 16진수로 12 34 56 78 이라면, 단순히 8비트 단위로 더한 값은 0x12 + 0x34 + 0x56 + 0x78 = 0x00000114 와 같이 계산될 수 있으며, 실제 체크섬 값은 이 합계를 특정 규칙(예: 하위 8비트만 취하거나, 2의 보수를 취하는 등)에 따라 가공하여 결정된다.

4. 체크섬의 예

단순한 체크섬의 예를 들면 다음과 같다.

• 다음과 같이 4 바이트의 데이터가 있다고 가정한다: 0x25, 0x62, 0x3F, 0x52
• 1 단계: 모든 바이트를 더한다.

• 2 단계: 합계(0x118)에서 캐리 니블(상위 니블 '1')을 버리고 하위 바이트(0x18)를 취한다.
• 3 단계: 0x18에 대한 16(0x100)의 보수를 구한다.

• 원래 데이터의 모든 바이트 합(0x118)과 계산된 체크섬 바이트(0xE8)를 더한다.

• 결과(0x200)에서 캐리 니블을 버리면 0x00이 된다. 이는 데이터 오류가 없음을 의미한다. (단, 오류가 있더라도 우연히 0x00이 될 가능성도 있다.)

5. 종류

체크섬 알고리즘에는 여러 종류가 있으며, 각각 다른 방식과 특징을 가진다.

가장 기본적인 형태 중 하나는 세로 중복 검사 방식으로, 데이터 워드들의 비트별 배타적 논리합(XOR)을 이용한다.^[3] 또 다른 방식으로는 데이터 워드들을 더한 후 2의 보수를 취하는 합의 보수 방식이 있다.^[4]

이러한 단순한 방식들의 한계를 보완하기 위해 데이터의 순서나 위치 정보를 계산에 포함하는 위치 의존적 체크섬(플레처 체크섬, Adler-32, 순환 중복 검사)들이 개발되었다. 이 방식들은 오류 검출 능력이 더 뛰어나다.

특수한 목적으로 설계된 체크섬도 있는데, 예를 들어 이메일 스팸 탐지를 위해 내용이 조금씩 변형된 메시지들을 동일하게 식별하도록 고안된 퍼지 체크섬이 있다.^[5]

5. 1. 패리티 바이트 또는 패리티 워드

5. 2. 합의 보수

5. 3. 위치 의존

5. 4. 퍼지 체크섬

6. 마이크로프로세서 실행 파일 체크섬

프로그램을 만든 후 생성되는 실행 파일은 여러 형태가 존재하지만, 아스키 코드를 기반으로 하는 텍스트 파일 형식이 자주 사용된다. 이러한 파일 형식에서는 정해진 포맷에 따라 각 줄 단위로 데이터 오류를 검증하며, 이를 위해 각 줄의 마지막에 체크섬 숫자를 추가한다. 이 체크섬은 해당 줄의 데이터가 전송이나 저장 과정에서 손상되지 않았는지 확인하는 데 사용된다. 마이크로프로세서 실행 파일에서 사용되는 구체적인 체크섬 구현 방식으로는 인텔 방식이나 모토로라 방식 등이 있다.

6. 1. 인텔 방식

:10010000214601360121470136007EFE09D2190140

:100110002146017EB7C20001FF5F16002148011988

:10012000194E79234623965778239EDA3F01B2CAA7

:100130003F0156702B5E712B722B732146013421C7

:00000001FF

• `:` : 시작 코드 (Start code)
• 첫 두 글자 (예: `10`) : 바이트 수 (Byte count) - 데이터 필드의 바이트 길이 (16진수)
• 다음 네 글자 (예: `0100`) : 주소 (Address) - 데이터가 저장될 메모리 주소 (16진수)
• 다음 두 글자 (예: `00`) : 레코드 유형 (Record type) - 데이터 레코드(00), 파일 끝(01) 등
• 가운데 데이터 부분 (예: `2146...1901`) : 데이터 (Data) - 실제 데이터 바이트 (16진수)
• 마지막 두 글자 (예: `40`) : 체크섬 (Checksum)

6. 2. 모토로라 방식

모토로라 S-record 형식에서 사용하는 체크섬은 각 레코드의 바이트 수, 주소, 데이터 필드의 바이트 값을 모두 더한 후, 그 합계의 1의 보수를 취하여 계산한다. 즉, 모든 바이트 값을 더한 결과의 최하위 바이트(LSB)를 0xFF에서 뺀 값이다.

예를 들어, 위 표의 네 번째 줄 레코드(S111003848656C6C6F20776F726C642E0A0042)를 살펴보자. 이 레코드에서 체크섬 계산에 사용되는 필드는 다음과 같다.

• 바이트 수: 11 (16진수)
• 주소: 0038 (16진수)
• 데이터: 48 65 6C 6C 6F 20 77 6F 72 6C 64 2E 0A 00 (16진수)

7. 변형

체크섬 구현에는 몇 가지 변형이 가능하다. 대표적인 변형 방식으로는 체크섬 필드에 기록하는 값의 차이(합계 또는 보수), 계산 시작 시 초기값 설정 방식, 데이터의 위치 정보 반영 여부 등이 있다.

7. 1. 체크섬 란에 기록하는 값

7. 2. 초기값 문제

7. 3. 위치 의존

8. 신뢰성

체크섬은 계산 방식이 단순한 덧셈에 기반하기 때문에 몇 가지 한계를 가진다. 예를 들어, 데이터 블록 내에서 각 워드(word)의 순서만 바뀌고 내용 자체는 그대로인 경우, 체크섬 값은 변경 전과 동일하게 계산된다. 또한, 다른 종류의 오류가 발생했음에도 우연히 같은 체크섬 값이 나올 확률이 존재하므로, 오류 검출 방법으로서의 신뢰성이 아주 높다고 보기는 어렵다.

체크섬을 포함한 오류 검출 부호는 암호화 해시 함수와는 달리, 데이터의 암호화나 위조 방지를 염두에 두고 설계된 기술이 아니다. 따라서 체크섬은 데이터 전송 과정 등에서 발생할 수 있는 우발적인 오류를 검출하는 데는 유용하지만, 누군가가 의도적으로 데이터를 조작하려는 시도에는 취약하다. 계산 방식이 단순하여, 원래 데이터와 내용은 다르지만 체크섬 값은 동일하게 만드는 것이 비교적 쉽기 때문이다. 예를 들어, '00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F' 데이터의 체크섬 값이 78(16진수)이라고 할 때, 순서를 바꾼 '08 09 0A 0B 0C 0D 0E 0F 00 01 02 03 04 05 06 07' 데이터의 체크섬 값도 동일하게 78(16진수)이 된다.

8. 1. 의도적인 개찬의 예

9. 일반적인 고려 사항

''m''비트 길이의 메시지는 ''m''차원 초입방체의 한 모서리로 볼 수 있다. ''n''비트 체크섬을 생성하는 체크섬 알고리즘은 각 ''m''비트 메시지를 더 큰 (''m'' + ''n'')차원 초입방체의 모서리로 대응시키는 과정이다. 이 초입방체의 2^{''m'' + ''n''}개의 모서리는 수신 가능한 모든 메시지를 나타낸다. 이 중 유효한 수신 메시지, 즉 올바른 체크섬을 가진 메시지는 2^''m''개의 모서리로 이루어진 더 작은 집합을 구성한다.

데이터 전송 중 단일 비트 오류는 유효한 모서리(정확한 메시지와 체크섬)에서 ''m''개의 인접한 모서리 중 하나로 이동하는 것에 해당한다. 만약 ''k''개의 비트에 오류가 발생하면 메시지는 올바른 모서리에서 ''k'' 단계 떨어진 모서리로 이동하게 된다. 좋은 체크섬 알고리즘의 목표는 유효한 모서리들을 서로 최대한 멀리 떨어뜨려, 일반적인 전송 오류가 발생했을 때 결과적으로 유효하지 않은 모서리에 도달할 가능성을 높이는 것이다. 이를 통해 오류 검출 확률을 높일 수 있다.

참조

_[1] 웹사이트 Definition of CHECKSUM https://www.merriam-[...] 2022-03-10
_[2] 웹사이트 What Is a Checksum (and Why Should You Care)? https://www.howtogee[...] 2019-09-30
_[3] 웹사이트 Checksums & Integrity Checks https://erg.abdn.ac.[...] 2022-03-11
_[4] 웹사이트 SAE J1708 http://www.kvaser.co[...] Kvaser.com
_[5] 웹사이트 IXhash https://cwiki.apache[...] Apache 2020-01-07
_[6] 간행물
_[7] 간행물
_[8] 간행물