Obtendo um número verdadeiramente aleatório no Arduino

13

Qual é o melhor método para obter um número aleatório verdadeiramente (em oposição ao pseudo) no Arduino, ou pelo menos a melhor aproximação possível? Pelo meu entendimento, a função randomSeed (analogRead (x)) não é aleatória o suficiente.

Se possível, o método deve aproveitar sozinho a configuração básica do Arduino (sem sensores adicionais). Soluções com sensores externos são bem-vindas se melhorarem significativamente a aleatoriedade em relação à configuração básica.

Rexcirus
fonte
Qual é a aplicação? Deve ser criptograficamente seguro? O que você está fazendo com a aleatoriedade então? Então, sem um chip externo implementando um TRNG a partir de uma fonte de entropia física, você estará sem sorte. Você também pode implementar um RNG determinístico como um HMAC DRBG e semeá-lo de algo estático, mais uma fonte de entropia de baixa qualidade, mas que ainda não será criptograficamente seguro.
Maximilian Gerhardt 12/03
Sim, preciso de números aleatórios para aplicativos criptograficamente seguros.
Rexcirus 12/0318

Respostas:

10

A biblioteca do Entropy usa:

o jitter natural do timer do watchdog para produzir um fluxo confiável de números aleatórios verdadeiros

Eu gosto dessa solução porque ela não usa pinos do seu microcontrolador e não requer circuitos externos. Isso também o torna menos sujeito a falhas externas.

Além de uma biblioteca, eles também fornecem um esboço que demonstra o uso da mesma técnica usada para gerar uma semente aleatória para o PRNG do microcontrolador sem a biblioteca: https://sites.google.com/site/astudyofentropy/project-definition / timer-jitter-entropy-sources / biblioteca de entropia / arduino-random-seed

per1234
fonte
8

randomSeed(analogRead(x))produzirá apenas 255 seqüências de números, o que torna trivial tentar todos os combos e produzir um oráculo que possa acoplar ao seu fluxo de saída, prevendo 100% da saída. Você está no caminho certo, porém, é apenas um jogo de números e precisa de muito mais deles. Por exemplo, fazer 100 leituras analógicas de 4 ADCs, resumindo todas elas e alimentando isso randomSeedseria muito melhor. Para segurança máxima, você precisa de entradas imprevisíveis e mixagens não determinísticas.

Não sou um criptógrafo, mas passei milhares de horas pesquisando e construindo geradores aleatórios de hardware e software, então deixe-me compartilhar um pouco do que aprendi:

Entrada imprevisível:

  • analogRead () (em pinos flutuantes)
  • GetTemp ()

Entrada potencialmente imprevisível:

  • micros () (com um período de amostra não determinístico)
  • tremulação do relógio (largura de banda baixa, mas utilizável)
  • readVCC () (se não for alimentado por bateria)

Entrada imprevisível externa:

  • sensores de temperatura, umidade e pressão
  • microfones
  • Divisores de tensão LDR
  • ruído de transistor com polaridade inversa
  • tremulação da bússola / aceleração
  • varredura do ponto de acesso wifi esp8266 (ssid, db, etc)
  • tempo esp8266 (as tarefas wifi em segundo plano tornam os micros () buscados indeterminados)
  • esp8266 HWRNG - RANDOM_REG32extremamente rápido e imprevisível, uma parada

coletando A última coisa que você quer fazer é cuspir a entropia como ela aparece. É mais fácil adivinhar um lançamento de moeda do que um balde de moedas. A soma é boa. unsigned long bank;depois bank+= thisSample;é bom; vai rolar. bank[32]é ainda melhor, continue a ler. Você deseja coletar pelo menos 8 amostras de entrada para cada parte da saída, idealmente muito mais.

Protegendo contra envenenamento Se o aquecimento da prancha causar um certo jitter máximo de clock, esse é um vetor de ataque. O mesmo ocorre com o jateamento de RFI nas entradas analogRead (). Outro ataque comum simplesmente desconectou a unidade, despejando toda a entropia acumulada. Você não deve produzir números até saber que é seguro fazê-lo, mesmo ao custo da velocidade.

É por isso que você quer manter alguma entropia em torno de longo prazo, utilizando EEPROM, SD, etc Olhe para a Fortuna PRNG , que usa 32 bancos, cada um atualizados metade tão frequentemente quanto o anterior. Isso dificulta o ataque a todos os 32 bancos em um período de tempo razoável.

Processamento Depois de coletar a "entropia", é necessário limpá-la e separá-la da entrada de uma maneira difícil de reverter. SHA / 1/256 é bom para isso. Você pode usar o SHA1 (ou até mesmo o MD5) para obter velocidade, pois não possui uma vulnerabilidade em texto sem formatação. Para colher, nunca use o banco de entopia completo e SEMPRE adicione um "sal" à saída que é diferente a cada vez para evitar saídas idênticas, sem alterações no banco de entropia: output = sha1( String(micros()) + String(bank[0]) + [...] );a função sha oculta as entradas e clareia a saída, protegendo contra sementes fracas, baixo nível de acúmulo acumulado e outros problemas comuns.

Para usar as entradas do timer, você precisa torná-las indeterministas. Este é um simples como delayMicroseconds(lastSample % 255); que pausa uma quantidade imprevisível de tempo, tornando o relógio "sucessivo" com uma diferença não uniforme. Faça isso de forma semi-regular, if(analogRead(A1)>200){...}desde que A1 seja barulhento ou conectado a uma entrada dinâmica. Tornar cada bifurcação do seu fluxo bastante difícil de determinar impedirá a criptoanálise na saída descompilada / rasgada.

A verdadeira segurança é quando o invasor conhece todo o sistema e ainda não consegue superá-lo.

Por fim, verifique seu trabalho. Execute sua saída através do ENT.EXE (também disponível para nix / mac) e veja se é bom. O mais importante é a distribuição do qui quadrado, que geralmente deve estar entre 33% e 66%. Se você receber 1,43% ou 99,999% ou algo do tipo, mais de um teste consecutivo, sua aleatória é uma porcaria. Você também deseja que os relatórios ENT da entropia sejam o mais próximo possível de 8 bits por byte,> 7,9, com certeza.

TLDR: A maneira mais simples e segura de enganar é o HWRNG do ESP8266. É rápido, uniforme e imprevisível. Execute algo assim em um ESP8266 executando o núcleo do Ardunio e use o serial para conversar com o AVR:

// ESP8266 Arduino core code:
void setup(){
 Serial.begin(9600); // or whatever
}

void loop() {
  // Serial.write((char)(RANDOM_REG32 % 256)); // "bin"
  Serial.print( String(RANDOM_REG32, HEX).substring(1)); // "hex"
}

** editar

aqui está um esboço de HWRNG que escrevi há algum tempo, operando não apenas como um coletor, mas como um CSPRNG inteiro saindo da porta serial. Ele foi desenvolvido para um profissional, mas deve ser facilmente adaptável a outras placas. Você pode usar apenas pinos analógicos flutuantes, mas é melhor adicionar itens a eles, de preferência coisas diferentes. Como microfones, LDRs, termistores (aparados ao máximo na temperatura ambiente) e até fios longos. Faz muito bem em ENT se você tiver um ruído moderado.

O esboço integra várias noções que mencionei na minha resposta e nos comentários seguintes: acumular entropia, esticar por sobre-amostrar uma entropia abaixo do ideal (von neumann disse que é legal) e buscar uniformidade. Ele renuncia à estimativa da qualidade da entropia em favor de "me dê qualquer coisa possivelmente dinâmica" e à mistura usando um primitivo criptográfico.

// AVR (ardunio) HWRNG by dandavis. released to public domain by author.
#include <Hash.h> 

unsigned long read[8] = {0, 0, 0, 0, 0, 0, 0, 0};
const int pincount = 9; // adjust down for non pro-mini boards
int pins[9] = {A0, A1, A2, A3, A4, A5, A6, A7, A0}; // adjust for board, name analog inputs to be sampled
unsigned int ticks = 0;
String buff = ""; // holds one round of derivation tokens to be hashed.
String cache; // the last read hash



void harvest() { // String() slows down the processing, making micros() calls harder to recreate
  unsigned long tot = 0; // the total of all analog reads
  buff = String(random(2147483647)) + String(millis() % 999);
  int seed =  random(256) + (micros() % 32);
  int offset =  random(2147483647) % 256;

  for (int i = 0; i < 8; i++) {
    buff += String( seed + read[i] + i + (ticks % 65), HEX );
    buff += String(random(2147483647), HEX);
    tot += read[i];
  }//next i

  buff += String( (micros() + ticks + offset) % 99999, HEX);
  if (random(10) < 3) randomSeed(tot + random(2147483647) + micros()); 
  buff = sha1( String(random(2147483647)) + buff + (micros()%64) + cache); // used hash to uniform output and waste time
  Serial.print( buff ); // output the hash
  cache = buff;
  spin();
}//end harvest()


void spin() { // add entropy and mix
  ticks++;
  int sample = 128;
  for (int i = 0; i < 8; i++) { // update ~6/8 banks 8 times
    read[ read[i] % 8] += (micros() % 128);
    sample = analogRead(  pins[i] ); // a read from each analog pin
    read[ micros() % 8] += ( read[i] % 64 ); // mix timing and 6LSBs from read
    read[i] += sample; // mix whole raw sample
    read[(i + 1) % 8] += random(2147483647) % 1024; // mix prng
    read[ticks % 8] += sample % 16; // mix the best nibble of the read
    read[sample % 8] += read[ticks % 8] % 2147483647; // intra-mix banks
  }

}//end spin()



void setup() {
  Serial.begin(9600);
  delay(222);
  int mx = 2028 + ((analogRead(A0)  + analogRead(A1) + analogRead(A2)  + analogRead(A3)) % 256);  
  while (ticks < mx) {
    spin();
    delay(1);
    randomSeed(read[2] + read[1] + read[0] + micros() + random(4096) + ticks);
  }// wend
}// end setup()



void loop() {
  spin();
  delayMicroseconds((read[ micros() % 8] %  2048) + 333  );
  delay(random(10));
  //if (millis() < 500) return;
  if ((ticks % 16) == (millis() % 16) ) harvest();
}// end loop()
dandavis
fonte
(Estou com falta de caracteres aqui, desculpe.) Boa visão geral! Eu sugeriria usar um contador para o sal; micros () é um desperdício de bits, pois pode pular várias etapas entre as chamadas. Evite os bits altos nas entradas analógicas, restrinja-os aos um ou dois bits mais baixos. Mesmo com um ataque direcionado, é difícil identificá-lo (a menos que você possa colocar um fio na entrada). "Mistura não determinística" não é algo que você pode fazer em software. A mistura SHA-1 é padronizada: crypto.stackexchange.com/a/6232 . O indet. O cronômetro que você propõe é tão aleatório quanto a fonte que você já possui. Não há muito ganho aqui.
Jonas Schäfer
O sha simplifica e protege, para que você não precise se preocupar com quantos bits obter de uma entrada analógica, por exemplo. alguns centímetros de fio conectado a um analógico (ou um rastro de serpentina de PCB) o balançam mais do que alguns bits. a mistura é não determinística em virtude do sal não salvo e desconhecido alimentado ao hash com uma subamostra de valores acumulados. micros () é mais difícil de reproduzir do que um contador, especialmente quando disparado em intervalos não determinísticos.
dandavis
1
Eu tenho uma pergunta. Você disse que tomar 100 medidas é melhor. Mas tomar muitas medidas não é uma espécie de "média" que limita a eficácia de obter esses dados "aleatórios"? Quero dizer, normalmente você média para obter menos ruidoso (por isso menos "aleatório") medições ...
frarugi87
bem, eu recomendo amostragem constante, eu estava dizendo apenas 100 é melhor que 1, pois oferece mais combinações. Um modelo de acumulação como Yarrow / Fortuna ainda é muito melhor. Considere concatenar (sem somar) essas 100 amostras analógicas antes do hash; mais forte porque torna a ordem das amostras importante, e ser um char produz um hash totalmente diferente. Portanto, mesmo que se possa calcular a média das amostras para obter menos ruído, um invasor precisaria recitar literalmente todos os valores ou nenhuma correspondência ... Meu ponto principal é "acumular, misturar e verificar" mais do que advogar uma fonte específica de ruído.
dandavis
4

Da minha experiência, analogRead()em um pino flutuante tem entropia muito baixa. Talvez um ou dois bits de aleatoriedade por chamada. Você definitivamente quer algo melhor. A instabilidade do cronômetro de vigilância, como proposto na resposta de per1234, é uma boa alternativa. No entanto, gera entropia a uma taxa bastante lenta, o que pode ser um problema se você precisar exatamente quando o programa for iniciado. O dandavis tem algumas boas sugestões, mas geralmente requerem um ESP8266 ou hardware externo.

Há uma fonte interessante de entropia que ainda não foi mencionada: o conteúdo da RAM não inicializada. Quando o MCU é ligado, alguns de seus bits de RAM (aqueles que possuem os transistores mais simétricos) são iniciados em um estado aleatório. Conforme discutido neste artigo , este pode ser usado como uma fonte de entropia. Ele está disponível apenas em uma inicialização a frio, portanto, você pode usá-lo para preencher um pool de entropia inicial, que seria reabastecido periodicamente de outra fonte potencialmente lenta. Dessa forma, seu programa pode iniciar seu trabalho sem precisar esperar que a piscina se encha lentamente.

Aqui está um exemplo de como isso pode ser obtido em um Arduino baseado em AVR. O trecho de código abaixo de XORs toda a RAM, a fim de construir uma semente que alimenta mais tarde srandom(). A parte complicada é que a coleta precisa ser feita antes que o tempo de execução C inicialize as seções de memória .data e .bss e, em seguida, a semente precisa ser salva em um local que o tempo de execução C não substitua. Isso é feito usando seções específicas da memória .

uint32_t __attribute__((section(".noinit"))) random_seed;

void __attribute__((naked, section(".init3"))) seed_from_ram()
{
    const uint32_t * const ramstart = (uint32_t *) RAMSTART;
    const uint32_t * const ramend   = (uint32_t *) RAMEND;
    uint32_t seed = 0;
    for (const uint32_t *p = ramstart; p <= ramend; p++)
        seed ^= *p;
    random_seed = seed;
}

void setup()
{
    srandom(random_seed);
}

Observe que, em uma redefinição a quente , a SRAM é preservada, portanto ainda possui todo o conteúdo do seu conjunto de entropia. Esse mesmo código pode ser usado para preservar a entropia coletada em uma redefinição.

Edit : corrigido um problema na minha versão inicial do seed_from_ram()que funcionava no global em random_seedvez de usar um local seed. Isso poderia levar a semente a ser XORed com ela mesma, destruindo toda a entropia colhida até agora.

Edgar Bonet
fonte
Bom trabalho! posso roubar? re: pins: um ou dois bits de desconhecido são suficientes se utilizados corretamente; que só iria limitar a velocidade de perfeita sigilo (eca) de saída, mas não o sigilo computacional precisamos ...
dandavis
1
@dandavis: Sim, você pode reutilizar, com certeza. Você tem razão em analogRead()ser utilizável se souber o que está fazendo. Você só precisa ter cuidado para não superestimar sua aleatoriedade ao atualizar uma estimativa da entropia da sua piscina. Meu ponto sobre analogRead()é principalmente significava como uma crítica de um pobre, mas muitas vezes repetida “receita” : randomSeed(analogRead(0)) apenas uma vez em setup()e assumir que é o suficiente.
Edgar Bonet
Se analogRead(0)houver 1 bit de entropia por chamada, a chamada repetida produzirá 10000/8 = 1,25 KBytes / s de entropia, 150 vezes mais que a biblioteca de entropia.
Dmitry Grigoryev
0

Se você realmente não precisa de entropia e simplesmente deseja obter uma sequência diferente de números pseudo-aleatórios em cada inicialização, você pode usar a EEPROM para iterar através de sementes consecutivas. Tecnicamente, o processo será completamente determinístico, mas em termos práticos é muito melhor do que randomSeed(analogRead(0))em um pino desconectado, o que geralmente fará com que você comece com a mesma semente de 0 ou 1023. Salvar a próxima semente na EEPROM garantirá que você comece com uma diferente semeie cada vez.

#include <EEPROM.h>

const int seed_addr = 0;
unsigned long seed;

void setup() {
    seed = EEPROM.read(seed_addr);
    EEPROM.write(seed_addr, seed+1);
    randomSeed(seed);
}

Se você precisar de entropia real, poderá coletá-la usando o desvio do relógio ou amplificando o ruído externo. E se você precisar de muita entropia, o ruído externo é a única opção viável. O diodo Zener é uma escolha popular, especialmente se você tiver uma fonte de tensão acima de 5-6V (ele funcionará com 5V também com um diodo Zener apropriado, mas produzirá menos entropia):

insira a descrição da imagem aqui

( fonte ).

A saída do amplificador deve ser conectada a um pino analógico, que produzirá vários bits de entropia com cada analogRead()um até dezenas de MHz (mais rápido do que o Arduino pode amostrar).

Dmitry Grigoryev
fonte