[CRC] Cyclic Redundancy Check: 데이터 전송 오류 검출 코드

CRC(Cyclic Redundancy Check)이란 디지털 데이터의 무결성을 확인하고, 전송 또는 저장 과정에서 발생할 수 있는 우발적인(고의적이지 않은) 오류를 탐지하기 위해 사용되는 에러 탐지 코드입니다. 네트워크 통신 시 패킷의 무결성 확인, HDD나 SSD, RAM에서 데이터를 읽고 쓸 때의 무결성 확인 등에 사용됩니다.

데이터를 전송하기 전 특정 규칙에 따라 주어진 데이터로 CRC 값을 계산해 데이터에 붙여서 전송합니다. 데이터를 전송받은 측은 받은 데이터로 CRC 값을 다시 계산해서 전송받은 CRC 값과 데이터로 다시 계산한 CRC값이 같다면 오류가 없다 판단을 하고 값이 다르다면 데이터 전송 과정에서 noise가 생겨 오류가 발생한 것으로 판단합니다.

이러한 계산 과정이 이진법 기반의 하드웨어에서 구현하기 쉽기 때문에 많은 경우 데이터 전송 시 오류 검출을 위해 CRC를 사용합니다.

이 때 CRC의 경우 데이터가 손상되었음을 알려줄 수는 있지만 데이터를 자동으로 복구할 수는 없습니다. 일반적으로 데이터 손상이 확인된 경우 데이터를 복구하지 않고 데이터 재전송 요청을 보내거나 다른 오류 수정 메커니즘을 사용합니다.

그럼 CRC는 어떻게 계산되며 데이터의 오류를 검출할 수 있을까요? CRC는 다항식 나눗셈(Polynomial Division)이라는 수학적 개념을 기반으로 합니다.

다항식 나눗셈과 CRC

근데 다항식 나눗셈과 데이터가 무슨 상관이 있길래 이를 사용하는 걸까요?

모든 데이터는 0과 1의 비트 스트림으로 표현할 수 있습니다. 이 때 각 비트 스트림을 다항식의 계수라고 생각하면 데이터를 다항식으로 표현할 수 있습니다. 예를 들어 1010의 비트는 아래의 다항식으로 표현할 수 있습니다.

$$ 1x^3 + 0x^2 + 1x + 0 = x^3 + x $$

마찬가지로 다항식도 비트 스트림으로 표현할 수 있을 겁니다.

이렇듯 CRC 값은 데이터를 다항식으로 바꾼 후 미리 정해진 특정 다항식으로 데이터 다항식을 나눠서 나온 나머지를 다시 비트 스트림으로 바꾼 값입니다. 그럼 1을 넘는 계수의 경우는 어떻게 비트 스트림으로 바꿀 수 있을 까요? 이런 경우는 modulo 2값을 사용합니다. 즉 아래의 다항식은

$$ x^3 + 2x +1 = x^3 + 1 $$

1001로 바꿀 수 있습니다.

CRC의 경우 이렇게 데이터를 다항식으로 바꿔서 미리 정해진 특정 다항식으로 데이터의 다항식을 나눠 그 나머지를 비트 스트림을 바꾼 값으로 계산이 됩니다. 예를 들어보면 데이터가 1110이고 정해진 다항식이 x+1이라면 CRC 값은 아래의 계산을 통해

$$ x^3 + x^2 + x = (x+1)(x^2+1) - 1 = (x+1)(x^2+1) + 1 $$

1이 됩니다.

다항식을 나눌 때 당연히 손으로 계산을 할 수는 없으니깐 shift 연산과 xor 연산을 통해 나머지를 계산합니다. 나눗셈에 대한 의사코드는 아래와 같습니다

function crc(bit array bitString[1..len], int polynomial) {
    shiftRegister := initial value // 보통 00000000 또는 11111111
    for i from 1 to len {
        if (shiftRegister의 최상위 비트) xor bitString[i] = 1
            shiftRegister := (shiftRegister left shift 1) xor polynomial
        else
            shiftRegister := shiftRegister left shift 1
    }
    return shiftRegister
}

나눗셈 알고리즘에 대해서 잘 모르시는 분들을 위해 간단히 설명하면 사람이 실제로 나눗셈을 손으로 할 때와 비슷하게 가장 높은 자릿수를 보고 나누는 값보다 해당 부분이 크다면 나누는 값을 빼주고 아니면 그냥 넘어가는 방식을 의사코드로 표현한 것입니다. 여기서는 빌림이라는 개념이 없기 때문에 빼기 연산대신 xor 연산을 사용합니다.

결론

이렇듯 CRC는 다항식 나눗셈을 통해 데이터 전송 시 오류를 검출할 수 있습니다. 하지만 CRC를 통해 모든 오류를 탐지할 수는 없습니다. 특정 패턴의 오류의 경우에는 CRC의 계산 결과에 영향을 미치지 않아 감지가 되지 않을 수도 있습니다(매우 드물게 발생하긴 함).

게다가 악의적으로 CRC의 계산 결과에 영향을 미치지 않게 해커가 데이터를 변경하는 보안 공격에 대해서는 취약합니다. 이런 공격 방지를 위해서는 보안 공격에 안전한 해시 함수(MD5, SHA-256 등)을 사용해야 합니다.