Контрольная сумма UDP

Большинство проектов, над которыми я когда-либо работал, так или иначе не работают без передачи данных по сети. Последним проектом не выходящим за рамки одного компьютера была поддержка Wow64 в ядре Windows. Тем не менее возится с кодом, непосредственно обрабатывающим IP пакеты мне довелось всего пару раз. Оба раза я столкнулся с одной и той же ошибкой вычисления контрольных сумм в IP стеке. В одном случае, сетевая карта ошибочно помечала хорошие пакеты как испорченные. В другом - две библиотеки, написанные разными людьми, неверно вычисляли контрольную сумму некоторых пакетов. Одна из библиотек широко использовалась в “боевых” условиях. Немного удивительно, что ошибка оставалась незамеченной так долго.

Корнями этот баг уходит в 1980-й год, когда был опубликована спецификация протокола UDP. Чтобы разобраться в чем заключается ошибка, нужно сначала разобраться как работают контрольные суммы в IP стеке. В IPv4 пакете есть две контрольные суммы: контрольная сумма IPv4 заголовка и контрольная сумма протокола следующего уровня (UDP, TCP, ICMP, и т.п.). Контрольная сумма IPv4 заголовка защищает только IPv4 заголовок. Контрольная сумма протокола следующего уровня защищает тело пакета и некоторые поля из заголовка.

Контрольная сумма IPv4 заголовка вычисляется по такому алгоритму:

The checksum field is the 16 bit one’s complement of the one’s complement sum of all 16 bit words in the header. For purposes of computing the checksum, the value of the checksum field is zero.

Поле контрольной суммы - 16 битное дополнение до единицы суммы всех 16 битных слов, вычисленной в обратном коде. Для целей вычисления контрольной суммы, значение поля контрольной суммы считается равным нулю.

В переводе с птичьего на человеческий это означает вот что. Обратный код - это способ представления чисел в двоичном коде. В отличие от более привычного дополнительного кода, обратный код использует два разных представления нуля: положительный и отрицательный ноль. Инвертирование числа дает то же самое число с обратным знаком:

    0111    +7
    0110    +6
    0101    +5
    0100    +4
    0011    +3
    0010    +2
    0001    +1
    0000    +0  # положительный ноль
    1111    -0  # отрицательный ноль
    1110    -1
    1101    -2
    1100    -3
    1011    -4
    1010    -5
    1001    -6
    1000    -7

Чтобы получить правильный результат при сложении двух чисел в обратном коде, перенос из старшего разряда просто прибавляется к сумме:

    0110    +6
  + 1101    -2
  ------
    0011    +3
  +    1        # перенос из старшего разряда
  ------
    0100    +4

“сумма всех 16 битных слов, вычисленной в обратном коде” - означает не что иное, как сумму всех 16 битных слов заголовка выполненную по вышеописанному правилу. “16 битное дополнение до единицы суммы” - указывает, что после вычисления суммы всех 16 битных слов заголовка, полученное значение инвертируется.

Такой алгоритм позволяет проверить пакет просто вычислив сумму всех 16 битных слов заголовка (включая поле контрольной суммы). Если результат равен нулю - пакет не поврежден. Что более важно, он позволяет легко обновить контрольную сумму, при изменении только некоторый полей заголовка, не вычисляя её заново. Это свойство было полезно при создании высокопроизводительных IP маршрутизаторов.

Написать и протестировать код, реализующий этот алгоритм, казалось бы можно за пол-часа, с перерывом на кофе. Однако эта простота обманчива. Существуют три RFC, поясняющие неочевидные детали инкрементального обновления контрольной суммы: RFC 1071, RFC 1141, RFC 1624. В каждом из этих документов были исправлены ошибки, найденные после их опубликования.

Как я уже упоминал выше, в каждом IPv4 пакете есть две контрольные суммы. Пока что мы обсудили только контрольную сумму заголовка IPv4 пакета. Вторая контрольная сумма (UDP или TCP) вычисляется по другому алгоритму.

Checksum is the 16-bit one’s complement of the one’s complement sum of a pseudo header of information from the IP header, the UDP header, and the data, padded with zero octets at the end (if necessary) to make a multiple of two octets.

If the computed checksum is zero, it is transmitted as all ones (the equivalent in one’s complement arithmetic). An all zero transmitted checksum value means that the transmitter generated no checksum (for debugging or for higher level protocols that don’t care).

Контрольная сумма - 16 битное дополнение до единицы суммы псевдо заголовка, заполненного информацией из IP заголовка, UDP заголовка и данных, выровненных до границы двух байт.

Если вычисленная сумма равна нулю, она передается как все единицы ( эквивалентное значение в дополнительном коде). Нулевая контрольная сумма в пакете означает что передающая сторона не указала контрольную сумму (в целях отладки или при использовании протоколов более высокого уровня которым все равно).

На первый взгляд этот алгоритм сильно отличается от алгоритма вычисления контрольной суммы заголовка IPv4, но при внимательном рассмотрении оказывается, что оба алгоритма очень похожи. Первый абзац фактически описывает ту же самую инвертированную сумму 16-битных слов в обратном коде. Единственное отличие - это диапазон данных (псевдо заголовок, UDP заголовок и данные вместо IPv4 заголовка), которые покрываются контрольной суммой.

Настоящее отличие кроется во втором абзаце. Если его перефразировать, то он утверждает, что контрольная сумма UDP необязательна. Передающая сторона может просто передать ноль вместо вычисления контрольной суммы. В случае если вычисленная контрольная сумма получается равной нулю, то она передается как -0, т.е. 0xffff. Фраза “эквивалентное значение в дополнительном коде” специально уточняет, что два разных значения в дополнительном коде (+0 и -0) соответствуют нулю и такая замена разрешена.

Именно здесь и скрывается баг. Дело в том, что при сложении чисел в обратном коде единственный способ способ получить значение 0x0000 (+0) - это сложить +0 и +0. Любая другая комбинация чисел дает результат от 0x0001 (+1) до 0xffff (-0). Любой корректный IP пакет содержит ненулевые байты, что гарантирует, что сумма 16-битных полей корректного пакета не будет равна 0x0000 (+0).

Итак сумма не может равняться +0 и 0x0000 используется как зарезервированное значение - пока что все сходится, разве нет? А вот и нет. Мы забыли, что вычисленная сумма инвертируется при передаче. Получается вот такой странный специальный случай:

# Сумма полей     Контрольная     Поле контрольной
# пакета          сумма           суммы в пакете

0x0001            0xfffe          0xfffe
0x0002            0xfffd          0xfffd
0x0003            0xfffc          0xfffc
...
0xfffd            0x0002          0x0002
0xfffe            0x0001          0x0001
0xffff            0x0000          0xffff  <-- ???

Получается, что спецификация подставляет подножку разработчикам и заставляет их на ровном месте добавлять в код обработку специального случая. Программисты с удовольствием наступают на эти грабли и пишут код, обрабатывающий этот случай неправильно. Я видел обе вариации этой ошибки. В одном случае контрольная сумма UDP пакета вычислялась по алгоритму для IPv4. В другом случае было ровно наоборот, - неправильно вычислялась контрольная сумма заголовка IP пакета. А ведь достаточно было бы взять другое зарезервированное значение для обозначения невычисленной контрольной суммы - 0xffff (-0) и желаемое поведение получилось бы естественным образом безо всяких ухищрений.

Забавно, что одна из причин по которым это баг может оставаться незамеченным долгое время это то, что в большинстве случаем вычисление контрольных сумм переносится с центрального процессора на сетевую карту (checksum offloading). Соответственно ошибочный код просто не выполняется. Другая причина заключается в том, что эта ошибка в среднем затрагивает один пакет из 65535 (0.0015% пакетов).

В заключение добавлю, что алгоритма вычисления контрольной суммы один из немногих примеров “промышленного” кода. который тривиально поддается 100% проверке полным перебором. Там всего-навсего 65536 возможных значений.