19 March 2024: Beyond the Q

I wrote about Signal usernames two weeks ago and then I migrated my Signal account to a new phone. I was a bit disappointed to find Signal telling my that I had to set my username again (I did of course choose the same one) and also that the previously set link wouldn’t work anymore. I hope it’s a bug and that it will be solved quickly, but I guess with complex systems like that, new features are bound to have some issues for a while.

Other than that, life continues to be super busy, so this is a slightly shorter newsletter, without any book or song to share. I did find time to read quite a bit though and if that’s a thing, you can always follow me on Goodreads; I’ll probably follow you back!

If someone forwarded this newsletter to you, that is very kind of them and don't forget to thank them for it. You can subscribe here to receive future newsletters directly into your inbox. Feedback and suggestions are always welcome!

Martijn
martijn@lapsedordinary.net
martijngrooten.37

Beyond the Q

A few weeks ago, my partner and I spent a long evening making a jigsaw puzzle. The next morning, she spent a few seconds taking the puzzle apart and putting the pieces back into the box.

There is a huge asymmetry here: taking a finished puzzle apart takes seconds, but turning all the individual pieces into a complete puzzle takes hours of work. There is no shortcut. For sure, working in parallel helps, but it won’t make the process anywhere near as fast as taking the puzzle apart.

This kind of asymmetry forms the bases of many cryptographic algorithms. For example, RSA makes use of the fact that it is very easy to multiply two large prime numbers, while it is very hard, given the product of two such numbers, to find the two prime factors. (To follow the rest of this post, you don’t need to know what this means, as long as you understand the concepts ‘easy’ and ‘hard’.)

It is not hard in a sense that we don’t know how to, it’s just that we don’t know how to do it in a fast way, other than just trying all the possible factors. If the prime numbers are large enough, it will take a modern computer billions of years to try them all. In practice, this makes it a problem that is impossible to solve.

Here too, a computer can work ‘in parallel’, by using multiple processors, and sometimes people find clever tricks to speed up the process, but this can improve speed by a factor of ten or maybe one hundred. It’s not helping one find the prime factors in a reasonable amount of time.

A similar asymmetry manifests itself in what mathematicians call the “discrete logarithm problem”, which lies behind cryptographic protocols like Diffie-Hellman and Elliptic Curve Diffie-Hellman. Again, you don’t need to know how these work, but if you’re interested: here is an article on Ars Technical on the former and here a YouTube video on the latter. Full disclosure: I wrote and presented these respectively.

(On a small aside, technically speaking we don’t know if a fast method to crack these cryptographic algorithms exist. This might sound a bit crazy: what if someone really clever suddenly finds a fast method. I’m sure you can write a spy novel about a brilliant mathematician who finds such a fast method and thus gives an intelligence agency super powers. In practice, there is extremely strong evidence such algorithms don’t exist.)

Back to the jigsaw puzzle: what if a human being were genetically engineered to have 1000 hands and 1000 eyes, one for each piece. They could pick up all the pieces, look at them at the same time, and solve the puzzle in a matter of seconds, thus breaking the asymmetry.

Well, a computer like that is being developed. It is called a quantum computer and it can essentially break the mathematical asymmetry that forms the basis of the cryptographic algorithms discussed above. Just like our genetically engineered human can pick up and look at all puzzle pieces at once, a quantum computer can pretty much try all of the incredibly large number of possible solutions at the same time, thus finding the real solution in a very short amount of time.

Quantum computers, which rely on quantum mechanical phenomena, are currently being built, but the existing ones are far from advanced enough to break the aforementioned cryptographic systems. I am not qualified to say when this will be the case, or if this will ever be the case, but it is fair to say: there is a good chance that in the not too distant future, such quantum computers will exist and many existing cryptographic algorithms will essentially be broken.

Thankfully, cryptographers have developed some new algorithms that cannot be broken by quantum computers. They form part of post-quantum cryptography. The mathematics behind them is a whole lot more complicated than that behind RSA or Diffie-Hellman, but the good thing is that to use cryptography, you don’t need to understand algorithms.

Many systems that rely on cryptography have started adding post-quantum cryptography to the suite of protocols they use. These include Signal, iMessage, and Tutanota. The reason for this is not just to be ready for when quantum computers are built that can really break older cryptographic protocols: it also protects existing data against future attacks.

We know that intelligence agencies collect a lot of data flowing on the Internet. In today’s post-Snowden world, the vast majority of this data is encrypted and thus looks like random noise. But if this data is stored then, once a good enough quantum computer has been built, the agency can decrypt it all.

How dangerous this is for the users of cryptography really depends on the particular case. In the vast majority of cases, it won’t be a serious concern, but there are certainly cases where the decryption of encrypted data after ten or twenty years can still cause harm. This is why the Signals of this world are right to protect your data against computers that haven’t been built yet.

So what does this mean for you in practice? Nothing. As a user of cryptography you shouldn’t have to worry about the algorithms protecting your data. If you are really concerned, look for third-party audit reports. Signal, for example, has had plenty of audits. But as the term ‘post-quantum cryptography’ will appear more and more, hopefully you have a slightly better idea of what this means.

What else?

Security company ESET has a long and detailed blog post on the targeting of the global Tibetan community in a watering hole attack. In such an attack, one or more websites regularly visited by the targeted community (in this case a Tibetan News website and a software company making translation software for the Tibetan language) are compromised to spread malware. In the past, some watering hole attacks have exploited vulnerabilities in browsers to silently install malware. In this case, users were socially engineered to install the malware, which would then spy on their activities. It won’t surprise anyone that the actor behind this campaign has been linked to China.

The Security Self-Defense guides from the EFF turn 15 this month. They’re one of my favorite online security guides for at-risk individuals and I’m excited that not only is it still around, it continues to be updated: this month a guide on detecting BlueTooth trackers was added.

I didn’t know March 12th is the “World Day Against Cyber Censorship”, but for the Tor Project it was a good reason to introduce WebTunnel. WebTunnel is essentially a way to make Tor traffic look like ordinary HTTPS traffic, reducing the likelihood of it being blocked by censors. The Project reports that it works well in Russia and China but less so in parts of Iran, though the world of Internet censorship is a very volatile one and these things can change very quickly.

A short blog post from security company White Fir explains how to safely remove malware from a compromised WordPress site.