Score:1

Crypto

How to most inexpensively extract 1 byte of uniformly distributed entropy from a 32-byte Curve25519 EC point

knaccc

5/31/23, 4:16 PM

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.

119

0 + 0

hash

x25519

Paul Uszak

5/31/23, 4:30 PM

XOR the point 31 times.

knaccc

5/31/23, 4:52 PM

@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

knaccc

5/31/23, 7:38 PM

@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

Score:2

Crypto

kelalaka

5/31/23, 8:38 PM

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]

0 + 0

knaccc

5/31/23, 8:51 PM

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?

kelalaka

5/31/23, 8:53 PM

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.

knaccc

5/31/23, 8:54 PM

Then why do the XOR, if the first byte of the BLAKE3 output would already be uniformly random?

kelalaka

5/31/23, 8:57 PM

You may not need it, however, condensing them to one byte has no danger and almost has no cost.

knaccc

5/31/23, 9:01 PM

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

kelalaka

5/31/23, 9:11 PM

This method clusters the points into 256 buckets uniform randomly. Yes, this gives an attacker 8-bit knowledge about the point(s). The checksum can provide simple relation about the point that can be exploited or linked to the curve equation that I cannot see or prove. I would stick to hashing.

kelalaka

5/31/23, 9:12 PM

Also, the uniform randomly needs to be proved for the checksum, this is the hard part.

knaccc

5/31/23, 9:13 PM

Thanks, I'll leave the question open for a few days, and will accept your answer if someone does not suggest something less compute-intensive

kelalaka

6/1/23, 3:40 PM

@knaccc that about using chacha8 with DHKE's extracted key and using zero IV? It is will be very fast. Where do you want to use this?

knaccc

6/1/23, 4:41 PM

Monero is currently debating how to implement something called a "view tag": https://github.com/monero-project/monero/pull/8061 It then came to light that it is important that the hash of two different occurences of the same ecdh secret with different ints concatenated need to be unlinkable when examining hashes of each, so that rules out skipping the hash entirely. Thanks for the chacha8 tip. We benchmarked Blake3, and that looks promising if there is an appetite among the developers to introduce a new type of hash (in addition to keccak that we currently use everywhere)

kelalaka

6/1/23, 5:14 PM

@knaccc our [vulture](https://chat.stackexchange.com/transcript/message/60312478#60312478) warned me, about this. You know, most of the times I've linked to their answer for your Qs.

knaccc

6/1/23, 5:29 PM

Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/133712/discussion-between-knaccc-and-kelalaka).

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to most inexpensively extract 1 byte of uniformly distributed entropy from a 32-byte Curve25519 EC point

TH: วิธีแยกเอนโทรปีแบบกระจายอย่างสม่ำเสมอ 1 ไบต์ออกจากจุด EC Curve25519 ขนาด 32 ไบต์

RO: Cum să extrageți cel mai ieftin 1 octet de entropie distribuită uniform dintr-un punct EC Curve25519 de 32 de octeți

RU: Как максимально недорого извлечь 1 байт равномерно распределенной энтропии из 32-байтовой точки EC Curve25519

VI: Cách trích xuất ít tốn kém nhất 1 byte entropy được phân phối đồng đều từ điểm Curve25519 EC 32 byte

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.