Schneier on Security

MarkH • April 8, 2020 12:49 PM

It’s a sign of the times, that this result wasn’t posted here (and I didn’t hear about it elsewhere) for a few weeks … a lot of us have had other things on our minds.

As usual, first-class work by INRIA.

The slow progress on challenge numbers confirms my judgment, that the cost of factoring even a 1024 bit semiprime with randomly selected factors continues to be many millions of dollars.

If the key generation wasn’t weakened in some way, and the asset under protection isn’t worth quite a lot of money to somebody, then your RSA-1024 secrets remain safe from cryptanalysis¹.

I felt rather sad when I read the INRIA announcement, because I learned from their dedication that Peter Montgomery died just a few days before they completed the factorization². He was a brilliant mathematician, who made vital contributions to computational number theory.

Every one of has made use of software implementing Montgomery multiplication³ … whether or not we were aware of it.

Some of his work of special interest to readers here includes analysis of certain side-channel attacks, and an algorithm to frustrate side-channel leakage.

¹ I did learn along the way that for roughly the price of a new car, you can now buy an off-the-shelf Hewlett Packard machine which (if I understand correctly) might be capable of performing the last step, which requires several terabytes of RAM. However, ascertaining whether such machines would really be up to a 1024-bit semiprime factorization is beyond my present knowledge.

² Montgomery played an important role in devising an algorithm which optimizes a gigantic matrix operation needed for factoring.

³ Years ago, when I realized that I needed to learn this “Montgomery multiplication” thing, I was able to download a facsimile of the first page of the paper in which he presented his work (the full paper was available only for purchase). I studied that page while riding somewhere on a train or plane; his presentation was so clear and succinct, that I was able from that fragment to make sense of what it was all about. For me, Montgomery multiplication remains one of those jewel-like innovations which is wonderful in its simplicity, and at the same time marvelous in its ingenuity.

MarkH • April 8, 2020 4:03 PM

@La Abeja, curious:

“I don’t believe it …”

I try to anchor my comments in facts and (hopefully) valid reasoning about those facts. That I believe or don’t believe something is a purely personal conclusion; since I’m not a recognized expert in any relevant field, why should anybody care what I do or don’t believe?

The same with “credible” or “not credible”, which are mealy-mouthed ways to say “I personally trust” or “I personally don’t trust” some source of information … rubbish!

If I have factual data on such a question, I’m pleased to write about it here.

Mr (or Ms) Bee: I don’t know what you’re talking about. Do you?

1. When RSA Labs put up the challenge numbers, they explained the process by which they were generated. This was extraordinarily thorough-going, probably because substantial money prizes were connected to some of these numbers, and they wished to minimize any suspicion of prizes obtained by cheating.

As I recall, the process included isolation of the computers on which the semiprimes were made, and physical destruction of their hard drives after the moduli were “read out”.

1. The INRIA results are, to the best of my knowledge, consistent with the “open literature” on GNFS factoring. The small population of experts who specialize in this stuff are always working on improvements to their factoring software.

GNFS is really complicated. The CADO-NFS package currently has about 440,000 source lines of code. To my limited understanding, most of the improvements are in some continuum between the fundamental algorithms and the mechanisms by which the software realizes those algorithms.

They’ve made remarkable progress, cutting running time by (at least approximately) constant factors of several, which will not be surprising to anyone who studies complexity theory in relation to such massive computations.

The extent to which they’ve published papers to document all of these improvements, I don’t know. However, the entire source code is freely available to anyone who cares to look.

In fact, if you’re interested, I believe you could install CADO-NFS on a small network of desktop computers, and try it yourself with smaller semiprimes of varying sizes. By plotting your results, and comparing them to the predicted running time formula, you could make your own informed judgment of how many core-years would be needed for semiprimes in the neighborhood of 800 bits.

MarkH • April 10, 2020 4:03 AM

@anon12:

It’s not such a dumb question after all. As you wrote, anyone applying RSA (in any sensible manner) would use a custom key.

Even so, what has been demonstrated is that up to roughly 850 bits, RSA is now practical to break in not many weeks, at a cost on the order of a few thousand dollars.

For ordinary applications, almost every implementation uses one of a few standard modulus bit-lengths. However, RSA is flexible enough that it’s easy to choose a custom length based on application constraints. One example would be microcontrollers with very limited memory capacity.

The way computation sizes grow for the best available RSA modulus factoring algorithm, the General Number Field Sieve, factoring a 1024 bit modulus remains very expensive … even though 1024 isn’t dramatically bigger than 850.

There is still no public report that anyone has ever factored a (properly generated) 1024 bit modulus. It’s sure to happen, but I wouldn’t be surprised if we wait a decade, or even longer. However, people who follow security recommendations switched to RSA modulus sizes greater than 1024 bits at least 15 years ago.