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

Safe randomness: theory and practice

Kenji Rikitake
September 07, 2018

Safe randomness: theory and practice

安全なランダムネスの理論と実践
Builderscon Tokyo 2018 7-SEP-2018

Kenji Rikitake

September 07, 2018
Tweet

More Decks by Kenji Rikitake

Other Decks in Technology

Transcript

  1. Kenji Rikitake Γ͖͚ͨ ͚Μ͡ 7-SEP-2018 Builderscon Tokyo 2018 Kyoseikan, Keio

    University Yokohama City, Kanagawa, Japan @jj1bdx Copyright ©2018 Kenji Rikitake. This work is licensed under a Creative Commons Attribution 4.0 International License. Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 2
  2. When randomness needed ϥϯμϜωε͕ඞཁͳ࣌ • Password/key generation / ύεϫʔυ΍伴ͷੜ੒ •

    Timing obfuscation / ॲཧ࣌ؒΛӅ͢ • Using multiple resources equally but unpredictably / ෳ਺ͷࢿݯΛಉ͡Α͏ʹɺ͔͠͠ ༧ଌ͞Εͳ͍Α͏ʹ࢖͍͍ͨ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 6
  3. In algorithm, randomness is represented as: Random numbers ΞϧΰϦζϜͰͷϥϯμϜωε͸ ཚ਺

    ʹΑͬͯදݱ͠·͢ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 7
  4. Software contribution to Erlang/OTP • Improve the random number algorithms

    • ཚ਺ΞϧΰϦζϜͷվળ • Erlang/OTP rand module • SFMT for Erlang/OTP • TinyMT calculation of 256M keys Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 9
  5. Legacy Erlang/OTP random module • A 1980s algorithm called AS183

    • Can be fully scanned in 8 hours • Became a security issue - deprecated since OTP 19 (June 2016) • 8࣌ؒͰશ਺ݕࡧͰ͖ͯ͠·͏ • ηΩϡϦςΟ໰୊ʹͳΓOTPόʔδϣϯ19ʢ2016 ೥6݄ʣΑΓඇਪ঑ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 11
  6. Why hardware? • Randomness is hard to find in a

    computer • Computers are programmed and predictive machines; finding randomness inside computers is extremely difficult • ίϯϐϡʔλͷதʹϥϯμϜωεΛݟ͚ͭΔͷ͸೉͍͠ • ίϯϐϡʔλ͸ϓϩάϥϜ͞Εͨ௨Γʹɺ༧૝௨Γʹ ಈ͘ˠίϯϐϡʔλͷதͰϥϯμϜωεΛݟ͚ͭΔͷ͸ ඇৗʹ೉͍͠ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 13
  7. Randomness sources in a computer • CPU clock jitter /

    CPUΫϩοΫͷ༳Ε • Keyboard timing / ΩʔϘʔυଧ伴ͷλΠϛϯά • Network packet timing / ύέοτͷλΠϛϯά • Storage seeking timing / ετϨʔδͷλΠϛϯά • ... Those sources do not give much randomness • … ͜ΕΒͷιʔε͔ΒಘΒΕΔϥϯμϜωε͸গྔ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 14
  8. Little randomness available in a system γεςϜͷத͔Β͸ϥϯμϜωε͸গ͔͠͠ಘΒΕͳ͍ A result: only

    ~0.62bit/sec • A dormant Linux server without attached keyboard • /proc/sys/kernel/random/entropy_avail • Bits of entropy (= randomness) in the system • 258 bits / 415.6 seconds (~7 minutes) Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 16
  9. Why? Because: Security depends on unpredictability Secure operations consume randomness

    Availability of randomness is limited ηΩϡϦςΟ͸༧ଌෆೳੑʹґଘ͍ͯ͠Δ ҆શͳॲཧ͸ϥϯμϜωεΛফඅ͢Δ ࢖͑ΔϥϯμϜωε͸༗ݶ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 18
  10. Physical randomness source ෺ཧతͳϥϯμϜωεݯ • Thermal noise / ೤ࡶԻ •

    Avalanche noise of semiconductor junctions / ൒ಋ ମ઀߹෦ͷͳͩΕ߱෬ࡶԻ • Timing jitter of oscillation circuits / ൃৼճ࿏ͷλ Πϛϯάͷ༳Ε Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 19
  11. Physical random number generator with Arduino UNO Displayed at Maker

    Faire Tokyo 2016 This implementation is working as a dice: generating numbers of 1~6 / αΠίϩಉ༷ʹ1͔Β6· Ͱͷ਺ࣈΛੜ੒͢Δ Generating ~10kbytes/sec Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 20
  12. Infinity Noise TRNG • Thermal noise based • USD35/device •

    Public domain, no patent • No MCU on the device / σόΠ ε͸MCUΛ࣋ͨͳ͍ • ~40Kbytes/sec Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 22
  13. Infinity Noise TRNG schematics FTDI bitbang I/O controls the noise

    amplifier Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 23
  14. How to inject external randomness to the operating systems •

    Linux: random(4) ioctl() of RNDGETENTCNT, RNDADDENTROPY (User accessible) • FreeBSD: random_harvest(9) (Accessible from kernel modules only, device driver needed) • Other proprietary OSes: unable to find the same functions / ͦͷଞͷಠࣗOSͰ͸֎෦͔ΒϥϯμϜ ωεΛ஫ೖͰ͖ͳ͍ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 24
  15. Whitening for uniform distribution • Cryptographically strong hash functions are

    used in the whitening • Whitening is implemented in the driver or the post- processing software • ҉߸Խϋογϡؔ਺Λద༻͠ ͯग़ྗͷ෼෍ΛҰ༷Խ͢Δॲ ཧʢϗϫΠτχϯάʣ͕ඞཁ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 25
  16. How much randomness is enough? • USD <100 generator: >

    ~10kbytes/sec, more than sufficient for an active server • If you generate a lot of keys/passwords, consider dedicated generator of Mbps or Gbps class (they exist but expensive) • ϋʔυ΢ΣΞੜ੒ث͕͋Ε͹~10kόΠτ/ඵҎ্ʢ௨ৗ ͷӡ༻ʹ͸े෼ʣ • ຊؾͰେྔʹ伴΍ύεϫʔυΛੜ੒͢ΔͳΒઐ༻ͷ෺ ཧཚ਺ੜ੒ثΛಋೖ͢΂͠ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 27
  17. Experimental systems in our office • FreeBSD 11 with Infinity

    Noise TRNG • https://github.com/jj1bdx/infnoise-freebsd • https://github.com/jj1bdx/freebsd-dev-trng • Ubuntu 18.04 with Infinity Noise TRNG • https://github.com/jj1bdx/infnoise-linux • Infinity Noise TRNG on Windows 10 also works • https://github.com/jj1bdx/infnoise-windows Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 28
  18. Summary/·ͱΊ • Good randomness is hard to obtain • External

    physical random number generator is essential for secure operation • Do not invent your own methods • ྑ͍ϥϯμϜωεΛಘΔͷ͸೉͍͠ • ҆શͳӡ༻ʹ͸֎෦ͷ෺ཧཚ਺૷ஔ͕ෆՄܽ • ࣗݾྲྀͰ΍Βͳ͍ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 29
  19. Other references • Presentation slide repository • Arduino UNO TRNG:

    avrhwrng • Crowd Supply product page of Infinity Noise TRNG • Infinity Noise TRNG (with the schematics) • Fifteen Ways to Leave Your Random Module (Erlang User Conference 2016) • ٙࣅཚ਺ͷ࡞Γํɾ࢖͍ํ ήʔϜ͔Β৘ใηΩϡϦ ςΟ·Ͱ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 30
  20. Acknowledgment This presentation is supported by Pepabo R&D Institute, GMO

    Pepabo, Inc. ͜ͷߨԋ͸GMOϖύϘגࣜձࣾ ϖύϘݚڀॴͷ͝ࢧԉͰ࣮ݱ͠ ·ͨ͠ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 31
  21. Thanks Questions? Give the feedback please; use the QR code

    on your name card ϑΟʔυόοΫΛ͓Ͷ͕͍͠·͢ / ωʔϜΧʔυͷQRίʔυΛ࢖͍ͬͯͩ͘͞ Kenji Rikitake / Builderscon Tokyo 2018 7-SEP-2018 32