Re: [openpgp] Review of crypto-refresh 07

[Falko Strenzke <[e-mail]>]

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>