Re: [openpgp] Review of crypto-refresh 07

[Andrey Jivsov <[e-mail]>]

I wouldn't prohibit key generation. Instead, I would fix the method, with
the understanding that we are unlikely to see these curves used in
practice.

I should have mentioned that such handling of "overflow" is currently one
of two FIPS-approved methods to generate a key, and that's the one that
OpenSSL uses. I think most SW uses it, and I believe gnupg is in this
category too.

See FIPS 186-4 sec. B.4.2 Key Pair Generation by Testing Candidates. It is
natural to overlay on top of it a condition for when we overflow into the
next byte with a private scalar, and reject this candidate.

If software passes an input random buffer that already satisfies the
property of not having the top bit set, by providing ceil(log2(p)) bits of
input entropy, then there is no code to add in this case. So, this is
simple and efficient change at the byte level, that generalizes to all
curves.



On Thu, Nov 17, 2022 at 4:57 AM Falko Strenzke <[e-mail]>
wrote:

> Hi Andrey,
>
> I tend to recommend not to specify the tweaks you propose or any other
> tweak to handle curves with this property, even though this would not be
> per se a security problem. The problems that I see are:
>
> - enhanced complexity for implementations
> - need for test vectors for this special case
> - possibly increased difficulty for OpenPGP-based products to pass
> security validations
>
> Further, I want to argue that the curves that are affected by this error
> are mostly irrelevant to OpenPGP:
>
> - The curves that I listed are the only ones with this property that I am
> aware of. Koblitz curves are generally hardly ever used, and the random
> 160-bit curves can only be used for lightweight authentication.
> - Probably new curves with this property could be created, if they follow
> the "prime = sparse linear combination of powers of two" paradigm, as the
> SECP curves do. But it seems no one has done this for a long time, and I
> would not expect anyone will do this in the future.
>
> On this background it suffices in my opinion to require implementations to
> gracefully reject these curves. However, that pertains only to key
> generation, since, as far as I can see, the stored private key is the only
> scalar that is affected. So it could be specified that
>
> 1. an implementation MUST NOT create keys for curves where the base point
> order is represented in one more octet than p.
> 2. an implementation SHOULD perform all other operations with such curves.
>
> The second point means that if an implementation ignores the first point
> using one of the methods you propose or it receives a private from
> elsewhere, it will still be interoperable with other implementations that
> only need to perform the public operation with that curve.
>
> Regarding the second point it could still be discussed if performing
> private operations should also be forbidden.
>
> Does that make sense?
>
> - Falko
> Am 17.11.22 um 01:55 schrieb Andrey Jivsov:
>
> ## 9.2. ECC Curves for OpenPGP
>>
>> > The "Field Size (fsize)" column represents the field size of the group
>> in number of octets, rounded up, such that [...] or scalars [...] for the
>> curve can be represented in that many octets.
>>
>> The assumption that a scalar, i.e. a group element, always fits into an
>> array long enough to hold a field element, is not correct: according to
>> Hasse's theorem for Weierstraß GF( p ) curves, we find for the base point
>> order N
>>
>>   N ≤ p + 2 √p + 1
>>
>> Thus, depending on the curve, scalars such as the private key can be one
>> bit longer than the field size, and thus also need one more octet.
>> secp160k1, secp160r1, secp160r2, and secp224k1 are examples of a domain
>> parameter sets where the representation of N needs one more octet than p.
>> I do not think that there is a need (or desire) to correct the OpenPGP
>> specification in this point. I would not expect that the need arises to
>> support any new elliptic curves, and the ones listed above most likely are
>> not desired to be supported at all.
>> But I think a note should be given in the quoted section (or another
>> appropriate place) regarding this restriction, as an OpenPGP implementation
>> may behave undefined when attempting to use it with any of the curves
>> listed above (in an extension implementation of any kind). Implementations
>> should be prepared to reject curves with this property for security reasons.
>>
>
> The probability to hit this condition is at most 2^-80 for these new
> curves.
>
> When this condition is known to occur, the key's security strength is only
> 40 bits. In general, we don't need to special-case odd key values, as they
> are expected to be within the key space.
>
> However, in this case there will need to be special processing due to the
> overflow into the next 64-bit word (or a byte at least). This may result in
> a side channel information, either due to time needed to process this new
> condition, new code path, or even the key size on disk.
>
> For these reasons I think the best fix for this is to treat the overflow
> of private value over log2(p) bits as an error. If detected, the key should
> be regenerated.
>
> This error is an unfortunate side effect  of supporting new ECC curves.
> However, the error handling can be hidden inside the key generation routine
> with e.g. a maximum loop count over key generation fixed at 2.
> Specifically, if we detect this condition, generate again, and if this
> fails, return a key generation error to the higher level.
>
>
> --
>
> *MTG AG*
> Dr. Falko Strenzke
> Executive System Architect
>
> Phone: [phone]
> E-Mail: [e-mail]
> Web: mtg.de <https://www.mtg.de>
>
>
> *MTG Exhibitions 2022 – Let´s meet again!*
> ------------------------------
> <https://www.itsa365.de/de-de/companies/m/mtg-ag>
>
> MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
> Commercial register: HRB 8901
> Register Court: Amtsgericht Darmstadt
> Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
> Chairman of the Supervisory Board: Dr. Thomas Milde
>
> This email may contain confidential and/or privileged information. If you
> are not the correct recipient or have received this email in error,
> please inform the sender immediately and delete this email. Unauthorised
> copying or distribution of this email is not permitted.
>
> Data protection information: Privacy policy
> <https://www.mtg.de/en/privacy-policy>
>