From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 To: Bitcoin Development Mailing List Message-Id: <9f9f0b4d-98b0-4e41-a1c3-903ee05da462n@googlegroups.com> In-Reply-To: References: <69194329-4ce6-4272-acc5-fd913a7986f3n@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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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:

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

either:
- 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.

or:
- 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:
> 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 < 1, which indicat= es 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=E2=80=AFPM UTC+8 Greg Maxwell wrote= :
On Saturday, May 3, 2025 at 11:55:28=E2=80=AFAM UTC Sanket Kanj= alkar wrote:
> 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 && B=3D=3DD) || (A=3D=3DD &&= ; B=3D=3DC))

What if instead of hash we encry= pt with AES and modular add/subs? I cannot prove it; but I also don't s= ee a clear way this is broken.=C2=A0

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) =3D=3D 0 =3D>=C2=A0=C2=A0(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? 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.

=C2=A0

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/9f9f0b4d-98b0-4e41-a1c3-903ee05da462n%40googlegroups.com.
------=_Part_152609_1928432315.1746280405137-- ------=_Part_152608_619217101.1746280405137--