6.1.3. Traditional Pseudo-random Sequences (Séquences pseudo-aléatoires traditionnelles)

6.1.3. Traditional Pseudo-random Sequences (Séquences pseudo-aléatoires traditionnelles)

Cette section parle des sources traditionnelles de nombres déterministes ou "pseudo-aléatoires". Celles-ci commencent typiquement avec une quantité "graine" et utilisent des opérations numériques ou logiques simples pour produire une séquence de valeurs. Notez qu'aucune des techniques discutées dans cette section n'est adaptée à une utilisation cryptographique. Elles sont présentées pour information générale.

[KNUTH] a une exposition classique sur les nombres pseudo-aléatoires. Les applications qu'il mentionne sont les simulations de phénomènes naturels, l'échantillonnage, l'analyse numérique, le test de programmes informatiques, la prise de décision et les jeux. Aucune de ces applications n'a les mêmes caractéristiques que les types d'utilisations de sécurité dont nous parlons. Seulement dans les deux dernières pourrait-il y avoir un adversaire essayant de trouver la quantité aléatoire. Cependant, dans ces cas, l'adversaire n'a normalement qu'une seule chance d'utiliser une valeur devinée. En devinant des mots de passe ou en tentant de casser un schéma de chiffrement, l'adversaire a normalement de nombreuses chances, peut-être illimitées, de deviner la valeur correcte. Parfois, l'adversaire peut stocker le message à casser et l'attaquer à plusieurs reprises. Les adversaires sont également supposés être aidés par un ordinateur.

Pour tester "l'aléa" des nombres, Knuth suggère une variété de mesures, incluant statistiques et spectrales. Ces tests vérifient des choses comme l'autocorrélation entre différentes parties d'une séquence "aléatoire" ou la distribution de ses valeurs. Mais ces tests pourraient être satisfaits par une séquence aléatoire constante stockée, telle que la séquence "aléatoire" imprimée dans les CRC Standard Mathematical Tables [CRC]. Malgré la satisfaction de tous les tests suggérés par Knuth, cette séquence est inadaptée à une utilisation cryptographique, car les adversaires doivent être supposés avoir des copies de toutes les séquences "aléatoires" publiées communément et être capables de repérer la source et de prédire les valeurs futures.

Une technique typique de génération de nombres pseudo-aléatoires est le générateur de nombres pseudo-aléatoires à congruence linéaire. Cette technique utilise l'arithmétique modulaire, où la valeur numérotée N+1 est calculée à partir de la valeur numérotée N par

    V    = ( V  * a + b )(Mod c)
     N+1      N

La technique ci-dessus a une relation forte avec les générateurs de nombres pseudo-aléatoires à registre à décalage linéaire, qui sont bien compris cryptographiquement [SHIFT*]. Dans de tels générateurs, des bits sont introduits à une extrémité d'un registre à décalage comme le Ou Exclusif (somme binaire sans retenue) de bits à partir de prises fixes sélectionnées dans le registre. Par exemple, considérons ce qui suit:

  +----+     +----+     +----+                      +----+
  | B  | <-- | B  | <-- | B  | <--  . . . . . . <-- | B  | <-+
  |  0 |     |  1 |     |  2 |                      |  n |   |
  +----+     +----+     +----+                      +----+   |
    |                     |            |                     |
    |                     |            V                  +-----+
    |                     V            +----------------> |     |
    V                     +-----------------------------> | XOR |
    +---------------------------------------------------> |     |
                                                          +-----+

   V    = ( ( V  * 2 ) + B  XOR  B ... )(Mod 2^n)
    N+1         N         0       2

La qualité des algorithmes traditionnels de générateur de nombres pseudo-aléatoires est mesurée par des tests statistiques sur de telles séquences. Des valeurs a, b, c, et V initial soigneusement choisies ou un placement soigneusement choisi de la prise du registre à décalage dans le processus simple ci-dessus peuvent produire d'excellentes statistiques.

Ces séquences peuvent être adéquates dans les simulations (expériences de Monte Carlo) tant que la séquence est orthogonale à la structure de l'espace exploré. Même là, des motifs subtils peuvent causer des problèmes. Cependant, de telles séquences sont clairement mauvaises pour une utilisation dans les applications de sécurité. Elles sont entièrement prévisibles si l'état initial est connu. Selon la forme du générateur de nombres pseudo-aléatoires, la séquence peut être déterminable à partir de l'observation d'une courte portion de la séquence [SCHNEIER, STERN]. Par exemple, avec les générateurs ci-dessus, on peut déterminer V(n+1) étant donné la connaissance de V(n). En fait, il a été montré qu'avec ces techniques, même si seulement un bit des valeurs pseudo-aléatoires est libéré, la graine peut être déterminée à partir de courtes séquences.

Non seulement les générateurs à congruence linéaire ont été cassés, mais les techniques sont maintenant connues pour casser tous les générateurs à congruence polynomiale [KRAWCZYK].