For corCTF this year, I wrote the challenge
oil spill, which is based on forging a signature in the unbalanced oil and vinegar signature scheme. It turned out to be much harder than intended, getting 3 solves total during the competition.
Unbalanced Oil and Vinegar
Unbalanced oil and vinegar is a multivariate quadratic based signature scheme. It has now been submitted to the new NIST post quantum signatures competition, along with other schemes such as MAYO. The signature scheme Rainbow, which attacked and broken and was a finalist in the previous NIST competition, also relies on UOV.
So how do UOV and multivariate quadratics work? A quadratic form is given by
Here, is an upper triangular matrix. Each element represents the coefficient of the term . The polar form of the following quadratic is
Notice that . This is true as
Therefore, the polar form is symmetric and linear in both and .
A multivariate quadratic map is then defined as
The multivariate quadratic map is a vector of multivariate quadratic polynomials in variables.
To sign some vector we must find such that .
To find such an , we need some secret knowledge (the secret key). If we know a subspace and such that
we can find for any quickly.
To do this, we pick a random vector and instead solve for a vector such that .
We can rewrite as
We know both and . Since is linear in and , we can use gaussian elimination to solve for our vector if we have a basis of .
Therefore, to sign a message , we must find such that , which is easy given .
In the challenge, we are provided a server which generates a multivariate quadtratic map (slightly smaller than NIST level 1 parameters) and a basis for .
In addition to this, we are provided two "oil spills" or hints.
- We are given a vector , where is a vector of and elements (hint hint lattice) and .
- We are also given the vector .
First, let be the vector "close" to . Then note that
Notice that since we know , we also know its map . Let this value be .
We know the vector on the right hand side, so what's left is the left. If we consider a singular equation , we see that
Since is a vector, this is basically an instance of the subset sum problem!
Lattices, after all
Consider the lattice spanned by the rows of the following matrix:
Consider the linear combination (here is the coefficient of when doing the modular arithmetic under )
This linear combination gives us the short vector
However, the density of the problem is too high for LLL, and typically LLL does not actually recover our vector . We can just run BKZ instead, with progressively higher block sizes until it finds the vector. I was able to recover it with a block size of 15 consistently.
Section 2: Recovering the full basis
Now we have the vector . Since we have , we also have a single vector .
Once we have a single vector in the oil basis, it is much easier to recover the full basis. There are two methods:
Brute force Groebner Basis approach
We want to recover another vector . What constraints do we have on our vector? We know that . This gives us polynomial equations in variables under . We can use a Groebner basis to solve this system, but it will run forever.
However, we know that . This means that we can fix variables in as constants, and then solve the reduced variable system.This is still not very doable.
Since we know , we know that . Therefore, we get another linear equations. So with all the information, we have variables, quadratic equations, and linear equations. This can be solved relatively fast with a groebner basis algorithm such as F4.
Finally, once we have found , instead of linear equations, we have linear equations and variables. This gives us more linear equations than variables, so we can recover the rest of the basis relatively easily.
Kipnis-Shamir like intersection approach
If we know one vector , consider the vector . Note that is a subspace of the vector, as we know . We can compute the basis of this kernel. From here, we can perform a Kipnis Shamir attack by finding the common eigenvectors of each , which will allow us to recover the full basis.
Bringing it all together
Once we have the full basis, we can just forge a signature to the random message sent, and we get the flag.
Some extra notes
- I (was thinking of) but did not add a proof of work, so one participant solved by reconnecting until an LLL-able instance is found, instead of using BKZ. I didn't really expect this, though there might have been some load on the server due to this. In hindsight I probably should have added a POW.
- This paper was released after I had written the challenge but before the CTF started. It details and provides an implementation of an algorithm to recover the full basis from a single vector. It is similar to the Kipnis Shamir attack, and was also used during the competition. I didn't really want my challenge to become an "implement the paper" crypto challenge, but unfortunately I got sniped. Both KS and Groebner are pretty well known attacks so I expected participants would use those. Hellman also pointed me to another paper after the CTF which also does a similar basis recovery and was published much earlier (thank you!).
- Hopefully the challenge was fun, I really enjoyed writing it 🙂 (get ready for oil spill 2 🙃)