New Lattice Cryptanalytic Technique

A new paper presents a polynomial-time quantum algorithm for solving certain hard lattice problems. This could be a big deal for post-quantum cryptographic algorithms, since many of them base their security on hard lattice problems.

A few things to note. One, this paper has not yet been peer reviewed. As this comment points out: “We had already some cases where efficient quantum algorithms for lattice problems were discovered, but they turned out not being correct or only worked for simple special cases.” I expect we’ll learn more about this particular algorithm with time. And, like many of these algorithms, there will be improvements down the road.

Two, this is a quantum algorithm, which means that it has not been tested. There is a wide gulf between quantum algorithms in theory and in practice. And until we can actually code and test these algorithms, we should be suspicious of their speed and complexity claims.

And three, I am not surprised at all. We don’t have nearly enough analysis of lattice-based cryptosystems to be confident in their security.

EDITED TO ADD (4/20): The paper had a significant error, and has basically been retracted. From the new abstract:

Note: Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.

Tags: cryptanalysis, cryptography, quantum cryptography

Posted on April 15, 2024 at 7:04 AM • 33 Comments

Comments

Parzo • April 15, 2024 8:18 AM

Hard not to layer geopolitics over the top of this. Not a crypto person at all but I’d have thought that a serious potential attack on PQC is basically the textbook definition of a capability you wouldn’t declare if you were China.

Clive Robinson • April 15, 2024 8:56 AM

@ Bruce, ALL,

With regards,

“I am not surprised at all. We don’t have nearly enough analysis of lattice-based cryptosystems to be confident in their security.”

Which is why I an concerned at two things,

1, The push against hybrid systems.
2, The push for only lattice systems.

Kind of reduces the eggs and basket argument to one egg with one dodgy basket.

echo • April 15, 2024 9:19 AM

I was lost after the first sentence. If I had the confidence of your average transphobe I would then go on to opine at great length about a subject I knew nothing about and claim the sky was falling in.

One question I would ask is what would any system look like if we assumed an arbitrary time to encryption being broken. For 99% of stuff it doesn’t matter to me one way or another whether it’s encrypted or not. Expanding out from there what are the practices and mitigations you need as the need for encryption and the chance of it being attacked goes up. That’s my dumb stupid question. Someone must have a report lying around gathering dust answering that one.

Growing up before the internet was a thing I’m not personally bothered if it went away overnight as long as the libraries were resourced and various social structures and whatnot were in place. Banks and diplomatic services and the military and the like are big enough to look after themselves.

Crikey. I’m old enough to remember when China was in the news maybe once every few years and they rode around on bicycles, there was occasional news footage of Breshnev (who seemed to live forever) scowling and food queues in the Soviet Union, and Americans were loud people with checked trousers and big cameras, and Dr Magnus Pyke was a thing. Mind you women’s rights was really crappy back then.

Anyway, I’m done with this topic. I couldn’t even tell you what a “hard lattice” is. Lattice pastry sure but not that.

Clive Robinson • April 15, 2024 10:01 AM

@ echo

Re : Not the method but the results.

“I was lost after the first sentence.”

You are not, nor will you be the only person to suffer from this.

Let me ask you a question,

“Do you need to understand the infinitesimals of the Carnot Cycle to drive a car?”

Of course not, nor does a mechanic to service the car and keep it running safely and we hope to published specification (yes I will duck at this point due to certain manufacturers cheating).

You do not need to understand the algorithms at that level.

However at a higher level yes.

HTTPS enables us to use unproven trickery to hide the transfer of a “shared secret” used as a “Root of trust”

At it’s simplest you can transfer a long integer that you can use as a crypto key for say AES in some chained mode.

If you as the first party and your bank / financial house are the second party and no third parties can find that long integer in less than say a hundred years then you might consider it safe to do “on line banking”.

But what if someone comes up with an attack that reduces the search time to say ten years? Would you still consider it safe?

I don’t but then I’m supposedly “paranoid” about security (untill I’m shown to be right usually within a decade or so then I’m seen as a “lucky guesser” or “ahead of the curve”…).

So you don’t need to know the details of the method, but you really do need to know what the “likely” worst case for you results will be (ID theft having life savings / pension stolen etc).

It’s not just vast news breaking crypto-coin sums that go missing on people not understanding the results of not using cryptography safely, it’s little sums as well.

These lattice algorithms are supposed to stop one class of potential future attack. The problem… The chances are you’ve already compromised you “roots of trust” some years ago, as we know certain people collect such data…

So at some point if these methods do become in use, you are already compromised so will need to change all your roots of trust.

Do you know what makes your “root of trust” provably not, but that means you could make superficial changes that don’t in reality change a thing.

And that’s a problem because the banks and financial houses do not want you protecting yourself for various reasons, not least because they can hide their failings behind it…

Emoya • April 15, 2024 11:49 AM

Generally (without needing to understand all the specifics) …

From its outset, formalized mathematics has produced difficult-to-solve problems and over time a handful of these problems have remained unsolved. Cryptographers attempt to find creative ways of utilizing special classes of these problems, collectively called trapdoor functions, to publicly send secure messages. Trapdoor functions are defined as having easy/efficient solutions in one direction, but not in their inversion without having specific knowledge (i.e. decryption key). This is the basis upon which nearly all modern public-key cryptography is built.
The problem is that the security of these trapdoor functions relies entirely upon their non-invertibility, and there is no proof that true trapdoor functions even exist, as it is intrinsically tied to the P vs NP problem. Since quantum algorithms have been identified that possibly compromise existing widely used trapdoor functions, others have been submitted as potential replacements, one being certain operations over lattices.

The viability of any trapdoor function is fundamentally based on two things:
1) An efficient inversion is not discovered in either the classical or quantum computation spaces.
2) It is not true that P=NP.

Proof that P=NP means that trapdoor functions are impossible and that an efficient inversion must exist, even if one has not yet been found.
Proof that P≠NP implies only that trapdoor functions can exist, not that those we might believe to be are, in truth, one-way. Mathematical breakthroughs will always be a threat to a suspected trapdoor function unless proof of its one-wayness is also possible.

Even under the assumption that P≠NP and that a securely implemented cryptosystem leveraging a proven trapdoor function is achievable, there will always be ways in which it could be subverted, as Clive pointed out.

In other words, security will never be absolute.

echo • April 15, 2024 2:14 PM

Anyone here to talk about the maths can ignore me unless they want to ruin their career.

@Clive

Did I just get mansplained? o_O

I just can’t be bothered to write up paragraph two partly because I’m lazy and, er, partly because I’m too lazy to ask questions to fill in the bits I don’t know. I’m not sweating it. The majority of traffic is junk. A lot of critical information expires fast or doesn’t even touch open communications. Heck, some critical stuff needs “wet ink” on paper and sits in a very offline cupboard. Even with a guaranteed three day limit to encryption being broken damage can be stopped or limited. Some legacy systems might be stuffed but that’s another problem. Assuming encryption can be cracked in three days flat or fail completely someone needs to do a desk exercise on this on the “just in case” basis. Would it have ramifications? Sure. Again, I’m not bothered. It’s just something you deal with. I’m too lazy to even begin thinking it through but there’s some interesting possibilities and things. There probably is a report or reports gathering dust somewhere on which planning can begin now for various scenarios and if there isn’t someone should get on with it instead of lunching with newspaper editors.

Now the excuse for saying this is out of the way I do like a good lunch. There was this lunch once where I opened my mouth to the chief of a regulatory body and the then Conservative government afterwards watched ordinary working people take £500 million off the treasury as a line in regulation changed by means mysterious which removed a policy deadlock. I thought it was funny even if they didn’t which is why that particular budget item was removed after it was cleaned out. Still, that was the Conservatives champagne fund £500 million lighter in the pocket so mission accomplished.

So £500 million down and one CEO down and that’s only two lunches involving “plaintext” information. I don’t know anything which isn’t public information or which someone isn’t stupid enough to tell me. I don’t know about hard lattice problems and roots of trust. Like, maths gives me a headache and I’m my own root of trust and I don’t even trust me! Lattice pastry and unguarded moments that I can do. The value isn’t in the information it’s in the information and knowing who to give it to. So does anyone else want to buy me lunch?

Oh don’t worry. I’m messing about, mostly. I just can’t help myself when opportunity knocks.

Clive Robinson • April 15, 2024 4:27 PM

@ echo,

“I just can’t be bothered to write up paragraph two partly because I’m lazy “

So you wrote up three paragraphs of irrelevant self promoting nonsense yet again.

Oh and yet another threat,

“Anyone here to talk about the maths can ignore me unless they want to ruin their career.”

This thread is about the maths so why are you still self aggrandising like a low rent “Drama Queen”

As for,

“Did I just get mansplained”

Oh dear yet more Misandry[1] from you the answer is clearly no except in your perverted head. So can we assume you are going to Australia in the near future to be the next one?

But I guess like most of your other nonsense you will be a self promoting failure who talks big but only ever tells bull.

[1] The odd thing is with it’s very rapid increase misandristic behaviour is very much on the rise, but because of significant bias in the MSM we don’t get to hear about it and the very real harms it causes. In short,

“Misandry is the hatred of, contempt for, or prejudice against boys and men in general, and is often associated with the suffering of males being mocked, minimised, dismissed…”

It is a scourge from a particular type of very venal “poisoner” mentality.

You call people out on it and you can hear the venomous hissing from miles around. And when called on it the you get the misandrist pretense of “joking” which fails to hold any credibility, because it’s not, never was and never will be funny,

‘hxxps://counsellorinleeds.co.uk/blog/misandry-stop-saying-kill-all-men/

‘hxxps://www.psychologytoday.com/us/blog/rethinking-men/201010/why-some-people-have-issues-men-misandry

But also there are surprisingly to many a rapidly increasing numbers of female misogynists,

‘hxxps://www.psychologytoday.com/us/blog/the-mysteries-love/201908/12-ways-spot-female-misogynist

Have a look down to the “She Devil” characterisation,

“She is host to dark personality traits. Her firm belief that she is superior to other women points most strongly to narcissism. But narcissistic traits are also routinely present in borderline personalities and psychopaths. In the general population, dark traits tend to be subclinical, which means that they are not associated with the level of dysfunction seen in clinical cases. But mixing high functionality with sinister character traits is more likely to give you a Molotov cocktail than a Cosmopolitan.”

But echo “high functionality is what you ain’t got”, so I guess more an “old 70’s boilermaker” failing to be a depthcharge.

Erdem Memisyazici • April 15, 2024 5:35 PM

Sort of unrelated but I got around to using a simple protocol for exchanging JWT tokens between services and I was wondering since you guys are well informed if you could scrutinize the weaknesses that may be apparent.

I posted it to crypto.stackexchange for commentary. The HMAC(RS, C) part is pretty much TOTP without the (mod integer) part from RFC-6238.

Your comments will truly help me improve. I rotate RS is rotated daily starting from an initialization value. K1 for all services are rotated every 6 months which I thought was fairly well for what it looks to me like quite a few years of computation time to get the keys by bruteforce. Since it’s not RSA there are no shortcuts with any other way that I can see either.

echo • April 15, 2024 6:43 PM

@Clive

So you wrote up three paragraphs of irrelevant self promoting nonsense yet again.

It’s a bit of a stretch I agree and by the gods don’t we know when you do it. O_O

This thread is about the maths so why are you still self aggrandising like a low rent “Drama Queen”

That’s why I put a “please do skip if you’re here for the maths” comment right at the top, and everyone ought to know by now I’m a chatterbox.

Honestly, Clive. Calm down or you’ll give yourself a thrombosis. You could have just gone “Sure, fair point. Hah hah I know what you mean fair play.” and that would have been it so I don’t know what the page of hurty words were for you big meanie. Clive, I would dazzle and amaze you if we had lunch so stop moaning. You know you love me really.

As for the maths I don’t have the foggiest what anyone is saying and I’m not being paid to enjoy it so…

BCS • April 15, 2024 6:54 PM

If we take as given that we a finite fraction of deployed systems will be found, after being deployed, to have fatal classical or quantum attacks, how would we build a secure system under that assumption?

I’d think the best solution would be a combination of huge safety margins (e.g. 10x key sizes) and N-fold hybrid systems.

If we already have symmetric encryption functions that are.proven to be no more vulnerable to quantum than classical attacks, a few of those layered would seem to be practical for channel encryption. Channel setup could be done via secret sharing and multiple PQC functions. Authentication would also be easy by just allowing multiple independent signatures (which would also improve robustness in the face of a CA brach). All that would take (other than protocol tweaks) is a low order multiplication of compute and a bit of extra bandwidth during startup.

It seems like this should all be an easy way to guard against the unknown.

Clive Robinson • April 15, 2024 7:22 PM

@ echo,

“That’s why I put a “please do skip if you’re here for the maths””

You did nothing of the sort, what you said was very clearly a threat,

“Anyone here to talk about the maths can ignore me unless they want to ruin their career.“

As for,

“Sure, fair point. Hah hah I know what you mean fair play.”

You consider threatening people “fair play?” The you really are deranged.

As for,

“I would dazzle and amaze you if we had lunch so stop moaning.”

No you would not, not in the past, not in the present and certainly not in the future.

If you look up the statistics the favoured murder weapon of many women is poison.

So I’d have to be tempting death by eating anything you have made, touched or just been close to in a whole manner of ways.

Oh and I see back to your old stalker ways again,

“You know you love me really.”

I never have, and I never will. But something tells me from the abuse and threats you throw out probably nobody actually loves you and your truly abusive ways.

As for,

“As for the maths I don’t have the foggiest what anyone is saying and I’m not being paid to enjoy it so…

Rather than go and do something actually productive you thought it would be fun to ruin the thread for every one else with your threats and nonsense…

And you wonder why people raise frequent complaint against you.

echo • April 15, 2024 8:06 PM

@Clive

Oh, Clive lighten up for God’s sake. You said “You did nothing of the sort, what you said was very clearly a threat,” to what was clearly a melodramatic joke that people could stick to the po-faced maths or end up in a silly conversation. Look at the page of old man desk banging you’re pulling now! It kind of proves the point.

So I’d have to be tempting death by eating anything you have made, touched or just been close to in a whole manner of ways.

I was thinking more chicken pie at Claridges with a glass of champagne, or the Savoy so I could outrage decency by having a cigar in the cigar lounge if anyone is paying but you do you.

Don’t you remember the days when we used to talk so romantically about silenced pistols? Oh, it seems so long ago. Honestly, can you dial back the shouty paranoia? At least have two fingers of whiskey to take the edge off before you start.

plz stahp • April 15, 2024 9:11 PM

10:01 was polite and informative.

4:27 took it beyond what anyone else cares about

Let 2:14 stand on its own merits, and more. Generative AI affects us all (stupidly, or worse. I don’t have £500 million, so I don’t know)

MrC • April 15, 2024 9:45 PM

Classic McEliece is looking better and better.

Clive Robinson • April 16, 2024 2:27 AM

@ echo,

Re : Read as written

“Clive lighten up for God’s sake. You said “You did nothing of the sort, what you said was very clearly a threat,” to what was clearly a melodramatic joke”

You keep pulling this nonsense

1, You make repeated threats
2, You get called
3, You pretend it was a joke
4, You hope @Moderator deletes it

It’s why I’ve repeatedly asked @Moderator not to delete it, so that your actual MO can be pointed out to people.

If you think threatening people is funny, then you really should seek professional help

As for Claridges I would not be seen dead in there, it’s at best a fusty old hole replying on a past reputation hoping to drag in US stars and the like who have more money than sense. I’ve certainly got better taste.

As for champagne don’t make me laugh, it’s over priced over rated and a drink for silly people to get skinned on. Even vintage bolly is inferior to several new world wines at a tenth the price.

I’d much prefer a sparkling water with a twist of citrus, it’s way better all round. That’s because I prefer to actually taste my food.

But then it appears you are as clueless as ever pretending to have a “james bond” life style. I suspect your reality is not even up to Grandpa Potts doing guard on the privy.

echo • April 16, 2024 10:16 AM

@Clive

I’ve commented on a desk exercise on hardening/refactoring, plaintext sources in the open and on the inside versus secure transmission systems, and post a bit of fluff and silliness to amuse myself which people can always skip past. So I no idea what your wall of snide is for. Like I said. If you’re up to no good it’s your reputation Mr Scowly Pants.

I have a page in draft explaining how things tick from my perspective but the mood isn’t right and it’s really not the topic for it so I’ll save it for another day maybe.

Emoya • April 16, 2024 3:35 PM

@ MrC

McEliece (code-based) is certainly better understood at this point than lattices, even if it is less convenient. If the choice is between robust + unwieldy vs uncertain + efficient, I would choose the former and be judicious in its use.

@ BC S

The issue is that understanding the true potential (and limits) of quantum computing, taking full advantage of it through quantum algorithm design, and addressing its impact on established security are all relatively still in their infancy, but are inseparably linked. Advancement in one is dependent to a significant degree upon that of the others.

There will undoubtedly be a repeated cycle of…
1) Identify a secure (enough) algorithm and implement
2) Build a bigger quantum computer and/or algorithm that undermines security
3) Repeat
…at least until the technology reaches a significantly higher maturity.

This has been the history of cryptography in general and will continue indefinitely unless there is a significant fundamental breakthrough.

At this point, we can’t be certain how resilient any proposed public-key PQC algorithm will be in the long run.

Quantum key distribution (QKD) could be leveraged as a stand-in for public-key crypto in certain cases, within its present limitations, basically countering like-with-like.

Clive Robinson • April 16, 2024 5:48 PM

@ Emoya, MrC, ALL,

Re : How inefficient to be secure?

“If the choice is between robust + unwieldy vs uncertain + efficient, I would choose the former and be judicious in its use.”

A little history for you…

I first read about McEliece crypto way back last century.

And yes it was inefficient as a cipher, it was also inefficient as a correction code.

That is still true today, and you will often here it or a variation of it said.

However as a combined cipher and error correction system it’s not that inefficient and in fact more efficient than other PQC systems that are seen as “just crypto”.

I investigated on my own about as far as I could go without other input. So in 2000 I asked a few “experts” in the crypto field about it… Basically they knew it’s name and it’s alleged reputation and that was about it… (Yup read that again whilst your jaw drops).

For various reasons one of the “There be dragons here” of security is “do not segregate”.

Quite simply McEliece had got a bad rep over a mantra…

In a way I played my part, I’ve always noted that people should take care with the balance of,

“Security v Efficiency”

But noted that the concerns were increasing complexity and increasing side channels and transparency in systems.

And further noted that those with sufficient knowledge could avoid the pitfalls but at the risk of fragility.

As such it’s like the oft heard mantra of,

“Don’t roll your own crypto”

But as with AES and the NSA rigging the contest through “advising NIST” we ended up with about the most insecure of crypto code you could imagine, written by the supposed “experts” in the Open Community.

Why because the NSA ensured two things,

1, All submitted code would be “publicly posted”.
2, Part of the competition requirements would be a “speed competition”.

What was known back then but not much talked about and to be honest is still not much talked about today is that the processes of increasing speed significantly opens up time based side channels…

The result was that the worst possible software implementations as far as “distance evesdropping” were concerned became the “reference code” for nearly every AES and security library there was…

I’ve pointed out this quite a few times over the years on this blog and other places but of nearly all the alleged “security experts” in the field they effectively “whistle and look the other way”.

I’ve even pointed out that there was a history of this going back before the NSA was formed and it can be traced back to an individual, his wife, and a mechanical engineer who set up a crypto company in Zug Switzerland.

Now consider,

https://www.schneier.com/blog/archives/2024/04/backdoor-in-xz-utils-that-almost-happened.html

This sort of game has been going on since the start of mechanical cipher systems before “The Great War” or “World War One”(WWI) as we now call it.

Some have noted that there has been “odd recommendations” like “No Hybrid Systems” with PQC and Conventional Crypto Algorithms.

So keep your eye on the McEliece PQC system especially those who take strong positions on it pro or con. And above all check their work, not for what we know but what we incorrectly assume.

Remember,

“Many a traitor wrap themselves patriotically in the flag.”

Or more simply

“The best place to hide a lie is in the plain sight of the truth.”

If nothing else after AES we had the NSA push that backdoored Dual Eliptic Digital Random Bit Generator and a couple of other suspect systems.

Does anyone realistically think the NSA or any other SigInt Agency around the world has given up trying to subvert the crypto that

“Gives the ordinary citizen privacy from the tyranny of the State”

Or the lazy law enforcement agencies and their “desk jockey” manned “National hyper agencies” run by so amenable “useful idiots” to political influence if not control.

Yup it sounds like paranoia or conspiracy theory… But all I say is,

“As there is an identified track record of such behaviours a wise man would keep his eyes open and his face blank.”

echo • April 16, 2024 8:11 PM

@Clive

So you can have an opinion without having a moment? I knew you had it in you. I know security as defined by a traditionally male dominated industry is a bit of a fidget spinner for men but I do have a different point of view and it’s valid enough within security theory. We may never agree but I have my opinion and I’m not going to shut up about it.

Does anyone realistically think the NSA or any other SigInt Agency around the world has given up trying to subvert the crypto that

“Gives the ordinary citizen privacy from the tyranny of the State”

Or the lazy law enforcement agencies and their “desk jockey” manned “National hyper agencies” run by so amenable “useful idiots” to political influence if not control.

Yup it sounds like paranoia or conspiracy theory… But all I say is,

Um, well, yes and no. I know 0.01% of the maths needed to talk about it and my knowledge of cryptology is thin to say the least. I’m sure the tension between security and cracking is there. I guess and it is only a guess that analysts might have a slight clue as to where advantages are or not. How well they can be exploited I have no idea. Then there’s traffic analysis and profiling and perhaps analysis which can be overlooked. Then there’s politics and policy and maybe even office politics, and open source intelligence and leaks intended or otherwise from bad actors or inside sources.

Encrypted traffic and encrypted storage only mean something in some contexts. I live in the world of analogue and plaintext. There’s enough there to keep me busy and where 99.9% of the activity and threat environment is whether online or offline or in the open or behind closed doors.

I don’t personally feel threatened by door kickers or intelligence services and annoying as law enforcement can be am not especially threatened by them. Politicians and dodgy oligarchs maybe. The ones who are a problem are the ones who give everyone else a problem.

“As there is an identified track record of such behaviours a wise man would keep his eyes open and his face blank.”

Pronouns, Clive. It’s 2024 not 1824. I know the Garrick club is behind but even so. There are people who want to genocide people like me whereas you’re a cisgender heteronormative male so yes I do think you’re being a tad angry and paranoid.

You really do need to pay attention to Helena Kennedy and Judith Butler. Oppressive systems don’t just harm women they harm men too. It feeds into a cycle of violence and emotionally damaged and cold men and authoritarian environments. This is partly why I maintain that the best security is a good society. Men have vertical power but women have social power which is horizontal. It’s one reason why women prioritise self-care and support networks and have a higher in-group out-group bias.

If you insist on being angry and paranoid I have another one for you: “Women are a conspiracy against men”. Well, yes and no. As much as men want to build things women want everyone to be like other women. It doesn’t make men lesser men. In fact there are generational changes happening. Men feel better for not living in an uptight monochromatic world and enjoy parental leave. Work life and home life is becoming better and more equal. Not everywhere and not for everyone but the trend is there.

A century ago people like me barely existed and I would never have been able to treat myself to lobster and champagne in an art deco restaurant, or wear the kind of clothes that get me called a lady and good service to match. That’s what encryption gets me. I couldn’t give a stuff about the rest of it as it’s completely irrelevant. I’m not making a particular point but as you brought them up if you re-examine the Bond novels ask yourself who the smartest person in the room was. It wasn’t Bond.

As I said right at the start I’m lost after the first sentence. I just know what it means to me and that’s all I need to know. All the high forehead types and spooks and doorkickers can do their job and I’ll do mine which is pootling about and being a Womble. It’s less stress!!!!

plz stahp • April 16, 2024 8:12 PM

I have a page in draft explaining how things tick from my perspective but the mood isn’t right and it’s really not the topic for it so I’ll save it for another day maybe.

Please don’t. I would use the input box labeled URL: to link to a personal blog.

For those of us who are interested in your personal state of mind on related security stories, we can then read it now or later, even if the mood isn’t right

echo • April 17, 2024 5:33 AM

@plz stahp

For a start you have no idea what was in the draft. And you’ve ignored paragraphs 2,3, and 4 in my last post. There’s more content in there than Clive triggering himself and going off on angry paranoid arm waving. And state of mind or mental fitness is a security topic in its own right.

Maths and physics is a topic but doesn’t tell you anything more than that. Then we have the old “second law of thermodynamics” thrown around by some to sound clever. It doesn’t apply to human decision making or creativity within a local system or tell you what you should or shouldn’t do. Then we have wheeling off into “dark triad”. That doesn’t say a lot either before we start trotting into things like abuse of power and DV and, drum roll, state of mind and mental fitness and supporting structures. See also paragraph 2, 3, and 4 but also paragraphs 5, 6, 7, 8, and 9.

Just because something is dressed up in formal masculine technospeak doesn’t make it any more right or valuable or useful. Sometimes it’s less so.

Anyway, I don’t do maths so you’re free to skip it unless you want a self-inflicted life defining moment.

Z.Lozinski • April 19, 2024 8:35 AM

There is an updated (18 April 2024) version of Yilen Chen’s 2024/555 preprint on the IACR server.

“Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today”.

The error is quite technical and it has taken a week of careful analysis to find it.

My prediction. There will be more novel attacks on lattice systems. We should plan on seeing a serious paper every quarter. This is good, because we need to increase confidence in lattice cryptography. Or find alternatives, but 9 years of the NIST process hasn’t done this.

We need to plan on how to be ‘cryptographically agile” how do we replace cryptographic suite? Right now this is not something we can do automatically. There is relatively little public information on how long it takes to to replace a cipher system. In practice it is probably a decade and we have seen cases where this transition creates a window of vulnerability.

Emoya • April 19, 2024 10:04 AM

@Z.Lozinski

Crypto-Agility is achievable and not very complex, even in practice.

It is as simple as storing the necessary information to define the cryptographic algorithm alongside the data (similar to a salt with a hashed password) so that the system will know the method of encryption/decryption. Note that any key information is obviously not included in this data.

The trick is that when the algorithm needs to be changed, the secured data is decrypted using the one defined and then re-encrypted using the replacement while concurrently updating the info that describes the algorithm.

The problem isn’t crypto-agility as a concept, but rather finding durable PQ algorithms and implementing them properly, then making it a business priority to dedicate the necessary resources to do so.

A.Gorilla • April 19, 2024 11:06 AM

@ Emoya,

Crypto-Agility is achievable and not very complex, even in practice.

It is as simple as storing the necessary information to define the cryptographic algorithm alongside the data

Well, no, not really. You’re talking about re-encrypting data that’s already present, which is a pretty easy case to handle—under the assumption that one’s adversary doesn’t already have one’s encrypted data.

But, realistically, a lot of crypto is used in network communication, and we have to handle that. Which means we have to worry about oracle attacks, timing attacks, downgrade attacks, and so on. Real cryptosystems, designed and implemented by smart people, have been negatively and sometimes seriously affected by all of these.

Emoya • April 19, 2024 11:24 AM

@A.Gorilla

I agree, communication crypto is much more complex for all of the reasons you’ve listed. Most modern protocols have been designed to handle improvement through iteration, which may be crypto-agile depending upon the specifics, but this also opens the door for potential downgrade attacks. I was just outlining a simple example to demonstrate that crypto-agility is not the largest of the challenges.

Clive Robinson • April 19, 2024 1:00 PM

@ Z.Lozinski,

Nice to hear from you I hope your are doing well? Oh and where have they moved your desk to? The last time I went past the London office, it was not very welcoming except to those in hard hats, high vis, and steel toe cap boots (a look that nolonger suits me 😉

Anyway onwards and upwards,

“We need to plan on how to be ‘cryptographically agile” how do we replace cryptographic suite?”

Well you might remember for quite some years now going back well before the failed Hash3 contest I’ve been arguing that NIST should get off of it’s well padded back side, and come up with a standard for a framework to do just this…

And as nobody was prepared to do so I started into looking how to do so for the most vulnerable of “embedded” systems,

1, Medical implanted electronics.
2, Infrastructure / unitlity metering systems.

Well the simple answer to your question kind of boils down to,

“Not in our life times”

If you want reliability and security.

@ Emoya, Z.Lozinski, ALL,

“It is as simple as storing the necessary information to define the cryptographic algorithm alongside the data (similar to a salt with a hashed password) so that the system will know the method of encryption/decryption.”

Not a “snowballs chance in Hell” that, that sort of “simple” system will work.

Have a think about how you deal with version differences… It just can not be “legally” made to work, and that’s before you consider “technically”.

@ A.Gorilla, Emoya, Z.Lozinski, ALL,

“But, realistically, a lot of crypto is used in network communication, and we have to handle that. Which means we have to worry about oracle attacks, timing attacks, downgrade attacks, and so on. Real cryptosystems, designed and implemented by smart people, have been negatively and sometimes seriously affected by all of these.
“

If only it were as simple as “network communication” or even “secure formal databases”.

It’s not think about the mess that is “plaintext Email” that could go back five decades. Then consider what that would mean if it was not just “plaintext” but had blocks of “ciphertext”.

Heck we can not get the basic email protocols to work securely even using modern cipher and modes suites.

@ ALL,

As I said above I’ve looked into it on and off over the years and whilst,

“I’m not a rocket Scientist”

Applies, I can usually work my way through real world problems that are reasonably tractable. This issue has so far proved intractable…

It’s like hanging wallpaper where you get an air bubble, you push it down one place it just comes up another you push that down and some of it goes back to where you started, the rest pops up in two or more other places.

Soon you end up looking like you either have to live with a field of mole-hills, or a mountain of mole-hills, with each push making the problem worse…

Yes there is a solution of use a pin to “breach the barrier”. Whilst this can be okay with wallpaper it’s not with security systems where privacy is important.

Is it impossible to solve? Probably not, just very difficult and very very fragile…

Z.Lozinski • April 19, 2024 3:36 PM

@Clive,

I’m fine thanks. Hope you are OK too.

Oh and where have they moved your desk to?

It’s still where it has always been: AA 101, Seat 22G. If you mean South Bank, that building had reached the point it needed a major refurbishment. But that meant removing the asbestos, which is difficult with people in the building. So Alan Sugar is doing a ground up re-construction then the exterior will be finished to satisfy the Listed building officer.

We have moved to the redeveloped Shell upstream complex on York Road opposite Waterloo Station. There is a Quantum Computer in the foyer that is designed to be visible from the pavement. It is a real system, but one that has been decommissioned.

It is a fun observation that we have decommissioned around 40 Quantum computers in the last 6 years ..

Z.Lozinski • April 19, 2024 4:22 PM

@Emoya,

Quantum key distribution (QKD) could be leveraged as a stand-in for public-key crypto in certain cases

QKD is a beautiful piece of physics. But it suffers from three problems in deploying it into a production environment.

The trust model does not match enterprise IT. With a QKD network the network endpoints and the intermediate nodes (the quantum repeaters) are trusted systems (using the NSA definition that a trusted node is one whose failure breaks the security of the entire system). But enterprise IT doesn’t work like this. The reason you have end-to-end encryption in enterprise IT is because you don’t trust the network. (This dates back to the late 1960s and the IBM 2984 ATM which introduced encryption to keep customer PINs secure when sent from the ATM to the mainframe.) So if you already have end-to-end encryption how does QKD or Quantum Communications help?
The engineering is .. difficult. You need to build single photon sources and single photon detectors. Now, these devices exist, and work well in the lab. Adding them to a national scale telecom network is .. challenging. The reason for the Chinese Micas QKD satellite is that the man-free-path of a photon in vacuo is significantly better than the MFP in a dark fibre. There are also published physical layer attacks on these sources and detectors. See Djordjevic “Physical-Layer Security and Quantum Key Distribution” 2019.
The theory does not take account ofd our experience implementing cryptographic systems. The basic idea is that a QKD system distributes One Time Pads with perfect secrecy. Only because of the impementation challenges what actually apps is various “distillation” to create extra KEYAMT from the quantum key. Now as @Clive can explain, working with One Time Pads and getting the statistics wrong is a good way to get people killed. The distillation step worries me (actually it terrifies me) because you are going back to PRNGs. “We’ll just expand the amount of randomness.”

Yes there are people working on First Office applications for QKD. And there is lots of interest from Government business development departments. We need to solve the underlying problem. Please let’s continue the research, but don’t assume you can deploy QKD at scale in the next few years. And how do you use QKD to get keys to 8 Billion mobile devices?

A final observation. So far ANSSI (France), BSI (Germany), AVIID (Netherlands), Swedish Army, NCSC (UK) and NSA (USA) have all said you may not use QKD for any high grade application.

Anonymous • April 19, 2024 4:41 PM

@Emoya, @Clive

Crypto-Agility is achievable and not very complex, even in practice.

I agree with Clive here – no.

The idea of a Cryptographic policy enforcement point is a really good thought experiment.

Let’s think about all the different places in Enterprise IT we use cryptography, and then ask can we make the cryptographic algorithm replicable.

Infrastructure: firmware signing. Today, we do not have a way tp implement firmware and software signing that is both Quantum Safe and can be implemented to be FIPS-certifiable. LMS/XMSS signing is believed to be Quantum Safe, but due to the state management issues there is no way to have FIPS compliance. You can’t make it pluggable as the algorithm has to be iburned onto the motherboard.

Infrastructure: admin access to the IPMI. Again burned into the motherboard or BMC. Dependent on a set of certificates. Can’t just update TLS you have to update the PKI/CA, build a new firmware level, then deploy.

Infrastructure: the public cloud. The good news here is that Alicoud, AWS, Azure, GCP and IBM are all deploying PQC for customers to get early experience and I expect they will all update to the final FIPS standards in the summer.

There are another 32 use cases in my notebook of places we depend on cryptography for enterprise IT. Each one has to be dealt with separately. And requires the vendor in many cases.

Then we come onto telecom. There are 500+ standards that have to be updated. the good news we started working on that 2 years ago.

IoT. As Clive says, heaven help us all. You have tens of thousands of manufacturers all aiming at the lowest cost and no on-going support.

We need cryptographic agility. But as a real, measurable thing.

Z.Lozinski • April 19, 2024 5:02 PM

@Emoya, @Clive,

Apologies – I didn’t sign my reply to you both. I’m the anonymous contributor above.

@Clive,

“Hybrid” is being overloaded. Hybrids of PQC and symmetric cryptography, hybrids of current PKC and symmetric cryptography, hybrids of PQC and current PKC, hybrids of PQC and QKD and there are others.

There is an IETF draft which is trying to get the terminology consistent: draft-ietf-pquip-pqt-hybrid-terminology-02

One of the reasons people are nervous of “hybrid” (beyond the usual vendors of finest snake-oil) is that we don’t know the security properties of all the hybrid schemes. (Like DES encryption, double-DES doesn’t give you the security you might think, which is why we ended up with Triple-DES). The way I think of it is like the period during the Battle of the Atlantic where the German Navy was using two cipher systems in parallel. A break into the weaker system gives you depth to attack the stronger system.

FYI. There will be a paper on the analysis of hybrid schemes at the ETSI PQC Conference in Singapore in May.

And I think you are right, we’d better prepare for Classic McElice now, so we have a fallback

A.Gorilla • April 19, 2024 9:41 PM

One of the reasons people are nervous of “hybrid” (beyond the usual vendors of finest snake-oil) is that we don’t know the security properties of all the hybrid schemes. (Like DES encryption, double-DES doesn’t give you the security you might think, which is why we ended up with Triple-DES).

There’s good reason to be careful, but I think cryptographers basically know what needs to be done: ensure no private key material is shared between the systems (and, as always, watch for side-channels). I mean, it’d be absurd if I could just randomly make up a lattice-system key and encrypt some RSA data I don’t have the key for, and get the plaintext.

As for the point on FIPS, I’m not too familiar with the details of those standards. Would it really be forbidden to verify the signature in a FIPS-approved (quantum-vulnerable) way, and then verify an independent quantum-resistant signature?

Who? • April 23, 2024 10:09 AM

A bug has been found on the paper that will make challenging at best using the algorithm the way it was proposed. Good for our privacy and for the cryptography of the world on a post-quantum era (see updated paper).

On the other hand, I completely agree with Mr. Schneier on the three points he notes. Perhaps we should not work so hard on lattice problems and look for alternative approaches to quantum-resistant cryptography instead, just in case lattice problems finally break on an unfixable way.

Who? • April 23, 2024 10:12 AM

A tip on alternative approaches to post-quantum cryptography: it seems quantum computers are bad a brute-force attacks, we should work on preshared keys, as WireGuard does to protect against these future attack vectors.

Schneier on Security

New Lattice Cryptanalytic Technique

Comments

Leave a comment Cancel reply