[CFRG] Re: I-D Action: draft-irtf-cfrg-rsa-guidance-01.txt

[Phillip Hallam-Baker <[e-mail]>]

On Fri, Sep 6, 2024 at 6:59 AM Alicja Kario <[e-mail]> wrote:

> On Friday, 6 September 2024 07:29:42 CEST, Phillip Hallam-Baker wrote:
> > On Thu, Sep 5, 2024 at 2:03 PM Alicja Kario <[e-mail]> wrote:
> > On Thursday, 5 September 2024 19:21:39 CEST, Phillip Hallam-Baker wrote:
> >> Very interesting. RSA will be with us for a long time...
> >>
> >> Have you considered key generation? Just adding a reference to
> >> FIPS 185-5 might be enough. I am currently trying to decide
> >> whether probabilistic or provable primes are the way to go. I
> >> have also noticed that keygen on my state of the art 2023
> >> machine is taking almost as long as it used to take in 1990.
> >> That is because we are using longer keys and we are doing a lot
> >> more checks - the auxiliary primes.
> >
> > RSA key generation is a very rare occurance, so it's easier to just
> > do it offline, on a trusted system, than to work to make it side
> > channel safe. So, no, I consider it out of scope.
> >
> > RSA is vulnerable to kleptography attacks.
> >
> > If we are going to do the job, we should do it right.
> > Kleptography is a real world attack.
> >
> > If you want to create a malicious HSM, you use the following:
> >
> > p1 = number(seed)
> > p = nextPrime (p1)
> > m1 = BytesToBigNum   (Encrypt (p, traitorKey)  + random)
> >
> > q1 = m1/p
> > q = nextPrime (q1)
> >
> > Moti Yung is credited with the public discovery of this but
> > there is reason to believe it has been used in the wild.
> >
> > Having thought through the process of storing ML-DSA seeds, I
> > am convinced that storing the seed rather than the expanded key
> > is the correct move for security grounds even if the keys were
> > not gienormous. Giving the expanded key is an invitation to
> > kleptographic malice.
> >
> > RSA is no different, specifying the seed and a strong key
> > derivation mechanism offers superior security.
>
> So the solution to protecting against backdoored systems, where
> the attacker has a control over the rendom number generator, is
> to use the output from the random number generator directly
> to deterministially generate the whole private key?
>

Which is slow and as Sophie Schmeig pointed out, we can speed it up by
giving hints.

So to generate according to FIPS 186-5, for the first generation you start
with a seed, you then count the number of times you need to increment your
auxiliaries p1, xp1 until they are prime. Then you do the thing to work out
the modulo, generate a candidate for p and count the number of modulos you
need to add to make that prime.

I don't think you need to do much more than mention FIPS 186-5 for key gen
in your draft and note the kleptography attacks aren't covered. They will
be a separate draft if we ever go that route. I am currently writing some
code and will submit a proposal.