Evidence for the Security of PKCS #1 Digital Signatures

This is interesting research: “On the Security of the PKCS#1 v1.5 Signature Scheme“:

Abstract: The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the most recent version of PKCS#1 (RFC 8017) even recommends a replacement the more complex and less efficient scheme RSA-PSS, as it is provably secure and therefore considered more robust. The main obstacle is that RSA PKCS#1 v1.5 signatures use a deterministic padding scheme, which makes standard proof techniques not applicable.

We introduce a new technique that enables the first security proof for RSA-PKCS#1 v1.5 signatures. We prove full existential unforgeability against adaptive chosen-message attacks (EUF-CMA) under the standard RSA assumption. Furthermore, we give a tight proof under the Phi-Hiding assumption. These proofs are in the random oracle model and the parameters deviate slightly from the standard use, because we require a larger output length of the hash function. However, we also show how RSA-PKCS#1 v1.5 signatures can be instantiated in practice such that our security proofs apply.

In order to draw a more complete picture of the precise security of RSA PKCS#1 v1.5 signatures, we also give security proofs in the standard model, but with respect to weaker attacker models (key-only attacks) and based on known complexity assumptions. The main conclusion of our work is that from a provable security perspective RSA PKCS#1 v1.5 can be safely used, if the output length of the hash function is chosen appropriately.

I don’t think the protocol is “provably secure,” meaning that it cannot have any vulnerabilities. What this paper demonstrates is that there are no vulnerabilities under the model of the proof. And, more importantly, that PKCS #1 v1.5 is as secure as any of its successors like RSA-PSS and RSA Full-Domain.

Tags: academic papers, algorithms, cryptanalysis, cryptography, RSA, signatures

Posted on September 25, 2018 at 6:50 AM • 6 Comments

Comments

Me • September 25, 2018 8:38 AM

In other words, I’m right until proven wrong.

Mostly joking. I know it is more than that.

Clive Robinson • September 25, 2018 12:00 PM

@ Bruce,

I don’t think the protocol is “provably secure,” meaning that it cannot have any vulnerabilities.

As Matthew Green observed the other day about proofs involving “Random Oracle Models” the problem is there are no Random Oracles…

As was shown with AES, you can have something that is deemed sufficiently secure in theory but not in practice in implementations (loop unrolling and cache attacks amongst many others the NSA would have been very well aware of but for some reason encoraged NIST to organise the competition such that timing attacks would be easy on frealy available fast code).

But there is another issue you hardly ever hear mentioned…

We here of over complexity and the large attack surface being “probably” insecure, but what about the opposite?

That is it is fairly easy to show that you need a certain minimum of complexity for things to be secure.

That is basic computer instructions are in no way secure, you need to use sufficient of them in certain ways for security to start to become possible.

This applies all the way up the computer language stack and all the way up the computer hardware stack.

It’s why my prefrence for finding attacks is “low in the stack” and “bubble it up”, because nearly all security is assumed to be built on secure foundations, when in fact they are nothing of the sort. This assumption of secure foundations also has the downside that it encorages people to think and build security at the highest levels they can, which is realy a fatal mistake in security…

Rabbit Clock • September 25, 2018 5:56 PM

@Clive Robinson
Are you aware of any “worth to read” pratical attacks on exploiting temporal emanations on AES. Or better yet on current knowledge base foundations that may yield some clues on how AES is being exploited in the wild. I guess high temporal resolution is a prime factor for such attacks feasibility, something that can easily be gleaned by the likes of NSA controlling the pipes. I bet such capability is mixed with a deep study on OS scheduling and memory management algorithms combined with deep hardware/circuitry knowledge.

echo • September 25, 2018 7:19 PM

I have nothing useful to add to this topic nobody doesn’t already know. Anything beyond nodding along is above my head.

It’s funny how people keep attacking the NSA. It certainly takes the heat off GCHQ who are even bigger rascals. People keep mentioming the NSA finessing encryption standards and completely miss how GCHQ finessed law in the Netherlands to widen the intelligence net and increase the margin of appreciation in EU law.

(required) • September 27, 2018 9:49 PM

https://www.techdirt.com/articles/20131120/12242125305/nsa-worked-out-deal-with-gchq-to-spy-uk-citizens-secretly-expanded-it.shtml

https://www.techdirt.com/articles/20130621/11274723556/latest-snowden-leak-uk-spies-tap-fiber-optic-cables-to-collect-worlds-communications.shtml

They’re not much at all in competition. Mutual backscratching of loopholes.

Clive Robinson • September 28, 2018 3:44 AM

@ (required),

The “agreement” was well known in certain circles long prior to 2013 and can be found in books and journals.

Put simply the arangment was originally cooked up by or for the politicians, who were only to happy to go along with it from then onwards, till being caught out in 2013. Thus, they switched to tactic number two, get someone who was “not in the know” to express shock and outrage etc etc. If that fails kick it into the very long grass by anouncing you are lookibg into setting up a parliamentary or similar enquirey, by which time it will either get forgoton or the other party will be in power and will thus get any pain being handed out…

This occurs because of an “inconveniant truth”, to put it simply in a “Parliamentary System” members of the Parliment are “not allowed to knowingly lie”.

So the way out is simple if the US spys on UK citizens and then hands the information across to UK intel entities the UK Prime Minister can stand up in Parliament and thunderously say “We do not spy on our citizens” or similar. It’s just one of many “lies of ommission” used as misdirection.

As a rough rule of thumb the more strenuous or thunderous a reply from a Minister to a Parliamentary Question the more likely it is to be a well practiced “lie of ommission” or other deceit…

As my son is fond of saying in a fake “Sarf Lunden” accent “That d’way it be bro”.

Schneier on Security

Evidence for the Security of PKCS #1 Digital Signatures

Comments

Leave a comment Cancel reply