CBC-MAC - CBC-MAC

Na criptografia , um código de autenticação de mensagem de encadeamento de bloco de cifra ( CBC-MAC ) é uma técnica para construir um código de autenticação de mensagem a partir de uma cifra de bloco . A mensagem é criptografada com algum algoritmo de criptografia de bloco no modo CBC para criar uma cadeia de blocos de forma que cada bloco dependa da criptografia adequada do bloco anterior. Essa interdependência garante que uma alteração em qualquer um dos bits de texto simples fará com que o bloco criptografado final seja alterado de uma forma que não possa ser prevista ou anulada sem o conhecimento da chave para a cifra do bloco.

Para calcular o CBC-MAC da mensagem m , criptografa-se m no modo CBC com vetor de inicialização zero e mantém-se o último bloco. A figura a seguir descreve o cálculo do CBC-MAC de uma mensagem que compreende blocos usando uma chave secreta k e uma cifra de bloco E : ${\ displaystyle m_ {1} \ | m_ {2} \ | \ cdots \ | m_ {x}}$

Segurança com mensagens de comprimento fixo e variável

Se a cifra de bloco usada for segura (o que significa que é uma permutação pseudo - aleatória ), então o CBC-MAC é seguro para mensagens de comprimento fixo. No entanto, por si só, não é seguro para mensagens de comprimento variável. Assim, qualquer chave única deve ser usada apenas para mensagens de comprimento fixo e conhecido. Isso ocorre porque um invasor que conhece os pares de tag de mensagem corretos (isto é, CBC-MAC) para duas mensagens e pode gerar uma terceira mensagem cujo CBC-MAC também será . Isso é feito simplesmente executando um XOR no primeiro bloco de com t e, em seguida, concatenando m com este modificado ; ou seja, fazendo . Ao calcular o MAC para a mensagem , segue-se que calculamos o MAC para m da maneira usual como t , mas quando este valor é encadeado para a frente para a computação de estágio , realizaremos uma operação OU exclusiva com o valor derivado para o MAC de a primeira mensagem. A presença dessa tag na nova mensagem significa que ela será cancelada, não deixando nenhuma contribuição para o MAC dos blocos de texto simples da primeira mensagem m : e, portanto, a tag para is . ${\ displaystyle (m, t)}$${\ displaystyle (m ', t')}$${\ displaystyle m ''}$${\ displaystyle t '}$${\ displaystyle m '}$${\ displaystyle m '}$${\ displaystyle m '' = m \ | [(m_ {1} '\ oplus t) \ | m_ {2}' \ | \ dots \ | m_ {x} ']}$${\ displaystyle m ''}$${\ displaystyle E_ {K _ {\ text {MAC}}} (m_ {1} '\ oplus t)}$${\ displaystyle E_ {K _ {\ text {MAC}}} (m_ {1} '\ oplus t \ oplus t) = E_ {K _ {\ text {MAC}}} (m_ {1}')}$${\ displaystyle m ''}$${\ displaystyle t '}$

Este problema não pode ser resolvido adicionando um bloco de tamanho de mensagem ao final. Existem três maneiras principais de modificar o CBC-MAC para que seja seguro para mensagens de comprimento variável: 1) Separação de chave de comprimento de entrada; 2) Adição por comprimento; 3) Criptografar o último bloco. Nesse caso, também pode ser recomendado o uso de um modo diferente de operação, por exemplo, CMAC ou HMAC para proteger a integridade de mensagens de comprimento variável.

Comprimento precedendo

Uma solução é incluir o comprimento da mensagem no primeiro bloco; na verdade, o CBC-MAC provou ser seguro, desde que duas mensagens que sejam prefixos uma da outra nunca sejam usadas, e adicionar o comprimento antes é um caso especial disso. Isso pode ser problemático se o comprimento da mensagem não for conhecido quando o processamento começar.

Criptografar último bloco

Criptografar o último bloco CBC-MAC (ECBC-MAC) é definido como CBC-MAC-ELB ( m , ( k ₁ , k ₂ )) = E ( k ₂ , CBC-MAC ( k ₁ , m )) . Em comparação com os outros métodos discutidos de estender CBC-MAC para mensagens de comprimento variável, encrypt-last-block tem a vantagem de não precisar saber o comprimento da mensagem até o final do cálculo.

Métodos de ataque

Tal como acontece com muitos esquemas criptográficos, o uso ingênuo de cifras e outros protocolos pode levar a ataques, reduzindo a eficácia da proteção criptográfica (ou mesmo tornando-a inútil). Apresentamos ataques que são possíveis devido ao uso incorreto do CBC-MAC.

Usando a mesma chave para criptografia e autenticação

Um erro comum é reutilizar a mesma chave k para criptografia CBC e CBC-MAC. Embora a reutilização de uma chave para finalidades diferentes seja uma prática ruim em geral, neste caso particular, o erro leva a um ataque espetacular:

Suponha que Alice tenha enviado a Bob os blocos de texto cifrado . Durante o processo de transmissão, Eva pode adulterar qualquer um dos blocos de texto cifrado e ajustar qualquer um dos bits que ela escolher, desde que o bloco final , permaneça o mesmo. Assumimos, para os propósitos deste exemplo e sem perda de generalidade, que o vetor de inicialização usado para o processo de criptografia é um vetor de zeros. ${\ displaystyle C = C_ {1} \ | C_ {2} \ | \ dots \ | C_ {n}}$${\ displaystyle C_ {1}, \ dots, C_ {n-1}}$${\ displaystyle C_ {n}}$

Quando Bob receber a mensagem, ele primeiro a descriptografará, revertendo o processo de criptografia que Alice aplicou, usando os blocos de texto cifrados . A mensagem adulterada, entregue a Bob em substituição à original de Alice, é . ${\ displaystyle C = C_ {1} \ | C_ {2} \ | \ cdots \ | C_ {n}}$${\ displaystyle C '= C_ {1}' \ | \ dots \ | C_ {n-1} '\ | C_ {n}}$

Bob primeiro descriptografa a mensagem recebida usando a chave secreta compartilhada K para obter o texto simples correspondente. Observe que todo texto simples produzido será diferente daquele que Alice enviou originalmente, porque Eva modificou tudo, exceto o último bloco de texto cifrado. Em particular, o texto simples final,, difere do original ,, que Alice enviou; embora é o mesmo, , portanto, um texto simples diferente é produzido quando o encadeamento do bloco de texto cifrado anterior para a descriptografia ou exclusivo depois de : . ${\ displaystyle P_ {n} '}$${\ displaystyle P_ {n}}$${\ displaystyle C_ {n}}$${\ displaystyle C_ {n-1} '\ not = C_ {n-1}}$${\ displaystyle P_ {n} '}$${\ displaystyle C_ {n}}$${\ displaystyle P_ {n} '= C_ {n-1}' \ oplus E_ {K} ^ {- 1} (C_ {n})}$

Segue-se que Bob agora computará a tag de autenticação usando CBC-MAC sobre todos os valores de texto simples que ele decodificou. A tag para a nova mensagem ,, é fornecida por: ${\ displaystyle t '}$

${\ displaystyle t '= E_ {K} (P_ {n}' \ oplus E_ {K} (P_ {n-1} '\ oplus E_ {K} (\ dots \ oplus E_ {K} (P_ {1} '))))}$

Observe que esta expressão é igual a

${\ displaystyle t '= E_ {K} (P_ {n}' \ oplus C_ {n-1} ')}$

que é exatamente : ${\ displaystyle C_ {n}}$

${\ displaystyle t '= E_ {K} (C_ {n-1}' \ oplus E_ {K} ^ {- 1} (C_ {n}) \ oplus C_ {n-1} ') = E_ {K} (E_ {K} ^ {- 1} (C_ {n})) = C_ {n}}$

e segue isso . ${\ displaystyle t '= C_ {n} = t}$

Portanto, Eva foi capaz de modificar o texto cifrado em trânsito (sem necessariamente saber a que texto simples ele corresponde) de forma que uma mensagem totalmente diferente,, foi produzida, mas a tag para esta mensagem correspondeu à tag do original, e Bob foi sem saber que o conteúdo foi modificado em trânsito. Por definição, um Código de Autenticação de Mensagem é quebrado se pudermos encontrar uma mensagem diferente (uma sequência de pares de texto simples ) que produz a mesma marca que a mensagem anterior, P , com . Conclui-se que o protocolo de autenticação de mensagem, neste cenário de uso, foi quebrado, e Bob foi enganado ao acreditar que Alice enviou a ele uma mensagem que ela não produziu. ${\ displaystyle P '}$${\ displaystyle P '}$${\ displaystyle P \ not = P '}$

Se, em vez disso, usarmos chaves diferentes para os estágios de criptografia e autenticação, digamos e , respectivamente, esse ataque será frustrado. A descriptografia dos blocos de texto cifrado modificados obtém alguma string de texto simples . No entanto, devido ao uso de uma chave diferente pelo MAC , não podemos "desfazer" o processo de descriptografia na etapa de avanço do cálculo do código de autenticação da mensagem de modo a produzir a mesma tag; cada modificação será agora criptografada por no processo CBC-MAC para algum valor . ${\ displaystyle K_ {1}}$${\ displaystyle K_ {2}}$${\ displaystyle C_ {i} '}$${\ displaystyle P_ {i} '}$${\ displaystyle K_ {2}}$${\ displaystyle P_ {i} '}$${\ displaystyle K_ {2}}$${\ displaystyle \ mathrm {MAC} _ {i} \ not = C_ {i} '}$

Este exemplo também mostra que um CBC-MAC não pode ser usado como uma função unilateral resistente à colisão: dada uma chave, é trivial criar uma mensagem diferente que "hashes" para a mesma tag.

Permitindo que o vetor de inicialização varie em valor

Ao criptografar dados usando uma cifra de bloco no modo de encadeamento de bloco de cifra (ou outro), é comum introduzir um vetor de inicialização no primeiro estágio do processo de criptografia. Normalmente, é necessário que esse vetor seja escolhido aleatoriamente (um nonce ) e que não seja repetido para qualquer chave secreta sob a qual a cifra de bloco opera. Isso fornece segurança semântica, por meio de garantir que o mesmo texto simples não seja criptografado para o mesmo texto cifrado, permitindo que um invasor inferir que existe um relacionamento.

Ao computar um código de autenticação de mensagem, como por CBC-MAC, o uso de um vetor de inicialização é um possível vetor de ataque.

Na operação de uma cifra de encadeamento de blocos de texto cifrado, o primeiro bloco de texto simples é misturado com o vetor de inicialização usando um OU exclusivo ( ). O resultado dessa operação é a entrada para a cifra de bloco para criptografia. ${\ displaystyle P_ {1} \ oplus IV}$

No entanto, ao realizar a criptografia e descriptografia, somos obrigados a enviar o vetor de inicialização em texto simples - normalmente como o bloco imediatamente anterior ao primeiro bloco de texto cifrado - de forma que o primeiro bloco de texto simples possa ser descriptografado e recuperado com êxito. Se estiver computando um MAC, também precisaremos transmitir o vetor de inicialização para a outra parte em texto simples para que eles possam verificar se a etiqueta na mensagem corresponde ao valor calculado.

Se permitirmos que o vetor de inicialização seja selecionado arbitrariamente, segue-se que o primeiro bloco de texto simples pode ser potencialmente modificado (transmitindo uma mensagem diferente) enquanto produz a mesma tag de mensagem.

Considere uma mensagem . Em particular, ao calcular a tag de mensagem para CBC-MAC, suponha que escolhemos um vetor de inicialização de forma que a computação do MAC comece . Isso produz um par (mensagem, tag) . ${\ displaystyle M_ {1} = P_ {1} | P_ {2} | \ pontos}$${\ displaystyle IV_ {1}}$${\ displaystyle E_ {K} (IV_ {1} \ oplus P_ {1})}$${\ displaystyle (M_ {1}, T_ {1})}$

Agora produza a mensagem . Para cada bit modificado em , inverta o bit correspondente no vetor de inicialização para produzir o vetor de inicialização . Segue-se que, para calcular o MAC para esta mensagem, iniciamos o cálculo por . Como os bits no texto simples e no vetor de inicialização foram invertidos nos mesmos lugares, a modificação é cancelada neste primeiro estágio, o que significa que a entrada para a cifra de bloco é idêntica àquela para . Se nenhuma outra alteração for feita no texto simples, a mesma tag será derivada, apesar de uma mensagem diferente ser transmitida. ${\ displaystyle M_ {2} = P_ {1} '| P_ {2} | \ dots}$${\ displaystyle P_ {1} '}$${\ displaystyle IV_ {1} '}$${\ displaystyle E_ {K} (P_ {1} '\ oplus IV_ {1}')}$${\ displaystyle M_ {1}}$

Se a liberdade de selecionar um vetor de inicialização for removida e todas as implementações de CBC-MAC fixarem-se em um vetor de inicialização específico (geralmente o vetor de zeros, mas em teoria, pode ser qualquer coisa, desde que todas as implementações concordem), este ataque não poderá prosseguir.

Resumindo, se o invasor for capaz de definir o IV que será usado para a verificação do MAC, ele pode realizar modificações arbitrárias no primeiro bloco de dados sem invalidar o MAC.

Usando vetor de inicialização previsível

Às vezes, o IV é usado como um contador para evitar ataques de repetição de mensagem. No entanto, se o invasor puder prever qual IV será usado para a verificação do MAC, ele pode reproduzir a mensagem observada anteriormente, modificando o primeiro bloco de dados para compensar a alteração no IV que será usado para a verificação. Por exemplo, se o invasor observou a mensagem com e sabe , ele pode produzir que passará na verificação do MAC com . ${\ displaystyle M_ {1} = P_ {1} | P_ {2} | \ pontos}$${\ displaystyle IV_ {1}}$${\ displaystyle IV_ {2}}$${\ displaystyle M_ {1} '= (P_ {1} \ oplus IV_ {1} \ oplus IV_ {2}) | P_ {2} | \ pontos}$${\ displaystyle IV_ {2}}$

A contramedida mais simples é criptografar o IV antes de usá-lo (ou seja, adicionar o IV aos dados). Alternativamente, o MAC no modo CFB pode ser usado, porque no modo CFB o IV é criptografado antes de ser XORed com os dados.

Outra solução (caso não seja necessária proteção contra ataques de repetição de mensagem) é sempre usar um vetor zero IV. Observe que a fórmula acima para se torna . Portanto, como e são a mesma mensagem, por definição, eles terão a mesma tag. Isso não é uma falsificação, mas sim o uso pretendido do CBC-MAC. ${\ displaystyle M_ {1} '}$${\ displaystyle M_ {1} '= (P_ {1} \ oplus 0 \ oplus 0) | P_ {2} | \ dots = P_ {1} | P_ {2} | \ dots = M_ {1}}$${\ displaystyle M_ {1}}$${\ displaystyle M_ {1} '}$

Padrões que definem o algoritmo

FIPS PUB 113 Computer Data Authentication é um padrão (agora obsoleto) do governo dos EUA que especificava o algoritmo CBC-MAC usando DES como cifra de bloco.

O algoritmo CBC-MAC é equivalente ao Algoritmo 1 MAC ISO / IEC 9797-1 .

Veja também

• CMAC - Um algoritmo MAC baseado em cifra de bloco que é seguro para mensagens de diferentes comprimentos (recomendado pelo NIST ).
• OMAC e PMAC - Outros métodos para transformar cifras de bloco em códigos de autenticação de mensagem (MACs).
• Função de compressão unilateral - as funções hash podem ser feitas a partir de cifras de bloco. Mas observe que há diferenças significativas na função e nos usos para segurança entre MACs (como CBC-MAC) e hashes .

Referências