Loading
Nota de Estudos
Study Reminders
Support
Text Version

Instanciação prática de PRGs

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 Professor de Technology-BangaloreLecture-12Practical Instantiações do PRGOlá todos, bem-vindo à palestra 11. (Consulte o Tempo do slide: 00 :30) O plano para esta palestra é o seguinte. Nesta palestra discutiremos sobre as instanciações práticas de geradores de pseudo aleatórios, a saber, veremos a construção baseada no registro de turnos de feedback linear e RC4 e discutiremos sobre os desenvolvimentos recentes na área de instanciações práticas de pseudo gerador aleatório. A razão pela qual chamamos essas instanciações como práticas é que elas são super-rápidas, em comparação com as construções provavelmente seguras de pseudo geradores aleatórios que havemos discutido na última palestra com base em uma só função e uma forma de permutação. No entanto, infelizmente, para essas instanciações práticas de pseudo geradores aleatórios, não temos nenhuma prova matemática de que eles sejam de fato pseudo geradores aleatórios. Isso significa que não temos a declaração de teorema, o que prova que ei não existe um distinguidor de tempo polinomial que pode distinguir a saída deste gerador de número aleatório da saída de um verdadeiro gerador de números aleatórios. É somente porque desde a construção dessas instanciações práticas de PRGs não encontramos nenhum ataque adequado ou qualquer outro adequado, acreditamos que essas construções são seguras, enquanto que para as construções provavelmente seguras baseadas em uma função de uma maneira e predicado hard-core que discutimos na última palestra, temos uma prova matemática de que de fato eles são seguros no sentido não existe nenhum distinguidor de tempo polinomial para distinguir a saída desses algoritmos da saída do real gerador de número aleatório verdadeiro. Assim, na prática, onde quer que você tenha uma construção criptográfica onde deseja instanciar um gerador pseudo-aleatório, nós realmente vamos para essas instanciações práticas. (Consulte o Tempo do slide: 02 :08) Então em todas as instanciações práticas de geradores pseudo-aleatórios, podemos seguir a abstração a seguir. Imagine que você recebe um gerador pseudo-aleatório, que expande uma entrada de l-bits para uma saída de?-bits. Podemos supor que o gerador pseudo-aleatório consiste em um par de algoritmos, a saber, um algoritmo de inicialização e algoritmo de GetNextBit. E o que basicamente esses algoritmos fazem são como segus.Então, o algoritmo do Init é na verdade o algoritmo de inicialização que configura o estado inicial do seu algoritmo e ele é uma função determinística. E leva a semente para o algoritmo? como a entrada e juntamente com isso um vetor de inicialização opcional, portanto, este vetor de inicialização é opcional. Não é necessário que toda instanciação prática de um gerador pseudo-aleatório deva assumir este vetor de inicialização, depende da construção.Entretanto, se o?? é dado como uma entrada, ele é publicamente conhecido, e baseado na semente e??, o algoritmo de inicialização produz um estado inicial do algoritmo que denotamos por? ?0. Agora, o algoritmo GetNextBit faz o seguinte. É preciso o estado atual do seu algoritmo ou o PRG, que eu denote por? ??, e ele atualiza o estado para? ?? + 1 e junto com isso ele produz o próximo bit de saída do seu algoritmo?, right.Então, se você deseja gerar uma sequência de bits, o que fazemos é fazer o algoritmo de inicialização, obter o estado inicial??? e dizer se você está interessado em obter uma saída de big?-bits, basicamente nós invocamos este algoritmo de GetNextBit? número de vezes em sequência e em cada chamada o estado fica atualizado e os bits de saída se mantêm em ser gerados um a um. Sendo assim, essa é a abstração que podemos utilizar para abstrair qualquer instrumentação prática de pseudo gerador aleatório. (Consulte o Tempo do slide: 04 :03) Então vejamos, uma popularmente usada instanciação prática de gerador pseudo-aleatório, que utilizamos no hardware. E isso é chamado de registro de turno de feedback linear ou LFSR. Por isso, historicamente, foi usado como PRG. E é muito rápido quando implementado em hardware. No entanto, não é recomendável ser usado para aplicações críticas, pois é muito fácil para um adversário recuperar a chave inteira apenas vendo poucos bits de saída do LFSR.Então, um LFSR de grau? basicamente consiste em? registros denotados por? 0to?? − 1. E junto com isso, vai ter? coeficientes de feedback? 0to?? − 1, onde os coeficientes serão valores booleanos. Assim, por exemplo, aqui temos um LFSR de grau 4 composto por 4 cadastros, e os coeficientes de feedback são 0, 1, 0, 1. Então, como funciona um LFSR. No que diz respeito ao estado de um LFSR, o estado não passa dos valores de bits que são armazenados no register.Então, se tomarmos este exemplo particular, então o estado do LFSR não passa de uma cadeia de 4 bit a saber: os 4 bits armazenados nos registos? 3,? 1 e? 0 e atualização do estado acontece da seguinte forma: após cada ciclo do relógio, o bit que está presente em? 0is vai ser produzido como o bit de saída e o conteúdo de todos os registos são de direita deslocados. Como resultado disso, o que vai acontecer é que a atual? 1 vai se tornar a próxima? 0. A corrente? 2 vai se tornar a próxima? 1 e assim por diante. E como resultado? 3 se tornará vazio. E o valor atualizado do último cadastro, neste caso? 3, será determinado tomando-se um XOR dos subconjuntos dos bits do estado atual. E os subconjuntos dos cadastros cujo XOR tiramos é realmente determinado pelo coeficiente de feedback. Por isso, novamente neste exemplo, uma vez que os coeficientes de feedback são 0, 1, 0, 1, isso significa, depois de cada ciclo de clock uma vez que fizermos o deslocamento certo aqui, o valor de? 3, não é nada, mas o XOR da corrente? 2, e o atual? 0. Se você pegar o XOR que será o valor que será alimentado como o novo valor de? 3. É por isso que o nome linear feedback shift register. Em cada ciclo do relógio, deslocamos o conteúdo de todos os cadastros por uma posição e é por isso que o shift register. E o feedback linear, porque temos um loop de feedback que determina o valor do conteúdo de?? − 1, no ciclo do próximo relógio. E essa função de feedback é uma função linear do conjunto atual de registros. É por isso que o nome linear feedback shift register. (Consulte o Slide Time: 06 :54) Assim por exemplo, se você pegar este LFSR de grau 4, e suponha que o estado inicial seja 0011, então após o primeiro relógio, tudo será deslocado por uma posição, e como resultado, o bit 1 vai ser o primeiro bit de saída e o feedback que estará indo para o LFSR para a próxima iteração será 1, a saber o XOR do bit 0 e 1 porque seus coeficientes de feedback são 0, 0, 1 e como resultado o próximo estado do LFSR será 1001.Again após o próximo ciclo de clock, o valor de bit 1 será fluseado saída de teste; que será o segundo bit de saída de seu LFSR e o feedback que estará indo será de 1 e como resultado o seu estado será atualizado para 1100 e assim por diante. Então, é assim que um LFSR de grau? opera. (Consulte o Slide Time: 07 :49) Agora vamos argumentar se este LFSR está seguro ou não, isso significa que podemos considerar que este LFSR é um pseudo gerador aleatório. E a exigência de um gerador aleatório pseudo é que se alguém lhe der a amostra de um LFSR, onde você não é dado o estado inicial do algoritmo porque se você for dado o estado inicial do LFSR então você pode realmente computar todos os bits de saída do LFSR. Por isso, imagine que você não é dado o estado de entrada do LFSR e junto com isso imagine que você não está atendendo os coeficientes de feedback também mas você recebe o grau do LFSR, isso significa, você sabe o número de cadastros que são usados no LFSR. Em seguida, é possível que o atacante compute ou preenda resultado de LFSR. Acontece que se nós temos um LFSR de grau?, então pode ter no máximo 2? − 1 estados não zero. E por que estamos interessados em estados não nulos? Pois uma vez que o LFSR ocupa o estado, onde o conteúdo de todos os cadastros é de 0, então depois disso não importa quantas vezes ou quantas ciclovia operamos o LFSR,todos os estados subsequentes serão 0. Isso significa que uma vez que atingimos um estado all-zero, devemos parar de gerar as saídas de LFSR. Por isso, o caso interessante é quando na verdade nos concentramos nos estados não zero da LFSR. Definimos o LFSR para ser um LFSR de comprimento máximo, se ele a sequência de saída se repete depois de exatamente 2? − 1number de estados não zero. E, curiosamente, verifica-se que não importa com qual estado de entrada você começa com, se você começar com qualquer estado inicial diferente de zero, então é sempre possível configurar os coeficientes de feedback de tal forma que seu LFSR realmente se torne um comprimento máximo LFSR.Isso significa começar com aquele estado inicial diferente de zero, você pode passar por todos os 2? − 1 não zerostatos e, em seguida, apenas a sequência se repetirá. Então imagine para o momento que você tem um LFSR de comprimento máximo. Intuitivamente, você pode sentir que todas as cordas de? bits vão ser produzidas com igual frequência, então isso significa que o seu LFSR é um PRG seguro porque se o estado de saída vai ser repetido depois de 2? − 1 número de estados, isso significa para um atacante, tem que esperar por 2? − 1 número de estados, que é uma quantidade exponencial de quantidade. E, portanto, não pode distinguir a saída do LFSR da saída de um verdadeiro gerador de números aleatórios. Essa pode ser a sua intuição subjacente com base na qual você pode declarar seu LFSR para ser seguro. Mas acontece que esse não é o caso. Para um LFSR de grau?, apenas observando o número polinomial de bits de saída, (Consulte o Tempo do slide: 10 :26) um adversário pode recuperar a chave inteira e uma vez que ele recupera a chave inteira, ele pode prever todos os bits de saída futuros de LFSR direito. Então imagine que você recebe um LFSR de grau?, onde você não sabe os coeficientes de feedback e você não conhece os estados iniciais de LFSR e imagina que o adversário observou os primeiros 2? bits de saída do LFSR que eu denoço por? 1, …,? ?.E o estado inicial do estado inicial do LFSR é denotado pela notação (?? − 1 (0), …,? 0 (0)). Então nesta notação, no superscript, estou colocando 0 no parêntese que denota o 0º estado de LFSR a saber, o estado inicial, e que também é desconhecido para o atacante, o atacante viu apenas os primeiros 2? bits de saída. Também assumimos que o adversário não está ciente dos coeficientes de feedback; do ponto de vista do adversário, poderia ser qualquer subconjunto do? registra que na verdade estão recebendo XORed para decidir o feedback. Então, os coeficientes desconhecidos?? − 1to? 0 também são, portanto, o atacante. Acontece que adversário sabe a relação que o estado inicial do LFSR não é senão o primeiro? saída bits que ele viu porque se você ver o funcionamento do LFSR, depois de cada ciclo do relógio, o conteúdo de? 0is realmente saindo como a saída e após cada ciclo do relógio, o novo conteúdo de? 0is na verdade o conteúdo anterior? 1, que por sua vez é na verdade o anterior? 2 e assim por diante. Isso significa adversário sabe que o primeiro? bits de saída de seu LFSR não são nada, mas o seu estado inicial. Sendo assim, essa é a primeira informação que agora está disponível para o adversário, que é hoje uma quantidade significativa de informações para o adversário. E acontece que os próximos bits de saída, a saber?? + 1to? 2?, dá realmente um sistema de equações lineares nas incógnitas nos coeficientes de feedback para o adversário. A saber, adversário sabe que o? + 1 ?h saída bit?? + 1is nada, mas? 0?1 ⨁?1?2 que usa … bateria?? − 1 ??. Da mesma forma, o bit de saída de 2 ??h satisfaz a relação? 2? =? 0??⨁?1?? + 1 folhas … bateria?? − 1 ?2? − 1. Então adversário recebe um sistema de? equações independentes em? variáveis. E, resolvendo-os, pode recuperar completamente de volta os coeficientes de feedback. Por isso, agora tanto as chaves quanto os coeficientes de feedback são conhecidos do adversário.E daí pode determinar completamente todas as saídas subsequentes do seu LFSR. Isso significa apenas observando 2? de saída de bits do LFSR, adversário pode quebrar completamente este LFSR. E daí, de jeito nenhum, é na verdade um pseudo gerador aleatório. (Consulte o Tempo do slide: 13 :27) Assim, um método que é usado para preservar a segurança do LFSR é adicionar algum tipo de non?linearidade. Se você vir o ataque, ou a estratégia, que é usada pelo atacante aqui é explorar o sistema de equação linear, ou a saber, o atacante usa o fato de que o feedback é realmente uma função linear do subconjunto do cadastro. Por isso, uma maneira de se conviver com isso é adicionar algum tipo de non?linearidade no registro de deslocamento de feedback. E há várias formas de introduzir a não linearidade na construção de registo de turnos de feedback linear. O primeiro método de adição da não linearidade é fazer com que o seu feedback em si seja não linear. Ou seja, o que supomos aqui é que o conteúdo do? ?hregister no ciclo do relógio? + 1 será o conteúdo do? + 1 ?hregistra-se no ciclo do relógio?, isso significa que tudo ainda é deslocado por uma posição após cada ciclo do relógio. Mas o conteúdo do último registo é agora uma função não linear dos registos actuais. Então, na construção anterior no LFSR, a função? era na verdade uma função linear. Mas a proposta aqui é que, em vez de garantir que o feedback seja uma função linear, o feedback agora vai ser uma função não linear do conjunto de bits que estão lá no cadastro atual. Então, essa é uma maneira de adicionar não linearidade que é seguida nas construções modernas de pseudo geradores aleatórios baseados em registros de deslocamento de feedback. A outra maneira de adicionar a não-linearidade é adicionar non linearidade na própria saída. Então até agora estamos discutindo o caso em que a saída é realmente o conteúdo da corrente? 0, onde? 0is o valor de? 1in o ciclo do relógio anterior e assim por diante e a cada ciclo de clock tudo fica deslocado por uma posição. Mas eu poderia ter outra maneira de determinar a saída, em que a saída é realmente uma função não linear. E existem 2 maneiras de determinar geradores de combinação não linear. Variante um é o seguinte: ainda usamos o LFSR único, onde tudo é deslocado por uma posição e temos um feedback linear. Mas, em vez de apenas garantir que? 0is o bit de saída, o bit de saída acaba sendo uma função não linear dos registradores atuais. E a variante dois é, em vez de usar um LFSR, teremos agora vários LFSR, de preferência de diferentes graus. E o bit de saída geral do LFSR encadeado será uma complicada função não linear da saída das LFSRs individuais. Sendo assim, essa é a segunda variant.Então, isso significa adicionar não linearidade você tem 2 opções, não linearidade no feedback e não linearidade na saída, em que a não linearidade na saída pode ser alcanada de 2 maneiras. Basta usar 1 LFSR, com a saída sendo uma função não linear complicada e a opção dois é utilizar vários LFSRs, sendo que a saída é uma função não linear complicada da saída das LFSRs individuais. (Consulte o Tempo de Slides: 16 :31) E verifica-se que as construções modernas de PRGs baseadas em LFSR de fato utilizam esses princípios. Por isso, aqui está uma construção candidata baseada no LFSR, que se chama Trivium. E é uma instanciação altamente popular de pseudo gerador aleatório. Se você ver pictorialmente, na verdade é uma combinação de 3 registros de deslocamento de feedback. Então você tem o primeiro LFSR composto por 93 registros, que nós denotamos como o registro de deslocamento de feedback A. Então você tem o próximo LFSR, que nós denotamos B consistindo de 84 registradores. E então temos o próximo turno de feedback registra C, consistindo em 111 registros. Agora, a razão pela qual ela está usando 93, 84, 111 não são claramente conhecidos; eles são o princípio de design utilizado pelos designers do trivium. No entanto, existem alguns princípios bem conhecidos que são utilizados para selecionar o valor de FSR A, FSR B, FSR C assim. Mas, caso contrário, em geral não há diretrizes fixas que sejam usadas para selecionar o tamanho de FSR A, FSR B, FSR C para ser assim. E agora, você vê que cada FSR tem uma saída individual. Portanto, se eu considerar a saída da FSR A, portanto, é basicamente o XOR do registo de mais à direita, neste caso, o 93º registo e outro registo da mesma FSR. Sendo assim, esta é a primeira diferença na construção do Trivium em comparação com o LFSR.No LFSR regular, o 93º output, o conteúdo do 93º registro será considerado como a saída pouco depois de cada ciclo do relógio. Mas agora depois de cada ciclo do relógio, é o XOR do 93º registo e um 66 ?hregister in the FSR A, que será considerado como a saída da FSR A após os ciclos de clock individual. E o mesmo se mantém para a FSR B assim como a FSR C. Essa é a primeira forma de adicionar a não-linearidade aqui. E a saída geral da FSR é basicamente o XOR da saída da FSR A, FSR B, FSR C. Então essa é a segunda forma de adicionar a não linearidade aqui. Até onde o feedback é considerado aqui, se você vê por exemplo, o FSR A aqui, agora o que está indo como o feedback? Assim, o feedback não passa de uma função basicamente de um dos registos na mesma FSR e um subconjunto de registos da FSR acima dele. Então o que quero dizer “ acima dele ” aqui é o seguinte: como eu disse a sequência dos primeiros 93 registos é o FSR A e o próximo registo 84 é FSR B e o próximo registo 1011 é FSR C. Pode-se imaginar esta construção como algum tipo de construção circular, onde acima da FSR A, temos o FSR C, acima da FSR B temos o FSR A e acima da FSR B temos o FSR B. É o que eu quero dizer por “ acima ” Neste contexto. E o feedback da FSR A é basicamente um XOR de um dos registos da FSR A, juntamente com alguns dos registos da FSR C. Da mesma forma, o feedback da FSR B é um XOR de alguns dos registo da FSR B junto com alguns dos registos na FSR A, e da mesma forma o feedback para a FSR C é um XOR de alguns dos registos da FSR C juntamente com alguns dos registos na FSR B.É assim que estamos introduzindo a não linearidade. Então, a ideia aqui é de fazer essa construção complicada, estamos realmente removendo completamente a linearidade que estava presente na construção original da LFSR. E é assim que o Trivium é projetado. E este é considerado um PRG seguro porque, após o desenvolvimento desta construção, não temos nenhum ataque prático. Isso significa que nenhum algoritmo de tempo polinomial foi relatado, o que pode realmente prever resultado do trivium se o estado inicial do trivium não for conhecido do you.Então, eu não estou indo para os detalhes completos da construção, quais princípios de design são usados, por que as 3 FSRs usadas, seus graus são construídos como este e assim por diante. Se você quiser saber mais sobre os detalhes de tais construções você pode se referir a qualquer uma das referências que estamos seguindo neste curso. (Consulte o Tempo do slide: 20 :56) Agora consideraremos outra instanciação popular de gerador de pseudo aleatório, a saber, RC4 que é super rápido quando implementado em software. E apesar de ter sido altamente popular tillalguns anos de volta, recentemente várias vulnerabilidades foram relatadas. E é por isso que não é mais recomendado para ser usado para fins críticos. Na verdade, ele foi usado como um dos padrões no WEP.E depois que vulnerabilidades foram relatadas em RC4 ele não é mais usado no padrão. Então, lembre-se de que qualquer instanciação prática de pseudo gerador aleatório consiste de 2 algoritmos, a saber, um algoritmo de inicialização e um algoritmo de atualização de estado. E no algoritmo de inicialização, o estado é inicializado e dentro do algoritmo de atualização do estado, o estado é atualizado e os próximos bits de saída gerados. Assim, no que diz respeito ao estado em RC4, o Estado basicamente consiste em uma matriz, consistindo em 256 bytes. E ao longo do algoritmo, será garantido que estes 256 bytes realmente consistem em uma permutação do conjunto de 0 255. Isso significa que cada um dos valores de 0 a 255 ocorrerá como um dos bytes entre estes 256 bytes. E é por isso que se trata de uma permutação do conjunto 0 para 255.Now o algoritmo de inicialização para este RC4 é o seguinte. O algoritmo de inicialização cria uma permutação aleatória pseudo-aleatória do conjunto de 0 255. E junto com isso, inicializar os ponteiros 2index? e? na faixa de 0 255. É assim que a inicialização acontece para o RC4, entraremos em detalhes da inicialização muito em breve. E uma vez que a inicialização é feita, no algoritmo de atualização do estado em cada iteração os bytes do?, que na verdade são uma permutação pseudo dependente principal do conjunto 0 a 255 são embaralados em volta, e depois de embaralhamento um dos bytes é saída, é assim que o estado é atualizado. (Consulte o Tempo do slide: 23 :02) Então agora vamos entrar nos detalhes do algoritmo de inicialização. Por isso, a chave ou a semente para o RC4algorithm é basicamente uma chave de 16 byte, que vai ser uma chave aleatória de 16 byte. Então nós denotamos itby? 0to? 15. E a saída vai ser uma pseudo permutação aleatória do set 0 255. Então, essa será a matriz?. Então inicializamos a matriz? consistindo de valores 0 255 em sequence.Namely, o primeiro byte é definido como 0. O próximo byte é configurado para ser 1 e o último byte é dito como thevalue 255. Esta é uma permutação de identidade. E agora temos que alguns como reshuffle o conteúdo da matriz? com base no valor da matriz chave?. Isso significa que dependendo do conteúdo dos bytes principais, temos que embaralar o conteúdo da matriz?, garantindo que depois de embaralhamento, o modificado? ainda representa uma permutação do conjunto 0 ao 255.So para fazer isso, na verdade repetimos os valores da chave e garantimos que a matriz chave torne-se do tamanho 255. E isso é feito realizando a operação,? [?] =? [? mod 16], isso significa que nós tiramos os primeiros 16 bytes minutos, e repetimos de novo e de novo, para garantir que tenhamos agora uma matriz de chave expandida de tamanho 256. Essa é a forma como fazemos a expansão fundamental. E então definimos o ponteiro de índice inicial? a ser 0. E uma vez o ponteiro? é configurado para 0, para as próximas 256 iterações, fazemos o seguinte. Nós fazemos o embaralhamento e para fazer o embaralhamento, na verdade mudamos o valor de? como esta: nós definimos? ser a somatória da corrente? e conteúdo atual do? ?h byte de? e o byte de chave? ?h. Ou seja,? =? +? [?] +? [?]. E uma vez que temos o índice atualizado?, trocamos o conteúdo de? [?] e? [?]. É assim que fazemos o "embaralhamento". Então, intuitivamente o que você pode imaginar aqui é que em cada iteração, o índice? fica incrementado em 1. E em cada iteração o índice? é aleatoriamente embaralhando, dependendo do byte das chaves. E uma vez o ponteiro? é atualizado, vamos para aquele local na matriz? .E troque o conteúdo? [?] com o conteúdo desse local. É assim que geramos de fato uma permutação aleatória pseudo-dependente de?. Por que esta é uma permutação aleatória pseudo-dependente de? é porque em cada iteração, o valor de? depende do conteúdo da matriz de chaves. Esse ’ s como a permutação resultante é uma permutação-chave-dependente. (Consulte o Tempo do slide: 26 :01) Agora uma vez que o estado foi inicializado, vamos para o algoritmo de atualização e saída do estado. Sendo assim, no algoritmo de atualização do estado, em cada chamada, o conteúdo atual do? será embaralhando em torno e um dos bytes vai ser saída. Então, a forma como ela é gerada é a seguinte. Imagine que temos a corrente? e a corrente?, o que fazemos é incrementar o valor de?. E então, aleatoriamente, decidimos o valor de?, dependendo do conteúdo atual de? da seguinte forma. Então, o valor de? é atualizado de forma pseudo-aleatória configurando-se:? Libras (? +? [?]) mod 256. Isso quer dizer, seja qual for o índice atual de?, para isso adicionamos o valor de byte que é armazenado na? ?hlocation da matriz?, e para garantir que fazemos o wArmazenound, todas as operações são feitas modulares 256. Então, ao fazer essa operação atualizamos o valor do contador de índice? de uma moda pseudo?aleatória. E então o que fazemos é, trocamos o conteúdo de? ?hlocalização da matriz? e? ?hlocalização da matriz?. É assim que realmente fazemos a atualização do Estado. Para determinar a saída, o que fazemos é determinar um novo índice?, que não passa de somatória do conteúdo da? ?hlocation da matriz? e o? ?hlocation da matriz? .Ou seja,? Fixo (? [?] +? [?]) mod 256. E nós vamos para aquele local, que é o? ?hlocation e qualquer que seja o valor de byte que é armazenado lá, esse é o valor de byte que vamos para a saída. (Consulte O Tempo De Deslizamento: 27 :46) Então, agora, vamos discutir sobre a segurança do algoritmo RC4. Por isso, se você vir o pseudocode do algoritmo de atualização de estado e algoritmo de inicialização, você pode ver que nós não estamos fazendo nenhuma operação complicada. É por isso que este algoritmo é super-rápido quando você implementa em software. E é por isso que foi altamente popular. Em seguida, as pessoas começaram a relatar vulnerabilidades na segurança do RC4. Então, nós queremos analisar aqui se realmente RC4 é um candidato pseudo-gerador de número aleatório ou não. Por isso, se você relembrar, em cada alteração da atualização do estado, RC4 outputs um byte. Então temos que comparar o algoritmo do gerador de bytes RC4 com um verdadeiro algoritmo gerador de byte aleatório verdadeiro algoritmo gerador aleatório de byte aleatório produzirá qualquer byte no conjunto 0 255, uniformemente aleatoriamente. E o resultado esperado a partir do RC4 é que em cada chamada do algoritmo de atualização do estado, o byte de saída poderia ser quase como um valor aleatório uniformemente do set 0 255. Acontece que em uma das obras anteriores, Mantin e Shamir mostraram que mesmo que assumamos que a inicialização de algoritmo do RC4 é uma inicialização uniforme (isso significa que ele não depende do algoritmo chave), se começarmos a executar o algoritmo de atualização do estado, então o segundo byte de saída de RC4 é mais provável que seja 0 que significa, a probabilidade de que o segundo byte de saída de RC4is 0 seja de 2256, comparado a 1256. E isso pode ser provado formalmente. Então, se você quer ver os detalhes formais exatos que como exatamente essa probabilidade é derivada você pode se referir a uma das referências que estamos seguindo. Então, supondo que este seja o caso, então aqui está um RC4distinguisher muito simples que pode distinguir um byte de amostra gerado pelo gerador de bytes RC4, a partir de uma amostra que é gerada por um gerador de bytes verdadeiramente aleatório. Então imagine que o distinguidor recebe uma amostra?, e ele tem que determinar se ele é produzido pelo gerador de bytes RC4 ou por um gerador de bytes aleatórios. Então o que o diferenciador faz, já que sabe o resultado de Mantin e Shamir, ele apenas verifica o segundo byte de?, e então se o segundo byte de? acaba por ser 0, então ela rotula que a amostra? é gerada pelo gerador de bytes RC4. Caso contrário, rotula a amostra? ser gerado por uma saída verdadeiramente aleatória. Agora, calculemos a vantagem distintiva do distinguidor que projetamos. Se de fato a amostra? que é uma sequência de bytes é gerada pelo RC4 por gerador é dada ao distinguidor então a probabilidade de que realmente o segundo byte seja 0 é 2256. Portanto, a probabilidade de que nosso distinguidor quando dada uma amostra aleatória gerada por gerador de bytes de RC4 ele como o resultado de RC4 é 2256. Considerando que se a sequência de bytes é gerada por um gerador de bytes verdadeiramente aleatório é dado ao distinguidor, do que a probabilidade de que o seu segundo byte seja de 0 é realmente de 1 acima de 256. Isso significa, nesse caso, apenas, com tanta probabilidade apenas, nosso distinguidor acabará rotulando uma verdadeira sequência aleatória de bytes para ser um resultado de um RC4. Então qual é a vantagem distintiva do atacante neste caso? Bem, a diferença absoluta é de 1256, o que é uma probabilidade significativa. Isso significa que não podemos mais afirmar que a sequência de bytes que são gerados pelo bytegerador RC4 está próximo da sequência de bytes, que um gerador de bytes verdadeiramente aleatório teria produzido e é por isso que este RC4 não é mais considerado como seguro. Para concluir, nesta palestra temos visto em um nível muito alto algumas das instanciações práticas de pseudo gerador aleatório. Em seguida, vimos uma construção baseada em hardware, que chamamos como o registro de turno de feedback linear. O registro de turno de feedback linear original não é mais usado na forma como foi proposto, pois ao observar o número polinomial de saídas, um adversário pode descobrir o estado inteiro assim como os coeficientes de feedback e, portanto, obter pode prever todos os bits de saída subsequentes do LFSR. Por isso, é por isso que as modernas instanciações de geradores aleatórios pseudoados baseados no registro de deslocamento de feedback introduzem algum tipo de não linearidade que pode ser feita por várias formas, como a não linearidade na forma de coeficientes de feedback não linear, bits de saída não linear e assim por diante. Também discutimos uma construção chamada Trivium, baseada nesse princípio, e uma segunda construção que vimos é a construção de software que pode ser implementada em software e ela é super?rápida, a saber, RC4. Infelizmente, também vimos algumas das vulnerabilidades que foram relatadas em RC4 devido ao qual não é mais recomendável ser usado.