Loading
Nota de Estudos
Study Reminders
Support
Text Version

Protocolos De Troca De Chaves

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fundamentos of Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bangalore Lecture – 36 Key Exchange Protocolos Parte 1 (Consulte O Slide Time: 00:35) Olá todos, bem-vindos a esta palestra. o plano para esta palestra é o seguinte, nesta palestra, introduziremos a noção de protocolos de troca de chave anônima. Veremos as várias definições e veremos as ideias subjacentes envolvidas por trás do protocolo de troca de chave seminal devido à Diffie e Hellman. (Consulte O Tempo De Deslizamento: 00 :47) Então só para recapitear, o quadro até agora é o seguinte. Até agora tínhamos visto vários poderosos primitivos simétricos, tanto no mundo passivo como no mundo ativo. Temos visto várias noções de segurança, como criptografia autenticada, segurança CCA, segurança CPA; tínhamos visto outras primitivas para integridade e autenticações como código de autenticação de mensagens. E tínhamos visto construções de todas essas noções de segurança, onde as construções são baseadas em pseudo funções aleatórias, pseudo permutação aleatória, fortes pseudo permutações aleatórias e assim por diante. Por isso, um fato básico sobre todas as construções que tínhamos visto até agora é que a segurança para todas essas primitivas criptográficas que vimos, se mantém sob a suposição de que uma chave desconhecida aleatória comum já está acordada entre as partes, especificamente o emissor e o receptor. Então agora a pergunta que queremos abordar aqui é que como uma chave aleatória comum é acordada privadamente sobre um canal público inseguro? Então até agora estávamos assumindo que de alguma forma o acordo chave já aconteceu e dado que o acordo chave já aconteceu, vimos como projetar esquemas de criptografia autenticados, esquemas de criptografia segura CCA, esquemas de criptografia segura de CPA e etc. Mas agora gostaríamos de abordar o principal problema. Gostaríamos de abordar a questão de que como no primeiro lugar em si, uma chave aleatória é privadamente acordada sobre um canal público e inseguro. E isso soa como uma situação clássica do catch-22 certo? Porque se você tem um mecanismo onde emissor e receptor podem trocar de forma segura uma chave desconhecida que é conhecida apenas para o emissor e o receptor sobre um canal público inseguro, então usando esse mecanismo, eles no primeiro lugar em si podem fazer a comunicação segura também. Então o que exatamente pegar 22 situação significa é, onde você tem um cenário, onde dizer por exemplo você é um recém-formado, sai da faculdade e se aplica para um emprego e quando o candidato enfrenta a entrevista de emprego, ele encara a pergunta que você tem alguma experiência ou não? Mas em primeiro lugar o candidato obterá experiência apenas se o cargo for dado ao candidato. Portanto, é isso que queremos dizer com a situação do catch-22. E estamos exatamente enfrentando o mesmo cenário aqui também. Sabemos como fazer a comunicação segura, assumindo que sabemos trocar de forma segura a chave sobre um canal inseguro. (Consulte O Tempo De Deslizamento: 03:16) Assim, isso nos leva ao problema da troca de chave anônima. Então, vamos definir o que exatamente é o problema de troca de chave anônima. Por isso, a configuração é a seguinte: temos um emissor e o receptor, e assumimos que, de alguma forma, eles se conhecem a identidade de cada um ’, mas não possuiram nenhuma informação pré-compartilhada. Então você pode estar se perguntando que como é possível um remetente e o receptor que estão se encontrando pela primeira vez que conhecem cada uma outra entidade ’. Mais adiante, removamos esta suposição também. Mas, para o momento, para tornar mais simples a descrição do problema de troca de chave anônima, vamos supor que tanto o remetente quanto o receptor conhecem cada outra entidade ’. Assim, o objetivo aqui é projetar um par de protocolos, que eu denote como Π para o remetente, e Π para o receptor, que agora são protocolos interativos. E o espaço de saída deste protocolo será algum e o objetivo é projetar tal par de protocolos um para o remetente e outro para o receptor tal que de acordo com os protocolos individuais remetente e receptor se comuniquem sobre um canal inseguro e no final de seus respectivos protocolos, emissor e saída de receptor algumas respectivas chaves. Assim, a saída do remetente I denote como e saída do receptor I denote como. E nós assumimos nessa definição de problema que temos um eavesdropper, um eavesdropper delimitado computacionalmente, que está conseguindo acesso a toda a comunicação que está acontecendo entre o emissor e o receptor. Assim, o adversário está ciente do par de protocolos utilizando o qual o remetente e um receptor estão interagindo. A saber, conheça as etapas do Π e Π e também obtém acesso as informações que são trocadas entre o emissor e o receptor, que chamamos de transcrição de protocolo, que denotamos como. E observe que essa transcrição do protocolo vai ser uma variável aleatória, pois as informações que remetente e receptor vão trocar, vão depender da aleatoriedade interna com a qual o emissor e o receptor vão se chamar nos respectivos protocolos Π e Π. Portanto, não é o caso de que remetente e receptor trocarão o mesmo conjunto de valores toda vez que invocarem este protocolo Π, pois estão invocando um protocolo randomizado. Agora as propriedades que eu necessito a partir deste par de protocolos Π e Π são as seguintes. A primeira propriedade é a propriedade de correção, que diz que com uma probabilidade muito alta, as saídas individuais do remetente e do receptor devem ser as mesmas. A saber, a saída kand output kdeverá ser igual. E agora podemos ter 2 variantes de segurança, que podemos exigir a partir desses protocolos Π e Π. A primeira definição é uma forma mais fraca de privacidade, que chamo de privacidade fraca, que exige que com muito alta probabilidade, um adversário computacionalmente delimitado, mesmo depois de saber a transcrição do protocolo não aprenda nada sobre a saída do remetente e do receptor. Por isso, aqui não estou exigindo segurança no sentido indistinguível; aqui a exigência é no sentido de que ou o adversário não deve aprender toda a kand a k inteira. Está bem se o adversário aprende com “ algo ” sobre kand k. Mas a exigência aqui é que, como uma totalidade, as saídas do remetente e do receptor não devem ser aprendidas pelo atacante. Considerando que podemos ir para uma maior noção de segurança, que chamo de privacidade mais forte, que exige que do ponto de vista desse adversário, mesmo que o adversário tenha acesso à transcrição do protocolo, do ponto de vista do adversário as respectivas saídas do remetente e da respectiva saída do receptor, devem ser computacionalmente distinguíveis de um elemento uniformemente aleatório do espaço-chave de saída. Portanto, essa é uma noção mais mais forte de sigilo. Porque se você for para a noção mais forte de sigilo, então não é permitido que adversário aprenda algo sobre os respectivos bits de kand k; do ponto de vista do adversário, as respectivas saídas do remetente e do receptor poderiam ser qualquer elemento candidato do espaço-chave subjacente. Por isso, veremos a construção satisfazendo tanto a forma mais fraca de privacidade quanto a construção que satisfaça a forma mais forte de privacidade. Você pode estar se perguntando que por que exatamente nós nos preocupamos em alcançar uma forma mais fraca de privacidade. Assim, isso será claro mais adiante. Olhando à frente, veremos construções alcançando uma forma mais fraca de privacidade, com base em consumos criptógrafos que são brandos. Considerando que se você deseja alcançar protocolos de troca de chave que alcanam uma noção mais forte de privacidade, então temos que ir para premissas criptográficas que são ligeiramente mais fortes. (Consulte O Tempo De Deslizamento: 08 :05) Então, tínhamos visto intuitivamente o que exatamente significa privacidade e meios de privacidade fortes. Por isso, agora vamos em frente e modelar esses requisitos formalmente por um jogo baseado em indistinção. E enquanto dá as definições de indistinguibilidade, pela simplicidade supomos que estamos considerando protocolos de troca de chave que tem erro de 0 de correção. Isso significa com probabilidade 1, a saída do emissor e saída do receptor será a mesma, portanto, estamos considerando esse tipo de protocolos de troca de chave. Por isso, vejamos primeiro como modelar a fraca-privacidade e lembrar a exigência dos estados fracos de privacidade mesmo que o adversário veja toda a troca de transcrição entre o remetente e o receptor, a chave de saída resultante obtida pelo remetente e o receptor não deve ser aprendida ou não deve ser conhecida desse adversário, na sua totalidade. E esse requisito é modelado por esse jogo. Assim, este jogo, que chamamos de KEweav (, aqui KE significa chave-troca e um superscript weav denota fraca espionagem ou privacidade fraca, aqui o jogo é jogado entre um desafiante e um adversário de tempo polo. E o que o desafiante ou o experimento faz é, basicamente ele simula uma instância aleatória do protocolo chave de troca Π. Assim, o protocolo Π é basicamente o par de protocolos e, onde o protocolo vai ser invocado pelo remetente e o protocolo vai ser invocado pelo receptor. Mas como uma coleção, chamamos de protocolo. Assim, o desafiante basicamente simula uma instância aleatória do protocolo, fazendo o papel do remetente e de um receptor em sua mente com suas respectivas moedas conforme o protocolo e ele gera uma transcrição Π. Agora o que faz é, lança um desafio ao adversário, a saber, a transcrição e esta modela o fato de que no mundo real, um adversário sentado entre o remetente e o receptor, teria observado uma transcrição que é gerada pelo emissor e pelo receptor executando o protocolo. Agora o desafio para o adversário é que ao ver essa transcrição Π, tem que descobrir o que exatamente é o valor de chave, qual emissor e receptor teriam obtido por correria pelo respeito a esta transcrição de protocolo Π. Por isso, basicamente o adversário tem que responder com uma chave do espaço chave, que eu denoço como. E a forma como definimos a saída do experimento é a seguinte. Dizemos que adversário ganhou o experimento, o que também é denotado dizendo que a saída do experimento é 1, se e só se o palpite do adversário for exatamente igual a. Isso significa, o adversário A, sem saber a aleatoriedade interna do remetente e a aleatoriedade interna do receptor e por apenas observar a transcrição do protocolo Π, é capaz de apresentar a chave exata, que remetente e receptor vão obter por rodar com relação a esta transcrição de protocolo Π. Se isso acontecer então dizemos que a saída do experimento é de 1. E a definição de segurança é, dizemos que o protocolo de geração de chave Π possui privacidade fraca, se para qualquer adversário de tempo poltica participando deste experimento, existe alguma função insignificante, tal que a probabilidade de que adversário vença o experimento é superior delimitado por alguma função insignificante, onde a probabilidade é tomada sobre as moedas aleatórias do desafiante. A saber, as moedas aleatórias, com as quais está simulando o papel do remetente e do receptor. Por isso, observe que aqui o adversário não tem que distinguir entre algo. O objetivo do adversário é chegar com a chave que o remetente e o receptor vão obter com relação à transcrição do protocolo Π. É por isso que a definição de segurança não terá uma expressão da forma que adversário chances de ganhar o experimento é superior delimitado pela metade mais alguma função insignificante. O objetivo do adversário é chegar com a chave exata com qual remetente e receptor vão obter executando o protocolo Π e que é consistente com a transcrição do protocolo. Também nesta definição permitimos que o adversário vença o jogo com alguma probabilidade insignificante porque sempre há um adversário de adivinhação, que pode apenas adivinhar algum candidato do espaço chave e com probabilidade diferente de zero ele pode se transformar exatamente igual a. (Consulte O Tempo De Deslizamento: 12:31) Então, agora, vamos ver como podemos modelar a privacidade forte. E lembre-se do objetivo da forte-privacidade é que um adversário que monitora a transcrição trocada entre o emissor e o receptor, não deve ser capaz de distinguir a chave resultante que remetente e receptor vão obter, a partir de qualquer elemento uniformemente aleatório do espaço chave. E novamente para modelar a privacidade forte, assumimos protocolos de troca de chave onde há erro de 0 de correção. Isso está novamente sem perda de generalidade; o seu muito direto em frente a incorporar essa condição também na definição de segurança. Por isso, agora o experimento se chama KEeav (porque agora não estamos modelando a privacidade fraca. Estamos agora modelando forte-a privacidade aqui e as regras do jogo são as seguintes. O adversário está à espera de um desafio aqui e o desafio volta a ser gerado mais ou menos da mesma forma como foi gerado no experimento para a fraca privacidade. A saber, o desafiante aqui desempenha o papel do remetente e do receptor em sua mente e invoca uma instância do protocolo para o remetente e invocação na instância do protocolo para o receptor, com sua respectiva aleatoriedade e ele gera uma transcrição de protocolo Π. Essa transcrição protocolar agora é dada como um desafio para o adversário. Então, isso modela o fato de que a eavesdropper entre o remetente e o receptor teria eaveslargado e obtido a transcrição do protocolo Π. E agora já que estamos tentando modelar a noção baseada em indistinção de segurança no contexto do protocolo de troca de chave, o desafiante adicionalmente lança um desafio da seguinte forma. Ele joga uma moeda justa, com probabilidade 1/2 pode ser de 0 ou com probabilidade 1/2 pode ser de 1. E agora além da transcrição, dependendo se o tostão da moeda é de 0 ou se o tostão da moeda é de 1, o desafiante submete um elemento aleatório do espaço chave para o adversário ou a chave, que o remetente e o receptor teriam obtido executando a instância de protocolo na mente do desafiante ’. Agora adversário não sabe, se o valor a partir da chave-espaço que está vendo é um elemento aleatório do espaço-chave ou se é uma chave que o emissor e o receptor teriam obtido executando o protocolo Π e obtendo a transcrição. Por isso, o desafio para o adversário é encontrar se ele está no método ou se está no método. E submete a sua resposta, nomeadamente um pouco. E a definição aqui é, dizemos que o adversário vence o experimento, que também é denotado como a saída do experimento é 1, se e somente se adversário A poderia identificar corretamente se ele está vendo um elemento conforme o método ou se ele está vendo um elemento do espaço chave como para o método. E a definição de forte-privacidade aqui é, dizemos que um protocolo de troca de chave Π lhe dá forte-privacidade, se para qualquer adversário de tempo poltica participar deste experimento, há alguma função insignificante, de tal forma que o adversário de probabilidade vence o experimento é superior delimitado pela metade mais alguma função insignificante. Então, agora isso é diferente da definição da fraca-privacidade. Porque na fraca-privacidade o objetivo desse adversário era chegar com o exato que é consistente, ou que teria sido obtido pelo remetente e receptor conforme a transcrição Π. Mas agora aqui o objetivo do adversário é distinguir o, que remetente e receptor vão se obter conforme a transcrição do protocolo Π, a partir de um elemento uniformemente aleatório da chave-space.Então é por isso que agora estamos tendo uma condição parecida com a definição baseada em indistinção e novamente estamos colocando essa condição meia mais insignificante, pois sempre há uma estratégia de adivinhação pelo adversário e a estratégia de adivinhação do adversário será apenas para adivinhar se ele está no método ou se está no método. E a probabilidade de sucesso dessa estratégia de adivinhação é de 1/2. Fora que estamos dispostos a deixar que o adversário ganhe essa experiência com alguma função insignificante porque estamos no mundo computacional. Uma formulação equivalente dessa noção de forte-privacidade é que dizemos que o protocolo Π lhe dá forte-privacidade, se para qualquer adversário de tempo poltica participar deste experimento, a vantagem distintiva do adversário é superior delimitado por alguma função insignificante no parâmetro de segurança. Isso significa que não importa se o desafiante gerou o desafio pelo método = 0 ou se ele gerou o desafio por método. Em ambos os casos a resposta do adversário deve ser quase a mesma ′ = 1, exceto com alguma probabilidade insignificante. E podemos provar que ambas as condições são equivalentes umas às outras. A saber, se você tem um protocolo de troca de chave que satisfaça a primeira condição então ela também implica que satisfaça a segunda condição e vice-versa. Portanto, dependendo da nossa conveniência podemos usar qualquer uma dessas duas condições. (Consulte O Slide Time: 17:41) Então agora temos as definições de segurança de protocolos de troca de chave e agora você pode estar se perguntando se realmente é possível projetar protocolos de troca de chave, onde emissor e receptor, sem ter nenhuma informação pré-compartilhada pode fazer alguma comunicação sobre um canal inseguro publicamente conhecido e acaba concordando sobre uma chave que não é conhecida a qualquer terceiro? Então em um nível muito alto pode parecer uma tarefa impossível porque como ela é possível? Ou seja, um remetente e receptor desconhecido que apenas conhecem sua identidade e não possuem informações pré-compartilhadas de forma alguma, podem fazer interação pública e concordar sobre algo que é conhecido apenas por eles. Mas acontece que de fato temos tais protocolos de troca de chave. E a base deste protocolo de troca de chave deve-se ao trabalho pioneiro da Diffie e Hellman que são o primeiro par de criptógrafos que surgiu com seu protocolo de troca de chave seminal. Por isso, nesta palestra vamos ver as ideias subjacentes com base nas quais o seu protocolo chave de troca foi desenvolvido. Por isso, antes disso deixe-me contar alguma história fascinante sobre como exatamente o seu protocolo chave de troca entrou em existência. Assim, Whitfield Diffie estava muito interessado em resolver o problema de troca de chave. E acreditava fortemente que realmente é possível que um remetente e um receptor façam a comunicação pública e concorde sobre uma chave secreta comum. E em 1974 ele deu um seminário no laboratório IBMs Watson para um público cético, que não estava comprando sua ideia de que de fato chave-troca é possível sobre um canal público. O único resultado positivo que saiu daquele seminário é que ele chegou a saber que não é só ele, há uma outra pessoa, um professor de Stanford, chamado Martin Hellman, que também está trabalhando no mesmo problema e tentando chegar a protocolos de troca de chave pública. E assim que o Diffie chegou a saber sobre isso, ele iniciou alguma jornada de estrada de 5000 quilômetros para se encontrar e par com Martin Hellman e foi assim que eles iniciaram seu trabalho em chegar a um protocolo para resolver o problema de troca de chave. E eles trabalham por dois anos rigorosamente e finalmente eles vieram com seu inovador protocolo de troca de chave Diffie-Hellman. (Consulte O Tempo De Deslizamento: 20 :07) Então, vamos tentar entender a ideia subjacente que está lá no protocolo de troca de chave Diffe-Hellman. Por isso, a ideia básica por trás de seu protocolo de troca de chave é que existem várias tarefas neste mundo, que têm assimetria ou são assimétricas na natureza. E assimetria no sentido de que eles são muito fáceis de executar. Isso significa que essas ações são muito fáceis de executar mas extremamente difíceis de reverter. Então o que eu quero dizer com isso é imaginar que eu dou um cadeado em um estado aberto. E se eu pedir para prendê-lo então você não precisa de nenhuma chave. Você só tem que pressionar a cabeça do cadeado e a partir do estado aberto você pode facilmente levá-lo para o estado bloqueado. Mas agora se eu te der o cadeado no estado bloqueado e peço que você leve de volta para o estado aberto então será extremamente difícil para você se você não possuir a chave para o cadeado. Então, nesse sentido, isso você tem uma ação aqui onde ir de um estado para outro é extremamente fácil. Mas voltar do estado obtido de volta para o estado original é extremamente difícil. Não é impossível. Lembre-se que estou dizendo o seu “ extremamente difícil ” para voltar ou reverter a ação se você não souber a chave. Pode haver outros métodos para reverter essa ação sem a chave, mas essas alternativas serão extremamente difíceis. Da mesma forma considerar esta tarefa que você recebe uma cor conhecida publicamente e dizer se você quer preparar uma mistura secreta, então é muito fácil você fazer isso tirando aquela cor publicamente conhecida e adicionando aquela cor existente, uma cor secreta e então obtendo a mistura. Por isso, preparar a mistura é muito fácil para você. Mas se alguém me dá esta mistura e não me diz o que exatamente foi a cor secreta que foi acrescentada à cor pública para obter esta mistura, então será muito difícil para mim descobrir ou separar esta mistura em seus constituintes, nomeadamente a cor publicamente conhecida e a cor secreta que adicionei aqui. Por isso, nesse sentido, preparar uma mistura é fácil mas separar a mistura para seus componentes individuais é uma tarefa extremamente difícil. Por isso, esse novo requisito não estava lá quando visávamos obter o protocolo de troca de chave Diffie Hellman com uma noção mais fraca de privacidade. Porque lá a exigência era de que o adversário não deveria aprender nem mesmo se sabe,. Mas agora já que estamos visando uma noção de privacidade mais forte, estamos colocando requisitos adicionais sobre a função e. A saber, nós exigimos que mesmo que alguém saiba, o valor de para aquele adversário ou para essa pessoa deve ser computacionalmente indistinguível de qualquer valor aleatório do conjunto. E se assumirmos que realmente a nossa função e satisfaça esta exigência adicional, é fácil perceber que o mesmo protocolo que acabámos de ver a dar-nos a noção de privacidade mais fraca, acaba por nos dar uma noção de privacidade mais forte. Não temos que adicionar etapa adicional; apenas temos que fazer suposições mais fortes sobre as funções e. Então isso me leva até o final desta palestra. Só para resumir rapidamente, nesta palestra, introduzimos o problema de troca de chave onde o objetivo do remetente e do receptor é interagir publicamente sobre um canal inseguro com nenhum pre