Upgrade to Pro — share decks privately, control downloads, hide ads and more …

The plain simple reality of entropy @ 32C3

The plain simple reality of entropy @ 32C3

Filippo Valsorda

December 29, 2015
Tweet

More Decks by Filippo Valsorda

Other Decks in Programming

Transcript

  1. The plain simple reality of entropy Or how I learned

    to stop worrying and love urandom Filippo Valsorda — @FiloSo=le Cryptography and systems engineering at
  2. Random bytes • Keys
 ssh-keygen -b 2048
 SSL/TLS symmetric keys

    • Nonces, (EC)DSA signatures • TCP Sequence number, DNS Query ID • ASLR (Address space layout randomiza[on) • Passphrases, tokens, … • Simula[ons
  3. Unpredictable events ȡ Ý • Visible to the kernel •

    Carrying variable amounts of entropy • Not uniform and usually not enough
  4. SHA2-512( ) Example hash-based CSPRNG 1492bcf6062118a27098c426122651 805958a9b7149a8b4c534fb8721d81 d59029df69ddb0624fb07ecd55d4e0 6a74e0dcdf8b209576d2705e520eb5 9f1a3212b0e30d445cd08d06b3ccf8

    fedb56c946266cb56d0df18dd2c79f a09087f6a580f7f1dc8a1840de5483 75aeebc228421a1dadc091b9088b99 1b38b2f77e478cff4cc92ff99fa06d9029a2cf8a10f5cfee83ea2e7bd8a123f7 31ff26c51e048c5030cb3469349fe221835f7ffc70893c5b2674691b7dafc744
  5. Example hash-based CSPRNG 0fb23fc707f8764892f3fa613c6ea24b 27d159a6d29e6daa1a53297e96155022 17268915dd48c60864aca2de3f105266 4452b99f41e1f7221711529eb3191b9f SHA2-512( || 0

    ) f376eb8cee3b9c4c44c3b467a417ab7b f577ac352cf9705eda0e98b6e32daad7 318aa173e463e1f9cb1e93806fd702e3 c58946ff9320aae429385e22aa6ba271 Entropy pool Random bytes … 0fb23fc707f8764892f3fa613c6ea24b 27d159a6d29e6daa1a53297e96155022 17268915dd48c60864aca2de3f105266 4452b99f41e1f7221711529eb3191b9f SHA2-512( || 1 ) c43a436dc112dff2ca252e37a16b2a7d 3dfb83a73edae801ac127de95d2489d2 3fe2569654499f5538d66b2b7917dce9 4b400747fe898c79b4692b2f2c11aa94 0fb23fc707f8764892f3fa613c6ea24b 27d159a6d29e6daa1a53297e96155022 17268915dd48c60864aca2de3f105266 4452b99f41e1f7221711529eb3191b9f SHA2-512( || 2 ) 945114d9a387f945aed19a1e94a5f804 a3a94dba7d62c67298fbaf1dcc1a72a5 0e1f6785f206ac7b85ef9344f9c0d598 b868183247b511e9b6171fe23f52d053
  6. /dev/urandom $ head -c 300 /dev/urandom | xxd 0000000: f60d

    4bda 67a1 83b4 d095 0db9 5366 0bb7 ..K.g.......Sf.. 0000010: bf20 7474 2b62 8a61 88f5 7938 52ed f77a . tt+b.a..y8R..z 0000020: c2e7 6fa9 3c66 2998 dc54 a6cb 8c59 caa6 ..o.<f)..T...Y.. 0000030: ac37 9640 81d5 1691 09ca 1d64 6d4f 7e9f [email protected]~. 0000040: 6749 8674 4df6 e6d3 85de 4e19 e979 63f2 gI.tM.....N..yc. 0000050: de44 09c5 d6c7 b26b 6407 35e9 5bd3 cbd6 .D.....kd.5.[... 0000060: 1a02 10b8 6111 9713 57a6 191c 5e27 601c ....a...W...^'`. 0000070: 6965 1fc2 5798 8faf 5f6b 104f 351c b2b5 ie..W..._k.O5... 0000080: 573f 9bb9 10bf 16f6 fe0d fdff 2e49 2d86 W?...........I-. 0000090: c183 1cc1 25f1 923e 54ec e235 7ff4 db05 ....%..>T..5.... 00000a0: 56bd 2b26 4e87 a7ad 6542 f01e 183c 718f V.+&N...eB...<q. 00000b0: 7437 6f31 4af6 17e7 7870 ccc9 61e3 dd94 t7o1J...xp..a... 00000c0: 72d1 1b46 bf17 c8ed 2b67 f440 3c34 c22e r..F....+g.@<4..
  7. /dev/[u]random #define INPUT_POOL_SHIFT 12 #define INPUT_POOL_WORDS (1 << (INPUT_POOL_SHIFT-5)) static

    __u32 input_pool_data[INPUT_POOL_WORDS]; static struct entropy_store input_pool = { .poolinfo = &poolinfo_table[0], .name = "input", .limit = 1, .lock = __SPIN_LOCK_UNLOCKED(input_pool.lock), .pool = input_pool_data }; hAps:/ /github.com/torvalds/linux/blob/85051e295m7487fd2254/drivers/char/random.c pool of 4096 bit
  8. /dev/[u]random The pool is mixed with unpredictable bytes from various

    sources using a fast CRC-like hash /* * This function adds bytes into the entropy “pool”. The pool is * stirred with a primitive polynomial of the appropriate degree, * and then twisted. We twist by three bits at a time because * it’s cheap to do so and helps slightly in the expected case * where the entropy is concentrated in the low-order bits. */ static void _mix_pool_bytes(struct entropy_store *r, const void *in, int nbytes) hAps:/ /github.com/torvalds/linux/blob/85051e295m7487fd2254/drivers/char/random.c
  9. /dev/[u]random Random numbers are generated by hashing the pool with

    SHA1 static void extract_buf(struct entropy_store *r, __u8 *out) { sha_init(hash.w); /* Generate a hash across the pool, 16 words (512 bits) at a time */ for (i = 0; i < r->poolinfo->poolwords; i += 16) sha_transform(hash.w, (__u8 *)(r->pool + i), workspace); __mix_pool_bytes(r, hash.w, sizeof(hash.w)); hash.w[0] ^= hash.w[3]; hash.w[1] ^= hash.w[4]; hash.w[2] ^= rol32(hash.w[2], 16); memcpy(out, &hash, EXTRACT_SIZE); } hAps:/ /github.com/torvalds/linux/blob/85051e295m7487fd2254/drivers/char/random.c
  10. /dev/[u]random /dev/random and /dev/urandom use the same code, sizes and

    entropy sources static ssize_t random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) extract_entropy_user(&blocking_pool, buf, nbytes); static ssize_t urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) extract_entropy_user(&nonblocking_pool, buf, nbytes); hAps:/ /github.com/torvalds/linux/blob/85051e295m7487fd2254/drivers/char/random.c
  11. /dev/[u]random Only difference: /dev/random • tries to guess how many

    bits of entropy were mixed in the pool • decreases that number when bytes are read • blocks if number is low
  12. /dev/[u]random If CSPRNGs didn’t work (leaked secret bits): • Stream

    ciphers wouldn’t work • CTR wouldn’t work • TLS wouldn’t work • PGP wouldn’t work Cryptography relies on this.
  13. /dev/[u]random /dev/urandom is safe for crypto • Google’s BoringSSL uses

    it • Python, Go, Ruby use it • Sandstorm replaces /dev/random with it • Cryptographers say so, too • other OSes don’t have /dev/random
  14. /dev/[u]random ✦ hAps:/ /www.imperialviolet.org/2015/10/17/boringssl.html ✦ hAp:/ /sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ ✦ hAp:/ /www.2uo.de/myths-about-urandom/

    ✦ hAp:/ /blog.cr.yp.to/20140205-entropy.html ✦ hAps:/ /developer.apple.com/library/mac/documenta[on/Darwin/Reference/ ManPages/man4/random.4.html ✦ hAps:/ /en.wikipedia.org/wiki/ /dev/random#FreeBSD ✦ hAps:/ /docs.sandstorm.io/en/latest/developing/security-prac[ces/ ✦ hAp:/ /lists.randombit.net/pipermail/cryptography/2013-August/004983.html
  15. You don’t need /dev/random • You don’t need to keep

    measuring your entropy pool • You don’t need to “refill” the pool
 (like haveged, etc.) • Random numbers “quality” does not decrease
  16. The early boot problem At early boot, there’s no pool

    yet. And you o4en have keys to generate. Embedded devices, containers o4en fall prey to this.
  17. Very early at boot, /dev/urandom might not be seeded yet,

    predictable. This is a Linux shortcoming. The OS must save the entropy pool at poweroff. Your distribu[on probably does already. The early boot problem
  18. To sum up: CSPRNGs are cool. You don’t need /dev/random.

    Avoid userspace CSPRNG. Use /dev/urandom
  19. Thank you! Q/A Doubts? Unconvinced? Ask! Filippo Valsorda — @FiloSo=le

    filippo@cloudflare.com Slides: hAps:/ /filippo.io/entropy-talk-ccc
  20. It’s equivalent to OpenBSD getentropy(2) Behaves like urandom, but blocks

    at boot un[l the pool is ini[alized hAps:/ /lwn.net/Ar[cles/606552/ getrandom(2)
  21. #include <linux/random.h> int getrandom(void *buf, size_t buflen, unsigned int flags);

    [...] when reading from /dev/urandom, it blocks if the entropy pool has not yet been initialized. getrandom(2)
  22. If you • can’t use getrandom(2) • run early at

    boot • don’t trust your distribuAon you might want to first read 1 byte from /dev/ random, then use urandom The boot problem
  23. Unseeded CSPRNG Userspace CSPRNG are more dangerous: it’s easy to

    en[rely forget to seed them. It happened: hAp:/ /android-developers.blogspot.it/2013/08/some- securerandom-thoughts.html
  24. hAp:/ /android-developers.blogspot.it/2013/08/some- securerandom-thoughts.html Unseeded CSPRNG “Exploi[ng ECDSA Failures in the

    Bitcoin Blockchain” hAps:/ /speakerdeck.com/filoso=le/exploi[ng-ecdsa- failures-in-the-bitcoin-blockchain
  25. Unseeded CSPRNG Or to seed them with predictable informa[on, like

    the [mestamp. “Linux Ransomware Debut Fails on Predictable Encryp[on Key” hAp:/ /labs.bitdefender.com/2015/11/linux-ransomware- debut-fails-on-predictable-encryp[on-key/
  26. Broken CSPRNG Between 2006 and 2008, in Debian, the OpenSSL

    CSPRNG was crippled, seeding only with the PID. All outputs, keys, etc. of anything using it were easily predictable. hAps:/ /www.debian.org/security/2008/dsa-1571
  27. Broken CSPRNG --- openssl/trunk/rand/md_rand.c 2006/05/02 16:25:19 140 +++ openssl/trunk/rand/md_rand.c 2006/05/02

    16:34:53 141 @@ -271,7 +271,10 @@ static void ssleay_rand_add( else MD_Update(&m,&(state[st_idx]),j); +/* + * Don't add uninitialised data. MD_Update(&m,buf,j); +*/ MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c)); MD_Final(&m,local_md); md_c[1]++;
  28. Fork()ed entropy pool The state of a userspace CSPRNG is

    duplicated on fork(), so the child and the parent will generate iden[cal streams if not reseeded. hAps:/ /www.agwa.name/blog/post/ libressls_prng_is_unsafe_on_linux
  29. Non-CS PRNG Not all PRNG are Cryptographically Secure Normal PRNG

    are usually fast and uniform, but not unpredictable.
  30. Non-CS PRNG Mersenne Twister (MT19937) Python: random.random() Ruby: Random::rand() PHP:

    mt_rand() C (depends on stdlib impl, but non-CS): rand(3), random(3)
  31. Non-CS PRNG For example, MT19937 core is a state of

    624 numbers, and a mixing func[on that iterates over them. Given an output, it’s easy to reconstruct the state number from which it was generated. Ayer seeing just 624 outputs, we can predict all future outputs.
  32. Non-CS PRNG def untemper_MT19937(y): x = y for i in

    range(32 // 18): y ^= x >> (18 * (i + 1)) for i in range(32 // 15): y ^= (((y >> (i*15)) % (2**15)) << ((i+1)*15)) & 0xefc60000 for i in range(32 // 7): y ^= (((y >> (i*7)) % (2**7)) << ((i+1)*7)) & 0x9d2c5680 x = y for i in range(32 // 11): y ^= x >> (11 * (i + 1)) return y
  33. A word about HWRNG Many CPUs now have built-in hardware

    random number generators. Intel (RDRAND), Broadcom (on the Raspberry Pi), many others. When/if loaded in the kernel, they seed the pool and every SHA1 extrac[on.
  34. A word about HWRNG /* * If we have an

    architectural hardware * random number generator, use it for SHA’s * initial vector */ sha_init(hash.w); for (i = 0; i < LONGS(20); i++) { unsigned long v; if (!arch_get_random_long(&v)) break; hash.l[i] = v; }