English Version À esquerda, a versão final feita em uma placa de circuito impresso face simples. À direita, o protótipo em uma placa universal. Esquema (clique para ampliar) O gerador em ação

T12RNG

O T12RNG é um gerador de números aleatórios em hardware que se conecta à porta serial comum do PC. É um dispositivo simples, compacto e de baixíssimo custo que usa o microcontrolador ATTiny12 da Atmel e um gerador de ruído branco baseado nas propriedades quânticas dos semicondutores.

Recursos

• Compacto, menos de 3x3cm
• Conecta-se ao conector serial D-Sub9 comum na maioria dos PCs.
• Alimentado pela porta serial, dispensa baterias
• Baixíssimo custo, menos de R$ 25 em componentes
• Velocidade média de geração: 60 bytes aleatórios por segundo
• Protocolo trivial: dígitos hexadecimais transmitidos a 1200bps 8N1 -- suportado por qualquer emulador de terminal

Aplicações

Eu originalmente desenvolvi o T12RNG para criar material criptográfico realmente imprevisível para senhas, chaves criptográficas, one-time pads, etc. Esta página descreve os testes que eu executie para me convencer de que ele seria adequado para meus propósitos. Contudo, não afirmo ser um especialista em criptografia, geração de números aleatórios nem estatística. Se você quiser usar esse dispositivo para algo importante, não deixe de projetar e conduzir seus próprios testes.

A taxa de geração de 60 bytes/seg do T12RNG pode ser lenta demais para certas aplicações, tal como integração Monte-Carlo. Se é isso que você está tentando fazer, talvez você deva procurar geradores de números pseudo-aleatórios rápidos em software, tal como o Mersenne Twister.

O T12RNG pode ser usado para inicializar ou periodicamente embaralhar o estado de algum outro PRNG tal como o ISAAC para obter seqüências aleatórias extremamente imprevisíveis de forma rápida.

Por outro lado, ele pode ser rápido demais em certos casos -- 60 bytes/segundo é quase 5MB/dia. Se você só precisa de alguns bytes aleatórios vez por outra, descarte todo o resto.

Motivação

Estou transformado meu já antiquado iPaq H3650 em um tipo de dispositivo critpográfico para certas aplicações especializadas. Acontece que o armazenamento primário dele é em memória flash e ele será usado em uma situação onde ele não receberá praticamente nenhuma entrada do mundo exterior, de sorte que a coleta de entropia desse dispositivos será muito baixa. Isso o torna um alvo ideal para os ataques descritos no artigo paper e tese de mestrado do Tzachy Reinman.

O Circuito

Eu queria tornar o circuito tão simples e com a menor quantidade de componentes quanto possível. Usei o oscilador RC de 1.2MHz embutido do microcontrolador como fonte do clock para dispensar o cristal externo e seus capacitores. Pela mesma razão eu fiz a comunicação unidirecional: não há circuito para receber dados do computador; há apenas o transmissor, o que significa que não há opções de configuração nem possibilidade de upgrade de firmware automática.

A maior parte do circuito é apenas um "copiar e colar" de várias idéias de outros circuitos que eu achei na Internet.

Dois truques importantes vieram do projeto do Multímetro Digital baseado no AVR do Murray Greenman: o método de obter a alimentação das linhas RTS e DTR da porta serial usando diodos e a idéia de usar a voltagem negativa "mark" do sinal TX para impulsionar o RX quando quisermos transmitir "uns".

O gerador de ruído branco veio da página do Aaron Logue, exceto por pequenas alterações que eu fiz nos valores de alguns resistores para centrar o sinal ao redor de 1.1V, que é a tensão de referência do comparador analógico embutido do microcontrolador.

Para poder gerar um efeito avalanche devente, precisamos de pelo menos 12V entre os transistores Q3 e Q4. Para obter isso, eu os liguei ao RX e TX, dado que em portas seriais típicas o TX normalmente fica abaixo de -6V e o RX fica acima de +6V. O dispositivo pode não funcionar direito se sua porta serial não provir pelo menos essas voltagens, como é o caso de certas seriais de notebooks.

O resto é apenas amplificar o sinal com Q5 e centrar o sinal. Assim, a saída do comparador analógico deve ser um bit aleatório dançando ao som do rúido branco.

O software no sistema operacional deve subir as linhas DTR e RTS ao abrir a porta serial -- doutra feita, o circuito não ligará. Baixar essas linhas desliga o circuito, economizando os cerca de 5 miliampères que o circuito consome.

O circuito na figura não tem o conector de programação ISP necessário para subir o programa para a memória flash do microcontrolador. Assume-se que você já tenha um programador ou placa de avaliação capaz disso. O pacote ZIP anexo tem uma versão do circuito que tem esse conector. O dispositivo à esquerda na figura é o protótipo que eu construi -- esse sim com o conector de programação. Eu o tirei na versão final da placa de circuito impresso para torná-lo fisicamente menor. Pode-se torná-lo ainda menor usando componentes SMD.

O Firmware

O firmware obtém amostragens da saída do comparador analógico 9600 vezes por segundo. Se a fonte for verdadeiramente aleatória e a média do nível do sinal for exatamente a voltagem de referência, isso deveria teoricamente nos dar bits aleatórios puros com uma proporção de 50-50% de uns e zeros. Contudo, por causa da tolerância dos componentes, variações de temperatura e outras imperfeições, essa proporção provavelmente terá um viés mais para um lado do que o outro.

Por causa disso, os bits aleatórios são passados por algoritmo de "remoção de viés" inventado por Von Neumann: eles são agrupados em pares e se forem iguais, nós os descartamos. Caso contrário, o último é inserido em um registrador de deslocamento. Esse processo é repetido até obtermos um byte inteiro.

Qualquer bom livro de teoria da informação ou criptografia explica por que esse processo remove o viés, ajeitando a propoção para quase exatamente 50-50% independente de qual o fosse o viés original. Um efeito colaterial é que esse processo diminui a taxa de saída média por um fator de quatro, de sorte que deveríamos estar obtendo cerca de 2400 bits (300 bytes) por segundo. Pode ser muito menos que isso se o viés original for muito forte, digamos, 75-25% ou 90-10%. Mesmo com um viés decentementen baixo, ainda assim é possível obtermos uma seqüência incomumente longa de apenas zeros ou apenas uns, apesar da chace disso acontecer se torna muito pequena à medida em que o comprimento da seqüência aumenta.

O byte aleatorio então é misturada com o item atual em um buffer circular e o próximo item torna-se o atual. Na primeira versão do firmware, a função de mistura era apenas um XOR. Contudo, isso fez com que o gerador passasse nos testes estatísticos em certos computadores mas não em outros. Ao tentar bolar uma contramedida, decidi experimentar com uma função de mistura mais complexa envolvendo adições e o valor do timer. Apesar de ser uma espécie de "abracadabra" sem um suporte teórico lá muito firme, os resultados passaram todos os testes estatísticos em todos os computadores em que testei. Vai entender.

O processo de transmissão roda simultaneamente com o de amostragem. Um byte é removido do buffer circular, convertido para dois dígitos hexademais e transmitidos por uma 'UART em software', uma vez que o ATTiny12 não tem uma UART embutida em hardware. Essa UART em software apneas transmite o bit de partida, os bits de ados e o bit de parada nos instantes apropriados a 1/8 da taxa de amostragem. Em outras palavras, os dados são transmitidos a 1200bps, 8 bits, sem paridade, com um bit de parada. Isso nos dá 120 dígitos hexadecimais ou 60 bytes aleatórios por segundo.

A cada 78 dígitos uma quebra de linha (CRLF ou "\r\n") é inserida para tornar o resultado bonitinho no emulador de terminal.

Uma vez que o processo de transmissão acontece concomitantemente com o de amostragem/remoção de viés/mistura, é importante que os bits sejam gerados mais rápido do que os transmitimos. Como vimos, a velocidade de transmissão é fixa, mas a geração é quase sempre muito mais rápida. Frequentemente a posição inserção ultrapassa a posição de transmissão. Contudo, também vimos acima que não há garantias que isso aconteça sempre.

Por exemplo, o efeito avalanche diminui com a temperatura. Isso poderia reduzir a taxa de geração a um ponto que que ele se torna consistentemente mais lento que a taxa de transmissão. Por causa disso, impelementei uma precaução adicional: há um outro buffer de 10 nibbles (5 bytes) que conta quantas vezes cada item do buffer circular foi misturado. Nós não transmitimos um byte se esse contador for zero; nesse caso, transmitimos dois traços para dar ao gerador tempo de se recuperar. Por outro lado, se o contador for diferente de zero, nós transmitimos o byte aleatório correspondente e zeramos o contador. Em outras palavras, o firmware verifica se o gerador está atrasado em relação ao transmissor e transmite traços quando ele precisa de tempo para se recuperar.

Essa precaução evita que o dispositivo falhe silenciosamente. Digamos que após milhares de horas de funcionamento normal, um dos transistores 2N3904 do gerador pife (improvável, mas possível). Ou que você o inseriu com força o bastante para fazer uma das perninhas forçar a solda a pular da placa (isso aconteceu comigo uma vez -- é por isso que na foto você vê essa seção coberta com cola de silicone). Isso faria com que o dispositivo ficasse eternamente repetindo os dez últimos bytes porque o transmissor continuaria rodando mas o gerador estaria parado porque o algoritmo de Von Neumann descartaria todos os zeros.

Com essa precaução, o gerador simplesmente começaria a transmitir traços sem parar. O software no computador poderia tratar esse caso gerando um alarme se ele não receber nada além de traços durante um certo tempo, digamos, um segundo ou dois. Receber alguns traços de vez em quanto, digamos, menos de oito, é normal -- isso é quando o gerador se atrasa em relação ao transmissor.

Quando o dispositivo é iniciado, o buffer está vazio e ele ficaria transmitindo traços até o gerador ultrapassar o transmissor. Isso é evitado transmitindo-se uma saudação de abertura com a versão do firmware e a mensagem de direitos autorais.

Testes

Para os testes iniciais, pensei em em usar o programa ent do John Walker. Ele computa alguns testes estatísticos para determinar se a seqüência de números parece aleatória ou não, tais como média, entropia, qui-quadrado, correlação serial, etc. Veja a página dele para explicações do que tudo isso significa e algumas referências úteis.

O problema é que o ent opera em arquivos compeltos; impaciente que sou, não queria esperar várias horas para coletar números o bastante para o teste simplesmente para ver que o resultado foi ruim. Eu queria ver como ele se comporta ao longo do tempo, dando uma olhada de vez em quando nas estatísticas enquanto eu fazia outras coisas.

Então escrevi um script em perl baseado no ent que computa as estatíscias à medida em que são lidas da porta serial, mostando os resultados parciais uma vez por segundo. Acrescentei algumas outras estatísticas e troquei a reprsentação de algumas outras: ao invés de mostrar os valores em si, o programa mostra o desvio em relação aos valores ideais. Eu não incluí o cálculo de Pi pelo método Monte-Carlo porque ele converge lento demais.

Eu reescrevi a maior parte desse programa em C para realizar outra função: ele acumula 10KB de dados aleatórios do gerador e os testa. Se passarem por certos critérios de qualidade, eles são acrescentados a uma fila de "bytes aprovados". Essa fila é inserida no reservatório de entropia do cerne do Linux via o dispositivo /dev/random, com o cuidado de fazê-lo à mesma velocidade que os dados são aprovados, de sorte a nunca esvaziar a fila. Fazer isso não resolve todas as vulerabilidades descritas no trabalho do Reinman, mas pode ser o bastante para várias aplicações.

Licenciamento

Esse projeto é disponibilizado nos termos de uma licença do Creative Commons. Por favor leia:

• http://creativecommons.org/licenses/by-nc-sa/2.5/deed.pt

Downloads

• t12rng-v2.zip: Pacote com o software, esquema do hardware e layout da placa de circuito impresso

topo