Loading
Nota de Estudos
Study Reminders
Support
Text Version

Modo De Feedback De Saída e Modo Contador

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 de CryptographyProf. Dr. Ashish Choudhury (Ex-) Infosys Foundation Career Development Cátedra Instituto de Informações Technology-BangaloreLecture-17Modes de Operações do Bloco Cifradores Parte IIOlá todos, bem-vindos à palestra 16. Nesta palestra continuaremos nossa discussão a respeito dos modos de operações de cifras de blocos. (Consulte o Tempo de Slides: 00 :36) especificamente o roteiro para esta palestra é o seguinte, discutiremos como projetar cifras seguras de CPA eficientes usando 2 dos modos de operações, a saber, o modo de feedback de saída e o modo de contador de operação. (Consulte o Tempo de Slide: 00 :50) Assim, vamos começar com o modo de feedback de saída ou modo OFB em curto. Então, a ideia aqui é basicamente remetente e receptor geram um pseudo fluxo aleatório de pad, que na verdade é independente do texto à plaina, que remetente quer criptografar. E uma vez que o pseudo fluxo aleatório de pad é gerado e a mensagem está disponível, o pseudo fluxo aleatório de pad é usado para XORing ou mascarando a mensagem. Por isso, vejamos como o pseudo fluxo aleatório de pad é gerado. Então, o remetente escolhe aleatoriamente um IV, que nós não fazemos como y0.E o tamanho do IV tem que ser o mesmo que o comprimento do bloco de sua função subjacente F. E então imagine que queremos gerar 3 blocos de pseudo fluxo aleatório de pads aqui é como vamos. Por isso, invocamos 3 invocações subjacentes da função F, tudo instanciado com a mesma chave k e alimentamos o IV como entrada de blocos para a primeira chamada, obtemos a saída y1, e então fazemos a chaining. Mas agora esta chaining é diferente do modo CBC de criptografia que tínhamos visto na última palestra. Aqui a chavagem é independente do bloco de mensagens porque a partir de agora, não há nenhum texto concreto que esteja se envolvendo aqui. Então, a saída y1 é alimentada como a entrada de bloco para a segunda chamada da função para obter o segundo bloco de pseudo fluxo aleatório de pad que poderíamos denotar como y2 e então este é alimentado como a entrada de bloco para a terceira chamada. E podemos continuar assim certos. Então, é assim que o pseudo fluxo aleatório de pad é gerado. E agora se a mensagem estiver disponível para criptografia, qualquer que seja o pseudo fluxo aleatório de pad que tenha sido gerado até agora ele pode ser usado para dominar a mensagem dependendo do comprimento da mensagem direito. Então, você pode imaginar que a criptografia aqui é agora um processo de estágio 2 e processo off-line e um processo online em que na fase offline ou em uma fase independente de mensagem um pseudo fluxo aleatório de pad é gerado. E durante a fase online quando a mensagem real estiver disponível, nós fazemos a criptografia usando qualquer tipo de pad que tenha sido gerado na fase offline como a máscara certa. Assim, se o IV também for comunicado ao receptor e o receptor também pode gerar um fluxo aleatório pseudo de pad offline e uma vez que a mensagem é criptografada do lado do remetente e comunicada de volta ao receptor pode ser decriptografada adequadamente.Sendo assim, neste exemplo específico, a criptografia da mensagem consistirá no IV e na criptografia real a saber: c1 c2 c3, certo. E para descriptografar, fazemos a operação correspondente, a saber, recuperar de volta o bloco ith plaintext, o que fazemos é receptor precisa do i-ésimo bloco de pseudo fluxo aleatório de pad e que pode ser computado apenas fazendo esta operação e uma vez que o i-ésimo bloco de pseudo fluxo aleatório de pad esteja disponível pode ser XORed do i-ésimo bloco de texto cifrado para recuperar de volta o plaintexto. Isso significa, é suficiente neste modo de operação, para que a F seja apenas uma função pseudo aleatória, não precisamos da função f para ser uma função invertível. Ou seja, basta a F (k) ser apenas a PRF. E a vantagem desse modo de operação é que que o fluxo pode ser pré-computado e uma vez pré-computados o cálculo do texto cifrado é paralelizável. Isso significa que não podemos gerar o fluxo de pads em paralelo porque a geração de pad acontece sequencialmente.Mas uma vez que a fase offline acabou e o pad estiver disponível, qualquer que seja o bloco de mensagens que quisermos criptografar a criptografia pode acontecer em paralelo certo, além disso, a outra vantagem aqui é que um plaintexto pode não ser um múltiplo do comprimento do bloco de sua função subjacente F, isso significa aqui não exigimos nenhum preenchimento sofisticado para fazer o comprimento da mensagem para beto ser um múltiplo do comprimento do bloco de sua função subjacente antes de criptografar a mensagem, certo. Portanto, isso é diferente do seu modo CBC de criptografia. E pode ser provado formalmente que se a sua função chaveada subjacente F (k) for uma PRF segura, então este modo de operação a saber, o modo OFB é o CPA seguro, também podemos provar que uma variante stateful também é CPA segura que significa, imagine um cenário em que emissor e receptor são sincronizados e eles geraram um fluxo aleatório pseudo de pad y1 y2 y3 e que é usado para criptografar uma mensagem m certo. E agora, há uma nova mensagem m ’ para encriptação que está disponível para o remetente. Assim, se o remetente agora quer criptografar uma mensagem m ’ usando o modo OFB, não há necessidade de escolher um fresco IV o y3 que foi usado qual foi o último bloco do pseudo pad aleatório para a mensagem anterior pode ser usado como o IV para a mensagem m ’ e usando y3 podemos chutar start todo o processo. E gerar um fluxo aleatório de pseudo aleatório de pad que pode ser então usado para mascarar a nova mensagem m ’ e pode ser provado que uma variante stateful deste modo OFB também é CPA secureright. Então, mais ou menos nós realmente obtemos todas as vantagens que queremos ou esperamos do melhor modo de operação possível. Nomeadamente, agora temos a segurança CPA, temos o pressuposto mínimo exigido da função subjacente, nomeadamente a assunção de PRF. E se assumirmos que o pad foi gerado na fase offline e o cálculo de texto cifrado é paralelizável e assim por diante. Mas acontece que podemos fazer melhor, certo. (Consulte o Tempo do slide: 06 :26) E melhor modo de operação é o modo de contador de operação do modo CTR. E a ideia aqui é mais ou menos a mesma. Ou seja, dividimos o processo de criptografia em 2 fases. A primeira fase é a fase independente da mensagem, onde um pseudo fluxo aleatório de pad é gerado, e que mais tarde é usado para fazer o real mascaramento da mensagem. Mas agora, a forma como o pseudo fluxo aleatório de pad será gerado, tudo pode ser paralelizado. Isso significa que a geração de pad assim como a criptografia real pode ser feita de forma paralelizada. Então aqui é como o modo de contador de operação é executado. Assim como no modo OFB, começamos com um aleatório IV, que chamamos de contador, e o contador é selecionado aleatoriamente a partir do domínio do comprimento do bloco de sua função subjacente. Por isso, é uma cadeia de bits uniformemente aleatória de comprimento L e que também será uma parte do texto cifrado. E então geramos o pseudo fluxo aleatório de pad, mas, ao contrário do modo OFB, não fazemos nenhuma chacina aqui, a forma como geramos o pseudo fluxo aleatório de pad é a seguinte. Sendo assim, a primeira chamada de sua função F será com o contador de entrada mais um, a segunda chamada da função será com o contador de entrada mais 2 e assim por diante. Isso significa que todas as chamadas subsequentes da função estarão com uma entrada que é uma a mais do que o valor anterior do contador usado no anterior ou na chamada anterior da função. E uma vez que as funções Fs são avaliadas nessa entrada, obtemos o pseudo fluxo aleatório de blocos de pads que podem ser levados a usados para realmente mascarar sua mensagem para a direita de criptografia. Então essa é a única diferença aqui, a forma como estamos gerando o pseudo aleatório fluxo aleatório de pad, permanecendo todas as operações permanecem iguais como no modo OFB aqui. Portanto, aqui novamente, a criptografia real da mensagem consistirá do seu valor do contador, que será o bloco c0, e realmente os blocos de criptografia serão os blocos criptografados serão c1 c2 c3 ok. (Consulte o Tempo do slide: 08 :26) Assim, como no modo OFB, podemos realmente provar formalmente que basta para a função chaveada subjacente apenas ser uma PRF over para ter o modo de contador de operação para ser seguro CPA. Pois para o processo de decriptografia não exigimos que qualquer inversão seja computada. Por isso, é por isso que o suficiente para que a função chaveada subjacente seja apenas uma PRF. Mais importante ainda, a criptografia assim como a decriptografia podem acontecer em paralelo. Isso porque quando se vê de perto a maneira como estamos gerando o pseudo fluxo aleatório de pad. Se eu quiser gerar y2 eu não preciso depender de y1 que foi o caso no modo OFB, no modo OFB e até e a não ser que você gere, y1 não pode computar y2 e, portanto, até e a menos que y2 seja computado, não é possível gerar y3 e assim por diante. Por isso, é por isso que o pseudo fluxo aleatório de geração de pad que não era paralelizável. Mas a maneira como estamos gerando o pseudo fluxo aleatório de pad e o modo de contador de operação, o y2 pode ser gerado independentemente de y1 e assim por diante. Nesse sentido, tanto a criptografia quanto a operação de decriptografia podem ser paralelizadas à direita. Mais importante no modo contador de operação, se eu quiser apenas descriptografar um bloco de texto cifrado específico, e não estou interessado em decriptografar os outros blocos que é possível, e que para apenas invocando uma invocação da função chaveada subjacente, por exemplo, se eu apenas quiser descriptografar c2, para decriptografar c2 o que eu preciso é y2.E o y2 só me exige a invocação da função subjacente no contador de valor mais 2. Então, se eu tiver o valor do contador inicial, que está lá em c0, e se eu quiser decriptografar c2 o que eu tenho que fazer é preciso criar c0 como valor do contador, computar contador mais 2 chamar minha keyedfunction sublinhado no contador de entrada mais 2 gere o pseudo aleatório pad y2 e XOR ele a partir de c2which vai me devolver m2.So, dependendo do meu requisito, eu posso descriptografar qualquer bloco de cifraria específico invocando apenas uma invocação da função de chave subjacente, o que não foi possível no modo OFB. E mais importante, podemos provar formalmente que a variante estadual do modo contador de operação também é a CPA segura. Isso significa, se eu tiver uma mensagem m, e para isso meu texto cifrado resultante é c0, c1 c2 c3, onde y3 foi o último fluxo de pseudo random pad. E agora eu tenho uma nova mensagem m ’, certo, então, não preciso escolher um novo valor de contador para gerar um fluxo aleatório de pad para a mensagem m ’, eu posso usar y3 como o valor do contador para gerar a próxima sequência de pseudo pad aleatório para a mensagem m ’, e o mesmo pode ser feito no final do receptor, e pode ser provado anteriormente que a variante stateful também é CPA segura. Por isso, temos agora quase exatamente todos os recursos que exigimos dela, bom modo de operação da cifra do bloco. E é por isso que esse modo de contra-operação é muito popular, que é usado em várias instanciações dos protocolos do mundo real ok. (Consulte o Tempo do slide: 11 :25) Então agora queremos fazer rigorosa análise de segurança da segurança CPA para esse modo de contador de operação direito. Então, eu vou usar este exemplo. Então imagine um cenário em que um remetente tenha criptografado dizer uma mensagem formada por 3 blocos certo e é assim que o modo de contador de operação teria operado. E queremos provar que esse modo de contramão de operação é o CPA seguro. Portanto, antes de entrar na prova real de segurança do modo de contra-operação. Vamos considerar uma variante desse modo de operação de operação em que tudo permanece como está no modo de operação do contador real, exceto que todas as invocações da PRF chave são substituídas por invocações de uma função verdadeiramente aleatória que é uma função deskeada. Então, imagine que tanto o emissor quanto o receptor tenham concordado sobre uma função verdadeiramente aleatória que é uma função não chaveada, mapeando as cordas de bit L a L bit strings.Então, a variante do modo de contador de operação que eu denote como Π??? é quase o mesmo que o modo contador real de operação, exceto que todas as invocações da função chaveada Fk são substituídas pelas invocações verdadeiramente da função verdadeiramente aleatória f. Agora, o que vamos provar a seguir é que, se considerarmos essa variante do modo contador de operação baseado em função verdadeiramente aleatória. E se considerarmos qualquer adversário de tempo de polia arbitrária participando de uma instância de jogo de indistinção de CPA e faz total de q (n) número de consultas oracle de criptografia então a probabilidade com a qual aquele adversário pode ganhar o jogo CPA é superior delimitado por ½ + (2 q (n) 2/ 2L), certo. Portanto, se L é realmente se supomos que L é alguma função polinomial do parâmetro de segurança, e anyhow q (n) é uma função polinomial do parâmetro de segurança. Então, no geral, acabamos mostrando que a probabilidade de qualquer adversário de tempo polo vencer o jogo CPA contra este modo de operação de contador baseado verdadeiramente aleatório de funcionamento é metade mais insignificante, o que satisfaz a definição de segurança CPA. Por isso, vamos primeiro fazer isso. Uma vez que fizermos isso, mais adiante mostraremos realmente aquele modo de contador real de operação que queremos provar formalmente para ser seguro CPA, não é seguro CPA, Então significa que existe um distinguidor que pode distinguir o comportamento da função aleatória chaveada do comportamento de uma função verdadeiramente aleatória e que será uma contradição com a suposição de que a função chaveada é uma função pseudo aleatória. Sendo assim, essa é a ideia geral da prova, consideraremos em primeiro lugar uma variante do modo de operação do contador provê-lo como a CPA segura formalmente.E então vamos voltar e argumentar que já que a única diferença entre o modo de contador real de operação e uma variante do modo contador de operação são as invocações subjacentes da função. Assim, o modo de operação do contador real também deve ser o CPA seguro. Caso contrário, há um distinguidor que pode distinguir fora a função chaveada a partir do resultado de um direito de função verdadeiramente aleatório. (Consulte o Tempo do slide: 14 :37) Então, vamos primeiro proceder para provar a segurança CPA do modo de operação de contador baseado em função verdadeiramente aleatória. Então, considere um adversário arbitrário computacionalmente delimitado que participa de uma instância de um jogo CPA que consistirá de 4 fases, teremos fase de treinamento pre?desafio e teremos uma fase de desafio, certo. E para responder às consultas da fase de treinamento do pré-desafio basicamente, o desafiante selecionará uma função verdadeiramente aleatória que não seria conhecida por esse direito adversário. E todas essas consultas serão criptografadas executando o algoritmo de criptografia do processo de criptografia baseado em função verdadeiramente aleatória. E então uma vez que o par de autores do desafio é submetido pelo adversário, o desafiante escolherá uma dessas mensagens aleatoriamente para a criptografia. E vai criptografá-lo escolhando um valor de contador aleatório, que eu denote como CTR* e então c * será basicamente o valor do CTR* na função verdadeiramente aleatória XORed com a mensagem mb. E então haverá uma fase de treinamento de post desafio, novamente, em que o adversário apresentará consultas oracle de criptografia e quais serão criptografadas conforme esse processo de criptografia modificado. E, finalmente, o adversário irá fazer a saída se este desafio cifrado é uma criptografia de mensagem m0 ou mensagem m1, certo. Por isso, vamos supor que o número total de consultas que o adversário está pedindo em toda esta instância deste experimento é q (n).O q (n) é alguma função polinomial do parâmetro de segurança l. Além disso, também assumimos que cada consulta também consiste em na maioria q (n) número de blocos. Então, na verdade vamos assumir o pior cenário de caso em que há total de q (n) número de consultas e cada consulta é exatamente constituída de q (n) número de blocos direito. Assim, denoquei a i-ésima consulta para a qual o adversário pediu o serviço de oracle de criptografia para ser Mi.E já que Mi consiste em q (n) número de blocos adversos para responder o serviço de oracle de encriptação para responder para criptografar esta mensagem Mi, o desafiante precisa levar q (n) número de valores de contador. Então, eu denoquei aqueles valores de contador como contador i + 1, contador i + q (n) e assim por diante. Assim, a primeira observação é que se adversário submete a mensagem Mi para criptografia e c é a criptografia dessa mensagem conforme esta variante do modo de operação do contador, então ao ver o texto cifrado adversário será aprenderá o valor da função verdadeiramente aleatória desconhecida sobre esses valores de contador, a saber, contador i + 1, contador i + 2 e assim por diante. (Consulte o Tempo do slide: 17 :20) Por que, portanto, consideremos a i-ésima consulta Mi que basicamente consiste em q (n) número de blocos, rightand para criptografar essa mensagem, o desafiante escolherá um valor de contador aleatório, o qual eu denote como direito CTRi. E uma vez que o valor do contador é selecionado, uma vez que há q (n) número de blocos na minha mensagem mi basicamente o desafiante precisa avaliar a função verdadeiramente aleatória sobre CTRi + 1, CTRi + 2 e CTRi + q (n), que irá gerar a sequência de blocos de pad que serão XORed com os blocos de mensagens reais que estão presentes na mensagem mi para gerar os blocos cifras.E todo o texto cifrado será comunicado de volta ao adversário como resposta da consulta oracle de criptografia, uma vez que o adversário saberá o valor do contador i e contador i + 1 e assim por diante. O adversário simplesmente pode simplesmente realizar esta operação a saber, pode XORed o bloco jthciphertext e o bloco de mensagens jth presentes na mensagem mi e que lhe dará o valor da função verdadeiramente aleatória desconhecida neste valor do contador a saber o contador i + 2 direito. (Consulte o Slide Time: 18 :32) Assim, já que estou assumindo que meu adversário vai fazer q (n) número de consultas essas consultas eu estou representando como mensagem m1 m2 e mq (n) e estou assumindo que cada uma dessas mensagens consiste ainda mais em q (n) número de blocos. E presumo que o nosso desafiante nesta instância do experimento utiliza esses valores de contador para criptografar esses blocos de mensagens a saber, a primeira mensagem é criptografada usando os valores do contador CTR1 + 1, CTR1 + 2, CTR1 + q (n) so on.Assim, estes são os valores contrários que são utilizados pelo desafiante. E como já vi que com base na criptografia de sua mensagem o adversário aprende a saída correspondente da função verdadeiramente aleatória sobre os valores contrários correspondentes. Assim, isso significa que adversário basicamente tem acesso ao valor da função verdadeiramente aleatória desconhecida f e todos os valores de contador que foram usados pelo desafiante para responder às consultas oracle de criptografia. Agora nosso objetivo é analisar qual é a probabilidade de sucesso deste adversário em identificar se este texto cifrado de cifração é uma criptografia da mensagem m0 ou se é uma criptografia de m1 e podemos dividir essa probabilidade geral na somatória de 2 probabilidades. Por isso, considere o primeiro caso quando os valores contrários que são usados para preparar o desafio ciphertexto c * são diferentes de todo o valor do contador que foram utilizados para responder às consultas oracle de criptografia levantadas pelo adversário.Esse é o primeiro caso. E o segundo evento é quando os valores de contador que são usados para preparar o desafio ciphertexto se sobrepõe ou se repetem em pelo menos uma das instâncias das consultas oracle de criptografia a saber os valores de contador que são usados para preparar o desafio cifrado sobrepõe-se aos valores contrários que foram utilizados para responder às consultas oracle do adversário ’ sencryption. Então estes são os 2 casos separados. (Consulte o Tempo do slide: 20 :33) E deixe-nos pegar o primeiro caso e tentar analisar qual é a probabilidade de que, nesse caso, adversário seja capaz de vencer o jogo da CPA certo. Portanto, estamos no caso quando os valores do contador a saber: CTR* + 1, CTR* + 2 e assim por diante, que são realmente utilizados para criptografar o desafio plaintexto mb são diferentes de todos os valores de contador que foi usado para responder ao adversário ’ s consultas oracle de criptografia direito, portanto, este é o desafio plaintext mb criptografado por avaliar primeiro a função verdadeiramente aleatória sobre esses valores de contador que não foram utilizados até agora em qualquer uma das consultas oracle de criptografia para gerar os pads. É isso que o nosso próximo objetivo é. Assim, isso vai seguir mais ou menos usando o mesmo argumento que nós tínhamos usado para provar a segurança CPA do nosso primeiro candidato, esquema seguro CPA baseado na função pseudo aleatória, certo. Por isso, lembre-se de que, nessa prova, nós tínhamos primeiramente considerado uma construção baseada em função verdadeiramente aleatória, comprovada sua segurança CPA.E aí nós demos um argumento baseado em redução onde mostramos que a diferença na vantagem vencedora do adversário entre as 2 instâncias do jogo CPA é superior delimitado por uma probabilidade insignificante se a minha função subjacente for uma função pseudo aleatória. Assim, podemos usar o mesmo ou similar argumento e acabar mostrando que a diferença do adversário vencendo o jogo CPA contra o modo de operação do contador real. E o adversário vencer o jogo CPA contra um modo de operação de contador baseado em função verdadeiramente aleatória pode ser superior delimitado por uma grandeza insignificante. E como sabemos que adversário vencer o jogo CPA contra o modo de operação contra o modo de operação é 1/2 + (2 q (n) 2 / 2L) ao reshufflar o termo acabamos ficando que o modo de contador de operação usando a função pseudo aleatória também é direito de segurança CPA. (Consulte o Tempo do slide: 34 :05) Então é isso que acabamos mostrando, e que conclui que o modo de contador de operação é realmente CPA seguro. Então, isso me leva até o final desta palestra. Resumindo, nesta palestra, tínhamos visto 2 dos modos de operação, a saber, o modo OFB e o modo de contador de operação. E também tínhamos visto a prova de segurança do modo contador de operação, o modo contador de operação tem vários features.Namely, a criptografia e a decriptografia podem acontecer em paralelo. E não exigimos nenhuma suposição sofisticada da função chaveada subjacente, basta ou bastar para a função chaveada subjacente ser apenas uma função pseudo aleatória. E a variante estadual também é CPA segura. E esses recursos atrativos fazem com que o modo de contração da operação seja usado com rigor no protocolo real do mundo. Obrigado.