If I remember correctly, what you want to do is a Diffie-Hellman key exchange to set up a key pair, then use that to exchange a symmetric, randomly generated session key (for AES, AES-256, or similar,) then send a random nonce/IV at the head of each packet.

Don't forget to check server certificate on the client-side (against CA root embedded into client); without certificate check it will be akin to so-called Anonymous Diffie-Hellman (or a reasonable facsimile), which is a Big No-No due to MITM attacks (and as a rule of thumb, you don't want to have MITM against your game, not only because it is Really Insecure, but also because it easily enables all kinds of proxy bots). In short - to avoid MITM, you do need a certificate (to disable MITM-player-mounts-against-himself attack, the one which enables bots, there are a few further tricks, but this is a significantly longer story going beyond classical security and laden with obscurity trickery, so I will elaborate only if there are people here interested in it).

(DTLS seems to just use sequence number, which seems less secure than a strong random per PDU)

FWIW: IIRC, current understanding is that sequence numbers are just as secure as strong randoms (using sequence numbers is akin to implementing CTR mode over your packets, and while CTR was frowned upon for a long while exactly because of this perception, it is currently accepted is The Way To Go). I'd say that these days there is no difference in this regard for any practical purpose (and nobody knows what will happen two years down the road ;-( ).

Most of the overhead is involved in establishing the connection. Overhead once the connection is established is pretty minimal - enough so that it's unlikely to be a bottleneck in this day and age.

Yep. Basically, the only thing which is done after connection is established, is symmetric encryption (such as AES128), which is darn cheap. You can find out AES speed by running "openssl speed aes" (well, on Windows you'll need to build openssl first :-( ). For my measly laptop, it reports "Doing aes-128 cbc for 3s on 64 size blocks: 7284228 aes-128 cbc's in 2.99s" - i.e. over 2 million packets per second (that's for a single thread AFAIR). OTOH, establishing connection is a completely different matter altogether - it can go as slow as 0.1 sec/connection/core, and when you have 100000 connections disconnected and then reconnected - it can get Ugly :-(.

CTR is obviously weaker than CBC for UDP applications, because you have to include the sequence number in the packet

It depends on the attack model. If we're working under the classical attacker-controls-the-communication-channel-completely model, then I think it is not. Order of packets as they come out of the server is supposedly already known to the attacker (they're already outside of our security perimeter, and for the purposes of security analysis we should assume that attacker has no problems with monitoring communication channel all the time). Then - well, there is no additional info to be gained for the attacker from these numbers, they're just redundant for the attacker-who-controls-the-channel.

Also for most other CTR applications, it's obviously weaker as well.

Well, security community will disagree with you :-). Overall, currently CTR is generally pushed over CBC (with the reason being like "for CBC is too easy to mess up padding", which is not that a good reason if you ask me, but that's what they're saying more often than not).

OTOH, formally - being able to run in CTR mode securely is currently considered a required property of a "Good Symmetric Cypher", so modern ciphers (AES included) in CTR mode are being attacked a lot (and if/when somebody manages to succeed cracking AES-in-CTR - we'll know about it for sure, it will be very loud). That's actually the reason why DTLS is using it (and quite a few other guys are using it too; for example, most of modern AEAD algorithms - and you do want AEAD if building your own UDP-level encryption - are proven relying only on nonce to be unique - but not requiring randomness).

we've learned to ignore "steep" drops less than 1% because it's inevitably some cable modem provider in Germany having an outage, or something quite like it.

From what I've seen, Comcast going down is even worse (affecting 15-20% easily :-(( ).

This is with TLS, not DTLS, btw

For TLS, there is a rather obscure feature of "session cache"; from I've read/heard about it, it helps exactly for mass-reconnect scenario (didn't try it myself though). No idea if works for DTLS.

There's a lot of acronyms here for a noob lol. What is a CTR and a CFB?

What does a sequence number act as? I was thinking that it just made up the order of datagrams if order mattered, otherwise they weren't needed. Is it just a sequential integer, or a GUID and is it used to verify the datagram in anyway? If so, how so?

I appreciate the conversation, this is really helpful stuff. A lot of googling going on in my browser :D

assuming the role of the IV being unguessable is important for security.

Wait, wait. IVs have never been intended "unguessable" (the only thing "unguessable" is the key, that's it). Even for CBC-over-TCP (the one you seem to prefer, am I right?) you normally still have IVs well-known (or randomly-generated-and-exchanged-in-open), further complications with "secret" IV are possible but are not common IIRC; moreover, any "secret" IV is pretty much useless specifically for CBC mode because of CBC peculiarity with each next IV being ?ciphertext of the previous block, so IVs for all-but-the-first-block are effectively transferred in open for CBC.

BTW, how would you avoid transferring IV in open for your-own-UDP-protocol? Even if your IV is perfectly random, it still needs to be transferred in open... Of course, you can transfer sequential and calculate IV=sequential^pre_shared_secret_IV, but honestly, I would rather simply increase key length :-) (still, this is a viable option which shouldn't make anything worse as long as pre_shared_secret_IV is independent from keys).

The question-which-has-changed-its-answer-over-20-last-years-or-so is whether IV being sequential does any Bad Things to the security, but this (since post-DES times) is considered a responsibility of a Good Cipher to deal with.

What is a CTR and a CFB?

See https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

What does a sequence number act as?

Usually, it acts as an IV (initialisation vector) for those modes listed above. My point (actually not mine, but of majority of crypto-community at the time - should be "good enough" for games ;-)) - is that IV doesn't need to be secret, and that it can even be sequential, as long as IV is 100% guaranteed to be unique for all the messages encrypted with the same key. Fine, so to encrypt UDP we can add sequence number to each packet (it needs to be there anyway for other purposes, we just need to get it out of encryption) - and encrypt the packet-except-for-sequence-number with, say, AES128 in CTR mode using sequence-number as an IV, bingo! For this to work and comply with unique-for-all requirement - we'll need to make sure that this is a session key (generated, for example, as a part of standard RSA or certificate-based-DH key exchange). As an additional measure - you MAY pre-share additional 128-bit "secret IV" and calculate your IV=sequence^pre_shared_secret_IV, but IIRC this won't give you any additional "brownie points" with security guys ;-) (I hope that you won't be punished for doing it either).

Thanks for the information. This is all really new to me; I'm trying to pick up and understand how this would work. If you are encrypting the packets over AES128, do I need to go over DTLS? If I do, what is the point of encrypting the packets then? In the past, when using AES256 I've seen massive overhead penalties. I can't imagine how much overhead this would have if I'm sending a thousand packets per second.

If encrypting is acceptable over DTLS, can I reduce the overhead by just encrypting "cheat" vectors? Things like IAP transactions, in-game store and in-game currency award packets etc. This would leave things like chat messages and character movement unencrypted?

Do you know of a book, Udemy/Pluralsite or blog-series on building out these mechanics? It doesn't matter the language, I can get it into my language of choice if I can see some working basic examples of the concept in-action to help visualize the flow of operations a bit more.

To OP: Yes, this post went off track into theoretical cryptography!
Use a DTLS library like tinydtls, or the DTLS modes of OpenSSL / Gnu TLS / whatever, and you'll be more than fine.

If I use a DTLS lib I don't have to worry about encryption at all? At which point I can just use a sequence number meant for tracking my packet delivery rather than a sequence number needed for and IV on the packet?