On Sat, Oct 19, 2019 at 12:40 AM brian m. carlson <
sandals(_at_)crustytoothpaste(_dot_)net> wrote:
On 2019-10-19 at 03:40:03, Phillip Hallam-Baker wrote:
Someone just said we need a spec. Here is a spec:
https://www.ietf.org/id/draft-hallambaker-mesh-udf-07.txt
It is in the new format which is intended to be read as HTML. Until the
tools catch up, you can read it here:
http://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html
This doesn't specify any method of primality testing which means
different implementations can produce different values[0] (and is
therefore not deterministic), unless you literally interpret the text
"smallest prime integer" as requiring an actual prime. That could be
implemented by using the Miller test instead of Miller-Rabin, but that
would be much, much slower.
I am trying to work out what the necessary criteria should be. It is
certainly something to think about.
If someone is using a random primality test with 128 rounds, there is an
infinitesimal chance it isn't a prime, 2^-128.
The work factor for picking such a prime is 2^128 so it should not happen
by accident either.
Right now, my feeling is that if someone is going to use a broken primality
test, the risk of not recovering their key might be the least of their
concerns...
I think I might have a solution though...
In this particular case, the approach to invalid keys (where p and q are
unsuitable) is "try again with a different seed", which is probably okay
in terms of RSA, because the number of retries necessary will be low.
The only problem with that approach is that it prevents generating RSA keys
from shared secrets...
It also doesn't specify DSA keys, which, while uncommon, are still a
part of the spec. The "try again" approach will probably be a little
more difficult here.
I can add them. Which DSA key sizes are still relevant?
The draft does not specify the value of e which it should but I am pretty
sure we have standardized on 65537. I see no reference to p being greater
than q and it is a mystery to me why we would care when the RSA
parameters
are the modulus and the private exponent d. Knowledge of p and q is only
used to determine d, they are not req
The OpenPGP secret key contains u, the multiplicative inverse of p mod
q, which is used along with p and q for the Chinese Remainder Theorem.
RFC 4880 specifically mentions that p must be less than q, which is
required for u to exist. (This is backwards from most other specs,
which require the opposite and define u as the multiplicative inverse of
q mod p.)
OK, so I will rework that part and merely specify that it outputs two
primes X and Y which implementations are free to use for either p or q as
they please.
So long as the resulting value of d is the same...
[0] Yes, people should pick a suitable number of iterations for
primality testing, but there are people that pick 1 iteration for
PBKDF2, which is a demonstration of why we can't have nice things. We
actually have to tell people how to write things in an interoperable
and secure way.
Absolutely. And there are folk who have calculated their RSA parameters by
setting the upper n bits of their RSA modulus to be the encrypted value of
their seed value, choosing a random p and then working out what their q
should be. Then sold the result to a foreign adversary...
There are two possible situations.
1) User generates a strong key, recovery fails on a bad implementation with
insufficient testing.
2) User generates a broken key due to insufficient testing, cannot recover
it.
The first is the least worst. We can still recover the key on a good
implementation.
The second is trickier. But since we have specified the search pattern, we
can still recover the key provided that we know the fingerprint.
In either case, we can blame and shame the bad implementation!
_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp