Soma de verificação

Efeito de uma função de checksum típica (o Unixcksum utilidade)

Um checksum é um pequeno bloco de dados derivado de outro bloco de dados digitais com a finalidade de detectar erros que possam ter sido introduzidos durante sua transmissão ou armazenamento. Por si só, as somas de verificação são frequentemente usadas para verificar a integridade dos dados, mas não são confiáveis para verificar a autenticidade dos dados.

O procedimento que gera essa soma de verificação é chamado de função de soma de verificação ou algoritmo de soma de verificação. Dependendo de seus objetivos de projeto, um bom algoritmo de soma de verificação geralmente produz um valor significativamente diferente, mesmo para pequenas alterações feitas na entrada. Isso é especialmente verdadeiro para funções hash criptográficas, que podem ser usadas para detectar muitos erros de corrupção de dados e verificar a integridade geral dos dados; se a soma de verificação calculada para a entrada de dados atual corresponder ao valor armazenado de uma soma de verificação calculada anteriormente, há uma probabilidade muito alta de que os dados não tenham sido acidentalmente alterados ou corrompidos.

As funções de soma de verificação estão relacionadas a funções de hash, impressões digitais, funções de randomização e funções de hash criptográficas. No entanto, cada um desses conceitos tem diferentes aplicações e, portanto, diferentes objetivos de design. Por exemplo, uma função que retorna o início de uma string pode fornecer um hash apropriado para alguns aplicativos, mas nunca será uma soma de verificação adequada. As somas de verificação são usadas como primitivas criptográficas em algoritmos de autenticação maiores. Para sistemas criptográficos com esses dois objetivos de design específicos, consulte HMAC.

Dígitos de verificação e bits de paridade são casos especiais de somas de verificação, apropriados para pequenos blocos de dados (como números de CPF, números de contas bancárias, palavras de computador, bytes únicos, etc.). Alguns códigos de correção de erros são baseados em somas de verificação especiais que não apenas detectam erros comuns, mas também permitem que os dados originais sejam recuperados em certos casos.

Algoritmos

Byte de paridade ou palavra de paridade

O algoritmo de soma de verificação mais simples é a chamada verificação de paridade longitudinal, que divide os dados em "palavras" com um número fixo n de bits e, em seguida, calcula o ou exclusivo (XOR) de todas essas palavras. O resultado é anexado à mensagem como uma palavra extra. Em termos mais simples, isso significa adicionar um bit ao final da palavra para garantir que haja um número par de '1's. Para verificar a integridade de uma mensagem, o receptor calcula o ou exclusivo de todas as suas palavras, incluindo o checksum; se o resultado não for uma palavra que consiste em n zeros, o receptor saberá que ocorreu um erro de transmissão.

Com esta soma de verificação, qualquer erro de transmissão que altere um único bit da mensagem, ou um número ímpar de bits, será detectado como uma soma de verificação incorreta. No entanto, um erro que afete dois bits não será detectado se esses bits estiverem na mesma posição em duas palavras distintas. Também a troca de duas ou mais palavras não será detectada. Se os bits afetados forem escolhidos aleatoriamente de forma independente, a probabilidade de um erro de dois bits não detectado é 1/n.

Complemento de soma

Uma variante do algoritmo anterior é adicionar todas as "palavras" como números binários não assinados, descartando quaisquer bits de estouro e acrescentando o complemento de dois do total como a soma de verificação. Para validar uma mensagem, o receptor soma todas as palavras da mesma forma, incluindo o checksum; se o resultado não for uma palavra cheia de zeros, deve ter ocorrido um erro. Essa variante também detecta qualquer erro de bit único, mas a soma modular profissional é usada no SAE J1708.

Dependente da posição

As somas de verificação simples descritas acima não conseguem detectar alguns erros comuns que afetam muitos bits de uma só vez, como alterar a ordem das palavras de dados ou inserir ou excluir palavras com todos os bits definidos como zero. Os algoritmos de soma de verificação mais usados na prática, como a soma de verificação de Fletcher, Adler-32 e verificações de redundância cíclica (CRCs), abordam essas deficiências considerando não apenas o valor de cada palavra, mas também sua posição na sequência. Esse recurso geralmente aumenta o custo de calcular a soma de verificação.

Soma de verificação difusa

A ideia da soma de verificação difusa foi desenvolvida para detecção de spam de e-mail, construindo bancos de dados cooperativos de vários ISPs de e-mail suspeito de ser spam. O conteúdo desse spam geralmente pode variar em seus detalhes, o que tornaria a soma de verificação normal ineficaz. Por outro lado, uma "soma de verificação difusa" reduz o corpo do texto ao seu mínimo característico e, em seguida, gera uma soma de verificação da maneira usual. Isso aumenta muito as chances de e-mails de spam ligeiramente diferentes produzirem a mesma soma de verificação. O software de detecção de spam do ISP, como o SpamAssassin, de ISPs cooperantes, envia somas de verificação de todos os e-mails para o serviço centralizado, como o DCC. Se a contagem de uma soma de verificação difusa enviada exceder um determinado limite, o banco de dados observará que isso provavelmente indica spam. Os usuários do serviço ISP também geram uma soma de verificação difusa em cada um de seus e-mails e solicitam o serviço para uma probabilidade de spam.

Considerações gerais

Uma mensagem com m bits pode ser visualizada como um canto do m-dimensional. O efeito de um algoritmo de soma de verificação que produz uma soma de verificação de n bits é mapear cada m-bit para um canto de um hipercubo maior, com dimensão m + n. Os cantos 2^{m + n} deste hipercubo representam todas as possíveis mensagens recebidas. As mensagens recebidas válidas (aquelas que possuem o checksum correto) compõem um conjunto menor, com apenas 2^m cantos.

Um erro de transmissão de um único bit corresponde então a um deslocamento de um canto válido (a mensagem correta e a soma de verificação) para um dos m adjacentes cantos. Um erro que afeta k bits move a mensagem para um canto que é k etapas removidas de seu canto correto. O objetivo de um bom algoritmo de soma de verificação é espalhar os cantos válidos o mais longe possível um do outro, para aumentar a probabilidade de erros "típicos" erros de transmissão terminarão em um canto inválido.