Por que a codificação base64 requer preenchimento se o comprimento de entrada não é divisível por 3?

100

Qual é a finalidade do preenchimento na codificação base64. O seguinte é o extrato da wikipedia:

"Um caractere de preenchimento adicional é alocado, o qual pode ser usado para forçar a saída codificada em um múltiplo inteiro de 4 caracteres (ou de forma equivalente quando o texto binário não codificado não for um múltiplo de 3 bytes); esses caracteres de preenchimento devem ser descartados durante a decodificação, mas ainda permitem o cálculo do comprimento efetivo do texto não codificado, quando seu comprimento binário de entrada não seria um múltiplo de 3 bytes (o último caractere não-pad é normalmente codificado de forma que o último bloco de 6 bits que ele representa será zero - preenchido em seus bits menos significativos, no máximo dois caracteres de preenchimento podem ocorrer no final do fluxo codificado). "

Eu escrevi um programa que poderia codificar qualquer string em base64 e decodificar qualquer string codificada em base64. Qual problema o preenchimento resolve?

Anand Patel
fonte

Respostas:

208

Sua conclusão de que o preenchimento é desnecessário está certa. Sempre é possível determinar o comprimento da entrada sem ambigüidade a partir do comprimento da sequência codificada.

No entanto, o preenchimento é útil em situações em que strings codificadas em base64 são concatenadas de forma que os comprimentos das sequências individuais sejam perdidos, como pode acontecer, por exemplo, em um protocolo de rede muito simples.

Se strings não preenchidas forem concatenadas, é impossível recuperar os dados originais porque as informações sobre o número de bytes ímpares no final de cada sequência individual são perdidas. No entanto, se sequências preenchidas forem usadas, não haverá ambigüidade e a sequência como um todo poderá ser decodificada corretamente.

Editar: Uma Ilustração

Suponha que tenhamos um programa que codifica palavras em base64, concatena-as e as envia pela rede. Ele codifica "I", "AM" e "TJM", junta os resultados sem preenchimento e os transmite.

  • Icodifica para SQ( SQ==com preenchimento)
  • AMcodifica para QU0( QU0=com preenchimento)
  • TJMcodifica para VEpN( VEpNcom preenchimento)

Portanto, os dados transmitidos são SQQU0VEpN. O receptor base64 decodifica isso como em I\x04\x14\xd1Q)vez do pretendido IAMTJM. O resultado é um absurdo porque o remetente destruiu informações sobre onde cada palavra termina na sequência codificada. Se o remetente tivesse enviado SQ==QU0=VEpN, o receptor poderia ter decodificado isso como três sequências de base64 separadas que se concatenariam para dar IAMTJM.

Por que se preocupar com acolchoamento?

Por que não apenas projetar o protocolo para prefixar cada palavra com um comprimento inteiro? Em seguida, o receptor poderia decodificar o fluxo corretamente e não haveria necessidade de preenchimento.

Essa é uma ótima ideia, contanto que saibamos o comprimento dos dados que estamos codificando antes de começar a codificá-los. Mas e se, em vez de palavras, estivéssemos codificando pedaços de vídeo de uma câmera ao vivo? Podemos não saber o comprimento de cada pedaço com antecedência.

Se o protocolo usasse preenchimento, não haveria necessidade de transmitir um comprimento. Os dados poderiam ser codificados conforme vinham da câmera, cada pedaço terminado com preenchimento e o receptor seria capaz de decodificar o fluxo corretamente.

Obviamente, esse é um exemplo muito artificial, mas talvez ilustre por que o preenchimento pode ser útil em algumas situações.

TJM
fonte
22
+1 A única resposta que realmente fornece uma resposta razoável além de "porque gostamos de verbosidade e redundância por algum motivo inexplicável".
inválido
1
Isso funciona bem para blocos que são codificados distintamente, mas espera-se que sejam concatenados de forma indivisível após a decodificação. Se você enviar U0FNSQ == QU0 =, poderá reconstruir a frase, mas perderá as palavras que a compõem. Melhor do que nada, eu acho. Notavelmente, o programa GNU base64 lida automaticamente com codificações concatenadas.
Marcelo Cantos
2
E se o comprimento das palavras fosse um múltiplo de 3? Essa forma burra de concatenação destrói informações (terminações de palavras), não a remoção de preenchimento.
GreenScape
2
A concatenação Base64 permite que os codificadores processem grandes blocos em paralelo, sem a carga de alinhar os tamanhos dos blocos a um múltiplo de três. Da mesma forma, como um detalhe de implementação, pode haver um codificador que precise liberar um buffer de dados interno de um tamanho que não seja múltiplo de três.
Andre D
1
Essa resposta pode fazer você pensar que pode decodificar algo como "SQ == QU0 = VEpN" apenas passando-o para um decodificador. Na verdade, parece que você não pode, por exemplo, as implementações em javascript e php não suportam isso. Começando com uma string concatenada, você deve decodificar 4 bytes por vez ou dividir a string após preencher os caracteres. Parece que essas implementações simplesmente ignoram os caracteres de preenchimento, mesmo quando eles estão no meio de uma string.
Romano
38

Em uma nota relacionada, aqui está um conversor de base para conversão de base arbitrária que criei para você. Aproveitar! https://convert.zamicol.com/

O que são caracteres de preenchimento?

Os caracteres de preenchimento ajudam a satisfazer os requisitos de comprimento e não têm significado.

Exemplo de Decimal de Preenchimento: Dado o requisito arbitrário de todas as strings terem 8 caracteres de comprimento, o número 640 pode atender a esse requisito usando os 0s anteriores como caracteres de preenchimento, pois eles não têm significado, "00000640".

Codificação Binária

O Paradigma do Byte: O byte é a unidade de medida padrão de fato e qualquer esquema de codificação deve estar relacionado aos bytes.

Base256 se encaixa exatamente neste paradigma. Um byte é igual a um caractere em base256.

Base16 , hexadecimal ou hex, usa 4 bits para cada caractere. Um byte pode representar dois caracteres de base16.

Base64 não se encaixa uniformemente no paradigma de byte (nem base32), ao contrário de base256 e base16. Todos os caracteres de base64 podem ser representados em 6 bits, 2 bits menos que um byte completo.

Podemos representar a codificação base64 versus o paradigma do byte como uma fração: 6 bits por caractere em 8 bits por byte . Esta fração reduzida é de 3 bytes em 4 caracteres.

Essa proporção, 3 bytes para cada 4 caracteres base64, é a regra que desejamos seguir ao codificar base64. A codificação Base64 só pode prometer medição com pacotes de 3 bytes, ao contrário de base16 e base256, onde cada byte pode estar sozinho.

Então, por que o preenchimento é encorajado, embora a codificação pudesse funcionar bem sem os caracteres de preenchimento?

Se o comprimento de um fluxo for desconhecido ou se puder ser útil saber exatamente quando um fluxo de dados termina, use preenchimento. Os caracteres de preenchimento comunicam explicitamente que esses pontos extras devem estar vazios e elimina qualquer ambigüidade. Mesmo que o comprimento seja desconhecido com o preenchimento, você saberá onde termina o seu fluxo de dados.

Como contra-exemplo, alguns padrões como JOSE não permitem caracteres de preenchimento. Neste caso, se houver algo faltando, uma assinatura criptográfica não funcionará ou outros caracteres não base64 estarão faltando (como o "."). Embora suposições sobre o comprimento não sejam feitas, o preenchimento não é necessário porque se houver algo errado, ele simplesmente não funcionará.

E isso é exatamente o que diz o RFC de base64 ,

Em algumas circunstâncias, o uso de preenchimento ("=") em dados codificados de base não é necessário ou usado. No caso geral, quando suposições sobre o tamanho dos dados transportados não podem ser feitas, o preenchimento é necessário para produzir dados decodificados corretos.

[...]

O passo de preenchimento na base 64 [...] se implementado incorretamente, leva a alterações não significativas dos dados codificados. Por exemplo, se a entrada for apenas um octeto para uma codificação de base 64, todos os seis bits do primeiro símbolo serão usados, mas apenas os dois primeiros bits do próximo símbolo serão usados. Esses bits de preenchimento DEVEM ser definidos como zero pelos codificadores em conformidade, que são descritos nas descrições de preenchimento abaixo. Se essa propriedade não for mantida, não haverá representação canônica de dados codificados por base e várias strings codificadas por base poderão ser decodificadas para os mesmos dados binários. Se esta propriedade (e outras discutidas neste documento) for mantida, uma codificação canônica é garantida.

O preenchimento nos permite decodificar a codificação base64 com a promessa de que não haverá perda de bits. Sem preenchimento, não há mais o reconhecimento explícito da medição em pacotes de três bytes. Sem preenchimento, você pode não ser capaz de garantir a reprodução exata da codificação original sem informações adicionais geralmente de algum outro lugar em sua pilha, como TCP, somas de verificação ou outros métodos.

Exemplos

Aqui está o formulário de exemplo RFC 4648 ( http://tools.ietf.org/html/rfc4648#section-8 )

Cada caractere dentro da função "BASE64" usa um byte (base256). Em seguida, traduzimos isso para base64.

BASE64("")       = ""           (No bytes used. 0%3=0.)
BASE64("f")      = "Zg=="       (One byte used. 1%3=1.)
BASE64("fo")     = "Zm8="       (Two bytes. 2%3=2.)
BASE64("foo")    = "Zm9v"       (Three bytes. 3%3=0.)
BASE64("foob")   = "Zm9vYg=="   (Four bytes. 4%3=1.)
BASE64("fooba")  = "Zm9vYmE="   (Five bytes. 5%3=2.)
BASE64("foobar") = "Zm9vYmFy"   (Six bytes. 6%3=0.)

Este é um codificador com o qual você pode brincar: http://www.motobit.com/util/base64-decoder-encoder.asp

Zamicol
fonte
16
-1 É uma postagem agradável e completa sobre como funcionam os sistemas numéricos, mas não explica por que o preenchimento é usado quando a codificação funcionaria perfeitamente sem.
Matti Virkkunen
2
Você ao menos leu a pergunta? Você não precisa de preenchimento para decodificar corretamente.
Navin
3
Acho que essa resposta de fato explica o motivo, conforme declarado aqui: "não podemos mais garantir a reprodução exata da codificação original sem informações adicionais". É realmente simples, o preenchimento nos permite saber que recebemos a codificação completa. Cada vez que você tiver 3 bytes, você pode assumir com segurança que está tudo bem para ir em frente e decodificá-los, você não se preocupe que, hum ... talvez mais um byte venha, possivelmente alterando a codificação.
Didier A.
@DidierA. Como você sabe que não há mais 3 bytes em uma substring base64? Para decodificar um char*, você precisa do tamanho da string ou de um terminador nulo. O preenchimento é redundante. Daí a pergunta de OP.
Navin
4
@Navin Se você está decodificando os bytes de base64, você não sabe o comprimento, com o preenchimento de 3 bytes, você sabe que toda vez que você obtém 3 bytes pode processar os 4 caracteres, até chegar ao final do fluxo. Sem ele, você pode precisar retroceder, porque o próximo byte pode fazer com que o caractere anterior mude, fazendo com que você só tenha certeza de decodificá-lo corretamente quando chegar ao final do fluxo. Portanto, não é muito útil, mas tem alguns casos extremos em que você pode querer usá-lo.
Didier A.
1

Não há muito benefício nisso nos dias modernos. Portanto, vamos examinar isso como uma questão de qual pode ter sido o propósito histórico original .

A codificação Base64 faz sua primeira aparição na RFC 1421 datada de 1993. Na verdade, essa RFC concentra-se na criptografia de e-mail e a base64 é descrita em uma pequena seção 4.3.2.4 .

Este RFC não explica a finalidade do preenchimento. O mais próximo que temos de uma menção do propósito original é esta frase:

Um quantum de codificação completo é sempre concluído no final de uma mensagem.

Não sugere concatenação (resposta principal aqui), nem facilidade de implementação como um propósito explícito para o preenchimento. No entanto, considerando toda a descrição, não é absurdo supor que isso pode ter a intenção de ajudar o decodificador a ler a entrada em unidades de 32 bits ( "quanta" ). Isso não traz nenhum benefício hoje, no entanto, em 1993, o código C inseguro provavelmente teria realmente aproveitado essa propriedade.

Roman Starkov
fonte
1
Na ausência de preenchimento, uma tentativa de concatenar duas cadeias de caracteres quando o comprimento da primeira não é um múltiplo de três frequentemente resultaria em uma cadeia aparentemente válida, mas o conteúdo da segunda cadeia seria decodificado incorretamente. Adicionar o preenchimento garante que isso não ocorra.
supercat
1
@supercat Se esse fosse o objetivo, não seria mais fácil terminar cada string base64 com apenas um único "="? O comprimento médio seria menor e ainda evitaria concatenações errôneas.
Roman Starkov
2
O comprimento médio de b'Zm9vYmFyZm9vYg==' b'Zm9vYmFyZm9vYmE=' b'Zm9vYmFyZm9vYmFy' b'Zm9vYmFyZm9vYmFyZg==' b'Zm9vYmFyZm9vYmFyZm8=' b'Zm9vYmFyZm9vYmFyZm9v' é igual ao de b'Zm9vYmFyZm9vYg=' b'Zm9vYmFyZm9vYmE=' b'Zm9vYmFyZm9vYmFy=' b'Zm9vYmFyZm9vYmFyZg=' b'Zm9vYmFyZm9vYmFyZm8=' b'Zm9vYmFyZm9vYmFyZm9v='
Scott