Cipher Hash Construction - Symmetric Key

[Will Adair]

Hi,

I was reviewing the code for the Cipher Hash Construction (CHC) compression function. It appears to XMALLOC a key, but then does not populate it with any actual key, effectively resulting in a zero key. I have a few questions about this.

1. Is this intentional?

2. Would it make sense to allow the key to be specified on a per-call basis of the chc_process function? (I ask particularly about this one since it would change the function signature of CHC and cause it to look different from the usual hash. However, this would also be reasonable since CHC is literally constructed from a cipher that requires a key as input.)

Thanks.

Will Adair.

[g...@jaeckel.eu]

Hi Will,

On 1/29/25 2:51 PM, Will Adair wrote:
> Hi,
>
> I was reviewing the code for the Cipher Hash Construction (CHC)
> compression function. It appears to XMALLOC a key, but then does not
> populate it with any actual key, effectively resulting in a zero key. I
> have a few questions about this.
>
> 1. Is this intentional?

I'd say yes, that's intentional.

> 2. Would it make sense to allow the key to be specified on a per-call
> basis of the chc_process function? (I ask particularly about this one
> since it would change the function signature of CHC and cause it to look
> different from the usual hash. However, this would also be reasonable
> since CHC is literally constructed from a cipher that requires a key as
> input.)

I wouldn't change the existing API, but add an additional API for that
purpose.

_BUT_ I'm not sure if you should really do that resp. even use the CHC
mode, after reading through the answers of [0].

If you plan to extend it and want your changes upstream, feel free to
provide them either via a patch on the ML or via a PR on our Github repo.
FTR: if you send the patch to the ML I'll take it and make a PR for you,
since that's our regular workflow for reviews and CI.


HTH

Cheers
Steffen

[0] https://crypto.stackexchange.com/questions/6472

[Will Adair]

Hi Steffen, apologies for the slow response. Nice to talk to the famous sjaeckel from Github.

I'm actually trying to implement the functionality from here: Specification of Secure Hardware Extensions

Particularly the Miyaugchi-Praneel Compression function in chapter 4.3.3 which is similar in nature to the CHC, but not quite the same.

I'll let you know if I am successful in implementing it. I have not been able to recreate the test vector in chapter 4.13.2.4, even using AES-128 in ECB mode directly.

Thanks.

Will Adair

[g...@jaeckel.eu]

Hi Will,

On 01.02.25 01:16, Will Adair wrote:
> Hi Steffen, apologies for the slow response.

no worries.

> I'm actually trying to implement the functionality from here:
> Specification of Secure Hardware Extensions

> <https://www.autosar.org/fileadmin/standards/R22-11/FO/AUTOSAR_TR_SecureHardwareExtensions.pdf>

>
> Particularly the Miyaugchi-Praneel Compression function in chapter 4.3.3
> which is similar in nature to the CHC, but not quite the same.
>
> I'll let you know if I am successful in implementing it. I have not been
> able to recreate the test vector in chapter 4.13.2.4, even using AES-128
> in ECB mode directly.

I just tried it out and it's possible.

> cipher_hash_test....state in contents:
> 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ........ ........
> buf contents:
> 6B C1 BE E2 2E 40 9F 96 E9 3D 7E 11 73 93 17 2A | k....@.. .=~.s..*
> state out contents:
> A4 EF 1D 68 3C 7B 7D 91 8C D6 F2 4D 25 59 E5 0E | ...h<{}. ...M%Y..
> state in contents:
> A4 EF 1D 68 3C 7B 7D 91 8C D6 F2 4D 25 59 E5 0E | ...h<{}. ...M%Y..
> buf contents:
> AE 2D 8A 57 1E 03 AC 9C 9E B7 6F AC 45 AF 8E 51 | .-.W.... ..o.E..Q
> state out contents:
> 19 76 AE D1 8C 2F 37 46 16 5E 5D E2 C4 C5 D4 46 | .v.../7F .^]....F
> state in contents:
> 19 76 AE D1 8C 2F 37 46 16 5E 5D E2 C4 C5 D4 46 | .v.../7F .^]....F
> buf contents:
> 80 00 00 00 00 00 00 00 00 00 00 00 00 00 01 00 | ........ ........
> state out contents:
> C7 27 7A 0D C1 FB 85 3B 5F 4D 9C BD 26 BE 40 C6 | .'z....; _M..&.@.
> tmp contents:
> C7 27 7A 0D C1 FB 85 3B 5F 4D 9C BD 26 BE 40 C6 | .'z....; _M..&.@.
> passed 346.836ms

You're right, it's only a slight deviation of CHC and I've not decided
for myself yet, whether it's only a variant of CHC or an entirely
separate implementation.

Feel free to get back if you have questions (or with your version of the
implementation) :)

Cheers
Steffen

[Will Adair]

Hi Steffen,

One part of me just wants to make another implementation for the AES-MP algorithm in the AUTOSAR specification from earlier in this e-mail chain. (I already did. It's basically a copy of CHC with slight modifications to match the Miyaguchi-Pranel and I named it chc_mp. Having said that, it doesn't feel like a nice holistic, extendable solution for libtomcrypt, so I wouldn't want to necessarily submit the patch for merge.)

The other part of me wants to redesign CHC to match the theoretical designs as shown here: One-way compression function - Wikipedia 

Off the top of my head, several changes would need to be considered:

• CHC must accept an IV rather than assuming the IV is a zero-block. The user must (and really should want to) specify H0, even if it just ends up being a zero block.
• CHC must accept a compression function mode argument. I would probably start with Miyaguchi-Preneel since it's what I need, but it would be easily extendable to the other compression function designs while maintaining the Merkle–Damgård construction and would not alter the function prototype of CHC. (Initial thought would be an array of function pointers indexed by a mode enumeration, perhaps with bounds check to make sure we don't index outside the array.)
• CHC must utilize and / or accept a "g" function. (I will refer to the "g" function as the key input transform function) This essentially is a transform to take Hi-1 and transform it into a valid key for the block cipher to use for processing mi into Hi for a given increment of the compression function execution.
• I question whether or not the user should be able to provide this as a function pointer at run-time or if they should be forced to implement it within libtomcrypt. I would propose the default key input transform function be an identity function on Hi-1 to create the key for that increment of compression function execution. This helps create a clean separate boundary for the key input transform function in the software design while not necessarily doing anything "unexpected" by default for a user that uses libtomcrypt out of the box. (Of course, this would all be documented in the TeX file as well.)

Lastly, (and technically separate of wanting to add modes) I would propose that the arbitrary padding function in chc_mp_done() be removed. The Merkle–Damgård construction seems to show that it is the responsibility of the user calling the hash to correctly pad the inputs to the compression function. I'm honestly not sure where the design for the implementation of the current CHC comes from, but I'd be inclined to retain all the functionality if there was a clear source of the design for the current implementation.

Looking forward to feedback.

Thanks.

Will Adair