On Mon, 2025-06-16 at 10:02 -0400, Simo Sorce wrote: > On Fri, 2025-06-13 at 13:50 -0400, James Bottomley wrote: > > I agree it's coming, but there's currently no date for post quantum > > requirement in FIPS, which is the main driver for this. > > The driver is the CNSA 2.0 document which has precise deadlines, not > FIPS. The NSA "hopes" that the CNSA algorithms will be in FIPS by about 2030, yes. However, even if you have CNSA 2.0 requirement, it still includes several classical algorithms (it even includes RSA3072 which is, to say the least, a bit controversial). > That said ML-KEM and ML-DSA can already be validated, so FIPS is > also covered. The main worry everyone has is that while it is believed that there's not a quantum short cut over classical for lattice algorithms, they haven't been studied long enough to believe there's no classical short cut to breaking the encryption. The only real algorithms we're sure about are the hash based ones, so perhaps we should start with XMSS/LMS before leaping to ML-. Particularly for kernel uses like modules, the finite signatures problem shouldn't be that limiting. > > Current estimates say Shor's algorithm in "reasonable[1]" time > > requires around a million qubits to break RSA2048, so we're still > > several orders of magnitude off that. > > Note that you are citing sources that identify needed physical qbits > for error correction, but what IBM publishes is a roadmap for *error > corrected* logical qbits. If they can pull that off that computer > will already be way too uncomfortably close (you need 2n+3 error > corrected logical qbits to break RSA). The roadmap is based on a linear presumption of physical to logical qbit scaling. Since quantum error effects are usually exponential in nature that seems optimistic ... but, hey, we should know in a couple of years. > > Grover's only requires just over 2,000 (which > > is why NIST is worried about that first). > > Grover can at most half the search space, I assume you're thinking in terms of 2^n spaces, because for a search space of size s, classical brute force takes O(s) and quantum takes O(sqrt(s)). So if s=2^n then quantum takes O(2^(n/2)). Which is why the recommendation is to double the bits of security. > so it is not really a concern, even with the smallest key sizes the > search space is still 2^64 ... so it makes little sense to spend a > lot of engineering time to find all places where doubling key size > break things and then do a micro-migration to that. It is better to > focus the scarce resources on the long term. Well the CNSA 2.0 doc you cite above hedges and does a 1.5x security bit increase, so even following it we can't do P-256, 25519 or RSA2048 we have to move to at least P-384 and X448 (even though it allows RSA3072, I don't think we should be supporting that). So if we're going to have to increase key size anyway, we may as well up it to 256 bits of security. So even if you believe quantum is slightly more imminent than the Kazakh Gerbil invasion, we should still begin with the key size increase. Regards, James
