On Dec 21, 2016, at 1:01 PM, Niels Möller nisse@lysator.liu.se wrote:

...

Assuming there aren’t Python bindings yet, I would be tempted to try and craft my own (at least for UMAC for now). However, I’d like to be able to do it using the Python ‘ctypes’ library, and one difficulty I can see with doing that is knowing the amount of memory I should allocate for some of the structures used by this code. Specifically, for UMAC, I’d need to know the size things like “struct umac32_ctx”, “struct umac64_ctx”, “struct umac96_ctx”, and “struct umac128_ctx”. These sizes are trivial to get from C code using sizeof(), but I don’t believe there’s any good way to get them from Python using ctypes unless there’s an API call that can be made to a C function in the library which returns this information.

These sizes are arhitecture dependent. And may change between nettle release (with an ABI break, new soname, etc). It's technically possible to add functions you suggest, but it seems both ugly and unusual to me. I hope you can solve the problem in another way.

[Ron] Thanks very much for getting back to me, Niels!

Rather than adding a function to return the structure size here, what do you think about adding functions such as umac32_new() which would do the allocation of the structure and return a pointer to it? This would address the issue I’m seeing with ctypes in Python and remain completely compatible with the existing API. I understand the distaste for having libraries like this allocate memory, but the only options I know of to provide cross-language support like this is to either provide an allocator function that knows how much space to allocate or to provide a function which returns the amount of space needed to pass to an external allocator.

To make sure there weren’t any other issues in doing this, I did a proof of concept where I simply did a fixed-size allocation of 4 KB for the contexts (since the largest context is currently only about 2800 bytes on the system I’m running on) and I was able to make everything after that work fine. Here’s a snippet of some Python 3 test code (without a pretty wrapper yet):

import binascii import ctypes

UMAC_CTX_SIZE = 4096

UMAC32_DIGEST_SIZE = 4

_nettle_lib = ctypes.cdll.LoadLibrary('/opt/local/lib/libnettle.dylib')

_umac32_set_key = _nettle_lib.nettle_umac32_set_key _umac32_set_nonce = _nettle_lib.nettle_umac32_set_nonce _umac32_update = _nettle_lib.nettle_umac32_update _umac32_digest = _nettle_lib.nettle_umac32_digest

ctx = ctypes.create_string_buffer(UMAC_CTX_SIZE)

key = b'abcdefghijklmnop' nonce = b'bcdefghi' digest = ctypes.create_string_buffer(UMAC32_DIGEST_SIZE)

for msg in (b'', 3*b'a', 1024*b'a', 32768*b'a', 1024*1024*b'a', 32768*1024*b'a', b'abc', 500*b'abc'): _umac32_set_key(ctx, key) _umac32_set_nonce(ctx, ctypes.c_size_t(len(nonce)), nonce) _umac32_update(ctx, ctypes.c_size_t(len(msg)), msg) _umac32_digest(ctx, ctypes.c_size_t(len(digest)), digest) print(binascii.b2a_hex(digest.raw).decode())

I really don’t want to rely on a hard-coded size like this, though, in case future versions of the context structure grow much larger for some reason. Also, even if they don’t, rounding up like this is a waste of memory. Can you think of any other options here?

...

As an example of this, libsodium provides functions like crypto_stream_chacha20_keybytes() and crypto_stream_chacha20_noncebytes() which can be called to return the size of a Chacha20 key and nonce, respectively. In the C header file, these look like:

These are different; these constants are part of the algorithm specification. The defines in the header files are for convenience, but not the ultimate definition of the values.

[Ron] Fair enough. For these, I could potentially just replicate the definitions in the Python code, without worry that they would change. It was just nice in the libsodium case that I didn’t have to.

On Dec 22, 2016, at 12:16 PM, Niels Möller nisse@lysator.liu.se wrote:

Ron Frederick ronf@timeheart.net writes:

...

Rather than adding a function to return the structure size here, what do you think about adding functions such as umac32_new() which would do the allocation of the structure and return a pointer to it?

Actually, I think I'd prefer a way to get the struct size at run time; otherwise I'd have to consider interfaces to let an application override the allocation function used by the *_new functions.

Are you sure the ctypes package you use doesn't provide any general way to extract struct sizes from a C interface? I know it's common practice to design libraries to have only opaque types, with function calls for allocation, use, and deallocation. But I wouldn't expect nettle to be the only library which tries to be more low-level and expose some internals.

[Ron] Keep in mind that the binding we’re talking about here is all happening dynamically at run time of the Python program. At that point in time, source code to the C module wouldn’t even be available on the system (not even header files) in many cases, and there’d be no C compiler or preprocessor available to parse them even if they were. The only thing available is the information in the dynamic library itself, readable by the linker.

There is a “sizeof” function in ctypes for structures, but the exact types and ordering of the members of the structure would have to be provided in the Python code, which in this case would be translating the C structure definitions (and CPP macros in this case) into the ctypes equivalent, meaning the structure is no longer opaque.

For example, if one ever wants to let the python code read or write fields of a struct used in a C interface, then, I imagine, the python glue magic needs to either extract the layout from the header file, or generate a litte C code, including the header file, to get proper sizes and offsets or accesor functions.

[Ron] There are other ways to interface to C code in Python that can auto-generate shims to do something like this, but they would involve actually generating and compiling additional C code at build time and shipping an additional C shared library with the Python code, which means multiple versions of the package are needed to cover each of the supported architectures. That’s what I’m trying to avoid here, as up until now my package is 100% pure Python and the exact same code runs on all architectures and OSes (MacOS/Windows/UNIX). The only calls out to C code are either provided by other Python modules or involve dynamic linking against third-party C libraries using ctypes operating at the ABI level.

I think that, in general, it makes little sense to use C code in a shared library without also using the corresponding header file in some way or the other.

In principle, the compiler could insert information about sizes and struct layouts (for more general use than just debug info) into the object files, so that the python glue code could extract it from the shared library itself. But as far as I'm aware, common compilers and linkers don't do that.

[Ron] Yeah - I think that sort of information may be available when libraries are compiled with debug information, but it’s not something available to the linker as far as I know and I’ve never seen anything to allow languages like Python to use that data to access structures like this.

...

ctx = ctypes.create_string_buffer(UMAC_CTX_SIZE)

Note that nettle's context structs have stricter alignment requirements than a string. Maybe you need to use a different allocation method, to guarantedd you at least as much alignment as the system's malloc?

[Ron] This is a good point. Based on some simple tests, the returned memory always seems to be at least 16-byte aligned similar to malloc(), but I can’t actually find documentation that explicitly promises this. I’ll have to do more research on this.

...

I really don’t want to rely on a hard-coded size like this,

I totally agree that's a bad workaround.

[Ron] Unfortunately, my options at the moment seem to be to either do this or keep looking for alternate implementations of UMAC I can attempt to link against if I want to continue to keep my code 100% Python, and the Nettle version of UMAC is by far the cleanest thing I’ve found so far.

On Dec 23, 2016, at 8:07 AM, Niels Möller nisse@lysator.liu.se wrote:

Ron Frederick ronf@timeheart.net writes:

...

[Ron] There are other ways to interface to C code in Python that can auto-generate shims to do something like this, but they would involve actually generating and compiling additional C code at build time and shipping an additional C shared library with the Python code, which means multiple versions of the package are needed to cover each of the supported architectures.

That's they way I would expect language bindings to work. And I don't think any other way can work if one aims to have python glue for everything in Nettle.

That said, for umac and other mac algorithms, I think it would make sense to provide structs similar to nettle_hash which includes all needed sizes and function pointers.

Would that solve your problem? You could try to see if you can make 100% python wrapper for the supported hash functions in the nettle_hashes list (I think Daniel Kahn Gillmor did something similar in his perl bindings). I guess you'd still need to access struct members, though. If useful, it's also possible to add accessor functions like

size_t nettle_hash_ctx_size(const struct nettle_hash *hash) { return hash->ctx_size; }

nettle_hash_init_func *nettle_hash_init(const struct nettle_hash *hash) { return hash->init; }

etc. (Other variants are possible, if one aims for a function-call-only api).

Thanks - a function-call based API that didn’t rely on the Python code needing to access any Nettle-specific structures sounds good, and would be preferred to something that involves declaring a struct to access function pointers and other static data.

I’ve confirmed that for UMAC the only such function I would need to build a Python wrapper is something that returns the context size. In fact, I have a first cut of such a module written and working with a “try” clause that shows how I could call such a function to request the size if it existed, with a fallback which uses a hard-coded size if that’s not present.

Regarding the init function, that shouldn’t be necessary if Nettle guarantees that a call to set_key() resets the context structure and performs all necessarily initialization. I can see where init() would be needed for the key-less hash functions, but it may not be needed here.

That actually leads to one other wrinkle I’ve run into. According to the Nettle docs:

Function: void umac32_digest (struct umac32_ctx *ctx, size_t length, uint8_t *digest) <>Function: void umac64_digest (struct umac64_ctx *ctx, size_t length, uint8_t *digest) <>Function: void umac96_digest (struct umac96_ctx *ctx, size_t length, uint8_t *digest) <>Function: void umac128_digest (struct umac128_ctx *ctx, size_t length, uint8_t *digest) Extracts the MAC of the message, writing it to digest. length is usually equal to the specified output size, but if you provide a smaller value, only the first length octets of the MAC are written. These functions reset the context for processing of a new message with the same key. The nonce is incremented as described above, the new value is used unless you call the _set_nonce function explicitly for each message.

While this wouldn’t really be a problem for my use case, the Python cryptographic hash standard API (defined in PEP 452) states the following about the digest() method:

digest()

    Return the hash value of this hashing object as a bytes
    containing 8-bit data.  The object is not altered in any way
    by this function; you can continue updating the object after
    calling this function.

So, if I wanted to provide a Python module which adhered to this API, the automatic reset of the context and increment of the nonce would be a problem. Mind you, I think this is a very useful feature in Nettle and wouldn’t want to see it go away. However, do you think it would be possible to make this configurable? There could be something like a umac32_auto_increment_nonce() function that takes a context and a true/false value as an argument to determine whether calling digest() does this or not. If it didn’t, you could continue to append to a message even after requesting a hash of the data provided so far, without the need to make a copy of the context structure first.

And then there's a known ABI problem with exporting that list, discussed in another mail to the list, which needs to be solved in one way or the other.

Yeah, I saw the earlier e-mail on that. My vote would be for option 2 in your list where a function is defined that returns a pointer to the list, and I think that would probably be a good approach for accessing any static data in the library.

That said, I like the suggestion in your other e-mail about providing both an ABI and API level interface, leaving it up to callers to decide if they’re willing to deal with the upgrade/downgrade issues of replacing the libnettle library without recompiling the calling code against the latest header file. More on that shortly in a follow-up to that other e-mail.

...

[Ron] This is a good point. Based on some simple tests, the returned memory always seems to be at least 16-byte aligned similar to malloc(), but I can’t actually find documentation that explicitly promises this. I’ll have to do more research on this.

If you don't find any better way, maybe you can use ctype to call libc malloc directly?

Yes - this definitely seems like it would work if the Python allocator didn’t already provide such a guarantee.

On Dec 23, 2016, at 11:00 PM, Niels Möller nisse@lysator.liu.se wrote:

Ron Frederick ronf@timeheart.net writes:

...

While this wouldn’t really be a problem for my use case, the Python cryptographic hash standard API (defined in PEP 452) states the following about the digest() method:

...

digest()

   Return the hash value of this hashing object as a bytes
   containing 8-bit data.  The object is not altered in any way
   by this function; you can continue updating the object after
   calling this function.

So, if I wanted to provide a Python module which adhered to this API, the automatic reset of the context and increment of the nonce would be a problem.

The way you'd do this with Nettle is to make a copy (plain memcpy or struct assignment) of the context struct, and extract the digest from the copy.

The nettle design is based on the assumption that it's an uncommon use case to hash (or mac) both a string and a prefix thereof. So it's possible, but not optimized for.

Understood, and I’ve already implemented a copy() method on the wrapper which allocates a new context structure and initializes it with the contents of the existing context. However, it seems very expensive to do that malloc & memcpy on _every_ call to digest(), since as you’ve said this is the uncommon case. Given the documented behavior of the digest() function in PEP 452 though, that’s what I would have to do, since there’s no way in the wrapper to know if the caller might want to continue feeding data after digest() is called.

It makes sense to me to have Nettle default to doing the reset & auto-increment of the nonce, as I agree that would be the common case for someone using Nettle directly.. However, if this could be made configurable when the context is created, it would make it possible to avoid the cost of the malloc & memcpy in the Python wrapper unless the caller actually wanted to “fork” a context and hash multiple independent streams of data which had a common prefix.

What I’d suggest is to split out the nonce increment into its own externally callable function, and add a flag on the context about whether to call that function automatically or not. The flag would default to true to preserve existing behavior, but a function could be provided to disable this for callers that wanted to be able to do partial hashing. They could then call the increment manually if they wanted to reuse a context for multiple messages, avoiding the malloc & memcpy even in both cases. The copy would only be needed in the case I mention above when hashing multiple streams that start with a common prefix.

Ron Frederick ronf@timeheart.net writes:

One other thought on this: Since the sender and receiver of a message need to both know the nonce, I think it would be useful for Nettle to provide a get_nonce() function if it is going to auto-increment the nonce.

One can access it directly from the nonce field of the context struct, but it makes some sense to provide a more abstract method. If we want to do this consistently, the details are not entirely obvious, though:

1. Should it return a pointer to the nonce, assuming that it is present in raw form in the context, so that it can be returned cheaply, or should it make a copy into an area provided by the caller?

2. Should a get_nonce method be added to the nettle_aead struct?

If a receiver is receiving an explicit nonce with each message, there’s no reason for them to pay the cost of doing the increment function every time they call digest() to verify a message, as they’re just going to reset the nonce to something else when the next message arrives.

It's true that the auto-increment is unnecessary in that case, but it is such a small cost that I don't think it's a good tradeoff to optimize for. (It's an invocation of the INCREMENT macro in macros.h). I think it's going to be negligible compared to all other processing done by digest(). Making it optional (via a flag in the context, or an extra function) will increase the code size for a performance gain (in some use cases) which is hardly measurable.

Ron Frederick ronf@timeheart.net writes:

Do any of the AEAD functions modify the nonce after it is set?

poly1305_aes_digest also increments the nonce. And it's in the same category as umac: A keyed hash with a per-message nonce. It seems the AEAD functions don't, so it's not entirely consistent.

Regards, /Niels

Ron Frederick ronf@timeheart.net writes:

Understood, and I’ve already implemented a copy() method on the wrapper which allocates a new context structure and initializes it with the contents of the existing context. However, it seems very expensive to do that malloc & memcpy on _every_ call to digest(), since as you’ve said this is the uncommon case. Given the documented behavior of the digest() function in PEP 452 though, that’s what I would have to do, since there’s no way in the wrapper to know if the caller might want to continue feeding data after digest() is called.

One problem is that many hash functions have an end-of-data padding which, if implemented in the simple way, clobbers the block buffer. So if the digest() wasn't allowed to modify the context, that would introduce some extra copying or complexity for the common case where digest is the final operation on the data.

And most hashes have a pretty small context, so that an extra copy in the uncommon case isn't a big deal. Now, umac differs from plain hash functions in that it has a much larger context, making copying more expensive.

The nonce auto-increment is less of a problem.

I would also like to say that for a MAC which depends on a nonce (in contrast to plain hash functions and HMAC), the python "PEP 452" API allowing multiple calls to digest seems dangerous. I'd expect that the key could be attacked if you expose both UMAC(key, nonce, "foo") and UMAC(key, nonce, "foobar"), since the nonce is supposed to be unique for each message.

Maybe one reasonable way to implement the python API could be to require an explicit set_nonce, and raise an exception if digest is called without a corresponding set_nonce? I.e., if set_nonce was never called, or if there are two digest calls without an intervening set_nonce. And then do any helper methods you want for managing the nonce value in the python code?

It makes sense to me to have Nettle default to doing the reset & auto-increment of the nonce, as I agree that would be the common case for someone using Nettle directly.. However, if this could be made configurable when the context is created, it would make it possible to avoid the cost of the malloc & memcpy in the Python wrapper unless the caller actually wanted to “fork” a context and hash multiple independent streams of data which had a common prefix.

If you'd like to experiment, you could try writing a

umac32_digest_pure (const struct umac32_ctx *ctx, ...)

which doesn't modify the context, to see what it takes. Probably can't use the "padding cache" optimization, though.

I'd prefer a separate function (naming is a bit difficult, as usual) over a flag in the context.

What would probably be better (but a larger reorg), is to separate the state which depends on the key from the state which depends on message and nonce. The only MAC-like algoritm currently done like that is GCM, which also has a large key-dependent table. That allows several contexts sharing the same key-dependent tables.

It would make sense to do something similar for HMAC too. Currently, a hmac_sha256_ctx consists of three sha256_ctx, which is three SHA256 state vectors of 32 bytes each, plus three block buffers of 64 bytes each. So a total of 300 bytes or so. But it really needs only one block buffer, so if state vectors and block buffers were better separated, it could be trimmed down to about 170 bytes.

Regards, /Niels

Ron Frederick ronf@timeheart.net writes:

I’m not a cryptographer

And I'm an amateur when it comes to cryptanalysis.

but how would this be different than supporting a copy() function for something like HMAC, where you generate a digest for both a message and its prefix?

Difference is that HMAC doesn't have a nonce. When the attacker gets the HMAC of two messages (related or not) using the same key, the attacker is supposed to only be able to tell if the messages were identical or not.

I thought the main attack against UMAC when you reused both a key and a nonce for two different messages was that the key stream for both messages was identical and it was only later mixed with data from the messages.

I'm afraid I can't give a concrete attack, but my gut feeling is that the security analysis depends on nonces being unique, it's generally a bad idea to depart from that.

I don't recall all details of UMAC; it's some years since I wrote it. But the way I understand it, it works by computing a relatively weak low-complexity function of the expanded key and message. IIRC, L1 is a plain linear convolution, and L2 is some kind of polynomial evaluation. And then to hide the low-complexity structure from the attacker, a value derived from the key and nonce is XORed to the tag at the end. Looking at the code, that final "whitening" is the only use of the nonce I see.

So basically,

umac(key, nonce, msg) = F(key, msg) ^ AES(pdf_key, nonce)

where F(key, msg) is a low-complexity function. So if you compute

t0 = umac(key, nonce, "foo") t1 = umac(key, nonce, "foobar")

then

t0 XOR t1 = F(key, "foo") ^ F(key,"foobar")

which looks a bit too well structured, and defeats the whitening step. I can't tell if it leads to practical attacks, but I wouldn't be suprised of a few of these would let the attacker derive the parts of the expanded key corresponding to the suffix, and then forge additional messages with identical tag.

Admittedly, PEP 247/452 doesn’t explicitly contemplate hash functions with nonces, but it would cover cases where multiple digests were generated using the same key and no other randomization to make the two digests independent.

As I said, multiple messages with the same key is pretty normal use of HMAC, and if one doesn't want the attacker to be able to identify identical messages from the MACs, one can prepend a sequence number to the message. Supposedly unique per-message nonces make the situation quite different.

I agree that a separate function is probably better than a flag. What do you think of the name partial_digest(), or perhaps running_digest()?

running_digest sounds quite clear to me. Or maybe snapshot_digest?

So, would you basically have two different context objects in this case, one associated with just the key and a separate one associated with the nonce and the message data provided so far? It seems like you’d still need to make a copy of the second object before calculating a digest if you wanted to support partial digests and didn’t have a “pure” digest function that could do that without modifying the state, but at least the amount of data you had to copy might be smaller.

That's the idea. For umac, the second part is quite large too, so it would make some sense with a function that can produce the digest without clobbering (or copying) it.

Regards, /Niels

On Dec 27, 2016, at 1:11 AM, Niels Möller nisse@lysator.liu.se wrote:

If you'd like to experiment, you could try writing a

umac32_digest_pure (const struct umac32_ctx *ctx, ...)

which doesn't modify the context, to see what it takes. Probably can't use the "padding cache" optimization, though.

I looked over the code today, and it turns out that it’s a fairly clean change. We can even keep the “padding cache” optimization. A key thing to realize is that it ok to modify parts of the context, as long as they don’t affect future calculations. In other words, it’s ok to write things like padding data to the input buffer which are “beyond the end”, since later calls update() will simply overwrite this padding as long as the “index” value is unchanged. Similarly, it’s ok to update the padding cache and set the flag for that, as long as the two low-order bits of the nonce_low value aren’t changed and the nonce is never incremented.

More specifically, the only parts of the context which need to be updated but which should not be modified in place are the l2_state[] array and the count value. If a local copy of these values is made on the stack and used in place of the values in the context, you get the right result. Other things like the index value and the nonce only need to be read and not updated, and the nonce increment and the final reset of the index and count can just be removed entirely.

Attached is a patch which implements new snapshot_digest() functions for all of umac32, umac64, umac96, and umac128. I tested these against a full range of input buffer sizes and incremental buffer additions to make sure I caught all the different edge cases and I feel pretty confident in the results. The resulting digest values were validated by calling the original unmodified digest function as a reference. I tested both the output of snapshot_digest() against digest() and then the result of calling update(), snapshot_digest(), update() again, and the original digest(), making sure I got the same results as I would have when calculating digest() on the combined data from both updates in a separate umac context.

Nikos Mavrogiannopoulos n.mavrogiannopoulos@gmail.com writes:

An approach for Ron to overcome the specific problem could be to use wrappers over nettle which hide the details, such as the gnutls functions (e.g., gnutls_mac_fast etc.).

If gnutls has sutable wrappers for umac, that sounds like an easy solution, at least until needed interfaces are added to nettle.

The more long term question, is should nettle be striving to provide an ABI? If not, it could transform to low-level library gnulib or ccan are (i.e. like a copy-lib)... or alternatively, if yes, provide a high level stable API which hides details and the ABI is easier to provide.

We could add a thin layer of functions involving only opaque pointers, byte strings, and ints. If we really want, it could be a separate .so-file, which could have an ABI more stable than nettle's. But I'm not sure if that's really solves Ron's problem of using the functions without depending on the header file. E.g, say we add a function like

void *mac_ctx_new(enum nettle_mac_algorithm);

and it's called like

void *umac_ctx = mac_ctx_new(NETTLE_ALGORITHM_UMAC);

And then the python glue loads libnettle.so, and wants to make this function call. How would it find the numeric value of NETTLE_ALGORITHM_UMAC? Would it duplicate the definitions in the C header (which is ok, since these constants are (i) part of the ABI and supposedly stable, and (ii) not architecture dependent), or would we need some interface using plain strings to identify algorithms?

Happy holidays, /Niels