cifras do mundo real de fluxo (20 min)

Neste segmento, eu quero dar alguns exemplos de fluxo cifras que são usados na prática.

Vou começar com dois exemplos antigos que na verdade não são

suposto ser usado em sistemas novos. Mas, no entanto, eles ainda são bastante

amplamente utilizada, e assim que eu apenas quero mencionar os nomes para que você esteja familiarizado com

esses conceitos. A cifra de fluxo primeiro eu quero falar é chamado RC4, projetado

em 1987. E eu só vou te dar a descrição de alto nível e, em seguida

nós vamos falar sobre alguns pontos fracos do RC4 e deixar por isso mesmo. Assim RC4 leva um

sementes de tamanho variável, aqui eu só dei como um exemplo onde levaria 128

bits como o tamanho das sementes, que passaria então a ser utilizados como chave para a cifra de fluxo.

A primeira coisa que faz, é que se expande a chave de 128-bit segredo em 2.048 bits, que

vão ser usados como o estado interno para o gerador. E então, quando ele é feito

esta expansão, que basicamente executa um laço muito simples, onde cada iteração do

laço Isso gera um byte de saída. Então, basicamente, você pode executar o gerador de

, enquanto você quer, e gerar um byte de cada vez. Agora RC4 é, na verdade, como eu disse,

bastante popular. É usado no protocolo HTTPS é bastante comum, na verdade.

Estes dias, por exemplo, o Google usa RC4 em suas HTTPS. Também é usado no WEP como nós

discutido no último segmento, mas é claro que no WEP, ele é usado incorretamente e

é completamente inseguro da forma como ele é usado dentro do WEP. Assim, ao longo dos anos,

algumas deficiências foram encontradas no RC4, e como resultado, é recomendado que os novos projetos

na verdade não usar RC4, mas sim usar um mais moderno gerador pseudo-aleatório como veremos

discutir para a extremidade do segmento. Então deixe-me mencionar apenas dois dos pontos fracos.

Então a primeira é que é tipo de bizarra, basicamente, se você olhar para o segundo byte

da produção de RC4. Acontece que o segundo byte é um pouco tendencioso. Se RC4 foi

completamente aleatória, a probabilidade de que o segundo byte acontece ser igual a zero

seria exatamente um sobre 256. Existem 256 bytes possíveis, a probabilidade que

zero, deveria ser um sobre 256. Acontece que para RC4 a probabilidade é

realmente dois por 256, o que significa que se você usar a saída RC4 para criptografar uma

mensagem do segundo byte é provável que não seja encriptada de todo. Em outras palavras, ele vai

ser XOR-ed com zero com o dobro da probabilidade de que é suposto.

Assim, dois sobre 256, em vez de um sobre 256. E pelo jeito que eu deveria dizer que há

nada de especial sobre o segundo byte. Acontece que a primeira e os bytes terceiros

também são tendenciosos. E de fato ele é agora recomendado que se você vai usar RC4,

que você deve fazer é ignorar, basicamente, os primeiros 256 bytes da saída e apenas

começar a utilizar a saída do gerador a partir de byte 257. O primeiro casal

de bytes acabou por ser tendencioso, então você simplesmente ignorá-los. O segundo ataque que

foi descoberto é que de fato se você olhar para uma saída muito longo de RC4 que acontece

que você é mais provável conseguir o 00 de seqüência. Em outras palavras, você é mais

probabilidade de obter dezesseis bits, dois bytes de zero, zero, do que deveria. Novamente, se RC4

foi completamente aleatória a probabilidade de ver zero, zero seria exatamente 1/256

quadrado. Acontece RC4 é um pouco tendencioso eo viés é 1/256 cubos. Ele

Acontece que este viés realmente começa depois de vários gigabytes de dados são produzidos por

RC4. Mas, no entanto, este é algo que pode ser utilizado para prever o gerador

e, definitivamente, ele pode ser usado para distinguir a saída do gerador

partir de uma seqüência verdadeiramente aleatória. Basicamente o fato de que zero, zero aparece com mais freqüência

do que deveria é o Distinguisher. E então, no último segmento que falamos

relacionado-chave ataques que foram usados para atacar WEP, que basicamente dizem que

se teclas de um utilizações que estão intimamente relacionadas entre si, então é realmente possível

para recuperar a chave raiz. Assim, estes são os pontos fracos que são conhecidos de RC4 e, como um

resultado, é recomendado que os novos sistemas não realmente usar RC4 e utilizar um

gerador pseudo-aleatório moderna. Ok, segundo exemplo que quero dar-lhe é um

cifra de fluxo gravemente quebrado que é usada para criptografar filmes em DVD. Quando você compra um DVD

na loja, o próprio filme é criptografada usando uma cifra de fluxo chamado de

Content Scrambling System, CSS. CSS acaba por ser uma cifra de fluxo gravemente quebrado

e podemos muito facilmente quebrá-lo, e eu quero mostrar-lhe como o algoritmo de ataque

obras. Estamos fazendo isso para que você possa ver um exemplo de um algoritmo de ataque, mas em

verdade, existem muitos sistemas por aí que, basicamente, usar este ataque para descriptografar

DVDs criptografados. Assim, a cifra de fluxo CSS é baseada em algo que o hardware

projetistas gosta. Ele foi projetado para ser uma cifra de fluxo de hardware que é suposto

ser fácil de implementar em hardware, e baseia-se um mecanismo chamado linear

mudança comentários registar. Assim, um registrador de deslocamento linear feedback é basicamente um registo

que consiste em células em que cada célula contém um bit. Então, basicamente,

que acontece é que existem estas torneiras em certas células, não todas as células, certos

posições são chamados torneiras. E então essas torneiras alimentar em um XOR e, em seguida, em

cada ciclo de clock, o registrador de deslocamento desloca para a esquerda. O último pedaço cair

e, em seguida, o primeiro bit torna-se o resultado deste XOR. Assim você pode ver que

este é um mecanismo muito simples de implementar, e em hardware tem muito poucos

transistores. Apenas o deslocamento para a direita, o último bit cai e apenas o primeiro bit

torna-se o XOR dos bits anteriores. Assim, a semente para este LFSR

, basicamente, é o estado inicial do LFSR.

E é a base de uma série de codificações de fluxo. Então, aqui estão alguns exemplos. Assim, como

eu disse, a criptografia utiliza duas LFSRs DVD. Eu vou te mostrar como isso funciona em apenas um

segundo. Criptografia GSM, estes são chamados algoritmos A51 e A52. E isso

utiliza três LFSRs. Criptografia Bluetooth é um algoritmo chamado, E zero. Estes são todos

cifras de fluxo, e que utiliza quatro LFSRs. Acontece que todos eles são gravemente quebrado

e na verdade realmente não deve ser confiável para criptografar o tráfego, mas todos eles são

implementado em hardware, por isso é um pouco difícil agora para mudar o que o hardware

faz. Mas o mais simples deles, CSS, na verdade, tem um ataque bonito nele, então vamos

me mostrar-lhe como o ataque funciona. Então, vamos descrever como o CSS realmente funciona. Assim,

chave para o CSS é de cinco bytes, ou seja, 40 bits, cinco vezes oito é de 40 bits. O

razão eles tinham que se limitar a apenas 40 bits é que a criptografia do DVD foi

concebidos numa altura em que os regulamentos de exportação dos Estados Unidos só é permitido para a exportação de

algoritmos crpyto onde estava a chave apenas 40 bits. Assim, os designers de CSS foram

já limitados a chaves muito, muito curtos. Apenas 40 teclas bit. Assim, seu projeto trabalha

como se segue. Basicamente, o CSS usa duas LFSR do. Um é um LFSR de 17-bit. Em outras palavras,

registo a contém 17 bits. Eo outro é um LFSR 25-bit,

é um pouco mais, 25 bits LFSR. E a forma como estas são semeadas LFSRs

é como se segue. Portanto, a chave para a criptografia, basicamente, tem a seguinte aparência.

Você começa com um, e você concatenar a ele os dois primeiros bytes de

chave. E esse é o estado inicial do LFSR.

E então o segundo LFSR basicamente é intitialized da mesma maneira.

Uma concatenado os últimos três bytes da chave. E isso é

carregado para o estado inicial do LFSR. Você pode ver que os dois primeiros bytes são

16 bits, mais um líder, que tem dezessete pedaços geral, enquanto o segundo

LFSR é de 24 bits, mais um que é de 25 bits. E você percebe usamos todos os cinco pedaços de

chave. Então essas são basicamente LFSRs correr para oito ciclos, de modo que elas geram

oito bits de saída. E então eles passam por este componente que faz basicamente

adição módulo 256. É assim que esta é uma caixa disso, módulo 256. Há mais uma

coisa técnica que acontece. Na verdade vamos realmente, também adicionada é o transporte do

bloco anterior. Mas isso não é tão importante. Isso é um detalhe que não é tão

relevante. OK, então todos os blocos, você percebe que estamos fazendo além modulo 256 e

estamos ignorando o transporte, mas o transporte é basicamente adicionado como um zero ou um um ao

além do bloco seguinte. Ok? E então, basicamente, esta saída um byte por round.

Ok, e então este byte é usado, então é claro, XOR-ed com o adequado

byte do filme que está sendo criptografado. Ok, então é um fluxo muito simples

cifra, é preciso hardware muito pouco para implementar. Ele irá correr rápido, mesmo em muito

hardware barato e vai criptografar filmes. Então, acontece que este é fácil de quebrar

no tempo cerca de dois a 17. Agora deixe-me mostrar-lhe como.

Então, suponha que você interceptar os filmes, então aqui nós temos um

filme criptografado que você deseja descriptografar. Então, digamos que tudo isso é criptografado para

você não tem idéia do que está dentro de aqui. No entanto, acontece que só porque

criptografia DVD está usando arquivos MPEG, acontece se você souber de um prefixo da

texto simples, vamos apenas dizer que talvez esta é de vinte bytes. Bem, sabemos que se você

XOR essas duas coisas juntas, então, em outras palavras, você faz o XOR aqui,

que você vai conseguir é o segmento inicial do PRG. Assim, você terá a

primeiros vinte bytes de a saída do CSS, a saída do presente PRG. Ok, então agora

aqui é o que nós vamos fazer. Assim, temos os primeiros vinte bytes de saída. Agora

nós fazemos o seguinte. Nós experimentar todos dois para os valores possíveis de 17 a primeira

LFSR. Ok? Assim, duas aos dezassete valores possíveis. Assim, para cada valor, portanto, para

cada um destes dois aos dezassete valores iniciais do LFSR, vamos executar o

LFSR por vinte bytes, ok? Então, vamos gerar de vinte bytes de saídas a partir deste

LFSR primeiro, assumindo-para cada um dos dois para os dezassete configurações possíveis.

Agora, lembre-se que temos o resultado completo do sistema de CSS. Então o que podemos fazer é nos

pode tomar esta saída que temos. E subtrair os vinte mordidas que nós

obtido a partir do LFSR primeiro, e se de fato o nosso palpite para o estado inicial do primeiro

LFSR está correta, o que devemos começar é a saída 20-primeiro byte do

LFSR segundo. Certo? Porque isso é, por definição, o que a saída do CSS

sistema é. Agora, descobre-se que olhar para uma seqüência de 20 bytes, é muito fácil

dizer se essa seqüência de 20-byte veio de um LFSR 25-bit ou não. Se

não, então sabemos que o nosso palpite para o LFSR 17-bit foi

incorreto e, em seguida, passamos para o próximo palpite para o LFSR 17-bit e

suposição o seguinte e assim por diante e assim por diante. Até que finalmente chegamos ao direito inicial

estado para o LFSR 17-bit, e depois vamos realmente começar, vamos ver que

os 20 bytes que obtemos como a saída candidato para o LFSR 25-bit é

, de facto, uma saída possível para um LFSR 25-bit. E então, não só teremos

aprendeu o estado inicial correto para o LFSR 17-bit, nós também teremos

aprendeu o estado inicial correto do LFSR 25-bit. E então podemos prever o

saídas restantes do CSS, e é claro, usar isso, podemos, então, decifrar o resto

o filme. Na verdade, podemos recuperar o texto restante. Okay. Isto é

coisas que falamos antes. Então, eu disse isso um pouco rápido, mas espero que,

ficou claro. Nós também vamos estar fazendo um exercício de dever de casa neste tipo de fluxo

cifras e você vai espécie de chegar ao ponto de como esses algoritmos de ataque

trabalho. E devo mencionar que existem muitos sistemas open-source, agora que realmente

usar esse método para descriptografar CSS dados criptografados. Ok, então agora que já vimos dois

fracos exemplos, vamos passar para exemplos melhores, e em particular o melhor

pseudo-aleatórios geradores vêm do que é chamado de Projeto eSTREAM. Esta é uma

projeto que concluiu em 2008, e que se qualifiquem, basicamente, cinco fluxo diferente

cifras, mas aqui quero apresentar apenas um. Então, primeiro de todos os parâmetros para

essas cifras de fluxo é um pouco diferente do que estamos acostumados. Então, essas

fluxo cifras normalmente eles têm uma semente. Mas, além disso eles também têm, o que é

chamado nonce e vamos ver o que é um nonce é usada em apenas um minuto. Assim

tomam duas entradas de uma semente e um nonce. Vamos ver o que o nonce é usada no

apenas um segundo. E claro que o de produzir uma saída muito grande, então n é aqui

muito, muito, muito maior do que s. Agora, quando eu digo nonce, o que quero dizer é um valor que é

nunca indo para repetir enquanto a chave é fixo. E eu vou explicar isso em mais

detalhe em apenas um segundo. Mas, por agora, basta pensar nisso como um valor único que nunca

repete, desde que a chave é a mesma. E então é claro que quando você tem este PRG,

você criptografar, você obtém uma cifra de fluxo tal como antes, só que agora como você vê, o

PRG toma como entrada tanto a chave eo nonce. E a propriedade do nonce é

que o par, k vírgula r, de modo a vírgula chave nonce, é nunca, nunca se repete. É

nunca usou mais de uma vez. Assim a linha inferior é que você pode reutilizar a chave, reutilizar

a chave, porque o uso único faz com que o par único, porque K e R são apenas

usado uma vez. Eu vou dizer que é único. Ok então este nonce é uma espécie de truque bonito que

nos salva a dificuldade de se mudar para uma nova chave de cada vez. Ok, então o particular

exemplo do eSTREAM que eu quero lhe mostrar é chamado Salsa 20. É uma

cifra de fluxo que é projetado para implementações de software e hardware

implementações. É uma espécie de interessante. Você percebe que algumas cifras de fluxo são

projetado para software, como RC4. Tudo que ele faz é projetado para fazer

implementação de software de correr rápido, enquanto o fluxo cifras outros são projetados para

hardware, como CSS, utilizando um LFSR que está particularmente desenhado para fazer hardware

implementações muito baratos. É também, a única coisa boa disso é que é

projetado de modo que seja fácil de implementar em hardware e seu software

implementação também é muito rápido. Então deixe-me explicar como Salsa obras. Bem, Salsa

leva ou 128 ou 256-bit chaves. Eu só vou explicar a versão de 128 bits do Salsa.

Então esta é a semente. E então ele também leva um nonce, tal como antes, que

passa a ser de 64 bits. E então ele vai gerar uma grande saída. Agora, como faz

realmente funciona? Bem, a própria função é definida como se segue. Basicamente, dado

chave eo nonce, ele irá gerar um tempo muito longo, bem, pseudorandom uma longa

sequência, enquanto for necessário. E vai fazê-lo usando essa função que eu vou denotar por

H. Este H função recebe três entradas. Basicamente a chave. Bem, a semente k,

o r nonce, e, em seguida, um contador que incrementa a partir do passo a passo. Assim vai

de zero a um, dois, três, quatro, contanto que inaudível] [ser. Ok? Então, basicamente,

avaliando este H nesta kr, mas usando este contador incrementar, podemos obter uma

seqüência que é tão longo como nós queremos. Então, tudo o que tenho a fazer é descrever como esta função

H funciona. Agora, deixe-me fazer isso aqui para você. O modo como funciona é o seguinte. Bem, nós

começar pela expansão dos estados em algo muito grande que é de 64 bytes

longo, e fazemos isso da seguinte forma. Basicamente, manter uma constante no início, de modo

há tao zero, estes são quatro bytes, é uma de quatro bytes constante, de modo a especificação para

Salsa, basicamente dá-lhe o valor tao zero. Então nós colocamos k em que é

bytes dezesseis. Então nós colocamos uma outra constante. Novamente, isto é quatro bytes. E

como eu disse, a especificação basicamente especifica o que esta constante é fixo. Então nós colocamos

nonce o que é de oito bytes. Então vamos colocar o índice. Este é o zero do contador,

um, dois, três, quatro, que é mais oito bytes. Então nós colocamos uma outra constante

tau dois, que é mais quatro bytes. Então nós colocamos novamente a tecla, este é outro

bytes dezesseis. E então, finalmente, colocar a terceira constante, tau três, que é

mais quatro bytes. Ok então, como eu disse, se você somar estes acima, você vê que você tem 64

bytes. Então, basicamente, nós expandimos a chave eo nonce eo contador em 64

bytes. Basicamente a chave é repetido duas vezes, eu acho. E então o que fazemos é aplicar uma

função, eu vou chamar isso de h pouco funcional. Ok, então nós aplicamos essa função, h pouco.

E esta é uma função que é 12:59 assim que mapeia 64 bytes para 64 bytes. É uma

função completamente invertida, ok? Portanto, esta função é h, o que eu digo, é uma

função invertable. Assim, dada a entrada que você pode obter o resultado e dada a

saída você pode voltar para a entrada. E ele é projetado especificamente por isso é um fácil

de implementar em hardware e b-on um x86, é extremamente fácil de implementar, porque

x86 tem este conjunto de instruções SSE2 que suporta todas as operações que você precisa fazer

para esta função. É muito, muito rápido. Como resultado, salsa tem um fluxo muito rápido

cifra. E então ele faz isso, basicamente, uma e outra vez. Por isso, aplica-se este

função h de novo e fica outros 64 bytes. E assim por diante e assim por diante, basicamente

ele faz isso dez vezes. Ok então a coisa toda aqui, dizer repete dez vezes, de forma

basicamente aplicar h dez vezes. E, em seguida, por si só, isto não é na verdade muito aleatória.

Não vai parecer aleatória, pois como dissemos, H é completamente invertable. Portanto, dado

este resultado final, é muito fácil basta inverter h e depois voltar para o original

insumos e faça o teste que a de entrada tem a estrutura correta. Então você faz mais um

coisa, que é basicamente XOR as entradas e as saídas finais. Na verdade,

pena. Não é um XOR. É realmente uma adição. Então você faz uma palavra além de

palavra. Então, se existem 64 bytes, você faz uma adição palavra por palavra e quatro bytes de cada

tempo e, finalmente, chegar a saída 64-byte, e é isso. Esse é o todo

gerador pseudo-aleatório. Então, isso, isso é toda a função, h pouco. E como eu

explicou, esta construção inteira aqui é a grande função H. E então você avaliar

H grande, incrementando o I contador de zero, um, dois, três em diante. E isso

lhe dará uma seqüência pseudo-aleatório que é o tempo que você precisa que ele seja. E

basicamente, não há ataques signifigant sobre isso. Isto tem a segurança que é

muito perto de duas para o 128. Vamos ver o que isso significa mais precisamente mais tarde.

É uma cifra de fluxo muito rápido, tanto em hardware e em software. E, na medida do

podemos dizer, parece ser imprevisível como necessário para uma cifra de fluxo. Então, eu

deve dizer que o projeto eSTREAM realmente tem cinco cifras de fluxo como

presente. Eu só escolhi Salsa porque eu acho que é o mais elegante. Mas posso dar-lhe

alguns números desempenho aqui. Assim você pode ver, estes são os números de desempenho em um

gigahertz 2.2, você sabe, tipo de máquina x86. E você pode ver que na verdade é o RC4

mais lento. Porque, essencialmente, bem, realmente não tirar proveito da

hardware. Ele só faz operações de byte. E por isso há uma grande quantidade de ciclos de desperdício que

não estão sendo utilizados. Mas os candidatos E-Stream, tanto Salsa e outros

candidato chamado Sosemanuk. Devo dizer que estes são finalistas eSTREAM. Estes são

realmente fluxo cifras que são aprovados pelo projeto eSTREAM. Você pode ver que

de terem atingido uma taxa significativa. Esta é a 643 megabytes por segundo nesta

arquitetura, mais do que suficiente para um filme e estas são realmente muito impressionante

taxas. E agora que você já viu exemplos de duas cifras de fluxo antigos que não devem ser

utilizado, incluindo ataques a essas cifras de fluxo. Você viu o que as cifras de fluxo modernos

parecido com este nonce. E você vê os números de desempenho para estes

fluxo cifras modernas por isso, se acontecer de você precisar de uma cifra de fluxo, você poderia usar um dos

os finalistas eSTREAM. Em particular, você poderia usar algo como Salsa.