Random.self_init

Maintenant que je travaille un peu dans le domaine de la sécurité, je pense notamment aux générateurs de nombres aléatoires. Après quelques lectures sur le sujet, je me suis demandé comment fonctionnait le module Random de Caml.

Il y a sûrement beaucoup de choses à dire, mais mon attention a été retenue par un truc simple: self_init initialise le générateur de façon très simple, à partir de l'heure et de l'identifiant du processus, données pour le moins aléatoires. Il faut donc vraiment se méfier de cela si on souhaite utiliser le module Random à des fins cryptographiques. En pratique, le petit bout de code suivant devine assez rapidement la graine générée, en supposant connu l'identifiant du processus (ce n'est pas bien dur à deviner sinon) et en supposant approximativement connue l'heure de l'initialisation:

(** Random.self_init relies on caml_sys_random_seed
  * which returns an int.
  * That integer is sec ^ usec ^ ppid<<16 ^ pid.
  * We try to guess the seed to reproduce the output of
  * the random generator.
  * The PID and PPID are supposed to be known,
  * the time in seconds and micro-seconds is supposed
  * to be known resp. with precision 1s and 1000ms.
  * With that knowledge it's really fast;
  * with less it'd take longer. *)

let gen sec usec pid ppid =
  sec lxor usec lxor pid lxor (ppid lsl 16)

let random _ = Random.int 100

(** Given a leaked sequence of numbers consecutively
  * generated by [random] _immediately after_
  * [Random.self_init], call [k] with seeds that allow
  * to reproduce that sequence. *)
let crack leak k =
  let t = Unix.gettimeofday () in
  let sec = int_of_float t in
  let usec = int_of_float (fst (modf t) *. 1_000_000.) in
  let pid = Unix.getpid () in
  let ppid = Unix.getppid () in
    (* Since we sec and usec are xored, trying sec and
     * sec-1 would be useless: all we'd be doing is
     * flipping a bit that is flipped anyway when
     * enumerating posssible values for usec. *)
    for usec = usec - 10000 to usec do
      let seed = gen sec usec pid ppid in
        Random.init seed ;
        if Array.init (Array.length leak) random = leak then
          k seed
    done

let () =
  let leak,valid =
    Random.self_init () ;
    let leak = Array.init 1000 random in
    let valid = Array.init 5000 random in
      leak, valid
  in
  let k seed =
    let guess =
      Random.init seed ;
      ignore (Array.init (Array.length leak) random) ;
      Array.init (Array.length valid) random
    in
      Printf.printf
        "Guessed seed: %d. Validated: %b.\n"
        seed (guess=valid)
  in
    crack leak k ;
    Printf.printf "Search space exhausted.\n"

Quand on le lance, on a quelque chose comme ça en quelques secondes:

$ ocamlopt unix.cmxa crack.ml -o crack && ./crack
Guessed seed: 262818353. Validated: true.
Search space exhausted.

Il y a diverses variations possible. Ce qui m'intéresse, et qui est encore assez obscur pour moi, c'est la génération (répétitive) de graines à partir d'une partie privée et d'une partie publique, utilisée pour éviter d'avoir des séquences générées identiques (ce qui exposerait à des attaques dans certains cas). A quel point on affaiblit ou compromet son secret, en fonction du générateur utilisé, etc?