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

Embedded cryptography in Rust: RustCrypto + Ver...

Embedded cryptography in Rust: RustCrypto + Veriform

tarcieri

July 18, 2020
Tweet

More Decks by tarcieri

Other Decks in Programming

Transcript

  1. Tony Arcieri · Oxidize Global · July 18th, 2020 Embedded

    cryptography in Rust RustCrypto + Veriform
  2. A quick plug How iqlusion is using RustCrypto • USB

    Armory mkII
 https://github.com/iqlusioninc/usbarmory.rs • Armistice: RTIC-based Hardware Security Module
 https://github.com/iqlusioninc/armistice
  3. Is Rust a good language for crypto? Timing side-channels Is

    it possible to generate constant-time assembly from Rust source code? Towards a Rust common crypto library
  4. Conclusion Two-pronged approach 1. Wrap mainstream crypto libs 2. Experimental

    pure Rust crypto Final thoughts • Rust has immense potential for cryptography but we must tread carefully • Rust code without any branches isn’t necessarily constant time. Beware LLVM! • Stick with wrappers to mainstream crypto libraries until pure Rust crypto is more mature
  5. 2020 Two-pronged approach to Rust Cryptography • Libraries which wrap

    high-quality non-Rust crypto implementations: • ring • sodiumoxide (wrapper for libsodium/NaCl) • secp256k1-rs • Pure Rust cryptography: • RustCrypto • Dalek libraries (e.g. curve25519-dalek) • fiat-rust

  6. RustCrypto Project information • Home: https://github.com/RustCrypto • Started in 2016

    • Leads: • Artyom Pavlov (@newpavlov) • Myself (@tarcieri) • ~12 additional active contributors • ~100 crates
  7. RustCrypto You might already be using one of these crates:

    • aes • blake2 • digest • hmac • sha2
  8. RustCrypto Goals and Architectural Principles • Pure Rust as a

    baseline • #![no_std] as a baseline • Portable implementations which work on all targets • Optional assembly is allowed (off-by-default / opt-in only) • Multi-crate architecture: crate-per-trait / crate-per-algorithm • Trait-based architecture: trait per algorithm family, anyone can implement
  9. Authenticated Encryption https://github.com/RustCrypto/AEADs • Traits: `aead` crate • Algorithm crates:

    • aes-gcm • aes-gcm-siv and aes-siv • ccm and aes-ccm • chacha20poly1305 • xsalsa20poly1305 • …and more! ✅ ✅
  10. Hashes (a.k.a. digest algorithms) https://github.com/RustCrypto/hashes • Traits: `digest` crate •

    Algorithm crates: • blake2 • ripemd160 • sha2 (SHA-256, SHA-384, SHA-512) • …and more!
  11. Public Key Cryptography • Elliptic Curve Cryptography (ECC)
 https://github.com/RustCrypto/elliptic-curve •

    Traits: `elliptic-curve` crate • Curve crates: `k256` (secp256k1), `p256`, `p384`, `p512` • RSA: `rsa` crate
 https://github.com/RustCrypto/RSA • no_std + alloc support coming soon! (see RustCrypto/RSA#22) • Digital Signatures
 https://github.com/RustCrypto/signatures • Traits: `signature` crate • Algorithm crates: `ecdsa`, `ed25519` (now used by `ed25519-dalek`)
  12. Too Much Crypto Jean-Philippe Aumasson Teserakt AG, Switzerland Abstract. We

    show that many symmetric cryptography primitives would not be less safe with significantly fewer rounds. To support this claim, we review the cryptanalysis progress in the last 20 years, examine the reasons behind the current number of rounds, and analyze the risk of doing fewer rounds. Advocating a rational and scientific approach to round numbers selection, we propose revised number of rounds for AES, BLAKE2, ChaCha, and SHA-3, which o↵er more consistent security margins across primitives and make them much faster, without increasing the security risk. 1 Introduction 2 2 Security bits 2 3 A history of attacks 3 3.1 AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
  13. Salsa20 + Poly1305 Stream cipher Universal hash (MAC) Universal hash

    (MAC) ChaCha20 + Poly1305 Stream cipher Authenticated encryption algorithms
  14. Communication Theory of Secrecy Systems By C. E. SHANNON 1

    INTRODUCTION AND SUMMARY The problems of cryptography and secrecy systems furnish an interesting ap- plication of communication theory1. In this paper a theory of secrecy systems is developed. The approach is on a theoretical level and is intended to com- plement the treatment found in standard works on cryptography2. There, a detailed study is made of the many standard types of codes and ciphers, and of the ways of breaking them. We will be more concerned with the general mathematical structure and properties of secrecy systems. The treatment is limited in certain ways. First, there are three general types of secrecy system: (1) concealment systems, including such methods as invisible ink, concealing a message in an innocent text, or in a fake cov- ering cryptogram, or other methods in which the existence of the message is concealed from the enemy; (2) privacy systems, for example speech in- version, in which special equipment is required to recover the message; (3) “true” secrecy systems where the meaning of the message is concealed by cipher, code, etc., although its existence is not hidden, and the enemy is as- 1949
  15. produced by variation in M should divide the key space

    into a number of subsets of comparable probability, with the statistic specifying the one in which the correct key lies. The statistic should give us sizeable informa- tion about the key, not a tiny fraction of a bit. 4. The information it gives must be simple and usable. Thus the subsets in which the statistic locates the key must be of a simple nature in the key space. Frequency count for simple substitution is an example of a very good statistic. Two methods (other than recourse to ideal systems) suggest themselves for frustrating a statistical analysis. These we may call the methods of diffu- sion and confusion. In the method of diffusion the statistical structure of M which leads to its redundancy is “dissipated” into long range statistics—i.e., 708 “Diffusion” (Shannon 1949)
  16. ChaCha20 vs Salsa20 Algorithmic improvements • ChaCha20 improves per-round diffusion

    • ChaCha20 improves performance • Salsa20 has reduced round variants: • Salsa20/8 • Salsa20/12
  17. New Features of Latin Dances: Analysis of Salsa, ChaCha, and

    Rumba Jean-Philippe Aumasson1, Simon Fischer1, Shahram Khazaei2, Willi Meier1, and Christian Rechberger3 1 FHNW, Windisch, Switzerland 2 EPFL, Lausanne, Switzerland 3 IAIK, Graz, Austria Abstract. The stream cipher Salsa20 was introduced by Bernstein in 2005 as a can- didate in the eSTREAM project, accompanied by the reduced versions Salsa20/8 and Salsa20/12. ChaCha is a variant of Salsa20 aiming at bringing better diffusion for sim- ilar performance. Variants of Salsa20 with up to 7 rounds (instead of 20) have been broken by differential cryptanalysis, while ChaCha has not been analyzed yet. We in- troduce a novel method for differential cryptanalysis of Salsa20 and ChaCha, inspired by correlation attacks and related to the notion of neutral bits. This is the first appli- cation of neutral bits in stream cipher cryptanalysis. It allows us to break the 256-bit version of Salsa20/8, to bring faster attacks on the 7-round variant, and to break 6- and 7-round ChaCha. In a second part, we analyze the compression function Rumba, built as the XOR of four Salsa20 instances and returning a 512-bit output. We find collision and preimage attacks for two simplified variants, then we discuss differential attacks on the original version, and exploit a high-probability differential to reduce complexity of collision search from 2256 to 279 for 3-round Rumba. To prove the correctness of our approach we provide examples of collisions and near-collisions on simplified versions. 1 Introduction Salsa20 [5] is a stream cipher introduced by Bernstein in 2005 as a candidate in the eSTREAM project [12], that has been selected in April 2007 for the third and ultimate phase of the competition. Three independent cryptanalyses were published [11,13,16], reporting key-recovery attacks for reduced versions with up to 7 rounds, while Salsa20 has a total of 20 rounds. Bernstein also 2007 Too Much Crypto Jean-Philippe Aumasson Teserakt AG, Switzerland Abstract. We show that many symmetric cryptography primitives would not be less safe with significantly fewer rounds. To support this claim, we review the cryptanalysis progress in the last 20 years, examine the reasons behind the current number of rounds, and analyze the risk of doing fewer rounds. Advocating a rational and scientific approach to round numbers selection, we propose revised number of rounds for AES, BLAKE2, ChaCha, and SHA-3, which o↵er more consistent security margins across primitives and make them much faster, without increasing the security risk. 1 Introduction 2 2 Security bits 2 3 A history of attacks 3 3.1 AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2 BLAKE2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.3 ChaCha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.4 SHA-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 The meaning of attacks 5 4.1 Attacks as negative results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4.2 Attacks on paper vs. in reality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.3 Attacks and risk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.3.1 Perfection is imperfection . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.3.2 Cryptographic numerology . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2019
  18. and present attacks on ChaCha up to 7 rounds. The

    128-bit versions are also investigated. In a second part, we first show collision and preimage attacks for simplified versions of Rumba, then we present a differential analysis of the orig- inal version using the methods of linearization and neutral bits: our main result is a collision attack for 3-round Rumba running in about 279 trials (compared to 2256 with a birthday attack). We also give examples of near-collisions over three and four rounds. Table 1. Complexity of the best attacks known, with success probability 1/2. Salsa20/7 Salsa20/8 ChaCha6 ChaCha7 Rumba3 Before 2190 2255 2255 2255 2256 Now 2151 2251 2139 2248 279 Road Map. We first recall the definitions of Salsa20, ChaCha, and Rumba in §2, then §3 describes our attacks on Salsa20 and ChaCha, and §4 presents our cryptanalysis of Rumba. The appendices give the sets of constant values, and some parameters necessary to reproduce our attacks. “New Features of Latin Dances” (Aumasson et al 2007)
  19. Ask 10 cryptographers and you’ll get 10 di↵erent predictions (for

    di↵erent definitions of “quan- tum computer”), plus cryptographers are usually not the better informed on this question, due to their limited knowledge of quantum physics and engineering, and their natural incentive to exaggerate the risk. The past scientific and technological progress, as well as the current pace of research and engineering, do not support a prediction of a quantum computer able (say) to run Grover on AES anytime soon, or so we believe. Dismissing the risk as negligible is however as easy as it is to naively apply the precautionary principle—for every complex question there is an answer that is clear, simple, and wrong, to quote H.L. Mencken. Anyway, the number of rounds would not matter much would AES be Groverable, the answer to that question is therefore not important in choosing a number of rounds. 5.3 How many rounds? Our goal is to propose numbers of rounds for which we have strong confidence that the algorithm will never be wounded, let alone broken, using the terminology defined in §4.4. Based on the previous research and our cryptanalysis experience, in particular as related to these algorithm, we propose the following: • AES: 9 rounds instead of 10 for AES-128, 10 instead of 12 for AES-192, 11 instead of 14 for AES-256, yielding respectively a 1.1⇥, 1.2⇥, and 1.3⇥ speed-up. 13A third one might be Shor’s exponential speed-up, but it won’t apply to symmetric primitives as they rarely rely on Shorable problems—an exception is the VSH hash function [25]. 13 • BLAKE2: 8 rounds instead of 12 for BLAKE2b, 7 rounds instead of 10 for BLAKE2s (we’ll call these versions BLAKE2bf and BLAKE2sf), yielding respectively a 1.5⇥ and 1.4⇥ speed-up. • ChaCha: 8 rounds instead of 20 (that is, ChaCha8), yielding a 2.5⇥ speed-up. • SHA-3: 10 rounds instead of 24 (we’ll call this version KitTen, inspired by Keccak family member KangarooTwelve), yielding a 2.4⇥ speed-up. These suggested numbers of rounds are probably imperfect choices in terms of consistency, yet the security margins of these four families of algorithms are more consistent with these new rounds numbers than with their original ones. Note that AES’ initial security margin was the thinnest of all, not because it’s the older design, but because of the initial not-overconservative choice of rounds vs. best known attack. AES is thus the primitive for which we propose the smallest change. “Too Much Crypto” (Aumasson 2019)
  20. ChaCha20 is overkill 12 rounds provides equivalent security margin to

    Salsa20 8 rounds beats best known attack at 256-bit security level
  21. Elliptic Curve Cryptography RustCrypto Project Highlights • “Legacy” elliptic curves

    (Weierstrass curves: NIST, secp256k1) • Modern formulas (complete formulas using projective coordinates) • Optimizing for correctness first (performance second) • Constant-time implementations based on the subtle crate • No usages of lookup tables (yet) - small code size
  22. Elliptic curve cryptography RustCrypto implementation status Crate Curve Definitions 32-bit

    arithmetic 64-bit arithmetic ECDH ECDSA k256 secp256k1 (Bitcoin, etc) ✅ ✅ ✅ ✅ p256 NIST P-256 ✅ ✅ ✅ p384 NIST P-384 ✅ ⛔ ⛔ ⛔ ⛔ p521 NIST P-521 ⛔ ⛔ ⛔ ⛔ ⛔
  23. Elliptic Curve Cryptography Embedded highlights • Targeting embedded ECDH +

    ECDSA use cases • ECDH usable today; ECDSA expected in August • Embedded security plans: • Sidechannel resistance (DPA) via random blinding • RNG failures mitigated via RFC 6979 (deterministic ECDSA) • Fault attacks mitigated via additional randomess
 (draft-mattsson-cfrg-det-sigs-with-noise)
  24. The Most Dangerous Code in the World: Validating SSL Certificates

    in Non-Browser Software Martin Georgiev The University of Texas at Austin Subodh Iyengar Stanford University Suman Jana The University of Texas at Austin Rishita Anubhai Stanford University Dan Boneh Stanford University Vitaly Shmatikov The University of Texas at Austin ABSTRACT SSL (Secure Sockets Layer) is the de facto standard for secure In- ternet communications. Security of SSL connections against an active network attacker depends on correctly validating public-key certificates presented when the connection is established. We demonstrate that SSL certificate validation is completely bro- ken in many security-critical applications and libraries. Vulnerable software includes Amazon’s EC2 Java library and all cloud clients based on it; Amazon’s and PayPal’s merchant SDKs responsible for transmitting payment details from e-commerce sites to payment gateways; integrated shopping carts such as osCommerce, ZenCart, Ubercart, and PrestaShop; AdMob code used by mobile websites; Chase mobile banking and several other Android apps and libraries; Java Web-services middleware—including Apache Axis, Axis 2, Codehaus XFire, and Pusher library for Android—and all applica- tions employing this middleware. Any SSL connection from any of these programs is insecure against a man-in-the-middle attack. The root causes of these vulnerabilities are badly designed APIs of SSL implementations (such as JSSE, OpenSSL, and GnuTLS) and data-transport libraries (such as cURL) which present devel- opers with a confusing array of settings and options. We analyze perils and pitfalls of SSL certificate validation in software based on these APIs and present our recommendations. Categories and Subject Descriptors C.2.0 [Computer-Communication Networks]: General—Secu- rity and protection; K.4.4 [Computers and Society]: Electronic Commerce—Security cations. The main purpose of SSL is to provide end-to-end security against an active, man-in-the-middle attacker. Even if the network is completely compromised—DNS is poisoned, access points and routers are controlled by the adversary, etc.—SSL is intended to guarantee confidentiality, authenticity, and integrity for communi- cations between the client and the server. Authenticating the server is a critical part of SSL connection es- tablishment.1 This authentication takes place during the SSL hand- shake, when the server presents its public-key certificate. In order for the SSL connection to be secure, the client must carefully verify that the certificate has been issued by a valid certificate authority, has not expired (or been revoked), the name(s) listed in the certifi- cate match(es) the name of the domain that the client is connecting to, and perform several other checks [14, 15]. SSL implementations in Web browsers are constantly evolving through “penetrate-and-patch” testing, and many SSL-related vul- nerabilities in browsers have been repaired over the years. SSL, however, is also widely used in non-browser software whenever secure Internet connections are needed. For example, SSL is used for (1) remotely administering cloud-based virtual infrastructure and sending local data to cloud-based storage, (2) transmitting cus- tomers’ payment details from e-commerce servers to payment pro- cessors such as PayPal and Amazon, (3) logging instant messenger clients into online services, and (4) authenticating servers to mobile applications on Android and iOS. These programs usually do not implement SSL themselves. In- stead, they rely on SSL libraries such as OpenSSL, GnuTLS, JSSE, CryptoAPI, etc., as well as higher-level data-transport libraries, such as cURL, Apache HttpClient, and urllib, that act as wrappers around SSL libraries. In software based on Web services, there is an additional layer of abstraction introduced by Web-services mid-
  25. Veriform Design highlights • Canonical “TLV” encoding (inspired by both

    ASN.1 DER/OER and Protobufs) • “Heapless” #![no_std] implementation • Structured hashing: automatically computes digests for all parts of a message • Extensible: supports unknown fields and critical fields • Proc macro-derived encoders and decoders
  26. Veriform Use case examples • Certificates (code signing) • RPC

    serialization • Cryptographic audit logs