UCL Project Suggestions 2021 – Dr Nicolas Courtois

Here are some projects by Dr Nicolas Courtois proposed to final year CS students (MSc Information Security and MEng and Mathematical Computation):

1. Product Attacks on Four Versions of DES.

Description: We will study attacks of type P=R05*L07*(R28+1)*(L27+1)*L32 or (1+L06+L07)*L12 * R13*R24*R2 is invariant for 2 rounds of DES. In other words, if P=0 at input, then P=0 also at output after 2 rounds of encryption. This for a fraction of the key space. We will see how this type of attack works for four major versions of DES and compare their security side by side. We dispose of a database of ready attacks generated by a previous student focusing on single variables, we will extend it a bit using also sums of two variables and filter attacks which work neatly for 2R specifically.  Then we will select an optimal attack and generate a set of S-boxes for which the attack works.

Prerequisites: COMP0058 and SAGE maths tutorials and labs, COMP0025. Block ciphers, symmetric crypto, Boolean functions, hash functions, scientific programming skills, mathematical proofs, polynomials, finite fields, modular arithmetic, abstract algebra.

2. Weak Keys and Weak and Strong Long-Term Keys in Feistel Ciphers

Description: We will study four versions of SM3, two versions of SHA256, T-310, DES, GOST, KeeLoq and many other Feistel ciphers. We will be looking at ways to aggregate differentials so that certain output linear combinations remain constant. We will look at how designers made the cipher secure or not for truncated differential attacks with their choice of long term key and wiring. Extensive computer simulations, databases of events, learning feedback loops and visualizations, stats. We will look at how several points can simultaneously belong to an affine space. We will study the probability of events: how likely it is that certain events can happen accidentally.

Prerequisites: COMP0058, COMP0025. SAGE maths and Python programming. Mathematical proofs, polynomials, finite fields, modular arithmetic, abstract algebra, Boolean functions, annihilators.

 

 

3. Obfuscation and Prime Order Cycles derived from Block Ciphers

Description: We will study how cycles of prime order and groups with obscure representation and with efficiently computable automorphisms can be constructed from a block cipher operating on 2^n elements. This is similar like a walk on a finite field one cycle visiting all points except zero. The size of our cycle is a prime NOT dividing 2^36-1. Elements of our cycle can be added with a group operation but the result does not always belong the the same cycle. This is a little bit surprising and requires some technical special setup, it does not work in general for every block cipher. We will work with T-310 block cipher.

More generally we study how a group with highly non-linear transformations can operate on a polynomial ring, the degree of polynomials goes up and down and we obtain a cycle. The block cipher and concrete polynomials themselves make that the binary representation of the elements of this group is quite rich in mathematical properties. The block cipher generates a large group (with invariants), polynomials lie in a Boolean polynomial ring. Main goal: mapping what is observed to known mathematical objects unique up to isomorphism. 
It is about constructing a novel INEFFICIENT and obscure implementation of a known mathematical object. 

Prerequisites: COMP0058, COMP0025, COMP0061, COMP0143 and old project D73. SAGE maths and Python programming. Mathematical proofs, block ciphers, linear cryptanalysis, polynomials, finite fields, modular arithmetic, abstract algebra.

 

4. Adaptor Signatures or One-time Verifiably Encrypted Signatures 

Description: We will study the topic of so called Adaptor Signatures, and similar other extensions of the concept of digital signatures. Adaptor signatures allow encoding of a hard problem within the signature itself. This functionality is a key building block in blockchain systems and in particular with payment channel networks. It is a system where where money are exchanged against the disclosure of some information without a trusted third party. One method is Schnorr one-time VES, see Section 4.1. here

Prerequisites: COMP0058, COMP0025, COMP0061, COMP0143 and old project D73, COMP0025. SAGE maths and Python programming. Mathematical proofs, polynomials, finite fields, modular arithmetic, abstract algebra, discrete log, security proofs.

 

5. Cold War Cryptography and Modern Block Ciphers.

Description: We will study how to break various historical ciphers such as East-German T-310, DES, Russian GOST cipher etc. We will exploit invariant attacks where a certain set of constraints remains unchaged after one round of encryption. We will study violations of the Markov cipher theory and how differentials propagate. Main reference: https://eprint.iacr.org/2018/1242 and new papers.

Prerequisites: COMP0058 and SAGE maths tutorials and labs, COMP0025. Block ciphers, symmetric crypto, Boolean functions, hash functions, scientific programming skills, mathematical proofs, polynomials, finite fields, modular arithmetic, abstract algebra.

6. Backdoors in Enigma and Classical Crypto Machines

We will look how a malicious choice of a rotor makes a WW2 encryption machine like Enigma vulnerable to attacks and to reverse engineering. We will look at how a product of two or more permutations can be factored. Likewise we will study the Russian Fialka cipher machine. 

Prerequisites: COMP0058, basic crypto, some bits in maths like modular arithmetic and linear algebra. Some code breaking skills like language-based cryptanalysis, cribbing, stats, biases, bigrams etc. Combinatorics such as random permutation statistics.

7. Algebraic Polynomial Invariants and Codes Defined Over Elliptic Curves

Description: We will study violations of Hasse theorem and special choice of an elliptic curve and a base point. We will look for results such as Theorem D73 deep inside https://eprint.iacr.org/2017/440. We will study special elliptic curves where more such results are true.

Prerequisites: COMP0058 and old project D73, COMP0025. SAGE maths and Python programming. Mathematical proofs, polynomials, finite fields, modular arithmetic, abstract algebra.

 

8. Stealth Address, Ring Signatures, ZK, Anonymous Staking

We will study the privacy techniques in Monero, ShadowCash, SpectreCoin, ZeroCash and recent research on these topics..

Prerequisites: COMP0058, COMP0025, COMP0061, COMP0143 and also COMP0054. Experience with crypto protocols and crypto source code and implementations. Some provable security. SAGE maths and Python programming. Advanced PK crypto: ZK proofs, ring signatures, multi signatures, etc.

9. Recovery of Private Keys for Bitcoin Wallets

Group projects are possible here. We will develop and implement an attack which consist of discovering a private key of a bitcoin wallets due to a mathematical theorem. Requires EITHER extensive programming with several complex open source projects, and extensive work gathering huge quantities of data. OR inspection of source code for multiple wallets. Some of our earlier work on this topic can be found here. We will also work with graph visualisation in SAGEmaths or graph databases or other similar graph tools. We will work wtih RNGs, OpenSSL, Microsoft Crypto API etc, RNG in Intel CPUs etc. 

Prerequisites: COMP0058, COMP0025, COMP0061, COMP0143. Also COMP0054. Basic crypto, good programming skills, engineering background, maths, modular arithmetic, linear algebra,  elliptic curves (project D73). SAGE maths and Python programming. Write simple mathematical theorems with proofs.

10. Carlitz Rank and Cryptanalysis

We will develop methods to approximate arbitrary permutations by linear fractional transformations. This is related to cryptanalysis with AES S-box and Enigma WW2 crypto.

Prerequisites: COMP0058, COMP0025, COMP0061, COMP0143. Basic crypto, semi strong on maths, modular arithmetic, linear algebra. Boolean functions. SAGE maths and Python programming. Simple mathematical theorems with proofs.

11. P2P Health Cooperative

We will build a censorship resistant system where people can exchange with peers their experience about whether their Covid or cancer treatment works. Main focus: fighting deep pocket corruption and fake information and fake user infiltration attacks. 

Prerequisites: Crypto currency, Android programming, blockchain integration, P2P networking, applied cryptography, writing patent applications.