Re: TMP_DECL_ALIGN (was: Re: [PATCH v2 1/2] Implement PSS encoding functions)

[Nikos Mavrogiannopoulos]

On Sun, 2018-02-18 at 22:30 +0100, Niels Möller wrote:
> ni...@lysator.liu.se (Niels Möller) writes:
> 
> > For now, I think I'll fix this, and add a TMP_ALIGN_DECL,
> > TMP_ALIGN_ALLOC.
> 
> Below patch seems to work. Other options?
> 
> Regards,
> /Niels
> 
> diff --git a/nettle-internal.h b/nettle-internal.h
> index 38c8d2a8..b109e944 100644
> --- a/nettle-internal.h
> +++ b/nettle-internal.h
> @@ -35,20 +35,41 @@
>  #ifndef NETTLE_INTERNAL_H_INCLUDED
>  #define NETTLE_INTERNAL_H_INCLUDED
>  
> +#include 
> +
>  #include "nettle-meta.h"
>  
> +/* For definition of NETTLE_MAX_HASH_CONTEXT_SIZE. */
> +#include "sha3.h"
> +
>  /* Temporary allocation, for systems that don't support alloca. Note
>   * that the allocation requests should always be reasonably small,
> so
>   * that they can fit on the stack. For non-alloca systems, we use a
> - * fix maximum size, and abort if we ever need anything larger. */
> + * fix maximum size + an assert.
> + *
> + * TMP_DECL and TMP_ALLOC allocate an array of the given type, and
> + * take the array size (not byte size) as argument.
> + *
> + * TMP_DECL_ALIGN and TMP_ALLOC_ALIGN are intended for context
> + * structs, with void * pointer, size in bytes, and alignment
> + * requirements. On systems without alloca, implemented as an array
> of
> + * uint64_t, to ensure alignment. Since it is used as void *
> argument,
> + * no type casts are needed.
> + */

#define ALIGN16(x) \
((void *)(((ptrdiff_t)(x)+(ptrdiff_t)0x0f)&~((ptrdiff_t)0x0f)))
 
>  #if HAVE_ALLOCA
>  # define TMP_DECL(name, type, max) type *name
>  # define TMP_ALLOC(name, size) (name = alloca(sizeof (*name) *
> (size)))
> +# define TMP_DECL_ALIGN(name, max) void *name
> +# define TMP_ALLOC_ALIGN(name, size) (name = alloca(size))

What about this macros (untested, just idea demo):

#if defined(HAVE_ALLOCA)
# define TMP_DECL_ALLOC(name, type, max, size) type *name =
alloca(sizeof (*name) * (size)))
#else if __STDC_VERSION__ >= 199901L
# define TMP_DECL_ALLOC(name, type, max, size) \
  type _tmp##name[size+16]; \
  type *name = ALIGN16(_tmp##name)
#else /* fallback for pre-C99 and pre-alloca() times
# define TMP_DECL_ALLOC(name, type, max, size) \
  type _tmp##name[max+16]; \
  type *name = ALIGN16(_tmp##name); \
  assert(size <= max)
#endif

A more simplified version would be by eliminating the need to calculate
max, and this removing support for compilers which don't have alloca()
or C99 support (not sure if there are any of these).

regards,
Nikos

___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs

Re: [PATCH v2 1/2] Implement PSS encoding functions

[Nikos Mavrogiannopoulos]

On Sat, 2018-02-17 at 23:55 +0100, Niels Möller wrote:
> ni...@lysator.liu.se (Niels Möller) writes:
> 
> > Daiki Ueno  writes:
> > 
> > > I have incorporated the suggested changes here:
> > > https://gitlab.com/dueno/nettle/commits/wip/dueno/rsa-padding
> > 
> > Thanks!
> > 
> > I've added these changes on a branch merge-pss in the main repo,
> > together with some smaller post-merge cleanups. 
> 
> Some late comments. 
> 
> In testsuite/Makefile.in, pss-mgf1-test.c is listed in
> TS_NETTLE_SOURCES. Should be moved to TS_HOGWEED_SOURCES, to not get
> link failured in builds without hogweed. Right? 
> 
> Alternatively, we could move pss-mgf1.c from libhogweed to libnettle,
> but that doesn't seem very useful to me.
> 
> Both pss_mgf1 and pss_encode_mgf1 allocate the hash context using
> 
>   TMP_DECL(state, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
>   ...
>   TMP_ALLOC(state, hash->context_size);
> 
> That should work fine if we are using alloca, which provides suitable
> alignment, but if !HAVE_ALLOCA, we're only guaranteed uint8_t
> alignment.

What if TMP_ALLOC() allocates 16 bytes more and makes sure it returns a
16-byte aligned buffer? That is, return something passed from:

#define ALIGN16(x) \
((void *)(((ptrdiff_t)(x)+(ptrdiff_t)0x0f)&~((ptrdiff_t)0x0f)))

(the 16-byte alignment is because that's the worse case alignment
needed, e.g., for AESNI keys etc).

> Alternatively, can we drop support for compilers lacking alloca, or
> substitute malloc rather than fixed size stack allocation? In the
> latter
> case, we'd need to augment TMP_* facilities with TMP_FREE to
> deallocate
> properly in that case (like we already do for TMP_GMP_ALLOC).

What about switching to C99 buffers like:
uint8_t buffer[buffer_size]; and fallback to alloca otherwise?

That would still require additional allocation for alignment handling,
but it would be standard C. The current macros would also be simplified
by such a move.

regards,
Nikos

___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs

TMP_DECL_ALIGN (was: Re: [PATCH v2 1/2] Implement PSS encoding functions)

[Niels Möller]

ni...@lysator.liu.se (Niels Möller) writes:

> For now, I think I'll fix this, and add a TMP_ALIGN_DECL,
> TMP_ALIGN_ALLOC.

Below patch seems to work. Other options?

Regards,
/Niels

diff --git a/nettle-internal.h b/nettle-internal.h
index 38c8d2a8..b109e944 100644
--- a/nettle-internal.h
+++ b/nettle-internal.h
@@ -35,20 +35,41 @@
 #ifndef NETTLE_INTERNAL_H_INCLUDED
 #define NETTLE_INTERNAL_H_INCLUDED
 
+#include 
+
 #include "nettle-meta.h"
 
+/* For definition of NETTLE_MAX_HASH_CONTEXT_SIZE. */
+#include "sha3.h"
+
 /* Temporary allocation, for systems that don't support alloca. Note
  * that the allocation requests should always be reasonably small, so
  * that they can fit on the stack. For non-alloca systems, we use a
- * fix maximum size, and abort if we ever need anything larger. */
+ * fix maximum size + an assert.
+ *
+ * TMP_DECL and TMP_ALLOC allocate an array of the given type, and
+ * take the array size (not byte size) as argument.
+ *
+ * TMP_DECL_ALIGN and TMP_ALLOC_ALIGN are intended for context
+ * structs, with void * pointer, size in bytes, and alignment
+ * requirements. On systems without alloca, implemented as an array of
+ * uint64_t, to ensure alignment. Since it is used as void * argument,
+ * no type casts are needed.
+ */
 
 #if HAVE_ALLOCA
 # define TMP_DECL(name, type, max) type *name
 # define TMP_ALLOC(name, size) (name = alloca(sizeof (*name) * (size)))
+# define TMP_DECL_ALIGN(name, max) void *name
+# define TMP_ALLOC_ALIGN(name, size) (name = alloca(size))
 #else /* !HAVE_ALLOCA */
 # define TMP_DECL(name, type, max) type name[max]
 # define TMP_ALLOC(name, size) \
-  do { if ((size) > (sizeof(name) / sizeof(name[0]))) abort(); } while (0)
+  do { assert((size_t)(size) <= (sizeof(name) / sizeof(name[0]))); } while (0)
+# define TMP_DECL_ALIGN(name, max) \
+  uint64_t name[((max) + (sizeof(uint64_t) - 1))/ sizeof(uint64_t)]
+# define TMP_ALLOC_ALIGN(name, size) \
+  do { assert((size_t)(size) <= (sizeof(name))); } while (0)
 #endif 
 
 /* Arbitrary limits which apply to systems that don't have alloca */
diff --git a/pss-mgf1.c b/pss-mgf1.c
index 67df5570..3f5e204b 100644
--- a/pss-mgf1.c
+++ b/pss-mgf1.c
@@ -48,12 +48,12 @@ pss_mgf1(const void *seed, const struct nettle_hash *hash,
 size_t length, uint8_t *mask)
 {
   TMP_DECL(h, uint8_t, NETTLE_MAX_HASH_DIGEST_SIZE);
-  TMP_DECL(state, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
+  TMP_DECL_ALIGN(state, NETTLE_MAX_HASH_CONTEXT_SIZE);
   size_t i;
   uint8_t c[4];
 
   TMP_ALLOC(h, hash->digest_size);
-  TMP_ALLOC(state, hash->context_size);
+  TMP_ALLOC_ALIGN(state, hash->context_size);
 
   for (i = 0;;
i++, mask += hash->digest_size, length -= hash->digest_size)
diff --git a/pss.c b/pss.c
index 88125c06..d28e7b13 100644
--- a/pss.c
+++ b/pss.c
@@ -67,12 +67,12 @@ pss_encode_mgf1(mpz_t m, size_t bits,
const uint8_t *digest)
 {
   TMP_GMP_DECL(em, uint8_t);
-  TMP_DECL(state, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
+  TMP_DECL_ALIGN(state, NETTLE_MAX_HASH_CONTEXT_SIZE);
   size_t key_size = (bits + 7) / 8;
   size_t j;
 
   TMP_GMP_ALLOC(em, key_size);
-  TMP_ALLOC(state, hash->context_size);
+  TMP_ALLOC_ALIGN(state, hash->context_size);
 
   if (key_size < hash->digest_size + salt_length + 2)
 {
@@ -127,7 +127,7 @@ pss_verify_mgf1(const mpz_t m, size_t bits,
 {
   TMP_GMP_DECL(em, uint8_t);
   TMP_DECL(h2, uint8_t, NETTLE_MAX_HASH_DIGEST_SIZE);
-  TMP_DECL(state, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
+  TMP_DECL_ALIGN(state, NETTLE_MAX_HASH_CONTEXT_SIZE);
   uint8_t *h, *db, *salt;
   size_t key_size = (bits + 7) / 8;
   size_t j;
@@ -138,7 +138,7 @@ pss_verify_mgf1(const mpz_t m, size_t bits,
   TMP_GMP_ALLOC(em, key_size * 2);
 
   TMP_ALLOC(h2, hash->digest_size);
-  TMP_ALLOC(state, hash->context_size);
+  TMP_ALLOC_ALIGN(state, hash->context_size);
 
   if (key_size < hash->digest_size + salt_length + 2)
 goto cleanup;


-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs

Re: [PATCH v2 1/2] Implement PSS encoding functions

[Niels Möller]

ni...@lysator.liu.se (Niels Möller) writes:

> In testsuite/Makefile.in, pss-mgf1-test.c is listed in
> TS_NETTLE_SOURCES. Should be moved to TS_HOGWEED_SOURCES, to not get
> link failured in builds without hogweed. Right? 

Moved now.

> Both pss_mgf1 and pss_encode_mgf1 allocate the hash context using
>
>   TMP_DECL(state, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
>   ...
>   TMP_ALLOC(state, hash->context_size);
>
> That should work fine if we are using alloca, which provides suitable
> alignment, but if !HAVE_ALLOCA, we're only guaranteed uint8_t
> alignment.

It seems this currently doesn't work at all without alloca. If I delete
"#define HAVE_ALLOCA 1 " from config.h, compilation fails with

In file included from /home/nisse/hack/nettle/pss.c:48:0:
/home/nisse/hack/nettle/pss.c: In function ‘nettle_pss_encode_mgf1’:
/home/nisse/hack/nettle/nettle-internal.h:57:46: error: invalid application of 
‘sizeof’ to incomplete type ‘struct sha3_224_ctx’
 #define NETTLE_MAX_HASH_CONTEXT_SIZE (sizeof(struct sha3_224_ctx))
  ^
/home/nisse/hack/nettle/nettle-internal.h:49:46: note: in definition of macro 
‘TMP_DECL’
 # define TMP_DECL(name, type, max) type name[max]
  ^~~
/home/nisse/hack/nettle/pss.c:70:28: note: in expansion of macro 
‘NETTLE_MAX_HASH_CONTEXT_SIZE’
   TMP_DECL(state, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
^~~~

For now, I think I'll fix this, and add a TMP_ALIGN_DECL,
TMP_ALIGN_ALLOC. I still wonder if support for compilers without alloca
is relevant?

Regards, 
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs

Re: [PATCH v2 1/2] Implement PSS encoding functions

[Niels Möller]

ni...@lysator.liu.se (Niels Möller) writes:

> Daiki Ueno  writes:
>
>> I have incorporated the suggested changes here:
>> https://gitlab.com/dueno/nettle/commits/wip/dueno/rsa-padding
>
> Thanks!
>
> I've added these changes on a branch merge-pss in the main repo,
> together with some smaller post-merge cleanups. 

Some late comments. 

In testsuite/Makefile.in, pss-mgf1-test.c is listed in
TS_NETTLE_SOURCES. Should be moved to TS_HOGWEED_SOURCES, to not get
link failured in builds without hogweed. Right? 

Alternatively, we could move pss-mgf1.c from libhogweed to libnettle,
but that doesn't seem very useful to me.

Both pss_mgf1 and pss_encode_mgf1 allocate the hash context using

  TMP_DECL(state, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
  ...
  TMP_ALLOC(state, hash->context_size);

That should work fine if we are using alloca, which provides suitable
alignment, but if !HAVE_ALLOCA, we're only guaranteed uint8_t
alignment.

Nikos recent SIV patch does something similar. I'm thinking that maybe
we need some variant of TMP_DECL/TMP_ALLOC which takes a size in bytes
and guarantees alignment of at least uint64_t or so.

Alternatively, can we drop support for compilers lacking alloca, or
substitute malloc rather than fixed size stack allocation? In the latter
case, we'd need to augment TMP_* facilities with TMP_FREE to deallocate
properly in that case (like we already do for TMP_GMP_ALLOC).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs

Re: [PATCH v2 1/2] Implement PSS encoding functions

[Niels Möller]

Daiki Ueno  writes:

>> I'd suggest
>>
>>   VALGRIND_MAKE_MEM_DEFINED(m, sizeof(*m));
>>   VALGRIND_MAKE_MEM_DEFINED(m->_mp_d, sizeof(mp_limb_t) * mpz_size(m));
>>
>> The first is a bit tricky since the mpz_t is a typedef:ed array, I hope
>> I got it right.
>
> Fixed, thanks for pointing that out.

I've tried to actually enable use of this function, by replacing
pss_encode_mgf1 by pss_encode_mgf1_for_test below in the pss-test.c
file. Turns out it's not truly side-channel silent with respect to the
salt and digest inputs. The problem is that the initial bytes of the
padded value, em, depend on both digest and salt.

When converting em to an mpz_t, gmp wants internal normalization, so it
has to check if the high bits of the number are zero or not, resulting
in a branch depending on the input values.

The valgrind failure looks like this:

==23591== Memcheck, a memory error detector
==23591== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==23591== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==23591== Command: ./pss-test
==23591== 
==23591== Conditional jump or move depends on uninitialised value(s)
==23591==at 0x52C1D01: __gmpz_import (in 
/usr/lib/x86_64-linux-gnu/libgmp.so.10.2.0)
==23591==by 0x4E414C9: nettle_mpz_set_str_256_u (bignum.c:146)
==23591==by 0x4E42973: nettle_pss_encode_mgf1 (pss.c:124)
==23591==by 0x10B16B: pss_encode_mgf1_for_test.constprop.0 (pss-test.c:28)
==23591==by 0x10B32B: test_main (pss-test.c:51)
==23591==by 0x10AF6E: main (testutils.c:134)

It's curious that pkcs#1 v1.5 signatures don't have this particular
issue, since v1.5 padding always puts the most significant 1 bit at the
same position.

So I guess we'll unfortunately have to take out the valgrind magic from
this test. It's still desirable to test if RSA private key operations
are side-channel silent with respect to the private key.

If/when nettle's RSA code is reorganized to use the mpn interface for
signatures rather than the mpz interface, normalization would be less of
an issue, since most mpn functions tolerate leading zeros.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs

Re: [PATCH v2 1/2] Implement PSS encoding functions

[Niels Möller]

Daiki Ueno  writes:

> I have incorporated the suggested changes here:
> https://gitlab.com/dueno/nettle/commits/wip/dueno/rsa-padding

Thanks!

I've added these changes on a branch merge-pss in the main repo,
together with some smaller post-merge cleanups. 

I'm considering renaming some of the pss files and functions to use a
"pkcs1" prefix, and perhaps move declarations to pkcs1.h, do you think
that's appropriate?

> "These variants
> take advantage of a randomly choosen salt value, which could enhance the
> security by causing output to be different for equivalent inputs.
>
> However, assuming the same security level as inverting the @acronym{RSA}
> algorithm, a longer salt value does not always mean a better security
> @uref{http://www.iacr.org/archive/eurocrypt2002/23320268/coron.pdf}.
> The typical choices of the length are between 0 and the digest size of
> the underlying hash function."

That's better, but still not crystal clear. In what scenarios does the
salt provide additional security? If the attacker gets to see signatures
but not the corresponding messages?

Let me think aloud...

In that scenario, for a small message space, the attacker could try all
possible messages to find the message for which the signature is valid,
which is an information leakage. But if we also have a large salt space,
there can be multiple messages for which the signature is valid. Which
is good in this particular attack scenario, but otherwise sounds a bit
dangerous...

Or is the salt only intended to hide message repetition, still in the
atack scanario where the attacker observes the signatures but not the
signed messages?

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs

Re: [PATCH v2 1/2] Implement PSS encoding functions

[Daiki Ueno]

Hello,

ni...@lysator.liu.se (Niels Möller) writes:

> I hope you're ok if we do this piecewise. Here are comments on some on
> the pieces.

Sure, I really appreciate that :-)

I have incorporated the suggested changes here:
https://gitlab.com/dueno/nettle/commits/wip/dueno/rsa-padding

If you prefer, I can post those to the list.

> Maybe rename it pkcs1-mgf1.h, then? I feel "mgf1.h" is a bit too obscure
> for a short name.

Renamed.

>> +#define NETTLE_MAX_HASH_CONTEXT_SIZE 512
>
> It's not so nice with a literal constant, since sizes are somewhat
> platform dependent. I'm considering the patch at the end of this message
> instead. It uses sizeof(sha3_224_ctx), which turns out to be the largest
> one by a quite large margin (and 352 bytes, on x86_64). The drawback is
> that code using this constant needs to include sha3.h to get the size,
> but I think that's ok for implementation files.

Yes, that seems like a good idea.

> I'd suggest
>
>   VALGRIND_MAKE_MEM_DEFINED(m, sizeof(*m));
>   VALGRIND_MAKE_MEM_DEFINED(m->_mp_d, sizeof(mp_limb_t) * mpz_size(m));
>
> The first is a bit tricky since the mpz_t is a typedef:ed array, I hope
> I got it right.

Fixed, thanks for pointing that out.

>> +While the above functions for the RSA signature operations use the
>> +@cite{PKCS#1} padding scheme, Nettle also provides the variants based on
>> +the PSS padding scheme, specified in @cite{RFC 3447}.
>> +
>> +Creating an RSA signature with the PSS padding scheme is done with one
>> +of the following functions:
>
> It would be nice if the documentation gave some explanation of the
> purpose of the salt input, and some guidance on how to select the salt
> length and contents.

I have added the following:

"These variants
take advantage of a randomly choosen salt value, which could enhance the
security by causing output to be different for equivalent inputs.

However, assuming the same security level as inverting the @acronym{RSA}
algorithm, a longer salt value does not always mean a better security
@uref{http://www.iacr.org/archive/eurocrypt2002/23320268/coron.pdf}.
The typical choices of the length are between 0 and the digest size of
the underlying hash function."

Hanno Böck  writes:

> I'd recommend adding test cases for key sizes like 2049 bits, 2047 bits
> that are not divisible by 8. Such keys aren't common, but they do
> sometimes appear in the wild in TLS certificates. So this could easily
> lead to bugs that rarely show up and are hard to debug.

Thank you for the suggestion.  The current test includes a case for a
777-bit key, though it is self-generated.  Would this be sufficient, or
is there any test vector for such keys?

By the way, I have added (partial) verification support for gnutls:
https://gitlab.com/dueno/gnutls/commits/wip/dueno/rsa-padding

For testing RSA-PSS certificate verification, one can do:
$ certtool --verify --load-ca-certificate ca.crt --infile ca.crt

Regards,
-- 
Daiki Ueno
___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs

Re: [PATCH v2 1/2] Implement PSS encoding functions

[Niels Möller]

Daiki Ueno  writes:

> ni...@lysator.liu.se (Niels Möller) writes:
>
> Thank you for the detailed comments.  Please find attached the updated
> patches.

I hope you're ok if we do this piecewise. Here are comments on some on
the pieces.

>>> + mgf1.h \
>>
>> mgf1.h is intended as a public, rather than internal, header? Maybe
>> rename to pss-mgf1.h, unless you foresee some non-pss use for it.
>
> RSA-OAEP could also use it, though I am not sure if it is worth being
> supported.

Maybe rename it pkcs1-mgf1.h, then? I feel "mgf1.h" is a bit too obscure
for a short name.

> diff --git a/nettle-internal.h b/nettle-internal.h
> index 4e3098b..47b35c2 100644
> --- a/nettle-internal.h
> +++ b/nettle-internal.h
> @@ -54,6 +54,7 @@
>  /* Arbitrary limits which apply to systems that don't have alloca */
>  #define NETTLE_MAX_HASH_BLOCK_SIZE 128
>  #define NETTLE_MAX_HASH_DIGEST_SIZE 64
> +#define NETTLE_MAX_HASH_CONTEXT_SIZE 512
>  #define NETTLE_MAX_SEXP_ASSOC 17
>  #define NETTLE_MAX_CIPHER_BLOCK_SIZE 32

It's not so nice with a literal constant, since sizes are somewhat
platform dependent. I'm considering the patch at the end of this message
instead. It uses sizeof(sha3_224_ctx), which turns out to be the largest
one by a quite large margin (and 352 bytes, on x86_64). The drawback is
that code using this constant needs to include sha3.h to get the size,
but I think that's ok for implementation files.

> --- /dev/null
> +++ b/testsuite/pss-test.c
> @@ -0,0 +1,101 @@
> +#include "testutils.h"
> +
> +#include "pss.h"
> +
> +#if HAVE_VALGRIND_MEMCHECK_H
> +# include 
> +
> +static void
> +test_unmark_mpz(mpz_t m)
> +{
> +  VALGRIND_MAKE_MEM_DEFINED (>_mp_alloc, sizeof(m->_mp_alloc));
> +  VALGRIND_MAKE_MEM_DEFINED (>_mp_size, sizeof(m->_mp_size));
> +  VALGRIND_MAKE_MEM_DEFINED (>_mp_d, sizeof(mp_limb_t) * m->_mp_alloc);
^ This looks wrong. 
> +}

I'd suggest

  VALGRIND_MAKE_MEM_DEFINED(m, sizeof(*m));
  VALGRIND_MAKE_MEM_DEFINED(m->_mp_d, sizeof(mp_limb_t) * mpz_size(m));

The first is a bit tricky since the mpz_t is a typedef:ed array, I hope
I got it right.

> --- a/nettle.texinfo
> +++ b/nettle.texinfo
> @@ -3770,6 +3770,36 @@ of the digest together with an object identifier for 
> the used hash
>  algorithm.
>  @end deftypefun
>  
> +While the above functions for the RSA signature operations use the
> +@cite{PKCS#1} padding scheme, Nettle also provides the variants based on
> +the PSS padding scheme, specified in @cite{RFC 3447}.
> +
> +Creating an RSA signature with the PSS padding scheme is done with one
> +of the following functions:

It would be nice if the documentation gave some explanation of the
purpose of the salt input, and some guidance on how to select the salt
length and contents.

Regards,
/Niels

diff --git a/nettle-internal.h b/nettle-internal.h
index 4e3098b..9c4c699 100644
--- a/nettle-internal.h
+++ b/nettle-internal.h
@@ -54,6 +54,7 @@
 /* Arbitrary limits which apply to systems that don't have alloca */
 #define NETTLE_MAX_HASH_BLOCK_SIZE 128
 #define NETTLE_MAX_HASH_DIGEST_SIZE 64
+#define NETTLE_MAX_HASH_CONTEXT_SIZE (sizeof(struct sha3_224_ctx))
 #define NETTLE_MAX_SEXP_ASSOC 17
 #define NETTLE_MAX_CIPHER_BLOCK_SIZE 32
 
diff --git a/testsuite/meta-hash-test.c b/testsuite/meta-hash-test.c
index 0dcd1b9..f7fa536 100644
--- a/testsuite/meta-hash-test.c
+++ b/testsuite/meta-hash-test.c
@@ -1,6 +1,8 @@
 #include "testutils.h"
 #include "nettle-internal.h"
 #include "nettle-meta.h"
+/* For NETTLE_MAX_HASH_CONTEXT_SIZE */
+#include "sha3.h"
 
 const char* hashes[] = {
   "md2",
@@ -34,7 +36,8 @@ test_main(void)
   while (NULL != nettle_hashes[j])
 j++;
   ASSERT(j == count); /* we are not missing testing any hashes */
-  for (j = 0; NULL != nettle_hashes[j]; j++)
+  for (j = 0; NULL != nettle_hashes[j]; j++) {
 ASSERT(nettle_hashes[j]->digest_size <= NETTLE_MAX_HASH_DIGEST_SIZE);
+ASSERT(nettle_hashes[j]->context_size <= NETTLE_MAX_HASH_CONTEXT_SIZE);
+  }
 }
-  
diff --git a/tools/nettle-hash.c b/tools/nettle-hash.c
index fc991ee..488dff3 100644
--- a/tools/nettle-hash.c
+++ b/tools/nettle-hash.c
@@ -53,11 +53,11 @@ list_algorithms (void)
 {
   unsigned i;
   const struct nettle_hash *alg;
-  printf ("%10s digestsize (internal block size), in units of octets\n", 
"name");
+  printf ("%10s digestsize (internal block size, context size), in units of 
octets\n", "name");
 
   for (i = 0; (alg = nettle_hashes[i]); i++)
-printf ("%10s %d (%d)\n",
-   alg->name, alg->digest_size, alg->block_size);
+printf ("%10s %d (%d, %d)\n",
+   alg->name, alg->digest_size, alg->block_size, alg->context_size);
 };
 
 static const struct nettle_hash *

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
___
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se

Re: [PATCH v2 1/2] Implement PSS encoding functions

[Daiki Ueno]

ni...@lysator.liu.se (Niels Möller) writes:

Thank you for the detailed comments.  Please find attached the updated
patches.

>> +  mgf1.h \
>
> mgf1.h is intended as a public, rather than internal, header? Maybe
> rename to pss-mgf1.h, unless you foresee some non-pss use for it.

RSA-OAEP could also use it, though I am not sure if it is worth being
supported.

>> index 000..11e908c
>> --- /dev/null
>> +++ b/mgf1-sha256.c
>> +int
>> +mgf1_sha256(const struct sha256_ctx *hash, size_t mask_length, uint8_t 
>> *mask)
>
> Rename first argument "seed", for consistency with the mgf1 function.
> "hash" is generally used for struct nettle_hash, using it for a context
> struct is a bit confusing. (And similarly for the other functions
> mgf1_sha* functions).

I removed mgf1_sha* functions and made the mgf1 function more generic,
based on the suggestion below for pss_sha*_encode.  The interface now
looks like:

  void
  mgf1(const void *seed, const struct nettle_hash *hash,
   size_t length, uint8_t *mask);

>> --- /dev/null
>> +++ b/mgf1.c
>> @@ -0,0 +1,72 @@
>> +/* mgf1.c
>
>> +#define MGF1_MIN(a,b) ((a) < (b) ? (a) : (b))
>
> Could consider moving the definition to macros.h or nettle-internal.h
> (I'm a bit surprised a macro like this isn't defined already, from a
> quick search, there's only GMP_MIN in mini-gmp.c, which isn't visible
> here).

After rewriting the loop, the macro is no longer necessary.  I just
removed it.

>> +
>> +int
>> +mgf1(void *seed, void *state, const struct nettle_hash *hash,
>
> I think seed should be declared as const void *.

Sure, fixed.

>> +  c[0] = (i >> 24) & 0xFF;
>> +  c[1] = (i >> 16) & 0xFF;
>> +  c[2] = (i >> 8) & 0xFF;
>> +  c[3] = i & 0xFF;
>
> Use the WRITE_UINT32 macro.

Done.

>> +  memcpy(state, seed, hash->context_size);
>> +  hash->update(state, 4, c);
>> +  hash->digest(state, hash->digest_size, h);
>> +  memcpy(p, h, MGF1_MIN(hash->digest_size, mask_length - (p - mask)));
>
> No need for the second memcpy, just pass the desired length to hash->digest.

Done.

> Also, I'd consider rewriting the loop to decrement mask_length as you go
> (and rename it to just length). Then you may also be able to eliminate
> the blocks variable. You might also want to handle the final iteration
> specially (there are a couple of ways to do that, not sure what's
> cleanest), then you get rid of the MIN conditional. You might be able to
> get some ideas from the pbkdf2 function.
>
> And unless you really need the original value of mask around, I think it
> makes the code simpler to update it throughout the loop too, and
> eliminate the extra loop variable p.

Thank you, those changes made the code much simpler.

>> --- /dev/null
>> +++ b/pss-sha256.c
>> @@ -0,0 +1,64 @@
>> +/* pss.c
>
> I admit filenames in this place are of questionable utility. But this
> one is not correct.

I removed pss-sha*.c, in favor of consolidating them into
the generic pss_{encode,verify}_mgf1 functions.

>> +int
>> +pss_sha256_encode(mpz_t m, size_t bits,
>> +  size_t salt_length, const uint8_t *salt,
>> +  const uint8_t *digest)
>> +{
>> +  struct sha256_ctx state;
>> +  return pss_encode(m, bits,
>> +, _sha256,
>> +(nettle_mgf_func *) mgf1_sha256,
>
> Since you pass _sha256 as an argument here, do you really need
> the specialized function mgf1_sha256 at all? Couldn't pss_encode use
> the generic mgf1 directly? If this loss of generality seems like a
> problem, pss_encode could be renamed to pss_encode_mgf1.

Done.

>> --- /dev/null
>> +++ b/pss.c
>> +int
>> +pss_encode(mpz_t m, size_t bits,
>> +   void *state, const struct nettle_hash *hash,
>
> Is state needed by the callers? If not, allocate it locally here (using
> TMP_ALLOC and hash->context_size. If we need a NETTLE_MAX_HASH_CONTEXT_SIZE,
> we could add that in some way, preferably as a separate patch with some
> sanity check which could go in testsuite/meta-hash-test).

I am attaching a separate patch for this.

> It would be nice with some comments summarizing how pss_encode and
> pss_verify relate. 

Done.

>> +  /* Check if H' = H.  */
>> +  if (memcmp(h2, h, hash->digest_size) != 0)
>> +{
>> +  TMP_GMP_FREE(em);
>> +  return 0;
>> +}
>
> You could add a fail: label and use goto, to avoid repeating this block
> lots of times. Also there are lots of different ways this function can
> fail. What are the consequences if one of the falure cases is handled
> incorrectly, do we need tests for them all?
>
>> --- /dev/null
>> +++ b/testsuite/pss-test.c
>> @@ -0,0 +1,35 @@
>> +#include "testutils.h"
>> +
>> +#include "pss.h"
>> +
>> +void
>> +test_main(void)
>> +{
>> +  struct tstring *salt;
>> +  struct tstring *digest;
>> +  mpz_t m;
>> +  mpz_t expected;
>> +  int ret;
>> +
>> +  mpz_init(m);
>> +  mpz_init(expected);
>> +
>> +  salt = SHEX("11223344556677889900");
>> +  /* From sha256-test.c */
>> +  digest = SHEX("ba7816bf8f01cfea 

Re: [PATCH v2 1/2] Implement PSS encoding functions

[Niels Möller]

Daiki Ueno  writes:

> From: Daiki Ueno 

Comments and questions on patch 1/2:

> index 135542f..035074c 100644
> --- a/Makefile.in
> +++ b/Makefile.in
> @@ -110,6 +110,7 @@ nettle_SOURCES = aes-decrypt-internal.c aes-decrypt.c \
>md2.c md2-meta.c md4.c md4-meta.c \
>md5.c md5-compress.c md5-compat.c md5-meta.c \
>memeql-sec.c memxor.c memxor3.c \
> +  mgf1.c mgf1-sha256.c mgf1-sha384.c mgf1-sha512.c \
>nettle-meta-aeads.c nettle-meta-armors.c \
>nettle-meta-ciphers.c nettle-meta-hashes.c \
>pbkdf2.c pbkdf2-hmac-sha1.c pbkdf2-hmac-sha256.c \
> @@ -144,6 +145,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \
> pkcs1.c pkcs1-encrypt.c pkcs1-decrypt.c \
> pkcs1-rsa-digest.c pkcs1-rsa-md5.c pkcs1-rsa-sha1.c \
> pkcs1-rsa-sha256.c pkcs1-rsa-sha512.c \
> +   pss.c pss-sha256.c pss-sha512.c \
> rsa.c rsa-sign.c rsa-sign-tr.c rsa-verify.c \
> rsa-pkcs1-sign.c rsa-pkcs1-sign-tr.c rsa-pkcs1-verify.c \
> rsa-md5-sign.c rsa-md5-sign-tr.c rsa-md5-verify.c \
> @@ -194,9 +196,10 @@ HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h \
> md2.h md4.h \
> md5.h md5-compat.h \
> memops.h memxor.h \
> +   mgf1.h \

mgf1.h is intended as a public, rather than internal, header? Maybe
rename to pss-mgf1.h, unless you foresee some non-pss use for it.

> index 000..11e908c
> --- /dev/null
> +++ b/mgf1-sha256.c
> +int
> +mgf1_sha256(const struct sha256_ctx *hash, size_t mask_length, uint8_t *mask)

Rename first argument "seed", for consistency with the mgf1 function.
"hash" is generally used for struct nettle_hash, using it for a context
struct is a bit confusing. (And similarly for the other functions
mgf1_sha* functions).

> --- /dev/null
> +++ b/mgf1.c
> @@ -0,0 +1,72 @@
> +/* mgf1.c

> +#define MGF1_MIN(a,b) ((a) < (b) ? (a) : (b))

Could consider moving the definition to macros.h or nettle-internal.h
(I'm a bit surprised a macro like this isn't defined already, from a
quick search, there's only GMP_MIN in mini-gmp.c, which isn't visible
here).

> +
> +int
> +mgf1(void *seed, void *state, const struct nettle_hash *hash,

I think seed should be declared as const void *.

> + size_t mask_length, uint8_t *mask)
> +{
> +  TMP_DECL(h, uint8_t, NETTLE_MAX_HASH_DIGEST_SIZE);
> +  size_t i, blocks;
> +  uint8_t c[4], *p;
> +
> +  TMP_ALLOC(h, hash->digest_size);
> +
> +  blocks = (mask_length + hash->digest_size - 1) / hash->digest_size;
> +  for (i = 0, p = mask; i < blocks; i++, p += hash->digest_size)
> +{
> +  c[0] = (i >> 24) & 0xFF;
> +  c[1] = (i >> 16) & 0xFF;
> +  c[2] = (i >> 8) & 0xFF;
> +  c[3] = i & 0xFF;

Use the WRITE_UINT32 macro.

> +  memcpy(state, seed, hash->context_size);
> +  hash->update(state, 4, c);
> +  hash->digest(state, hash->digest_size, h);
> +  memcpy(p, h, MGF1_MIN(hash->digest_size, mask_length - (p - mask)));

No need for the second memcpy, just pass the desired length to hash->digest.

Also, I'd consider rewriting the loop to decrement mask_length as you go
(and rename it to just length). Then you may also be able to eliminate
the blocks variable. You might also want to handle the final iteration
specially (there are a couple of ways to do that, not sure what's
cleanest), then you get rid of the MIN conditional. You might be able to
get some ideas from the pbkdf2 function.

And unless you really need the original value of mask around, I think it
makes the code simpler to update it throughout the loop too, and
eliminate the extra loop variable p.

> --- /dev/null
> +++ b/pss-sha256.c
> @@ -0,0 +1,64 @@
> +/* pss.c

I admit filenames in this place are of questionable utility. But this
one is not correct.

> +int
> +pss_sha256_encode(mpz_t m, size_t bits,
> +   size_t salt_length, const uint8_t *salt,
> +   const uint8_t *digest)
> +{
> +  struct sha256_ctx state;
> +  return pss_encode(m, bits,
> + , _sha256,
> + (nettle_mgf_func *) mgf1_sha256,

Since you pass _sha256 as an argument here, do you really need
the specialized function mgf1_sha256 at all? Couldn't pss_encode use
the generic mgf1 directly? If this loss of generality seems like a
problem, pss_encode could be renamed to pss_encode_mgf1.

> --- /dev/null
> +++ b/pss.c
> +int
> +pss_encode(mpz_t m, size_t bits,
> +void *state, const struct nettle_hash *hash,

Is state needed by the callers? If not, allocate it locally here (using
TMP_ALLOC and hash->context_size. If we need a NETTLE_MAX_HASH_CONTEXT_SIZE,
we could add that in some way, preferably as a separate patch with some
sanity check which could go in testsuite/meta-hash-test).

> +nettle_mgf_func mgf,
> +size_t salt_length, const uint8_t *salt,
> +const uint8_t *digest)
> +{
> +