CC #9: A Wild ECDSA Appears!

Hey 👋! Welcome to the 9th issue of password-based eprint derivation, err ciphertext compression.

Range considered. new ePrints posted between Sun, 9 Jan 2022 12:01AM UTC and Sun, 16 Jan 2022 12:01AM UTC!

This was another slow-ish week on ePrint with 25 new postings.

Real-World Cryptanalysis

RSA, DH and DSA in the Wild — Cryptography in the textbook is not the same as cryptography in the standards which is not the same as cryptography in the libraries. There are many reasons for this, from convenience (“it is a pain to upgrade crypto algorithms”) to performance (“lemme just reuse this expensive-to-generate math thingy”) to underspecified standards (“the standard didn’t tell me which number to pick, so I picked something arbitrarily”). This paper, for RSA, (EC)DH, and (EC)DSA, gives the textbook definition, points out how implementations can differ from it, how that can allow them to be less secure, and lessons for future cryptographic design.

E2EE Group Messaging

Membership Privacy for Asynchronous Group Messaging — Groups need to keep state, like who is in the group, so they can send messages. An easy solution to this, one taken in non-e2ee messengers, is to store this information with the service provider and clients can query the service provider to retrieve and update this information. But, this approach is not great because you are storing private information with some 3rd party. An immediate remediation is to just push everything to the client, the clients keep state locally and on update, all clients update accordingly. This works and was the original approach taken by Signal, but as groups get larger, this becomes annoying to manage, you need heavy-weight distributed systems tools to ensure that users are not lying and retain a consistent view. So, in 2019, Signal upgraded to their current private group system that stores encrypted/verifiable information on the server, so you don’t have to do the expensive distributed systems stuff but still get the privacy because of the encryption. At the same time that Signal was working on this, a different group of computer scientists was working on a different problem: scaling Signal-style e2ee group messaging to thousands of users and came up with Asynchronous Ratcheting Trees (ART).¹ This paper starts the process towards consolidating the two milestones by building Signal-style group membership privacy on top of ART, at the cost of moving back to the clients keep state model.

Lattice Crypto

BAT: Small and Fast KEM over NTRU Lattices — The lattice-based trapdoor functions used in modern lattice KEMs (like NIST Round 3 NTRU) and modern lattice signatures (like NIST Round 3 Falcon) are different. At a supremely high-level, the trapdoor in KEMs is pair of polynomials (the problem reduces to the shortest vector problem), while the trapdoor in signatures is a basis (the problem reduces to the closest vector problem). This paper explores building a KEM from a Falcon-esque trapdoor function and gives a construction BAT that achieves a ciphertext+public key size that is smaller than current lattice KEMs and at NIST-I (128-bit security) parameters comparable to SIKE p434, at the cost of a slower keygen.

Blockchains

Broken Proofs of Solvency in Blockchain Custodial Wallets and Exchanges — The blockchain space is largely unregulated, there is no blockchain FDIC to protect your cryptocoins stored in a custodial wallet. The traditional approach to this problem was to suggest that people don’t use custodial wallets and manage their own private keys. But managing private keys is hard (think about the password recovery problem) and doesn’t let you take advantage of economies of scale (think about the other features banks offer). So, the modern approach is to force the custodians to be honest. Recall that the FDIC achieves this by conducting regular audits to ensure that banks are sufficiently capitalized. At a high-level, being sufficiently capitalized has two parts: (1) having enough money (reserves) and (2) having bounded risk (liabilities). Ideally, to keep with the blockchain ethos, we would like to support such audits without a central trusted 3rd party. This is achieved with proofs of solvency which consist of proofs of reserves and proofs of liabilities. This paper looks at existing deployments of proofs of solvency and observes privacy and security vulnerabilities in their proofs of liabilities from leaking user data (like users’ liabilities) to integrity issues (like using 64-bit hashes in a Merkle tree.)

Benchmarking

ABE Squared: Accurately Benchmarking Efficiency of Attribute-Based Encryption — Benchmarking cryptography is hard. Even for simple block ciphers, the performance is dependent on how much you optimize the finite field math. For more complicated primitives like ABE based on pairings, the performance characteristics are far more brittle relying on the curve you pick and the subtle decisions like the source group you pick to do most of the computation in. This paper builds a modular benchmarking framework for ABE with 4 distinct stages, builds optimized implementations of ABE schemes into it, and shows tradeoffs between the schemes and choices of optimizations.

Closing Words

Thanks for sticking till the end. 💜

You can subscribe to this hooey via Buttondown (using email or rss) and find it on Twitter.

Feel like this can be made better? Please let me know via 📝 this Google Form.

Obvious Disclaimer. Views are mine. All mistakes are mine. If you’d like to point them out, shoot me an email. Maybe I can covertly embed secret messages here. 231D29238A30CA51DDEDA4DDEDC3DD89