Fundamentos of Cryptography Prof. Dr. Ashish Choudhury (Ex-) Infosys Foundation Career Development Chair International Institute of Information Technology – Bangalore Lecture – 31 Random Oracle Model – Part I (Consulte O Slide Time: 00:30) Olá a todos, bem-vindos a esta palestra. Apenas uma breve recapitinha. Na última palestra discutimos alguns dos ataques genéricos que podem ser lançados sobre as funções de hash, nomeadamente ataques de aniversário, e discutimos também algumas das aplicações de funções de hash como cadeias de Bloco, árvores de Merkel e etc. Nesta palestra, continuaremos nossa discussão sobre a função de hash criptográfico. Basicamente, introduziremos um modelo de prova muito interessante o que chamamos de modelo Random-Oracle. (Consulte O Slide Time: 00 :58) Então, vamos começar com a nossa discussão sobre o modelo Random-Oracle que também é chamado de ROM. Por isso, existem vários cenários onde projetamos primitivas criptográficas onde as funções de hash resistentes à colisão são usadas e essas construções são altamente práticas na natureza e são altamente eficientes. Alguns dos exemplos de tais primitivas são função de derivação de chave, esquema de comprometimento, primitivas de primitivas e assim por diante, mas infelizmente acontece que não podemos provar a segurança dessas primitivas criptográficas com base nas propriedades padrão da função hash. O que eu quero dizer com propriedades padrão da função hash é a propriedade de resistência de colisão, certo. Então o que exatamente o modelo Random-Oracle faz é ele te dá um modelo no qual você pode provar a segurança das primitivas criptográficas projetadas com base em funções hash onde você não pode dar as provas de segurança apenas com base na propriedade de resistência de colisão da função hash subjacente e o que fazemos neste modelo Random-Oracle somos nós fazemos uma suposição muito forte sobre a função hash subjacente. A saber, fazemos uma suposição idealizada e suposição exata que fazemos sobre a função hash subjacente será discutida em breve e o que este modelo Random-Oracle faz é ele age como um meio termo para você onde você não tem nenhuma prova de segurança em uma das mãos e enquanto que a outra mão você tem uma prova de segurança rigorosa apenas com base nas premissas padrão de criptografia. Assim, uma vez que você não pode dar a comprovação de segurança das construções com base nas propriedades padrão da função hash criptográfica. Então, supondo que estamos no modelo Random-Oracle serve tipo de um meio-termo onde ao fazer suposições idealizadas sobre sua função hash subjacente, você pode concluir a prova de segurança. (Consulte O Tempo De Deslizamento: 02:47) Então, vamos entrar nos detalhes subjacentes do chamado modelo Random-Oracle. Assim, o que fazemos neste modelo Random-Oracle é supor que estamos projetando um primitivo criptográfico baseado em uma função hash mapeando cadeias de bits de comprimento arbitrário para saídas de tamanho fixo de l bit strings. Assim, o que fazemos é supor que as funções hash subjacentes se comportam como uma função aleatória mapeando entrada de comprimento arbitrário para saídas de comprimento fixo e imagine que estamos projetando um primitivo criptográfico onde estamos usando esta função hash subjacente modelada como uma função verdadeiramente aleatória. Supomos que cada participante do sistema tenha acesso oráculo à função hash. Isso significa que nenhum participante do sistema incluindo o usuário genuíno, assim como o adversário, não estará conhecendo os detalhes internos e o código e a lógica da função hash subjacente. Então, essa é uma suposição muito forte que estamos fazendo sobre a função hash subjacente neste modelo porque na realidade quando estamos projetando um primitivo criptográfico, vamos instanciar essa função hash por alguma função de hash prático. Quando estamos usando uma alguma função hash prática toda entidade no sistema estará conhecendo o código exato ou a lógica da função hash, mas quando estamos dando a prova no modelo Random-Oracle, assumimos que nenhuma entidade no sistema sabe sobre os detalhes exatos da função hash subjacente. Também as chamadas entre o oráculo e os participantes são privadas. Isso significa, imagine se eu tiver um primitivo de criptografia envolvendo dizer usuário 1, usuário 2, e usuário 3 e cada um deles precisar usar essa função hash no digamos que o usuário 1 deseja avaliar a função hash subjacente em alguma entrada x. Então assumimos que no modelo Random-Oracle a interação entre o usuário 1 e a interface ou o oracle H é através de um canal privado entre o usuário 1 e o oracle H. Então o usuário 2 e o usuário 3 não estariam sabendo as entradas exatas nas quais o usuário 1 vai avaliar a função hash subjacente ou o oracle. Supõe-se também que o oráculo H seja mantido como uma tabela formada por vários x, valor y e a forma como esta tabela é mantida é a seguinte. Se alguma entidade consulta este oráculo em uma entrada x, então o que a tabela faz é ou o oracle o faz é basicamente verifica na tabela existente que é uma lista de vários (xi, yi) valoriza se existe uma entrada de xi com o valor sendo x. Isso significa basicamente, a tabela verifica se o valor do oráculo na entrada x já está lá na tabela ou não. Se for lá já, então a yi correspondente é devolvida como a saída do oráculo na entrada x, enquanto que se não houver entrada de xi existente com correspondência o valor x, então o que o oracle faz? Ele cria uma nova entrada na tabela em que armazena o valor do x e contra esse x ele armazena um valor y uniformemente aleatório onde o valor y é uma cadeia de bits l uniformemente aleatória e que serve como referência ou a saída de função ou o valor oracle ou a saída oracle para a entrada x para as chamadas subsequentes ao oracle. Assim, mantendo esse oráculo como uma tabela (x, y) como esta, é assegurado que realmente o oráculo satisfaça as propriedades que são exigidas a partir de uma função verdadeiramente aleatória, certo. (Consulte O Tempo De Deslizamento: 06 :06) Então, há algumas propriedades importantes no modelo Random-Oracle e isso será crucial quando estaremos dando provas no modelo Random-Oracle. Portanto, a primeira propriedade é que se alguma entrada x não tiver sido consultada para o oracle H, então o valor do oráculo sobre esta entrada x será um valor de bits uniformemente aleatório e isto se mantém mesmo que a entrada x seja conhecida por uma entidade ou alguma parte do x seja conhecida da entidade ou mesmo se x não for uniformemente valor aleatório. Isso significa mesmo que x seja alguma entrada onde todos os bits da entrada, exceto o último bit é conhecido e se o oráculo não foi consultado sobre essa entrada x, então a saída do oracle nessa entrada x vai ser um valor de bits uniformemente aleatório, e eu ressalto que isso é diferente da propriedade pseudo aleatoriedade do gerador de pseudorandom. Diga se temos um gerador de pseudorandom G, então pseudo propriedade aleatoriedade ali requer que a saída do gerador de pseudorandom G em alguma entrada x deve ser quase igual a um valor uniformemente aleatório apenas se a entrada x para o gerador pseudorandom for um valor aleatório uniformemente e desconhecido, enquanto que no contexto do modelo Random-Oracle, há pseudo propriedade aleatoriedade que estamos exigindo é diferente. Aqui, aqui nós exigimos que se o oráculo não for consultado para a entrada x e mesmo que o x não seja um valor uniformemente aleatório e seja conhecido por você, o valor de saída H (x) vai ser um valor aleatório uniformemente do co-domínio. Sendo assim, essa é uma das propriedades importantes. (Consulte O Tempo De Deslizamento: 07 :41) A segunda propriedade importante no modelo Random-Oracle é propriedade de extractabilidade que vai ser uma propriedade muito crucial mais tarde quando veremos as provas das primitivas criptográficas no modelo Random-Oracle. Então, assuma que temos uma construção de criptografia de algum primitivo, digamos que esse C primitivo envolvendo certo número de entidades, poderia ser uma comunicação segura, protocolo, ou poderia ser apenas qualquer tipo de protocolos de criptografia. Por exemplo, imagine que essa criptografia primitiva C envolve 3 entidades e esta primitiva também requer chamadas para uma função hash subjacente e suponhamos que estamos dando uma prova de redução baseada em que realmente este primitivo criptográfico satisfaz alguma propriedade, alguma propriedade de segurança como por alguma definição, e dizer que estamos dando uma prova baseada em redução e basicamente quando estamos dando uma prova baseada em redução para provar que realmente os chamados primitivos de criptografia satisfazem certas propriedades de segurança como por alguma definição dada no modelo Random Oracle então quando estamos dando a redução sonda baseada o que basicamente nós vamos fazer é vamos supor que digamos que temos um adversário A atacando o seu primitivo C criptográfico, então usando aquele adversário nosso objetivo será projetar outro adversário dizer Um ’ atacar outro primitivo, certo. É o que tipicamente fazemos na prova de redução baseada em redução. Agora como parte de sua estratégia de ataque, este adversário A pode precisar chamar a função hash subjacente, certo, porque isso poderia ser uma parte de sua estratégia de ataque subjacente. Mas já que agora estamos no modelo Random-Oracle, este adversário precisa fazer chamadas oracle para a função H. Então, quando este adversário A ’ que estamos projetando como parte da redução, está invocando este adversário existente A como subroutine, ele virá a saber que adversário A ou o adversário existente A precisa invocar o oracle H em vários x entradas de sua escolha. Assim, esses insumos, a saída do oráculo sobre aqueles insumos que o adversário A quer consultar, serão agora aprendidas pelo adversário A ’ como parte da redução. Então, é isso que queremos dizer com a propriedade de extractabilidade. Isso significa que o adversário A ’ agora pode ver as x consultas que o adversário existente A gostaria de fazer para o Oracle H. Isso não contradiz o imóvel que como mencionado anteriormente onde eu disse que as chamadas entre toda entidade e oráculo são mantidas ou está acontecendo através de um canal privado. Na prova de redução, o adversário A ’ está basicamente invocando o adversário A em sua mente. Isso significa que quando se está invocando o adversário existente A como subroutine, automaticamente virá a saber que como parte de sua estratégia de ataque, quais são as consultas x ou os valores x para os quais o adversário existente A gostaria de fazer as chamadas H oracle, certo. Sendo assim, isso não está violando a propriedade existente do modelo Random-Oracle, mas o ponto importante aqui é que, em como parte da redução, o novo adversário que estamos tentando construir a saber de A ’, ele pode extrair as entradas x para as quais o adversário existente gostaria de fazer as chamadas oracle. Sendo assim, essa é uma das propriedades importantes do modelo Random-Oracle e da segunda propriedade. (Consulte O Tempo De Deslizamento: 11:02) A terceira propriedade do modelo Random-Oracle que novamente será muito crucial quando vamos fazer provas das primitivas criptográficas no modelo ROM é a propriedade de programabilidade, e o que exatamente eu quero dizer com a propriedade de programabilidade como mencionei que se estamos dando uma redução baseada provou, então o novo adversário A ’ que estamos projetando quando ele invoca o adversário existente A, ele aprenderá as consultas H a saber, as entradas x para as quais o adversário existente gostaria de fazer as chamadas para o oráculo, certo. Mas como estamos agora a fazer uma redução aqui direita, não há uma função H que esteja realmente disponível tanto para o adversário A ou para o adversário A ’ porque agora não estamos invocando uma instância do C primitivo, certo. Quando estamos realmente instanciando uma invocação do C primitivo, as partes estarão tendo acesso a um oráculo H, mas agora o que estamos fazendo aqui é estamos dando uma prova de redução baseada, portanto não há instanciação do primitivo C. Então, não há oráculo disponível nem para o adversário A ’ ou o adversário A, mas já que como parte da redução nossa estratégia adversarial A é fazer chamadas oracle para o oracle H em vários entradas x basicamente o nosso adversário A ’ tem que simular a interação do adversário existente com H. Basicamente, o adversário A ’ tem que configurar a saída do oracle H a estes entradas x que o adversário A está exigindo. Então, o que o adversário A ’ pode fazer como parte da redução que ele mesmo pode configurar ou ela própria pode fingir como se a própria sua própria tenha o acesso ao oráculo e o que ele pode fazer é apenas selecionar aleatoriamente alguns valores y do co-domínio do oracle subjacente H e devolver-o de volta como a saída da consulta oracle que o adversário A pediu. Portanto, é isso que queremos dizer com a propriedade de programabilidade. Chamamos de propriedade de programabilidade porque na redução, o novo adversário A ’ pode programar, pode configurar a saída do oráculo nos insumos x para os quais o adversário A pediu a resposta do oráculo. Sendo assim, esta é outra propriedade importante do modelo Random Oracle que utilizaremos quando obteremos as provas de redução baseadas em primitivas criptográficas no modelo Random-Oracle. (Consulte O Tempo De Deslizamento: 13 :21) Então agora vamos comparar uma prova de prova dada ou de segurança para algum primitivo de criptografia dado no modelo Random-Oracle versus a prova de segurança dada no modelo padrão. Por isso, novamente imagine que temos algumas primitivas criptográficas dizem C e isso envolve dizer várias entidades e onde exigimos que cada entidade use alguma função hash subjacente. Por isso, no modelo padrão quando dizemos que temos uma prova de segurança no modelo padrão, não abstramos a função hash subjacente como um Random-Oracle. Em vez disso, assumimos que ela é uma função hash padrão e toda entidade tem livre acesso à função hash subjacente. Isso significa, ele conhece o código completo, a descrição completa da função hash subjacente. Não fazemos a suposição de que as entidades interajam com a função hash por oracle, enquanto que no modelo Random-Oracle quando estamos assumindo que se está projetando dizer outro primitivo C ’ envolvendo a função hash. Se dissermos que estamos dando uma prova no modelo Random-Oracle, então o que exatamente nós queremos dizer com isso é que sempre que estamos instanciando o primitivo C ’ no início uma nova função aleatória H será instanciada e nenhuma da entidade saberá o que exatamente é essa função hash específica, certo. Então, essa é uma grande diferença para uma prova de segurança dada no modelo Random Oracle. Isso significa que toda vez que instanciamos o primitivo C ’, não seria o caso de que o mesmo Random-Oracle ou a mesma instanciação do oracle H estarão disponíveis como estava lá na invocação anterior. Em cada invocação subsequente em cada nova chamada ou uma chamada independente de C ’, um oracle H independente será fixado no início e cada instância terá acesso a esse oráculo via canais privados onde nenhuma entidade saberá o que exatamente é a descrição do oráculo subjacente ou instanciado. A definição de segurança nas provas de 2 que nós demos aqui vai diferir da seguinte forma. Assim, daremos certa definição de alguma segurança, portanto, basicamente a definição de segurança no modelo padrão será que para todos os tempos de adversário de tempo polinomial ou tentando atacar o C primitivo, a definição será que a probabilidade de um determinado evento deve ser insignificante que será definição de segurança para o primitivo C, certo, no modelo padrão e mais ou menos o mesmo se mantém até mesmo para uma definição de segurança dada no modelo Random-Oracle. A saber, a definição de segurança será a de que para todos os adversários de poli-tempo tentando atacar o primitivo C ’ no modelo Random-Oracle, a probabilidade de certos eventos deve ser insignificante. O que exatamente esse evento é que depende da primitiva C primitiva e subjacente primitiva C ’ que estamos tentando construir. Por exemplo se o C primitivo é um processo de criptografia seguro, então basicamente aquele evento é o evento de diferenciação. Considerando que se o C primitivo é um primitivo de criptografia muito complicado, então aquele evento que define se o adversário é capaz de vencer o jogo ou não pode ser um evento complicado, mas independentemente disso, a intuição subjacente é que na definição padrão de segurança do modelo significa que a probabilidade de adversário atacar ou quebrar certo ou a probabilidade de que um adversário garanta que determinado acontecimento particular ocorra com alguma probabilidade é insignificante enquanto que no modelo ROM, a definição de segurança mais ou menos permanece a mesma. A diferença é que no modelo padrão, a probabilidade é assumida sobre a escolha aleatória das partes e não sobre a função hash subjacente porque a função hash subjacente vai ser uma função hash fixa porque toda vez que vamos instanciar o C primitivo no modelo padrão, a mesma função hash será usada novamente e novamente, mas quando estamos considerando a probabilidade de que determinado evento seja insignificante no modelo Random Oracle então a probabilidade é tomada não só sobre as consultas aleatórias sobre as partes mas também sobre a escolha aleatória do oracle H que é instanciado no início da instanciação do primitivo C ’. Então, essa é outra diferença importante na prova de segurança no modelo Random-Oracle versus uma prova de segurança no modelo padrão. (Consulte O Tempo De Deslizamento: 17 :29) Então o que isso significa é que no modelo Random-Oracle, a segurança é garantida não para cada instanciação do Oracle possível. Significa que a segurança pode não estar garantida para uma determinada instanciação de H, mas pode ser garantida para outra instanciação de H, enquanto que na definição padrão quando estamos dando a prova apenas com base na propriedade de resistência de colisão da função hash subjacente, a prova de segurança se mantém para qualquer instanciação de H que seja garantida como resistente à colisão, mas que não precisa ser o caso no modelo Random Oracle. Isso significa que pode ser difícil argumentar que qualquer instanciação concreta do oráculo H por uma hash específica de um mundo real que sejam determinísticos na natureza vai render um esquema seguro, certo, e o ponto importante é que mesmo se damos uma prova de segurança no modelo Random Oracle quando realmente implantamos esse esquema no mundo real, o oráculo H tem que ser instanciado por uma função hash determinista concreta e assim que instanciamos o oracle H por uma função hash determinista concreta toda entidade no sistema, o emissor, o receptor, o partido honesto e adversário também irá ter acesso ao código da instanciação subjacente do H. Que significa adversário não pode ser restrito a apenas o acesso oracle a H, certo. Sendo assim, essas são as propriedades importantes do modelo Random-Oracle. (Consulte O Slide Time: 18 :48) Agora, vejamos rapidamente um exemplo para entender como exatamente as coisas funcionam no modelo Random Oracle. Então imagine que temos uma função hash que leva insumos de tamanho lin bits e te dá saída de bits lout size e usando esta função hash suponha que eu projete uma função G que leva uma entrada de tamanho lin bits e te dá uma saída de bits lout size e basicamente o que esta função G faz é apenas avaliar a função hash na entrada x. Agora, eu afirme que se estamos no modelo Random-Oracle e se interpretamos esta função hash subjacente como Random-Oracle que é instanciada no início de cada instanciação da função G, então esta função G pode ser visualizada como um gerador de pseudorandom e para provar que realmente a função G que construímos aqui é um gerador pseudorandom no modelo Random-Oracle, temos que modificar o jogo indistinguível, o jogo padrão indistinguível que usamos para definir a segurança do gerador pseudorandom para incorporar o modelo Random-Oracle. A mudança que vai acontecer aqui é que se você relembrar no jogo padrão de indistinção para PRG, o desafio para o adversário é distinguir uma amostra de pseudorandom de uma amostra verdadeiramente aleatória, mas agora já que vamos dar uma prova no modelo Random-Oracle, também precisamos modelar o acesso oracle à função hash subjacente do Random-Oracle que o distinguidor pode ter acesso. Por isso, vejamos o jogo de indistinção modificada para o PRG no modelo Random-Oracle. Imagine que há um adversário A sentado entre o remetente e o receptor, e já que estamos agora no modelo Random-Oracle, o que o adversário vai fazer é, adversário estará agora fazendo número polinomial de consultas oracle a este H e adversário não seria saber o que exatamente é o oracle H. So, até e a não ser que adversário não consulta este oráculo H no valor exato, que é pré-partilhado entre o emissor e o receptor, o valor de, que remetente e receptor são outcolocando aqui será uniformemente aleatório do ponto de vista do adversário. Ora, qual é a probabilidade de que adversário de fato tenha se consultado para H de, dado que fez número de consultas ao oráculo? Bem, se a minha distribuição de probabilidade ou se os dados que foram pré-partilhados entre o emissor e o receptor têm grandes -bits de min-entropia, então o que o adversário pode esperar é que toda vez ele possa perguntar o valor deste oráculo H sobre os dados mais favoráveis que achar que o remetente e o receptor podem ter escolhido conforme essa distribuição de probabilidade Então, a probabilidade de que em cada consulta única, ela tenha realmente consultado para o exato, é 12, pois isso veio da definição de -bits de min-entropia e já que o adversário fez número de consultas, com probabilidade máxima 2, adversário A pode consultadas para a entrada H de a partir do oracle H. E se assumirmos que grandes são suficientemente grandes e é qualquer como polinomialmente delimitado no parâmetro de segurança, esta é alguma função insignificante no parâmetro de segurança. Assim, já que o adversário não se consultou por H de, exceto com probabilidade insignificante, do ponto de vista do adversário, a chave resultante vai ser uma sequência uniformemente aleatória l e que garante que agora o emissor e o receptor podem usar com segurança a chave derivada para qualquer criptografia de criptografias como chave. Diga por exemplo se eles querem usar a chave como a chave para AES, eles podem usá-la com segurança. Então, agora, você pode ver que como essa função de derivação de chave altamente eficiente baseada na função hash pode ser comprovada segura se entrarmos no modelo Random-Oracle. Mas se apenas entrarmos em modelo padrão e utilizarmos as propriedades padrão das funções hash, a saber, a colisão-resistência, não podemos provar que a tão chamada função de derivação de chave é, de fato, uma função de derivação de chave segura. Então isso me leva até o final desta palestra. Só para resumir nesta palestra, continuamos nossa discussão sobre o modelo Random-Oracle. Vimos que temos certos argumentos a favor do modelo Random-Oracle, temos certos argumentos contra o modelo Random-Oracle e assim por diante. Então isso me leva até o final desta palestra. Só para resumir nesta palestra, introduzimos um modelo Random-Oracle. Isto basicamente é usado para dar a prova de segurança de primitivas criptográficas com base em algumas funções hash onde não podemos concluir uma prova de segurança desse primitivo apenas usando as propriedades padrão das funções hash nomeadamente a propriedade de resistência de colisão e vimos também uma demonstração do modelo Random-Oracle, nomeadamente vimos que se tomarmos uma função hash e modelá-la como um Oracle Random, então podemos usá-la para construir um gerador pseudorandom. Obrigado.