Três protocolos de passagem

Este texto será um dos capítulos reescritos do manual sobre proteção de informações do Departamento de Engenharia de Rádio e Sistemas de Controle, bem como, a partir deste código de treinamento, o Departamento de Proteção de Informações do MIPT (GU). O tutorial completo está disponível no github (veja também versões preliminares ). Em Habrir, pretendo fazer upload de novas peças "grandes", primeiro para coletar comentários e observações úteis e, em segundo lugar, para fornecer à comunidade mais material de visão geral sobre tópicos úteis e interessantes.

Tópicos anteriores:

• Protocolos criptográficos: definições, registros, propriedades, classificação, ataques
• Protocolos de distribuição de chaves em cifras simétricas

Se houver um canal de comunicação entre Alice e Bob que não seja acessível para modificação por um invasor (ou seja, quando apenas o modelo passivo de criptoanalista for aplicável), mesmo sem uma troca preliminar de chaves secretas ou outras informações, você poderá usar as idéias usadas anteriormente na criptografia de chave pública. Depois de descrever a RSA em 1978, em 1980, Adi Shamir propôs o uso de sistemas de criptografia baseados em operações comutativas para transmitir informações sem primeiro trocar chaves secretas. Se assumirmos que as informações transmitidas são uma chave de sessão secreta gerada por uma das partes, geralmente obtemos o seguinte protocolo de três passagens.

Preliminar:

• Alice e Bob são conectados por um canal de comunicação não seguro, aberto para ouvir (mas não para modificação) por um invasor.
• Cada lado possui um par de chaves públicas e privadas $$$K_A$ , $$$k_A$ , $$$K_B$ , $$$k_B$ em conformidade.
• As partes escolheram e usaram a função de criptografia comutativa:
  

  $$

  $$\ begin {array} {lll} D_ {A} \ left (E_ {A} \ left (X \ right) \ right) = X & \ forall X, \ left \ {K_A, k_a \ right \}; \\ E_ {A} \ esquerda (E_ {B} \ esquerda (X \ direita) \ direita) = E_B \ esquerda (E_A \ esquerda (X \ direita) \ direita) & \ forall ~ K_A, K_B, X. \ end {array}$$

O protocolo consiste em três passagens com a transmissão de mensagens (daí o nome) e uma final, na qual Bob recebe a chave.

1. Alice seleciona uma nova chave de sessão $$$K$
   
   $$$Alice \ à \ esquerda \ {E_A \ esquerda (K \ direita) \ direita \} \ para Bob$
2. $$$Bob \ à \ esquerda \ {E_B \ esquerda (E_A \ esquerda (K \ direita) \ direita) \ direita \} \ para Alice$
3. Alice, usando a comutatividade da função de criptografia,
   

   $$

   $$D_A \ esquerda (E_B \ esquerda (E_A \ esquerda (K \ direita) \ direita) \ direita) = D_A \ esquerda (E_A \ esquerda (E_B \ esquerda (K \ direita) \ direita) \ direita) \ direita) = E_B \ esquerda (K \ direita).$$
   $$$Alice \ à \ esquerda \ {E_B \ esquerda (K \ direita) \ direita \} \ para Bob$
4. Bob descriptografa $$$D_B \ esquerda (E_B \ esquerda (K \ direita) \ direita) = K$

Como resultado, as partes recebem uma chave secreta compartilhada. $$$K$ .

Uma desvantagem comum de todos esses protocolos é a falta de autenticação das partes. Obviamente, no caso de um criptoanalista passivo, isso não é necessário, mas na vida real você ainda precisa considerar todos os modelos possíveis (incluindo um criptoanalista ativo) e usar protocolos que envolvam autenticação mútua das partes. Além disso, diferentemente do esquema Diffie - Hellman, a nova chave é selecionada pelo iniciador da sessão, o que permite que o iniciador, não com boas intenções, force o segundo participante a usar a chave da sessão desatualizada.

Falando em termos de propriedades de segurança , todos os representantes dessa classe de protocolos declaram apenas autenticação de chave (G7). Ao contrário do esquema Diffie - Hellman, os protocolos de três passagens não exigem a seleção de novas chaves "mestras" para cada sessão de protocolo, e é por isso que nem o sigilo direto perfeito (G9) nem a formação de novas chaves (G10) podem ser garantidos.

Opção trivial

Vamos dar um exemplo de protocolo baseado na função XOR (módulo de adição bit a bit 2). Embora essa função possa ser usada como base para a construção de sistemas de perfeita força criptográfica, para um protocolo de três passagens, essa é uma má escolha.

Antes de iniciar o protocolo, ambas as partes têm suas chaves secretas. $$$K_A$ e $$$K_B$ representando seqüências binárias aleatórias com uma distribuição uniforme de caracteres. A função de criptografia é definida como $$$E_i (X) = X \ oplus K_i$ onde $$$X$ esta mensagem também $$$K_i$ chave secreta. Obviamente:

$$

$$\ forall i, j, X: E_i \ left (E_j \ left (X \ right) \ right) = X \ oplus K_j \ oplus K_i = X \ oplus K_i \ oplus K_j = E_j \ left (E_i \ left (X \ right) \ right)$$

1. Alice seleciona uma nova chave de sessão $$$K$
   
   $$$Alice \ à \ esquerda \ {E_A \ esquerda (K \ direita) = K \ oplus K_A \ direita \} \ para Bob$
2. $$$Bob \ à \ esquerda \ {E_B \ esquerda (E_A \ esquerda (K \ direita) \ direita) = K \ oplus K_A \ oplus K_B \ direita \} \ para Alice$
3. Alice, usando a comutatividade da função de criptografia,
   

   $$

   $$D_A \ esquerda (E_B \ esquerda (E_A \ esquerda (K \ direita) \ direita) \ direita) = K \ oplus K_A \ oplus K_B \ oplus K_A = K \ oplus K_B = E_B \ esquerda (K \ direita).$$
   $$$Alice \ à \ esquerda \ {E_B \ esquerda (K \ direita) = K \ oplus K_B \ direita \} \ para Bob$
4. Bob descriptografa $$$D_B \ esquerda (E_B \ esquerda (K \ direita) \ direita) = K \ oplus K_B \ oplus K_B = K$

No final da sessão de protocolo, Alice e Bob conhecem a chave da sessão comum $$$K$ .

A escolha proposta da função de criptografia comutativa de segredo perfeito não é bem-sucedida, pois há situações em que um analista de criptografia pode determinar a chave $$$K$ . Suponha que um criptoanalista interceptou todas as três mensagens:

$$

$$K \ oplus K_A, ~~ K \ oplus K_A \ oplus K_B, ~~ K \ oplus K_B.$$

A adição do módulo 2 de todas as três mensagens fornece a chave $$$K$ . Portanto, esse sistema de criptografia não é usado.

Agora, apresentamos o protocolo para transferência confiável da chave secreta, com base na função de criptografia exponencial (comutativa). A estabilidade deste protocolo está associada à dificuldade da tarefa de calcular o logaritmo discreto: para valores conhecidos $$$y, g, p$ encontrar $$$x$ da equação $$$y = g ^ x \ bmod p$ .

Protocolo sem chave de Shamir

As partes concordam provisoriamente em um grande $$$p \ sim 2 ^ {1024}$ . Cada uma das partes escolhe uma chave secreta. $$$a$ e $$$b$ . Essas chaves são menores e mutuamente simples. $$$p-1$ . Além disso, as partes preparadas de acordo com um número especial $$$a '$ e $$$b '$ que permitem descriptografar uma mensagem criptografada com sua chave:

$$

$$\ begin {array} {l} a '= a {-1} \ mod (p-1), \\ a \ vezes a' = 1 \ mod (p-1), \\ \ em todo o X: (X ^ a) ^ {a '} = X. \\ \ end {array}$$

A última expressão é verdadeira como consequência do pequeno teorema de Fermat \ index {teorema! A fazenda é pequena}. As operações de criptografia e descriptografia são definidas da seguinte maneira:

$$

$$\ begin {array} {lll} \ forall M <p: & C = E (M) = M ^ {a} & \ mod p, \\ & D (C) = C ^ {a '} & \ mod p, \\ & D_A (E_A (M)) = M ^ {aa '} = M & \ mod p. \\ \ end {array}$$

1. Alice seleciona uma nova chave de sessão $$$K <p$
   
   $$$Alice \ à \ esquerda \ {E_A \ esquerda (K \ direita) = K ^ a \ bmod p \ direita \} \ para Bob$
2. $$$Bob \ à \ esquerda \ {E_B \ esquerda (E_A \ esquerda (K \ direita) \ direita) = K ^ {ab} \ bmod p \ direita \} \ para Alice$
3. Alice, usando a comutatividade da função de criptografia,
   

   $$

   $$D_A \ esquerda (E_B \ esquerda (E_A \ esquerda (K \ direita) \ direita) \ direita) = K ^ {aba '} = K ^ b = E_B \ esquerda (K \ direita) \ mod p.$$
   
   $$$Alice \ à \ esquerda \ {E_B \ esquerda (K \ direita) = K ^ b \ direita \} \ para Bob$
4. Bob descriptografa $$$D_B \ left (E_B \ left (K \ right) \ right) = K ^ {bb '} \ bmod p = K$

No final da sessão de protocolo, Alice e Bob conhecem a chave da sessão comum $$$K$ .

Suponha que um criptoanalista interceptou três mensagens:

$$

$$\ begin {array} {l} y_1 = K ^ a \ bmod p, \\ y_2 = K ^ {ab} \ bmod p, \\ y_3 = K ^ b \ bmod p. \\ \ end {array}$$

Para encontrar a chave $$$K$ , um criptoanalista precisa resolver um sistema dessas três equações, que possui uma complexidade computacional muito grande, inaceitável do ponto de vista prático, se todos os três números $$$a, b, ab$ bastante grande. Suponha que $$$a$ (ou $$$b$ ) não é suficiente. Então, computando graus sucessivos $$$y_3$ (ou $$$y_1$ ), pode ser encontrado $$$a$ (ou $$$b$ ), comparando o resultado com $$$y_2$ . Saber $$$a$ fácil de encontrar $$$a ^ {- 1} \ bmod (p-1)$ e $$$K = (y_1) ^ {a ^ {- 1}} \ bmod p$ .

Sistema de criptografia Massey-Omura

Em 1982, James Massey e Jim Omura registraram uma patente (James Massey, Jim K. Omura), melhorando (em sua opinião) o protocolo sem chave de Shamir. Como uma operação de criptografia em vez de exponenciação em um grupo multiplicativo $$$\ mathbb {Z} _p ^ *$ eles sugeriram o uso de exponenciação no campo de Galois $$$\ mathbb {GF} {2 ^ n}$ . Chave secreta de cada parte (para Alice - $$$a$ ) deve satisfazer as condições:

$$

$$\ begin {array} {l} a \ in \ mathbb {GF} {2 ^ n}, \\ gfd \ left (a, x ^ {n-1} + x ^ {n-2} + ... + x + 1 \ right) = 1. \\ \ end {array}$$

Caso contrário, o protocolo será semelhante.

Posfácio

O autor será grato por comentários factuais e outros sobre o texto.