Posts in Crypto (20 found)
ptrchm 1 months ago

How to Accept Crypto Payments in Rails

I wanted to see what it would take to implement crypto payments in PixelPeeper . With Coinbase Commerce, it’s surprisingly easy. To accept crypto, you’ll need an ETH wallet address and a Coinbase Commerce account. Coinbase provides a nice hosted checkout page, where users have multiple options to pay (the funds will be converted to USDC). Upon successful payment, Coinbase will collect a small fee and the funds will be sent to your ETH address (there’s a caveat, see the last section). How does it work? Create a Charge Rails Integration The Woes of Crypto UX

Crypto tutorial Tutorial ruby Ruby
0 views
Jim Nielsen 1 months ago

Research Alt

Jeremy imagines a scenario where you’re trying to understand how someone cut themselves with a blade. It’d be hard to know how they cut themselves just by looking at the wound. But if you talk to the person, not only will you find out the reason, you’ll also understand their pain. But what if, hear me out here, instead we manufactured tiny microchips with sensors and embedded them in all blades? Then we program them such that if they break human flesh, we send data — time, location, puncture depth, current blade sharpness, etc. — back to our servers for processing with AI. This data will help us understand — without bias, because humans can’t be trusted — how people cut themselves. Thus our research scales much more dramatically than talking to individual humans, widening our impact on humanity whilst simultaneously improving our product (and bottom line)! I am accepting venture funds for this research. You can send funds to this bitcoin address: . Reply via: Email · Mastodon · Bluesky

ai AI Crypto business Business
0 views
Filippo Valsorda 4 months ago

Encrypting Files with Passkeys and age

Typage ( on npm) is a TypeScript 1 implementation of the age file encryption format . It runs with Node.js, Deno, Bun, and browsers, and implements native age recipients, passphrase encryption, ASCII armoring, and supports custom recipient interfaces, like the Go implementation . However, running in the browser affords us some special capabilities, such as access to the WebAuthn API. Since version 0.2.3 , Typage supports symmetric encryption with passkeys and other WebAuthn credentials, and a companion age CLI plugin allows reusing credentials on hardware FIDO2 security keys outside the browser. Let’s have a look at how encrypting files with passkeys works, and how it’s implemented in Typage. Passkeys are synced, discoverable WebAuthn credentials. They’re a phishing-resistant standard-based authentication mechanism. Credentials can be stored in platform authenticators (such as end-to-end encrypted iCloud Keychain), in password managers (such as 1Password), or on hardware FIDO2 tokens (such as YubiKeys, although these are not synced). I am a strong believer in passkeys, especially when paired with email magic links , as a strict improvement over passwords for average users and websites. If you want to learn more about passkeys and WebAuthn I can’t recommend Adam Langley’s A Tour of WebAuthn enough. The primary functionality of a WebAuthn credential is to cryptographically sign an origin-bound challenge. That’s not very useful for encryption. However, credentials with the extension can also compute a Pseudo-Random Function while producing an “assertion” (i.e. while logging in). You can think of a PRF as a keyed hash (and indeed for security keys it’s backed by the FIDO2 extension): a given input always maps to the same output, without the secret there’s no way to compute the mapping, and there’s no way to extract the secret. Specifically, the WebAuthn PRF takes one or two inputs and returns a 32-byte output for each of them. That lets “relying parties” implement symmetric encryption by treating the PRF output as a key that’s only available when the credential is available. Using the PRF extension requires User Verification (i.e. PIN or biometrics). You can read more about the extension in Adam’s book . Note that there’s no secure way to do asymmetric encryption: we could use the PRF extension to encrypt a private key, but then an attacker that observes that private key once can decrypt anything encrypted to its public key in the future, without needing access to the credential. Support for the PRF extension landed in Chrome 132, macOS 15, iOS 18, and 1Password versions from July 2024 . To encrypt an age file to a new type of recipient, we need to define how the random file key is encrypted and encoded into a header stanza . Here’s a stanza that wraps the file key with an ephemeral FIDO2 PRF output. The first argument is a fixed string to recognize the stanza type. The second argument is a 128-bit nonce 2 that’s used as the PRF input. The stanza body is the ChaCha20Poly1305 encryption of the file key using a wrapping key derived from the PRF output. Each credential assertion (which requires a single User Presence check, e.g. a YubiKey touch) can compute two PRFs. This is meant for key rotation , but in our use case it’s actually a minor security issue: an attacker who compromised your system but not your credential could surreptitiously decrypt an “extra” file every time you intentionally decrypt or encrypt one. We mitigate this by using two PRF outputs to derive the wrapping key. The WebAuthn PRF inputs are composed of a domain separation prefix, a counter, and the nonce. The two 32-byte PRF outputs are concatenated and passed to HKDF-Extract-SHA-256 with as salt to derive the ChaCha20Poly1305 wrapping key. That key is used with a zero nonce (since it’s used only once) to encrypt the file key. This age recipient format has two important properties: Now that we have a format, we need an implementation. Enter Typage 0.2.3. The WebAuthn API is pretty complex, at least in part because it started as a way to expose U2F security keys before passkeys were a thing, and grew organically over the years. However, Typage’s passkey support amounts to less than 300 lines , including a simple implementation of CTAP2’s CBOR subset . Before any encryption or decryption operation, a new passkey must be created with a call to . calls with a random to avoid overwriting existing keys, set to to ask the authenticator to store a passkey, and of course . Passkeys not generated by can also be used if they have the extension enabled. To encrypt or decrypt a file, you instantiate an or , which implement the new and interfaces. The recipient and identity implementations call with the PRF inputs to obtain the wrapping key and then parse or serialize the format we described above. Aside from the key name, the only option you might want to set is the relying party ID . This defaults to the origin of the web page (e.g. ) but can also be a parent (e.g. ). Credentials are available to subdomains of the RP ID, but not to parents. Since passkeys are usually synced, it means you can e.g. encrypt a file on macOS and then pick up your iPhone and decrypt it there, which is pretty cool. Also, you can use passkeys stored on your phone with a desktop browser thanks to the hybrid BLE protocol . It should even be possible to use the AirDrop passkey sharing mechanism to let other people decrypt files! You can store passkeys (discoverable or “resident” credentials) on recent enough FIDO2 hardware tokens (e.g. YubiKey 5). However, storage is limited and support still not universal. The alternative is for the hardware token to return all the credential’s state encrypted in the credential ID, which the client will need to give back to the token when using the credential. This is limiting for web logins because you need to know who the user is (to look up the credential ID in the database) before you invoke the WebAuthn API. It can also be desirable for encryption, though: decrypting files this way requires both the hardware token and the credential ID, which can serve as an additional secret key, or a second factor if you’re into factors . Rather than exposing all the layered WebAuthn nuances through the typage API, or precluding one flow, I decided to offer two profiles: by default, we’ll generate and expect discoverable passkeys, but if the option is passed, we’ll request the credential is not stored on the authenticator and ask the browser to show UI for hardware tokens. returns an age identity string that encodes the credential ID, relying party ID, and transports as CTAP2 CBOR, 4 in the format . This identity string is required for the security key flow, but can also be used as an optional hint when encrypting or decrypting using passkeys. More specifically, the data encoded in the age identity string is a CBOR Sequence of One more thing… since FIDO2 hardware tokens are easily accessible outside the browser, too, we were able to build a age CLI plugin that interoperates with typage security key identity strings: age-plugin-fido2prf . Since FIDO2 PRF only supports symmetric encryption, the identity string is used both for decryption and for encryption (with ). This was an opportunity to dogfood the age Go plugin framework , which easily turns an implementation of the Go interface into a CLI plugin usable from age or rage , abstracting away all the details of the plugin protocol . The scaffolding turning the importable Identity implementation into a plugin is just 50 lines . For more details, refer to the typage README and JSDoc annotations. To stay up to date on the development of age and its ecosystem, follow me on Bluesky at @filippo.abyssdomain.expert or on Mastodon at @[email protected] . On the last day of this year’s amazing CENTOPASSI motorcycle rallye, we watched the sun set over the plain below Castelluccio , and then rushed to find a place to sleep before the “engines out” time. Found an amazing residence where three cats kept us company while planning the next day. Geomys , my Go open source maintenance organization, is funded by Smallstep , Ava Labs , Teleport , Tailscale , and Sentry . Through our retainer contracts they ensure the sustainability and reliability of our open source maintenance work and get a direct line to my expertise and that of the other Geomys maintainers. (Learn more in the Geomys announcement .) Here are a few words from some of them! Teleport — For the past five years, attacks and compromises have been shifting from traditional malware and security breaches to identifying and compromising valid user accounts and credentials with social engineering, credential theft, or phishing. Teleport Identity is designed to eliminate weak access patterns through access monitoring, minimize attack surface with access requests, and purge unused permissions via mandatory access reviews. Ava Labs — We at Ava Labs , maintainer of AvalancheGo (the most widely used client for interacting with the Avalanche Network ), believe the sustainable maintenance and development of open source cryptographic protocols is critical to the broad adoption of blockchain technology. We are proud to support this necessary and impactful work through our ongoing sponsorship of Filippo and his team. It started as a way for me to experiment with the JavaScript ecosystem, and the amount of time I spent setting up things that we can take for granted in Go such as testing, benchmarks, formatting, linting, and API documentation is… incredible. It took even longer because I insisted on understanding what tools were doing and using defaults rather than copying dozens of config files. The language is nice, but the tooling for library authors is maddening. I also have opinions on the Web Crypto APIs now. But all this is for another post.  ↩ 128 bits would usually be a little tight for avoiding random collisions , but in this case we care only about never using the same PRF input with the same credential and, well, I doubt you’re getting any credential to compute more than 2⁴⁸ PRFs.  ↩ This is actually a tradeoff: it means we can’t tell the user a decryption is not going to work before asking them the PIN of the credential. I considered adding a tag like the one being considered for stanzas or like the one. The problem is that the WebAuthn API only lets us specify acceptable credential IDs upfront, there is no “is this credential ID acceptable” callback, so we’d have to put the whole credential ID in the stanza. This is undesirable both for privacy reasons, and because the credential ID (encoded in the identity string) can otherwise function as a “second factor” with security keys.  ↩ Selected mostly for ecosystem consistency and because it’s a couple hundred lines to handroll.  ↩ Per-file hardware binding : each file has its own PRF input(s), so you strictly need both the encrypted file and access to the credential to decrypt a file. You can’t precompute some intermediate value and use it later to decrypt arbitrary files. Unlinkability : there is no way to tell that two files are encrypted to the same credential, or to link a file to a credential ID without being able to decrypt the file. 3 the version, always the credential ID as a byte string the RP ID as a text string the transports as an array of text strings It started as a way for me to experiment with the JavaScript ecosystem, and the amount of time I spent setting up things that we can take for granted in Go such as testing, benchmarks, formatting, linting, and API documentation is… incredible. It took even longer because I insisted on understanding what tools were doing and using defaults rather than copying dozens of config files. The language is nice, but the tooling for library authors is maddening. I also have opinions on the Web Crypto APIs now. But all this is for another post.  ↩ 128 bits would usually be a little tight for avoiding random collisions , but in this case we care only about never using the same PRF input with the same credential and, well, I doubt you’re getting any credential to compute more than 2⁴⁸ PRFs.  ↩ This is actually a tradeoff: it means we can’t tell the user a decryption is not going to work before asking them the PIN of the credential. I considered adding a tag like the one being considered for stanzas or like the one. The problem is that the WebAuthn API only lets us specify acceptable credential IDs upfront, there is no “is this credential ID acceptable” callback, so we’d have to put the whole credential ID in the stanza. This is undesirable both for privacy reasons, and because the credential ID (encoded in the identity string) can otherwise function as a “second factor” with security keys.  ↩ Selected mostly for ecosystem consistency and because it’s a couple hundred lines to handroll.  ↩

Crypto javascript JavaScript typescript TypeScript go Go
0 views
Neil Madden 5 months ago

Streaming public key authenticated encryption with insider auth security

Note: this post will probably only really make sense to cryptography geeks. In “When a KEM is not enough ”, I described how to construct multi-recipient (public key) authenticated encryption. A naïve approach to this is vulnerable to insider forgeries: any recipient can construct a new message (to the same recipients) that appears to come from the original sender. For some applications this is fine, but for many it is not. Consider, for example, using such a scheme to create auth tokens for use at multiple endpoints: A and B. Alice gets an auth token for accessing endpoints A and B and it is encrypted and authenticated using the scheme. The problem is, as soon as Alice presents this auth token to endpoint A, that endpoint (if compromised or malicious) can use it to construct a new auth token to access endpoint B, with any permissions it likes. This is a big problem IMO. I presented a couple of solutions to this problem in the original blog post. The most straightforward is to sign the entire message, providing non-repudiation. This works, but as I pointed out in “ Digital signatures and how to avoid them ”, signature schemes have lots of downsides and unintended consequences. So I developed a weaker notion of “insider non-repudiation”, and a scheme that achieves it: we use a compactly-committing symmetric authenticated encryption scheme to encrypt the message body, and then include the authentication tag as additional authenticated data when wrapping the data encryption key for each recipient. This prevents insider forgeries, but without the hammer of full blown outsider non-repudiation, with the problems it brings. I recently got involved in a discussion on Mastodon about adding authenticated encryption to Age (a topic I’ve previously written about ), where abacabadabacaba pointed out that my scheme seems incompatible with streaming encryption and decryption, which is important in Age use-cases as it is often used to encrypt large files. Age supports streaming for unauthenticated encryption, so it would be useful to preserve this for authenticated encryption too. Doing this with signatures is fairly straightforward: just sign each “chunk” individually. A subtlety is that you also need to sign a chunk counter and “last chunk” bit to prevent reordering and truncation, but as abacabadabacaba points out these bits are already in Age, so its not too hard. But can you do the same without signatures? Yes, you can, and efficiently too. In this post I’ll show how. One way of thinking about the scheme I described in my previous blog post is to think of it as a kind of designated-verifier signature scheme. (I don’t hugely like this term, but it’s useful here). That is, we can view the combination of the committing MAC and authenticated KEM as a kind of signature scheme where the signature can only be verified by recipients chosen by the sender, not by third-parties. If we take that perspective, then it becomes clear that we can just do exactly the same as you do for the normal signature scheme: simply sign each chunk of the message separately, and include some chunk counter + last chunk marker in the signature. How does this work in practice? Firstly, we generate a fresh random data encryption key (DEK) for the message. This is shared between all recipients. We then use this DEK to encrypt each chunk of the message separately using our compactly-committing AEAD. To prevent chunk reordering or truncation we can use the same method as Age: Rogaway’s STREAM construction , which effectively just encodes the chunk counter and last-chunk bit into the AEAD nonce. (Personally, I prefer using a symmetric ratchet instead, but that’s for another post). This will produce a compactly committing tag for each chunk—typically 16 bytes per chunk (or 32 bytes if we care about malicious senders ). The original scheme I proposed then fed this tag (of which there was only 1) as associated data when wrapping the DEK for each recipient using an authenticated key-wrap algorithm and a per-recipient wrapping-key derived from an authenticated KEM. If the DEK is 32 bytes, and the key-wrapping algorithm produces a 16-byte tag then this outputs 48 bytes per recipient. We can do exactly the same thing for the new scheme, but we only feed the tag from the first chunk as the associated data, producing wrapped keys that commit to the first chunk only. We then simply repeat the process for each subsequent chunk, but as the DEK is unchanged we can leave it empty: effectively just computing a MAC over the commitment for each chunk in turn. In our example, this will produce just a 16-byte output per recipient for each chunk. If we compare this to typical signature schemes that would be used for signing chunks otherwise, we can fit 4 recipient commitments in the same space as a single Ed25519 signature (64 bytes), or 16 recipients in the same space as an RSA-2048 signature. To support such a scheme, the interface of our KEM would need to change to include a new operation that produces an intermediate commitment to a particular chunk tag, with an indication of whether it is the last tag or not. The KEM is then free to reuse the shared secrets derived for each recipient, avoiding the overhead of computing new ones for each chunk. This is an efficiency gain over using a normal digital signature for each chunk. Here is a sketch of what the overall process would look like, to hopefully clarify the ideas presented. Alice is sending a message to Bob and Charlie. The message consists of three “chunks” and is using an authenticated KEM based on X25519. The total space taken is then 128 + 32 + 32 = 192 bytes, and we can remove the 3 original 16-byte AEAD tags, giving a net overhead of just 144 bytes. Compared to signing each chunk with Ed25519 which would need 192 bytes, or RSA-2048 which needs 768 bytes. Decryption then performs the obvious operations: decrypting and recomputing the MAC tag for each chunk using the decapsulated DEK and then verifying the commitment blocks match at the end of each subsequent chunk. This is still very much a sketch, and needs to be reviewed and fleshed out more. But I believe this is quite a neat scheme that achieves streaming authenticated encryption without the need for tricksy little signatureses , and potentially much more efficient too. First, Alice generates a random 32-byte DEK and uses it to encrypt the message, producing tags t 1 , t 2 , and t 3 . Alice generates a random ephemeral X25519 keypair: ( esk , epk ). She computes a shared secret with Bob, ss b , via something like HPKE’s DH-AKEM. Likewise, she computes a shared secret with Charlie, ss c . Alice then wraps the DEK from step 1 for Bob and Charlie, using a key-wrap algorithm like AES in SIV mode (keyed with ss b and then ss c ), including t 1 as additional authenticated data. She outputs the two wrapped keys plus the ephemeral public key ( epk ) as the encapsulated key blob. This will be 32 bytes for the epk, plus 48 bytes for each key blob (one for Bob, another for Charlie), giving 128 bytes total. She then calls a new “commit” operation on the KEM for each subsequent chunk tag: i.e., t 2 and t 3 . This commit operation performs the same as step 5, but with a blank DEK, outputting just a 16-byte SIV for each recipient for a total of 32 bytes per chunk. These commitment blocks can then be appended to each chunk. (In fact, they can replace the normal AEAD tag, saving even more space).

Crypto security Security
0 views
Neil Madden 5 months ago

Are we overthinking post-quantum cryptography?

tl;dr: yes, contra thingamajig’s law of wotsits . Before the final nail has even been hammered on the coffin of AI, I hear the next big marketing wave is “quantum”. Q uantum computing promises to speed up various useful calculations, but is also potentially catastrophic to widely-deployed public key cryptography. Shor’s algorithm for a quantum computer, if realised, will break the hard problems underlying RSA, Diffie-Hellman, and Elliptic Curve cryptography—i.e., most crypto used for TLS, SSH and so on. Although “cryptographically-relevant” quantum computers (CRQCs) still seem a long way off ( optimistic roadmap announcements and re-runs of previously announced “breakthroughs” notwithstanding), for some applications the risk is already real. In particular, if you are worried about nation-states or those with deep pockets, the threat of “store-now, decrypt-later” attacks must be considered. It is therefore sensible to start thinking about deploying some form of post-quantum cryptography that protects against these threats. But what, exactly? If you are following NIST’s post-quantum crypto standardisation efforts, you might be tempted to think the answer is “everything”. NIST has now selected multiple post-quantum signature schemes and public key encryption algorithms (“ KEMs ”), and is evaluating more. Many application and protocol standards are then building on top of these with the assumption that post-quantum crypto should either replace all the existing crypto, or else at least ride alongside it everywhere in a “hybrid” configuration. We have proposals for post-quantum certificates , post-quantum ciphersuites for TLS , for SSH , for Signal and so on. From my view on the sidelines, it feels like many cryptographers are pushing to entirely replace existing “classical” cryptographic algorithms entirely with post-quantum replacements, with the idea that we would turn off the classical algorithms somewhere down the line. Unfortunately, many of the proposed post-quantum cryptographic primitives have significant drawbacks compared to existing mechanisms, in particular producing outputs that are much larger. For signatures, a state of the art classical signature scheme is Ed25519, which produces 64-byte signatures and 32-byte public keys, while for widely-used RSA-2048 the values are around 256 bytes for both. Compare this to the lowest security strength ML-DSA post-quantum signature scheme, which has signatures of 2,420 bytes (i.e., over 2kB!) and public keys that are also over a kB in size (1,312 bytes). For encryption, the equivalent would be comparing X25519 as a KEM (32-byte public keys and ciphertexts) with ML-KEM-512 (800-byte PK, 768-byte ciphertext). What is the practical impact of this? For some protocols, like TLS, the impact is a bit painful but doable, and post-quantum hybrid ciphersuites are already being rolled out. But there is a long tail of other technologies that have yet to make the transition. For example, consider JWTs, with which I am intimately familiar (in a Stockholm Syndrome way). The signature of a JWT is base64-encoded, which adds an extra 33% size compared to raw binary. So, for Ed25519 signatures, we end up with 86 bytes, after encoding. For ML-DSA, the result is 3,227 bytes. If you consider that browsers typically impose a 4kB maximum size for cookies per-domain, that doesn’t leave a lot of room left for actual data. If you wanted to also encrypt that JWT, then the base64-encoded content (including the signature) is encrypted and then base64-encoded again, resulting in a signature that is already over the 4kB limit on its own. None of this should be taken as an endorsement of JWTs for cookies, or of the design decisions in the JWT specs, but rather it’s just an example of a case where replacing classical algorithms with post-quantum equivalents looks extremely hard. In my own view, given that the threat from quantum computers is at best uncertain and has potentially already stalled (see image below), the level of effort we invest in replacing already deployed crypto with something new needs to be proportional to the risk. In a list of things that keep me up at night as a security engineer, quantum computing would be somewhere on the second or third page. There is, IMO a not-insignificant chance that CRQCs never materialise, and so after a few years we actually roll back entirely to pre-quantum cryptographic algorithms because they are just better. For some applications (such as Signal) that risk profile is quite different, and it is right that they have invested effort into moving to PQC already, but I think for most organisations this is not the case. What would a Minimum Viable Post-Quantum Cryptography transition look like? One that protects against the most pressing threats in a way that is minimally disruptive. I believe such a solution would involve making two trade-offs: To my eyes, this is the obvious first step to take and is potentially the only step we need to take. But this approach seems at odds with where PQC standardisation is heading currently. For example, if we adopt this approach then code-based approaches such as Classic McEliece seem much more attractive than the alternatives currently being standardised by NIST. The main drawback of McEliece is that it has massive public keys (261kB for the lowest security parameters, over 1MB for more conservative choices). But in exchange for that you get much smaller ciphertexts: between 96 and 208 bytes. This is much less than the other lattice-based KEMs, and somewhere between elliptic curves and RSA in size. For many applications of JWTs, which already use static or rarely-updated keys, not to mention OAuth, SAML, Age , PGP, etc this seems like an entirely sensible choice and essentially a low-risk drop-in replacement. Continue using pre-quantum signatures or Diffie-Hellman based authentication mechanism , and layer Classic McEliece on top. A hybrid X25519-McEliece KEM could use as little as 128 bytes for ciphertext—roughly half the size of a typical RSA equivalent and way less than ML-KEM, and could also support (pre-quantum) authentication as an Authenticated KEM by hybridisation with an existing DH-AKEM , avoiding the need for signatures at all . This is the approach I am taking to PQC in my own upcoming open source project, and it’s an approach I’d like to see in JWT-land too (perhaps by resurrecting my ECDH-1PU proposal , which avoids many JWT-specific pitfalls associated with alternative schemes). If there’s enough interest perhaps I’ll find time to get a draft together. Firstly, to commit only to post-quantum confidentiality and ignore any threats to authenticity/integrity from quantum computers until it is much more certain that CRQCs are imminent. That is, we transition to (hybrid) post-quantum encryption to tackle the store-now, decrypt-later threat, but ignore post-quantum signature schemes. We will still have classical authentication mechanisms. Secondly, we implement the absolute bare minimum needed to protect against that store-now, decrypt-later threat: that is, simple encryption with static keys. Any stronger properties, such as forward secrecy, or post-compromise recovery, are left to existing pre-quantum algorithms such as elliptic curve crypto. This largely eliminates the need to transfer bulky PQ public keys over the network, as we can share them once (potentially out-of-band) and then reuse them for a long time.

security Security Crypto
0 views
Binary Igor 7 months ago

Bitcoin P2P Network: peer discovery, reachability and resilience

Peer-to-Peer (P2P) Networks introduce a completely new set of challenges. In the traditional Client-Server Architecture, there is a server and client ... Things work completely differently in the Peer-to-Peer (P2P) Networks. These networks consist of equal peers that communicate directly with each other. Their goal is to be as decentralized as possible and not to have any single point of control or failure.

Crypto Networking
0 views
Filippo Valsorda 11 months ago

Benchmarking RSA Key Generation

RSA key generation is both conceptually simple, and one of the worst implementation tasks of the field of cryptography engineering. Even benchmarking it is tricky, and involves some math: here’s how we generated a stable but representative “average case” instead of using the ordinary statistical approach. Say you want to generate a 2048-bit RSA key. The idea is that you generate random 1024-bit numbers until you find two that are prime, you call them p and q , and compute N = p × q and d = 65537⁻¹ mod φ(N) 1 (and then some more stuff to make operations faster, but you could stop there). The computation of d is where the RSA magic lies, but today we are focusing on the first part. There is almost nothing special to selecting prime candidates. You draw an appropriately sized random number from a CSPRNG, and to avoid wasting time, you set the least significant bit and the two most significant bits: large even numbers are not prime, and setting the top two guarantees N won’t come out too small. Checking if a number x is prime is generally done with the Miller-Rabin test 2 , a probabilistic algorithm where you pick a “base” and use it to run some computations on x . It will either conclusively prove x is composite (i.e. not prime), or fail to do so. Figuring out how many Miller-Rabin tests you need to run is surprisingly difficult: initially you will learn the probability of a test failing for a composite is 1/4, which suggests you need 40 rounds to reach 2⁻⁸⁰; then you learn that’s only the upper bound for worst-case values of x , 3 while random values have a much much lower chance of failure; eventually you also realize that it doesn’t matter that much because you only run all the iterations on the prime, while most composites are rejected in the first iteration. Anyway, BoringSSL has a table and we’ll want 5 Miller-Rabin tests with random bases for a 1024-bit prime. Miller-Rabin is kinda slow though, and most numbers have small divisors, so it’s usually more efficient to quickly reject those by doing “trial divisions” or a GCD with the first handful of primes. The first few dozens are usually a major win, but using more and more primes has diminishing returns. There are a million and one things that can go wrong, but interestingly enough you have to go out of your way to get them wrong: if generating large candidates fully at random, all those cases have cryptographically negligible chance. To recap, to generate an RSA key you generate two primes. To generate a prime you pick random numbers, try to rule them out with trial divisions, and then do a few Miller-Rabin tests on them. Now, how are we supposed to benchmark that? Luck will drastically affect runtime: you’re essentially benchmarking a lottery. While debugging a performance regression Russ Cox ran hundreds of measurements and still got some noisy and in some places suspect results. It’s also not fast enough that you can run millions of measurements and let things average out. One might be tempted to normalize the measurements by dividing the runtime by the number of candidates tested, but this unevenly dilutes all the final computations, and is still perturbed by how many candidates are caught by trial division and how many proceed to the Miller-Rabin tests. Similarly, benchmarking Miller-Rabin in isolation ignores the final computations, and doesn’t measure the impact of trial divisions. What we can do is use math to figure out how an average representative sequence of candidates looks like and benchmark that. Since the key generation process is repeatable, 4 we can pre-generate a golden sequence of candidates, and even share it across implementations to benchmark apples to apples. First, we need to figure out how many composites we should expect on average before each prime. The prime-counting function approximation tells us there are Li(x) primes less than x , which works out 5 to one prime every 354 odd integers of 1024 bits. Then, we normalize the small divisors of the composites. A random number has a 1/p chance of being divisible by p , and based on that we can calculate how many composites divisible by the first n primes we’d expect to encounter before a prime. For example, we’d expect 33% of numbers to be divisible by 3, 46% to be divisible by 3 or 5, 69% of numbers to be divisible by one of the first 10 primes, 80% to be divisible by one of the first 50 primes, and so on . Flipping that around, we make 118 of our 353 composites divisible by 3, 47 divisible by 5 but not by 3, 27 divisible by 7 but not by 3 or 5, and so on. This will make the number of successful trial divisions representative, and will even let us do comparative benchmarks between different trial division thresholds without regenerating the inputs. Beyond setting the top and bottom bits like keygen will , we also unset the second-least significant bit and set the third-least significant bit of each candidate to normalize the number of iterations of the inner loop of Miller-Rabin, which depends on the trailing zeroes of x-1 . We don’t need to worry about composites failing Miller-Rabin tests: if 5 tests are enough to get to 2⁻¹¹² then one test fails with at most 2⁻²² chance, which is not cryptographically negligible but will not show up in benchmarks. Similarly, we don’t need to worry about e not being invertible modulo φ(N) : we use 65537 as e , which is prime, so only 1/65537 numbers aren’t coprime with it. The result is remarkably stable and should be representative both in terms of absolute runtime and in terms of CPU time spent in different functions, allowing meaningful profiling. Generating 20 random average traces and benchmarking them yields variance of less than 1%. You can see it in use in this Go standard library code review . The script to generate the traces, as well as ten ready to use traces are available in CCTV and you’re welcome to use them to benchmark your implementations! If you got this far, you might also want to follow me on Bluesky at @filippo.abyssdomain.expert or on Mastodon at @[email protected] . One day a friend was driving me to the SFO airport from Redwood Park and we were late. Like, flight begins boarding in a few minutes late. But then we came up to this view, and had to stop to take it in. The people in the other car had set out a little camping chair to watch the sun set over the clouds below. I have an incredible video of driving down into the clouds. Made the flight! My maintenance work is funded by the awesome Geomys clients: Interchain , Smallstep , Ava Labs , Teleport , SandboxAQ , Charm , Tailscale , and Sentry . Through our retainer contracts they ensure the sustainability and reliability of our open source maintenance work and get a direct line to my expertise and that of the other Geomys maintainers. (Learn more in the Geomys announcement .) Here are a few words from some of them! Teleport — For the past five years, attacks and compromises have been shifting from traditional malware and security breaches to identifying and compromising valid user accounts and credentials with social engineering, credential theft, or phishing. Teleport Identity is designed to eliminate weak access patterns through access monitoring, minimize attack surface with access requests, and purge unused permissions via mandatory access reviews. Ava Labs — We at Ava Labs , maintainer of AvalancheGo (the most widely used client for interacting with the Avalanche Network ), believe the sustainable maintenance and development of open source cryptographic protocols is critical to the broad adoption of blockchain technology. We are proud to support this necessary and impactful work through our ongoing sponsorship of Filippo and his team. SandboxAQ — SandboxAQ ’s AQtive Guard is a unified cryptographic management software platform that helps protect sensitive data and ensures compliance with authorities and customers. It provides a full range of capabilities to achieve cryptographic agility, acting as an essential cryptography inventory and data aggregation platform that applies current and future standardization organizations mandates. AQtive Guard automatically analyzes and reports on your cryptographic security posture and policy management, enabling your team to deploy and enforce new protocols, including quantum-resistant cryptography, without re-writing code or modifying your IT infrastructure. Charm — If you’re a terminal lover, join the club. Charm builds tools and libraries for the command line. Everything from styling terminal apps with Lip Gloss to making your shell scripts interactive with Gum . Charm builds libraries in Go to enhance CLI applications while building with these libraries to deliver CLI and TUI-based apps. Or, if you want to make your life harder and your code more complex for no practical benefit, you can use λ(N) instead of φ(N) , but that’s for a different rant.  ↩ There is also the Lucas test, and doing both a round of Miller-Rabin with base 2 and a Lucas test is called a Baillie–PSW. There are no known composites that pass the Baillie–PSW test, which sounds great, but the Lucas test is a major pain to implement.  ↩ In an adversarial setting, you also need to worry about the attacker forcing or adapting to your selection of bases. The amazingly-named Prime and Prejudice: Primality Testing Under Adversarial Conditions by Albrecht et al. pulls a number of fun tricks, but the main one boils down to the observation that if you hardcode the bases or generate them from x , they are not random.  ↩ It’s not strictly speaking deterministic, because the tests are randomized, but the chance of coming to a different conclusion is cryptographically negligible, and even the chance of major deviations in runtime is very small, as we will see.  ↩ I did a quick Monte Carlo simulation to check this was correct, and it was really fun to see the value swing and converge to the expected value. Math!  ↩ Or, if you want to make your life harder and your code more complex for no practical benefit, you can use λ(N) instead of φ(N) , but that’s for a different rant.  ↩ There is also the Lucas test, and doing both a round of Miller-Rabin with base 2 and a Lucas test is called a Baillie–PSW. There are no known composites that pass the Baillie–PSW test, which sounds great, but the Lucas test is a major pain to implement.  ↩ In an adversarial setting, you also need to worry about the attacker forcing or adapting to your selection of bases. The amazingly-named Prime and Prejudice: Primality Testing Under Adversarial Conditions by Albrecht et al. pulls a number of fun tricks, but the main one boils down to the observation that if you hardcode the bases or generate them from x , they are not random.  ↩ It’s not strictly speaking deterministic, because the tests are randomized, but the chance of coming to a different conclusion is cryptographically negligible, and even the chance of major deviations in runtime is very small, as we will see.  ↩ I did a quick Monte Carlo simulation to check this was correct, and it was really fun to see the value swing and converge to the expected value. Math!  ↩

Crypto shell Shell performance Performance go Go security Security
0 views
Neil Madden 1 years ago

Digital signatures and how to avoid them

Wikipedia’s definition of a digital signature is: A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient. They also have a handy diagram of the process by which digital signatures are created and verified: Alice signs a message using her private key and Bob can then verify that the message came from Alice, and hasn’t been tampered with, using her public key. This all seems straightforward and uncomplicated and is probably most developers’ view of what signatures are for and how they should be used. This has led to the widespread use of signatures for all kinds of things: validating software updates, authenticating SSL connections, and so on. But cryptographers have a different way of looking at digital signatures that has some surprising aspects. This more advanced way of thinking about digital signatures can tell us a lot about what are appropriate, and inappropriate, use-cases. There are several ways to build secure signature schemes. Although you might immediately think of RSA, the scheme perhaps most beloved by cryptographers is Schnorr signatures. These form the basis of modern EdDSA signatures, and also (in heavily altered form) DSA/ECDSA. The story of Schnorr signatures starts not with a signature scheme, but instead with an interactive identification protocol . An identification protocol is a way to prove who you are (the “prover”) to some verification service (the “verifier”). Think logging into a website. But note that the protocol is only concerned with proving who you are, not in establishing a secure session or anything like that. There are a whole load of different ways to do this, like sending a username and password or something like WebAuthn/passkeys (an ironic mention that we’ll come back to later). One particularly elegant protocol is known as Schnorr’s protocol. It’s elegant because it is simple and only relies on basic security conjectures that are widely accepted, and it also has some nice properties that we’ll mention shortly. The basic structure of the protocol involves three phases: Commit-Challenge-Response . If you are familiar with challenge-response authentication protocols this just adds an additional commitment message at the start. Alice (for it is she!) wants to prove to Bob who she is. Alice already has a long-term private key, a , and Bob already has the corresponding public key, A . These keys are in a Diffie-Hellman-like finite field or elliptic curve group, so we can say A = g^a mod p where g is a generator and p is the prime modulus of the group. The protocol then works like this: Don’t worry if you don’t understand all this. I’ll probably do a blog post about Schnorr identification at some point, but there are plenty of explainers online if you want to understand it. For now, just accept that this is indeed a secure identification scheme. It has some nice properties too. One is that it is a (honest-verifier) zero knowledge proof of knowledge (of the private key). That means that an observer watching Alice authenticate, and the verifier themselves, learn nothing at all about Alice’s private key from watching those runs, but the verifier is nonetheless convinced that Alice knows it. This is because it is easy to create valid runs of the protocol for any private key by simply working backwards rather than forwards, starting with a response and calculating the challenge and commitment that fit that response. Anyone can do this without needing to know anything about the private key. That is, for any given challenge you can find a commitment for which it is easy to compute the correct response. (What they cannot do is correctly answer a random challenge after they’ve already sent a commitment). So they learn no information from observing a genuine interaction. So what does this identification protocol have to do with digital signatures? The answer is that there is a process known as the Fiat-Shamir heuristic by which you can automatically transform certain interactive identification protocols into a non-interactive signature scheme. You can’t do this for every protocol, only ones that have a certain structure, but Schnorr identification meets the criteria. The resulting signature scheme is known, amazingly, as the Schnorr signature scheme. You may be relieved to hear that the Fiat-Shamir transformation is incredibly simple. We basically just replace the challenge part of the protocol with a cryptographic hash function, computed over the message we want to sign and the commitment public key: c = H(R, m) . That’s it. The signature is then just the pair (R, s). Note that Bob is now not needed in the process at all and Alice can compute this all herself. To validate the signature, Bob (or anyone else) recomputes c by hashing the message and R and then performs the verification step just as in the identification protocol. Schnorr signatures built this way are secure (so long as you add some critical security checks!) and efficient. The EdDSA signature scheme is essentially just a modern incarnation of Schnorr with a few tweaks. The way I’ve just presented Schnorr signatures and Fiat-Shamir is the way they are usually presented in cryptography textbooks. We start with an identification protocol, performed a simple transformation and ended with a secure signature scheme. Happy days! These textbooks then usually move on to all the ways you can use signatures and never mention identification protocols again. But the transformation isn’t an entirely positive process: a lot was lost in translation! There are many useful aspects of interactive identification protocols that are lost by signature schemes: These points may sound like bonuses for signature schemes, but they are actually drawbacks in many cases. Signatures are often used for authentication, where we actually want things to be tied to a specific interaction. This lack of context in signatures is why standards like JWT have to add lots of explicit statements such as audience and issuer checks to ensure the JWT came from the expected source and arrived at the intended destination, and expiry information or unique identifiers (that have to be remembered) to prevent replay attacks. A significant proportion of JWT vulnerabilities in the wild are caused by developers forgetting to perform these checks. WebAuthn is another example of this phenomenon. On paper it is a textbook case of an identification protocol. But because it is built on top of digital signatures it requires adding a whole load of “contextual bindings” for similar reasons to JWTs. Ironically, the most widely used WebAuthn signature algorithm, ECDSA, is itself a Schnorr-ish scheme. TLS also uses signatures for what is essentially an identification protocol, and similarly has had a range of bugs due to insufficient context binding information being included in the signed data. (SSL also uses signatures for verifying certificates, which is IMO a perfectly good use of the technology. Certificates are exactly a case of where you want to convert an interactive protocol into a non-interactive one. But then again we also do an interactive protocol (DNS) in that case anyway :shrug:). In short, an awful lot of uses of digital signatures are actually identification schemes of one form or another and would be better off using an actual identification scheme. But that doesn’t mean using something like Schnorr’s protocol! There are actually better alternatives that I’ll come back to at the end. Before I look at alternatives, I want to point out that pretty much all in-use signature schemes are extremely fragile in practice. The zero-knowledge security of Schnorr identification is based on it having a property called special soundness . Special soundness essentially says that if Alice accidentally reuses the same commitment (R) for two runs of the protocol, then any observer can recover her private key. This sounds like an incredibly fragile notion to build into your security protocol! If I accidentally reuse this random value then I leak my entire private key??! And in fact it is: such nonce-reuse bugs are extremely common in deployed signature systems, and have led to compromise of lots of private keys (eg Playstation 3, various Bitcoin wallets etc). But despite its fragility, this notion of special soundness is crucial to the security of many signature systems. They are truly a cursed technology! To solve this problem, some implementations and newer standards like EdDSA use deterministic commitments, which are based on a hash of the private key and the message. This ensures that the commitment will only ever be the same if the message is identical: preventing the private key from being recovered. Unfortunately, such schemes turned out to be more susceptible to fault injection attacks (a much less scalable or general attack vector), and so now there are “hedged” schemes that inject a bit of randomness back into the hash. It’s cursed turtles all the way down. If your answer to this is to go back to good old RSA signatures, don’t be fooled. There are plenty of ways to blow your foot off using old faithful, but that’s for another post. Another way that signatures cause issues is that they are too powerful for the job they are used for. You just wanted to authenticate that an email came from a legitimate server, but now you are providing irrefutable proof of the provenance of leaked private communications . Oops! Signatures are very much the hammer of cryptographic primitives. As well as authenticating a message, they also provide third-party verifiability and (part of) non-repudiation . You don’t need to explicitly want anonymity or deniability to understand that these strong security properties can have damaging and unforeseen side-effects. Non-repudiation should never be the default in open systems. I could go on. From the fact that there are basically zero acceptable post-quantum signature schemes (all way too large or too risky), to issues with non-canonical signatures and cofactors and on and on. The problems of signature schemes never seem to end. Ok, so if signatures are so bad, what can I use instead? Firstly, if you can get away with using a simple shared secret scheme like HMAC, then do so. In contrast to public key crypto, HMAC is possibly the most robust crypto primitive ever invented. You’d have to go really far out of your way to screw up HMAC. (I mean, there are timing attacks and that time that Bouncy Castle confused bits and bytes and used 16-bit HMAC keys, so still do pay attention a little bit…) If you need public key crypto, then… still use HMAC. Use an authenticated KEM with X25519 to generate a shared secret and use that with HMAC to authenticate your message. This is essentially public key authenticated encryption without the actual encryption. (Some people mistakenly refer to such schemes as designated verifier signatures , but they are not). Signatures are good for software/firmware updates and pretty terrible for everything else. Alice generates a random ephemeral key , r , and the corresponding public key R = g^r mod p . She sends R to Bob as the commitment . Bob stores R and generates a random challenge, c and sends that to Alice. Alice computes s = ac + r and sends that back to Bob as the response. Finally, Bob checks if g^s = A^c * R (mod p ). If it is then Alice has successfully authenticated, otherwise it’s an imposter. The reason this works is that g^s = g^(ac + r) and A^c * R = (g^a)^c * g^r = g^(ac + r) too. Why it’s secure is another topic for another day. A protocol run is only meaningful for the two parties involved in the interaction (Alice and Bob). By contrast a signature is equally valid for everyone. A protocol run is specific to a given point in time. Alice’s response is to a specific challenge issued by Bob just prior. A signature can be verified at any time.

Crypto security Security
0 views
bitonic's blog. 1 years ago

Message authentication codes for safer distributed transactions

I've been developing and quickly deploying a distributed system, which is a class of software where bugs are expensive. A few hundred petabytes later, we haven't lost a single byte of data, also thanks to a simple trick which catches a large class of bugs when delegating responsibilities to possibly buggy software. It's a neat use of cryptography beyond security, so here's a small description.

security Security Crypto
0 views