Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints

From: Weikeng Chen <[email-masked]>
Date: Sat, 3 May 2025 06:53:25 -0700 (PDT)

I want to add a footnote that, there could be a security complication for 
either using SHA-256 or AES:

for this to be secure:
hash(UTXO_A||salt) + hash(UTXO_B||salt) - hash(UTXO_C||salt) - 
hash(UTXO_D||salt) == 0

either:
- using a regular hash or AES_k, which should work in the same way, but 
salt/AES key needs to have sufficient security and only known by trusted 
parties (e.g., the user who is computing the sum). aka, the hash sum would 
be the user's own bookkeeper, and other people should not trust that result.

or:
- using a significantly longer hash function, although it should still be 
performant enough. A paper from Facebook "Securing Update Propagation with 
Homomorphic Hashing" has cited that:

> AdHash initially received the most attention by several works which aimed 
to implement the construction [SY98, CL99, GSC01], each using a 128-bit or 
256-bit modulus. However, Wagner [Wag02] later showed an attack on the 
generalized birthday problem which could be used to find collisions for 
AdHash on an n-bit modulus in time O(2^{2\sqrt{n})), and that the AdHash 
modulus needs to be greater than 1600 bits long to provide 80-bit security. 
Lyubashevsky [Lyu05] and Shallue [Sha08] showed how to solve the Random 
Modular Subset Sum problem (essentially equivalent to finding collisions in 
AdHash) in time O(2^{n^\epsilon}) for any \epsilon < 1, which indicates 
that AdHash requires several more orders of magnitude larger of a modulus 
just to provide 80-bit security.

On Saturday, May 3, 2025 at 8:07:54 PM UTC+8 Greg Maxwell wrote:

> On Saturday, May 3, 2025 at 11:55:28 AM UTC Sanket Kanjalkar wrote:
>
> > hash(UTXO_A||salt) + hash(UTXO_B||salt) - hash(UTXO_C||salt) - 
> hash(UTXO_D||salt) == 0 (proving (A==C && B==D) || (A==D && B==C))
>
> What if instead of hash we encrypt with AES and modular add/subs? I cannot 
> prove it; but I also don't see a clear way this is broken. 
>
> 1. Sample random symmetric key `k`
> 2. Instead of above; AES_k(UTXO_A) + AES_k(UTXO_B) - AES_k(UTXO_C) - 
> AES(UTXO_D) == 0 =>  (proving (A==C && B==D) || (A==D && B==C))?
>
>
> AES in CTR mode is, I'm not sure about other modes? Obviously CTR mode 
> would be unsuitable! (I mean sure modular add/sub and xor are different 
> operations but they are quite close).  I think that in many modes the 
> collision resistance would have to at least be restricted by the birthday 
> bound with the small block size. I think CMC might be needed to avoid that 
> sort of issue.
>
>  
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email-masked].
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/9f9f0b4d-98b0-4e41-a1c3-903ee05da462n%40googlegroups.com.