Support for SHA512 and proper ED25519 usage

[de-nordic]

There are two commits in this PR:

• the first one brings the SHA512 processing in MCUboot and has been taken from https://github.com/mcu-tools/mcuboot/pull/1967, with small fix
• imgtool changes to support the SHA512 and proper ED25519 signare.

This PR is alternative to https://github.com/mcu-tools/mcuboot/pull/2029 where new TLV is introduced. While working on image changes I have decided that it is not needed to provide new TLV for signature, because:

• the SHA512 is newly support hash and there is no logic for it yet so no possible mismatch of SHA and key
• it is enough to decide by key and hash TLV whether the ED25519 is double or single hashing.

Depends on https://github.com/mcu-tools/mcuboot/pull/1967

[de-nordic]

Found a problem with signature. The problem is as follows:

• the imgtool with ed25519 uses PureEdDSA taking sha256 of image as input for signature;
• the correct way would be to use directly put image through PureEdDSA and get sha512 of the images signed this way - that is how the PR is doing now;
• the problem on MCUboot side is that it is not possible to put image directly through PureEdDSA, which requires loading entire message to memory, so sha512 is calculated as image is read and that is put in HashEdDSA.
• PureEdDSA signature and HashEdDSA signature on the same binary string, with the same sha512 over the binary used in second case are not the same.

[taltenbach]

@de-nordic I'm looking into this PR because I would like to have proper Ed25519 usage on one of the projects I'm currently working on. To me PureEdDSA should be favored if possible because of the higher collision resistance it provides compared to HashEdDSA. Wouldn't it be possible to use PureEdDSA by modifying this line: https://github.com/mcu-tools/mcuboot/blob/52e2afc2f809c424b0f337f56059d1dfcc7e6d98/ext/fiat/src/curve25519.c#L1110 to something that would gradually read and hash the firmware image from flash memory, similarly to what is currently done by bootutil_img_hash? That would make possible to use PureEdDSA since it wouldn't be necessary anymore to load the entire image to RAM.

[de-nordic]

@de-nordic I'm looking into this PR because I would like to have proper Ed25519 usage on one of the projects I'm currently working on. To me PureEdDSA should be favored if possible because of the higher collision resistance it provides compared to HashEdDSA. Wouldn't it be possible to use PureEdDSA by modifying this line:

https://github.com/mcu-tools/mcuboot/blob/52e2afc2f809c424b0f337f56059d1dfcc7e6d98/ext/fiat/src/curve25519.c#L1110

to something that would gradually read and hash the firmware image from flash memory, similarly to what is currently done by bootutil_img_hash? That would make possible to use PureEdDSA since it wouldn't be necessary anymore to load the entire image to RAM.

The PureEdDSA is supposed to be used for signature of entire message at once. Using hash of image as message in PureEdDSA dos not help to improve security. There are only two ways to do the PureEdDSA in MCUboot:

1. run PureEdDSA signature verification directly on image, if it is possible to address flash or storage as RAM (pass it as buffer and size to verification function);
2. divide image into chunks and have separate signature for each chunk (for example one signature every 4k of image).

What we have now is PureEdDSA(sha256(image)), what this PR was supposed to provide PureEdDSA on image and sha512, without introducing new TLV for signature, but it seems that, at this point, I have to do PureEdDSA on sha512, as this allows us, at the cost of lowered collision resistance and security, in respect to proper PureEdDSA, ability to easily support external images for which PureEdDSA may not always be possible; the PureEdDSA on external storage may not be possible if external storage can not be mapped to RAM, where external slot image could be verified at once, or there is not enough memory to just copy the image to RAM and validate it there.

to something that would gradually read and hash the firmware image from flash memory, similarly to what is currently done by bootutil_img_hash? That would make possible to use PureEdDSA since it wouldn't be necessary anymore to load the entire image to RAM.

This is not possible. The HashEdDSA has been provided for that purpose. The PureEdDSA is supposed to work on entire message at once.

[de-nordic]

imgtool part: LGTM I think ed25519 signature & its hash selection consequences need to be documented (which i can do myself) You must add yours signed-off-by line to the 1st commmit

I have moved back to, as discussed off-line, to doing PureEdDSA on hash of image. I will follow this PR with update that also does the proper PureEdDSA signature but that will require new TLV and change in MCUboot, in image validation - not only in algorithm but also in how image is passed for verication,

[de-nordic]

I'm currently integrating your changes in my project (I cannot wait for this PR to be merged unfortunately), I just noticed two minor things you might want to fix :)

Note that there is still missing the ED25519 over sha512 configuration for MCUboot. There is patch that adds sha512 with PSA crypto, but there is no ED25519 verify that can use it. Nordic is working on PSA support for ed25519, here https://github.com/nrfconnect/sdk-mcuboot/pull/323/files, but it may take a moment before it gets to upstream.

[taltenbach]

Note that there is still missing the ED25519 over sha512 configuration for MCUboot. There is patch that adds sha512 with PSA crypto, but there is no ED25519 verify that can use it. Nordic is working on PSA support for ed25519, here https://github.com/nrfconnect/sdk-mcuboot/pull/323/files, but it may take a moment before it gets to upstream.

Thanks for the details! The project I'm working on is using mbedTLS, not PSA, so I just had to modify a bit sha.h to be able to use SHA-512 with mbedTLS. That's a quick and straightforward change but in case it saves you some time, I can create a PR.

[d3zd3z]

the problem on MCUboot side is that it is not possible to put image directly through PureEdDSA, which requires loading entire message to memory, so sha512 is calculated as image is read and that is put in HashEdDSA.

So, right here, you've summarized the entirety of the problem I have with EdDSA. The thing is, I have no problem with the algorithm itself, and as far as I can tell it is sound. But it seems to every implementation seems to have been done by someone who has actually never even tried to use it.

There is absolutely no reason that an implementation of PureEdDSA would ever need to have the entire image in memory. But, as part of the hash, it does require hashing of the image multiple times, so can't just use a simplistic API.

Given that we are basically stuck with the implementations that exist, however, using HashEdDSA seems perfectly fine. HashEdDSA basically reduces the security of EdDSA to the same as ECDSA, and, for that matter, every other signature algorithm.

[de-nordic]

* I'd remove the "not a perfect usage". Using EdDSA to sign the hash of the image is perfectly acceptable, even described in the original documentation for the algorithm.

OK, will fix the comment.

* Change "sing" to "sign", unless perhaps we've become musical in nature.

Heh, no.

* I wouldn't really bother saying that larger hashes bring higher collision resistance. Unless we plan on doing something like signing all of the atoms in universe, individually, even SHA256 will never encounter a collision. Larger hashes are generally more about having more information to give to a large signature size.

OK, will fix. Still some of implementations, like PSA ed25519, require sha512 otherwise they refuse to work.

[de-nordic]

So, right here, you've summarized the entirety of the problem I have with EdDSA. The thing is, I have no problem with the algorithm itself, and as far as I can tell it is sound. But it seems to every implementation seems to have been done by someone who has actually never even tried to use it.

I think the general idea is to not let anyone feed you whatever they want as something you try to verify signature on. If you have some black-box crypto device you can just feed it message and signature and get verification for it, without pulling hash out of the black box. If you can provide hash, same may be possible for an attacker (?), which means that having valid signature-hash pair is enough to validate any message.

There is absolutely no reason that an implementation of PureEdDSA would ever need to have the entire image in memory. But, as part of the hash, it does require hashing of the image multiple times, so can't just use a simplistic API.

Above would be the reason, although if an implementation would just have callback "give-me-chunk" then that would be enough to pass whatever the implementation wants.

Given that we are basically stuck with the implementations that exist, however, using HashEdDSA seems perfectly fine. HashEdDSA basically reduces the security of EdDSA to the same as ECDSA, and, for that matter, every other signature algorithm.

We do not have HashEdDSA, we have SHA256-ED25519-SHA512 or SHA512-ED25519-SHA512, as far as I understand http://ed25519.cr.yp.to/eddsa-20150704.pdf and https://www.rfc-editor.org/rfc/rfc8032.html#page-9

[utzig]

We do not have HashEdDSA, we have SHA256-ED25519-SHA512 or SHA512-ED25519-SHA512, as far as I understand http://ed25519.cr.yp.to/eddsa-20150704.pdf and https://www.rfc-editor.org/rfc/rfc8032.html#page-9

There is no such thing as ED25519-SHA512. ed25519 is by definition built with curve25519-sha512, so what we currently have is SHA256-ED25519. Both primitives have 128 bit equivalent security. Using SHA512-ED25519 is adding a 256 bit equivalent hash in front a of 128 bit curve. If SHA256-ED25519 is unsecure because of the hash size, then SHA256-EC256 is also to be considered unsecure because of the hash size, since curve25519 and secp256r1 provide similar security.

[taltenbach]

We do not have HashEdDSA, we have SHA256-ED25519-SHA512 or SHA512-ED25519-SHA512, as far as I understand http://ed25519.cr.yp.to/eddsa-20150704.pdf and https://www.rfc-editor.org/rfc/rfc8032.html#page-9

There is no such thing as ED25519-SHA512. ed25519 is by definition built with curve25519-sha512, so what we currently have is SHA256-ED25519. Both primitives have 128 bit equivalent security. Using SHA512-ED25519 is adding a 256 bit equivalent hash in front a of 128 bit curve. If SHA256-ED25519 is unsecure because of the hash size, then SHA256-EC256 is also to be considered unsecure because of the hash size, since curve25519 and secp256r1 provide similar security.

I think @de-nordic was referring to the notation used in the first paper he cited, i.e. EdDSA for more curves. The standard Ed25519 defined by RFC 8032 is indeed "Ed25519-SHA-512" in the paper.

I agree that SHA-256-Ed25519, as done currently by MCUboot, provides a similar level of security as ECDSA with P-256 and SHA-256. So using SHA-256 pre-hashing with Ed25519 seems fine. However, the standard way of doing HashEdDSA with Edwards25519 is defined in RFC 8032 as Ed25519ph and Ed25519ph mandates the use of SHA-512 as the pre-hashing function. As said, I guess using SHA-256 instead is unlikely to cause any trouble, but I also think that staying as close as possible to the standard is a good practice, especially when we are talking about security.

[utzig]

I think @de-nordic was referring to the notation used in the first paper he cited, i.e. EdDSA for more curves. The standard Ed25519 defined by RFC 8032 is indeed "Ed25519-SHA-512" in the paper.

Good point, I stand corrected. Do you know any ed25519 implementation, in any library/language, that is not built with sha-512 as the hash?

Edwards25519 is defined in RFC 8032 as Ed25519ph and Ed25519ph mandates the use of SHA-512 as the pre-hashing function

Which section mentions this? Is there a rationale or do they just pick sha-512 because it's already there as the hash?

Unrelated point but does mcumgr already support testing an image whose hash is sha-512?

[de-nordic]

Good point, I stand corrected. Do you know any ed25519 implementation, in any library/language, that is not built with sha-512 as the hash?

No. Still on the loop regarding the shaxyz-ed25519-sha512 naming? It is just a designation, and a correct one.

Which section mentions this? Is there a rationale or do they just pick sha-512 because it's already there as the hash?

Actually they just state (in http://ed25519.cr.yp.to/eddsa-20150704.pdf) that you can use any hash function as input to the PureEdDSA, which kinda makes sense - it just signs/verifies message, it does not really know what it is. For rationale, ask the authors of both documents - and if they say "yes", then what?

Using what you have is still a good rationale, considering the fact that you only need to bring in implementation of a single hash function; also if there is hardware support there may be sha512 accelerator, because there is ed25519 hardware support, it does not mean you will have other sha implementations - which again means that you have to bring either driver or software support for other sha. The HashEdDSA expects sha512 by algorithm definition; the PSA implementation of HashEdDSA requires SHA512 and will refuse to work on sha256. I do not see why we should not then use sha512 as message for PureEdDSA in the sha-512-ed25519 scheme. Even if that does not improve security, as you state, the reduction in required support for two sha algs is already an improvement.

Unrelated point but does mcumgr already support testing an image whose hash is sha-512?

Not yet, but I work on the implementation, with use of the PSA of PureEdDSA and the PureEdDSA(sha512) over image and have been using the imgtool here to generate images for tests.

[utzig]

Good point, I stand corrected. Do you know any ed25519 implementation, in any library/language, that is not built with sha-512 as the hash?

No. Still on the loop regarding the shaxyz-ed25519-sha512 naming? It is just a designation, and a correct one.

Which section mentions this? Is there a rationale or do they just pick sha-512 because it's already there as the hash?

Actually they just state (in http://ed25519.cr.yp.to/eddsa-20150704.pdf) that you can use any hash function as input to the PureEdDSA, which kinda makes sense - it just signs/verifies message, it does not really know what it is. For rationale, ask the authors of both documents - and if they say "yes", then what?

Using what you have is still a good rationale, considering the fact that you only need to bring in implementation of a single hash function; also if there is hardware support there may be sha512 accelerator, because there is ed25519 hardware support, it does not mean you will have other sha implementations - which again means that you have to bring either driver or software support for other sha. The HashEdDSA expects sha512 by algorithm definition; the PSA implementation of HashEdDSA requires SHA512 and will refuse to work on sha256. I do not see why we should not then use sha512 as message for PureEdDSA in the sha-512-ed25519 scheme. Even if that does not improve security, as you state, the reduction in required support for two sha algs is already an improvement.

Unrelated point but does mcumgr already support testing an image whose hash is sha-512?

Not yet, but I work on the implementation, with use of the PSA of PureEdDSA and the PureEdDSA(sha512) over image and have been using the imgtool here to generate images for tests.

Sorry for asking.

[de-nordic]

Sorry for asking.

No problem.

[de-nordic]

@d3zd3z I have addressed your comments, can you re-review?

[taltenbach]

LGTM, using https://github.com/mcu-tools/mcuboot/pull/2066 I was able to test the images generated by imgtool.py on an STM32F4 MCU. Works fine :+1: