When You Break Something, It Is Good To Fix It

When You Break Something, It Is Good To Fix It

Preface: In my work, I have moved to the point of telling people to stop telling me that something is broken or doesn’t work, to a point where, when someone poses a problem, I just ask them to go and find a solution, and propose the solution to me. There are perhaps more people in this world who can find fault in things, than those who can actually fix them. In my world, I want to work with fixers (and those who can find faults in things) rather than those who just break. So let’s look at some research, where the breakers also become the fixers (or, at least, propose a solution). For a Pen Tester or a Crypto Analyst, or, in-fact, any engineer, the ability to not only break, but also to fix, is a great skill that we need in this complex and dynamically changing world.

In Cybersecurity, there can be two types of people: someone who breaks things and then fixes them (or proposes a fix), and someone who break things and never fixes them (or even proposes a solution). For the latter, the breaks something, and leaves it for others to fix. But for the one, we look for people to break/crack things, and then show others how to actually fix the break. For academic research, you thus get researchers continually pushing methods to their boundaries and finding new vulnerabilities. But when they break things, they should, at least, try to fix them, too. One of my favouriate papers for this is led by the mighty Daniel Bernstein [here]:

In the paper, he took the McEliece method and broke it in seven days with a 200 CPU cluster. These days, we would be able to use GPUs and it would take a considerably less to crack it.

Overall, McEliece cryptosystem uses binary Goppa codes for an error-correcting method. For this, we define a vector space dimension (n), a code dimension (k), and an error-correcting capability (t). This defines a parameters set of (n, k, t), and which defines the security level, performance levels and sizes of hey keys. Normally n and t are select, and k is then derived from these.

In the method, we define a (n, k, t)-Goppa code of with a Goppa polynomial g of degree t, and which can correct up to t errors. The value of k is then n − t · log_2(n). Initially, we define a generator matrix of G, and which is k × n. We then select a random k × k invertible binary matrix S (defined as a scrambler) and then define a random n × n permutation matrix (P). The public key (G’) then becomes the multiplication of these matrices:

G’= SGP

and where S, G and P are the private key elements. To encrypt, we take the message (m) of length k, and add a random error vector (e) to give the ciphertext of:

Bob then decrypts with:

At this stage, we will use another matrix (H) to determine the syndrome and identify where the errors are. As the position of the error would have changed because of the permutation matrix, we need to remap the position of the error. Here is an example of this process using Hamming codes: [link].

In McEliece’s classic paper, the parameters used were (𝑛,𝑘,𝑡)=(1024,524,50). So while the broke the method, they proposed (1632,1269,33) (80-bit), (2960,2288,56) (128-bit) and (6624,5129,118) (256-bit). These days, the 80-bit definition is a non-starter, and would be seen as being insecure. A more recent paper brings McEiece provides a more up-to-date foundation for McEliece [here]:

In the paper they propose (1702,1219,45) for 80-bit security and (3807,2891,77) for 128-bits. But things have even moved on since then, and the submission of McEliece has increased to the value of n to at least 3,488 and a t value of 64.

With McEliece348864 KEM, we have parameters of n=3488, and t=64. For McEliece460896 KEM, we set n=4608, and t=96. With McEliece348864, we have a base level security of level one ( 128 bit AES security). We can see that McEliece348864 gives us large keys of 261,120 bytes and 13,568 bytes for the public key and the private key, respectively:

As can see that McEliece6699128 pushes the public key to over 1MB. On the upside, McEliece provides the smaller ciphertext for the key encapsulation process.

Here is the C program implementation of McEliece for Key Exchange:

and the C code:

and where you run “./kem” once compiled:

Conclusions

In a post-quantum world, lattice methods are the King of the Hill. But, we need an alternative… just in case … so McEliece is likely to be around for a while. A 1MB key might seem quite large, but, for security, it may be worth it. At least, it’s not a 1TB key that would be required for our RSA methods in the post-quantum era. For me, I love the McEliece method, and it takes me back to the days I studied Hamming methods and their amazing properties of fixing errors. I will, too, never forget the first demos of the CD player, and where Reed Solomon codes were used to fix the damaged areas on a CD-ROM: