[v6,12/13] crypto: asymmetric_keys - Adjust signature size calculation for NIST P521

Commit Message

Stefan Berger March 12, 2024, 6:36 p.m. UTC

From: Stefan Berger <[e-mail]>

Adjust the calculation of the maximum signature size for support of
NIST P521. While existing curves may prepend a 0 byte to their coordinates
(to make the number positive), NIST P521 will not do this since only the
first bit in the most significant byte is used.

If the encoding of the x & y coordinates requires at least 128 bytes then
an additional byte is needed for the encoding of the length. Take this into
account when calculating the maximum signature size.

Signed-off-by: Stefan Berger <[e-mail]>
Reviewed-by: Lukas Wunner <[e-mail]>
Tested-by: Lukas Wunner <[e-mail]>
---
 crypto/asymmetric_keys/public_key.c | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

Comments

Bharat Bhushan March 18, 2024, 5:58 a.m. UTC | #1

> -----Original Message-----
> From: Stefan Berger <[e-mail]>
> Sent: Wednesday, March 13, 2024 12:06 AM
> To: [e-mail]; [e-mail];
> [e-mail]; [e-mail]
> Cc: [e-mail]; [e-mail];
> [e-mail]; Bharat Bhushan <[e-mail]>;
> [e-mail]; Stefan Berger <[e-mail]>
> Subject: [EXTERNAL] [PATCH v6 12/13] crypto: asymmetric_keys - Adjust
> signature size calculation for NIST P521
> ----------------------------------------------------------------------
> From: Stefan Berger <[e-mail]>
> 
> Adjust the calculation of the maximum signature size for support of NIST
> P521. While existing curves may prepend a 0 byte to their coordinates (to
> make the number positive), NIST P521 will not do this since only the first bit in
> the most significant byte is used.
> 
> If the encoding of the x & y coordinates requires at least 128 bytes then an
> additional byte is needed for the encoding of the length. Take this into account
> when calculating the maximum signature size.
> 
> Signed-off-by: Stefan Berger <[e-mail]>
> Reviewed-by: Lukas Wunner <[e-mail]>
> Tested-by: Lukas Wunner <[e-mail]>
> ---
>  crypto/asymmetric_keys/public_key.c | 14 +++++++++++++-
>  1 file changed, 13 insertions(+), 1 deletion(-)
> 
> diff --git a/crypto/asymmetric_keys/public_key.c
> b/crypto/asymmetric_keys/public_key.c
> index e5f22691febd..16cc0be28929 100644
> --- a/crypto/asymmetric_keys/public_key.c
> +++ b/crypto/asymmetric_keys/public_key.c
> @@ -233,6 +233,7 @@ static int software_key_query(const struct
> kernel_pkey_params *params,
>  	info->key_size = len * 8;
> 
>  	if (strncmp(pkey->pkey_algo, "ecdsa", 5) == 0) {
> +		int slen = len;
>  		/*
>  		 * ECDSA key sizes are much smaller than RSA, and thus could
>  		 * operate on (hashed) inputs that are larger than key size.
> @@ -246,8 +247,19 @@ static int software_key_query(const struct
> kernel_pkey_params *params,
>  		 * Verify takes ECDSA-Sig (described in RFC 5480) as input,
>  		 * which is actually 2 'key_size'-bit integers encoded in
>  		 * ASN.1.  Account for the ASN.1 encoding overhead here.
> +		 *
> +		 * NIST P192/256/384 may prepend a '0' to a coordinate to
> +		 * indicate a positive integer. NIST P521 never needs it.
>  		 */
> -		info->max_sig_size = 2 * (len + 3) + 2;
> +		if (strcmp(pkey->pkey_algo, "ecdsa-nist-p521") != 0)
> +			slen += 1;
> +		/* Length of encoding the x & y coordinates */
> +		slen = 2 * (slen + 2);
> +		/*
> +		 * If coordinate encoding takes at least 128 bytes then an
> +		 * additional byte for length encoding is needed.
> +		 */
> +		info->max_sig_size = 1 + (slen >= 128) + 1 + slen;

Is "(slen >= 128)" valid for P192/256/384 also?

Thanks
-Bharat

>  	} else {
>  		info->max_data_size = len;
>  		info->max_sig_size = len;
> --
> 2.43.0

Lukas Wunner March 18, 2024, 7:06 a.m. UTC | #2

On Mon, Mar 18, 2024 at 05:58:23AM +0000, Bharat Bhushan wrote:
> > --- a/crypto/asymmetric_keys/public_key.c
> > +++ b/crypto/asymmetric_keys/public_key.c
> > @@ -233,6 +233,7 @@ static int software_key_query(const struct
> > kernel_pkey_params *params,
> >  	info->key_size = len * 8;
> > 
> >  	if (strncmp(pkey->pkey_algo, "ecdsa", 5) == 0) {
> > +		int slen = len;
> >  		/*
> >  		 * ECDSA key sizes are much smaller than RSA, and thus could
> >  		 * operate on (hashed) inputs that are larger than key size.
> > @@ -246,8 +247,19 @@ static int software_key_query(const struct
> > kernel_pkey_params *params,
> >  		 * Verify takes ECDSA-Sig (described in RFC 5480) as input,
> >  		 * which is actually 2 'key_size'-bit integers encoded in
> >  		 * ASN.1.  Account for the ASN.1 encoding overhead here.
> > +		 *
> > +		 * NIST P192/256/384 may prepend a '0' to a coordinate to
> > +		 * indicate a positive integer. NIST P521 never needs it.
> >  		 */
> > -		info->max_sig_size = 2 * (len + 3) + 2;
> > +		if (strcmp(pkey->pkey_algo, "ecdsa-nist-p521") != 0)
> > +			slen += 1;
> > +		/* Length of encoding the x & y coordinates */
> > +		slen = 2 * (slen + 2);
> > +		/*
> > +		 * If coordinate encoding takes at least 128 bytes then an
> > +		 * additional byte for length encoding is needed.
> > +		 */
> > +		info->max_sig_size = 1 + (slen >= 128) + 1 + slen;
> 
> Is "(slen >= 128)" valid for P192/256/384 also?

It is valid but never true for those.

The signature consists of two integers encoded in ASN.1.
So each integer is prepended by 1 byte for the tag and 1 byte for the length.

The two integers are bundled together in a "sequence", which in turn requires
1 byte for the tag and 1 byte for the length.  However, for P521 the length
of the sequence is at least 2*(1+1+66) = 136 bytes, which exceeds 128 bytes
and therefore the length of the sequence occupies 2 bytes instead of 1.

For the shorter key lengths, the sequence fits in less than 128 bytes and
does not require the extra byte for the sequence length.

So the code is fine AFAICS.

Thanks,

Lukas

Jarkko Sakkinen March 18, 2024, 9:12 p.m. UTC | #3

On Tue Mar 12, 2024 at 8:36 PM EET, Stefan Berger wrote:
> From: Stefan Berger <[e-mail]>
>
> Adjust the calculation of the maximum signature size for support of
> NIST P521. While existing curves may prepend a 0 byte to their coordinates
> (to make the number positive), NIST P521 will not do this since only the
> first bit in the most significant byte is used.
>
> If the encoding of the x & y coordinates requires at least 128 bytes then
> an additional byte is needed for the encoding of the length. Take this into
> account when calculating the maximum signature size.
>
> Signed-off-by: Stefan Berger <[e-mail]>
> Reviewed-by: Lukas Wunner <[e-mail]>
> Tested-by: Lukas Wunner <[e-mail]>
> ---
>  crypto/asymmetric_keys/public_key.c | 14 +++++++++++++-
>  1 file changed, 13 insertions(+), 1 deletion(-)
>
> diff --git a/crypto/asymmetric_keys/public_key.c b/crypto/asymmetric_keys/public_key.c
> index e5f22691febd..16cc0be28929 100644
> --- a/crypto/asymmetric_keys/public_key.c
> +++ b/crypto/asymmetric_keys/public_key.c
> @@ -233,6 +233,7 @@ static int software_key_query(const struct kernel_pkey_params *params,
>  	info->key_size = len * 8;
>  
>  	if (strncmp(pkey->pkey_algo, "ecdsa", 5) == 0) {
> +		int slen = len;
>  		/*
>  		 * ECDSA key sizes are much smaller than RSA, and thus could
>  		 * operate on (hashed) inputs that are larger than key size.
> @@ -246,8 +247,19 @@ static int software_key_query(const struct kernel_pkey_params *params,
>  		 * Verify takes ECDSA-Sig (described in RFC 5480) as input,
>  		 * which is actually 2 'key_size'-bit integers encoded in
>  		 * ASN.1.  Account for the ASN.1 encoding overhead here.
> +		 *
> +		 * NIST P192/256/384 may prepend a '0' to a coordinate to
> +		 * indicate a positive integer. NIST P521 never needs it.
>  		 */
> -		info->max_sig_size = 2 * (len + 3) + 2;
> +		if (strcmp(pkey->pkey_algo, "ecdsa-nist-p521") != 0)
> +			slen += 1;

Just wondering the logic of picking between these:

1. "strncmp"
2. "strcmp"

Now the "ecdsa" is matched with strncmp and "ecdsa-nist-p521" is
compared with strcmp.

So is there a good reason to use different function in these
cases?

I'd guess both could be using strcmp since comparing against
constant...

> +		/* Length of encoding the x & y coordinates */
> +		slen = 2 * (slen + 2);
> +		/*
> +		 * If coordinate encoding takes at least 128 bytes then an
> +		 * additional byte for length encoding is needed.
> +		 */
> +		info->max_sig_size = 1 + (slen >= 128) + 1 + slen;
>  	} else {
>  		info->max_data_size = len;
>  		info->max_sig_size = len;


BR, Jarkko

Stefan Berger March 18, 2024, 10:42 p.m. UTC | #4

On 3/18/24 17:12, Jarkko Sakkinen wrote:
> On Tue Mar 12, 2024 at 8:36 PM EET, Stefan Berger wrote:
>> From: Stefan Berger <[e-mail]>
>>
>> Adjust the calculation of the maximum signature size for support of
>> NIST P521. While existing curves may prepend a 0 byte to their coordinates
>> (to make the number positive), NIST P521 will not do this since only the
>> first bit in the most significant byte is used.
>>
>> If the encoding of the x & y coordinates requires at least 128 bytes then
>> an additional byte is needed for the encoding of the length. Take this into
>> account when calculating the maximum signature size.
>>
>> Signed-off-by: Stefan Berger <[e-mail]>
>> Reviewed-by: Lukas Wunner <[e-mail]>
>> Tested-by: Lukas Wunner <[e-mail]>
>> ---
>>   crypto/asymmetric_keys/public_key.c | 14 +++++++++++++-
>>   1 file changed, 13 insertions(+), 1 deletion(-)
>>
>> diff --git a/crypto/asymmetric_keys/public_key.c b/crypto/asymmetric_keys/public_key.c
>> index e5f22691febd..16cc0be28929 100644
>> --- a/crypto/asymmetric_keys/public_key.c
>> +++ b/crypto/asymmetric_keys/public_key.c
>> @@ -233,6 +233,7 @@ static int software_key_query(const struct kernel_pkey_params *params,
>>   	info->key_size = len * 8;
>>   
>>   	if (strncmp(pkey->pkey_algo, "ecdsa", 5) == 0) {
>> +		int slen = len;
>>   		/*
>>   		 * ECDSA key sizes are much smaller than RSA, and thus could
>>   		 * operate on (hashed) inputs that are larger than key size.
>> @@ -246,8 +247,19 @@ static int software_key_query(const struct kernel_pkey_params *params,
>>   		 * Verify takes ECDSA-Sig (described in RFC 5480) as input,
>>   		 * which is actually 2 'key_size'-bit integers encoded in
>>   		 * ASN.1.  Account for the ASN.1 encoding overhead here.
>> +		 *
>> +		 * NIST P192/256/384 may prepend a '0' to a coordinate to
>> +		 * indicate a positive integer. NIST P521 never needs it.
>>   		 */
>> -		info->max_sig_size = 2 * (len + 3) + 2;
>> +		if (strcmp(pkey->pkey_algo, "ecdsa-nist-p521") != 0)
>> +			slen += 1;
> 
> Just wondering the logic of picking between these:
> 
> 1. "strncmp"
> 2. "strcmp"
> 

strncmp: prefix-matching
strcmp: full string matching

> Now the "ecdsa" is matched with strncmp and "ecdsa-nist-p521" is
> compared with strcmp.

That's prefix matching vs. full string match.

.. and indeed 'ecdsa' is a prefix of 'ecdsa-nist-p521'.

> 
> So is there a good reason to use different function in these
> cases?

Yes, there is.

> 
> I'd guess both could be using strcmp since comparing against
> constant...

No, prefix versus full string matching requires different function calls.

> 
>> +		/* Length of encoding the x & y coordinates */
>> +		slen = 2 * (slen + 2);
>> +		/*
>> +		 * If coordinate encoding takes at least 128 bytes then an
>> +		 * additional byte for length encoding is needed.
>> +		 */
>> +		info->max_sig_size = 1 + (slen >= 128) + 1 + slen;
>>   	} else {
>>   		info->max_data_size = len;
>>   		info->max_sig_size = len;
> 
> 
> BR, Jarkko
>

Bharat Bhushan March 19, 2024, 3:38 a.m. UTC | #5

> -----Original Message-----
> From: Lukas Wunner <[e-mail]>
> Sent: Monday, March 18, 2024 12:36 PM
> To: Bharat Bhushan <[e-mail]>
> Cc: Stefan Berger <[e-mail]>; [e-mail];
> [e-mail]; [e-mail];
> [e-mail]; [e-mail];
> [e-mail]; [e-mail]; Stefan Berger
> <[e-mail]>
> Subject: Re: [EXTERNAL] [PATCH v6 12/13] crypto: asymmetric_keys - Adjust
> signature size calculation for NIST P521
> 
> On Mon, Mar 18, 2024 at 05:58:23AM +0000, Bharat Bhushan wrote:
> > > --- a/crypto/asymmetric_keys/public_key.c
> > > +++ b/crypto/asymmetric_keys/public_key.c
> > > @@ -233,6 +233,7 @@ static int software_key_query(const struct
> > > kernel_pkey_params *params,
> > >  	info->key_size = len * 8;
> > >
> > >  	if (strncmp(pkey->pkey_algo, "ecdsa", 5) == 0) {
> > > +		int slen = len;
> > >  		/*
> > >  		 * ECDSA key sizes are much smaller than RSA, and thus could
> > >  		 * operate on (hashed) inputs that are larger than key size.
> > > @@ -246,8 +247,19 @@ static int software_key_query(const struct
> > > kernel_pkey_params *params,
> > >  		 * Verify takes ECDSA-Sig (described in RFC 5480) as input,
> > >  		 * which is actually 2 'key_size'-bit integers encoded in
> > >  		 * ASN.1.  Account for the ASN.1 encoding overhead here.
> > > +		 *
> > > +		 * NIST P192/256/384 may prepend a '0' to a coordinate to
> > > +		 * indicate a positive integer. NIST P521 never needs it.
> > >  		 */
> > > -		info->max_sig_size = 2 * (len + 3) + 2;
> > > +		if (strcmp(pkey->pkey_algo, "ecdsa-nist-p521") != 0)
> > > +			slen += 1;
> > > +		/* Length of encoding the x & y coordinates */
> > > +		slen = 2 * (slen + 2);
> > > +		/*
> > > +		 * If coordinate encoding takes at least 128 bytes then an
> > > +		 * additional byte for length encoding is needed.
> > > +		 */
> > > +		info->max_sig_size = 1 + (slen >= 128) + 1 + slen;
> >
> > Is "(slen >= 128)" valid for P192/256/384 also?
> 
> It is valid but never true for those.

Okay, just want to check if that was valid for P192/256/384 and this patch is fixing same as well.

Otherwise looks good to me as well.

Thanks
-Bharat
 
> 
> The signature consists of two integers encoded in ASN.1.
> So each integer is prepended by 1 byte for the tag and 1 byte for the length.
> 
> The two integers are bundled together in a "sequence", which in turn requires
> 1 byte for the tag and 1 byte for the length.  However, for P521 the length of
> the sequence is at least 2*(1+1+66) = 136 bytes, which exceeds 128 bytes and
> therefore the length of the sequence occupies 2 bytes instead of 1.
> 
> For the shorter key lengths, the sequence fits in less than 128 bytes and does
> not require the extra byte for the sequence length.
> 
> So the code is fine AFAICS.
> 
> Thanks,
> 
> Lukas

Jarkko Sakkinen March 19, 2024, 6:21 p.m. UTC | #6

On Tue Mar 19, 2024 at 12:42 AM EET, Stefan Berger wrote:
>
>
> On 3/18/24 17:12, Jarkko Sakkinen wrote:
> > On Tue Mar 12, 2024 at 8:36 PM EET, Stefan Berger wrote:
> >> From: Stefan Berger <[e-mail]>
> >>
> >> Adjust the calculation of the maximum signature size for support of
> >> NIST P521. While existing curves may prepend a 0 byte to their coordinates
> >> (to make the number positive), NIST P521 will not do this since only the
> >> first bit in the most significant byte is used.
> >>
> >> If the encoding of the x & y coordinates requires at least 128 bytes then
> >> an additional byte is needed for the encoding of the length. Take this into
> >> account when calculating the maximum signature size.
> >>
> >> Signed-off-by: Stefan Berger <[e-mail]>
> >> Reviewed-by: Lukas Wunner <[e-mail]>
> >> Tested-by: Lukas Wunner <[e-mail]>
> >> ---
> >>   crypto/asymmetric_keys/public_key.c | 14 +++++++++++++-
> >>   1 file changed, 13 insertions(+), 1 deletion(-)
> >>
> >> diff --git a/crypto/asymmetric_keys/public_key.c b/crypto/asymmetric_keys/public_key.c
> >> index e5f22691febd..16cc0be28929 100644
> >> --- a/crypto/asymmetric_keys/public_key.c
> >> +++ b/crypto/asymmetric_keys/public_key.c
> >> @@ -233,6 +233,7 @@ static int software_key_query(const struct kernel_pkey_params *params,
> >>   	info->key_size = len * 8;
> >>   
> >>   	if (strncmp(pkey->pkey_algo, "ecdsa", 5) == 0) {
> >> +		int slen = len;
> >>   		/*
> >>   		 * ECDSA key sizes are much smaller than RSA, and thus could
> >>   		 * operate on (hashed) inputs that are larger than key size.
> >> @@ -246,8 +247,19 @@ static int software_key_query(const struct kernel_pkey_params *params,
> >>   		 * Verify takes ECDSA-Sig (described in RFC 5480) as input,
> >>   		 * which is actually 2 'key_size'-bit integers encoded in
> >>   		 * ASN.1.  Account for the ASN.1 encoding overhead here.
> >> +		 *
> >> +		 * NIST P192/256/384 may prepend a '0' to a coordinate to
> >> +		 * indicate a positive integer. NIST P521 never needs it.
> >>   		 */
> >> -		info->max_sig_size = 2 * (len + 3) + 2;
> >> +		if (strcmp(pkey->pkey_algo, "ecdsa-nist-p521") != 0)
> >> +			slen += 1;
> > 
> > Just wondering the logic of picking between these:
> > 
> > 1. "strncmp"
> > 2. "strcmp"
> > 
>
> strncmp: prefix-matching
> strcmp: full string matching

Right, in first case is necessary because strcmp() would return "-1" for
the substring.

BR, Jarkko

Patch

diff --git a/crypto/asymmetric_keys/public_key.c b/crypto/asymmetric_keys/public_key.c
index e5f22691febd..16cc0be28929 100644
--- a/crypto/asymmetric_keys/public_key.c
+++ b/crypto/asymmetric_keys/public_key.c
@@ -233,6 +233,7 @@  static int software_key_query(const struct kernel_pkey_params *params,
 	info->key_size = len * 8;
 
 	if (strncmp(pkey->pkey_algo, "ecdsa", 5) == 0) {
+		int slen = len;
 		/*
 		 * ECDSA key sizes are much smaller than RSA, and thus could
 		 * operate on (hashed) inputs that are larger than key size.
@@ -246,8 +247,19 @@  static int software_key_query(const struct kernel_pkey_params *params,
 		 * Verify takes ECDSA-Sig (described in RFC 5480) as input,
 		 * which is actually 2 'key_size'-bit integers encoded in
 		 * ASN.1.  Account for the ASN.1 encoding overhead here.
+		 *
+		 * NIST P192/256/384 may prepend a '0' to a coordinate to
+		 * indicate a positive integer. NIST P521 never needs it.
 		 */
-		info->max_sig_size = 2 * (len + 3) + 2;
+		if (strcmp(pkey->pkey_algo, "ecdsa-nist-p521") != 0)
+			slen += 1;
+		/* Length of encoding the x & y coordinates */
+		slen = 2 * (slen + 2);
+		/*
+		 * If coordinate encoding takes at least 128 bytes then an
+		 * additional byte for length encoding is needed.
+		 */
+		info->max_sig_size = 1 + (slen >= 128) + 1 + slen;
 	} else {
 		info->max_data_size = len;
 		info->max_sig_size = len;