Re: RSA Signing Security?

JG <johngarner@xxxxxxxxxxxxx> wrote:

I'm working on a document management system for a client and need to
sign a large number of documents for storage. According to the latest
pkcs#1 spec (1v2-1):
"Although no attacks are known against RSASSA-PKCS1-v1_5,in the
interest of increased robustness, RSASSA-PSS is recommended for
eventual adoption in new applications."

The best result I know of against PKCS#1 1.5 padding is by Brier,
Clavier, Coron and Naccache, `Cryptanalysis of RSA Signatures with
Fixed-Pattern Padding', at Crypto 2001,

http://citeseer.ist.psu.edu/brier01cryptanalysis.html

As far as I'm concerned, that result left PKCS#1 1.5-style fixed
signature padding in the not-with-a-bargepole category.

The PSS scheme mentioned in the above quote is much better: its security
is provably related to that of the underlying RSA problem.

This indicates there are no attacks against RSA for digital signing. Is
this true?, and if not, what are the caveats to this statement?

No, it's not true. Understanding these results is difficult if you
don't understand exactly what's going on.

RSA itself is a `trap-door one-way permutation'. It's not a
signature scheme, or a public-key encryption scheme or anything else
like that. Breaking RSA, in the sense of being able to invert it
with non-negligible probability, is not proven to be as difficult as
factoring the modulus, but is certainly no harder.

RSA can be used as the basis of a signature scheme in various ways.
Applying the RSA trap-door directly to a message doesn't work: this
permits existential forgery under key-only attack and selective forgery
under chosen-message attacks.

To make the scheme practical, you need a hash function. It's been shown
that if the hash function's range is close to the domain of the RSA
permutation and the hash is `random-like' (in a hard-to-make-properly-
rigorous way) then that's all you need, though the provable-security
results aren't all we'd like them to be[1]. It's possible to get better
probable results by making signing a randomized algorithm; this is what
the PSS scheme does.

The PKCS#1 1.5 padding scheme takes a `narrow' hash of the message to be
signed and pads it to the left with a constant string. This is the kind
of scheme attacked by Brier et al. above.

So, speaking of `attacks against RSA for digital signing' doesn't make
sense, because RSA isn't a signature scheme. There are ways of using
RSA for signing messages which are just plain bad (direct application),
ways which are provably good (FDH and PSS), and ways which have worrying
but not utterly devastating attacks against them (PKCS#1 1.5).

If SHA1withRSA and a 2048 modulus are used, and all the RSA parameters
are generated 'correctly' (proper primes, d & e exponents etc), and the
application uses one of the signature schemes mentioned above, are
there any risks? (assume there are no issues with SHA1).

Like I said, PKCS#1 1.5 padding is in my not-with-a-bargepole category.
I'd really use PSS instead.

Finally, are there any real, or theoretical risks related to the number
of documents the application signs & stores i.e. if an adversary could
access the repository, is there any greater risk of the signing keys
being broken if I sign 100 million documents, rather than 10?

Hard to say. PKCS#1 1.5 doesn't have any `positive' security results to
guide one in this area. PSS doesn't have a problem with signing large
numbers of documents. Its security doesn't degrade much with respect to
how many messages you sign.

[1] This scheme is called RSA-FDH. While the existing reductions aren't
what we'd like, and producing better ones doesn't actually look
possible, there are reasons to believe that this is more the fault
of the way we go about proving security of things.

-- [mdw]
.

Relevant Pages

  • Re: RSA Signing Security?
    ... is provably related to that of the underlying RSA problem. ... signature scheme, or a public-key encryption scheme or anything else ... the PSS scheme does. ... RSA for signing messages which are just plain bad, ...
    (sci.crypt)
  • Rabin vs. RSA/ElGamal
    ... You know RSA and ElGamal and their shortcomings, ... Now there is Rabin's pubkey encryption scheme, ... The ciphertext is the square of the plaintext. ...
    (sci.crypt)
  • Re: Asymmetric key pairs storage format
    ... corporations will pay millions of dollars to use their scheme to ... for commercial exploitation] technology your into their products. ... How can the CEO guarantee life for RSA Laboratories after September ... Perhaps the business people ...
    (sci.crypt)
  • RE: Signing before Encryption and Signing after Encryption
    ... David stated "Signing requires a private key". ... schemes that only require symmetric keys. ... In fact there are scheme to sign a message using only Hashing ... Signing before Encryption and Signing after Encryption ...
    (Security-Basics)
  • Re: ISO 9796-2 2002
    ... This probably implies the RSA or Rabin scheme rather than DSA. ... It implies a padding scheme MUST be used for a safe system. ... There used to be ISO/IEC 9796-1, ...
    (sci.crypt)