네트워크 통신에서의 데이터 무결성 검사 ··· Checksum

INTRO

누구나 컴퓨터는 0과 1로 이루어져 있다는 이야기를 들어본 적이 있을 것이다. 실제로 모든 디지털 정보는 0과 1의 조합을 통해 표현된다. 우리가 어떤 문자를 이용해 정보를 기록하는 것과 같은 이치로 볼 수 있는데, 그 이해를 위해 두 가지 간단한 예를 들어보겠다.

먼저, 사람이 사용하는 문장을 0과 1로 바꾸어보자. 만약 a부터 e까지 다섯 개의 알파벳을 a: 000 / b: 001 / c: 01 / d: 10 / e: 11 와 같이 대응시킨다면, ‘abbdca’라는 문장은 ‘0000010011001000’로, 거꾸로 ‘0000010011001000’라는 문장은 위 대응 관계에 근거하여 ‘abbdca’로 유일하게 해석됨을 직접 확인할 수 있다.

이번에는 어떤 명령들을 0과 1로 나타내보자. 4가지 명령 ‘앉아’, ‘일어서’, ‘왼손’, ‘오른손’을 최대한 짧은 길이의 문장으로 겹치지 않게 표현하기 위해선 최소 4가지의 경우를 나타낼 수 있는 0과 1의 조합을 생각해야한다. 이 경우에는 2-bit 만을 이용하여 00, 01, 10, 11 네 가지 경우를 각 명령에 대응 시킬 수 있으며, 해석하는 입장에서는 각 bit의 값을 보고 즉각 어떤 명령인지 알 수 있을 것이다.

우리가 매일 사용하는 전자기기들은 매 순간 이러한 문장들을 저장하고, 컴퓨터의 중추 CPU에서는 0과 1로 표현된 정해진 길이의 명령들을 1초에 수억번에서 수십억번 가까이 처리하고 있다. 특히 전자기기가 일반인들에게 널리 보급되고, 모든 분야에서 컴퓨터가 사용되고 있으며, 네트워크가 상상할 수 없는 규모로 확장된 지금 사회에선 매 순간 엄청난 양의 정보들이 이동하고 있다.

여기서 한 가지 의문이 든다. 0과 1로만 이루어진 정보를 무선 통신으로 주고 받는데, 우리의 스마트폰과 노트북은 지구 반대편에서 보낸 정보 조차 한치의 오차 없이 받아낸다. 데이터의 결함은 그 규모에 상관 없이 큰 골칫거리인게, 위에서 예로 든 ‘0000010011001000’를 전송하는 도중 통신의 장애로 인해 ‘0000000011001000’으로 받아진다면 그 의미는 ‘abbdca’가 아닌 ‘aabdca’로 완전히 다른 뜻이 되어버린다. 전송하는 문장이 어떤 명령이라면 시스템 자체에 결함이 생기는 것이다.

하지만 당장 비가 오는 날 축구 생중계를 볼 때만 해도 통신 상태가 불안정해 TV화면이 자주 끊기는데, 네트워크 통신에서는 어떻게 아무 결함 없이 데이터가 전송될까? 이를 해결하는 단순하지만 강력한 방법, 체크섬(checksum)을 소개하려고 한다.

Checksum이란

체크섬은 중복 검사의 한 형태로, 수신한 자료의 무결성을 보장하려는 하나의 시도라 할 수 있다. 그 형태는 전송하려는 데이터를 더하여 얻은 값에 정해진 비트 수의 모듈라 연산을 취함으로서 결정되는 bit-string이며, 발신하는 입장에서는 raw-data에 checksum을 이어붙여 만들어진 새로운 데이터를 전송한다.

위 그림을 보면 이해에 큰 도움이 될 것이다. Pre-code는 어떤 작업(실행)을 위해 필요한 필수 정보들이라 생각하면 되고, 실질적으로 해석해야 할 raw-data에 대해서 어떤 함수 f를 통해 생성되는 bit-string이 checksum이며, 이 파일의 꼬리에 checksum이 붙는 형태이다.

Checksum의 동작

크게 생성 함수 $f$에 대해서, 그리고 checksum을 통해 어떻게 무결성이 검증되는지 이 두 가지를 설명하려 한다. 방법만 보았을 땐 둘 다 굉장히 간단하다.

Checksum의 생성

흔히 나열된 데이터를 더하여 체크섬 숫자를 얻고, 이 숫자를 정해진 수로 나누어 그 나머지를 checksum으로 지정한다. 간단하게 예를 들어보겠다. 우리는 지금 32-bit(8-byte) 길이의 데이터에 대해 1-byte checksum을 생성하려고 한다. 32-bit data를 $m$이라 하고, 이 값은 $A267CBF3_{(16)}$이라 하자. 각 byte를 모두 더하면 $43_{(16)}$이 된다. 이때 checksum은 1-byte 크기이므로 $3_{(16)}$, 즉 $0011_{(2)}$이 될 것이다.

식으로 나타내면, $f(m) = c$ where $m = A267CBF3_{(16)}$, $c = 0011_{(2)}$

무결성 검증

수신한 메시지에서 raw-data와 checksum에 해당하는 bit-string을 각각 $m’$, $c’$이라 하자. 이때 checksum 생성 함수 $f$는 서로 약속되어 있다. 만약 $f(m’) = c’$이면, 메시지의 변조나 누락이 없다고 판단한다. 데이터의 변조는 크게 두 가지 케이스로 나뉜다.

1. 전송 과정에서 발생하는 물리적인 장애로 인한 변조
2. 의도적인 데이터 조작

여기까지 납득했다면 checksum은 1.의 대안으로 등장했다는 것을 알 수 있다. 2.의 경우 프로토콜의 암호화를 통해 극복한다. 이 이야기를 갑자기 한 이유는 단순하게 정의된 $f$에 대해 만들어진 $f(m’)$과 주어진 $c’$값의 비교 만으로 어떻게 무결성이 보장되는지 설명하기 위함이다.

$m’$은 어떤 이유로 인해 $m$(송신 raw-data)의 bit들이 변조된 bit-string이고, $c’$도 마찬가지의 이유로 변조되었을 가능성이 존재한다. 이 때 checksum이 1-bit라면 $m=m’$이 아닌데도 $f(m’)=c’$ 이 될 확률이 굉장히 높을 수 있다. 하지만, checksum의 bit를 하나 늘려 2-bit checksum으로 만들어버리면, 그 확률이 크게 감소한다. 구체적으로는, checksum bit가 2배로 늘어날 때마다 ‘$m \ne m’$이면서 $f(m’)=c’$일 확률’은 logarithmic하게 감소한다.

Checksum 생성 함수 $f$의 특징을 고려하여 경우를 따져보면 쉽게 그 이유를 확인할 수 있는데, 글로만 보아선 크게 와닿지 않으므로 직접 간단한 테스트를 해보았다. (10000회)

0과 1로 이루어진 임의의 문장을 생성하고, 각 bit에 대해 동일하게 변조될 확률을 부여한다. 이를 통해 각 케이스 당 10번, 그리고 각 시도 당 10000번 $f(m’)=c’$여부를 확인하여 확률을 도출해냈다. Checksum bit를 2배로 늘려가며 같은 시행을 총 4번 반복하였고, 이를 통해 값들이 서로 지수적인 관계를 가진다는 것을 보이려했다.

2017학년도 1학기에 해보았던 것이라 구체적으로 설정했던 $m$의 length와 각 bit의 변조 확률은 기억나지 않는다. (아쉽게도 소스 코드를 폐기한듯..) 하지만 위 실험 결과로 미루어 보아 위에서 강조한 내용이 맞는 것을 확인할 수 있다..!

즉, 어떤 메시지를 수신한 후, 그에 해당하는 $m’$과 $c’$에 대해 $f(m’)=c’$이 아닐경우 이를 reject하고 다시 같은 요청을 보내는데, 변조된 메시지가 이 과정을 통과할 가능성은 checksum의 길이에 따라 급격히 줄어드는 것이다.

실제로 인터넷 통신 시스템이나 마이크로프로세서 시스템 내부 명령에서의 오류 검증에 checksum이 사용되며, 그 정확성은 확률로서 보장한다. 이런 간단한 방식으로 완전한 데이터 통신을 보장할 수 있다는 점이 실로 놀랍다! 관심있는 사람은 확률을 통해 정확성을 보장하는 비슷한 방식의 영지식 증명 프로토콜(ZKP)도 함께 살펴보면 좋을 것 같다.