kwantam · HackerTrans

2 года назадdiscuss

The whole point of this article is that performant Wireguard-over-TCP support in Wireguard simply does not work. You're not fighting the prevalence of an idea, you're fighting an inherent behavior of the system as currently constituted.

In more detail, let's imagine we make a Wireguard-over-TCP tunnel. The "outer" TCP connection carrying the Wireguard tunnel is, well, a TCP connection. So Wireguard can't stop the connection from retransmitting. Likewise, any "inner" TCP connections routed through the Wireguard tunnel are plain-vanilla TCP connections; Wireguard cannot stop them from retransmitting, either. The retransmit-in-retransmit behavior is precisely the issue.

So, what could we possibly do about this? Well, Wireguard certainly cannot modify the inner TCP connections (because then it wouldn't be providing a tunnel).

Could it work with a modified outer TCP connection? Maybe---perhaps Wireguard could implement a user-space "TCP" stack that sends syntactically valid TCP segments but never retransmits, then run that on both ends of the connection. In essence, UDP masquerading as TCP. But there's no guarantee that this faux-TCP connection wouldn't break in weird ways because the network (especially, as you've discovered, any cloud provider's network!) isn't just a dumb pipe: middleboxes, for example, expect TCP to behave like TCP.

Good news (and oops), it looks like I've just accidentally described phantun (and maybe other solutions): https://github.com/dndx/phantun I'd be curious if this manages to sidestep the issues you're seeing with AWS and OVH.

kwantam

2 года назадdiscuss

One of the fun things about the median-of-medians algorithm is its completely star-studded author list.

Manuel Blum - Turing award winner in 1995

Robert Floyd - Turing award winner in 1978

Ron Rivest - Turing award winner in 2002

Bob Tarjan - Turing award winner in 1986 (oh and also the inaugural Nevanlinna prizewinner in 1982)

Vaughan Pratt - oh no, the only non-Turing award winner in the list. Oh right but he's emeritus faculty at Stanford, directed the SUN project before it became Sun Microsystems, was instrumental in Sun's early days (director of research and designer of the Sun logo!), and is responsible for all kinds of other awesome stuff (near and dear to me: Pratt certificates of primality).

Four independent Turing awards! SPARCstations! This paper has it all.

kwantam

2 года назадdiscuss

Great stuff dga :)

Turns out, Niall was also involved in one of the winning ZPrize submissions for fast multi-scalar multiplication (closely related to batch modexp, although over an elliptic curve rather than mod a prime); I assume it inherits from his work on CGBN.

He give a very nice talk about it last year at a Stanford crypto lunch, and it turns out the slides and recording are online!

https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...

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

kwantam

2 года назадdiscuss

Maybe we're looking at different things, but the link appears to discuss ElGamal encryption, which is discrete log based (which means modern implementations use elliptic curves; historically it would have been discrete log in a subgroup of a large prime field). It also talks about BLS signatures, which are exclusively elliptic curve based.

By and large, anything whose security relies on discrete log can be implemented using an elliptic curve, but beginning cryptography classes treat that as an implementation detail because mostly all you need is a prime-order group, and elliptic curves can mostly be treated as a black-box prime order group.

(BLS signatures are an exception; they require a bilinear pairing, which in turn requires a special kind of elliptic curve that's not just a black-box prime order group.)

There are all sorts of great algebraic geometry tricks to be played with elliptic curves, but those almost certainly aren't going to be found in an intro crypto class, or maybe any CS class...

kwantam

2 года назадdiscuss

Excellent points all around, and thank you for the pointer to the ECC slides :)

(And indeed, nature could have been kinder to us and given us a Mersenne between 127 and 521...)

kwantam

2 года назадdiscuss

EdDSA signatures are specified to use deterministic nonce generation, so you're correct that they do not require randomness. But they certainly do require modular arithmetic in order to implement the elliptic curve operations!

kwantam

2 года назадdiscuss

RFC6979 attempts to guarantee that the nonce is unbiased (under the assumption that HMAC's output is indistinguishable from random). It's definitely attempting to give a stronger property than simply preventing a repeated nonce.

See step (h) in Section 3.2. The nonce is selected by rejection sampling. Thus, under the above assumption about HMAC, the result is indistinguishable from uniformly random in the [1, q-1] range.

kwantam

2 года назадdiscuss

The nonce is taken modulo the order of the prime-order subgroup. For DSA that's generally a 256ish-bit prime (e.g.: choose a 1024-bit prime p such that a 256-bit prime q divides p-1; then there exists an order-q subgroup of Zp).

For P-521, the base field is 2^521 - 1, but the modulus used when computing the nonce is not that value, it's the order of the P-521 curve. By Hasse's theorem, that's roughly p +- sqrt(p), which is essentially p for such large numbers (the cofactor of P-521 is 1, so the order of the group is prime).

So: both are 521-bit numbers, but the group order is less than 2^521-1. Its hex representation is 0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409.

kwantam

2 года назадdiscuss

This vulnerability has very little to do with P-521 per se. The issue is with ECDSA: any use of ECDSA with biased nonce generation, regardless of the elliptic curve it's implemented over, immediately causes secret key leakage.

(Rant: All these years later, we're all still doing penance for the fact that Schnorr signatures were patented and so everyone used ECDSA instead. It's an absolute garbage fire of a signature scheme and should be abandoned yesterday for many reasons, e.g., no real proof of security, terrible footguns like this.)

kwantam

2 года назадdiscuss

I'm sorry to say that your analysis is wildly incorrect.

- 10 billion people =~ 2^33

- 1000 CPUs =~ 2^10

- 1024 cores =~ 2^10

- 10 GHz =~ 2^33

So: one second's computation by all of these people is 2^86 UUIDs generated. UUIDs are 128 bits. With probability essentially 1, there will be a collision within one second.

The reason is known as the birthday paradox. If you sample random values from a set of size k, after you've chosen about sqrt(k) values you will have chosen the same value twice with probability very close to 1/2. By 10*sqrt(k) samples you'll have found a collision with probability well over 90%.

In this case, after sampling 2^64 values you'll have a collision with probability 1/2. That happens in roughly 250 nanoseconds (2^-22 seconds) in your thought experiment.

2^64 sounds like a lot, but in many contexts it's not all that much. Every bitcoin block mined takes well in excess of 2^70 SHA evaluations. Obviously the miners are not dedicated to generating UUID collisions, but if they were they'd easily find thousands of them in the time it takes to mine one block (this neglects the fact that it is much easier to sample a UUID than to evaluate double-SHA256).

kwantam

2 года назадdiscuss

The example you give is similar to but not quite the same as "lzAES". The distinction is that in your example, the application is deciding whether to compress or not---the input/output behavior of the cipher doesn't include the compression step, so the cipher it self doesn't suffer from the problem I mentioned in my first note.

But it's still possible for an application to use a cipher incorrectly. In particular, an application-level decision about whether to compress some data before encrypting can have an effect on the application's security. In the case you mention it seems unlikely to be a problem (but that's an application-level question, so it could be).

As an example where it seems like the application-level decision to compress or not matters a lot, imagine an application that sends an encrypted password to a server. If the application compresses the password first, an attacker could learn which values are not my password via guess-and-check-length. (Of course, even without compression the attacker can learn something about the length of my password just by looking at the length of the ciphertext---so probably this is a case where the application should first pad the message to some fixed length before encrypting. But in any case it almost certainly shouldn't compress the password!)

kwantam

2 года назадdiscuss

Yes, a correct encryption algorithm can encrypt (essentially) any bit string. But it's quite easy to turn a correct encryption algorithm into an incorrect one by bolting on something seemingly innocuous.

Here's a concrete example. Let's say you decide you want to make AES encryption more efficient by defining a new standard, "lzAES", that is just:

    Enc_lz(key, msg) := AES-Encrypt(key, lzw_compress(msg))
    Dec_lz(key, ctxt) := lzw_decompress(AES-Decrypt(key, ctxt))

This "works", in the sense that you can correctly decrypt ciphertexts, and it certainly seems innocuous. But it is now an insecure cipher!

Here's why: the definition of a secure cipher is that ciphertexts resulting from the encryptions of any two messages of equal length are indistinguishable. In other words, for any two messages you can choose, if I encrypt both messages under a randomly generated key, you can't tell which ciphertext corresponds to which message. In contrast, lzAES as defined above does not have this property: you could choose one message that's easily compressible (say, a string of zeros) and one that's not (say, a uniformly random string), and then you'd be able to tell which ciphertext corresponds to which plaintext just by looking at the ciphertext lengths.

And this is not just a definitional issue! If you use lzAES to encrypt something, an attacker can guess your message and test whether compressing the guess gives the same length as your ciphertext. Guess-and-check isn't possible with a secure cipher, but it is with lzAES---in other words, it gives away information about your plaintext!

comments