WebAuthn Optimization: optimizing ECC sec256r1

Transcript

[Music] Innovation team and today we're going to talk about uh cryptographic uh elliptical cryptography optimization for the term account abstraction so I work at a ledger Innovation team uh or Mantra or self-custody user experience and security or a short team of six person Gathering whole skills alvare software cryptography hello that's me uh and you may wonder why should I under this talk because I had Mass so don't

panic I will do through this so you can speak about it later so second part of the talk is a contraction it brings a way to implement your own cryptography so this is the peak of self custody it could be used to to improve user experience for instance using passkeys we're going to talk about this later and this requires sorry for your list to uh to implement yourself your security your your cryptography so you have to uh to optimize to optimize this because this is very uh gas expensive so this is the plan the plan of the talk okay so uh I'm gonna be really short

about the accountab section but because I'm sure that uh you're gonna hear a lot about it during uh during this week but mainly uh what interests uh us for for this talk is that many uh basically account abstraction enables you to to choose any cryptographic algorithm as as a your signing algorithm so cynos will be a arbitrary logic so for instance if you're a religion is that you cannot use a curve with a null discriminant you can switch to another one okay so this one you don't care so what uh but in fact it means that all uh all uh the problems that we Face uh uh are solve many user experience

governance past consume resistance programs such as inner inheritance and even a mix makes the coffee so let's give some some use cases so the fact that the signer May implements any signing protocol can be used to simplify the ux there are different Frameworks uh aiming at implementing weberton so Weber 10 Alias Fido is the the crypto that is used when you use your touch ID face ID implementing the secure Enclave of your phone so it's our different framework from Bravo's cartridge uh abuse Argent

and of course Ledger legendary innovation uh you can you can solve governance Problem by implementing multi-party competition protocols such as Music 2 protocol which is used to to perform for instance lightning or if you want to to have a threshold threshold management of your security without implying the need of a trusted HSM so implementing consume resistance for example use the Falcon algorithm signature inheritage it can okay basically you all those use case are enabled by a concept section

but for the coffee highlight get it yourself okay so now just a brief about passkeys so passkeys is is a way to have a streamlined signing without passwords because handling password is a is a pain okay we all have this see the uh and this beep to to manage all those worlds to to keep somewhere uh there's there are some attempts to uh to uh to manage it that could be discussed but uh okay using uh uses baskets could be a way to empower the user by simply okay uh making uh something really familiar as uh okay uh you make your your face ID

you have a you have your password which is used as your secret key uh for uh for your signing uh signing mechanism so this is the easiest possible crypto onboarding from a mobile web browsers and actually the keys are stored in the host secure Enclave which is really good it provides a phishing resistance mechanism it's still malware prone because we don't have a secure screen on a uh on her mobiles that's uh that's uh that's a very good start and at Ledger her ID is to text to Two Rivers away with that we are usually working to onboard first using a

very easy user experience and maybe straighten later when the stakes are worthy um and then convince the user to add a hardware wallet to to his security perimeter to have the anti-malware feature that you have with a hardware wallet okay so to do this we want to implement a web button but Weber 10 requires to perform non-native elliptic curve computations and from what what we found when we begin to to work on it it was like 30 hundredths time more expensive in Cairo or solidity than using a native

Native computation uh so mainly this would kill all the benefits that we could have using uh using layer 2 to have such a such a huge huge Factor okay so from here there are two solutions so the easy way would be to just introduce a new pre-compile and there are the ways to optimize things a bit and as I need to work that's a the that's what we will talk uh we'll talk now so implementing such a such mechanism in uh you know smart contract language is a bit different than from what we we do

usually uh when uh implementing cryptography mean these are very exact feature in solidity for example modular multiplication and addition of the same cost memory cost model also are very specific and we have less available implementation of all those mechanisms okay so let's uh let's dip a bit into detail now so mainly uh what you need to know about the elliptic curve cryptography you just need two operation addition okay and a multiple multiply the point by by a scalar uh uh that's it so like the person you have on the vector vectoral

space many the the Keystone of all elliptic curve cryptography is point multiplication because multiplying a point is easy but extracting the scalar from the knowledge of the results which is known as the elliptic curve discrete logarithm is uh intractable uh and this operation is what you use when you derivate your private key uh uh to to to your public one it's a multiplication and when you verify your signature you perform a double multiplication and addition which we will refer as okay and this is very expensive and this is a 98 of uh

cryptographic protocol uh in average so first we perform a systematic bench of uh the solidity implementations as they were in the wild you have the result here so for instance Ops Network I think that's the one maybe upclave used when they claim there are one million uh one million gas gas costs there are more efficient implementations actually the best one is from abuse of your stake and Alan big introduced uh introduce your ID to use to use pre-competition to speed up to speed up things uh

uh so we did so we use a lot a lot of tricks first we revisit all coordinate systems as said before it's unusual to have multiplication and addition having the same cost so it's not a usual especially jacobians that were the the most efficient so we we used another one so we had again here we use the multibase expenditure session so a seminality is known as xiaomi streak it's a very classic one it's used in openssl and all classic cryptographic Library it's a way to uh to have a development application for the cost of one and what we did is we extended to

eight precontributed bases splitting each each of the input p and Q into four four values uh leading to a 16 kilobytes of meditation to uh to again forecast to 75 percent but in reality as memory access are expensive we also had to optimize this so basically there is a cold and warm access cost when using a a storage load or xcode copy so xcode copy is the classic trick and there is okay non-contract to uh to to

use it to to to to improve to improve the cost and actually what we did we we really use this ID to to use Cut Copy instead by over writing for each for each User it's publicly into into the Contour enabling the fact to use code copy instead of xcode copy and several other tricks so implementing everything in assembly okay in lining because the compiler was not so good and so on and finally we reached five uh five time faster uh implementation that's the best best previous one so here are our results there are uh

here two uh to propose the implementation with suit pre-computation we reached 200 uh kilos gas and with pre-competation 60 uh 61. so we think that with these numbers uh signing is as expensive as a single mint uh and maybe there is no need for for pre-compile and also by analyzing the other Library we found some some vulnerabilities so this also highlights the point that okay a current abstraction will introduce the possibility to change your crypto but you have to be very careful because it is really easy to to make mistakes and

mistakes lead to could lead to a fatal uh the Fatal vulnerability for instance before or Pierre it was possible to uh to still hold uh all currencies from a abuse Tech implementation so to wrap up things we achieved a five-time cheaper gas cost uh we assisted thematically a bench and review all a solid decoder we found we made some PR on Bravo so this is Cairo implementation and there are also technical details on a paper which is available available on the on the eprints and you will have okay it's a link later

and as for the worker we still are working on further trade-off from the 30 to 30 million first diploma in cost to uh to zero there are we we aim at benching and this work on different layer tools and we are also working on NPC implementations so here is a link to the pepper it is also linked to to the GitHub to the GitHub repo and if you have any question foreign thank you do you think this also applied

to things like Patterson hashes uh yes yes of course thanks yeah that's simply you just have to split uh to split the the Four Points each into into two and you can use a multi-baser Expedition as well sure thanks could you please also explain what what is the precompute station that you did on your implementation the 3.2 megabytes or yep I I would advise you to to go into the paper because you will have all the formulas but mainly the height is here is that uh in fact instead of splitting uh uh as as a as a window what you can do

is for instance so the two points the the public generating point of the elliptic curve on the public key you can split it into a uh and this way instead of having just two points in your in Shamir you you can have eight so it's like cutting it's not only using uh one scan of the full size of the operand it's a fourth of this of the length of the operand that is that is performed because uh using on your on unalondic Europe like that okay there is scanning of a 250 here six bits in only

one Loop okay this is a classic Champion uh using uh eight bases you can do it uh by scanning only uh 64 or 64. 64 bits okay this is a 64 meter Loop so the asymptotic complexity is cut by four someone want to ask another question okay it's okay um thank you Reno and now I will let you enjoy a little break before the next conference thank you very much [Applause] [Music]

thank you [Music]