Post-Quantum Crypto/Cryptanalysis
Moved
I had to move this to here
where I'll go through Tanja Lange's PQ crypto course. Originally I was going to do all the courses but out of nowhere TU/e locked up all the lectures and assignments.
OLD TEXT
There is a variety of courses we can take by Tanja Lange at TU/e who with Daniel Bernstein (also now at TU/e) are the premiere researchers in post-quantum cryptography and cryptanalysis. If you're wondering why this is all done out of countries like the Netherlands now it's because it is impossible to build crypto in many other countries due to crazy export laws and standards body sabotage.
Let's try Selected Areas in Cryptology mixing the 2023/2021 versions.
- The first part Tanja teaches a crash course on existing crypto and the new post-quantum crypto research going on. Most of the exercises are breaking things.
- The second part covers cryptanalysis techniques. We can try some Cryptopals and MysteryTwister challenges too.
Begin
I'm starting with the recommended 2022 videos as prereqs.
- Motivation and Intro - Prof Tanja Lange
They already have quantum virtual machines to design and simulate running quantum algorithms and quantum cloud services where IBM has 433-qubit 'premium plan' available to the general public to run algorithms. Google/IBM are promising a 4000 qbit machine in 2025 while it's generally agreed you only need 300 qubits for 'quantum supremacy'.
Is any of these qubit claims by IBM/Google true or just marketing? Who knows but this motivation lecture explains that we should be ready anyway and start using post-quantum crypto now as all our countries are storing network data on a massive scale in order to break it years later for various illicit political purposes. She actually shows the NSA Utah data station that vacuums up and holds the world's data in football field sized buildings and notes the problems with existing software update signatures because they are never going to tell the public when they've achieved the ability to forge software update keys.
Basic concepts and intro
Watching this video. Channels spying on our data, and modifying it.
Tails and Qubes OS is mentioned. Tails is one of those 'anonymous live CD' type distros where the idea used to be that you would insert a usb (once upon a time just a CD/DVD), boot the shadow system and it would only live in temporary RAM memory and (hopefully) never touch the disk. You'd do whatever you're doing and then shut it down and there was (again hopefully) no evidence you used that computer. I'm not up to date on h4xor meme OS's but last I heard a few years ago nobody could verify that Tails or it's many clones actually wiped the memory upon shutdown. The idea of Qubes is a modified Xen hypervisor where every application is running in it's own virtual space so your browser can't access your data or other applications because there is a hypervized separation. Does this work? Dj Bernstein seemed to think so and was an active contributor to Qubes mailing list when Joanna ran it like writing his own memory efficient VM command/status tool (because Qubes VM tool was trash). Joanna Rutkowska who was the chief security architect and founder is no longer involved and they literally scrubbed her identity from the Wikipedia page so I have no idea who's running it now.
Public-key & Symmetric crypto
Watching this video from the prereqs. You probably already know about GnuPG or how public keys work. They way this used to work is you would post your public key and people who actually knew you would sign it authenticating that indeed it's your key. Of course the problem is if your key gets compromised then all past messages can be decrypted you aren't generating a new key for each message.
Counter-strategies against surveillance
Jacob Appelbaum disappeared after being cancelled and got his PhD under DJ Bernstein and Tanja Lange in the Netherlands studying post-quantum security. There is a very good recent interview here. Let's skim through his PhD dissertation Communication in a world of pervasive surveillance: Sources and Methods: Counter-strategies against pervasive surveillance architecture which you can get here. Reading the intro he singles out the US but there is just a single country now called the Fourteen Eyes who pool their resources for one gigantic intel budget sharing all the tech to spy on themselves and the rest of planet earth so US is just one piece of 13 other countries doing mass surveillance.
The paper he talks about on page 5 Another Look is here and is an interesting skim how 'provable security' is misleading and how if you extract the assumptions out of any proof and show they don't hold, you've invalidated the security proof and they give 14 recent examples where assumptions did not hold. The authors also point out that in 2018 over 24 new papers per week with 'security proofs' of protocols or 1251 per year were published by eprint.iacr.org and there just is no way to verify them all. 5.1.3 "If the IACR some day decides to give a special award to the most prolific flaw-spotter, our nomination for this honor would be Mridul Nandi of the Indian Statistical Institute. Nandi and coauthors have found fallacies in security proofs for several types of protocols." they must be breaking them for class projects in the grad courses he teaches. This is definitely a paper to save and read during the cryptanalysis part of the course we're doing.
Page 7 the clown show that is the Internet Engineering Task Force (IETF). Daniel J. Bernstein has a large posting history on the those working groups like the CFRG group exposing sabotage and writing very lengthy responses deconstructing protocols and proving they are are worthless. For example if you read his messages on mailarchive.ietf.org he repeatedly warns about the patents in many proposed lattice-based cryptosystems are a complete minefield waiting to be stepped on as the holder surely won't say anything until one those crypto systems is standardized then they can start suing.
The rest of this chapter is teenage political activist tier and more like a blog post than a dissertation, skip to hapter 2 this is what we came here for, it's nice when papers give you a crash course.