Criptografia, assinaturas e PKI

Ana envia ao Bruno a lista de preços da loja. Um observador da rede não deve conseguir lê-la, e Bruno precisa de detetar alterações e verificar a origem. São objetivos distintos: confidencialidade, integridade e autenticidade. Uma primitiva criptográfica é um mecanismo básico, como uma cifra ou uma assinatura, que pode ser combinado num protocolo para cumprir esses objetivos.

Escolher a primitiva

A lista de preços da loja mostra quando cada mecanismo serve. Para esconder a lista em trânsito, Ana cifra para a chave pública do Bruno; para provar que a lista veio da direção, a direção assina com a sua chave privada e qualquer pessoa verifica com a pública; para detetar uma alteração acidental face a uma cópia confiável, basta comparar o hash com a referência guardada. A tabela seguinte resume cada caso e o que não resolve sozinho.

Mecanismo	Segredo necessário	Propriedade principal	O que não dá sozinho
Cifra simétrica	Chave partilhada	Confidencialidade	Autenticidade e proteção contra repetição
Cifra de chave pública	Privada do destinatário para decifrar	Confidencialidade para esse destinatário	Identidade de quem enviou
Hash criptográfico	Nenhum	Resumo para verificar alterações face a uma referência confiável	Autenticidade se o atacante puder trocar mensagem e resumo
MAC	Chave partilhada	Integridade e autenticidade entre quem conhece a chave	Confidencialidade ou prova pública do autor
Assinatura digital	Privada do signatário	Integridade e verificação pública da origem	Confidencialidade

Uma assinatura usa operações próprias Sign e Verify. Não se deve defini-la como “cifrar com a chave privada”: isso não descreve algoritmos como EdDSA e omite a codificação segura do RSA. Se a chave privada foi roubada, verificar a assinatura não distingue o titular do ladrão. Uma assinatura pode apoiar o não repúdio, porque terceiros podem verificar a prova. A atribuição de uma ação à pessoa continua a depender da associação da chave, da sua proteção e do contexto.

Uma função hash tem saída de tamanho fixo. Para a lista de preços, distingue três problemas:

• Pré-imagem: dado um resumo, encontrar alguma entrada que o produza.
• Segunda pré-imagem: dada a lista original, encontrar outra lista com o mesmo resumo.
• Colisão: escolher duas listas distintas que produzam o mesmo resumo, sem uma lista original imposta.

Para uma saída ideal de $n$ bits, a pesquisa genérica de colisões custa aproximadamente $2^{n/2}$ tentativas, por causa do paradoxo do aniversário. Isto não torna secreto um dado com poucos valores possíveis: se a lista só pudesse ser uma de dez versões conhecidas, calcular os dez hashes permitiria comparar as hipóteses com o resumo publicado.

Colisões existem necessariamente quando há mais entradas possíveis do que resumos: uma saída de $n$ bits só admite $2^n$ valores. Isso não fornece um método eficiente para encontrar duas entradas concretas. Existência de colisões e resistência computacional a encontrá-las são afirmações diferentes.

Cifrar e assinar com as chaves certas

Para confidencialidade, Ana cifra para a chave pública do Bruno, que decifra com a privada do Bruno. Para autenticidade, Ana assina com a privada da Ana, e Bruno verifica com a pública da Ana. Trocar estes nomes troca o objetivo.

Em sistemas híbridos, uma chave de sessão protege os dados com uma cifra simétrica autenticada. Um mecanismo de acordo ou encapsulamento de chaves estabelece esse segredo. Isto evita usar operações de chave pública para todo o conteúdo. O acordo de chaves também precisa de autenticação, como veremos em modos e protocolos.

Ordem entre assinar e cifrar

Assinatura e cifragem podem combinar-se nas duas ordens, como descreve a secção 3.7 do RFC 8551. O que muda é o objeto autenticado pela assinatura exterior e o que um verificador consegue concluir.

Quando Ana assina o texto original e depois cifra o conjunto para Bruno, quem decifra pode verificar a assinatura sobre esse texto. A identidade do signatário fica escondida de observadores sem a chave de decifra, e a verificação exige decifrar primeiro. Quando Ana cifra primeiro e assina o criptograma, qualquer pessoa pode verificar a assinatura exterior sem decifrar, mas essa verificação autentica o criptograma, não estabelece por si a mesma relação com o texto em claro.

Uma assinatura exterior não prova por si que o signatário compreendeu o conteúdo: processamento automático, chaves comprometidas e contextos diferentes quebram essa leitura. Do mesmo modo, o facto de Ana cifrar para a chave de Bruno não a impede de conhecer o texto que ela própria escolheu cifrar. Para o objetivo desta aula, provar perante terceiros a origem do texto em claro, a composição usada é assinar o original e cifrar depois, com a chave associada a Ana, a chave protegida e o contexto verificado. A outra ordem continua possível noutros objetivos, por exemplo quando se quer verificação sem decifrar. Em ambos os casos, continua a ser preciso proteger a chave de sessão e autenticar o acordo que a estabelece.

Cifras clássicas e espaço de chaves

A cifra de César desloca cada letra num alfabeto. Vamos usar só as 26 maiúsculas ASCII, com A=0, B=1, até Z=25, e manter espaços e pontuação. Com deslocamento $k=3$, ZEBRA passa a CHEUD, voltando a A depois de Z.

Se $x$ é o número da letra, ciframos com $y=(x+k)\bmod26$ e recuperamos com $x=(y-k)\bmod26$. O símbolo $\bmod$ dá o resto não negativo da divisão pelo módulo. Por exemplo, $28\bmod26=2$, a letra C. O deslocamento é a chave.

Só há 26 deslocamentos distintos, incluindo zero. Experimentar todos permite reconhecer uma mensagem legível. Numa substituição monoalfabética, cada letra recebe outra letra distinta: há $26! = 26\times25\times\cdots\times1$ permutações, mas as repetições e frequências do texto continuam a dar informação. Um espaço de chaves grande, sozinho, não demonstra segurança. Estas cifras servem para estudar ideias, não para proteger dados atuais.

Aleatoriedade e bits de segurança

A segurança depende de como se gera uma chave, não de a string resultante parecer complicada. Um gerador que devolve sempre tYs90a tem um único resultado possível, mesmo misturando maiúsculas, minúsculas e números. Uma amostra isolada não permite ordenar a entropia dos geradores que produziram tYs90a, Banan4 e YYYZZZ.

Se uma chave de 128 bits é escolhida uniformemente entre todos os valores, há $2^{128}$ hipóteses. Se o gerador escolhe uniformemente entre apenas 256 dessas strings, há oito bits de entropia, porque $256=2^8$. Escrever cada resultado em 128 bits não acrescenta escolhas ao gerador. Chaves exigem geração criptograficamente adequada; datas, contadores e geradores previsíveis não são substitutos.

Bits de segurança descrevem a ordem do trabalho do melhor ataque considerado: $b$ bits corresponde aproximadamente a $2^b$ operações no modelo. Não é necessariamente o tamanho da chave, da mensagem ou do módulo. Por exemplo, um hash ideal com saída de 256 bits tem resistência genérica a colisões da ordem de 128 bits. As hipóteses sobre ataques, recursos e algoritmo fazem parte desta estimativa.

O princípio de Kerckhoffs pede que o sistema continue protegido mesmo que o adversário conheça o seu desenho, desde que os segredos necessários, como a chave, se mantenham protegidos. Esconder o algoritmo não compensa uma chave previsível.

Aritmética modular

Escrever $u\equiv v\pmod n$ significa que $u-v$ é múltiplo de $n$. Não significa que os dois inteiros são iguais. Assim, $21\equiv1\pmod{20}$ porque a diferença é 20.

Dois inteiros são coprimos quando o seu máximo divisor comum é 1. Um inverso modular de $e$ é um inteiro $d$ que satisfaz $ed\equiv1\pmod n$; existe precisamente quando $e$ e $n$ são coprimos. Para $e=3$ e módulo 20, $d=7$ serve porque $3\times7=21$ deixa resto 1. Já 2 não tem inverso módulo 20: todos os seus produtos são pares e não podem deixar resto 1.

Podemos reduzir os resultados intermédios de uma potência. Por exemplo, $26^2\bmod33=16$ e $26^4\bmod33=25$, e como $7=4+2+1$ calculamos $25\times16\times26\bmod33=5$. Em Python, pow(26, 7, 33) faz a exponenciação modular sem construir primeiro o inteiro $26^7$.

RSA de brinquedo

A conta seguinte usa RSA sem codificação, só para compreender a aritmética. Este esquema não é seguro para uso real. Os esquemas reais de cifragem e assinatura acrescentam construções como OAEP e PSS.

Bruno escolhe os primos $p=3$ e $q=11$. Então $n=pq=33$ e $\varphi(n)=(p-1)(q-1)=20$. A função $\varphi$ conta os inteiros de 1 até $n-1$ coprimos com $n$; esta fórmula usa dois primos distintos. Escolhe $e=3$, coprimo com 20, e $d=7$, porque $ed=21\equiv1\pmod{20}$. A chave pública é $(n,e)$ e a privada inclui $d$.

Para $m=5$, com $0\leq m<n$, Ana calcula $c=m^e\bmod n=125\bmod33=26$. Bruno recupera o valor em passos: $26^2\bmod33=16$, $26^4\bmod33=25$ e $26^7=26^4\times26^2\times26\bmod33=25\times16\times26\bmod33=5$. Assim $m=c^d\bmod n=5$.

Para separar as identidades, Ana usa outro par: $p=5$, $q=11$, $n=55$, $\varphi(n)=40$, $e=3$, $d=27$. Neste exemplo aritmético, o representante da mensagem é 5. A operação privada dá $s=5^{27}\bmod55=25$. A operação pública verifica $25^3\bmod55=5$. O valor 25 pertence ao par da Ana, não ao do Bruno.

Operação	Chave usada	Cálculo	Resultado
Cifrar para Bruno	Pública de Bruno	$5^3\bmod33$	26
Recuperar por Bruno	Privada de Bruno	$26^7\bmod33$	5
Operação privada da Ana	Privada da Ana	$5^{27}\bmod55$	25
Verificar essa operação	Pública da Ana	$25^3\bmod55$	5

O módulo 33 pertence ao par do Bruno; o módulo 55 pertence ao da Ana. A última linha é apenas a verificação aritmética deste exemplo, sem a codificação de uma assinatura segura.

Os números pequenos permitem fatorizar o módulo imediatamente. Mesmo com números grandes, RSA sem codificação é determinístico e tem relações algébricas exploráveis. Esta conta demonstra o mecanismo, não a segurança de um protocolo.

Dois ataques ao RSA sem codificação

Se a mensagem só pode ser 4 ou 5 e a pública é $(n=33,e=3)$, qualquer observador calcula as duas hipóteses:

$$4^3\bmod33=31.$$ $$5^3\bmod33=26.$$

Observar 26 identifica a mensagem 5 sem obter a privada. O problema é a cifragem determinística, não apenas a fatorização fácil destes números. Um esquema seguro usa a aleatoriedade e a codificação da construção, como OAEP.

Na assinatura aritmética sem codificação, também há uma falsificação escolhida pelo atacante. Escolhe $s=2$ e calcula publicamente $m=s^e\bmod n=8$. O verificador aceita $(m=8,s=2)$ porque essa é exatamente a sua igualdade de verificação. O atacante não assinou uma mensagem arbitrária previamente imposta, mas construiu um par aceite sem conhecer $d$, o que já viola a segurança de uma assinatura. PSS tem uma codificação própria, não esta regra sobre inteiros crus.

Gestão de chaves

Uma chave precisa de geração adequada, distribuição autenticada, armazenamento protegido, controlo de utilização e revogação. A rotação não desfaz a leitura de dados antigos já expostos. Uma chave de cifragem perdida pode tornar os dados irrecuperáveis; uma chave roubada pode expor os dados e permitir falsificação, conforme a sua função.

Um sal de palavra-passe não é uma chave secreta. Um nonce também não precisa, em geral, de ser secreto. O requisito de cada valor depende da construção: confundir estes papéis leva a guardar segredos no sítio errado ou a reutilizar valores que têm de ser únicos.

Quantas chaves simétricas precisamos?

Se $N$ entidades tiverem uma chave diferente para cada par, existem

$$K_{pares}=\binom{N}{2}=\frac{N(N-1)}{2}.$$

Não contamos uma chave de A para B e outra de B para A: neste modelo, é um segredo partilhado pelo par. Para seis entidades, $6\times5/2=15$. Ao acrescentar uma sétima, precisamos de seis novas chaves.

Um centro de distribuição de chaves, ou KDC, permite a cada entidade partilhar uma chave duradoura com o centro. No modelo simplificado com seis entidades e um KDC adicional, há seis destas chaves. O centro ajuda a distribuir chaves de sessão entre participantes, protegidas pelas chaves duradouras. A distribuição segue três passos: Ana pede ao centro uma chave para falar com Bruno; o centro gera uma chave de sessão e envia uma cópia a cada um, protegida pela chave duradoura de cada um; Ana e Bruno usam depois essa chave de sessão para proteger os dados. Kerberos usa um KDC com tickets e autenticadores; não envia simplesmente segredos em claro.

A conta $N$ refere-se só às ligações duradouras entre as $N$ entidades e o centro. Não conta chaves de sessão, réplicas, chaves internas nem outras entidades de uma instalação real. O preço da centralização é confiança e dependência no KDC: comprometer o centro pode afetar muitos participantes. Não confundas reduzir o número de segredos duradouros com eliminar gestão de chaves.

Verificar certificados

Um certificado associa uma identidade a uma chave pública através da assinatura de uma autoridade de certificação. Uma raiz instalada como âncora de confiança permite verificar uma cadeia.

Para aceitar o servidor, verificamos a cadeia de assinaturas, datas, nome esperado do servidor, restrições e utilizações permitidas, e os requisitos de estado/revogação da política aplicável. Uma cadeia criptograficamente válida para outra-loja.example não autoriza loja.example. Uma raiz autoassinada só é confiável porque foi instalada por um mecanismo confiável, não porque consegue assinar-se a si própria.

O certificado também não prova que o serviço é honesto, não contém erros ou está autorizado a receber todos os nossos dados, porque prova apenas uma associação de chave e identidade dentro de uma política.

Revogação e CRL

Um certificado pode ter datas válidas e, mesmo assim, estar revogado porque a chave foi comprometida. Uma CRL, lista de revogação de certificados, é uma estrutura assinada que identifica certificados revogados no seu âmbito, normalmente por número de série. Não é a lista de todos os certificados válidos ou emitidos.

Antes de usar uma CRL, verifica quem a emitiu, a assinatura, o âmbito e a atualidade, incluindo thisUpdate e nextUpdate segundo a política. O número de série tem significado com o emissor, não como identificador global isolado.

Caso: validade ainda não terminou

O certificado de api.example expira em dezembro. Uma CRL atual do emissor contém o seu número de série, 42, com revogação aplicável. Estamos em outubro. A assinatura do certificado e as datas podem passar, mas a revogação faz falhar a aceitação sob essa política.

Se a série 42 não aparecer numa CRL antiga, isso não prova que continua aceitável: faltam atualidade, âmbito e as restantes verificações da cadeia e do nome. Uma política que exige informação de estado precisa de definir também o que acontece quando essa informação não pode ser obtida.