The Matasano Crypto Challenges (review)
If you don’t have time for the challenges themselves, reading this review a few times until the lessons are internalized may be a good substitute.
> How practical these attacks were. A lot of stuff that I knew was weak in principle (like re-using a nonce or using a timestamp as a ‘random’ seed) turns out to be crackable within seconds by an art major writing crappy Python.
> We present an attack on the encryption key negotiation protocol of Bluetooth BR/EDR. The attack allows a third party, without knowledge of any secret material (such as link and encryption keys), to make two (or more) victims agree on an encryption key with only 1 byte (8 bits) of entropy. Such low entropy enables the attacker to easily brute force the negotiated encryption keys, decrypt the eavesdropped ciphertext, and inject valid encrypted messages (in real-time). The attack is stealthy because the encryption key negotiation is transparent to the Bluetooth users. The attack is standard-compliant because all Bluetooth BR/EDR versions require to support encryption keys with entropy between 1 and 16 bytes and do not secure the key negotiation protocol. As a result, the attacker completely breaks Bluetooth BR/EDR security without being detected. We call our attack Key Negotiation Of Bluetooth (KNOB) attack.
Better Encrypted Group Chat
> End-to-end encrypted group messaging is also a hard problem to solve. Existing solutions such as Signal, WhatsApp, and iMessage have inherent problems with scaling, which I’ll discuss in detail, that make it infeasible to conduct group chats of more than a few hundred people. The Message Layer Security (MLS) protocol aims to make end-to-end encrypted group chat more efficient while still providing security guarantees like forward secrecy and post-compromise security.
> The primary contribution of molasses has been in detecting errors in the specification and other implementations through unit and interoperability testing. Molasses implements most of MLS draft 6. Why not all of draft 6? There was an error in the spec that made it impossible for members to be added to any group. This broke all the unit tests that create non-trivial groups. Errors like this are hard to catch just by reading the spec; they require some amount of automated digging. Once they are found, the necessary revisions tend to be pretty obvious, and they are swiftly incorporated into the subsequent draft.
Nice work and a very nice explanation of the protocol.
Dragonblood new results
> August 2019 — During our initial disclosure, the Wi-Fi Alliance privately created security recommendations to mitigate our attacks. In these recommendations, they claim that Brainpool curves are safe to use, at least if products securely implement Dragonfly’s quadratic residue test (i.e. it must be implemented without side-channel leaks). However, we found that using Brainpool curves introduces a second class of side-channel leaks in the Dragonfly handshake of WPA3. In other words, even if the advice of the Wi-Fi Alliance is followed, implementations remain at risk of attacks. This demonstrates that implementing Dragonfly and WPA3 without side-channel leaks is surprisingly hard. It also, once again, shows that privately creating security recommendations and standards is at best irresponsible and at worst inept.
That last line.
Four reasons why cryptography is so hard to get right and four solutions
> Before proceeding, I want to stress that everything I refer to here relates to mistakes made when using (good) cryptographic libraries. The challenge of implementing the low-level cryptographic primitives themselves (like AES, RSA, ECC and so on) is a very different one, requiring high cryptographic engineering experience and knowledge. As such, this should be avoided whenever possible. In contrast, many software engineers need to just use cryptography in their work, and this cannot be avoided. Unfortunately, even this turns out to be far more problematic than expected.
This rings very true. The recommended solution, use a better library instead of lower level pieces, is also good, but should probably give some names. libsodium for example.
> RSA is an intrinsically fragile cryptosystem containing countless foot-guns which the average software engineer cannot be expected to avoid. Weak parameters can be difficult, if not impossible, to check, and its poor performance compels developers to take risky shortcuts. Even worse, padding oracle attacks remain rampant 20 years after they were discovered. While it may be theoretically possible to implement RSA correctly, decades of devastating attacks have proven that such a feat may be unachievable in practice.
Hello World, and OpenPGP Is Broken
> This is the inaugural issue of Cryptography Dispatches, meant to be quick, frequent and lightly edited discussions of cryptographic topics. Longer form can be found at blog.filippo.io.
> For my first round, I am writing about the recent attack on the PGP keyservers. The overall goal of the newsletter is to explain cryptography rather than to comment on the news, so we will cover context and mechanics, not the last minute updates. Issues about Ristretto, Ed25519 in Go, AES-GCM-SIV, and OPRF based contact discovery are still coming as promised!
How does Apple (privately) find your offline devices?
> A big caveat: much of this could be totally wrong. I’ll update it relentlessly when Apple tells us more.
> Since this is a security system, the first question you should ask is: who’s the bad guy? The answer in this setting is unfortunate: everyone is potentially a bad guy. That’s what makes this problem so exciting.
Using Ed25519 Signing Keys For Encryption
> First, we need to understand the difference between Ed25519 and X25519. For that I recommend Montgomery curves and their arithmetic by Craig Costello and Benjamin Smith, which is where I learned most of the underlying mechanics of Montgomery curves. The high level summary is that the twisted Edwards curve used by Ed25519 and the Montgomery curve used by X25519 are birationally equivalent: you can convert points from one to the other, and they behave the same way.
age - A simple file encryption tool & format
> This is a design for a simple file encryption CLI tool, Go library, and format. It’s meant to replace the use of gpg for encrypting files, backups, streams, etc. It’s going to be called “age”, which might be an acronym for Actually Good Encryption.
Private Key Extraction from Qualcomm Hardware-backed Keystores
> A side-channel attack can extract private keys from certain versions of Qualcomm’s secure keystore. Recent Android devices include a hardware-backed keystore, which developers can use to protect their cryptographic keys with secure hardware. On some devices, Qualcomm’s TrustZone-based keystore leaks sensitive information through the branch predictor and memory caches, enabling recovery of 224 and 256-bit ECDSA keys. We demonstrate this by extracting an ECDSA P-256 private key from the hardware-backed keystore on the Nexus 5X.
A Go implementation of Poly1305 that makes sense
> Although it’s really a fraction of the complexity of e.g. elliptic curves, most of the implementations I’ve read look decidedly like magic, mysteriously multiplying values by enchanted constants, and shuffling bits like The Sorcerer’s Apprentice in Fantasia. Even the paper does not explain why and how its design decisions lead to faster code!
> Still, after reverse-engineering what the implementations were doing, I grew convinced that cryptography code could be perfectly understandable if only we commented it.
Cryptography During the French and American Wars in Vietnam
> After Vietnam’s Declaration of Independence on 2 September 1945, the country had to suffer through two long, brutal wars, first against the French and then against the Americans, before finally in 1975 becoming a unified country free of colonial domination. Our purpose is to examine the role of cryptography in those two wars. Despite the far greater technological resources of their opponents, the communications intelligence specialists of the Viet Minh, the National Liberation Front, and the Democratic Republic of Vietnam had considerable success in both protecting Vietnamese communications and acquiring tactical and strategic secrets from the enemy. Perhaps surprisingly, in both wars there was a balance between the sides. Generally speaking, cryptographic knowledge and protocol design were at a high level at the central commands, but deployment for tactical communications in the field was difficult, and there were many failures on all sides.
zkp: a toolkit for Schnorr proofs
> About two years ago, I made a proof-of-concept library called zkp, which used Rust macros to auto-generate an implementation of proving and verification for a class of Schnorr-style discrete logarithm proof statements. However, this approach had a number of limitations and wasn’t suitable for use in real applications. Today, I published a new and completely rewritten version of the library, which is now available on crates.io.
A Deep Dive on RSA Accumulators
> Accumulators are a topic of interest in academia since 1994. Similarly to a Merkle Tree, they are used to cryptographically commit to the knowledge of a set of data. At a later point in time, proving membership of a subset of the dataset in the dataset can be proven by publishing a proof. In Merkle Trees the proof is called a Merkle Branch (or Merkle Proof), and grows logarithmically to the size of the committed data (commit 16 elements, prove inclusion by revealing log_2(16)=4).
> Accumulators on the other hand, allow proving membership in constant size, as well as batching of proofs for multiple elements (which is not a feature of Merkle trees).
> The focus of this post will be on describing the building blocks of RSA Accumulators, how we can construct proofs of (non-)membership as well as batch them across multiple blocks. This particular technique also has applications in UTXO-Based Plasma, and has given birth to the Plasma Prime variant. A lot of effort is being put into designing an accumulator that allows compaction of the UTXO-set in Plasma.
The beginning of Public-key cryptography
> “Can the reader say what two numbers multiplied together will produce the number 8616460799? I think it unlikely that anyone but myself will ever know”
> -William S Jevons, The Principles of Science, 1874
Fast Perfect Hashing Of Integral Types
> Encrypting a padded 32-bit value with AES will not produce a perfect 32-bit hash. AES is only guaranteed to be perfect if the key is 128-bits. Making the AES algorithm produce a perfect hash of, for example, a 32-bit key in its lowest 32 bits requires understanding the internals of the AES algorithm.
Introducing Adiantum: Encryption for the Next Billion Users
> Where AES is used, the conventional solution for disk encryption is to use the XTS or CBC-ESSIV modes of operation, which are length-preserving. Currently Android supports AES-128-CBC-ESSIV for full-disk encryption and AES-256-XTS for file-based encryption. However, when AES performance is insufficient there is no widely accepted alternative that has sufficient performance on lower-end ARM processors.
> To solve this problem, we have designed a new encryption mode called Adiantum. Adiantum allows us to use the ChaCha stream cipher in a length-preserving mode, by adapting ideas from AES-based proposals for length-preserving encryption such as HCTR and HCH. On ARM Cortex-A7, Adiantum encryption and decryption on 4096-byte sectors is about 10.6 cycles per byte, around 5x faster than AES-256-XTS.
Paper link: https://tosc.iacr.org/index.php/ToSC/article/view/7360
Big Integer Design
> This page explains the design and implementation of operations on big (modular) integers, used for RSA and generic elliptic curve computations.
> This section describes the mathematical foundations of the algorithms implemented in BearSSL. This is in no way an exhaustive treaty of computations on big integers; there are many representations and algorithms that are not shown here. These algorithms are the ones that are used in BearSSL (except Karatsuba multiplication, which is briefly exposed below, but not used in BearSSL right now).
A proposed API for full-memory encryption
> Hardware memory encryption is, or will soon be, available on multiple generic CPUs. In its absence, data is stored — and passes between the memory chips and the processor — in the clear. Attackers may be able to access it by using hardware probes or by directly accessing the chips, which is especially problematic with persistent memory. One new memory-encryption offering is Intel’s Multi-Key Total Memory Encryption (MKTME) [PDF]; AMD’s equivalent is called Secure Encrypted Virtualization (SEV). The implementation of support for this feature is in progress for the Linux kernel. Recently, Alison Schofield proposed a user-space API for MKTME, provoking a long discussion on how memory encryption should be exposed to the user, if at all.