Fundamentos da Cryptography Prof. Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bangalore Lecture – 54 Schnorr Signature Scheme e TLS ou SSL (Consulte o tempo de deslizamento: 00:33) Olá a todos. Bem-vindo a esta palestra. O plano para esta palestra é o seguinte e esta palestra discutiremos uma transformação ou heurística muito poderosa, que chamamos de Fiat-Shamir heuristic. O que nos permite obter esquemas de assinatura digital a partir de quaisquer esquemas de identificação seguros e depois veremos como aplicar esta transformação em nenhum esquema de assinatura para obter um esquema de assinatura digital com base na suposição de log discreta. Por fim, veremos uma visão geral do protocolo TLS e SSL. (Consulte O Slide Time: 01:00)Então, vamos iniciar nossa discussão com a transformação Fiat-Shamir. Então, o que a Fiat-Shamir heurística ou transformação faz é, é preciso qualquer esquema de identificação interativa de 3 redondas, que tenha estrutura de comprometimento, desafio, resposta. E a transformação converte esse protocolo interativo em um protocolo não interativo. Não interativo no sentido de que ele terá apenas uma rodada de interação do prover para o verificador e usando esse protocolo não interativo basicamente, acabamos conseguindo um esquema de assinatura de 1. A ideia por trás dessa transformação é que, se você tem um esquema de identificação e se deseja obter um esquema de assinatura fora disso, então para assinar a mensagem usando a chave de assinatura, o signo tem que agir como um prover e ele tem que executar todo o protocolo do esquema de identificação em sua mente. Conforme as regras dessa transformação, venha com a transcrição inteira em um único tiro e dê para o verificador. Isso significa que, no protocolo interativo de 3 redondos que estava ali para o esquema de identificação, o desafio teria sido escolhido pelo verificador. Mas o que estamos dizendo aqui é que depois de fazer essa transformação, até mesmo o desafio também será colhida pelo próprio prover. Ele tem que desempenhar o papel do prover, assim como o verificador simultaneamente. Então, você pode estar se perguntando que se o prover for dada a disposição para escolher o desafio em nome o verificador, o prover malicioso ou o prover de trapaça podem trapacear. Pode não escolher um desafio uniformemente aleatório. Acontece que a transformação Fiat-Shamir é tão inteligente que acaba mesmo forçando o prover de trapaça a escolher uniformemente desafios aleatórios. Então, aqui está como fazemos a conversão de 3-round protocolo interativo em 1-round de protocolo interativo. Então, nós estamos dando esquema de identificação de 3 redondos Gen, 1, 2,. Usando-o, queremos obter sinal de esquema de assinatura de 1 redondos = (Gen, Sign, Vrfy). Como parte dessa transformação, assumimos que temos a descrição pública de alguma função hash mapeando entradas arbitrárias de comprimento arbitral para os elementos do espaço de desafio do esquema de identificação subjacente. Assim, o algoritmo de geração de chaves deste esquema de assinatura, será o mesmo que o algoritmo de geração de chave do seu esquema de identificação. Agora o algoritmo de assinatura é o seguinte. Imagine, há um signo que tem a chave de assinatura sk, e tem uma mensagem sobre a qual quer gerar sua assinatura. Então, como eu disse anteriormente tem que desempenhar o papel do prover, assim como o verificador do próprio esquema de identificação. Então, ele executa o algoritmo P1 na chave de assinatura para obter o comprometimento I e uma informação de estado, e agora ele tem que escolher o desafio aleatoriedade r em nome do próprio verificador. Por isso, o ideal deve escolher a aleatoriedade do desafiante r uniformemente a partir do espaço de desafio, mas agora vamos projetar um esquema de assinatura. Por isso, a mensagem também deve entrar em cena enquanto escolhe a aleatoriedade r ou o desafiante r. Então, para escolher o desafio. Então, a ideia aqui é basicamente, o desafio r vai ser de alguma forma associado com a mensagem, que o remetente quer assinar aqui. E se assumirmos ou se modelarmos a função hash subjacente como um oráculo aleatório aqui, verifica-se que o valor r, que signer vai obter gerando r como por este método, será de fato um valor uniformemente aleatório a partir do espaço de impugnação do esquema de identificação subjacente. Uma vez que o r é gerado, o signer tem que gerar a parte de resposta, a saber, executando o algoritmo P2 e finalmente a assinatura é (r, s). Então, agora para enviar uma mensagem assinada para o verificador, ele vai apenas enviar uma mensagem junto com a assinatura (r, s). E o modo como verificador verifica a assinatura é, ele executa o algoritmo de verificação do esquema de identificação subjacente, mas há uma diferença. No esquema de identificação original, o verificador estava verificando se a saída do algoritmo de verificação com a chave de verificação e a parte (r, s) da transcrição dá a parte de I da transcrição ou não. Aqui por outro lado, a s parte do algoritmo de verificação do esquema de assinatura, o verificador vai executar o algoritmo de verificação do esquema de identificação subjacente, mas não se compara a saída da função V com o componente I , pois ele não conhece o componente I como ele é. Se você vir a estrutura deste esquema de assinatura, o I não é dado pelo signer ao verificador, enquanto que no esquema de identificação, o verificador já teria obtido um I e por isso poderia comparar a saída da função V com o comprometimento I dado pelo prover. Assim, no algoritmo de verificação do esquema de assinatura, I é computado a partir do zero pelo verificador executando a função V e idealmente este I deverá ser o mesmo I, o qual um prover legítimo no esquema de identificação teria se comprometido com um verificador honesto. Agora, para verificar a assinatura o que o verificador faz é, ele tem agora o valor I , ele tem agora o valor m e cheques. Em seguida, aceita a assinatura, caso contrário, rejeita a assinatura. O ideal, se realmente o signer e o signer for honesto, então o I gerado executando a função de verificação ou a função V na chave de verificação r e s teria dado um I, tal que deveria de fato ser igual a r. Então, a declaração do teorema que podemos provar aqui é que se você está no modelo aleatório de oráculo, e se esse esquema de identificação pi é um esquema de identificação segura, então o esquema de assinatura que nós geramos aqui de fato é um esquema de assinatura seguro. A prova está ligeiramente envolvida, e temos que ir para as tecnicalidades do modelo aleatório de oráculo. Então, eu estou pulando a prova formal completa, vamos apenas ver uma visão geral da prova, você pode ver a prova formal completa no livro de Katz e Lindell. A ideia aqui é que se você ver a distribuição de r que o signo gerou no algoritmo de assinatura, sua distribuição é exatamente a mesma que teria sido em uma execução real do esquema de identificação, desde que você esteja no modelo aleatório-oracle. Isso significa, até mesmo o signo é corrupto, não tem controle sobre a aleatoriedade r porque vai ser um valor uniformemente aleatório, pois vai ser uma saída do oráculo aleatório. A forma como projetamos o esquema de assinatura, no algoritmo de assinatura, o randomness r, ou o desafio r, que o signer está gerando, é basicamente uma função tanto do comprometimento I como da mensagem em que quer gerar a assinatura. Então, se temos um adversário que quer forjar uma assinatura em nome de signer sem saber realmente a chave de assinatura sk, então basicamente o que o falsificador tem a fazer é sem saber a chave de assinatura sk, ele tem que chegar a algumas I e informações de estado e tem que apresentar algum desafio r, ao consultar o oráculo aleatório, e tem que chegar a alguma resposta s, tal que no geral é uma transcrição aceitante, a saber (I, r, s) é uma transcrição aceitante e não apenas aquela saída do aleatório-oráculo sobre o comprometimento I e a mensagem é igual a r. Essa coisa toda tem a ver sem saber realmente a chave de assinatura sk. Se existe um adversário que pode de fato fazer isso com uma probabilidade significativa, então intuitivamente quer dizer que tem um adversário que pode até mesmo forjar ou quem pode quebrar a segurança deste esquema de identificação subjacente, a saber, mesmo sem saber a chave de assinatura ou a chave secreta, sk, que adversário poderia vir a tona com uma transcrição de aceitação legítima em nome do prover e convencer o verificador e obtê-lo aceito. Mas isso vai contra o pressuposto de que o esquema de identificação subjacente é um esquema de identificação seguro. Então, essa é uma ideia intuitiva por trás dessa transformação Fiat-Shamir. Não vou entrar nos detalhes formais completos. (Consulte O Slide Time: 10:20)Agora, vamos ver como podemos aplicar a transformação Fiat-Shamir no esquema de identificação devido ao Schnorr e como resultado, obtemos um esquema de assinatura, que chamamos como Esqunorr Signature Scheme. Eu ressalto que essa transformação Fiat-Shamir é uma transformação genérica. Pode ser aplicado em qualquer esquema de identificação, em qualquer esquema de identificação de três redondos, para obter um esquema de assinatura de 1 redondos. Aqui estamos a aplicá-lo no contexto do Esquema de Identificação de Schnorr. Por isso, lembre-se que no Esquema de Identificação de Schnorr, a chave secreta:, e o esquema de identificação é o seguinte: o prover no esquema de identificação quer saber, por isso, provar que se compromete, submetendo-se gk. O verificador lança um linear aleatório combinado r e o prover tem que chegar a uma resposta s. A saber, uma combinação linear (mod e o verificador verifica o − = ou não. Se você aplicar o heurístico Fiat-Shamir no esquema de identificação, o algoritmo de geração de chaves do esquema de assinatura será o seguinte: a chave de verificação onde a chave de assinatura correspondente:. Junto com isso, haverá uma descrição publicamente conhecida de uma função hash ó r ⇒ Z, pois o espaço de desafio aqui não passa de Z. O algoritmo de assinatura será o seguinte: imagine que há um signo com um para assinar uma mensagem m. Ele primeiro computa o comprometimento escolhem um valor escolhido aleatoriamente e, em seguida, ele escolhe o desafio em nome do verificador chamando, ele computa o mod de resposta e a assinatura é (r, s, m). Para verificar a assinatura, o verificador tem que gerar o comprometimento de comprometimento −, e o que vier à tona, isso é tratado como o comprometimento do signo para o esquema de identificação subjacente de Schnorr. Em seguida, o verificador gera o desafio que esse comprometimento computado e a mensagem que o assinante está enviando teria produzido, então para isso o verificador chama aleatório-oracle Output 1, iff, que o signo está reivindicando fazer parte da assinatura. Quanto à segurança da heurística Fiat-Shamir, este esquema de assinatura de 1 redondos é de fato um esquema de assinatura de segurança no modelo aleatório-oracle. Então, agora temos um esquema de assinatura de candidato baseado na discreta assunção de log. Acabou-se que Schnorr patenteou esta ideia. Então, ele basicamente patenteou seu esquema de identificação de três redondas, então como resultado o esquema de assinatura que sai aplicando a transformação Fiat-Shamir também é considerado como patenteado, portanto, não podemos usá-lo no domínio público. Então o que o NIST fez foi, desenvolveu uma variação do esquema de Identificação de Schnorr e ao aplicar a transformação Fiat-Shamir nessa variante, obteve um esquema de assinatura baseado na discreta assunção de log, que chamamos de DSA, Digital Signature Algoritmo. É um padrão bem conhecido que utilizamos na prática e o grupo subjacente que utilizamos neste algoritmo DSA é o grupo baseado no ponto de curvas elípticas modulo prime, então a instanciação do DSA é chamada como ECDSA, Eliptic Curve Digital Signature Algoritmo e este é um algoritmo de assinatura digital muito popularmente usado em várias aplicações mundiais reais. (Consulte O Slide Time: 14:48) Então, agora mais ou menos chegamos ao fim da discussão sobre criptografia de chave pública. Vimos instanciação de esquema de criptografia, assinaturas digitais e etc. Durante a primeira metade do curso, discutimos com rigor sobre a criptografia de chave simétrica. Por isso, agora veremos que como combinamos várias primitivas criptográficas em ambos os mundos, chegamos a um protocolo de comunicação seguro mundial real. Então o que eu vou discutir é uma visão geral de nível muito alto do protocolo SSL, que na verdade é o sucessor do protocolo TLS e esta é apenas uma visão geral de alto nível. Nós não devemos tratar a discussão como uma implementação real do SSL para os detalhes exatos sob análise completa do protocolo SSL. Você deve se referir a qualquer texto padrão na segurança da rede. Então, aqui está como funciona o protocolo SSL. Então, imagine que você tem um computador e no seu navegador, você digita https seguido por alguns xyz.com, digamos google.com. Então, assim que você digita https, o s aqui denota que você realmente deseja iniciar uma sessão de comunicação segura com o servidor chamado mail.google.com. E assim que você digita isso realmente o protocolo SSL começa a executar, e como parte deste protocolo SSL, existem dois sub protocolos, que são executados. Há um protocolo de handshake onde acontece alguma interação entre o cliente, que o navegador neste caso e servidor que é google.com neste caso. Já em relação ao protocolo de handshake se tudo correr bem, então uma chave é estabelecida entre o servidor e o cliente. Então, para começar com o cliente, e o servidor não tinha informações pré-compartilhadas mas assim que o protocolo de handshake é executado e troca de chave autenticada acontece entre o servidor e o cliente. Se o protocolo de handshake for bem-sucedido, a chave será estabelecida com sucesso entre o servidor e o cliente. Agora, uma vez que a chave é estabelecida, o segundo sub protocolo que é iniciado executando é o protocolo da camada de registro. Este protocolo de camada de registro o que ele faz é a comunicação privada autenticada entre o servidor e o cliente utilizando as chaves que foram estabelecidas durante o protocolo de handshake. Em termos de primitivas criptográficas para fazer a troca de chave autenticada, o protocolo de handshake usa criptografia de chave pública enquanto uma vez que a chave foi estabelecida para fazer a comunicação real entre o servidor e o cliente, o protocolo da camada de registro utiliza os primitivos de chave privada. Agora você pode ver que como exatamente as várias primitivas criptográficas se combinam para fazer ou resolver todo o problema da comunicação segura aqui. Por isso, agora vamos nos aprofundar um pouco mais nos detalhes do protocolo de handshake e do protocolo da camada de registro. Por isso, lembre-se que o objetivo do protocolo de handshake é fazer uma troca de chave autenticada entre o cliente e o servidor. Imagine que o servidor tenha sua própria chave pública e uma chave de descriptografia para um mecanismo de encapsulamento de chave segura CCA e imagine que temos várias autoridades de certificação disponíveis no mercado que possuem a sua própria chave de assinatura e chave de verificação.Neste exemplo, estou supondo que existam quatro autoridades de certificação, e presumo aqui que a chave de verificação das autoridades do certificado já esteja pré-configurada no navegador, que é utilizado pelo cliente. Então, se você quiser pode ir para as configurações do navegador que está usando e pode ver a chave de verificação das conhecidas autoridades de certificados, que já estão inseridas em seus navegadores. Também assumo aqui que o servidor neste caso tenha um certificado emitido pelas segundas autoridades de certificação que certifique a sua chave de criptografia ou a chave pública e tal certificado esteja disponível com o servidor. Assim, assim que o protocolo de handshake inicia a execução entre o cliente e o servidor, a primeira mensagem vai do cliente para o servidor, onde basicamente o cliente envia as cifrassuites suportadas, a saber qual a versão da função hash que ele suporta, qual versão de cifras de blocos ela suporta, qual versão do gerador de pseudorandom ele suporta, e assim por diante e junto com isso o cliente envia o valor nonce escolhido aleatoriamente. Em resposta, o servidor escolhe um nonce aleatório, e envia o que o ciphersuites suporta, a saber, sua versão de função hash, sua versão de cifras de blocos, geradores pseudorandom e etc. E junto com isso o servidor envia a chave pública de seu mecanismo de encapsulamento fundamental, e para convencer que realmente essa chave pública pertence ao chamado servidor, o remetente envia o certificado que poderia ter obtido de uma dessas autoridades de certificação. Neste exemplo, é a segunda autoridade de certificação. Então, basicamente a ideia aqui é que tanto o cliente quanto o servidor estão tentando concordar sobre a versão de cifradas que eles vão usar para o resto da comunicação, e junto com isso o servidor está enviando sua chave de criptografia ou a chave pública e prova que realmente a chave pública pertence ao servidor enviando o certificado correspondente. Agora, o que o cliente faz é, ele verifica, ou verifica o certificado. Para verificar o certificado, ele utiliza a chave de verificação da autoridade de certificação que emitiu esse certificado para o servidor, e neste caso o certificado foi emitido pela segunda autoridade de certificação. A chave de verificação da segunda autoridade de certificação será utilizada e se somente o certificado for verificado com sucesso, a comunicação prosseguirá ainda mais, caso contrário o cliente irá abortar a sessão lá itself.Agora, pode ser possível que o certificado seja emitido por uma autoridade de certificação cuja chave de verificação não esteja inserida no navegador do cliente. Nesse caso, essa verificação não terá saída. Como resultado, o navegador lançará uma mensagem de aviso para o usuário ou para o cliente a saber: dizer que, “ Não posso identificar, ou não posso reconhecer a validade do certificado ”. Esta é uma mensagem de erro comum, que muitas vezes encontramos quando tentamos fazer uma comunicação SSL com um servidor, cujo certificado não pode ser reconhecido pelo nosso navegador. Nós obtemos a mensagem de aviso de que você pode prosseguir por seu próprio risco. É por isso que é sempre recomendado atualizar as versões do seu navegador porque toda vez que você vem com a sua nova versão do seu navegador, a chave de verificação de novas autoridades de certificados fica inserida nas novas versões e daí você não obterá este tipo de mensagem de erro. Por este exemplo, presumo que a chave de verificação da autoridade do certificado esteja disponível com o cliente e o certificado seja verificado adequadamente. Uma vez que a verificação do certificado acontece, agora o que o cliente faz é, ele executa o algoritmo de encapsulamento do mecanismo de encapsulamento de chave subjacente usando a chave pública fornecida pelo servidor. Como resultado, ele irá a saída de uma chave secreta, que eu denote como pmk. A encapsulação deste pmk não passa de chave premestre. Assim, este algoritmo de encapsulamento irá a saída de uma chave premestre e sua encapsulação c. O encapsulamento c será enviado para o servidor e o que o cliente vai fazer é, ele vai executar uma função de derivação de chave nas entradas Nc e Ns, a saber, as duas onças, que são escolhidas pelo cliente e pelo servidor, respectivamente, a chave premaster e a saída são consideradas como chave mestra. Além disso, qualquer que seja a comunicação que tenha acontecido entre o cliente e o servidor até agora incluindo este encapsulamento c, deixe-o ser chamado como transcrição. Todo esse cliente transcrição se autentica usando um código de autenticação de mensagens e usando a chave mestra como chave, e a tag correspondente é enviada para o servidor. Então, essa é uma mensagem agora do lado do cliente. O que o servidor faz é, é preciso o encapsulamento c e executa o algoritmo de decapsulação neste encapsulamento c para obter o mesmo pmk de chave premestra. Uma vez que obtém a chave premestra, ele executa a função de derivação de chave nos dois valores nonce e a chave premaster para obter a chave mestra.Então, agora conforme nossa suposição tanto cliente quanto servidor teriam concordado sobre as versões da função de derivação de chave que eles vão usar porque essa é a parte das suites cifradas suportadas. Ele garante que tanto o cliente quanto o servidor estejam usando a mesma versão da função de derivação de chave e a mesma versão do mecanismo de encapsulamento de chave. Agora, o servidor adicionalmente faz a seguinte etapa. Então, ele viu agora a autenticação de toda a transcrição que o cliente enviou para ele, então ele verifica a tag na transcrição que o cliente está enviando para ele e ele aborta se a verificação da tag falhar. Considerando que se a verificação da tag for bem-sucedida, ela faz o seguinte: executa um gerador de pseudorandom na chave mestra e derivam quatro teclas, que são denotadas por kc, kc ’, ks, ks ’. Além disso, seja qual for a transcrição agora o servidor viu até agora, chamamos de transcrição ’ e isso inclui tudo aquilo que o cliente enviou para ele seguido da autenticação da transcrição que o cliente enviou para o servidor. Essa coisa toda eu chamo como transcrição ’ e esta transcrição ’ agora é autenticada pelo servidor usando a mk chave mestra e a tag é enviada para o cliente. O que o cliente vai fazer é, ele realizará uma verificação na transcrição ’ usando a chave mestra. Se a verificação falhar, ela aborta, caso contrário, também executa o mesmo gerador de pseudorandom, que foi executado pelo servidor na mk da chave mestra, e derivar as mesmas quatro chaves, que o servidor gerou. Isso completa o protocolo de handshake. Agora, você pode ver em todo esse protocolo de aperto de mão, usamos o primitivo de chave pública a saber, o mecanismo de encapsulamento de chave, e junto com isso estamos usando a função de derivação de chave e um gerador de pseudorandom. Até o término do protocolo de handshake, as criptografias reais das mensagens, as quais o cliente gostaria de comunicar ao servidor não aconteceu. Até agora, apenas a troca de chave aconteceu e a troca de chave só invoca o mecanismo de encapsulamento chave juntamente com a função de derivação de chave e o gerador de pseudorandom. Agora, supondo que o protocolo de handshake seja executado com sucesso, tanto o servidor quanto o cliente têm agora dois pares de chaves. Sempre que servidor gostaria de comunicar algo para o cliente, ele executa um esquema de criptografia autenticado usando o par de chaves ks e ks ’ e podemos usar qualquer esquema de criptografia autenticado aqui, digamos que aquele obtido usando o criptografado, então, autenticar mecanismo. Em resposta sempre que o cliente gostaria de comunicar algo ao servidor, ele usa o outro par de chaves, a saber, o kc chave e chave kc ‘.Você pode relembrar que na abordagem genérica que tínhamos visto para construir o esquema de criptografia autenticada, ressaltamos que deve haver uma chave independente para instanciar o esquema de criptografia segura do CPA que está lá dentro do esquema de criptografia autenticado e deve haver uma chave independente para instanciar o componente MAC, que está lá no esquema de criptografia autenticado e por isso há um par de chaves, que é usado no esquema de criptografia autenticado. Temos um par dedicado de chaves sempre que o servidor quer se comunicar com o cliente, e temos uma chave dedicada sempre que o cliente quiser comunicar ao servidor. Agora você pode ver que por fazer a comunicação real entre o cliente e o servidor, estamos usando processo de criptografia de chave completamente simétrica. (Consulte Slide Time: 27:45) Então, para resumir, devemos definitivamente agradecer a esses dois geniais pessoas Diffie e Hellman que pensaram em resolver o problema do acordo chave enquanto que o emissor e o receptor que estão conectados por um canal inseguro à comunicação pública e ainda podem acabar concordando sobre uma chave privada aleatória comum conhecida apenas pelo remetente e pelo receptor. É só por causa de sua visão e devido ao trabalho pioneiro, surgiu toda a área de criptografia de chave pública e foi assim que poderíamos pensar em fazer comunicação segura com qualquer pessoa desconhecida com quem nunca nos encontramos, com quem nunca compartilhamos qualquer tipo de informação secreta e podemos convenientemente fazer comunicação segura com aquelas pessoas desconhecidas. Então, definitivamente devemos agradecer a essas duas pessoas por causa do impacto do trabalho que o que eles fizeram, são premiados com o prêmio Turing muito recentemente. Isso é tudo para esta palestra. Então, só para resumir nesta palestra, vimos, discutimos sobre um nível muito alto que temos a Fiat-Shamir heuristic e como podemos aplicá-lo para converter qualquer esquema de identificação de três redondos em um esquema de assinatura. Nós a aplicamos concretamente para esquema de identificação de Schnorr para obter esquema de assinatura de Schnorr e discutimos uma visão geral de alto nível do protocolo SSL e de um protocolo TLS. Então, que mais ou menos termine nossa discussão sobre o problema da comunicação segura. Nós agora sabemos como fazer a comunicação segura entre duas entidades sobre um canal público em que o remetente e o receptor podem não ter nenhuma informação pré-compartilhada. Para as palestras restantes, veremos que como podemos usar primitivas criptográficas para projetar protocolos interativos onde