path: root/e8/3a44f584b1ac0e5f7c14a5ceaf44fb1fbc4ca5

Delivery-date: Sat, 03 May 2025 07:26:22 -0700
Received: from mail-yb1-f185.google.com ([209.85.219.185])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBCTP33FZ3YMBBBGP3DAAMGQE33JTBOQ@googlegroups.com>)
	id 1uBDor-0006K6-Ct
	for bitcoindev@gnusha.org; Sat, 03 May 2025 07:26:22 -0700
Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-e752ac28e82sf3150731276.3
        for <bitcoindev@gnusha.org>; Sat, 03 May 2025 07:26:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1746282375; x=1746887175; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:sender:from
         :to:cc:subject:date:message-id:reply-to;
        bh=EQRl/OABQqruvNNW01q1z7obVRCYLE7M9/7NvlqvHqY=;
        b=SertCeMHUlpkDJ4rCxmJ7lC4BIiFsJJ3IgNl/l2oRWvrK01eduiY3DoStyzukXNwZ+
         XNMmaw/pZ7hlDjL2g+cx8cxPVaKvrpFS9S1vogDV0z5LpkUOZ8kGknxczrB1N60Hra62
         HhnjqAC0GtlqsOIg3gIZEq6kGHdoCFo0G8GOvuuVGl76ezzugDrMysw+O/XgWQrFZr/e
         HKzOTZSZZrW9uLkligcuHgNlO3GlhwUihA4yKhf6VtZYxkmMGfZygjjw7qhejoM9S7rF
         NuNWahcFfV0ymZq/yXTb2TF7dmmBZMHr6eREGOVPCzctmPPBs5UYMO6DWHFrFa+xhxFH
         wqQA==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups-com.20230601.gappssmtp.com; s=20230601; t=1746282375; x=1746887175; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:from:to:cc
         :subject:date:message-id:reply-to;
        bh=EQRl/OABQqruvNNW01q1z7obVRCYLE7M9/7NvlqvHqY=;
        b=v+uJUbuqVxzPWszaod671R0uPb3I1lCWpGpVGG/9SzjsFahl3+o/Y0DgtkDcJkogKw
         n0IHAuxBgjN98lnAtlZfzmAkS7EmoeufhdTSqjUNjFf2qscAnkrujy7s2nZ/v65CDzpe
         93O05E6m8Fa7SUWNMQVO8FTcndPPTrm9Zlq5vnjE8Gk4aVf8bMQrJl6SOUY5O5wo8brE
         kn5j3yzgcAZZj6EkoypXeEgtdZq55Qnv4AWar9SuhS6WucWhvonQ+IQC+Sskaf1Mhhtn
         qT73OG9LN3w/joy9iBkBmyrvXD4lKfuevM31MOh4EQWNFPtM9TrrNYp+TJRpF1OBuQX6
         0aog==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1746282375; x=1746887175;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:x-beenthere
         :x-gm-message-state:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=EQRl/OABQqruvNNW01q1z7obVRCYLE7M9/7NvlqvHqY=;
        b=ihPXZ4AWNnfFWhuUTjxIhUacZ/D4is8Xj9RX7CVfBfHrk+eL6UcgMC/crBQKIF1DL1
         CS2My2FVvZ1La9hGP+Smygu7UyIb+/YT7FtaDwG77thIVN0lkmVxxIb9gs9iS1+y+zJJ
         phyksrNZz2nN4TxOPdmKiPPAzvL1Fq6k54/ClVkqPweznN6/BuhmA8/U7ORqoGXwCRJe
         0QBhHA0y6bxKFq/A3J95w+b+0Pj62eXNbfWv2qeuVUs9Z+CxF6jEDFHQTSqrRhWT4mdp
         M6yN5eGDAqMx3aj+6pMdDMgzvQO4kYajCncDsFx9e9es2aA8rXVb+JvLCpaOeFVRv4ru
         oTig==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCUP1NsPpv1UuuL3TtjT+0p7IjT/EFyyzLcgQqZxOJHHZ3OIcUBjNitni2vPgYuuID4S1Q1WkBhm1ngn@gnusha.org
X-Gm-Message-State: AOJu0YzGfl+8phfO7Y+a8ta48rJXj3j5WFs4l0o+w+igDuYaND3qMwnt
	tyBE4aOZE+DlRMQI3b2rzzLzrysoeS8wDu+IEilHiH7SqFXGobZS
X-Google-Smtp-Source: AGHT+IHL8PpQK5AhJ4a+1Ea5XP3i6oV/x2RDh3Wc6Erf05x6d5z+yiyNNuiVTAZgsdBKIwVomzjeSQ==
X-Received: by 2002:a05:6902:2702:b0:e73:fd7:8d08 with SMTP id 3f1490d57ef6-e757d0e1409mr1422140276.15.1746282375381;
        Sat, 03 May 2025 07:26:15 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBGReflsIViCvHushvrZ8+fbJ9pWTG3OIJ+PUJyXDT0lSQ==
Received: by 2002:a25:2d05:0:b0:e73:2ea4:55ac with SMTP id 3f1490d57ef6-e74dcbaae19ls357185276.2.-pod-prod-07-us;
 Sat, 03 May 2025 07:26:11 -0700 (PDT)
X-Received: by 2002:a05:690c:64c5:b0:6fb:9280:5bf4 with SMTP id 00721157ae682-708eaf6458cmr15064167b3.30.1746282371830;
        Sat, 03 May 2025 07:26:11 -0700 (PDT)
Received: by 2002:a81:8544:0:b0:6fd:27d2:c7f1 with SMTP id 00721157ae682-708cfcbcea0ms7b3;
        Sat, 3 May 2025 06:53:26 -0700 (PDT)
X-Received: by 2002:a05:690c:890:b0:6ef:7f89:d906 with SMTP id 00721157ae682-708eaf83999mr13966817b3.33.1746280405493;
        Sat, 03 May 2025 06:53:25 -0700 (PDT)
Date: Sat, 3 May 2025 06:53:25 -0700 (PDT)
From: Weikeng Chen <weikeng.chen@l2iterative.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <9f9f0b4d-98b0-4e41-a1c3-903ee05da462n@googlegroups.com>
In-Reply-To: <fbf06c5b-57b6-4615-99bb-3a7ea31ebf22n@googlegroups.com>
References: <CAPv7TjaM0tfbcBTRa0_713Bk6Y9jr+ShOC1KZi2V3V2zooTXyg@mail.gmail.com>
 <cc2dfa79-89f0-4170-9725-894ea189a0e2n@googlegroups.com>
 <CAPv7TjaDGr4HCdQ0rR6_ma5zh2umU9r3_529szdswn_GjjnuCw@mail.gmail.com>
 <69194329-4ce6-4272-acc5-fd913a7986f3n@googlegroups.com>
 <CAExE9c8XfEH__onX3DhUQh0OnvpoOLwRRp8+Z6PozyKGtqpspw@mail.gmail.com>
 <fbf06c5b-57b6-4615-99bb-3a7ea31ebf22n@googlegroups.com>
Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_152608_619217101.1746280405137"
X-Original-Sender: weikeng.chen@l2iterative.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.7 (/)

------=_Part_152608_619217101.1746280405137
Content-Type: multipart/alternative; 
	boundary="----=_Part_152609_1928432315.1746280405137"

------=_Part_152609_1928432315.1746280405137
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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

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

either:
- using a regular hash or AES_k, which should work in the same way, but=20
salt/AES key needs to have sufficient security and only known by trusted=20
parties (e.g., the user who is computing the sum). aka, the hash sum would=
=20
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=
=20
performant enough. A paper from Facebook "Securing Update Propagation with=
=20
Homomorphic Hashing" has cited that:

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

On Saturday, May 3, 2025 at 8:07:54=E2=80=AFPM UTC+8 Greg Maxwell wrote:

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

--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
9f9f0b4d-98b0-4e41-a1c3-903ee05da462n%40googlegroups.com.

------=_Part_152609_1928432315.1746280405137
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I want to add a footnote that, there could be a security complication for e=
ither using SHA-256 or AES:<div><br /></div><div>for this to be secure:</di=
v><div>hash(UTXO_A||salt) + hash(UTXO_B||salt) - hash(UTXO_C||salt) - hash(=
UTXO_D||salt) =3D=3D 0<br /><br /></div><div>either:</div><div>- using a re=
gular hash or AES_k, which should work in the same way, but salt/AES key ne=
eds to have sufficient security and only known by trusted parties (e.g., th=
e 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.</div><div><br /=
></div><div>or:</div><div>- using a significantly longer hash function, alt=
hough it should still be performant enough. A paper from Facebook "Securing=
 Update Propagation with Homomorphic Hashing" has cited that:</div><div><br=
 /></div><div>&gt; AdHash initially received the most attention by several =
works which aimed to implement the construction [SY98, CL99, GSC01], each u=
sing a 128-bit or 256-bit modulus. However, Wagner [Wag02]
later showed an attack on the generalized birthday problem which could be u=
sed to find collisions
for AdHash on an n-bit modulus in time O(2^{2\sqrt{n})), and that the AdHas=
h modulus needs to be greater
than 1600 bits long to provide 80-bit security. Lyubashevsky [Lyu05] and Sh=
allue [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 &lt; 1, which indicat=
es that AdHash requires several more orders
of magnitude larger of a modulus just to provide 80-bit security.</div><div=
><br /></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_at=
tr">On Saturday, May 3, 2025 at 8:07:54=E2=80=AFPM UTC+8 Greg Maxwell wrote=
:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex;=
 border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div d=
ir=3D"auto">On Saturday, May 3, 2025 at 11:55:28=E2=80=AFAM UTC Sanket Kanj=
alkar wrote:<br></div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-=
left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr">&gt; has=
h(UTXO_A||salt) + hash(UTXO_B||salt) - hash(UTXO_C||salt) - hash(UTXO_D||sa=
lt) =3D=3D 0 (proving (A=3D=3DC &amp;&amp; B=3D=3DD) || (A=3D=3DD &amp;&amp=
; B=3D=3DC))<br><br></div><div dir=3D"ltr">What if instead of hash we encry=
pt with AES and modular add/subs? I cannot prove it; but I also don&#39;t s=
ee a clear way this is broken.=C2=A0<br><br>1. Sample random symmetric key =
`k`<br>2. Instead of above; AES_k(UTXO_A) + AES_k(UTXO_B) - AES_k(UTXO_C) -=
 AES(UTXO_D) =3D=3D 0 =3D&gt;=C2=A0=C2=A0(proving (A=3D=3DC &amp;&amp; B=3D=
=3DD) || (A=3D=3DD &amp;&amp; B=3D=3DC))?</div></blockquote><div><br></div>=
</div><div><div>AES in CTR mode is, I&#39;m not sure about other modes? Obv=
iously CTR mode would be unsuitable! (I mean sure modular add/sub and xor a=
re different operations but they are quite close).=C2=A0 I think that in ma=
ny modes the collision resistance would have to at least be restricted by t=
he birthday bound with the small block size. I think CMC might be needed to=
 avoid that sort of issue.</div><div><br></div><div>=C2=A0</div></div></blo=
ckquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/9f9f0b4d-98b0-4e41-a1c3-903ee05da462n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/9f9f0b4d-98b0-4e41-a1c3-903ee05da462n%40googlegroups.com</a>.<br />

------=_Part_152609_1928432315.1746280405137--

------=_Part_152608_619217101.1746280405137--