Re: [openpgp] Deriving an OpenPGP secret key from a human readable seed

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

OK so I have not implemented DSA but it turns out that it the spec mandates
the entire process:
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

The main consequence of DSA is that it mandates the entire process
including prime generation *and* provides a mechanism for validation of all
the parameters.

This discussion now has me thinking that we should have been validating
parameters for RSA before importing them into an application all along.


On Sat, Oct 19, 2019 at 9:04 AM Michael Richardson <[e-mail]>
wrote:

>
> Phillip Hallam-Baker <[e-mail]> wrote:
>     > 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...
>
> Yes, but the issue is bugs.
>
> If someone fixes (or introduces...) a bug in a primality test, then I might
> recover a different key.  This doesn't happen if I generate and key the
> private key.
>
> If I lose my system and I install a new system, the odds of new/patched
> software compared to when I first generated is high.
>

Absolutely!

And I can provide a recovery mechanism that does just that. So the set of
requirements I see are:

A) Generation/Import of keypairs meeting BCP criteria of NIST and IETF from
fingerprint
B) Identification of faulty implementations
C) Recovery of mis-generated key pairs.
D) Verifiable generation processes with separation of duties.

It is not necessary for every implementation to do all of these. An SSH /
OpenPGP / S/MIME app only needs to implement A and allow B and only if it
actually implements keygen at all.

I can meet the full set of requirements with the Mesh management tool. This
is open source, MIT license. The code for the UDF stuff is not complicated
though. Concentrating all the key management functions in a single app
allows them to be done better and more comprehensively.

*A) Generate*

The commands for generating, exporting and importing a key from the CLI
would probably look something like the following. Since I am thinking of
the general case, the key fingerprints used as UDF content digests rather
than OpenPGP but this is largely because it was easier to cut and paste
from my docs rather than find another.

> myapp generate [e-mail] --udf
Generated key:  MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4
Ready.
> myapp export [e-mail] --udf
ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
Ready.
> myapp import [e-mail]
--udf=ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
Ready.

*B) Detecting a faulty key*

myapp import [e-mail]
--udf=ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
--check=MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-ZZZZ
Error-ABEND-0243: Recovered key did not match

We can get a better test of the generated key checking with a different
application

mesh verify ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4
WARNING: Key does not match

*C) Recovery of mis-generated key pairs*

Recovery of a misgenerated key pair is easiest if we know the modulus. In
that case we can generate the starting points for the primality search for
either P or Q and then just do trial divisions until we get a exact match.
So the first thing the mesh recovery tool would do is to attempt to obtain
the public key parameters from the fingerprint.

If we only have the fingerprint, we have to assume at least one of the
parameters is prime, generate a trial key for each prime candidate in the
search and test to see if it matches the fingerprint:
> mesh recover ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4
WARNING: Key recovered is NOT SECURE
Primality testing failed.
Recovered key written to MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4.p12

*D) Verifiable generation processes with separation of duties. *

NB: This is not the sort of process I see many individuals performing for
themselves. But it is exactly the sort of procedure I might want to use as
the basis for separation of duties in a key ceremony type situation. Every
one of the input shares affects every bit of the output. The splitting (but
not the generated key!) is information theoretic secure.

UDF gives us the ability to use Shamir secret sharing to split a secret. We
can also use this in reverse to create a secret from random contributions
generated on separate machines.

So let us imagine we begin by generating the following nonce values on
independent machines.
NAQC-GKXI-6DTJ-COKM-4HBF-CZJJ-BO6G-I
NAED-CRXH-IASE-5ZYS-ZS2D-PQT4-6O6P-G
NCRB-6YXF-R5RA-ZFGY-W6TB-4H6Q-3O6Y-E

We can combine them to form a single secret for a specific purpose. Since
we need to encode some information into the first three bytes of the result
and we have one type code, we have 32 bits fixed in the output:

ZAAQ-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L

We can now generate a set of Shamir secrets that closely resemble but are
not exactly the same as our nonce inputs:

SAEC-GKXI-6DTJ-COKM-4HBF-CZJJ-BO6G-I
SAED-CRXH-IASE-5ZYS-ZS2D-PQT4-6O6P-G
SAMB-R3XF-R5RA-ZFGY-W6TB-4H6Q-3O6Y-E

Note that only the first three characters of the first two shares and the
first six characters of the last changed here.

We can verify that the above secrets combine to create ZAAQ-AWMQ-... and we
can even generate additional shares if we so choose. We can't change the
quorum unless we reshare the secret.

So now imagine we are generating these from QR codes being read by a
camera. We run the scheme some number of times with full observability.
Then we cover one of the inputs so the observers can only see the other
three and run the system some randomly chosen number of times with a
different input covered on each round.