Ah what am I saying, that 'mitigation' already lines up with how Jamtis works. The PQ shared secret just gets inserted between index decryption and Ko reconstruction for non-selfsends.

I thought npbits/ncbits would be changing, but that isn't necessary.

UkoeHB: Adding a new validation rule is a soft fork. Old clients won't validate it, but no blocks will be mined that violate the rule.

UkoeHB: The CSIDH shared secret is calculated after decrypting the address index.

Why does it need to be validated by miners? Seems cheap enough to validate in the scanner, since the check is behind view tags.

Plus a malicious remote node or filter assist layer could send invalid CSIDH keys, so they need to be validated anyway.

<kayabanerve:matrix.org> McEliece should actually have the first property, speed AFAIK. Re: key size, it's smaller than the proposal for 4 GB RSA keys /s

UkoeHB: The argument for validating the pubkey by consensus is that an invalid pubkey leaks the fact that the transaction is sending to a legacy address. It might stop lazy wallet developers from cutting corners. But yes, otherwise it could be validated just by the wallet if we are OK with having invalid keys in some transactions.

kayabanerve: IIRC the proposal was for 1 TB RSA keys: eprint.iacr.org/2017/351.pdf

<syntheticbird> > Level 31 takes two 500GB numbers and multiplies them to create the final 1TB output.

<syntheticbird> this paper is a meme

<syntheticbird> Level 1 RSA vs Level 99 RSA

<jpk68:matrix.org> It was a joke submission AFAIK

also: "A terabyte takes only a few hours to transmit over a gigabit-per-

second link

<kayabanerve:matrix.org> csrc.nist.gov/CSRC/media/Presentati…-media/PostQuantumRSA-April2018.pdf

<kayabanerve:matrix.org> This NIST presentation discusses a 2**30-byte key as their primary parameters, but it's absurd regardless

<kayabanerve:matrix.org> Eh. It's only half a joke IMO. The fact it technically works and could hold up as a battle-tested algorithm makes it not entirely dismissable. It's more of an artifact of what's technically an option rather than a practical suggestion.

<jpk68:matrix.org> Just use RFC 1149 and attach an SSD to the bird

<kayabanerve:matrix.org> I say that as in, if two government agencies wanted to do an key exchange using PKC, I wouldn't be surprised if a PQ RSA-inclusive-hybrid scheme was discussed.

<kayabanerve:matrix.org> For critical long-term communications between a limited set of participants, spending a day establishing the initial key material for use in a ratchet is probably acceptable.

<kayabanerve:matrix.org> Definitely not a candidate here, nor is McEliece though 😅

<syntheticbird> please can a genius stand up and make a 128 bit security 256 bit public key lattice pq algo? is that so much to ask ?

^ I'm pretty sure that's impossible.

<syntheticbird> impossible or impossible ?

tevador: Wallets would have a strong incentive to support sending to jamtis-pq addresses, so it's an unlikely edge case that one would cut corners in that way. They could easily circumvent a check by including a hard-coded 'valid' value in every tx.

Do you think checking the presence of the new tx extra field should also be removed from consensus?

tevador: probably. I can't find any actual rules about tx_extra in the crazy spaghetti mess of tx validation code (presumably it would be in `check_tx_semantic`), so not validating would be consistent.

This is how you get anonymity puddles. It would be just 2 puddles, but still.

Anyways, in that case Jamtis is not a fork at all, just a point release.

It can be revisited. Perhaps another hardfork will align with jamtis-pq release, and the tx_extra won't be needed.

In that case you would support verifying the key by consensus?

Probably not, since 13ms is substantial for such a small effect.

How about this: encode the CSIPH key with a hash derived from the filter-assist secret.

Then it is uniform.

Oh nvm, it is shared

13ms is similar to the cost of validating a modern CLSAG tx, if my tests at monero-project/research-lab #91 are correct (2in/2out)

<kayabanerve:matrix.org> @syntheticbird:monero.social: that's the ad for SQISign

<kayabanerve:matrix.org> Targeting the post-quantum NIST-1 level of security, our implementation results in signatures of 204 bytes, secret keys of 16 bytes and public keys of 64 bytes.

<kayabanerve:matrix.org> eprint.iacr.org/2020/1240

<kayabanerve:matrix.org> > The original paper concluded that their C implementation takes 0.6 s for key generation, 2.5 s for a sign operation and 0.05 s or 50 ms for a verification operation.[5]

<kayabanerve:matrix.org> > This has improved the signing time by a factor of 20 and the verification time by a factor of 6 while increasing the security level and reducing the signature size by 14%.

<kayabanerve:matrix.org> To quote the Wikipedia page

<kayabanerve:matrix.org> The public key is itself an elliptic curve though, and one would need a way to have a homomorphic derivation process from an isogeny, elliptic curve to isogeny', elliptic curve', to be useful for subaddresses

<kayabanerve:matrix.org> Hm. Off-hand, I think someone who knows the signing key could rerandomize it with algebraic structure. Solely having an private-key account derivation scheme isn't notable though, and this is a signature scheme, when for addresses, we need a KEM. I also understand the currently discussed KEM is also premised on isogenies.

<kayabanerve:matrix.org> For signing, we really need public-key rerandomization...

kayabanerve: PQ signing is out of scope of Jamtis. SQISign is basically equivalent to CSIDH-512 (even uses the exact same prime field). The revised security is less than NIST level 1.

<kayabanerve:matrix.org> I'm aware signing is out of scope and this isn't the current discussion. Thanks for clarifying the relation to CSIDH and its disappointing security

<genoce:matrix.org> > <UkoeHB> genoce: yes, the carrot hierarchy should only be useful for adding wallet functionality. But the main beneficiaries are cold/hardware wallets, so most users wouldn't have a reason to adopt it. Much simpler to just wait a little longer for Jamtis-PQ so most or all users can benefit and wallet complexity is minimized.

<genoce:matrix.org> github.com/jeffro256/carrot/blob/ma…address-conditional-forward-secrecy

<genoce:matrix.org> "A SDLP can learn no receiver or amount information about a transaction output, nor where it is spent, without knowing a receiver's public address."

<genoce:matrix.org> I try to understand if a QA can learn the full XMR money trail if a public address is known.[... more lines follow, see mrelay.p2pool.observer/e/4ojB6fcKeTVjT25Z ]

kayabanerve: Apologies, I confused SQISign with CSI-Fish. So disregard what I wrote about SQISign.

<kayabanerve:matrix.org> genonce: There shouldn't be a cascade

<koe000:matrix.org> genonce: learning where an enote is spent does not mean learning the destination addrs, just the tx where its key image appears.

<kayabanerve:matrix.org> tevador: No worries. It was just a tangent about PQ crypto which advertises comparable sizes. It wasn't an endorsement and I apologize if it distracted from the current conversation, which I do consider critical despite not meaningfully participating at this time.

<syntheticbird> genoce: i remember asking that exact question a year ago, and i was told, as kayabanerve said, that it wouldn't be the case.

<syntheticbird> this message took 2 minutes to send

<koe000:matrix.org> kayabanerve: Where is the sal implementation? I found a multisig impl in Monero-Oxide but no non-multisig impl. Or is everything supposed to use the multisig one?

<koe000:matrix.org> Oh it's in the mod? This is why I don't like putting stuff there, it's so hard to navigate.

<koe000:matrix.org> In other news, I tried reworking sal as a seraphis-style composition proof based on (1/r_i), and ended up with exactly the same proof size (12 points/scalars). Though could shave one by removing the r_j T term from R.

<jeffro256> @genoce:matrix.org: No, the QA cannot learn Bob's address indirectly from knowing Alice's. But under a lot of circumstances, the QA can see in which input Alice spent their funds on-chain

<jeffro256> So if the QA knows Alice and Bob's addresses, then they can link their portions of the traction graph together

<jeffro256> *transaction

<jeffro256> Unless Alice uses the new key hierarchy listed in the CARROT spec and churns her received enote before sending to Bob

<jeffro256> Because the new key hierarchy has the "internal forward secrecy" property where all internal enotes (i.e. selfsend enotes in the new hierarchy) are protected from QAs, even if their public address is known

<syntheticbird> Ok I'm lost right now. I've originally assumed that the new key hierarchy bringed the symmetrically encrypted self-enotes, therefore churning is a viable strategy against QA. I've argumented against Tevador proposal of dropping this new hierarchy because of this feature, and I got told that you didn't need the new hierarchy for this.

<syntheticbird> there is a misunderstanding somewhere i believe

<syntheticbird> . > <UkoeHB> genoce: yes, the carrot hierarchy should only be useful for adding wallet functionality. But the main beneficiaries are cold/hardware wallets, so most users wouldn't have a reason to adopt it. Much simpler to just wait a little longer for Jamtis-PQ so most or all users can benefit and wallet complexity is minimized.

<syntheticbird> ok nvm sorry tevador for the free bullet. That was actually ukoe who answered

<syntheticbird> my sentence is confused. I thought tevador was the one who said that the new hierarchy wasn't needed but actually that was ukoe.

<syntheticbird> oh wait that was ukoe's proposal too. so yeah my bad tevador.

<jeffro256> Yes, this is true. That's why I said in the previous comments that a QA can locate your spends unless you use the new key hierarchy. Sorry if that was unclear

<jeffro256> TBF you don't have to use MY exact key hierarchy to get these properties, but if you use the old kery hierarchy as normal, then you definitely will not get those properties

<syntheticbird> i see. thx for clarifying

<jeffro256> And any new key material derived as a function of the seed is vulnerable to this attack if using the default legacy software 24 word seed format: gist.github.com/jeffro256/4155401274699e0437ba5b79b93c647f

<jeffro256> > Mitigation for exclusive selfsend primary view tag analysis: only use 1 byte of the view tag, the rest gibberish. A filter-assist layer will send all 1-byte matches along with 3-byte matches (assuming 3 bytes for the primary view tag - a 2000x cost for CSIDH-1024 would be 11-bit slowdown, so 3 bytes seems reasonable) to the [... too long, see mrelay.p2pool.observer/e/9s2S6_cKc1c2ZlNz ]

<jeffro256> @UkoeHB I don't see how this mitigates the attack if the 1 byte view tag check still uses ECC. No matter the bit width, the probability of a social connection increases exponentially with more use. For example, if Alice and Bob don't send XMR to each other ever, they will most likely not have one transaction in which both Alic [... too long, see mrelay.p2pool.observer/e/9s2S6_cKc1c2ZlNz ]

<jeffro256> Perhaps there is some compact form to write the probability of an overlap of N txs b/t alice and bob given the total number of transactions on-chain since Alice and Bob wallet creation, and bit width of the view tag

<jeffro256> The number of Bob's and Alice's individual transaction counts affects this probability, but a QA won't know this for sure. But they might be able to guess if either one of them has unusual tx patterns

<koe000:matrix.org> @jeffro256: I was thinking more about transaction flows. Minimizing selfsend analysis with smaller vulnerable view tags aids that. Another option would just be to set the entire view tag to depend on k_vb, filter assist layers would send all enotes, and all enotes would be checked for selfsend view tag matches (and nor [... too long, see mrelay.p2pool.observer/e/-qSv6_cKeG1TTU9m ]

<koe000:matrix.org> A lot more bandwidth (same as current, which is a bottleneck for some users)

<koe000:matrix.org> So only auxiliary selfsends, no more exclusive/auxiliary distinction.

<genoce:matrix.org> Ok the new key hierachy is required for internal forward secrecy. Churning to the same wallet is pointless without the new key hierachy. > <@jeffro256> Because the new key hierarchy has the "internal forward secrecy" property where all internal enotes (i.e. selfsend enotes in the new hierarchy) are protected from QAs, even if their public address is known

<genoce:matrix.org> Without the new key hierachy. Is churning to a new wallet still protected from QAs (ignore seed extraction)

<genoce:matrix.org> Eve > Alice 1 (throw away wallet) > Alice 2 (Of this wallet the QA do not know the addresses)

<jeffro256> > Ok the new key hierachy is required for internal forward secrecy. Churning to the same wallet is pointless without the new key hierachy.

<jeffro256> Yes

<jeffro256> > Without the new key hierachy. Is churning to a new wallet still protected from QAs (ignore seed extraction)[... more lines follow, see mrelay.p2pool.observer/e/y-DA6_cKeFFuWjZ5 ]

<jeffro256> @koe000:matrix.org: This would work AFAICT. I believe that this is basically the idea I wrote out here: gist.github.com/tevador/d3656a217c0…ment_id=5044400#gistcomment-5044400

<koe000:matrix.org> @jeffro256: Looks like it yeah

<genoce:matrix.org> @jeffro256: Good, but complicated. The new key hierachy have some strong benefits. Many people do actually churn and will have some protection against QAs in pre Jamtis-PQ.

<genoce:matrix.org> Adding the new key hierachy before Jamtis-PQ might be more work. At the same time it seems like a safer temporary solution. Who knows what problems will appear with Jamtis-PQ

<syntheticbird> ladies and gentlemen, after stealth addresses, we present to you stealth wallet

<syntheticbird> automatic creation of intermediary wallets to break QA graph

<syntheticbird> I cannot imagine a world where this feature wouldn't be implemented.

<syntheticbird> nor do i imagine anyone not using such feature

<koe000:matrix.org> @jeffro256: It should be opt-out though, not opt-in. Conservative by default, optimizable if your threat model can handle it.

<genoce:matrix.org> This can't be done with new seeds? They are 25 word long right > <@jeffro256> And any new key material derived as a function of the seed is vulnerable to this attack if using the default legacy software 24 word seed format: gist.github.com/jeffro256/4155401274699e0437ba5b79b93c647f

<genoce:matrix.org> @genoce:matrix.org: I advocated for skipping the new key hierachy on seraphis-migration/monero #310. I don't know if you guys can read my comment. Since I have a fresh account.

<genoce:matrix.org> I'm neutral now. That might change if I understand the seed extraction attack

<koe000:matrix.org> genoce: I do not see your comment there.

<syntheticbird> God Microslop has decided that genoce did not exist.

<jpk68:matrix.org> Erroneous ban counter: II

<genoce:matrix.org> @koe000:matrix.org: Hahaha. Github seem to hide comments from new accounts.

<genoce:matrix.org> I wrote:

<genoce:matrix.org> mrelay.p2pool.observer/p/-_227fcKUWtmYm9O/1.txt (code snippet, 18 lines)[... more lines follow, see mrelay.p2pool.observer/e/-_227fcKUWtmYm9O ]

<syntheticbird> You need to contact Github support for them to un-shadow-ban you. Warning: they will ask for phone number

<jeffro256> Damn micro$hit

<jeffro256> when librejo work ?

<syntheticbird> buy me time 😭

<jpk68:matrix.org> That's what I'd like to know ;)

<jpk68:matrix.org> theverge.com/news/757461/microsoft-…-resignation-coreai-team-transition

<jeffro256> @genoce Thanks for the donation, it is hugely appreciated.

<jeffro256> > what do you think about simplifying Carrot to just Legacy-Carrot and removing the new key hierarchy? Then you and I pushing hard on Jamtis-PQ once there is a spec (or falling back to Jamtis-Carrot if the forward secrecy effort is deemed intractable). This would alleviate FCMP++ hardfork pressure, avoid excess wallet complexity, and accelerate Jamtis feature inclusion.

<jeffro256> FWIW, the new key hierarchy is NOT integrated in wallet2 in the staging branch, so there's not much to be removed at this moment. I don't think that the codebase's current form holds up the FCMP++ fork whatsoever due to the new key hierarchy features

<jeffro256> Once the FCMP++ fork is through, there is nothing stopping users from using the new key hierarchy over the CARROT protocol, since its addresses are indistinguishable. Whether or not the core repo should have explicit support for it I guess is another issue.

<jeffro256> The new key hierarchy proposed in the CARROT spec, and the JAMTIS key hierarchy can technically be worked on almost completely in parallel. In reality, there will probably only be a couple developers due to labor resource constraints, who will have to context switch b/t developing on either of these projects.

<jeffro256> I'm not quite sure what you mean by Jamtis-Carrot. Could you explain that term, please? I don't doubt that someone has used since there's been a lot of ideas flying around on different compromises and variations of existing specs

<koe000:matrix.org> @jeffro256: You say this a lot about how other wallets could adopt their own key hierarchies. While technically true, in practice it's very unlikely. What matters and is relevant is core dev planning.

<genoce:matrix.org> @jeffro256: I did not say Jamtis-Carrot. it was a quote

<genoce:matrix.org> Next to > are quotes

<koe000:matrix.org> @jeffro256: seraphis-migration/monero #310 perhaps you missed it?

<genoce:matrix.org> This attack can't be done against seeds in the newer software? They are 25 words long instead of 24 right? > <@jeffro256> And any new key material derived as a function of the seed is vulnerable to this attack if using the default legacy software 24 word seed format: gist.github.com/jeffro256/4155401274699e0437ba5b79b93c647f

jeffro256: The privacy issue could probably be mitigated by adding a new symmetric secret for internal view tags. QA won't know it, filter assist will.

"SSSSAAH-BROSKI" is then opt-in by not sharing s_fa with the LWS server.

<jeffro256> > I vote for Legacy-Carrot and skip the new Carrot key hierarchy if that speed up Jamtis-PQ development significantly. If Jeffro really wants to finish the Carrot key hierarchy integration and it does not slow down Jamtis-PQ development too much, I vote for that.

<jeffro256> I think since most of the code for the new Carrot key hierarchy is done, just not integration. I honestly don't think development would take that long, but I could be wrong. What I think would take a much longer time is ecosystem integration (downstream wallet apps, hardware wallets, etc) and pushing out education to users. Yo [... too long, see mrelay.p2pool.observer/e/j-OH7vcKY0VkV0VR ]

<koe000:matrix.org> tevador: I like this idea, no need for seed complexity.

<syntheticbird> tevador: sound sso simple it might work

<jeffro256> ohh that's what Jamtis-Carrot is referring too , my bad i shouldve known that

<jeffro256> @koe000:matrix.org: I do agree, especially since almost every single full wallet Monero application uses wallet2 underneath. I just like pointing it out, since I like your ideas of separating the core codebase from higher level layers like multisig. I believe at some point, the same should be done for addressing protocols

<jeffro256> Extremely long term, I think that we should move to private client side validation. After that, it doesn't make much sense to include addressing protocol code in the core codebase IMO

<jeffro256> tevador: I like this

<vtnerd> @jeffro256: Skylight/lwcli uses lwsf and not use wallet2

<genoce:matrix.org> > <@jeffro256> > I vote for Legacy-Carrot and skip the new Carrot key hierarchy if that speed up Jamtis-PQ development significantly. If Jeffro really wants to finish the Carrot key hierarchy integration and it does not slow down Jamtis-PQ development too much, I vote for that.

<genoce:matrix.org> I'm neutral on this case since the new key hierachy support internal forward secrecy. I did not know that. Many people do churn, so I see the benefits of the new key hierachy as temporary solution. I'm fine with skipping it too because churning to a new private wallet is safe. That's a decision you guys have to decide on

<vtnerd> Ah you said full wallet I guess

<jeffro256> @vtnerd: yes full wallet

<genoce:matrix.org> @genoce:matrix.org: This is the last thing I have to know before I turn into a silent spectator again

<syntheticbird> @genoce:matrix.org: at the risk of being annoying, jeffro256 said he thinks it's safe.

<genoce:matrix.org> A QA can extract the seed from wallet2 addresses or only from legacy wallets?

<genoce:matrix.org> @syntheticbird: Hodl until XMR is $1500

<jeffro256> @genoce:matrix.org: Unfortunately, I think 25 word has the same attack vector. IIRC, 25 word is just 24 word with a slightly different word set, and a checksum, right?

<syntheticbird> must be that. It doesn't having the birthday date so you can eliminate that as a growth factor

<genoce:matrix.org> @jeffro256: Ok so the internal forward secrecy doesn't matter? They can just extract seed by seed?

The 24/25 word seed is just the private key itself, so it can be extracted from an address.

<jeffro256> So the preconditions for the attack are laid out in the gist:

<jeffro256> > 2. The private spend key is the seed

<jeffro256> > 3. The private view key is a hash of solely the private spend key

<jeffro256> > 4. Subaddresses are generated by adding the public spend key to a base point multiplied by a scalar hash of the private view key and a small "index" space[... more lines follow, see mrelay.p2pool.observer/e/r4m87vcKanBDSzl4 ]

<jeffro256> So one wouldn't want to use a hybrid legacy<->new key wallet with an old seed phrase from the default wallet software, because the new wallet keys lose the forward secrecy properties since the old seed is leaked in its entirety. But if using a fresh seed, then the internal forward secrecy property holds.

<jeffro256> All of these weird, hard-to-understand conditions are a good argument for hard seed separation @tevador

<jeffro256> But for example, Ledger and Trezor wallets can have hybrid key hierarchies while maintaining internal forward secrecy because they derive the legacy spend privkey as a hash of the seed. The hash function, being a one-way function, won't leak the input knowing the output. So a QA can determine the spend privkey from the address, but not the seed.

<jeffro256> BIP39-esque seed derivation schemes prevent that sort of thing

<genoce:matrix.org> Ok then I 100% vote for adding the new key hierachy ASAP as temporary solution until Jamtis-PQ is done. Even if it delays Jamtis-PQ and make things a bit more complicated. With the new key hierachy we will have some PQ secrecy. That will also the decrease the pressure on the Jamtis-PQ development. > <@jeffro256> So the preconditions for the attack are laid out in the gist:

<jeffro256> I'd also like to point out that if using 2-way communication, one can have 100% PQ forward secret receives and self-sends without a lick of PQ cryptography, and without ever revealing one's incoming view key to a QA: monero-project/research-lab #106#issuecomment-2143280582

<jeffro256> As you remarked, hopefully with the new carrot ker hierarchy, and with different off-chain mechanisms, we can allow Jamtis-PQ time to finalize without harming PQ secrecy for users too much.

<jeffro256> BTW that above post was made for Jamtis, but the same concept can be applied to the new carrot key hierarchy

I wouldn't recommend doing anything that might delay the FCMP++ fork. Remember that without FCMP++ itself, the transaction graph of all your transactions will be deanonymized regardless of your key hierarchy.

<genoce:matrix.org> tevador: It can be added after the FCMP++ fork. But before Jamtis_PQ

<jeffro256> Agreed, which is why I don't think the new key hierarchy should be a blocker for FCMP++

<jeffro256> Rn, the legacy key hierarchy is PQ forward secret iff the public addresses are not known to a QA. That's the code that is currently running on stressnet

<genoce:matrix.org> Yes. I hope you guys decide to add the new carrot key hierachy ASAP after the FCMP++ fork. Thank you for your time. I will disappear again and keep funding where I can > <@jeffro256> As you remarked, hopefully with the new carrot ker hierarchy, and with different off-chain mechanisms, we can allow Jamtis-PQ time to finalize without harming PQ secrecy for users too much.

<jeffro256> Np I love talking about crypto. Thanks for your contribution