1
$\begingroup$

I'm looking for the simplest and most inexpensive hash with the following properties:

Input: A 32-byte Curve25519 EC point containing approximately 125 bits of non-uniformly distributed entropy (created as a result of an ECDH exchange).

Output: 1 byte containing 8 bits of entropy, uniformly distributed.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ XOR the point 31 times. $\endgroup$
    – Paul Uszak
    Jan 31, 2022 at 16:30
  • $\begingroup$ @PaulUszak What is the best way of demonstrating the validity of your method? Are there any papers that can be cited? I would need to convince people that are terrified of doing anything other than truncating the output of a cryptographically secure hash to 1 byte $\endgroup$
    – knaccc
    Jan 31, 2022 at 16:52
  • $\begingroup$ @kelalaka what is the fastest hash that would tame the non-uniformity, given that the one-byte output means we're not restricted to hashes that deliver collision resistance? I'm hoping that this lack of restriction means that far simpler and faster hashing methods are available for this use case $\endgroup$
    – knaccc
    Jan 31, 2022 at 19:38

1 Answer 1

Reset to default
2
$\begingroup$

The usual encoding of the points is structured and non-uniform since it must satisfy the curve equation. In Curve25519 with $x \in \mathbb Z(2^{255} - 19)\mathbb Z$ and using the curve equation $x^3 + 486662 x^2 + x$ is always a square for the points. There is common advice to use a KDF on the ECDH output to use AES keys since it may attack points to related key attakks.

One solution for the requirement is using a fast PRF like ChaCha8 where the key is the key of DHKE wiht zero IV.

func extact_one_byte( Point P):
  
   oneByte = 0  
   out512 = ChaCha8(key,00..00, x(P)||y(P))
   
   return out512[0:8]
Improve this answer
$\endgroup$
12
  • $\begingroup$ Are you saying that the characteristics of BLAKE3 are such that if it were truncated to a single byte, that byte would not meet the requirement of being uniformly random? Please could you give your reasoning? $\endgroup$
    – knaccc
    Jan 31, 2022 at 20:51
  • $\begingroup$ The output of a cryptographic hash function is expected to be indistinguishable from uniform random. Unless, one can prove the reverse, all bytes, all bits are indistinguishable. Therefore their x-or, too. $\endgroup$
    – kelalaka
    Jan 31, 2022 at 20:53
  • $\begingroup$ Then why do the XOR, if the first byte of the BLAKE3 output would already be uniformly random? $\endgroup$
    – knaccc
    Jan 31, 2022 at 20:54
  • $\begingroup$ You may not need it, however, condensing them to one byte has no danger and almost has no cost. $\endgroup$
    – kelalaka
    Jan 31, 2022 at 20:57
  • $\begingroup$ If I consider the EC point to be a secret with a bit strength of 125 bits, and if I am concerned about leaking information about this secret, what would be the bit strength of this secret after publishing the 1-byte hash? And if the answer is that I should expect it to be 125-8=117 bits after publishing the 1-byte hash, why would it matter if a cryptographically secure hash is used instead of a simpler checksum? I think this is the reason that @PaulUszak said to just XOR the bytes of the EC point and not hash at all $\endgroup$
    – knaccc
    Jan 31, 2022 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.