kwantam

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.

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.

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

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...

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...)

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!

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.

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.

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.)

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).

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!)

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))

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!

Came here to reminisce about the same trick :)

After a while we decided that adding one second per login was too subtle...

    echo "echo sleep 1 >> ~/.login" >> ~/.login

The paper, which is linked from the article, demonstrates a browser "fingerprinting" attack, which is to say, stealing pixels from one iframe using another iframe (which is quite clearly a violation of the safety properties the browser is supposed to provide).

It's unfortunate that this article is poor, but the paper itself is clear and readable.

I completely understand your position, and I'm certainly sympathetic that it's often hard to find good instructional materials. I'll readily admit, however, that I do not know Chegg as anything but a way to cheat. It is well known among the university-level educators I've spoken with (across several institutions) as the place that students go to find material for cheating.

So while it may not be the case that all users of Chegg are cheating, at some schools essentially all cheaters are using Chegg, including to cheat on exams (students post course bibles, test banks, etc.).

It doesn't help that Chegg is slow to take down materials even when explicitly told that the material was obtained illegitimately (which makes sense---empirically, illicit materials are the draw for at least some segment of their customers). I know several folks who have had to involve their university's legal team to get their course materials removed from the site.

Yes, dc/dc conversion is definitely applicable in high-power applications. As one example, high-voltage DC power transmission [1] is in widespread use globally, and always requires a dc/dc conversion step for connection to local grids. In addition to dc/dc conversion during transmission, converting from DC to AC (known as inversion) uses essentially the same techniques.

To answer your question more directly: stepping a battery's output to 10 kV is a good example of an application that would almost always be done with a dc/dc converter in an industrial application.

(Aside: "without an AC step" is slightly tricky. If by AC you mean 50 or 60 Hz, definitely can and should be avoided. But AC is generally used to refer to any non-constant voltage or current, and if that's what you mean then the answer is no since a dc/dc converter works by switching, which by definition means there's some sinusoidal voltage somewhere in the circuit.)

(Source: I used to design integrated circuits for industrial control.)

[1] https://en.wikipedia.org/wiki/High-voltage_direct_current

Well, for one, UDP brings the U. It's called the User Datagram Protocol because (at least on UNIX-like systems) unprivileged programs can almost always send and receive UDP datagrams, but in general cannot send and receive raw IP datagrams.

Is this a good time to bring up T/TCP?

https://www.rfc-editor.org/rfc/rfc1644

    This memo specifies T/TCP, an experimental TCP extension for
    efficient transaction-oriented (request/response) service.  This
    backwards-compatible extension could fill the gap between the current
    connection-oriented TCP and the datagram-based UDP.

Do you have a source for this? I'd really love to read more about it.

My impression from Ray's congressional testimony was "FTX.us might be solvent, but we don't know yet because the forensic accountants are still chipping away". But I was only half focused and am not confident I remember correctly.

This is definitely very cool!

But the circuit topology here can't meaningfully be called a discrete implementation of an LM386, unless by LM386 we just mean "a two-stage op-amp capable of driving a small speaker." The two circuits may have the same goals, but they're completely different designs (and the LM386 is a much better design---no shame in that, considering it's professional versus hobbyist).

The simplified diagram of the LM386 shown on Hackaday's website (which appears to be reproduced from the TI datasheet [1]) shows a few distinctive features that the discrete circuit lacks, and which result in better performance; and we can guess at some other details that are probably lost in the simplification.

- The LM386 input devices are a differential pair of PNP Darlingtons [2]. The Darlingtons are there partly because PNPs have worse current gain than NPNs, but they're also a conscious choice that allows the amplifier to be powered from a single supply while taking in a DC-coupled signal that's referenced to ground: the signal inputs (pins 2 and 3) can safely go below ground by roughly a diode drop, by design.

- In contrast, the linked discrete implementation uses NPN transistors for the input diff pair (Q1 and Q2), which means that it requires a separate R-C biasing network (C2, R7, R11, R12) and also means that the bias current in the diff pair depends on the power supply voltage (making power supply rejection tough).

- The LM386 uses a pair of NPNs in the first stage to effect a differential to single-ended conversion. The simplified diagram doesn't show it, but I'd bet that the real circuit matches the bias current in the output stage (the current source above the two diodes in the middle-right of the simplified schematic) with the current through the input stage, in order to hold the collector of the right NPN transistor at roughly the same DC voltage as the collector of the diode-connected NPN [3] on the left. This minimizes mismatch due to finite output impedance of the NPN transistors [4].

- In contrast, there's no differential to single-ended conversion in the discrete circuit. Q2's gain is essentially thrown away, the signal is taken from R4, and there's no attempt to match the collector voltages of Q1 and Q2 (adding a diode-connected device between Q2's collector and the supply would improve matching).

Again: I love when folks build and release their discrete circuit designs! I've done the same multiple times (here's a fun one [5]). It would have been better for the author (and Hackaday) to leave the LM386 out of this.

Finally, it seems like the author didn't actually build the device, just simulated it. I probably wouldn't build the discrete circuit as described. It's going to have some performance issues (poor power supply rejection is one) and will be quite sensitive to temperature, device characteristics, etc.---all things that one should try to minimize in a design.

[1] https://www.ti.com/lit/ds/symlink/lm386.pdf

[2] https://en.wikipedia.org/wiki/Darlington_transistor

[3] https://en.wikipedia.org/wiki/Diode-connected_transistor

[4] https://en.wikipedia.org/wiki/Early_effect

[5] https://web.jfet.org/gilberd/

Very nice! It turns out that latexmk has this functionality:

    latexmk -pvc -pdf foo.tex

I usually add something like this command as the `auto` target in my latex Makefiles, which works pretty nicely.

Sounds like a great improvement! Would it be possible to contribute your code to the existing crate rather than release your own? Then we could all enjoy the benefits on the next recompile :)

"Pick a random odd number and keep adding 2 until you find a prime" is, perhaps unintuitively, essentially fine for RSA key generation---under mild conditions, the security loss is single-digit bits at best. See Abboud and Prest, "Cryptographic Divergences: New Techniques and New Applications", SCN 2020 [1], Section 4.1.

(This is a relatively recent result. And as I mentioned in my other comment, this is not a defense of the article!)

[1] https://eprint.iacr.org/2020/815

Can you expand on the applicability of Prime and Prejudice [1] to RSA key generation? As far as I can tell, the two have nothing to do with one another.

The point of the Prime and Prejudice paper is, in effect, that the Miller-Rabin primality test should only be applied to random prime candidates, not adversarially chosen ones. The reason is: for a random composite, each M-R iteration has probability roughly 1/4 of revealing that the number is indeed composite. But it is possible to find composites that fool M-R with high probability. The upshot is: if an adversary is proposing primes to you, be very careful about using M-R!

For RSA key generation, unless you're worried about your RNG (in which case you're sunk anyway, to a first approximation), candidate primes are not adversarially chosen. So, as this article says, it does not appear that Prime and Prejudice is an issue for RSA key generation.

As further evidence for this, the Prime and Prejudice paper does not talk about vulnerabilities in RSA key generation. The issues that it describes have to do with validating prime-field DH parameters provided to a client by a potentially adversarial TLS server. As far as I can tell, the P&P paper only mentions RSA three times: twice as name-checks and once in the name of a library.

This isn't a defense of any other claim in the article. But as far as I can tell, P&P is not an issue in the context of RSA key generation.

[1] https://eprint.iacr.org/2018/749

The general message here is true, but I suspect that your specific example is not. Do you have a citation for the claim that PRIMEINC (generate random odd value, increment by 2 until you find a prime) caused overlapping prime factors?

The work I'm guessing you refer to on colliding prime factors is by Heninger et al., "Mining Your Ps and Qs", USENIX Security 2012 [1]. That paper does not mention anything about PRIMEINC causing this problem. The cases they found all related to bad entropy or extremely bad ways of generating moduli (like, pick two random values from a short list of known primes and use that as the modulus---an IBM product actually did this).

In fact, PRIMEINC is provably secure for generating RSA keys (though this was only shown somewhat recently): Abboud and Prest [2] analyze the distribution of outputs from PRIMEINC and show (see Section 4.1) that the security loss is negligible under quite mild conditions. Concretely, generating a reasonably sized RSA key using PRIMEINC rather than uniformly random primes reduces the security of RSA by a few bits at most.

But in some sense this reinforces your point---it was definitely not trivial to show that a tweak as seemingly simple as PRIMEINC is actually safe!

[1] https://factorable.net/weakkeys12.extended.pdf

[2] https://eprint.iacr.org/2020/815.pdf

In what sense were they Ukraine's nuclear weapons? They were physically inside Ukraine but controlled by Russia, as the article you linked makes clear.

They are! Inhaled flu vaccines are generally live attenuated virus, which isn't recommended for everyone but is perfectly effective for a large segment of the population:

https://www.cdc.gov/flu/prevent/nasalspray.htm

It's a tempting sound bite, but it's wrong.

First, a real vaccine is designed to be much safer than the disease it protects against (compare extremely rare incidence of vaccine side effects with extremely common incidence of hospitalization for infection). What would be the point otherwise?

Second, in the case of COVID variants prior to Omicron, infection is 5x less effective than vaccination at protecting against future infection: https://www.cdc.gov/media/releases/2021/s1029-Vaccination-Of...

Sorry I left out ZeroCoin, and thanks for pointing it out! Total braino as I was writing the post.

One incomplete answer:

At the bottom, this lets you prove that you know a signature without revealing what that signature is. This idea has been used in anonymous credential systems---much like this one! In the cryptographic literature, the underlying idea goes back to David Chaum ("Blind signatures for untraceable payment," Crypto 1982) and as far as I know the first implementation was Camenisch and Lysyanskya ("An efficient system for non-transferable anonymous credentials with optional anonymity revocation", Eurocrypt 2001).

Even without the zero-knowledge property this idea is useful, essentially because the "K" in "SNARK" stands for "knowledge" (as in, argument of knowledge). In other words: a convincing proof tells the verifier that the prover must know a signature, even if the prover doesn't actually publish that signature. You could also prove that you know 10 signatures, or 100, or more (well, up to the somewhat limited reach of existing proof systems).

Meanwhile, the size of the proof and the cost to verify it grows much more slowly than the number of signatures whose knowledge it establishes---so you can think of this as a kind of cryptographic "compression." This is one of the big ideas behind rollups, which are one possible way of improving the scaling behavior of blockchains like Ethereum.