Gerador de números aleatórios AVR

12

Eu li uma nota de aplicativo da TI ( slaa338 ) que descreve uma técnica para gerar números aleatórios "de verdade" (em oposição a "pseudo"). Ele explora o subsistema de relógio um tanto exótico do MSP430 para atingir esse objetivo. Alguém sabe de uma técnica que pode ser implementada em um AVR (estou interessado no XMega, em particular) para gerar números aleatórios "de verdade"?

vicatcu
fonte
1
aleatório psuedo funciona para jogos de dados. Eu acho que ele quer criptograficamente seguro.
Kortuk
2
Você pode dar uma dica sobre a aplicação e / ou o grau de aleatoriedade necessário? Se for para criptografia, há considerações adicionais além da qualidade da semente. Algumas das sugestões já feitas - como amostragem de entradas ambientais de vários tipos podem ou não ser apropriadas com base em seus requisitos.
Windell Oskay

Respostas:

6

Quão ruim você usa o XMega? Se a geração criptográfica e de números aleatórios é uma grande parte do seu projeto, a série SecureAVR da Atmel possui um número aleatório de hardware embutido e foi projetado para aplicativos criptográficos.

Independentemente disso, duvido que você encontre uma fonte de semente aleatória que tenha uma boa distribuição. Você desejará executá-lo através de um gerador de números pseudo-aleatórios algumas vezes. Desde que você comece com uma semente diferente a cada vez, isso fornecerá um bom conjunto de números aleatórios. Um LGC é um gerador pseudo-aleatório rápido e fácil:

static unsigned long Seed; 

/* Call before first use of NextVal */
unsigned long InitSeed()
{
   //Your code for random seed here

   // Correct distribution errors in seed
   NextVal();
   NextVal();
   NextVal();
   return NextVal();
}

 /* Linear Congruential Generator 
  * Constants from  
  * "Numerical Recipes in C" 
  * by way of 
   * <http://en.wikipedia.org/wiki/Linear_congruential_generator#LCGs_in_common_use>
   * Note: Secure implementations may want to get uncommon/new LCG values
  */
unsigned long NextVal()
{
  Seed=Seed*1664525L+1013904223L;
  return Seed;
} 
Kevin Vermeer
fonte
1
Isso é incrível, eu não sabia que a linha SecureAVR existia, obrigado pelo ponteiro!
vicatcu
BTW: Se você REALMENTE precisa de segurança, o método LCG simples, eficaz e rápido que apresentei não é o que você deseja: Muitos LCGs podem ser quebrados; basta obter 2-3 valores seguidos e conectá-los a um gerador LCG com um conjunto de constantes conhecidas - isso incluiria tudo na página da Wikipedia. Um padrão de correspondência permitirá que o invasor preveja qual será o próximo número. É possível (mas mais difícil) descobrir quais são as constantes do nada também.
22610 Kevin Vermeer
1
@reemrevnivek FYI, a Atmel está vendendo sua linha SecureAVR ... eles recomendam seus processadores de 32 bits baseados em ARM se você quiser coisas criptográficas que são um jogo completamente diferente em termos de ambiente de desenvolvimento para o AVR. No entanto, eles têm um casal com RNGs verdadeiros, talvez eu possa brincar com eles algum dia.
vicatcu
7

Conecte o ADC a uma fonte de ruído de hardware e use o software para "embranquecer" os números aleatórios, se necessário.

Aqui está um projeto baseado em AVR que faz isso: Mini Gerador de Número Aleatório Portátil de Leon (mPRNG)

Dependendo da segurança criptográfica necessária, você pode usar o ruído de uma entrada analógica aterrada ou o " sensor interno de temperatura " como sua semente de aleatoriedade, em vez de hardware externo.

Atualização : Mais tarde, escrevi um programa para o Arduino que usa os temporizadores do chip como fonte de entropia (o ADC acabou sendo inútil porque os bits ruidosos são truncados) e isso inspirou a criação da biblioteca Entropy .

Nos dois casos, a aleatoriedade não é, por exemplo, o valor da temperatura em si, que muda apenas lentamente, mas dos bits menos significativos , que variam aleatoriamente de uma leitura para a seguinte. Eu li o valor várias vezes, uma vez para cada bit de saída, deslocamento de bits e XOR na leitura anterior. XORing um bit verdadeiramente aleatório com um bit não correlacionado preserva a aleatoriedade , para que a aleatoriedade se espalhe por todos os bits e se torne um verdadeiro ruído branco. Porém, sua taxa de bits não será muito alta, pois você obtém apenas um bit de saída por tempo de aquisição ou ciclo do temporizador. Com o método do timer, eu estava obtendo cerca de 64 bits / s.

endólito
fonte
5
Nomear um RNG (mais ou menos verdadeiro), "-PRNG" é lamentável.
Nick T
+1 para o ADC, acho que você provavelmente está procurando algo que muda com uma frequência mais alta do que um sensor de temperatura.
Octopus
1
@ Octopus Bem, você não está usando a temperatura como fonte de entropia, está usando os bits menos significativos, que mudam aleatoriamente toda vez que você lê o ADC, mesmo que a temperatura seja constante. No entanto, quando testei no Arduino, esses bits sempre eram 0, então não era possível e tive que usar a variação do temporizador. Em outro MCU em que usei esse método, os LSBs do ADC eram barulhentos e utilizáveis.
endolith
3

Outro truque para gerar uma semente aleatória é contar o número de ciclos de relógio até um evento externo. Por exemplo, se este é um dispositivo a ser usado por uma pessoa, conte o número de ciclos de relógio até que ele pressione o botão 'ir' e use-o como a semente aleatória.

davr
fonte
4
Isso pode não ser muito seguro contra ataques de canal lateral, pois eles podem interromper o controle de um dispositivo, mas, como em toda criptografia, o aplicativo determina a viabilidade.
Kortuk
3

Para ter certeza de não reiniciar com a mesma sequência, eu uso somme byte no eeprom:

#include <avr/eeprom.h>
#include <stdlib.h> // rand

u16  EEMEM randinit; 

int main(void) {
        srand(eeprom_read_word(&randinit));
        eeprom_write_word(&randinit,rand());
        [...]
 }

Isso dá um bom aleatório e não custa muito em programa / memória.

jojo l'abricot
fonte
2
Isso lê byte 0 todas as vezes. Que evidência você tem de que esse byte é aleatório? Se for, essa é uma ótima técnica!
Kevin Vermeer
Esta palavra (byte 0 e 1 de fato) será aleatória, porque a cada inicialização eu inicializo o gerador aleatório com seu conteúdo. ENTÃO carrego-o com um novo rand (). Portanto, o próximo init parecerá aleatório em relação ao atual ... e assim por diante ... Mas se eu redefinir randinit para ffff (ou 0000?), Terei a mesma sequência randinit! Portanto, não é perfeito. Esqueci um aviso sobre o fusível que apagar o eeprom ao carregar o .hex *;)
jojo l'abricot
3

Eu criei uma biblioteca que, embora o original projetado para o Arduino funcione bem como uma classe em uma implementação de C ++ usando g ++ no avr, de fato ele também foi portado recentemente para a arquitetura ARM.

Utiliza a instabilidade entre o cronômetro do watchdog e o relógio do sistema e foi testado em vários chips diferentes (documentados na página da wiki)

http://code.google.com/p/avr-hardware-random-number-generation/wiki/WikiAVRentropy

Walter Anderson
fonte
2

Você já olhou para usar algo como randomSeed () ? - usado no IDE do Arduino

Você pode usar esta função para testar um pino analógico flutuante (gratuito) no atmel AVR e, em seguida, usa o valor para criar um ponto de partida arbitrário para a função de número pseudo- aleatório - random ().

O valor criado por random () pode ser um número pseudo-aleatório - mas o ponto de partida arbitrário criado por randomSeed () deve ser o número / valor aleatório mais real possível.

Jim
fonte
2
A amostragem de coisas como os pinos analógicos é quase aleatória, mas não terá uma distribuição uniforme. Execute a semente aleatoriamente algumas vezes, no entanto, e assim será.
22610 Kevin Vermeer
.... através de um gerador de números pseudo-aleatórios um par ... <- Como isso desapareceu? NTS: envolva o cérebro primeiro, depois os dedos.
22610 Kevin Vermeer
Exatamente - também não é o mais seguro se você o usar para criptografia / proteção, etc., mas fornecerá um bom número aleatório para algo como música generativa ou jogos de dados. É bom e fácil de implementar também :)
Jim
1

Há um artigo sobre como conseguir isso com o hardware AVR. Envolve confiar no jitter do relógio. Basicamente, você usa uma interrupção do timer com base em uma fonte de relógio para amostrar os bits mais baixos de um timer separado, com o clock de uma fonte de relógio independente separada. Os dois relógios terão algum tremor aleatório associado a eles e a amostragem não será perfeitamente periódica.

Eu fiz uma pequena prova de conceito disso em um microcontrolador STM32, o código está no github aqui . Obteve alguns bons resultados com base em um conjunto de conjuntos de testes de randomização.

Na minha opinião, acho que isso é melhor do que amostrar um pino flutuante com um ADC que é extremamente fácil de atacar (amarre o pino no chão e seu número não será mais tão aleatório!). Tenho certeza de que existe uma maneira de manipular um RNG baseado em jitter de clock, mas me sinto um pouco melhor por poder fazer isso puramente com base em fontes de clock interno no chip.

Jon L
fonte