In late 2022, I blogged about the work needed to develop a specification for end-to-end encryption for the fediverse. I sketched out some of the key management components on GitHub, and then the public work abruptly stalled.

A few of you have wondered what’s the deal with that.

This post covers why this effort stalled, what I’m proposing we do next.

What’s The Hold Up?

The “easy” (relatively speaking) parts of the problem are as follows:

1. Secret key management. (This is sketched out already, and provides multiple mechanisms for managing secret key material. Yay!)
2. Bulk encryption of messages and media. (I’ve done a lot of work in this space over the years, so it’s an area I’m deeply familiar with. When we get to this part, it will be almost trivial. I’m not worried about it at all.)
3. Forward-secure ratcheting / authenticated key exchange / group key agreement. (RFC 9420 is a great starting point.)

That is to say, managing secret keys, using secret keys, and deriving shared secret keys are all in the “easy” bucket.

The hard part? Public key management.

CMYKat made this

Why is Public Key Management Hard?

In a centralized service (think: Twitter, Facebook, etc.), this is actually much easier to build: Shove your public keys into a database, and design your client-side software to trust whatever public key your server gives them. Bob’s your uncle, pack it up and go home.

Unfortunately, it’s kind of stupid to build anything that way.

If you explicitly trust the server, the server could provide the wrong public key (i.e., one for which the server knows the corresponding secret key) and you’ll be none the wiser. This makes it trivial for the server to intercept and read your messages.

If your users are trusting you regardless, they’re probably just as happy if you don’t encrypt at the endpoint at all (beyond using TLS, but transport encryption is table stakes for any online service so nevermind that).

But let’s say you wanted to encrypt between peers anyway, because you’re feeling generous (or don’t want to field a bunch of questionably legal demands for user data by law enforcement; a.k.a. the Snapchat threat model).

You could improve endpoint trust by shoving all of your users’ public keys into an append-only data structure; i.e. key transparency, like WhatsApp proposed in 2023:

https://www.youtube.com/watch?v=_N4Q05z5vPE

And, to be perfectly clear, key transparency is a damn good idea.

Key transparency keeps everyone honest and makes it difficult for criminals to secretly replace a victim’s public key, because the act of doing so is unavoidably published to an append-only log.

The primary challenge is scaling a transparency feature to serve a public, federated system.

AJ

Federated Key Transparency?

Despite appearances, I haven’t been sitting on my thumbs for the past year or so. I’ve been talking with cryptography experts about their projects and papers in the same space.

Truthfully, I had been hoping to piggyback off one of those upcoming projects (which is focused more on public key discovery for SAML- and OAuth-like protocols) to build the Federated PKI piece for E2EE for the Fediverse.

Unfortunately, that project keeps getting delayed and pushed back, and I’ve just about run out of patience for it.

Additionally, there are some engineering challenges that I would need to tackle to build atop it, so it’s not as simple as “let’s just use that protocol”, either.

So let’s do something else instead:

Art: ScruffKerfluff

Fediverse Public Key Directories

Orthogonal to the overall Fediverse E2EE specification project, let’s build a Public Key Directory for the Fediverse.

This will not only be useful for building a coherent specification for E2EE (as it provides the “Federated PKI” component we’d need to build it securely), but it would also be extremely useful for software developers the whole world over.

Imagine this:

• If you want to fetch a user’s SSH public key, you can just query for their username and get a list of non-expired, non-revoked public keys to choose from.
• If you wanted public key pinning and key rotation for OAuth2 and/or OpenID Connect identity providers without having to update configurations or re-deploy any applications, you can do that.
• If you want to encrypt a message to a complete stranger, such that only they can decrypt it, without any sort of interaction (i.e., they could be offline for a holiday and still decrypt it when they get back), you could do that.

Oh, and best of all? You can get all these wins without propping up any cryptocurrency bullshit either.

From simple abstractions, great power may bloom.

Mark Miller

How Will This Work?

We need to design a specific kind of server that speaks a limited set of the ActivityPub protocol.

I say “limited” because it will only not support editing or deleting messages provided by another instance. It will only append data.

To understand the full picture, let’s first look at the message types, public key types, and how the message types will be interpreted.

Message Types

Under the ActivityPub layer, we will need to specify a distinct set of Directory Message Types. An opening offer would look like this:

1. [b]AddKey[/b] — contains an Asymmetric Public Key, a number mapped to the user, and instance that hosts it, and some other metadata (i.e., time)
2. [b]RevokeKey[/b] — marks an existing public key as revoked
3. [b]MoveIdentity[/b] — moves all of the public keys from identity A to identity B. This can be used for username changes or instance migrations.

We may choose to allow more message types at the front-end if need be, but that’s enough for our purposes.

Public Key Types

We are not interested in backwards compatibility with every existing cryptosystem. We will only tolerate a limited set of public key types.

At the outset, only Ed25519 will be supported.

In the future, we will include post-quantum digital signature algorithms on this list, but not before the current designs have had time to mature.

RSA will never be included in the set.

ECDSA over NIST P-384 may be included at some point, if there’s sufficient interest in supporting e.g., US government users.

If ECDSA is ever allowed, RFC 6979 is mandatory.

Message Processing

When an instance sends a message to a Directory Server, it will need to contain a specific marker for our protocol. Otherwise, it will be rejected.

Each message will have its own processing rules.

After the processing rules are applied, the message will be stored in the Directory Server, and a hash of the message will be published to a SigSum transparency ledger. The Merkle root and inclusion proofs will be stored in an associated record, attached to the record for the new message.

Every message will have its hash published in SigSum. No exceptions.

We will also need a mechanism for witness co-signatures to be published and attached to the record.

Additionally, all messages defined here are generated by the users, client-side. Servers are not trusted, generally, as part of the overall E2EE threat model.

AddKey

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "action": "AddKey", "message": { "time": "2024-12-31T23:59:59Z", "identity": "foo@mastodon.example.com", "public-key": "ed25519:<key goes here>" }, "signature": "SignatureOfMessage"}

The first AddKey for any given identity will need to be self-signed by the key being added (in addition to ActivityPub messages being signed by the instance).

After an identity exists in the directory, every subsequent public key MUST be signed by a non-revoked keypair.

RevokeKey

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "action": "RevokeKey", "message": { "time": "2024-12-31T23:59:59Z", "identity": "foo@mastodon.example.com", "public-key": "ed25519:<key goes here>" }, "signature": "SignatureOfMessage"}

This marks the public key as untrusted, and effectively “deletes” it from the list that users will fetch.

Important: RevokeKey will fail unless there is at least one more trusted public key for this user. Otherwise, a denial of service would be possible.

Replaying an AddKey for a previously-revoked key MUST fail.

MoveIdentity

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "action": "MoveIdentity", "message": { "time": "2024-12-31T23:59:59Z", "old-identity": "foo@mastodon.example.com", "new-identity": "bar@akko.example.net" }, "signature": "SignatureOfMessage"}

This exists to facilitate migrations and username changes.

Other Message Types

The above list is not exhaustive. We may need other message types depending on the exact feature set needed by the final specification.

Fetching Public Keys

A simple JSON API (and/or an ActivityStream; haven’t decided) will be exposed to query for the currently trusted public keys for a given identity.

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "public-keys": [ { "data": { "time": "2024-12-31T23:59:59Z", "identity": "foo@mastodon.example.com", "public-key": "ed25519:<key goes here>" }, "signature": "SignatureOfData", "sigsum": { /* ... */ }, }, { "data": { /* ... */ }, /* ... */ }, /* ... */ ]}

Simple and easy.

CMYKat

Gossip Between Instances

Directory Servers should be configurable to mirror records from other instances.

Additionally, they should be configurable to serve as Witnesses for the SigSum protocol.

The communication layer here between Directory Servers will also be ActivityPub.

Preventing Abuse

The capability of learning a user’s public key doesn’t imply the ability to send messages or bypass their block list.

Additionally, Fediverse account usernames are (to my knowledge) generally not private, so I don’t anticipate there being any danger in publishing public keys to an append-only ledger.

That said, I am totally open to considering use cases where the actual identity is obfuscated (e.g., HMAC with a static key known only to the instance that hosts them instead of raw usernames).

What About GDPR / Right To Be Forgotten?

Others have previously suggested that usernames might be subject to the “right to be forgotten”, which would require breaking history for an append-only ledger.

After discussing a proposed workaround with a few people in the Signal group for this project, we realized complying necessarily introduced security issues by giving instance admins the capability of selectively remapping the user ID to different audiences, and detecting/mitigating this remapping is annoying.

However, we don’t need to do that in the first place.

According to this webpage about GDPR’s Right to be Forgotten:

However, an organization’s right to process someone’s data might override their right to be forgotten. Here are the reasons cited in the GDPR that trump the right to erasure:

• (…)
• The data is being used to perform a task that is being carried out in the public interest or when exercising an organization’s official authority.
• (…)
• The data represents important information that serves the public interest, scientific research, historical research, or statistical purposes and where erasure of the data would likely to impair or halt progress towards the achievement that was the goal of the processing.

Enabling private communication is in the public interest. The only information that will be stored in the ledger in relation to the username are cryptographic public keys, so it’s not like anything personal (e.g., email addresses or legal names) will be included.

However, we still need to be extremely up-front about this to ensure EU citizens are aware of the trade-off we’re making.

Account Recovery

In the event that a user loses access to all of their secret keys and wants to burn down the old account, they may want a way to start over with another fresh self-signed AddKey.

However, the existing policies I wrote above would make this challenging:

1. Since every subsequent AddKey must be signed by an incumbent key, if you don’t have access to these secret keys, you’re locked out.
2. Since RevokeKey requires one trusted keypair remains in the set, for normal operations, you can’t just burn the set down to zero even while you still had access to the secret keys.

There is an easy way out of this mess: Create a new verb; e.g. BurnDown that an instance can issue that resets all signing keys for a given identity.

The use of BurnDown should be a rare, exceptional event that makes a lot of noise:

• All existing E2EE sessions must break, loudly.
• All other participants must be alerted to the change, through the client software.
• Witnesses and watchdog nodes must take note of this change.

This comes with some trade-offs. Namely: Any account recovery mechanism is a backdoor, and giving the instance operators the capability of issuing BurnDown messages is a risk to their users.

Therefore, users who trust their own security posture and wish to opt out of this recovery feature should also be able to issue a Fireproof message at any point in the process, which permanent and irrevocably prevents any BurnDown from being accepted on their current instance.

If users opt out of recovery and then lose their signing keys, they’re locked out and need to start over with a new Fediverse identity. On the flipside, their instance operator cannot successfully issue a BurnDown for them, so they have to trust them less.

Notice

This is just a rough sketch of my initial ideas, going into this project. It is not comprehensive, nor complete.

There are probably big gaps that need to be filled in, esp. on the ActivityPub side of things. (I’m not as worried about the cryptography side of things.)

How Will This Be Used for E2EE Direct Messaging?

I anticipate that a small pool of Directory Servers will be necessary, due to only public keys and identities being stored.

Additional changes beyond just the existence of Directory Servers will need to be made to facilitate private messaging. Some of those changes include:

• Some endpoint for users to know which Directory Servers a given ActivityPub instance federates with (if any).
• Some mechanism for users to asynchronously exchange Signed Pre-Key bundles for initiating contact. (One for users to publish new bundles, another for users to retrieve a bundle.)
  
  • These will be Ed25519-signed payloads containing an ephemeral X25519 public key.

  
  

This is all outside the scope of the proposal I’m sketching out here today, but it’s worth knowing that I’m aware of the implementation complexity.

The important thing is: I (soatok@furry.engineer) should be able to query pawb.fun, find the Directory Server(s) they federate with, and then query that Directory server for Crashdoom@pawb.fun and get his currently trusted Ed25519 public keys.

From there, I can query pawb.fun for a SignedPreKey bundle, which will have been signed by one of those public keys.

And then we can return to the “easy” pile.

MarleyTanuki

Development Plan

Okay, so that was a lot of detail, and yet not enough detail, depending on who’s reading this blog post.

What I wrote here today is a very rough sketch. The devil is always in the details, especially with cryptography.

Goals and Non-Goals

We want Fediverse users to be able to publish a public key that is bound to their identity, which anyone else on the Internet can fetch and then use for various purposes.

We want to leverage the existing work into key transparency by the cryptography community.

We don’t want to focus on algorithm agility or protocol compatibility.

We don’t want to involve any government offices in the process. We don’t care about “real” identities, nor about codifying falsehoods about names.

We don’t want any X.509 or Web-of-Trust machinery involved in the process.

Tasks

The first thing we would need to do is write a formal specification for a Directory Server (whose job is only to vend Public Keys in an auditable, transparent manner).

Next, we need to actually build a reference implementation of this server, test it thoroughly, and then have security experts pound at the implementation for a while. Any security issues that can be mitigated by design will require a specification update.

We will NOT punt these down to implementors to be responsible for, unless we cannot avoid doing so.

Once these steps are done, we can start rolling the Directory Servers out. At this point, we can develop client-side libraries in various programming languages to make it easy for developers to adopt.

My continued work on the E2EE specification for the Fediverse can begin after we have an implementation of the Directory Server component ready to go.

Timeline

I have a very demanding couple of months ahead of me, professionally, so I don’t yet know when I can commit to starting the Fediverse Directory Server specification work.

Strictly speaking, it’s vaguely possible to get buy-in from work to focus on this project as part of my day-to-day responsibilities, since it has immediate and lasting value to the Internet.

However, I don’t want to propose it because that would be crossing the professional-personal streams in a way I’m not really comfortable with.

The last thing I need is angry Internet trolls harassing my coworkers to try to get under my fur, y’know?

If there is enough interest from the broader Fediverse community, I’m also happy to delegate this work to anyone interested.

Once the work can begin, I don’t anticipate it will take more than a week for me to write a specification that other crypto nerds will take seriously.

I am confident in this because most of the cryptography will be constrained to hash functions, preventing canonicalization and cross-protocol attacks, and signatures.

Y’know, the sort of thing I write about on my furry blog for fun!

Building a reference implementation will likely take a bit longer; if, for no other reason, than I believe it would be best to write it in Go (which has the strongest SigSum support, as of this writing).

This is a lot of words to say, as far as timelines go:

CMYKat

How to Get Involved

Regardless of whether my overall E2EE proposal gets adopted, the Directory Server component is something that should be universally useful to the Fediverse and to software developers around the world.

If you are interested in participating in any technical capacity, I have just created a Signal Group for discussing and coordinating efforts.

All of these efforts will also be coordinated on the fedi-e2ee GitHub organization.

The public key directory server’s specification will eventually exist in this GitHub repository.

Can I Contribute Non-Technically?

Yes, absolutely. In the immediate future, once it kicks off, the work is going to be technology-oriented.

However, we may need people with non-technical skills at some point, so feel free to dive in whenever you feel comfortable.

What About Financially?

If you really have money burning a hole in your pocket and want to toss a coin my way, I do have a Ko-Fi. Do not feel pressured at all to do so, however.

Because I only use Ko-Fi as a tip jar, rather than as a business, I’m not specifically tracking which transaction is tied to which project, so I can’t make any specific promises about how any of the money sent my way will be allocated.

What I will promise, however, is that any icons/logos/etc. created for this work will be done by an artist and they will be adequately compensated for their work. I will not use large-scale computing (a.k.a., “Generative AI”) for anything.

Closing Thoughts

What I’ve sketched here is much simpler (and more ActivityPub-centric) than the collaboration I was originally planning.

Thanks for being patient while I tried, in vain, to make that work.

As of today, I no longer think we need to wait for them. We can build this ourselves, for each other.

https://soatok.blog/2024/06/06/towards-federated-key-transparency/

#cryptography #endToEndEncryption #fediverse #KeyTransparency #Mastodon #MerkleTrees #PublicKeys

Dhole Moments

2022-11-22 10:57:46

Update (2024-06-06): There is an update on this project.

---

As Twitter’s new management continues to nosedive the platform directly into the ground, many people are migrating to what seem like drop-in alternatives; i.e. Cohost and Mastodon. Some are even considering new platforms that none of us have heard of before (one is called “Hive”).

Needless to say, these are somewhat chaotic times.

One topic that has come up several times in the past few days, to the astonishment of many new Mastodon users, is that Direct Messages between users aren’t end-to-end encrypted.

And while that fact makes Mastodon DMs no less safe than Twitter DMs have been this whole time, there is clearly a lot of value and demand in deploying end-to-end encryption for ActivityPub (the protocol that Mastodon and other Fediverse software uses to communicate).

However, given that Melon Husk apparently wants to hurriedly ship end-to-end encryption (E2EE) in Twitter, in some vain attempt to compete with Signal, I took it upon myself to kickstart the E2EE effort for the Fediverse.

https://twitter.com/elonmusk/status/1519469891455234048

So I’d like to share my thoughts about E2EE, how to design such a system from the ground up, and why the direction Twitter is heading looks to be security theater rather than serious cryptographic engineering.

If you’re not interested in those things, but are interested in what I’m proposing for the Fediverse, head on over to the GitHub repository hosting my work-in-progress proposal draft as I continue to develop it.

How to Quickly Build E2EE

If one were feeling particularly cavalier about your E2EE designs, they could just generate then dump public keys through a server they control, pass between users, and have them encrypt client-side. Over and done. Check that box.

Every public key would be ephemeral and implicitly trusted, and the threat model would mostly be, “I don’t want to deal with law enforcement data requests.”

Hell, I’ve previously written an incremental blog post to teach developers about E2EE that begins with this sort of design. Encrypt first, ratchet second, manage trust relationships on public keys last.

If you’re catering to a slightly tech-savvy audience, you might throw in SHA256(pk1 + pk2) -> hex2dec() and call it a fingerprint / safety number / “conversation key” and not think further about this problem.

Look, technical users can verify out-of-band that they’re not being machine-in-the-middle attacked by our service.

An absolute fool who thinks most people will ever do this

From what I’ve gathered, this appears to be the direction that Twitter is going.

https://twitter.com/wongmjane/status/1592831263182028800

Now, if you’re building E2EE into a small hobby app that you developed for fun (say: a World of Warcraft addon for erotic roleplay chat), this is probably good enough.

If you’re building a private messaging feature that is intended to “superset Signal” for hundreds of millions of people, this is woefully inadequate.

https://twitter.com/elonmusk/status/1590426255018848256

Art: LvJ

If this is, indeed, the direction Musk is pushing what’s left of Twitter’s engineering staff, here is a brief list of problems with what they’re doing.

1. Twitter Web. How do you access your E2EE DMs after opening Twitter in your web browser on a desktop computer?
   
   • If you can, how do you know twitter.com isn’t including malicious JavaScript to snarf up your secret keys on behalf of law enforcement or a nation state with a poor human rights record?
   • If you can, how are secret keys managed across devices?
   • If you use a password to derive a secret key, how do you prevent weak, guessable, or reused passwords from weakening the security of the users’ keys?
   • If you cannot, how do users decide which is their primary device? What if that device gets lost, stolen, or damaged?

   
   

2. Authenticity. How do you reason about the person you’re talking with?
3. Forward Secrecy. If your secret key is compromised today, can you recover from this situation? How will your conversation participants reason about your new Conversation Key?
4. Multi-Party E2EE. If a user wants to have a three-way E2EE DM with the other members of their long-distance polycule, does Twitter enable that?
   
   • How are media files encrypted in a group setting? If you fuck this up, you end up like Threema.
   • Is your group key agreement protocol vulnerable to insider attacks?

   
   

5. Cryptography Implementations.
   
   • What does the KEM look like? If you’re using ECC, which curve? Is a common library being used in all devices?
   • How are you deriving keys? Are you just using the result of an elliptic curve (scalar x point) multiplication directly without hashing first?

   
   

6. Independent Third-Party Review.
   
   • Who is reviewing your protocol designs?
   • Who is reviewing your cryptographic primitives?
   • Who is reviewing the code that interacts with E2EE?
   • Is there even a penetration test before the feature launches?

   
   

As more details about Twitter’s approach to E2EE DMs come out, I’m sure the above list will be expanded with even more questions and concerns.

My hunch is that they’ll reuse liblithium (which uses Curve25519 and Gimli) for Twitter DMs, since the only expert I’m aware of in Musk’s employ is the engineer that developed that library for Tesla Motors. Whether they’ll port it to JavaScript or just compile to WebAssembly is hard to say.

How To Safely Build E2EE

You first need to decompose the E2EE problem into five separate but interconnected problems.

1. Client-Side Secret Key Management.
   
   • Multi-device support
   • Protect the secret key from being pilfered (i.e. by in-browser JavaScript delivered from the server)

   
   

2. Public Key Infrastructure and Trust Models.
   
   • TOFU (the SSH model)
   • X.509 Certificate Authorities
   • Certificate/Key/etc. Transparency
   • SigStore
   • PGP’s Web Of Trust

   
   

3. Key Agreement.
   
   • While this is important for 1:1 conversations, it gets combinatorially complex when you start supporting group conversations.

   
   

4. On-the-Wire Encryption.
   
   • Direct Messages
   • Media Attachments
   • Abuse-resistance (i.e. message franking for abuse reporting)

   
   

5. The Construction of the Previous Four.
   
   • The vulnerability of most cryptographic protocols exists in the joinery between the pieces, not the pieces themselves. For example, Matrix.

   
   

This might not be obvious to someone who isn’t a cryptography engineer, but each of those five problems is still really hard.

To wit: The latest IETF RFC draft for Message Layer Security, which tackles the Key Agreement problem above, clocks in at 137 pages.

Additionally, the order I specified these problems matters; it represents my opinion of which problem is relatively harder than the others.

When Twitter’s CISO, Lea Kissner, resigned, they lost a cryptography expert who was keenly aware of the relative difficulty of the first problem.

https://twitter.com/LeaKissner/status/1592937764684980224

You may also notice the order largely mirrors my previous guide on the subject, in reverse. This is because teaching a subject, you start with the simplest and most familiar component. When you’re solving problems, you generally want the opposite: Solve the hardest problems first, then work towards the easier ones.

This is precisely what I’m doing with my E2EE proposal for the Fediverse.

The Journey of a Thousand Miles Begins With A First Step

Before you write any code, you need specifications.

Before you write any specifications, you need a threat model.

Before you write any threat models, you need both a clear mental model of the system you’re working with and how the pieces interact, and a list of security goals you want to achieve.

Less obviously, you need a specific list of non-goals for your design: Properties that you will not prioritize. A lot of security engineering involves trade-offs. For example: elliptic curve choice for digital signatures is largely a trade-off between speed, theoretical security, and real-world implementation security.

If you do not clearly specify your non-goals, they still exist implicitly. However, you may find yourself contradicting them as you change your mind over the course of development.

Being wishy-washy about your security goals is a good way to compromise the security of your overall design.

In my Mastodon E2EE proposal document, I have a section called Design Tenets, which states the priorities used to make trade-off decisions. I chose Usability as the highest priority, because of AviD’s Rule of Usability.

Security at the expense of usability comes at the expense of security.

Avi Douglen, Security StackExchange

Underneath Tenets, I wrote Anti-Tenets. These are things I explicitly and emphatically do not want to prioritize. Interoperability with any incumbent designs (OpenPGP, Matrix, etc.) is the most important anti-tenet when it comes to making decisions. If our end-state happens to interop with someone else’s design, cool. I’m not striving for it though!

Finally, this section concludes with a more formal list of Security Goals for the whole project.

Art: LvJ

Every component (from the above list of five) in my design will have an additional dedicated Security Goals section and Threat Model. For example: Client-Side Secret Key Management.

You will then need to tackle each component independently. The threat model for secret-key management is probably the trickiest. The actual encryption of plaintext messages and media attachments is comparatively simple.

Finally, once all of the pieces are laid out, you have the monumental (dare I say, mammoth) task of stitching them together into a coherent, meaningful design.

If you did your job well at the outset, and correctly understand the architecture of the distributed system you’re working with, this will mostly be straightforward.

Making Progress

At every step of the way, you do need to stop and ask yourself, “If I was an absolute chaos gremlin, how could I fuck with this piece of my design?” The more pieces your design has, the longer the list of ways to attack it will grow.

It’s also helpful to occasionally consider formal methods and security proofs. This can have surprising implications for how you use some algorithms.

You should also be familiar enough with the cryptographic primitives you’re working with before you begin such a journey; because even once you’ve solved the key management story (problems 1, 2 and 3 from the above list of 5), cryptographic expertise is still necessary.

• If you’re feeding data into a hash function, you should also be thinking about domain separation. More information.
• If you’re feeding data into a MAC or signature algorithm, you should also be thinking about canonicalization attacks. More information.
• If you’re encrypting data, you should be thinking about multi-key attacks and confused deputy attacks. Also, the cryptographic doom principle if you’re not using IND-CCA3 algorithms.
• At a higher-level, you should proactively defend against algorithm confusion attacks.

How Do You Measure Success?

It’s tempting to call the project “done” once you’ve completed your specifications and built a prototype, and maybe even published a formal proof of your design, but you should first collect data on every important metric:

1. How easy is it to use your solution?
2. How hard is it to misuse your solution?
3. How easy is it to attack your solution? Which attackers have the highest advantage?
4. How stable is your solution?
5. How performant is your solution? Are the slow pieces the deliberate result of a trade-off? How do you know the balance was struck corectly?

Where We Stand Today

I’ve only begun writing my proposal, and I don’t expect it to be truly ready for cryptographers or security experts to review until early 2023.

However, my clearly specified tenets and anti-tenets were already useful in discussing my proposal on the Fediverse.

@soatok @fasterthanlime Should probably embed the algo used for encryption in the data used for storing the encrypted blob, to support multiples and future changes.

@fabienpenso@hachyderm.io proposes in-band protocol negotiation instead of versioned protocols

The main things I wanted to share today are:

1. The direction Twitter appears to be heading with their E2EE work, and why I think it’s a flawed approach
2. Designing E2EE requires a great deal of time, care, and expertise; getting to market quicker at the expense of a clear and careful design is almost never the right call

Mastodon? ActivityPub? Fediverse? OMGWTFBBQ!

In case anyone is confused about Mastodon vs ActivityPub vs Fediverse lingo:

The end goal of my proposal is that I want to be able to send DMs to queer furries that use Mastodon such that only my recipient can read them.

Achieving this end goal almost exclusively requires building for ActivityPub broadly, not Mastodon specifically.

However, I only want to be responsible for delivering this design into the software I use, not for every single possible platform that uses ActivityPub, nor all the programming languages they’re written in.

I am going to be aggressive about preventing scope creep, since I’m doing all this work for free. (I do have a Ko-Fi, but I won’t link to it from here. Send your donations to the people managing the Mastodon instance that hosts your account instead.)

My hope is that the design documents and technical specifications become clear enough that anyone can securely implement end-to-end encryption for the Fediverse–even if special attention needs to be given to the language-specific cryptographic libraries that you end up using.

Art: LvJ

Why Should We Trust You to Design E2EE?

This sort of question comes up inevitably, so I’d like to tackle it preemptively.

My answer to every question that begins with, “Why should I trust you” is the same: You shouldn’t.

There are certainly cryptography and cybersecurity experts that you will trust more than me. Ask them for their expert opinions of what I’m designing instead of blanketly trusting someone you don’t know.

I’m not interested in revealing my legal name, or my background with cryptography and computer security. Credentials shouldn’t matter here.

If my design is good, you should be able to trust it because it’s good, not because of who wrote it.

If my design is bad, then you should trust whoever proposes a better design instead. Part of why I’m developing it in the open is so that it may be forked by smarter engineers.

Knowing who I am, or what I’ve worked on before, shouldn’t enter your trust calculus at all. I’m a gay furry that works in the technology industry and this is what I’m proposing. Take it or leave it.

Why Not Simply Rubber-Stamp Matrix Instead?

(This section was added on 2022-11-29.)

There’s a temptation, most often found in the sort of person that comments on the /r/privacy subreddit, to ask why even do all of this work in the first place when Matrix already exists?

The answer is simple: I do not trust Megolm, the protocol designed for Matrix.

Megolm has benefited from amateur review for four years. Non-cryptographers will confuse this observation with the proposition that Matrix has benefited from peer review for four years. Those are two different propositions.

In fact, the first time someone with cryptography expertise bothered to look at Matrix for more than a glance, they found critical vulnerabilities in its design. These are the kinds of vulnerabilities that are not easily mitigated, and should be kept in mind when designing a new protocol.

You don’t have to take my word for it. Listen to the Security, Cryptography, Whatever podcast episode if you want cryptographic security experts’ takes on Matrix and these attacks.

From one of the authors of the attack paper:

So they kind of, after we disclosed to them, they shared with us their timeline. It’s not fixed yet. It’s a, it’s a bigger change because they need to change the protocol. But they always said like, Okay, fair enough, they’re gonna change it. And they also kind of announced a few days after kind of the public disclosure based on the public reaction that they should prioritize fixing that. So it seems kind of in the near future, I don’t have the timeline in front of me right now. They’re going to fix that in the sense of like the— because there’s, notions of admins and so on. So like, um, so authenticating such group membership requests is not something that is kind of completely outside of, kind of like the spec. They just kind of need to implement the appropriate authentication and cryptography.

Martin Albrecht, SCW podcast

From one of the podcast hosts:

I guess we can at the very least tell anyone who’s going forward going to try that, that like, yes indeed. You should have formal models and you should have proofs. And so there’s this, one of the reactions to kind of the kind of attacks that we presented and also to prior previous work where we kind of like broken some cryptographic protocols is then to say like, “Well crypto’s hard”, and “don’t roll your own crypto.” But in a way the thing is like, you know, we need some people to roll their own crypto because that’s how we have crypto. Someone needs to roll it. But we have developed techniques, we have developed formalisms, we have developed methods for making sure it doesn’t have to be hard, it’s not, it’s not a dark art kind of that only kind of a few, a select few can master, but it’s, you know, it’s a science and you can learn it. So, but you need to then indeed employ a cryptographer in kind of like forming, modeling your protocol and whenever you make changes, then, you know, they need to look over this and say like, Yes, my proof still goes through. Um, so like that is how you do this. And then, then true engineering is still hard and it will remain hard and you know, any science is hard, but then at least you have some confidence in what you’re doing. You might still then kind of on the space and say like, you know, the attack surface is too large and I’m not gonna to have an encrypted backup. Right. That’s then the problem of a different hard science, social science. Right. But then just use the techniques that we have, the methods that we have to establish what we need.

Thomas Ptacek, SCW podcast

It’s tempting to listen to these experts and say, “OK, you should use libsignal instead.”

But libsignal isn’t designed for federation and didn’t prioritize group messaging. The UX for Signal is like an IM application between two parties. It’s a replacement for SMS.

It’s tempting to say, “Okay, but you should use MLS then; never roll your own,” but MLS doesn’t answer the group membership issue that plagued Matrix. It punts on these implementation details.

Even if I use an incumbent protocol that privacy nerds think is good, I’ll still have to stitch it together in a novel manner. There is no getting around this.

Maybe wait until I’ve finished writing the specifications for my proposal before telling me I shouldn’t propose anything.

---

Credit for art used in header: LvJ, Harubaki

https://soatok.blog/2022/11/22/towards-end-to-end-encryption-for-direct-messages-in-the-fediverse/

#endToEndEncryption #Twitter

Let’s talk about digital signature algorithms.

Digital signature algorithms are one of the coolest ideas to come out of asymmetric (a.k.a. public-key) cryptography, but they’re so simple and straightforward that most cryptography nerds don’t spend a lot of time thinking about them.

Even though you are more likely to run into a digital signature as a building block (e.g. certificate signatures in TLS) than think about them in isolation (e.g. secure software releases), they’re still really cool and worth learning about.

What’s a Digital Signature?

A digital signature is some string that proves that a specific message was signed by some specific entity in possession of the secret half of an asymmetric key-pair. Digital Signature Algorithms define the process for securely signing and verifying messages with their associated signatures.

For example, if I have the following keypair:

• Secret key: 9080a2c7897faeb8526968161695da0f7b3afa2e8e7d8e8369a85547ab48ea05
• Public key: 482b8d3430445cdad6b5ce59778e09ab59d099120f32d316e881db1a6330390b

I can cryptographically sign the message “Dhole Moments: Never a dull moment!” with the above secret key, and it will generate the signature string: 63629779a31b623486145359c6f1d56602d8d9135e4b17fa2ae3667c8947397decd7ae01bfed08645a429f5dee906e87df4e18eefdfff9acb5b1488c9dec800f.

If you only have the message, signature string, and my public key, you can verify that I signed the message. But, very crucially, you cannot sign messages and convince someone else that they came from me. (With symmetric authentication schemes, such as HMAC, you can.)

A digital signature algorithm is considered secure if, in order for anyone else to pass off a different message as being signed by me, they would need my secret key to succeed. When this assumption holds true, we say the scheme is secure against existential forgery attacks.

How Do Digital Signatures Work?

Simple answer: They generally combine a cryptographic hash function (e.g. SHA-256) with some asymmetric operation, and the details beyond that are all magic.

More complicated answer: That depends entirely on the algorithm in question!

Art by Swizz

For example, with RSA signatures, you actually encrypt a hash of the message with your secret key to sign the message, and then you RSA-decrypt it with your public key to verify the signature. This is backwards from RSA encryption (where you do the totally sane thing: encrypt with public key, decrypt with secret key).

In contrast, with ECDSA signatures, you’re doing point arithmetic over an elliptic curve (with a per-signature random value).

Yet another class of digital signature algorithms are hash-based signatures, such as SPHINCS+ from the NIST Post-Quantum Cryptography Standardization effort, wherein your internals consist entirely of hash functions (and trees of hash functions, and stream ciphers built with other hash functions).

In all cases, the fundamental principle stays the same: You sign a message with a secret key, and can verify it with a public key.

In the interest of time, I’m not going to dive deep into how each signature algorithm works. That can be the subject of future blog posts (one for each of the algorithms in question).

Quick aside: Cryptographers who stumble across my blog might notice that I deviate from convention a bit. They typically refer to the sensitive half of an asymmetric key pair as a “private key”, but I instead call it a “secret key”.

The main reason for this is that “secret key” can be abbreviated as “sk” and public key can be abbreviated as “pk”, whereas private/public doesn’t share this convenience. If you ever come across their writings and wonder about this discrepancy, I’m breaking away from the norm and their way is more in line with the orthodoxy.

What Algorithms Should I Use?

What algorithm, indeed! (Art by circuitslime)

If you find yourself asking this question, you’re probably dangerously close to rolling your own crypto. If so, you’ll want to hire a cryptographer to make sure your designs aren’t insecure. (It’s extremely easy to design or implement otherwise-secure cryptography in an insecure way.)

Recommended Digital Signature Algorithms

(Update, 2022-05-19): I’ve published a more in-depth treatment of the Elliptic Curve Digital Signature Algorithms a few years after this post was created. A lot of the topics covered by EdDSA and ECDSA are focused on there.

EdDSA: Edwards Curve DSA

EdDSA comes in two variants: Ed25519 (widely supported in a lot of libraries and protocols) and Ed448 (higher security level, but not implemented or supported in as many places).

The IETF standardized EdDSA in RFC 8032, in an effort related to the standardization of RFC 7748 (titled: Elliptic Curves for Security).

Formally, EdDSA is derived from Schnorr signatures and defined over Edwards curves. EdDSA’s design was motivated by the real-world security failures of ECDSA:

1. Whereas ECDSA requires a per-signature secret number () to protect the secret key, EdDSA derives the per-signature nonce deterministically from a hash of the secret key and message.
2. ECDSA with biased nonces can also leak your secret key through lattice attacks. To side-step this, EdDSA uses a hash function twice the size as the prime (i.e. SHA-512 for Ed25519), which guarantees that the distribution of the output of the modular reduction is unbiased (assuming uniform random inputs).
3. ECDSA implemented over the NIST Curves is difficult to implement in constant-time: Complicated point arithmetic rules, point division, etc. EdDSA only uses operations that are easy to implement in constant-time.

For a real-world example of why EdDSA is better than ECDSA, look no further than the Minerva attacks, and the Ed25519 designer’s notes on why EdDSA stood up to the attacks.

The security benefits of EdDSA over ECDSA are so vast that FIPS 186-5 is going to include Ed25519 and Ed448.

Hooray for EdDSA adoption even in federal hellscapes.

This is kind of a big deal! The FIPS standards are notoriously slow-moving, and they’re deeply committed to a sunk cost fallacy on algorithms they previously deemed acceptable for real-world deployment.

RFC 6979: Deterministic ECDSA

Despite EdDSA being superior to ECDSA in virtually every way (performance, security, misuse-resistance), a lot of systems still require ECDSA support for the foreseeable future.

If ECDSA is here to stay, we might as well make it suck less in real-world deployments. And that’s exactly what Thomas Pornin did when he wrote RFC 6979: Deterministic Usage of DSA and ECDSA.

(Like EdDSA, Deterministic ECDSA is on its way to FIPS 186-5. Look for it in FIPS-compliant hardware 5 years from now when people actually bother to update their implementations.)

Acceptable Digital Signature Algorithms

ECDSA Signatures

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the incumbent design for signatures. Unlike EdDSA, ECDSA is a more flexible design that has been applied to many different types of curves.

This is more of a curse than a blessing, as Microsoft discovered with CVE-2020-0601: You could take an existing (signature, public key) pair with standard curve, explicitly set the generator point equal to the victim’s public key, and set your secret key to 1, and Windows’s cryptography library would think, “This is fine.”

For this reason, cryptographers were generally wary of proposals to add support for Koblitz curves (including secp256k1–the Bitcoin curve) or Brainpool curves into protocols that are totally fine with NIST P-256 (and maybe NIST P-384 if you need it for compliance reasons).

For that reason, if you can’t use EdDSA or RFC 6979, your fallback option is ECDSA with one of those two curves (secp256r1, secp384r1), and making sure that you have access to a reliable cryptographic random number generator.

RSA Signatures

It’s high time the world stopped using RSA.

Not just for the reasons that Trail of Bits is arguing (which I happen to agree with), but more importantly:

Replacing RSA with EdDSA (or Deterministic ECDSA) also gives teams an opportunity to practice migrating from one cryptography algorithm suite to another, which will probably be a much-needed experience when quantum computers come along and we’re all forced to migrate to post-quantum cryptography.

Encryption is a bigger risk of being broken by quantum computers than signature schemes: If you encrypt data today, a quantum computer 20 years down the line can decrypt it immediately. Conversely, messages that are signed today cannot be broken until after a quantum computer exists.

That being said, if you only need signatures and not encryption, RSA is still acceptable. If you also need encryption, don’t use RSA for that purpose.

If you can, use PSS padding rather than PKCS#1 v1.5 padding, with SHA-256 or SHA-384. But for signatures (i.e. not encryption), PKCS#1 v1.5 padding is fine.

Dishonorable Mention

DSA Signatures

There’s really no point in using classical DSA, when ECDSA is widely supported and has more ongoing attention from cryptography experts.

If you’re designing a system in 2020 that uses DSA, my only question for you is…

WHYYYYYY?! (Art by Khia)

Upcoming Signature Algorithms

Although it is far too early to consider adopting these yet, cryptographers are working on new designs that protect against wider ranges of real-world threats.

Let’s briefly look at some of them and speculate wildly about what the future looks like. For fun. Don’t use these yet, unless you have a very good reason to do so.

Digital Signature Research Topics

Hedged Signatures

Above, we concluded that EdDSA and Deterministic ECDSA were generally the best choice (and what I’d recommend for software developers). There is one important caveat: Fault attacks.

A fault attack is when you induce a hardware fault into a computer chip, and thereby interfere with the correct functioning of a cryptography algorithm. This is especially relevant to embedded devices and IoT.

The IETF’s CFRG is investigating the use of additional randomization of messages (rather than randomizing signatures) as a safeguard against leaking secret keys through fault injection.

Of course, the Dhole Cryptography Library (my libsodium wrapper for JavaScript and PHP) already provides a form of Hedged Signatures.

If this technique is proven successful at mitigating fault injection attacks, then libsodium users will be able to follow the technique outlined in Dhole Crypto to safeguard their own protocols against fault attacks. Until then, they’re at least as safe as deterministic EdDSA today.

Threshold ECDSA Signatures

Suppose you have a scenario where you want 3-or-more people to have to sign a message before it’s valid. That’s exactly what Threshold ECDSA with Fast Trustless Setup aspires to provide.

Although this is mostly being implemented in cryptocurrency projects today, the cryptography underpinnings are fascinating. At worst, this will be one good side-effect to come from blockchain mania.

Post-Quantum Digital Signatures

Hash-Based Signatures

The best hash-based signature schemes are based on the SPHINCS design for one simple reason: It’s stateless.

In earlier hash-based digital signatures, such as XMSS, you have to maintain a state of which keys you’ve already used, to prevent attacks. Google’s Adam Langley previously described this as a “huge foot-cannon” for security (although probably okay in some environments, such as an HSM).

Lattice-Based Signatures

There are a lot of post-quantum signature algorithm designs defined over lattice groups, but my favorite lattice-based design is called FALCON. FALCON stands for FAst-Fourier Lattice-based COmpact Signatures Over NTRU.

Sign Here, Please

Who knew there would be so much complexity involved with such a simple cryptographic operation? And we didn’t even dive deep on how any of them work.

That’s the problem with cryptography: It’s a fractal of complexity. The more you know about these topics, the deeper the complexity becomes.

But if you’re implementing a protocol today and need a digital signature algorithm, use (in order of preference):

1. Ed25519 or Ed448
2. ECDSA over NIST P-256 or P-384, with RFC 6979
3. ECDSA over NIST P-256 or P-384, without RFC 6979
4. RSA (as a last resort)

But most importantly: make sure you have a cryptographer audit your designs.

(Header art by Kyume.)

https://soatok.blog/2020/04/26/a-furrys-guide-to-digital-signature-algorithms/

#crypto #cryptography #DeterministicSignatures #digitalSignatureAlgorithm #ECDSA #Ed25519 #Ed448 #EdDSA #FIPS #FIPS186 #FIPSCompliance #RFC6979 #SecurityGuidance

Dhole Moments

2022-05-19 07:36:36

Earlier this year, Cendyne published A Deep Dive into Ed25519 Signatures, which covered some of the different types of digital signature algorithms, but mostly delved into the Ed25519 algorithm. Truth in advertising.

This got me thinking, “Why isn’t there a better comparison of different elliptic curve signature algorithms available online?”

Art: LvJ

Most people just defer to SafeCurves, but it’s a little dated: We have complete addition formulas for Weierstrass curves now, but SafeCurves doesn’t reflect that.

For the purpose of simplicity, I’m not going to focus on a general treatment of Elliptic Curve Cryptography (ECC), which includes pairing-based cryptography, Elliptic-Curve Diffie-Hellman, and (arguably) isogeny cryptography.

Instead, I’m going to focus entirely on elliptic curve digital signature algorithms.

Note: The content of this post is a bit lower-level than most programmers ever need to be concerned with. If you’re a programmer and interested in learning cryptography, start here. If you’re looking for library recommendations, libsodium is a good safe default.

Compliance Rules Everything Around Me

If you have to meet some arbitrary compliance requirements (i.e. FIPS 140-3, CNSA, etc.), your decision is already made for you, and you shouldn’t waste your time reading blogs like this that will only get your hopes up about the options available to you.

Choose the option your compliance officer demands, and hope it’s good enough.

“Sure, let me check that box.”
Art: LvJ

Elliptic Curves for Signature Algorithms

Let’s start with the same curve Cendyne analyzed: Ed25519.

Ed25519 (EdDSA, Curve25519)

Ed25519 is one of the two digital signature algorithms today that use the EdDSA algorithm framework. The other is Ed448, which targets a higher security level (224-bit vs 128-bit) but is also slower and uses SHAKE256 (which is overkill and not great for performance).

Ed25519 is a safe default choice for most applications where a digital signature is appropriate, for many reasons:

1. Ed25519 uses deterministic nonces, which means you’re severely unlikely to ever reproduce the Sony ECDSA k-reuse bug in your system.
   The deterministic nonce is calculated from the SHA512 hash of the secret key and message. Two invocations to crypto_sign_ed25519() with the same message and secret key will produce the same signature, but the intermediate nonce value is never revealed to an attacker.
2. Ed25519 includes the public key in the data hashed to produce the signature (more specifically s from the (R,s) pair). This offers a property that ECDSA lacks: Exclusive Ownership. I’ve written about this property before.
   Without Exclusive Ownership, it’s possible to create a single signature value that’s valid for multiple different (message, public key) pairs.

Years ago, there would have an additional list item: Ed25519 uses Edward Curves, which have complete addition formulas and are therefore safer to implement in constant-time than Weierstrass curves (i.e. the NIST curves). However, we now have complete addition formulas for Weierstrass curves, so this has become a moot point (assuming your implementation uses complete addition formulas).

Ed25519 targets the 128-bit security level.

Why Not Use Ed25519?

There is one minor pitfall of Ed25519 that makes it unsuitable for esoteric uses (say, Ring Signature Schemes or zero-knowledge proofs): Ed25519 is not a prime-order group; it has a cofactor h = 8. This detail famously created a double-spend vulnerability in all CryptoNote-based cryptocurrencies (including Monero).

For systems that want the security of Ed25519 and its various well-studied implementations, but still need a prime-order group for their protocol, cryptographers have developed the Ristretto Group to meet your needs.

If you’re working on embedded systems, the determinism inherent to EdDSA might be undesirable due to the possibility of fault attacks. You can use a hedged variant of Ed25519 to mitigate this risk.

Additionally, Ed25519 is not approved for many government applications, although it did make the latest draft revision of FIPS 186 in 2019. If you care about compliance (see above), you cannot use Ed25519. Yet.

A niche Internet meme for cryptography engineers

Guidance for Ed25519

Unless legally prohibited, Ed25519 should be your default choice, unless you need a prime-order group. In that case, build your desired protocol atop Ristretto255.

If you’re not sure if you need a prime-order group, you probably don’t. It’s a specialized requirement for uncommon use cases (ring signatures, password authenticated key exchange protocols, zero-knowledge proofs, etc.).

Art: LvJ

The Bitcoin Curve (ECDSA, secp256k1)

Secp256k1 is a Koblitz curve, which is a special case of Weierstrass curves that are more performant when used in binary fields, of the form, . This curve is almost exclusively used in cryptocurrency software.

There is no specified reason why Bitcoin chose secp256k1 over another elliptic curve at the time of its inception, but we can speculate:

The author was a pseudonymous contributor to the Metzdowd mailing list for cypherpunks, and probably didn’t trust the NIST curves. Since Ed25519 didn’t exist at the time, the only obvious choice for a hipster elliptic curve parameter selection was to rely on the SECG recommendations, which specify the NIST and Koblitz curves. If you cross the NIST curves off the list, only the Koblitz curves remained.

Therefore, the selection of secp256k1 is likely an artefact of computer history and not a compelling reason to select secp256k1 in new designs. Please look elsewhere.

Fact: Imgflip didn’t have a single secp256k1 meme until I made this one.

Secp256k1 targets the 128-bit security level.

Guidance for secp256k1

Don’t bother, there are better options. (i.e. Ed25519)

If you’re writing software for a cryptocurrency-related project, and you feel compelled to use secp256k1 for the sake of reducing your code footprint, please strongly consider the option of burning everything to the proverbial ground.

Cryptocurrency sucks!
Art: Swizz

Cryptocurrency Aside, Why Avoid Secp256k1?

As we noted above, secp256k1 isn’t widely used outside of cryptocurrency.

As a direct consequence of this (as we’ll discuss in the NIST P-256 section), most cryptography libraries don’t offer optimized, side-channel-resistant implementations of secp256k1; even if they do offer optimized implementations of NIST P-256.

(Meanwhile, Ed25519 is designed to be side-channel and misuse-resistant, partly due to its Schnorr construction and constant-time ladder for scalar multiplication, so any library that implements Ed25519 is overwhelmingly likely to be constant-time.)

Therefore, any secp256k1 library for most programming languages that isn’t an FFI wrapper for libsecp256k1 will have worse performance than the other 256-bit curves.

https://twitter.com/bascule/status/1320183684935290882

Additionally, secp256k1 implementations are often a source of exploitable side-channels that permit attackers to pilfer your secret keys.

The previously linked article was about BouncyCastle’s implementation (which covers Java and .NET), but there’s still plenty of secp256k1 implementations that don’t FFI libsecp256k1.

From a quick Google Search:

• Python (uses EEA rather than Binary GCD for modular inverse)
• Go (uses Numbers, which weren’t designed for cryptography)
• PHP (uses GMP, which isn’t constant-time)
• JavaScript (calls here, which uses bn.js, which isn’t constant-time)

If you’re using secp256k1, and you’re not basing your choice on cybercash-interop, you’re playing with fire at the implementation and ecosystem levels–even if there are no security problems with the Koblitz curve itself.

You are much better off choosing any different curve than secp256k1 if you don’t have a Bitcoin/Ethereum/etc. interoperability requirement.

“No thanks, I use Ed25519.”
Art: LvJ

NIST P-256 (ECDSA, secp256r1)

NIST P-256 is the go-to curve to use with ECDSA in the modern era. Unlike Ed25519, P-256 uses a prime-order group, and is an approved algorithm to use in FIPS-validated modules.

Most cryptography libraries offer optimized assembly implementations of NIST P-256, which makes it less likely that your signing operations will leak timing information or become a significant performance bottleneck.

P-256 targets the 128-bit security level.

Why Not Use P-256?

Once upon a time, P-256 was riskier than Ed25519 (for signatures) and X25519 (for Diffie-Hellman), due to the incomplete addition formulas that led to timing-leaky implementations.

If you’re running old software, you may still be vulnerable to timing attacks that can recover your ECDSA secret key. However, there is a good chance that you’re on a modern and secure implementation in 2022, especially if you’re outsourcing this to OpenSSL or its derivatives.

ECDSA requires a secure randomness source to sign data. If you don’t have one available, and you sign anything, you’re coughing up your secret key to any attacker capable of observing multiple signatures.

Guidance for P-256

P-256 is an acceptable choice, especially if you’re forced to cope with FIPS and/or the CNSA suite requirements when using cryptography.

Of course, if you can get away with Ed25519, use Ed25519 instead.

If you use P-256, make sure you’re using it with SHA-256. Some implementations may default to something weaker (e.g. SHA-1).

If you’re also going to be performing ECDH with P-256, make sure you use compressed points. There used to be a patent; it died in 2018.

If you can afford it, make sure you use deterministic ECDSA (RFC 6979) or hedged signatures (if fault attacks are relevant to your threat model).

Art: LvJ

NIST P-384 (ECDSA, secp384r1)

NIST P-384 has a larger field than the curves we’ve previously examined, which allows P-384 to target the 192-bit security level. That’s the primary reason why anyone would choose P-384.

Naturally, elliptic curve security is more complicated than merely security against the Elliptic Curve Discrete Logarithm Problem (ECDLP).

P-384 is most often paired with SHA-384, which is the most widely used flavor of the SHA-2 family hash functions that isn’t susceptible to length-extension attacks. (There are also truncated SHA-512 variants specified later, but that’s also what SHA-384 is under-the-hood.)

If you’re aiming to build a “secure-by-default” tool for a system that the US government might one day become a customer of, with minimal cryptographic primitive choice, using NIST P-384 with SHA-384 makes for a reasonably minimalistic bundle.

Why Not Use P-384?

Unlike P-256, most P-384 implementations don’t use constant-time, optimized, and/or formally verified assembly code. (Notable counter-examples: AWS-LC and Go x/crypto.)

Like P-256, P-384 also requires a secure randomness source to sign data. If you aren’t providing one, expect your signing key to end up on fail0verflow one day.

Guidance for P-384

If you use P-384, make sure you’re using it with SHA-384.

The standard NIST curve advice of RFC 6979 and point compression and/or hedged signatures applies here too.

Art: Kyume

NIST P-521 (ECDSA, secp521r1)

Biggest curve is best curve! — the clueless

https://www.youtube.com/watch?v=i_APoSfCYwU

Systems that choose P-521 often have an interesting threat model, even though said threat model is rarely formally specified.

It’s overwhelmingly likely that what eventually breaks the 256-bit elliptic curves will also break P-521 in short order: Cryptography Relevant Quantum Computers.

The only thing P-521 does against CRQCs that P-256 doesn’t is require more quantum memory. If you’re worried about QRQCs, you might want to look into hybrid post-quantum signature schemes.

If you’re choosing P-521 in your designs, you’re basically saying, “I want to have 256 bits of asymmetric cryptographic security, come hell or high water!” even though the 128-bit security level is likely just fine for your actual threats.

Aside: P-521 and 512-bit ECC Security

P-521 is not a typo, although people sometimes think it is. P-521 uses the Mersenne prime instead of a 512-bit near-Mersenne prime.

This has led to an unfortunate trend in cryptography media to map ECC key sizes to symmetric security levels that misleads people as to the relationship between the two. For example:

Source
Source

Regrettably, this is misleading, because plotting the ECC Key Size versus equivalent Symmetric Security isn’t a how ECDLP security works. The ratio of the exponents involved is totally linear; it doesn’t suddenly increase beyond 384-bit curves for a mysterious mathematical reason.

• 256-bit Curves target the 128-bit security level
• 384-bit Curves target the 192-bit security level
• 512-bit Curves target the 256-bit security level
• 521-bit Curves actually target the 260-bit security level, but that meets or exceeds the 256-bit security level, so that’s how the standards are interpreted

The reason for this boils down entirely to the best attack against the Elliptic Curve Discrete Logarithm Problem: Pollard’s Rho, which recovers the secret key from an -bit public key (which has a search space) in guesses.

Taking the square root of a number is the same as halving its exponent, so the security level is half: .

Takeaway: If someone tells you that you need a 521-bit curve to meet the 256-bit security level, they are mistaken and it’s not their fault.

Art: Harubaki

Why Not Use P-521?

It’s slow. Much slower than P-256 and Ed25519. Modestly slower than P-384.

Unlike P-384, you’re less likely to find an optimized, constant-time P-521 implementation.

Guidance for P-521

First, make a concerted effort to figure out the motivation for P-521 in your designs. Chances are, someone is putting too much emphasis on the wrong things for security.

If you use P-521, make sure you’re using it with SHA-512.

The standard NIST curve advice of RFC 6979 and point compression and/or hedged signatures applies here too.

Art: LvJ

Ed448 (EdDSA, Curve448)

Ed448 is the P-521 of the Edwards curves: It mostly exists to give standards committees a psychological comfort for the unlikely event that 256-bit ECC is desperately broken but ECC larger than 384 bits is somehow still safe.

https://twitter.com/dchest/status/703017144053833728

The very concept of having multiple “security levels” for raw cryptography primitives is mostly an artefact of the historical military roots of cryptography, rather than a serious consideration in the modern world.

Unfortunately, this leads to implementations that prioritize runtime algorithm selection negotiation, which maximizes the risk of protocol-level vulnerabilities. See also: JWT.

Ed448 was specified to use SHAKE256, which is a needlessly conservative decision which leads to an unnecessary performance bottleneck.

Why Not Use Ed448?

Aside from the performance hit mentioned previously, there’s no compelling reason to avoid Ed448 that isn’t also true of either Ed25519 or P-384.

Guidance for Ed448

If you want more speed, go with Ed25519. In addition to being faster, Ed25519 is also very widely supported.

If you need a prime-order field, use Decaf with Ed448 or consider P-384.

The Brainpool Curves

The main motivation for the Brainpool curves is that the NIST curves were not generated in a “verifiable pseudo-random way”.

The only reasons you’d ever want to support the Brainpool curves include:

1. You think the NIST curves are somehow backdoored by the NSA
2. You don’t appreciate small attack surfaces in cryptography libraries
3. The German government told you to (see: compliance)

Most of the advice for the NIST Curves at each security level can be copy/pasted for the Brainpool curves, with one important caveat:

When considering real-world implementations, Brainpool curves are more likely to use the general purpose Big Number procedures (which aren’t always constant-time), rather than optimized assembly code, than the NIST curves are.

Therefore, my general guidance for the Brainpool curves is simply:

1. Proceed at your own peril
2. Consider hiring a cryptography engineer to study the implementation you’re relying on, especially with regard to timing attacks

Me when I hear “brainpool”
Art: LvJ

Re-Examining the SafeCurves Criteria

Here’s a 2022 refresh of the SafeCurves criteria for all of the curves considered by this blog post.

SafeCurve Criteria	Relevance to the Curves Listed Above
Fields	All relevant curves satisfy the requirements
Equations	All relevant curves satisfy the requirements
Base Points	All relevant curves satisfy the requirements
Rho	All relevant curves satisfy the requirements
Transfers	All relevant curves satisfy the requirements
Discriminants	Only secp256k1 doesn’t satisfy the requirements (out of the curves listed in this blog post)
Rigidity	The NIST curves do not meet this requirement. If you care about whether or not the standards were manipulated to insert a backdoor, rigidity matters to you. Otherwise, it’s not a deal-breaker.
Ladders	While a Montgomery ladder is beneficial for speed and implementation security, it isn’t strictly speaking required. This is an icing-on-the-cake consideration.
Twists	The only curve listed above that doesn’t meet the requirement is the 256-bit Brainpool curve (brainpoolp256t1).
Completeness	All relevant curves satisfy the requirements, as of 2015. SafeCurves is out of date here.
Indistinguishability	All relevant curves satisfy the requirements, as of 2014.

SafeCurves continues to be a useful resource, especially if you stray from the guidance on this page.

For example: You wouldn’t want to use pairing-friendly curves for general purpose ECC digital signatures, because they’re suitable for specialized problems. SafeCurves correctly recommends not using BN(2,254).

However, SafeCurves is showing its age in 2022. BN curves still end up in digital signature protocol standards even though BLS-12-381 is clearly a better choice.

The Internet would benefit greatly for an updated SafeCurves that focuses on newer elliptic curve algorithms.

Art: Scruff

TL;DR

Ed25519 is great. NIST P-256 and P-384 are okay (with caveats). Anything else is questionable, and their parameter selection should come with a clear justification.

https://soatok.blog/2022/05/19/guidance-for-choosing-an-elliptic-curve-signature-algorithm-in-2022/

#asymmetricCryptography #BrainpoolCurves #cryptography #digitalSignatureAlgorithm #ECDSA #Ed25519 #Ed448 #EdDSA #ellipticCurveCryptography #P256 #P384 #P521 #secp256k1 #secp256r1 #secp384r1 #secp521r1 #SecurityGuidance

A paper was published on the IACR’s ePrint archive yesterday, titled LadderLeak: Breaking ECDSA With Less Than One Bit of Nonce Leakage.

The ensuing discussion on /r/crypto led to several interesting questions that I thought would be worth capturing and answering in detail.

What’s Significant About the LadderLeak Paper?

This is best summarized by Table 1 from the paper.
The sections labeled “This work” are what’s new/significant about this research.
The paper authors were able to optimize existing attacks exploiting one-bit leakages against 192-bit and 160-bit elliptic curves. They were further able to exploit leakages of less than one bit in the same curves.

How Can You Leak Less Than One Bit?

We’re used to discrete quantities in computer science, but you can leak less than one bit of information in the case of side-channels.

Biased modular reduction can also create a vulnerable scenario: If you know the probability of a 0 or a 1 in a given position in the bit-string of the one-time number (i.e. the most significant bit) is not 0.5 to 0.5, but some other ratio (e.g. 0.51 to 0.49), you can (over many samples) conclude a probability of a specific bit in your dataset.

If “less than one bit” sounds strange, that’s probably our fault for always rounding up to the nearest bit when we express costs in computer science.

What’s the Cost of the Attack?

Consult Table 3 from the paper for empirical cost data:
Table 3 from the LadderLeak paper.

How Devastating is LadderLeak?

First, it assumes a lot of things:

1. That you’re using ECDSA with either sect163r1 or secp192r1 (NIST P-192). Breaking larger curves requires more bits of bias (as far as we know).
2. That you’re using a cryptography library with cache-timing leaks.
3. That you have a way to measure the timing leaks (and not just pilfer the ECDSA secret key; i.e. in a TPM setup). This threat model generally assumes some sort of physical access.

But if you can pull the attack off, you can successfully recover the device’s ECDSA secret key. Which, for protocols like TLS, allow an attacker to impersonate a certificate-bearer (typically the server)… which is pretty devastating.

Is ECDSA Broken Now?

Non-deterministic ECDSA is not significantly more broken with LadderLeak than it already was by other attacks. LadderLeak does not break the Internet.

Fundamentally, LadderLeak doesn’t really change the risk calculus. Bleichenbacher’s attack framework for solving the Hidden Number Problem using Lattices was already practical, with sufficient samples.

There’s even a CryptoPals challenge about these attacks.

As an acquaintance put it, the authors made a time-memory trade-off with a leaky oracle. It’s a neat result worthy of publication, but we aren’t any minutes closer to midnight with this revelation.

Is ECDSA’s k-value Really a Nonce?

Ehhhhhhhhh, sorta.

It’s complicated!

Nonce in cryptography has always meant “number that must be used only once” (typically per key). See: AES-GCM.

Nonces are often confused for initialization vectors (IVs), which in addition to a nonce’s requirements for non-reuse must also be unpredictable. See: AES-CBC.

However, nonces and IVs can both be public, whereas ECDSA k-values MUST NOT be public! If you recover the k-value for a given signature, you can recover the secret key too.

That is to say, ECDSA k-values must be all of the above:

1. Never reused
2. Unpredictable
3. Secret
4. Unbiased

They’re really in a class of their own.

For that reason, it’s probably better to think of the k-value as a per-signature key than a simple nonce. (n.b. Many cryptography libraries actually implement them as a one-time ECDSA keypair.)

What’s the Difference Between Random and Unpredictable?

The HMAC-SHA256 output of a message under a secret key is unpredictable for anyone not in possession of said secret key. This value, though unpredictable, is not random, since signing the same message twice yields the same output.

A large random integer when subjected to modular reduction by a non-Mersenne prime of the same magnitude will be biased towards small values. This bias may be negligible, but it makes the bit string that represents the reduced integer more predictable, even though it’s random.

What Should We Do? How Should We Respond?

First, don’t panic. This is interesting research and its authors deserve to enjoy their moment, but the sky is not falling.

Second, acknowledge that none of the attacks are effective against EdDSA.

If you feel the urge to do something about this attack paper, file a support ticket with all of your third-party vendors and business partners that handle cryptographic secrets to ask them if/when they plan to support EdDSA (especially if FIPS compliance is at all relevant to your work, since EdDSA is coming to FIPS 186-5).

Reason: With increased customer demand for EdDSA, more companies will adopt this digital signature algorithm (which is much more secure against real-world attacks). Thus, we can ensure an improved attack variant that actually breaks ECDSA doesn’t cause the sky to fall and the Internet to be doomed.

(Seriously, I don’t think most companies can overcome their inertia regarding ECDSA to EdDSA migration if their customers never ask for it.)

https://soatok.blog/2020/05/26/learning-from-ladderleak-is-ecdsa-broken/

#crypto #cryptography #digitalSignatureAlgorithm #ECDSA #ellipticCurveCryptography #LadderLeak

Dhole Moments

2020-05-13 10:00:22

If you’re reading this wondering if you should stop using AES-GCM in some standard protocol (TLS 1.3), the short answer is “No, you’re fine”.

I specialize in secure implementations of cryptography, and my years of experience in this field have led me to dislike AES-GCM.

This post is about why I dislike AES-GCM’s design, not “why AES-GCM is insecure and should be avoided”. AES-GCM is still miles above what most developers reach for when they want to encrypt (e.g. ECB mode or CBC mode). If you want a detailed comparison, read this.

To be clear: This is solely my opinion and not representative of any company or academic institution.

What is AES-GCM?

AES-GCM is an authenticated encryption mode that uses the AES block cipher in counter mode with a polynomial MAC based on Galois field multiplication.

In order to explain why AES-GCM sucks, I have to first explain what I dislike about the AES block cipher. Then, I can describe why I’m filled with sadness every time I see the AES-GCM construction used.

What is AES?

The Advanced Encryption Standard (AES) is a specific subset of a block cipher called Rijndael.

Rijndael’s design is based on a substitution-permutation network, which broke tradition from many block ciphers of its era (including its predecessor, DES) in not using a Feistel network.

AES only includes three flavors of Rijndael: AES-128, AES-192, and AES-256. The difference between these flavors is the size of the key and the number of rounds used, but–and this is often overlooked–not the block size.

As a block cipher, AES always operates on 128-bit (16 byte) blocks of plaintext, regardless of the key size.

This is generally considered acceptable because AES is a secure pseudorandom permutation (PRP), which means that every possible plaintext block maps directly to one ciphertext block, and thus birthday collisions are not possible. (A pseudorandom function (PRF), conversely, does have birthday bound problems.)

Why AES Sucks

Art by Khia.

Side-Channels

The biggest reason why AES sucks is that its design uses a lookup table (called an S-Box) indexed by secret data, which is inherently vulnerable to cache-timing attacks (PDF).

There are workarounds for this AES vulnerability, but they either require hardware acceleration (AES-NI) or a technique called bitslicing.

The short of it is: With AES, you’re either using hardware acceleration, or you have to choose between performance and security. You cannot get fast, constant-time AES without hardware support.

Block Size

AES-128 is considered by experts to have a security level of 128 bits.

Similarly, AES-192 gets certified at 192-bit security, and AES-256 gets 256-bit security.

However, the AES block size is only 128 bits!

That might not sound like a big deal, but it severely limits the constructions you can create out of AES.

Consider the case of AES-CBC, where the output of each block of encryption is combined with the next block of plaintext (using XOR). This is typically used with a random 128-bit block (called the initialization vector, or IV) for the first block.

This means you expect a collision after encrypting (at 50% probability) blocks.

When you start getting collisions, you can break CBC mode, as this video demonstrates:

https://www.youtube.com/watch?v=v0IsYNDMV7A

This is significantly smaller than the you expect from AES.

Post-Quantum Security?

With respect to the number of attempts needed to find the correct key, cryptographers estimate that AES-128 will have a post-quantum security level of 64 bits, AES-192 will have a post-quantum security level of 96 bits, and AES-256 will have a post-quantum security level of 128 bits.

This is because Grover’s quantum search algorithm can search unsorted items in time, which can be used to reduce the total number of possible secrets from to . This effectively cuts the security level, expressed in bits, in half.

Note that this heuristic estimate is based on the number of guesses (a time factor), and doesn’t take circuit size into consideration. Grover’s algorithm also doesn’t parallelize well. The real-world security of AES may still be above 100 bits if you consider these nuances.

But remember, even AES-256 operates on 128-bit blocks.

Consequently, for AES-256, there should be approximately (plaintext, key) pairs that produce any given ciphertext block.

Furthermore, there will be many keys that, for a constant plaintext block, will produce the same ciphertext block despite being a different key entirely. (n.b. This doesn’t mean for all plaintext/ciphertext block pairings, just some arbitrary pairing.)

Concrete example: Encrypting a plaintext block consisting of sixteen NUL bytes will yield a specific 128-bit ciphertext exactly once for each given AES-128 key. However, there are times as many AES-256 keys as there are possible plaintext/ciphertexts. Keep this in mind for AES-GCM.

This means it’s conceivable to accidentally construct a protocol that, despite using AES-256 safely, has a post-quantum security level on par with AES-128, which is only 64 bits.

This would not be nearly as much of a problem if AES’s block size was 256 bits.

Real-World Example: Signal

The Signal messaging app is the state-of-the-art for private communications. If you were previously using PGP and email, you should use Signal instead.

Signal aims to provide private communications (text messaging, voice calls) between two mobile devices, piggybacking on your pre-existing contacts list.

Part of their operational requirements is that they must be user-friendly and secure on a wide range of Android devices, stretching all the way back to Android 4.4.

The Signal Protocol uses AES-CBC + HMAC-SHA256 for message encryption. Each message is encrypted with a different AES key (due to the Double Ratchet), which limits the practical blast radius of a cache-timing attack and makes practical exploitation difficult (since you can’t effectively replay decryption in order to leak bits about the key).

Thus, Signal’s message encryption is still secure even in the presence of vulnerable AES implementations.

Hooray for well-engineered protocols managing to actually protect users.
Art by Swizz.

However, the storage service in the Signal App uses AES-GCM, and this key has to be reused in order for the encrypted storage to operate.

This means, for older phones without dedicated hardware support for AES (i.e. low-priced phones from 2013, which Signal aims to support), the risk of cache-timing attacks is still present.

This is unacceptable!

What this means is, a malicious app that can flush the CPU cache and measure timing with sufficient precision can siphon the AES-GCM key used by Signal to encrypt your storage without ever violating the security boundaries enforced by the Android operating system.

As a result of the security boundaries never being crossed, these kind of side-channel attacks would likely evade forensic analysis, and would therefore be of interest to the malware developers working for nation states.

Of course, if you’re on newer hardware (i.e. Qualcomm Snapdragon 835), you have hardware-accelerated AES available, so it’s probably a moot point.

Why AES-GCM Sucks Even More

AES-GCM is an authenticated encryption mode that also supports additional authenticated data. Cryptographers call these modes AEAD.

AEAD modes are more flexible than simple block ciphers. Generally, your encryption API accepts the following:

1. The plaintext message.
2. The encryption key.
3. A nonce (: A number that must only be used once).
4. Optional additional data which will be authenticated but not encrypted.

The output of an AEAD function is both the ciphertext and an authentication tag, which is necessary (along with the key and nonce, and optional additional data) to decrypt the plaintext.

Cryptographers almost universally recommend using AEAD modes for symmetric-key data encryption.

That being said, AES-GCM is possibly my least favorite AEAD, and I’ve got good reasons to dislike it beyond simply, “It uses AES”.

The deeper you look into AES-GCM’s design, the harder you will feel this sticker.

GHASH Brittleness

The way AES-GCM is initialized is stupid: You encrypt an all-zero block with your AES key (in ECB mode) and store it in a variable called . This value is used for authenticating all messages authenticated under that AES key, rather than for a given (key, nonce) pair.
Diagram describing Galois/Counter Mode, taken from Wikipedia.
This is often sold as an advantage: Reusing allows for better performance. However, it makes GCM brittle: Reusing a nonce allows an attacker to recover H and then forge messages forever. This is called the “forbidden attack”, and led to real world practical breaks.

Let’s contrast AES-GCM with the other AEAD mode supported by TLS: ChaCha20-Poly1305, or ChaPoly for short.

ChaPoly uses one-time message authentication keys (derived from each key/nonce pair). If you manage to leak a Poly1305 key, the impact is limited to the messages encrypted under that (ChaCha20 key, nonce) pair.

While that’s still bad, it isn’t “decrypt all messages under that key forever” bad like with AES-GCM.

Note: “Message Authentication” here is symmetric, which only provides a property called message integrity, not sender authenticity. For the latter, you need asymmetric cryptography (wherein the ability to verify a message doesn’t imply the capability to generate a new signature), which is totally disparate from symmetric algorithms like AES or GHASH. You probably don’t need to care about this nuance right now, but it’s good to know in case you’re quizzed on it later.

H Reuse and Multi-User Security

If you recall, AES operates on 128-bit blocks even when 256-bit keys are used.

If we assume AES is well-behaved, we can deduce that there are approximately different 256-bit keys that will map a single plaintext block to a single ciphertext block.

This is trivial to calculate. Simply divide the number of possible keys () by the number of possible block states () to yield the number of keys that produce a given ciphertext for a single block of plaintext: .

Each key that will map an arbitrarily specific plaintext block to a specific ciphertext block is also separated in the keyspace by approximately .

This means there are approximately independent keys that will map a given all-zero plaintext block to an arbitrarily chosen value of (if we assume AES doesn’t have weird biases).

Credit: Harubaki

“Why Does This Matter?”

It means that, with keys larger than 128 bits, you can model the selection of as a 128-bit pseudorandom function, rather than a 128-bit permutation. As a result, you an expect a collision with 50% probability after only different keys are selected.

Note: Your 128-bit randomly generated AES keys already have this probability baked into their selection, but this specific analysis doesn’t really apply for 128-bit keys since AES is a PRP, not a PRF, so there is no “collision” risk. However, you end up at the same upper limit either way.

But 50% isn’t good enough for cryptographic security.

In most real-world systems, we target a collision risk. So that means our safety limit is actually different AES keys before you have to worry about reuse.

This isn’t the same thing as symmetric wear-out (where you need to re-key after a given number of encryptions to prevent nonce reuse). Rather, it means after your entire population has exhausted the safety limit of different AES keys, you have to either accept the risk or stop using AES-GCM.

If you have a billion users (), the safety limit is breached after AES keys per user (approximately 262,000).

“What Good is H Reuse for Attackers if HF differs?”

There are two numbers used in AES-GCM that are derived from the AES key. is used for block multiplication, and (the value of with a counter of 0 from the following diagram) is XORed with the final result to produce the authentication tag.

The arrow highlighted with green is HF.

It’s tempting to think that a reuse of isn’t a concern because will necessarily be randomized, which prevents an attacker from observing when collides. It’s certainly true that the single-block collision risk discussed previously for will almost certainly not also result in a collision for . And since isn’t reused unless a nonce is reused (which also leaks directly), this might seem like a non-issue.

Art by Khia.

However, it’s straightforward to go from a condition of reuse to an adaptive chosen-ciphertext attack.

1. Intercept multiple valid ciphertexts.
   
   • e.g. Multiple JWTs encrypted with {"alg":"A256GCM"}

   
   

2. Use your knowledge of , the ciphertext, and the AAD to calculate the GCM tag up to the final XOR. This, along with the existing authentication tag, will tell you the value of for a given nonce.
3. Calculate a new authentication tag for a chosen ciphertext using and your candidate value, then replay it into the target system.

While the blinding offered by XORing the final output with is sufficient to stop from being leaked directly, the protection is one-way.

Ergo, a collision in is not sufficiently thwarted by .

“How Could the Designers Have Prevented This?”

The core issue here is the AES block size, again.

If we were analyzing a 256-bit block variant of AES, and a congruent GCM construction built atop it, none of what I wrote in this section would apply.

However, the 128-bit block size was a design constraint enforced by NIST in the AES competition. This block size was during an era of 64-bit block ciphers (e.g. Triple-DES and Blowfish), so it was a significant improvement at the time.

NIST’s AES competition also inherited from the US government’s tradition of thinking in terms of “security levels”, which is why there are three different permitted key sizes (128, 192, or 256 bits).

“Why Isn’t This a Vulnerability?”

There’s always a significant gap in security, wherein something isn’t safe to recommend, but also isn’t susceptible to a known practical attack. This gap is important to keep systems secure, even when they aren’t on the bleeding edge of security.

Using 1024-bit RSA is a good example of this: No one has yet, to my knowledge, successfully factored a 1024-bit RSA public key. However, most systems have recommended a minimum 2048-bit for years (and many recommend 3072-bit or 4096-bit today).

With AES-GCM, the expected distance between collisions in is , and finding an untargeted collision requires being able to observe more than different sessions, and somehow distinguish when collides.

As a user, you know that after different keys, you’ve crossed the safety boundary for avoiding collisions. But as an attacker, you need bites at the apple, not . Additionally, you need some sort of oracle or distinguisher for when this happens.

We don’t have that kind of distinguisher available to us today. And even if we had one available, the amount of data you need to search in order for any two users in the population to reuse/collide is challenging to work with. You would need the computational and data storages of a major cloud service provider to even think about pulling the attack off.

Naturally, this isn’t a practical vulnerability. This is just another gripe I have with AES-GCM, as someone who has to work with cryptographic algorithms a lot.

Short Nonces

Although the AES block size is 16 bytes, AES-GCM nonces are only 12 bytes. The latter 4 bytes are dedicated to an internal counter, which is used with AES in Counter Mode to actually encrypt/decrypt messages.

(Yes, you can use arbitrary length nonces with AES-GCM, but if you use nonces longer than 12 bytes, they get hashed into 12 bytes anyway, so it’s not a detail most people should concern themselves with.)

If you ask a cryptographer, “How much can I encrypt safely with AES-GCM?” you’ll get two different answers.

1. Message Length Limit: AES-GCM can be used to encrypt messages up to bytes long, under a given (key, nonce) pair.
2. Number of Messages Limit: If you generate your nonces randomly, you have a 50% chance of a nonce collision after messages.
   However, 50% isn’t conservative enough for most systems, so the safety margin is usually much lower. Cryptographers generally set the key wear-out of AES-GCM at random nonces, which represents a collision probability of one in 4 billion.

These limits are acceptable for session keys for encryption-in-transit, but they impose serious operational limits on application-layer encryption with long-term keys.

Random Key Robustness

Before the advent of AEAD modes, cryptographers used to combine block cipher modes of operation (e.g. AES-CBC, AES-CTR) with a separate message authentication code algorithm (e.g. HMAC, CBC-MAC).

You had to be careful in how you composed your protocol, lest you invite Cryptographic Doom into your life. A lot of developers screwed this up. Standardized AEAD modes promised to make life easier.

Many developers gained their intuition for authenticated encryption modes from protocols like Signal’s (which combines AES-CBC with HMAC-SHA256), and would expect AES-GCM to be a drop-in replacement.

Unfortunately, GMAC doesn’t offer the same security benefits as HMAC: Finding a different (ciphertext, HMAC key) pair that produces the same authentication tag is a hard problem, due to HMAC’s reliance on cryptographic hash functions. This makes HMAC-based constructions “message committing”, which instills Random Key Robustness.

Critically, AES-GCM doesn’t have this property. You can calculate a random (ciphertext, key) pair that collides with a given authentication tag very easily.

This fact prohibits AES-GCM from being considered for use with OPAQUE (which requires RKR), one of the upcoming password-authenticated key exchange algorithms. (Read more about them here.)

Better-Designed Algorithms

You might be thinking, “Okay random furry, if you hate AES-GCM so much, what would you propose we use instead?”

I’m glad you asked!

XChaCha20-Poly1305

For encrypting messages under a long-term key, you can’t really beat XChaCha20-Poly1305.

• ChaCha is a stream cipher based on a 512-bit ARX hash function in counter mode. ChaCha doesn’t use S-Boxes. It’s fast and constant-time without hardware acceleration.
• ChaCha20 is ChaCha with 20 rounds.
• XChaCha nonces are 24 bytes, which allows you to generate them randomly and not worry about a birthday collision until about messages (for the same collision probability as AES-GCM).
• Poly1305 uses different 256-bit key for each (nonce, key) pair and is easier to implement in constant-time than AES-GCM.
• XChaCha20-Poly1305 uses the first 16 bytes of the nonce and the 256-bit key to generate a distinct subkey, and then employs the standard ChaCha20-Poly1305 construction used in TLS today.

For application-layer cryptography, XChaCha20-Poly1305 contains most of the properties you’d want from an authenticated mode.

However, like AES-GCM (and all other Polynomial MACs I’ve heard of), it is not message committing.

The Gimli Permutation

For lightweight cryptography (n.b. important for IoT), the Gimli permutation (e.g. employed in libhydrogen) is an attractive option.

Gimli is a Round 2 candidate in NIST’s Lightweight Cryptography project. The Gimli permutation offers a lot of applications: a hash function, message authentication, encryption, etc.

Critically, it’s possible to construct a message-committing protocol out of Gimli that will hit a lot of the performance goals important to embedded systems.

Closing Remarks

Despite my personal disdain for AES-GCM, if you’re using it as intended by cryptographers, it’s good enough.

Don’t throw AES-GCM out just because of my opinions. It’s very likely the best option you have.

Although I personally dislike AES and GCM, I’m still deeply appreciative of the brilliance and ingenuity that went into both designs.

My desire is for the industry to improve upon AES and GCM in future cipher designs so we can protect more people, from a wider range of threats, in more diverse protocols, at a cheaper CPU/memory/time cost.

We wouldn’t have a secure modern Internet without the work of Vincent Rijmen, Joan Daemen, John Viega, David A. McGrew, and the countless other cryptographers and security researchers who made AES-GCM possible.

Change Log

• 2021-10-26: Added section on H Reuse and Multi-User Security.

https://soatok.blog/2020/05/13/why-aes-gcm-sucks/

#AES #AESGCM #cryptography #GaloisCounterMode #opinion #SecurityGuidance #symmetricCryptography

There seems to be a lot of interest among software developers in the various cryptographic building blocks (block ciphers, hash functions, etc.), and more specifically how they stack up against each other.

Today, we’re going to look at how some symmetric encryption methods stack up against each other.

If you’re just looking for a short list of cryptographic “right answers”, your cheat sheet can be found on Latacora’s blog.

Comparisons

• AES-GCM vs. ChaCha20-Poly1305
• AES-GCM vs. XChaCha20-Poly1305
• AES-GCM vs. AES-CCM
• AES-GCM vs. AES-GCM-SIV
• AES-GCM vs. AES-SIV
• AES-GCM-SIV vs. AES-SIV
• AES-GCM vs. AES-CBC
• AES-GCM vs. AES-CTR
• AES-CBC vs. AES-CTR
• AES-CBC vs. AES-ECB
• AES vs. Blowfish
• ChaCha vs. Salsa20
• ChaCha vs. RC4
• Cipher Cascades

AES-GCM vs. ChaCha20-Poly1305

• If you have hardware acceleration (e.g. AES-NI), then AES-GCM provides better performance. If you do not, AES-GCM is either slower than ChaCha20-Poly1305, or it leaks your encryption keys in cache timing.
• Neither algorithm is message committing, which makes both unsuitable for algorithms like OPAQUE (explanation).
• AES-GCM can target multiple security levels (128-bit, 192-bit, 256-bit), whereas ChaCha20-Poly1305 is only defined at the 256-bit security level.
• Nonce size:
  
  • AES-GCM: Varies, but standard is 96 bits (12 bytes). If you supply a longer nonce, this gets hashed down to 16 bytes.
  • ChaCha20-Poly1305: The standardized version uses 96-bit nonces (12 bytes), but the original used 64-bit nonces (8 bytes).

  
  

• Wearout of a single (key, nonce) pair:
  
  • AES-GCM: Messages must be less than 2^32 – 2 blocks (a.k.a. 2^36 – 32 bytes, a.k.a. 2^39 – 256 bits). This also makes the security analysis of AES-GCM with long nonces complicated, since the hashed nonce doesn’t start with the lower 4 bytes set to 00 00 00 02.
  • ChaCha20-Poly1305: ChaCha has an internal counter (32 bits in the standardized IETF variant, 64 bits in the original design).

  
  

• Neither algorithm is nonce misuse resistant.

Conclusion: Both are good options. AES-GCM can be faster with hardware support, but pure-software implementations of ChaCha20-Poly1305 are almost always fast and constant-time.

Back to the top

AES-GCM vs. XChaCha20-Poly1305

• XChaCha20 accepts 192-bit nonces (24 bytes). The first 16 of the nonce are used with the ChaCha key to derive a subkey, and then the rest of this algorithm is the same as ChaCha20-Poly1305.
• To compare AES-GCM and ChaCha20-Poly1305 for encryption, see above.
• The longer nonce makes XChaCha20-Poly1305 better suited for long-lived keys (i.e. application-layer cryptography) than AES-GCM.

Conclusion: If you’re using the same key for a large number of messages, XChaCha20-Poly1305 has a wider safety margin than AES-GCM. Therefore, XChaCha20-Poly1305 should be preferred in those cases.

Back to the top

AES-GCM vs. AES-CCM

AES-GCM is AES in Galois/Counter Mode, AES-CCM is AES in Counter with CBC-MAC mode.

Although I previously stated that AES-GCM is possibly my least favorite AEAD, AES-CCM is decidedly worse: AES-GCM is Encrypt-then-MAC, while AES-CCM is MAC-then-encrypt.

Sure, CCM mode has a security proof that arguably justifies violating the cryptographic doom principle, but I contend the only time it’s worthwhile to do that is when you’re building a nonce-misuse resistant mode (i.e. AES-GCM-SIV).

A lot of cryptography libraries simply don’t even implement AES-CCM; or if they do, it’s disabled by default (i.e. OpenSSL). A notable exception is the Stanford Javascript Cryptography Library, which defaults to AES-CCM + PBKDF2 for encryption.

Conclusion: Just use AES-GCM.

Back to the top

AES-GCM vs. AES-GCM-SIV

AES-GCM-SIV encryption runs at 70% the speed of AES-GCM, but decryption is just as fast. What does this 30% encryption slowdown buy? Nonce misuse resistance.

Nonce misuse resistance is really cool. (Art by Swizz)

The algorithms are significantly different:

• AES-GCM is basically AES-CTR, then GMAC (parameterized by the key and nonce) is applied over the AAD and ciphertext. (Encrypt then MAC)
• AES-GCM-SIV derives two distinct keys from the nonce and key, then uses POLYVAL (which is related to GHASH) over the AAD and message with the first key to generate the tag. Then the tag used to derive a series of AES inputs that, when encrypted with the second key, are XORed with the blocks of the message (basically counter mode). (MAC then Encrypt)

AES-GCM is a simpler algorithm to analyze. AES-GCM-SIV provides a greater safety margin. However, like AES-GCM, AES-GCM-SIV is also vulnerable to the Invisible Salamanders attack.

So really, use which ever you want.

Better security comes from AES-GCM-SIV, better encryption performance comes from AES-GCM. What are your priorities?

https://twitter.com/colmmacc/status/986286693572493312

Conclusion: AES-GCM-SIV is better, but both are fine.

Back to the top

AES-GCM vs. AES-SIV

At the risk of being overly reductionist, AES-SIV is basically a nonce misuse resistant variant of AES-CCM:

• Where AES-CCM uses CBC-MAC, AES-SIV uses CMAC, which is based on CBC-MAC but with a doubling step (left shift then XOR with the round constant).
• AES-SIV is MAC then encrypt (so is AES-CCM).
• AES-SIV uses AES-CTR (so does AES-CCM).

If you need nonce misuse resistance, AES-SIV is a tempting choice, but you’re going to get better performance out of AES-GCM.

AES-GCM also has the added advantage of not relying on CBC-MAC.

Conclusion: Prefer AES-GCM in most threat models, AES-SIV in narrower threat models where nonce misuse is the foremost security risk.

Back to the top

AES-GCM-SIV vs. AES-SIV

If you read the previous two sections, the conclusion here should be obvious.

• AES-GCM-SIV is slightly better than AES-GCM.
• AES-GCM is better than AES-SIV.

Conclusion: Use AES-GCM-SIV.

Back to the top

AES-GCM vs. AES-CBC

Just use AES-GCM. No contest.

AES-GCM is an authenticated encryption mode. It doesn’t just provide confidentiality by encrypting your message, it also provides integrity (which guarantees that nobody tampered with the encrypted message over the wire).

If you select AES-CBC instead of AES-GCM, you’re opening your systems to a type of attack called a padding oracle (which lets attackers decrypt messages without the key, by replaying altered ciphertexts and studying the behavior of your application).

If you must use AES-CBC, then you must also MAC your ciphertext (and the initialization vector–IV for short). You should also devise some sort of key-separation mechanism so you’re not using the same key for two different algorithms. Even something like this is fine:

1. encKey := HmacSha256(“encryption-cbc-hmac”, key)
2. macKey := HmacSha256(“authentication-cbc-hmac”, key)
3. iv := RandomBytes(16)
4. ciphertext := AesCbc(plaintext, iv, encKey)
5. tag := HmacSha256(iv + ciphertext, macKey)

For decryption you need a secure compare function. If one is not available to you, or you cannot guarantee it will run in constant time, a second HMAC call with a random per-comparison key will suffice.

There is no possible world in which case unauthenticated AES-CBC is a safer choice than AES-GCM.

AES-CBC + HMAC-SHA256 (encrypt then MAC) is message-committing and therefore can be safely used with algorithms like OPAQUE.

The Signal Protocol uses AES-CBC + HMAC-SHA2 for message encryption.

Back to the top

AES-GCM vs. AES-CTR

Just use AES-GCM. No contest.

Unlike AES-GCM, AES-CTR doesn’t provide any message integrity guarantees. However, strictly speaking, AES-GCM uses AES-CTR under the hood.

If you must use AES-CTR, the same rules apply as for AES-CBC:

1. encKey := HmacSha256(“encryption-ctr-hmac”, key)
2. macKey := HmacSha256(“authentication-ctr-hmac”, key)
3. nonce := RandomBytes(16)
4. ciphertext := AesCtr(plaintext, nonce, encKey)
5. tag := HmacSha256(nonce + ciphertext, macKey)

For decryption you need a secure compare function.

AES-CTR + HMAC-SHA256 (encrypt then MAC) is message-committing and therefore can be safely used with algorithms like OPAQUE.

Back to the top

AES-CBC vs. AES-CTR

If you find yourself trying to decide between CBC mode and CTR mode, you should probably save yourself the headache and just use GCM instead.

That being said:

AES-CTR fails harder than AES-CBC when you reuse an IV/nonce.

AES-CBC requires a padding scheme (e.g. PKCS #7 padding) which adds unnecessary algorithmic complexity.

If you have to decide between the two, and you have a robust extended-nonce key-splitting scheme in place, opt for AES-CTR. But really, unless you’re a cryptography engineer well-versed in the nuances and failure modes of these algorithms, you shouldn’t even be making this choice.

Back to the top

AES-CBC vs. AES-ECB

Never use ECB mode. ECB mode lacks semantic security.

Block cipher modes that support initialization vectors were invented to compensate for this shortcoming.

Conclusion: If you’re trying to decide between these two, you’ve already lost. Rethink your strategy.

Back to the top

AES vs. Blowfish

A lot of OpenVPN configurations in the wild default to Blowfish for encryption. To the authors of these configuration files, I have but one question:

Why?! (Art by Khia)

Sure, you might think, “But Blowfish supports up to 448-bit keys and is therefore more secure than even 256-bit AES.”

Cryptographic security isn’t a dick-measuring contest. Key size isn’t everything. More key isn’t more security.

AES is a block cipher with a 128-bit block size. Blowfish is a block cipher with a 64-bit block size. This means that Blowfish in CBC mode is vulnerable to birthday attacks in a practical setting.

AES has received several orders of magnitude more scrutiny from cryptography experts than Blowfish has.

Conclusion: Use AES instead of Blowfish.

Back to the top

ChaCha vs. Salsa20

Salsa20 is an eSTREAM finalist stream cipher. After years of cryptanalysis, reduced round variants of Salsa20 (specifically, Salsa20/7 with a 128-bit key) were found to be breakable. In response to this, a variant called ChaCha was published that increased the per-round diffusion.

That is to say: ChaCha is generally more secure than Salsa20 with similar or slightly better performance. If you have to choose between the two, go for ChaCha.

Conclusion: Your choice (both are good but ChaCha is slightly better).

Back to the top

ChaCha vs. RC4

Don’t use RC4 for anything! What are you doing?

My reaction when I read that the CIA was using a modified RC4 in their Assassin malware instead of a secure stream cipher, per the Vault7 leaks. (Art by Khia)

RC4 was a stream cipher–allegedly designed by Ron Rivest and leaked onto a mailing list–that has been thoroughly demolished by cryptanalysis. RC4 is not secure and should never be relied on for security.

Conclusion: Use ChaCha. Never use RC4.

Back to the top

Cipher Cascades

A cipher cascade is when you encrypt a message with one cipher, and then encrypt the ciphertext with another cipher, sometimes multiple times. One example: TripleSec by Keybase, which combines AES and Salsa20 (and, formerly, Twofish–an AES finalist).

Cipher cascades don’t meaningfully improve security in realistic threat models. However, if your threat model includes “AES is broken or backdoored by the NSA”, a cipher cascade using AES is safer than just selecting a nonstandard cipher instead of AES. However, they’re necessarily slower than just using AES would be.

If you’re worried about this, your time is better spent worrying about key management, side-channel attacks, and software supply chain attacks.

Conclusion: Avoid cipher cascades, but they’re better than recklessly paranoid alternatives.

Back to the top

Symmetric Encryption Rankings

So with all of the above information, can we rank these algorithms into tiers?

Art by Riley

Sort of! Although it’s based on the above analyses, ranking is inherently subjective. So what follows is entirely the author’s opinion of their relative goodness/badness.

Soatok’s ranking of symmetric encryption methods
https://soatok.blog/2020/07/12/comparison-of-symmetric-encryption-methods/

#AEAD #AES #AESGCM #AESGCMSIV #ChaCha20Poly1305 #ciphers #comparison #cryptography #encryption #NMRAEAD #ranking #SecurityGuidance #streamCiphers #symmetricCryptography #symmetricEncryption #XChaCha20Poly1305

Dhole Moments

2020-04-21 12:25:46

Authenticated Key Exchanges are an interesting and important building block in any protocol that aims to allow people to communicate privately over an untrusted medium (i.e. the Internet).

What’s an AKE?

At their core, Authenticated Key Exchanges (AKEs for short) combine two different classes of protocol.

1. An authentication mechanism, such as a MAC or a digital signature.
2. Key encapsulation, usually through some sort of Diffie-Hellman.

A simple example of an AKE is the modern TLS handshake, which uses digital signatures (X.509 certificates signed by certificate authorities) to sign ephemeral Elliptic Curve Diffie-Hellman (ECDH) public keys, which is then used to derive a shared secret to encrypt and authenticate network traffic.

I guess I should say “simple” with scare quotes. Cryptography is very much a “devil’s in the details” field, because my above explanation didn’t even encapsulate mutual-auth TLS or the underlying machinery of protocol negotiation. (Or the fact that non-forward-secret ciphersuites can be selected.)

AKEs get much more complicated, the more sophisticated your threat model becomes.

For example: Signal’s X3DH and Double Ratchet protocols are components of a very sophisticated AKE. Learn more about them here.

The IETF is working to standardize their own approach, called Messaging Layer Security (MLS), which uses a binary tree of ECDH handshakes to manage state and optimize group operations (called TreeKEM). You can learn more about IETF MLS here.

Password AKEs

Recently, a collection of cryptographers at the IETF’s Crypto Research Forum Group (CFRG) decided to hammer on a series of proposed Password-Authenticated Key Exchange (PAKE) protocols.

PAKEs come in two flavors: Balanced (mutually authenticated) and augmented (one side is a prover, the other is a verifier). Balanced PAKEs are good for encrypted tunnels where you control both endpoints (e.g. WiFi networks), whereas Augmented PAKEs are great for eliminating the risk of password theft in client-server applications, if the server gets hacked.

Ultimately, the CFRG settled on one balanced PAKE (CPace) and one augmented PAKE (OPAQUE).

Consequently, cryptographer Filippo Valsorda managed to implement CPace in 125 lines of Go, using Ristretto255.

I implemented the CPace PAKE yesterday with Go and ristretto255, and it felt like cheating.

📦 https://t.co/Q0kI19JOPY 📦

125 lines of code! Really happy with it and it was a lot of fun.

— Filippo Valsorda (@FiloSottile) March 29, 2020

Why So Complicated?

At the end of the day, an AKE is just a construction that combines key encapsulation with an authentication mechanism.

But how you combine these components together can vary wildly!

Some AKE designs (i.e. Dragonfly, in WPA3) are weaker than others; even if only in the sense of being difficult to implement in constant-time.

The reason there’s so many is that cryptographers tend to collectively decide which algorithms to recommend for standardization.

(n.b. There are a lot more block ciphers than DES, Blowfish, and AES to choose from! But ask a non-cryptographer to name five block ciphers and they’ll probably struggle.)

https://soatok.blog/2020/04/21/authenticated-key-exchanges/

#ake #authenticatedKeyExchange #cryptography #ECDH

A question I get asked frequently is, “How did you learn cryptography?”

I could certainly tell everyone my history as a self-taught programmer who discovered cryptography when, after my website for my indie game projects kept getting hacked, I was introduced to cryptographic hash functions… but I suspect the question folks want answered is, “How would you recommend I learn cryptography?” rather than my cautionary tale about poorly-implemented password hash being a gateway bug.

The Traditional Ways to Learn

There are two traditional ways to learn cryptography.

If you want a book to augment your journey in either traditional path, I recommend Serious Cryptography by Jean-Philippe Aumasson.

Academic Cryptography

The traditional academic way to learn cryptography involves a lot of self-study about number theory, linear algebra, discrete mathematics, probability, permutations, and field theory.

You’d typically start off with classical ciphers (Caesar, etc.) then work your way through the history of ciphers until you finally reach an introduction to the math underpinning RSA and Diffie-Hellman, and maybe taught about Schneier’s Law and cautioned to only use AES and SHA-2… and then you’re left to your own devices unless you pursue a degree in cryptography.

The end result of people carelessly exploring this path is a lot of designs like Telegram’s MTProto that do stupid things with exotic block cipher modes and misusing vanilla cryptographic hash functions as message authentication codes; often with textbook a.k.a. unpadded RSA, AES in ECB, CBC, or some rarely-used mode that the author had to write custom code to handle (using ECB mode under the hood), and (until recently) SHA-1.

People who decide to pursue cryptography as a serious academic discipline will not make these mistakes. They’re far too apt for the common mistakes. Instead, they run the risk of spending years involved in esoteric research about homomorphic encryption, cryptographic pairings, and other cool stuff that might not see real world deployment (outside of novel cryptocurrency hobby projects) for five or more years.

That is to say: Academia is a valid path to pursue, but it’s not for everyone.

If you want to explore this path, Cryptography I by Dan Boneh is a great starting point.

Security Industry-Driven Cryptography

The other traditional way to learn cryptography is to break existing cryptography implementations. This isn’t always as difficult as it may sound: Reverse engineering video games to defeat anti-cheat protections has led several of my friends into learning about cryptography.

For security-minded folks, the best place to start is the CryptoPals challenges. Another alternative is CryptoHack.

There are also plenty of CTF events all year around, but they’re rarely a good cryptography learning exercise above what CryptoPals offers. (Though there are notable exceptions.)

A Practical Approach to Learning Cryptography

Art by Kyume.

If you’re coming from a computer programming background and want to learn cryptography, the traditional approaches carry the risk of Reasoning By Lego.

Instead, the approach I recommend is to start gaining experience with the safest, highest-level libraries and then slowly working your way down into the details.

This approach has two benefits:

1. If you have to implement something while you’re still learning, your knowledge and experience is stilted towards “use something safe and secure” not “hack together something with Blowfish in ECB mode and MD5 because they’re familiar”.
2. You can let your own curiosity guide your education rather than follow someone else’s study guide.

To illustrate what this looks like, here’s how a JavaScript developer might approach learning cryptography, starting from the most easy-mode library and drilling down into specifics.

Super Easy Mode: DholeCrypto

Disclaimer: This is my project.

Dhole Crypto is an open source library, implemented in JavaScript and PHP and powered by libsodium, that tries to make security as easy as possible.

I designed Dhole Crypto for securing my own projects without increasing the cognitive load of anyone reviewing my code.

If you’re an experienced programmer, you should be able to successfully use Dhole Crypto in a Node.js/PHP project. If it does not come easy, that is a bug that should be fixed immediately.

Easy Mode: Libsodium

Using libsodium is slightly more involved than Dhole Crypto: Now you have to know what a nonce is, and take care to manage them carefully.

Advantage: Your code will be faster than if you used Dhole Crypto.

Libsodium is still pretty easy. If you use this cheat sheet, you can implement something secure without much effort. If you deviate from the cheat sheet, pay careful attention to the documentation.

If you’re writing system software (i.e. programming in C), libsodium is an incredibly easy-to-use library.

Moderate Difficulty: Implementing Protocols

Let’s say you’re working on a project where libsodium is overkill, and you only need a few cryptography primitives and constructions (e.g. XChaCha20-Poly1305). A good example: In-browser JavaScript.

Instead of forcing your users to download the entire Sodium library, you might opt to implement a compatible construction using JavaScript implementations of these primitives.

Since you have trusted implementations to test your construction against, this should be a comparatively low-risk effort (assuming the primitive implementations are also secure), but it’s not one that should be undertaken without all of the prior experience.

Note: At this stage you are not implementing the primitives, just using them.

Hard Difficulty: Designing Protocols and Constructions

Repeat after me: “I will not roll my own crypto before I’m ready.” Art by AtlasInu.

To distinguish: TLS and Noise are protocols. AES-GCM and XChaCha20-Poly1305 are constructions.

Once you’ve implemented protocols and constructions, the next step in your self-education is to design new ones.

Maybe you want to combine XChaCha20 with a MAC based on the BLAKE3 hash function, with some sort of SIV to make the whole shebang nonce-misuse resistant?

You wouldn’t want to dive headfirst into cryptography protocol/construction design without all of the prior experience.

Very Hard Mode: Implementing Cryptographic Primitives

It’s not so much that cryptography primitives are hard to implement. You could fit RC4 in a tweet before they raised the character limit to 280. (Don’t use RC4 though!)

The hard part is that they’re hard to implement securely. See also: LadderLeak.

Usually when you get to this stage in your education, you will have also picked up one or both of the traditional paths to augment your understanding. If not, you really should.

Nightmare Mode: Designing Cryptography Primitives

A lot of people like to dive straight into this stage early in their education. This usually ends in tears.

If you’ve mastered every step in my prescribed outline and pursued both of the traditional paths to the point that you have a novel published attack in a peer-reviewed journal (and mirrored on ePrint), then you’re probably ready for this stage.

Bonus: If you’re a furry and you become a cryptography expert, you can call yourself a cryptografur. If you had no other reason to learn cryptography, do it just for pun!

Header art by circuitslime.

https://soatok.blog/2020/06/10/how-to-learn-cryptography-as-a-programmer/

#cryptography #education #programming #Technology

Dhole Moments

2020-05-27 00:13:21

A paper was published on the IACR’s ePrint archive yesterday, titled LadderLeak: Breaking ECDSA With Less Than One Bit of Nonce Leakage.

The ensuing discussion on /r/crypto led to several interesting questions that I thought would be worth capturing and answering in detail.

What’s Significant About the LadderLeak Paper?

This is best summarized by Table 1 from the paper.
The sections labeled “This work” are what’s new/significant about this research.
The paper authors were able to optimize existing attacks exploiting one-bit leakages against 192-bit and 160-bit elliptic curves. They were further able to exploit leakages of less than one bit in the same curves.

How Can You Leak Less Than One Bit?

We’re used to discrete quantities in computer science, but you can leak less than one bit of information in the case of side-channels.

Biased modular reduction can also create a vulnerable scenario: If you know the probability of a 0 or a 1 in a given position in the bit-string of the one-time number (i.e. the most significant bit) is not 0.5 to 0.5, but some other ratio (e.g. 0.51 to 0.49), you can (over many samples) conclude a probability of a specific bit in your dataset.

If “less than one bit” sounds strange, that’s probably our fault for always rounding up to the nearest bit when we express costs in computer science.

What’s the Cost of the Attack?

Consult Table 3 from the paper for empirical cost data:
Table 3 from the LadderLeak paper.

How Devastating is LadderLeak?

First, it assumes a lot of things:

1. That you’re using ECDSA with either sect163r1 or secp192r1 (NIST P-192). Breaking larger curves requires more bits of bias (as far as we know).
2. That you’re using a cryptography library with cache-timing leaks.
3. That you have a way to measure the timing leaks (and not just pilfer the ECDSA secret key; i.e. in a TPM setup). This threat model generally assumes some sort of physical access.

But if you can pull the attack off, you can successfully recover the device’s ECDSA secret key. Which, for protocols like TLS, allow an attacker to impersonate a certificate-bearer (typically the server)… which is pretty devastating.

Is ECDSA Broken Now?

Non-deterministic ECDSA is not significantly more broken with LadderLeak than it already was by other attacks. LadderLeak does not break the Internet.

Fundamentally, LadderLeak doesn’t really change the risk calculus. Bleichenbacher’s attack framework for solving the Hidden Number Problem using Lattices was already practical, with sufficient samples.

There’s even a CryptoPals challenge about these attacks.

As an acquaintance put it, the authors made a time-memory trade-off with a leaky oracle. It’s a neat result worthy of publication, but we aren’t any minutes closer to midnight with this revelation.

Is ECDSA’s k-value Really a Nonce?

Ehhhhhhhhh, sorta.

It’s complicated!

Nonce in cryptography has always meant “number that must be used only once” (typically per key). See: AES-GCM.

Nonces are often confused for initialization vectors (IVs), which in addition to a nonce’s requirements for non-reuse must also be unpredictable. See: AES-CBC.

However, nonces and IVs can both be public, whereas ECDSA k-values MUST NOT be public! If you recover the k-value for a given signature, you can recover the secret key too.

That is to say, ECDSA k-values must be all of the above:

1. Never reused
2. Unpredictable
3. Secret
4. Unbiased

They’re really in a class of their own.

For that reason, it’s probably better to think of the k-value as a per-signature key than a simple nonce. (n.b. Many cryptography libraries actually implement them as a one-time ECDSA keypair.)

What’s the Difference Between Random and Unpredictable?

The HMAC-SHA256 output of a message under a secret key is unpredictable for anyone not in possession of said secret key. This value, though unpredictable, is not random, since signing the same message twice yields the same output.

A large random integer when subjected to modular reduction by a non-Mersenne prime of the same magnitude will be biased towards small values. This bias may be negligible, but it makes the bit string that represents the reduced integer more predictable, even though it’s random.

What Should We Do? How Should We Respond?

First, don’t panic. This is interesting research and its authors deserve to enjoy their moment, but the sky is not falling.

Second, acknowledge that none of the attacks are effective against EdDSA.

If you feel the urge to do something about this attack paper, file a support ticket with all of your third-party vendors and business partners that handle cryptographic secrets to ask them if/when they plan to support EdDSA (especially if FIPS compliance is at all relevant to your work, since EdDSA is coming to FIPS 186-5).

Reason: With increased customer demand for EdDSA, more companies will adopt this digital signature algorithm (which is much more secure against real-world attacks). Thus, we can ensure an improved attack variant that actually breaks ECDSA doesn’t cause the sky to fall and the Internet to be doomed.

(Seriously, I don’t think most companies can overcome their inertia regarding ECDSA to EdDSA migration if their customers never ask for it.)

https://soatok.blog/2020/05/26/learning-from-ladderleak-is-ecdsa-broken/

#crypto #cryptography #digitalSignatureAlgorithm #ECDSA #ellipticCurveCryptography #LadderLeak

If you’re reading this wondering if you should stop using AES-GCM in some standard protocol (TLS 1.3), the short answer is “No, you’re fine”.

I specialize in secure implementations of cryptography, and my years of experience in this field have led me to dislike AES-GCM.

This post is about why I dislike AES-GCM’s design, not “why AES-GCM is insecure and should be avoided”. AES-GCM is still miles above what most developers reach for when they want to encrypt (e.g. ECB mode or CBC mode). If you want a detailed comparison, read this.

To be clear: This is solely my opinion and not representative of any company or academic institution.

What is AES-GCM?

AES-GCM is an authenticated encryption mode that uses the AES block cipher in counter mode with a polynomial MAC based on Galois field multiplication.

In order to explain why AES-GCM sucks, I have to first explain what I dislike about the AES block cipher. Then, I can describe why I’m filled with sadness every time I see the AES-GCM construction used.

What is AES?

The Advanced Encryption Standard (AES) is a specific subset of a block cipher called Rijndael.

Rijndael’s design is based on a substitution-permutation network, which broke tradition from many block ciphers of its era (including its predecessor, DES) in not using a Feistel network.

AES only includes three flavors of Rijndael: AES-128, AES-192, and AES-256. The difference between these flavors is the size of the key and the number of rounds used, but–and this is often overlooked–not the block size.

As a block cipher, AES always operates on 128-bit (16 byte) blocks of plaintext, regardless of the key size.

This is generally considered acceptable because AES is a secure pseudorandom permutation (PRP), which means that every possible plaintext block maps directly to one ciphertext block, and thus birthday collisions are not possible. (A pseudorandom function (PRF), conversely, does have birthday bound problems.)

Why AES Sucks

Art by Khia.

Side-Channels

The biggest reason why AES sucks is that its design uses a lookup table (called an S-Box) indexed by secret data, which is inherently vulnerable to cache-timing attacks (PDF).

There are workarounds for this AES vulnerability, but they either require hardware acceleration (AES-NI) or a technique called bitslicing.

The short of it is: With AES, you’re either using hardware acceleration, or you have to choose between performance and security. You cannot get fast, constant-time AES without hardware support.

Block Size

AES-128 is considered by experts to have a security level of 128 bits.

Similarly, AES-192 gets certified at 192-bit security, and AES-256 gets 256-bit security.

However, the AES block size is only 128 bits!

That might not sound like a big deal, but it severely limits the constructions you can create out of AES.

Consider the case of AES-CBC, where the output of each block of encryption is combined with the next block of plaintext (using XOR). This is typically used with a random 128-bit block (called the initialization vector, or IV) for the first block.

This means you expect a collision after encrypting (at 50% probability) blocks.

When you start getting collisions, you can break CBC mode, as this video demonstrates:

https://www.youtube.com/watch?v=v0IsYNDMV7A

This is significantly smaller than the you expect from AES.

Post-Quantum Security?

With respect to the number of attempts needed to find the correct key, cryptographers estimate that AES-128 will have a post-quantum security level of 64 bits, AES-192 will have a post-quantum security level of 96 bits, and AES-256 will have a post-quantum security level of 128 bits.

This is because Grover’s quantum search algorithm can search unsorted items in time, which can be used to reduce the total number of possible secrets from to . This effectively cuts the security level, expressed in bits, in half.

Note that this heuristic estimate is based on the number of guesses (a time factor), and doesn’t take circuit size into consideration. Grover’s algorithm also doesn’t parallelize well. The real-world security of AES may still be above 100 bits if you consider these nuances.

But remember, even AES-256 operates on 128-bit blocks.

Consequently, for AES-256, there should be approximately (plaintext, key) pairs that produce any given ciphertext block.

Furthermore, there will be many keys that, for a constant plaintext block, will produce the same ciphertext block despite being a different key entirely. (n.b. This doesn’t mean for all plaintext/ciphertext block pairings, just some arbitrary pairing.)

Concrete example: Encrypting a plaintext block consisting of sixteen NUL bytes will yield a specific 128-bit ciphertext exactly once for each given AES-128 key. However, there are times as many AES-256 keys as there are possible plaintext/ciphertexts. Keep this in mind for AES-GCM.

This means it’s conceivable to accidentally construct a protocol that, despite using AES-256 safely, has a post-quantum security level on par with AES-128, which is only 64 bits.

This would not be nearly as much of a problem if AES’s block size was 256 bits.

Real-World Example: Signal

The Signal messaging app is the state-of-the-art for private communications. If you were previously using PGP and email, you should use Signal instead.

Signal aims to provide private communications (text messaging, voice calls) between two mobile devices, piggybacking on your pre-existing contacts list.

Part of their operational requirements is that they must be user-friendly and secure on a wide range of Android devices, stretching all the way back to Android 4.4.

The Signal Protocol uses AES-CBC + HMAC-SHA256 for message encryption. Each message is encrypted with a different AES key (due to the Double Ratchet), which limits the practical blast radius of a cache-timing attack and makes practical exploitation difficult (since you can’t effectively replay decryption in order to leak bits about the key).

Thus, Signal’s message encryption is still secure even in the presence of vulnerable AES implementations.

Hooray for well-engineered protocols managing to actually protect users.
Art by Swizz.

However, the storage service in the Signal App uses AES-GCM, and this key has to be reused in order for the encrypted storage to operate.

This means, for older phones without dedicated hardware support for AES (i.e. low-priced phones from 2013, which Signal aims to support), the risk of cache-timing attacks is still present.

This is unacceptable!

What this means is, a malicious app that can flush the CPU cache and measure timing with sufficient precision can siphon the AES-GCM key used by Signal to encrypt your storage without ever violating the security boundaries enforced by the Android operating system.

As a result of the security boundaries never being crossed, these kind of side-channel attacks would likely evade forensic analysis, and would therefore be of interest to the malware developers working for nation states.

Of course, if you’re on newer hardware (i.e. Qualcomm Snapdragon 835), you have hardware-accelerated AES available, so it’s probably a moot point.

Why AES-GCM Sucks Even More

AES-GCM is an authenticated encryption mode that also supports additional authenticated data. Cryptographers call these modes AEAD.

AEAD modes are more flexible than simple block ciphers. Generally, your encryption API accepts the following:

1. The plaintext message.
2. The encryption key.
3. A nonce (: A number that must only be used once).
4. Optional additional data which will be authenticated but not encrypted.

The output of an AEAD function is both the ciphertext and an authentication tag, which is necessary (along with the key and nonce, and optional additional data) to decrypt the plaintext.

Cryptographers almost universally recommend using AEAD modes for symmetric-key data encryption.

That being said, AES-GCM is possibly my least favorite AEAD, and I’ve got good reasons to dislike it beyond simply, “It uses AES”.

The deeper you look into AES-GCM’s design, the harder you will feel this sticker.

GHASH Brittleness

The way AES-GCM is initialized is stupid: You encrypt an all-zero block with your AES key (in ECB mode) and store it in a variable called . This value is used for authenticating all messages authenticated under that AES key, rather than for a given (key, nonce) pair.
Diagram describing Galois/Counter Mode, taken from Wikipedia.
This is often sold as an advantage: Reusing allows for better performance. However, it makes GCM brittle: Reusing a nonce allows an attacker to recover H and then forge messages forever. This is called the “forbidden attack”, and led to real world practical breaks.

Let’s contrast AES-GCM with the other AEAD mode supported by TLS: ChaCha20-Poly1305, or ChaPoly for short.

ChaPoly uses one-time message authentication keys (derived from each key/nonce pair). If you manage to leak a Poly1305 key, the impact is limited to the messages encrypted under that (ChaCha20 key, nonce) pair.

While that’s still bad, it isn’t “decrypt all messages under that key forever” bad like with AES-GCM.

Note: “Message Authentication” here is symmetric, which only provides a property called message integrity, not sender authenticity. For the latter, you need asymmetric cryptography (wherein the ability to verify a message doesn’t imply the capability to generate a new signature), which is totally disparate from symmetric algorithms like AES or GHASH. You probably don’t need to care about this nuance right now, but it’s good to know in case you’re quizzed on it later.

H Reuse and Multi-User Security

If you recall, AES operates on 128-bit blocks even when 256-bit keys are used.

If we assume AES is well-behaved, we can deduce that there are approximately different 256-bit keys that will map a single plaintext block to a single ciphertext block.

This is trivial to calculate. Simply divide the number of possible keys () by the number of possible block states () to yield the number of keys that produce a given ciphertext for a single block of plaintext: .

Each key that will map an arbitrarily specific plaintext block to a specific ciphertext block is also separated in the keyspace by approximately .

This means there are approximately independent keys that will map a given all-zero plaintext block to an arbitrarily chosen value of (if we assume AES doesn’t have weird biases).

Credit: Harubaki

“Why Does This Matter?”

It means that, with keys larger than 128 bits, you can model the selection of as a 128-bit pseudorandom function, rather than a 128-bit permutation. As a result, you an expect a collision with 50% probability after only different keys are selected.

Note: Your 128-bit randomly generated AES keys already have this probability baked into their selection, but this specific analysis doesn’t really apply for 128-bit keys since AES is a PRP, not a PRF, so there is no “collision” risk. However, you end up at the same upper limit either way.

But 50% isn’t good enough for cryptographic security.

In most real-world systems, we target a collision risk. So that means our safety limit is actually different AES keys before you have to worry about reuse.

This isn’t the same thing as symmetric wear-out (where you need to re-key after a given number of encryptions to prevent nonce reuse). Rather, it means after your entire population has exhausted the safety limit of different AES keys, you have to either accept the risk or stop using AES-GCM.

If you have a billion users (), the safety limit is breached after AES keys per user (approximately 262,000).

“What Good is H Reuse for Attackers if HF differs?”

There are two numbers used in AES-GCM that are derived from the AES key. is used for block multiplication, and (the value of with a counter of 0 from the following diagram) is XORed with the final result to produce the authentication tag.

The arrow highlighted with green is HF.

It’s tempting to think that a reuse of isn’t a concern because will necessarily be randomized, which prevents an attacker from observing when collides. It’s certainly true that the single-block collision risk discussed previously for will almost certainly not also result in a collision for . And since isn’t reused unless a nonce is reused (which also leaks directly), this might seem like a non-issue.

Art by Khia.

However, it’s straightforward to go from a condition of reuse to an adaptive chosen-ciphertext attack.

1. Intercept multiple valid ciphertexts.
   
   • e.g. Multiple JWTs encrypted with {"alg":"A256GCM"}

   
   

2. Use your knowledge of , the ciphertext, and the AAD to calculate the GCM tag up to the final XOR. This, along with the existing authentication tag, will tell you the value of for a given nonce.
3. Calculate a new authentication tag for a chosen ciphertext using and your candidate value, then replay it into the target system.

While the blinding offered by XORing the final output with is sufficient to stop from being leaked directly, the protection is one-way.

Ergo, a collision in is not sufficiently thwarted by .

“How Could the Designers Have Prevented This?”

The core issue here is the AES block size, again.

If we were analyzing a 256-bit block variant of AES, and a congruent GCM construction built atop it, none of what I wrote in this section would apply.

However, the 128-bit block size was a design constraint enforced by NIST in the AES competition. This block size was during an era of 64-bit block ciphers (e.g. Triple-DES and Blowfish), so it was a significant improvement at the time.

NIST’s AES competition also inherited from the US government’s tradition of thinking in terms of “security levels”, which is why there are three different permitted key sizes (128, 192, or 256 bits).

“Why Isn’t This a Vulnerability?”

There’s always a significant gap in security, wherein something isn’t safe to recommend, but also isn’t susceptible to a known practical attack. This gap is important to keep systems secure, even when they aren’t on the bleeding edge of security.

Using 1024-bit RSA is a good example of this: No one has yet, to my knowledge, successfully factored a 1024-bit RSA public key. However, most systems have recommended a minimum 2048-bit for years (and many recommend 3072-bit or 4096-bit today).

With AES-GCM, the expected distance between collisions in is , and finding an untargeted collision requires being able to observe more than different sessions, and somehow distinguish when collides.

As a user, you know that after different keys, you’ve crossed the safety boundary for avoiding collisions. But as an attacker, you need bites at the apple, not . Additionally, you need some sort of oracle or distinguisher for when this happens.

We don’t have that kind of distinguisher available to us today. And even if we had one available, the amount of data you need to search in order for any two users in the population to reuse/collide is challenging to work with. You would need the computational and data storages of a major cloud service provider to even think about pulling the attack off.

Naturally, this isn’t a practical vulnerability. This is just another gripe I have with AES-GCM, as someone who has to work with cryptographic algorithms a lot.

Short Nonces

Although the AES block size is 16 bytes, AES-GCM nonces are only 12 bytes. The latter 4 bytes are dedicated to an internal counter, which is used with AES in Counter Mode to actually encrypt/decrypt messages.

(Yes, you can use arbitrary length nonces with AES-GCM, but if you use nonces longer than 12 bytes, they get hashed into 12 bytes anyway, so it’s not a detail most people should concern themselves with.)

If you ask a cryptographer, “How much can I encrypt safely with AES-GCM?” you’ll get two different answers.

1. Message Length Limit: AES-GCM can be used to encrypt messages up to bytes long, under a given (key, nonce) pair.
2. Number of Messages Limit: If you generate your nonces randomly, you have a 50% chance of a nonce collision after messages.
   However, 50% isn’t conservative enough for most systems, so the safety margin is usually much lower. Cryptographers generally set the key wear-out of AES-GCM at random nonces, which represents a collision probability of one in 4 billion.

These limits are acceptable for session keys for encryption-in-transit, but they impose serious operational limits on application-layer encryption with long-term keys.

Random Key Robustness

Before the advent of AEAD modes, cryptographers used to combine block cipher modes of operation (e.g. AES-CBC, AES-CTR) with a separate message authentication code algorithm (e.g. HMAC, CBC-MAC).

You had to be careful in how you composed your protocol, lest you invite Cryptographic Doom into your life. A lot of developers screwed this up. Standardized AEAD modes promised to make life easier.

Many developers gained their intuition for authenticated encryption modes from protocols like Signal’s (which combines AES-CBC with HMAC-SHA256), and would expect AES-GCM to be a drop-in replacement.

Unfortunately, GMAC doesn’t offer the same security benefits as HMAC: Finding a different (ciphertext, HMAC key) pair that produces the same authentication tag is a hard problem, due to HMAC’s reliance on cryptographic hash functions. This makes HMAC-based constructions “message committing”, which instills Random Key Robustness.

Critically, AES-GCM doesn’t have this property. You can calculate a random (ciphertext, key) pair that collides with a given authentication tag very easily.

This fact prohibits AES-GCM from being considered for use with OPAQUE (which requires RKR), one of the upcoming password-authenticated key exchange algorithms. (Read more about them here.)

Better-Designed Algorithms

You might be thinking, “Okay random furry, if you hate AES-GCM so much, what would you propose we use instead?”

I’m glad you asked!

XChaCha20-Poly1305

For encrypting messages under a long-term key, you can’t really beat XChaCha20-Poly1305.

• ChaCha is a stream cipher based on a 512-bit ARX hash function in counter mode. ChaCha doesn’t use S-Boxes. It’s fast and constant-time without hardware acceleration.
• ChaCha20 is ChaCha with 20 rounds.
• XChaCha nonces are 24 bytes, which allows you to generate them randomly and not worry about a birthday collision until about messages (for the same collision probability as AES-GCM).
• Poly1305 uses different 256-bit key for each (nonce, key) pair and is easier to implement in constant-time than AES-GCM.
• XChaCha20-Poly1305 uses the first 16 bytes of the nonce and the 256-bit key to generate a distinct subkey, and then employs the standard ChaCha20-Poly1305 construction used in TLS today.

For application-layer cryptography, XChaCha20-Poly1305 contains most of the properties you’d want from an authenticated mode.

However, like AES-GCM (and all other Polynomial MACs I’ve heard of), it is not message committing.

The Gimli Permutation

For lightweight cryptography (n.b. important for IoT), the Gimli permutation (e.g. employed in libhydrogen) is an attractive option.

Gimli is a Round 2 candidate in NIST’s Lightweight Cryptography project. The Gimli permutation offers a lot of applications: a hash function, message authentication, encryption, etc.

Critically, it’s possible to construct a message-committing protocol out of Gimli that will hit a lot of the performance goals important to embedded systems.

Closing Remarks

Despite my personal disdain for AES-GCM, if you’re using it as intended by cryptographers, it’s good enough.

Don’t throw AES-GCM out just because of my opinions. It’s very likely the best option you have.

Although I personally dislike AES and GCM, I’m still deeply appreciative of the brilliance and ingenuity that went into both designs.

My desire is for the industry to improve upon AES and GCM in future cipher designs so we can protect more people, from a wider range of threats, in more diverse protocols, at a cheaper CPU/memory/time cost.

We wouldn’t have a secure modern Internet without the work of Vincent Rijmen, Joan Daemen, John Viega, David A. McGrew, and the countless other cryptographers and security researchers who made AES-GCM possible.

Change Log

• 2021-10-26: Added section on H Reuse and Multi-User Security.

https://soatok.blog/2020/05/13/why-aes-gcm-sucks/

#AES #AESGCM #cryptography #GaloisCounterMode #opinion #SecurityGuidance #symmetricCryptography

Dhole Moments

2020-07-12 21:33:27

There seems to be a lot of interest among software developers in the various cryptographic building blocks (block ciphers, hash functions, etc.), and more specifically how they stack up against each other.

Today, we’re going to look at how some symmetric encryption methods stack up against each other.

If you’re just looking for a short list of cryptographic “right answers”, your cheat sheet can be found on Latacora’s blog.

Comparisons

• AES-GCM vs. ChaCha20-Poly1305
• AES-GCM vs. XChaCha20-Poly1305
• AES-GCM vs. AES-CCM
• AES-GCM vs. AES-GCM-SIV
• AES-GCM vs. AES-SIV
• AES-GCM-SIV vs. AES-SIV
• AES-GCM vs. AES-CBC
• AES-GCM vs. AES-CTR
• AES-CBC vs. AES-CTR
• AES-CBC vs. AES-ECB
• AES vs. Blowfish
• ChaCha vs. Salsa20
• ChaCha vs. RC4
• Cipher Cascades

AES-GCM vs. ChaCha20-Poly1305

• If you have hardware acceleration (e.g. AES-NI), then AES-GCM provides better performance. If you do not, AES-GCM is either slower than ChaCha20-Poly1305, or it leaks your encryption keys in cache timing.
• Neither algorithm is message committing, which makes both unsuitable for algorithms like OPAQUE (explanation).
• AES-GCM can target multiple security levels (128-bit, 192-bit, 256-bit), whereas ChaCha20-Poly1305 is only defined at the 256-bit security level.
• Nonce size:
  
  • AES-GCM: Varies, but standard is 96 bits (12 bytes). If you supply a longer nonce, this gets hashed down to 16 bytes.
  • ChaCha20-Poly1305: The standardized version uses 96-bit nonces (12 bytes), but the original used 64-bit nonces (8 bytes).

  
  

• Wearout of a single (key, nonce) pair:
  
  • AES-GCM: Messages must be less than 2^32 – 2 blocks (a.k.a. 2^36 – 32 bytes, a.k.a. 2^39 – 256 bits). This also makes the security analysis of AES-GCM with long nonces complicated, since the hashed nonce doesn’t start with the lower 4 bytes set to 00 00 00 02.
  • ChaCha20-Poly1305: ChaCha has an internal counter (32 bits in the standardized IETF variant, 64 bits in the original design).

  
  

• Neither algorithm is nonce misuse resistant.

Conclusion: Both are good options. AES-GCM can be faster with hardware support, but pure-software implementations of ChaCha20-Poly1305 are almost always fast and constant-time.

Back to the top

AES-GCM vs. XChaCha20-Poly1305

• XChaCha20 accepts 192-bit nonces (24 bytes). The first 16 of the nonce are used with the ChaCha key to derive a subkey, and then the rest of this algorithm is the same as ChaCha20-Poly1305.
• To compare AES-GCM and ChaCha20-Poly1305 for encryption, see above.
• The longer nonce makes XChaCha20-Poly1305 better suited for long-lived keys (i.e. application-layer cryptography) than AES-GCM.

Conclusion: If you’re using the same key for a large number of messages, XChaCha20-Poly1305 has a wider safety margin than AES-GCM. Therefore, XChaCha20-Poly1305 should be preferred in those cases.

Back to the top

AES-GCM vs. AES-CCM

AES-GCM is AES in Galois/Counter Mode, AES-CCM is AES in Counter with CBC-MAC mode.

Although I previously stated that AES-GCM is possibly my least favorite AEAD, AES-CCM is decidedly worse: AES-GCM is Encrypt-then-MAC, while AES-CCM is MAC-then-encrypt.

Sure, CCM mode has a security proof that arguably justifies violating the cryptographic doom principle, but I contend the only time it’s worthwhile to do that is when you’re building a nonce-misuse resistant mode (i.e. AES-GCM-SIV).

A lot of cryptography libraries simply don’t even implement AES-CCM; or if they do, it’s disabled by default (i.e. OpenSSL). A notable exception is the Stanford Javascript Cryptography Library, which defaults to AES-CCM + PBKDF2 for encryption.

Conclusion: Just use AES-GCM.

Back to the top

AES-GCM vs. AES-GCM-SIV

AES-GCM-SIV encryption runs at 70% the speed of AES-GCM, but decryption is just as fast. What does this 30% encryption slowdown buy? Nonce misuse resistance.

Nonce misuse resistance is really cool. (Art by Swizz)

The algorithms are significantly different:

• AES-GCM is basically AES-CTR, then GMAC (parameterized by the key and nonce) is applied over the AAD and ciphertext. (Encrypt then MAC)
• AES-GCM-SIV derives two distinct keys from the nonce and key, then uses POLYVAL (which is related to GHASH) over the AAD and message with the first key to generate the tag. Then the tag used to derive a series of AES inputs that, when encrypted with the second key, are XORed with the blocks of the message (basically counter mode). (MAC then Encrypt)

AES-GCM is a simpler algorithm to analyze. AES-GCM-SIV provides a greater safety margin. However, like AES-GCM, AES-GCM-SIV is also vulnerable to the Invisible Salamanders attack.

So really, use which ever you want.

Better security comes from AES-GCM-SIV, better encryption performance comes from AES-GCM. What are your priorities?

https://twitter.com/colmmacc/status/986286693572493312

Conclusion: AES-GCM-SIV is better, but both are fine.

Back to the top

AES-GCM vs. AES-SIV

At the risk of being overly reductionist, AES-SIV is basically a nonce misuse resistant variant of AES-CCM:

• Where AES-CCM uses CBC-MAC, AES-SIV uses CMAC, which is based on CBC-MAC but with a doubling step (left shift then XOR with the round constant).
• AES-SIV is MAC then encrypt (so is AES-CCM).
• AES-SIV uses AES-CTR (so does AES-CCM).

If you need nonce misuse resistance, AES-SIV is a tempting choice, but you’re going to get better performance out of AES-GCM.

AES-GCM also has the added advantage of not relying on CBC-MAC.

Conclusion: Prefer AES-GCM in most threat models, AES-SIV in narrower threat models where nonce misuse is the foremost security risk.

Back to the top

AES-GCM-SIV vs. AES-SIV

If you read the previous two sections, the conclusion here should be obvious.

• AES-GCM-SIV is slightly better than AES-GCM.
• AES-GCM is better than AES-SIV.

Conclusion: Use AES-GCM-SIV.

Back to the top

AES-GCM vs. AES-CBC

Just use AES-GCM. No contest.

AES-GCM is an authenticated encryption mode. It doesn’t just provide confidentiality by encrypting your message, it also provides integrity (which guarantees that nobody tampered with the encrypted message over the wire).

If you select AES-CBC instead of AES-GCM, you’re opening your systems to a type of attack called a padding oracle (which lets attackers decrypt messages without the key, by replaying altered ciphertexts and studying the behavior of your application).

If you must use AES-CBC, then you must also MAC your ciphertext (and the initialization vector–IV for short). You should also devise some sort of key-separation mechanism so you’re not using the same key for two different algorithms. Even something like this is fine:

1. encKey := HmacSha256(“encryption-cbc-hmac”, key)
2. macKey := HmacSha256(“authentication-cbc-hmac”, key)
3. iv := RandomBytes(16)
4. ciphertext := AesCbc(plaintext, iv, encKey)
5. tag := HmacSha256(iv + ciphertext, macKey)

For decryption you need a secure compare function. If one is not available to you, or you cannot guarantee it will run in constant time, a second HMAC call with a random per-comparison key will suffice.

There is no possible world in which case unauthenticated AES-CBC is a safer choice than AES-GCM.

AES-CBC + HMAC-SHA256 (encrypt then MAC) is message-committing and therefore can be safely used with algorithms like OPAQUE.

The Signal Protocol uses AES-CBC + HMAC-SHA2 for message encryption.

Back to the top

AES-GCM vs. AES-CTR

Just use AES-GCM. No contest.

Unlike AES-GCM, AES-CTR doesn’t provide any message integrity guarantees. However, strictly speaking, AES-GCM uses AES-CTR under the hood.

If you must use AES-CTR, the same rules apply as for AES-CBC:

1. encKey := HmacSha256(“encryption-ctr-hmac”, key)
2. macKey := HmacSha256(“authentication-ctr-hmac”, key)
3. nonce := RandomBytes(16)
4. ciphertext := AesCtr(plaintext, nonce, encKey)
5. tag := HmacSha256(nonce + ciphertext, macKey)

For decryption you need a secure compare function.

AES-CTR + HMAC-SHA256 (encrypt then MAC) is message-committing and therefore can be safely used with algorithms like OPAQUE.

Back to the top

AES-CBC vs. AES-CTR

If you find yourself trying to decide between CBC mode and CTR mode, you should probably save yourself the headache and just use GCM instead.

That being said:

AES-CTR fails harder than AES-CBC when you reuse an IV/nonce.

AES-CBC requires a padding scheme (e.g. PKCS #7 padding) which adds unnecessary algorithmic complexity.

If you have to decide between the two, and you have a robust extended-nonce key-splitting scheme in place, opt for AES-CTR. But really, unless you’re a cryptography engineer well-versed in the nuances and failure modes of these algorithms, you shouldn’t even be making this choice.

Back to the top

AES-CBC vs. AES-ECB

Never use ECB mode. ECB mode lacks semantic security.

Block cipher modes that support initialization vectors were invented to compensate for this shortcoming.

Conclusion: If you’re trying to decide between these two, you’ve already lost. Rethink your strategy.

Back to the top

AES vs. Blowfish

A lot of OpenVPN configurations in the wild default to Blowfish for encryption. To the authors of these configuration files, I have but one question:

Why?! (Art by Khia)

Sure, you might think, “But Blowfish supports up to 448-bit keys and is therefore more secure than even 256-bit AES.”

Cryptographic security isn’t a dick-measuring contest. Key size isn’t everything. More key isn’t more security.

AES is a block cipher with a 128-bit block size. Blowfish is a block cipher with a 64-bit block size. This means that Blowfish in CBC mode is vulnerable to birthday attacks in a practical setting.

AES has received several orders of magnitude more scrutiny from cryptography experts than Blowfish has.

Conclusion: Use AES instead of Blowfish.

Back to the top

ChaCha vs. Salsa20

Salsa20 is an eSTREAM finalist stream cipher. After years of cryptanalysis, reduced round variants of Salsa20 (specifically, Salsa20/7 with a 128-bit key) were found to be breakable. In response to this, a variant called ChaCha was published that increased the per-round diffusion.

That is to say: ChaCha is generally more secure than Salsa20 with similar or slightly better performance. If you have to choose between the two, go for ChaCha.

Conclusion: Your choice (both are good but ChaCha is slightly better).

Back to the top

ChaCha vs. RC4

Don’t use RC4 for anything! What are you doing?

My reaction when I read that the CIA was using a modified RC4 in their Assassin malware instead of a secure stream cipher, per the Vault7 leaks. (Art by Khia)

RC4 was a stream cipher–allegedly designed by Ron Rivest and leaked onto a mailing list–that has been thoroughly demolished by cryptanalysis. RC4 is not secure and should never be relied on for security.

Conclusion: Use ChaCha. Never use RC4.

Back to the top

Cipher Cascades

A cipher cascade is when you encrypt a message with one cipher, and then encrypt the ciphertext with another cipher, sometimes multiple times. One example: TripleSec by Keybase, which combines AES and Salsa20 (and, formerly, Twofish–an AES finalist).

Cipher cascades don’t meaningfully improve security in realistic threat models. However, if your threat model includes “AES is broken or backdoored by the NSA”, a cipher cascade using AES is safer than just selecting a nonstandard cipher instead of AES. However, they’re necessarily slower than just using AES would be.

If you’re worried about this, your time is better spent worrying about key management, side-channel attacks, and software supply chain attacks.

Conclusion: Avoid cipher cascades, but they’re better than recklessly paranoid alternatives.

Back to the top

Symmetric Encryption Rankings

So with all of the above information, can we rank these algorithms into tiers?

Art by Riley

Sort of! Although it’s based on the above analyses, ranking is inherently subjective. So what follows is entirely the author’s opinion of their relative goodness/badness.

S	XChaCha20-Poly1305, AES-GCM-SIV
A	AES-GCM, ChaCha20-Poly1305
B	AES-SIV
C	AES-CTR + HMAC-SHA2, AES-CBC + HMAC-SHA2
D	AES-CCM
F	Any: AES-ECB, RC4, Blowfish Unauthenticated: AES-CBC, AES-CTR, Salsa20, ChaCha

Soatok’s ranking of symmetric encryption methods
https://soatok.blog/2020/07/12/comparison-of-symmetric-encryption-methods/

#AEAD #AES #AESGCM #AESGCMSIV #ChaCha20Poly1305 #ciphers #comparison #cryptography #encryption #NMRAEAD #ranking #SecurityGuidance #streamCiphers #symmetricCryptography #symmetricEncryption #XChaCha20Poly1305

There are several different methods for securely hashing a password server-side for storage and future authentication. The most common one (a.k.a. the one that FIPS allows you to use, if compliance matters for you) is called PBKDF2. It stands for Password-Based Key Derivation Function #2.

Why #2? It’s got nothing to do with pencils. There was, in fact, a PBKDF1! But PBKDF1 was fatally insecure in a way I find very interesting. This StackOverflow answer is a great explainer on the difference between the two.

Very Hand-Wavy Description of a Hash Function

Let’s defined a hash function as any one-way transformation of some arbitrary-length string () to a fixed-length, deterministic, pseudo-random output.

Note: When in doubt, I err on the side of being easily understood by non-experts over pedantic precision. (Art by Swizz)

For example, this is a dumb hash function (uses SipHash-2-4 with a constant key):

function dumb_hash(string $arbitrary, bool $raw_binary = false): string{ $h = sodium_crypto_shorthash($arbitrary, 'SoatokDreamseekr'); if ($raw_binary) { return $h; } return sodium_bin2hex($h);}

You can see the output of this function with some sample inputs here.

Properties of Hash Functions

A hash function is considered secure if it has the following properties:

1. Pre-image resistance. Given , it should be difficult to find .
2. Second pre-image resistance. Given , it should be difficult to find such that
3. Collision resistance. It should be difficult to find any arbitrary pair of messages () such that

That last property, collision resistance, is guaranteed up to the Birthday Bound of the hash function. For a hash function with a 256-bit output, you will expect to need on average trial messages to find a collision.

If you’re confused about the difference between collision resistance and second pre-image resistance:

Collision resistance is about finding any two messages that produce the same hash, but you don’t care what the hash is as long as two distinct but known messages produce it.

On the other paw, second pre-image resistance is about finding a second message that produces a given hash.

Exploring PBKDF1’s Insecurity

If you recall, hash functions map an arbitrary-length string to a fixed-length string. If your input size is larger than your output size, collisions are inevitable (albeit computationally infeasible for hash functions such as SHA-256).

But what if your input size is equal to your output size, because you’re taking the output of a hash function and feeding it directly back into the same hash function?

Then, as explained here, you get an depletion of the possible outputs with each successive iteration.

But what does that look like?

Without running the experiments on a given hash function, there are two possibilities that come to mind:

1. Convergence. This is when will, for two arbitrary messages and a sufficient number of iterations, converge on a single hash output.
2. Cycles. This is when for some integer .

The most interesting result would be a quine, which is a cycle where (that is to say, ).

The least interesting result would be for random inputs to converge into large cycles e.g. cycles of size for a 256-bit hash function.

I calculated this lazily as the birthday bound of the birthday bound (so basically the 4th root, which for is ).

Update: According to this 1960 paper, the average time to cycle is , and cycle length should be , which means for a 256-bit hash you should expect a cycle after about or about 128 bits, and the average cycle length will be about . Thanks Riastradh for the corrections.

Conjecture: I would expect secure cryptographic hash functions in use today (e.g. SHA-256) to lean towards the least interesting output.

An Experiment Design

Since I don’t have an immense amount of cheap cloud computing at my disposal to run this experiments on a real hash function, I’m going to cheat a little and use my constant-key SipHash code from earlier in this post. In future work, cryptographers may find studying real hash functions (e.g. SHA-256) worthwhile.

Given that SipHash is a keyed pseudo-random function with an output size of 64 bits, my dumb hash function can be treated as a 64-bit hash function.

This means that you should expect your first collision (with 50% probability) after only trial hashes. This is cheap enough to try on a typical laptop.

Here’s a simple experiment for convergence:

1. Generate two random strings .
2. Set .
3. Iterate until .

You can get the source code to run this trivial experiment here.

Clone the git repository, run composer install, and then php bin/experiment.php. Note that this may need to run for a very long time before you get a result.

If you get a result, you’ve found a convergence.

If the loop doesn’t terminate even after 2^64 iterations, you’ve definitely found a cycle. (Actually detecting a cycle and analyzing its length would require a lot of memory, and my simple PHP script isn’t suitable for this effort.)

“What do you mean I don’t have a petabyte of RAM at my disposal?”

What Does This Actually Tell Us?

The obvious lesson: Don’t design key derivation functions like PBKDF1.

But beyond that, unless you can find a hash function that reliably converges or produces short cycles (, for an n-bit hash function), not much. (This is just for fun, after all!)

Definitely fun to think about though! (Art by circuitslime)

If, however, a hash function is discovered to produce interesting results, this may indicate that the chosen hash function’s internal design is exploitable in some subtle ways that, upon further study, may lead to better cryptanalysis techniques. Especially if a hash quine is discovered.

(Header art by Khia)

https://soatok.blog/2020/05/05/putting-the-fun-in-hash-function/

#crypto #cryptography #hashFunction #SipHash

Dhole Moments

2020-05-05 12:00:22

There are several different methods for securely hashing a password server-side for storage and future authentication. The most common one (a.k.a. the one that FIPS allows you to use, if compliance matters for you) is called PBKDF2. It stands for Password-Based Key Derivation Function #2.

Why #2? It’s got nothing to do with pencils. There was, in fact, a PBKDF1! But PBKDF1 was fatally insecure in a way I find very interesting. This StackOverflow answer is a great explainer on the difference between the two.

Very Hand-Wavy Description of a Hash Function

Let’s defined a hash function as any one-way transformation of some arbitrary-length string () to a fixed-length, deterministic, pseudo-random output.

Note: When in doubt, I err on the side of being easily understood by non-experts over pedantic precision. (Art by Swizz)

For example, this is a dumb hash function (uses SipHash-2-4 with a constant key):

function dumb_hash(string $arbitrary, bool $raw_binary = false): string{ $h = sodium_crypto_shorthash($arbitrary, 'SoatokDreamseekr'); if ($raw_binary) { return $h; } return sodium_bin2hex($h);}

You can see the output of this function with some sample inputs here.

Properties of Hash Functions

A hash function is considered secure if it has the following properties:

1. Pre-image resistance. Given , it should be difficult to find .
2. Second pre-image resistance. Given , it should be difficult to find such that
3. Collision resistance. It should be difficult to find any arbitrary pair of messages () such that

That last property, collision resistance, is guaranteed up to the Birthday Bound of the hash function. For a hash function with a 256-bit output, you will expect to need on average trial messages to find a collision.

If you’re confused about the difference between collision resistance and second pre-image resistance:

Collision resistance is about finding any two messages that produce the same hash, but you don’t care what the hash is as long as two distinct but known messages produce it.

On the other paw, second pre-image resistance is about finding a second message that produces a given hash.

Exploring PBKDF1’s Insecurity

If you recall, hash functions map an arbitrary-length string to a fixed-length string. If your input size is larger than your output size, collisions are inevitable (albeit computationally infeasible for hash functions such as SHA-256).

But what if your input size is equal to your output size, because you’re taking the output of a hash function and feeding it directly back into the same hash function?

Then, as explained here, you get an depletion of the possible outputs with each successive iteration.

But what does that look like?

Without running the experiments on a given hash function, there are two possibilities that come to mind:

1. Convergence. This is when will, for two arbitrary messages and a sufficient number of iterations, converge on a single hash output.
2. Cycles. This is when for some integer .

The most interesting result would be a quine, which is a cycle where (that is to say, ).

The least interesting result would be for random inputs to converge into large cycles e.g. cycles of size for a 256-bit hash function.

I calculated this lazily as the birthday bound of the birthday bound (so basically the 4th root, which for is ).

Update: According to this 1960 paper, the average time to cycle is , and cycle length should be , which means for a 256-bit hash you should expect a cycle after about or about 128 bits, and the average cycle length will be about . Thanks Riastradh for the corrections.

Conjecture: I would expect secure cryptographic hash functions in use today (e.g. SHA-256) to lean towards the least interesting output.

An Experiment Design

Since I don’t have an immense amount of cheap cloud computing at my disposal to run this experiments on a real hash function, I’m going to cheat a little and use my constant-key SipHash code from earlier in this post. In future work, cryptographers may find studying real hash functions (e.g. SHA-256) worthwhile.

Given that SipHash is a keyed pseudo-random function with an output size of 64 bits, my dumb hash function can be treated as a 64-bit hash function.

This means that you should expect your first collision (with 50% probability) after only trial hashes. This is cheap enough to try on a typical laptop.

Here’s a simple experiment for convergence:

1. Generate two random strings .
2. Set .
3. Iterate until .

You can get the source code to run this trivial experiment here.

Clone the git repository, run composer install, and then php bin/experiment.php. Note that this may need to run for a very long time before you get a result.

If you get a result, you’ve found a convergence.

If the loop doesn’t terminate even after 2^64 iterations, you’ve definitely found a cycle. (Actually detecting a cycle and analyzing its length would require a lot of memory, and my simple PHP script isn’t suitable for this effort.)

“What do you mean I don’t have a petabyte of RAM at my disposal?”

What Does This Actually Tell Us?

The obvious lesson: Don’t design key derivation functions like PBKDF1.

But beyond that, unless you can find a hash function that reliably converges or produces short cycles (, for an n-bit hash function), not much. (This is just for fun, after all!)

Definitely fun to think about though! (Art by circuitslime)

If, however, a hash function is discovered to produce interesting results, this may indicate that the chosen hash function’s internal design is exploitable in some subtle ways that, upon further study, may lead to better cryptanalysis techniques. Especially if a hash quine is discovered.

(Header art by Khia)

https://soatok.blog/2020/05/05/putting-the-fun-in-hash-function/

#crypto #cryptography #hashFunction #SipHash

Authenticated Key Exchanges are an interesting and important building block in any protocol that aims to allow people to communicate privately over an untrusted medium (i.e. the Internet).

What’s an AKE?

At their core, Authenticated Key Exchanges (AKEs for short) combine two different classes of protocol.

1. An authentication mechanism, such as a MAC or a digital signature.
2. Key encapsulation, usually through some sort of Diffie-Hellman.

A simple example of an AKE is the modern TLS handshake, which uses digital signatures (X.509 certificates signed by certificate authorities) to sign ephemeral Elliptic Curve Diffie-Hellman (ECDH) public keys, which is then used to derive a shared secret to encrypt and authenticate network traffic.

I guess I should say “simple” with scare quotes. Cryptography is very much a “devil’s in the details” field, because my above explanation didn’t even encapsulate mutual-auth TLS or the underlying machinery of protocol negotiation. (Or the fact that non-forward-secret ciphersuites can be selected.)

AKEs get much more complicated, the more sophisticated your threat model becomes.

For example: Signal’s X3DH and Double Ratchet protocols are components of a very sophisticated AKE. Learn more about them here.

The IETF is working to standardize their own approach, called Messaging Layer Security (MLS), which uses a binary tree of ECDH handshakes to manage state and optimize group operations (called TreeKEM). You can learn more about IETF MLS here.

Password AKEs

Recently, a collection of cryptographers at the IETF’s Crypto Research Forum Group (CFRG) decided to hammer on a series of proposed Password-Authenticated Key Exchange (PAKE) protocols.

PAKEs come in two flavors: Balanced (mutually authenticated) and augmented (one side is a prover, the other is a verifier). Balanced PAKEs are good for encrypted tunnels where you control both endpoints (e.g. WiFi networks), whereas Augmented PAKEs are great for eliminating the risk of password theft in client-server applications, if the server gets hacked.

Ultimately, the CFRG settled on one balanced PAKE (CPace) and one augmented PAKE (OPAQUE).

Consequently, cryptographer Filippo Valsorda managed to implement CPace in 125 lines of Go, using Ristretto255.

I implemented the CPace PAKE yesterday with Go and ristretto255, and it felt like cheating.

📦 https://t.co/Q0kI19JOPY 📦

125 lines of code! Really happy with it and it was a lot of fun.

— Filippo Valsorda (@FiloSottile) March 29, 2020

Why So Complicated?

At the end of the day, an AKE is just a construction that combines key encapsulation with an authentication mechanism.

But how you combine these components together can vary wildly!

Some AKE designs (i.e. Dragonfly, in WPA3) are weaker than others; even if only in the sense of being difficult to implement in constant-time.

The reason there’s so many is that cryptographers tend to collectively decide which algorithms to recommend for standardization.

(n.b. There are a lot more block ciphers than DES, Blowfish, and AES to choose from! But ask a non-cryptographer to name five block ciphers and they’ll probably struggle.)

https://soatok.blog/2020/04/21/authenticated-key-exchanges/

#ake #authenticatedKeyExchange #cryptography #ECDH

Dhole Moments

2020-04-21 12:25:46

Authenticated Key Exchanges are an interesting and important building block in any protocol that aims to allow people to communicate privately over an untrusted medium (i.e. the Internet).

What’s an AKE?

At their core, Authenticated Key Exchanges (AKEs for short) combine two different classes of protocol.

1. An authentication mechanism, such as a MAC or a digital signature.
2. Key encapsulation, usually through some sort of Diffie-Hellman.

A simple example of an AKE is the modern TLS handshake, which uses digital signatures (X.509 certificates signed by certificate authorities) to sign ephemeral Elliptic Curve Diffie-Hellman (ECDH) public keys, which is then used to derive a shared secret to encrypt and authenticate network traffic.

I guess I should say “simple” with scare quotes. Cryptography is very much a “devil’s in the details” field, because my above explanation didn’t even encapsulate mutual-auth TLS or the underlying machinery of protocol negotiation. (Or the fact that non-forward-secret ciphersuites can be selected.)

AKEs get much more complicated, the more sophisticated your threat model becomes.

For example: Signal’s X3DH and Double Ratchet protocols are components of a very sophisticated AKE. Learn more about them here.

The IETF is working to standardize their own approach, called Messaging Layer Security (MLS), which uses a binary tree of ECDH handshakes to manage state and optimize group operations (called TreeKEM). You can learn more about IETF MLS here.

Password AKEs

Recently, a collection of cryptographers at the IETF’s Crypto Research Forum Group (CFRG) decided to hammer on a series of proposed Password-Authenticated Key Exchange (PAKE) protocols.

PAKEs come in two flavors: Balanced (mutually authenticated) and augmented (one side is a prover, the other is a verifier). Balanced PAKEs are good for encrypted tunnels where you control both endpoints (e.g. WiFi networks), whereas Augmented PAKEs are great for eliminating the risk of password theft in client-server applications, if the server gets hacked.

Ultimately, the CFRG settled on one balanced PAKE (CPace) and one augmented PAKE (OPAQUE).

Consequently, cryptographer Filippo Valsorda managed to implement CPace in 125 lines of Go, using Ristretto255.

I implemented the CPace PAKE yesterday with Go and ristretto255, and it felt like cheating.

📦 https://t.co/Q0kI19JOPY 📦

125 lines of code! Really happy with it and it was a lot of fun.

— Filippo Valsorda (@FiloSottile) March 29, 2020

Why So Complicated?

At the end of the day, an AKE is just a construction that combines key encapsulation with an authentication mechanism.

But how you combine these components together can vary wildly!

Some AKE designs (i.e. Dragonfly, in WPA3) are weaker than others; even if only in the sense of being difficult to implement in constant-time.

The reason there’s so many is that cryptographers tend to collectively decide which algorithms to recommend for standardization.

(n.b. There are a lot more block ciphers than DES, Blowfish, and AES to choose from! But ask a non-cryptographer to name five block ciphers and they’ll probably struggle.)

https://soatok.blog/2020/04/21/authenticated-key-exchanges/

#ake #authenticatedKeyExchange #cryptography #ECDH