1
$\begingroup$

Given access to a 2048 bit public key, a large corpus of 2048 bit plain text messages and their signatures (RSA-PSS with SHA256 as the hash and MGF) are any of the following statements correct:

  1. Increasing the number of of messages available significantly increases the likelihood an attacker can reverse the private key
  2. Decreasing the plain text message size significantly increases the likelihood an attacker can reverse the private key

Note: by significantly I mean "before the heat death of the universe" becomes a few hundred years. If instead it becomes half the heat death of the universe, I'm less interested.

$\endgroup$
7
  • $\begingroup$ related crypto.stackexchange.com/a/51186/18298 $\endgroup$
    – kelalaka
    Mar 27, 2019 at 23:04
  • $\begingroup$ Note that the hash over the message is integral part of PSS, so increasing or decreasing the message size does nothing (special) to the input of the PSS padding algorithm (MGF1) and of course neither to the subsequent OS2IP algorithm or final RSA exponentiation. So part 2 is only of interest if you skip the data hashing part all together. You could probably argue that the resulting scheme would not be PSS. $\endgroup$
    – Maarten Bodewes
    Mar 28, 2019 at 0:16
  • $\begingroup$ Personally, if you're talking about reversing PSS, I would expect you mean that you can retrieve the messages or hash during verification. That's something entirely different from retrieving the private key and breaking the cipher. Maybe it is a good idea to adjust the title accordingly. And welcome to crypto.SE, of course :) $\endgroup$
    – Maarten Bodewes
    Mar 28, 2019 at 0:23
  • $\begingroup$ I updated the title $\endgroup$
    – Joshka
    Mar 28, 2019 at 17:31
  • $\begingroup$ @MaartenBodewes Verification requires knowledge of the message and/or its hash. The security definition of signatures usually addresses unforgability, maybe the question should point in that direction. But the answer is fairly simple: No, with data and computational power in realistic dimensions, this should not work unless you can break the computational assumptions of RSA or the hash function. $\endgroup$
    – tylo
    Mar 28, 2019 at 17:33

1 Answer 1

2
$\begingroup$

We don't know any forgery algorithm which can do a better job if there are more signed messages available, or smaller signed messages available.

The best way we know to forge messages is to factor $n$. The best algorithm we know to factor $n = pq$ when $2^{1023} < p < q < 2^{1024}$ are (near) uniform random primes, the general number field sieve, costs more than $e^{(\log n)^{1/3} (\log \log n)^{2/3}}$, and uses only the modulus $n$, without reference to any signed messages.

The standard PSS security theorem is that if you had an algorithm to forge signatures, then someone could use your signature forger as a subroutine in a program to invert $x \mapsto x^e \bmod n$ with essentially the same probability of success as the forger, and as many additional modular exponentiations as the forger makes hash or signing queries. Consequently, PSS forgery can't be much cheaper than computing $e^{\mathit{th}}$ roots, but we don't know any way to actually do it besides factoring $n$ in order to compute $e^{\mathit{th}}$ roots in the first place.

$\endgroup$
4
  • $\begingroup$ I've added a note underneath the question about small messages, something still missing from your answer. Feel free to integrate it if you agree with it. $\endgroup$
    – Maarten Bodewes
    Mar 28, 2019 at 0:21
  • $\begingroup$ By "algorithm that can do a better job" do you mean algorithm that factor RSA-PSS better or algorithms that to protect messages better? $\endgroup$
    – Joshka
    Mar 28, 2019 at 17:40
  • $\begingroup$ Yup, it is - thanks! $\endgroup$
    – Joshka
    Mar 28, 2019 at 18:48
  • $\begingroup$ It answers both questions, so in my opinion it is indeed better. $\endgroup$
    – Maarten Bodewes
    Mar 28, 2019 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.