Cifrador de fluxo Trivium e Autômatos Celulares

Trivium
Leandro Aparecido Sangalli
[email protected]
Marco Aurélio Amaral Henriques
[email protected]
Universidade Estadual de Campinas - UNICAMP
Faculdade de Engenharia Elétrica e de Computação - FEEC
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
1 / 19
Roteiro
Estaca Zero
Cifrador de Fluxo
Cifrador de Bloco
Introdução
Trivium
Geração de Chaves de Fluxo
Ideia Central no Estudo do Trivium
Autômatos Celulares
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
2 / 19
Estaca Zero
O que é um cifrador de fluxo?
No esquema de cifragem de fluxo, o texto em claro é cifrado bit a
bit.
Esta cifragem normalmente é realizada por meio do operador
lógico XOR (⊕).
Relembrando: 0 ⊕ 0 = 0; 1 ⊕ 0 = 1; 0 ⊕ 1 = 1 e 1 ⊕ 1.
Algoritmo ideal: One-Time-Pad (cifra de uso único)
Dificuldade: gerar números aleatórios com o mesmo tamanho da
mensagem que se deseja cifrar (chave).
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
3 / 19
Estaca Zero
Figure: Cifrador de fluxo (One-Time-Pad)
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
4 / 19
Estaca Zero
O que é um cifrador de bloco?
No esquema de cifragem de bloco, o texto em claro
primeiramente é dividido em blocos de tamanho pré-definido e
depois cifrado um bloco por vez.
Algoritmos: AES (128 bits), DES (128 bits), entre outros.
Problema: blocos de texto em claro iguais geram blocos idênticos
de texto cifrado.
Solução: utilizar dados extra na cifragem de cada bloco.
Exemplo: Um bloco cifrado é utilizado na cifragem do bloco seguinte
(Cipher Feedback Block).
Modo de Operação: Cipher Block Chaining (CBC), Cipher Feedback
Block (CFB), entre outros.
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
5 / 19
Estaca Zero
Figure: Cifrador de bloco
Cada bloco é enviado ao destinatário da mensagem
imediatamente após sua cifragem.
Ao receber todos os blocos o destinatário efetua a decifragem dos
mesmos na ordem como foram recebidos.
Após a decifragem os blocos são concatenados, formando a
mensagem original.
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
6 / 19
Introdução
Algoritmos criptográficos:
Troca de chaves:
Algoritmos Assimétricos (Chave Pública)
RSA
Curvas Elı́pticas
Baseado em Emparelhamentos
Cifragem de Dados
Algoritmos Simétricos (Chave secreta)
Triplo DES
AES
One-Time-Pad
OBS- Algoritmos simétricos são mais eficientes (computacionalmente
falando) para efetuar cifragem de dados que os assimétricos.
Maior simplicidade na implementação
baseados em operações lógicas simples, como, XOR, AND,
SHIFT, entre outras.
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
7 / 19
Introdução (Cont.)
Motivação: a busca por serviços de criptografia em tempo real está
relacionada diretamente com a busca por algoritmos cada vez mais
simples e seguros.
Algoritmo ideal: One-Time-Pad
Desafio: geração de números aleatórios
Proposta: Trivium
http://www.ecrypt.eu.org/stream/e2-trivium.html
Algoritmo extremamente eficiente em Hardware;
Utiliza sementes para gerar números aleatórios (chaves);
Estas chaves podem ser utilizadas na estrututa One-Time-Pad;
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
8 / 19
Trivium
Figure: Ideia do Trivium
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
9 / 19
Trivium (Cont.)
Parâmetros de entrada (sementes):
Chave (k) (80 bits);
Vetor inicial (IV) (80 bits).
Saı́da (Chave de Fluxo):
até 264 bits da chave de fluxo (Key Stream (KS)).
Os N bits da KS são derivados de IV, K e dos Estados Internos
(IS) do Trivium.
Os IS são 288 bits derivados a partir de IV, K e de PADDING’s,
distribuidos entre três registradores de 93, 84 e 111 bits,
respectivamente;
IS ← (s1 , s2 , · · · s288 ).
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
10 / 19
Trivium (Cont.)
Algoritmo: Geração Estados Internos(IV,K)
Entrada: IV, K.
Saı́da: Estados Internos (IS).
1: (s1 , s2 , · · · s93 ) ← (k1 , k2 , · · · k80 , 0, · · · , 0)
2: (s94 , s95 , · · · s177 ) ← (IV1 , IV2 , · · · IV80 , 0, · · · , 0)
3: (s178 , s179 , · · · s288 ) ← (0, 0, · · · 0, 0, 1, 1, 1)
4: for i = 1 to 4 · 288
5:
t1 ← s66 ⊕ (s91 s92 ) ⊕ s93 ⊕ s171
6:
t2 ← s162 ⊕ (s175 s176 ) ⊕ s177 ⊕ s264
7:
t3 ← s243 ⊕ (s286 s287 ) ⊕ s288 ⊕ s69
8:
(s1 , s2 , · · · s93 ) ← (t3 , s1 , s2 , · · · , s92 )
9:
(s94 , s95 , · · · s177 ) ← (t1 , s94 , s95 , · · · s176 )
10:
(s178 , s179 , · · · s288 ) ← (t2 , s178 , s179 , · · · s287 )
11: end for
12: return IS
: representa o operador lógido AND.
⊕: representa o operador lógido XOR.
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
11 / 19
Trivium (Cont.)
Algoritmo: Geração Chave Fluxo(IV,K) (bits)
Entrada: s1 , s2 , · · · s288
Saı́da: o bit zi da chave de fluxo.
1: for i = 1 to 264
2:
t1 ← s66 ⊕ s93
3:
t2 ← s162 ⊕ s177
4:
t3 ← s243 ⊕ s288
5:
zi ← t1 ⊕ t2 ⊕ t3
6:
t1 ← t1 ⊕ (s91 s92 ) ⊕ s171
7:
t2 ← t2 ⊕ (s175 s176 ) ⊕ s264
8:
t3 ← t3 ⊕ (s286 s287 ) ⊕ s69
9:
(s1 , s2 , · · · s93 ) ← (t3 , s1 , s2 , · · · , s92 )
10:
(s94 , s95 , · · · s177 ) ← (t1 , s94 , s95 , · · · s176 )
11:
(s178 , s179 , · · · s288 ) ← (t2 , s178 , s179 , · · · s287 )
12:
print(zi )
13: end for
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
12 / 19
Trivium (Cont.)
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
13 / 19
Trivium (Cont.)
Existem propostas de geradores de números aleatórios que
utilizam estruturas semelhantes a do Trivium
Trivium Toy
Utiliza três registradores de tamanho distintos, 31, 28 e 37 bits,
respectivamente.
Pode gerar até 264 bits da chave de fluxo.
IV, K: ?
Bivium-Toy
Utiliza dois registradores de tamanho distintos, 31 e 28 bits,
respectivamente.
Pode gerar até 264 bits da chave de fluxo.
IV, K: ?
Em ambas as variantes as propriedades matemática do Trivium
são preservadas.
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
14 / 19
Trivium (Cont.)
A qualidade de um gerador de números aleatórios está associada
diretamente ao comprimento do ciclo deste gerador.
Ciclo: a quantidade de números que pode ser gerada a partir de
determinada semente (sem repretição).
Uma forma de avaliar o comprimento do ciclo do gerador é a cada
saı́da, avaliar a correlação desta com as demais
Sendo todas derivadas da mesma semente.
O Trivium
Uma análise de ciclo possı́vel:
verificar a autocorrelação dos bits da chave de fluxo a cada IV e K
utilizados.
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
15 / 19
Ideia Central no Estudo do Trivium
Entender a forma como foi demonstrado o tamanho do ciclo do
Trivium;
Adaptar esta demonstração a medida que se possa utiliza-lá em
geradores aleatórios baseados em Autômatos Celulares.
https://scholar.google.com/citations?view_op=
view_citation&hl=en&user=aoiMfj8AAAAJ&citation_
for_view=aoiMfj8AAAAJ:u-x6o8ySG0sC
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
16 / 19
Autômatos Celulares
Autômatos Celulares Unidimensionais (AC)
Um AC pode ser associado a um vetor de n células (posições);
Inicialmente um vetor inicial possui todas as células com valor
zero, menos a célula central (valor um).
A cada evolução, este vetor inicial gera um novo vetor, onde cada
célula depende da vizinhança (células vizinhas) do vetor anterior.
Processo executado de forma iterativa.
A evolução dos autômatos ocorre de acordo com a regra
utilizada;
Existem 256 regras possı́veis (unidimencionais).
Regra escolhida: Regra 30.
Pode ser utilizada para geração de números aleatórios.
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
17 / 19
Autômatos Celulares
Figure: Evolução de um AC
Leandro Aparecido Sangalli
()
Prof. Dr. Marco Aurélio Amaral Henriques
March 2, 2015
18 / 19
Autômatos Celulares (Cont.)
Regra 30 A regra 30 é definida como:
xt+1
= xti−1 ⊕ (xti ∨ xti+1 )
i
onde, ∨ representa a operação lógica OU.
Exemplo: Observe a evolução do AC-30.
Vizinhança
Valor central (bit)
Leandro Aparecido Sangalli
000
0
001
1
010
1
011
1
100
1
()
Prof. Dr. Marco Aurélio Amaral Henriques
101
0
110
0
March 2, 2015
111
0
19 / 19