ToorCamp8 2024 - POST QUANTUM CRYPTOGRAPHY: LATTICES, CRYSTALS AND QUBITS – echo

craphy laes crystals ande give her a fr [Music] um yeah I'm going to be talking about postquantum cryptography um thank you all for coming um specifically we're going to start off talking about the history of both Quantum Computing and um postquantum cryptography we're going to talk about what quantum computers even are um we're going to talk about Shore's algorithm which is um okay U I was like is there something back there um okay um is there something that needs my attention um we're going to talk about Shores algorithm which is the the kind of reason that we're have this issue um we can talk about hard problems then the Threat Level that quantum computers pose how we're going to fix those threats and then what the status is currently and then what you can look forward to um in the future um but a bit about me I'm hacker obviously I'm Cipher Punk um ever since I found out that you can um keep secrets with math I've been completely hooked um I've worked as an applied cryptographer um most notably at Cisco Systems on their cryptographic applications team doing um applied cryptography stuff um including post Quantum stuff um but I'm very much on the applied side so I'm not a mathematician and I'm not a physicist um so some of the things the math like the deep math stuff the physics stuff in this presentation I might just have to hand wve about both because it won't fit in this presentation and I don't have that much experience with it um because on the applied side there it's like you know a whole different set of concerns um yeah so the history of quantum computers starts in the 1920s when the double double slit exper experiment found that light is sometimes a wave sometimes a particle and this like broke physics and we're still trying to figure out what the hell is even going on um and physics was kind of grappling with that and then in the 80s um with when like classical computers were getting big um theories started to come out about Quantum Compu Computing or using Quantum phenomena for computing reasons um especially the idea of quantum parallelism you might have heard that quantum computers try every possible solution to a problem at once that's Quantum parallelism um that's not actually how they how it works but it's a good mental model um to conceptualize them um then in 1984 sh's algorithm was released um sh's gthm is a way for quantum computers to factor primes for large numbers um which is how most of our um cryptography today is kind of built around that and we'll talk about most of these things um in more depth in in a little bit um yeah so Shores algorithm came out 19 in '94 it was pretty much immediately recognized as a threat to cryptography so in '96 um lattice cryptography was introduced and then in 98 we had a um a full um public key encryption system based on lates um a survey in 2001 found that most cryptographers were aware of Shore's algorithm as a threat um and agreed that we needed to address this um and then um work on postquantum cryptography continued and grew U mostly in the academic world um by 2006 we had the first postquantum cryptography conference um then jumping to 2016 um the open Quantum safe project started this is a um project to do the actual code implementation um and then the nist U postquantum cryptography competition started this is a competition to select which algorithms um that nist thinks is um good enough for the federal government to use um in 2017 those um submissions were due um then in 20123 just last year um signal released their postquantum cryptography update um and then this year we've been seeing more and more um releases of postquantum cryptography into like production environments um and then by the end of this year the nist competition will be complete and we actually have standards um that nist approves of so what even are quantum computers they're a computer that uses um Quantum phenomena to do computation so instead of using electricity and transistors you're using um entanglement and wave collapse and stuff um they're probabilistic so like nominally um classical computerss are deterministic it's like sometimes they're not but um but quantum computers are probabilistic like all the time so there will you'll run a program and it'll say this is probably the right answer but you need to go check um to make sure that it's right so often a quantum computer will be paired with a fast classical computer and the classical computer will do the control stuff in the io and also check the answers um physically quantum computers are like these steampunk like stag ties um that are really cool they operate at 15 Melvin so that's a fraction of a degree above absolute zero there's like a whole branch of hacking physics um just to get things this cold um and on so this is a picture of the quantum computer and this little gray square is the um is the actual chip and the rest of the wires and stuff are either IO or Cooling and you'll see there's like several different tiers um which is mainly due to cooling where each tier gets colder which is pretty cool um quantum computers use cubits so in regular In classical computers we have bits that use um that do that are just one or zero um in Quantum Crypt in quantum computers we have cubits which are kind of one and zero um you don't really know until you observe them what they are and there's a probability curve that you can set um and then there's the quantum Gates which work similarly to logic gates and that you can um use them to connect the cubits and um um yeah do logic with them um and it's all probabilistic so you program them with wave interference so you'll this is part of the stuff that I only kind of understand um but the different cubits you will connect in certain with the gates um such that they're linked prob probability wise um and so to program them it's reminds me a lot more of like prologue or um more like declarative programming paradigms where it's you're describing an entire system that will um eventually like will give you the answer rather than with classical programming and your um where you're like writing code that is executing qu entially like step by step um let me check this sorry um okay um sorry um quum computers are very susceptible to decoherence and noise decoherence is where the cubits become unlined to each other um which is kind of like your program breaking down um so they're very that's one of the reasons why they're they operate at 15 Melvin is to prevent um the noise because of physics reasons um and then there's Quantum Advantage which is a state where we consider that a quantum computer is better at a given task than a classical computer um just last year I think we um Quant Advantage was um achieved with the caveat that the the problem that they had it do was specifically made for that computer to be better than classical computers at so it's a kind of contrived um at this point at least um system where they're like we can do this problem better than a classical computer but we also made this problem specifically for this Quantum Advantage proof um but yeah um in this yeah um it's more the question was if quantum Advantage is measured by like efficiency in like watts per dollar it's more theoretical than that of it's like the like you know um it's more like they'll do an analysis on the problem and be like oh this is like o of N squared or whatever and they can prove that the theoretical um that their computer can do it faster than any theoretical classical computer um with their analysis um yeah so in this presentation I don't want to get the impression that I'm anti- quantum computer like I'm a hacker you show me a weird computer I'm going to be a fan that's just how it works and there's a lot of cool uses for them um that I wanted to highlight especially they're really good at modeling Quantum phenomena because they are quantum they can just do that um they can also solve the traveling salesman problem like really quickly which can be useful for a lot of things um they're also useful for um simulation of physics especially like some applications could be protein folding and also Material Science which could really benefit from using quantum computers so they're not all bad I just don't want them breaking cryptography um yeah so shes algorithm is the kind of reason that this that quantum computers can break cryptography um it's a way to make prime factorization easier which I said before um so you have like a number and then to get the primes that multiply to make that number is very hard to do for a classical computer but much easier to do for a quantum computer and the problem is that this factorization problem is how we um have built a lot of modern cryptography systems um which we'll talk a little bit or in a bit more depth a bit later um but the hard problems that Compton that shes algorithm can break our integer factorization which RSA uses um and then also because math it can also break the discret log problem which is what Diffy Helman uses and the elliptic curve discret log um which is what elliptic curve cryptography uses um so sh's algorithm works by you um you make a guess about what one of the primes is so you say tell the quantum computer I want to factor this number and I think this is one of the primes and you're probably wrong almost certainly wrong but then you run chores algorithm and then the quantum computer will give you a better guess and you can do that continuously until you get the actual uh results so it is still brute forcing you're still checking a bunch of things um a lot of people imply that it's like an instantaneous thing um it's it's not it's just a lot faster um to do the factorization to beat RSA 2048 with a classical computer we often talk about like computers the size of the physical Universe running for the entire length that the univers has existed existed probably not being able to break it um a big enough quantum computer could break it in like a day or less um I mentioned hard problems these are um the kind of mathematical building blocks that we build cryptographic systems out of they're easy to do one way hard to do the other way I talked about prime factorization so it's very easy to do 461 time 991 and getting 45685 most people could do that just like with a piece of paper and a pen it might take a bit but you could do that computers can do it pretty much immediately um but going the other way if I gave you 456,000 851 and asked you to find find the primes that takes a long time and you have to check each one um and like I said we build cryptographic systems with these and how we're going to oh yeah um in cryptography there's a concept called cryptographic agility which is kind of a design principle that your cryptographic system should be able to um swap out hard problems when needed um and if you're if you've used um TLS you'll see you might know of the um TLS Cipher Suite um tags this is essentially cryptographic agility where you can just swap out from RSA to elliptic curve depending like if both systems support it and stuff um but this is how we're going to fix or protect against Shores algorithm is swapping out hard problems for new ones so in a couple years we might see TLS Cipher Suite tags with postquantum stuff in them okay so there's been a lot of Fairly dramatic articles and videos and stuff about postquantum or about Quantum so like how bad is it this one says no secret is safe how quantum computers break the internet starting now or quantum computers destroy Internet Security and my favorite um Google's quantum computer finally turned on and what scientists discovered as terrifying so they are a serious threat um we do like act need to fix this um but it's not as bad as a lot of people imply or say like a lot of them imply that it's they can instantaneously break it or that um that if you get a big enough quantum computer then all of the internet is like immediately clear text um it's not that bad we still need to fix it though um but it's um yeah I don't really like those like very dramatic claims um the nice thing is that a lot of work has already been done um like we talked about in the History Section um Shore's algorithm was released two years later we had postquantum cryptography specifically to um to protect against Shores algorithm and that work has been going since the 90s um also symmetric systems aren't vulnerable um in cryptography we have asymmetric and symmetric systems where um symmetric systems only use one key and they are not vulnerable to quantum computers especially like AES is still safe um Quantum attacks are probably not possible today given our level of um of sophistication with our most advanced um quantum computers um yeah they're probably it's definitely infusible now it might not be feasible ever um it's always dangerous to say to speculate about new technology and saying that this will not happen but there's reason for some skepticism um I talked about the decoherence and noise where um your cubits will um become disconnected and out of sync with each other or they'll just like have errors um and and that's a thing to deal with um and you need over 6,000 cubits to break RSA 2048 the biggest Quantum Cubit we have is just over 1,000 cubits and the um the rate at which we're adding cubits hasn't been following Mo's law at least that I've seen um because the more cubits you put on a chip the more decco appearance and the more noise you have so scaling them at least now is very difficult um there might be some new paradigm shifts that make it super easy um and like we need to protect against it but it's there's some reason for skepticism um I don't know if you can see this chart but on the left hand side we have a bunch of ciphers and then in the middle column it says the minimum number of cubits you need to break that uh Cipher so for RSA 248 we need 6,190 cubits um for ecdsa an elliptic curve system um five for 512 you need 5,273 cubits um and then that's the minimum number that you need the rightmost column is kind of a weird unit of Mega Cubit days but that means the number of cubits you would need to run for one day to break that key so to break a single RSA 2048 key in 24 hours you'd need 1.17 million cubits running continuously for that day um to break ecdsa 512 you need 15.6 million and we're current h yeah I I don't know the math but yeah it it' still take a while yeah as the length of increases does theost to get higher or is it like Is it feasible to make it very annoying um yes that's one of the approaches you could use um the downside of that is with longer Keys the operations take longer so you get performance penalties um and it's it's probably better to just swap out entirely for something that's totally safe um yeah IBM Condor is the current biggest quantum computer with 1,200 1,121 cubits um there might be classified computers that are bigger than this I have to assume that the NSA and every other intelligence agency in the world is scrambling for this um so there might be bigger ones now and also there might be bigger ones in the future um that we have to protect against now because there is a attack called Harvest now and decrypts later which is where the NSA or whoever can intercept your data and if it's encrypted they just store it and just wait until they have a computer that's big enough to break it um and and so we have to protect against all future possible computers and how we're doing that um like I said is with postquantum cryptography which is a suite of new algorithms and new hard problems um that are not vulnerable to attacks that we can just swap out um like I said there's been academic work since the 90s more recently we've been getting actual code um implementations um the standards are being finalized and we're yeah implementing the code in in parallel and also in this um in this kind of in between period a lot of the implementations I've seen have been hybrid systems so it's like with the signal implementation is um it uses the regular signal double ratchet stuff and also a postquantum system that that way an attack would have to break both of them in order to decrypt it um but they are separate so that if um if this specific implementation or hard problem that they've um implemented is broken in the future they can swap that out fairly easy um so there's that's a thing that is happening is these hybrid systems um nist or the National Institute of Science and techn no National Institute of Standards and technology is a US Government um entity that does standards um and they have been doing a a competition for postquantum cryptography so you can submit your algorithms it goes through lots of review steps and then at the end Mist will choose several of them and say these are what we consider to be good enough for the US federal government and Military and intelligence and stuff to use um but that carries with a with it a lot of weight so a lot of it kind of becomes the de facto standard for everyone um the postquantum competition started in 2016 um there were 23 signatures and 59 um encryption systems that were submitted um it's going to be finishing up by the end of this year so we'll have the standards um there have been some intellectual property issues where some of the um some of the algorithms have been patented but in order to submit you have to sign documents that say if your algorithm is um is chosen the patent is essentially void like it's still there on record but it's not enforcable in any way um so but it might be an issue um there also hasn't been any indication of interference um nist has done several um competitions for different um cryptography systems and in a previous one there was indications that the NSA had influenced it and influenced the how they picked um some of the constant in order to weaken the weaken the um yeah weaken the systems um they like we found out about it missed lot a lot of lost a lot of um like respect and so that they've been a lot more or from what I've seen they've been a lot more above board um this time in terms of how and where the contributions are coming from and from what I've seen there hasn't been any indication of any sort of interference um one of the main um submitters I guess to the postquantum cryptography competition is called the crystals lab which is kind of sort of an acronym for the C cryptographic suite for algebraic luses um this is a lab of academics from all over the world who um have been working together on this for a while and they're very Pro lattice um um pratus cryptography that's their thing they're many of them invented a lot of it um and so they're very all on board with that and they've submitted kyber and dilithium which are their names for the algorithms that they've submitted and I guess they didn't want to wade into the Star Wars versus Star Trek fandom Wars so they chose to name their algorithms one of each to keep everybody happy um um yeah kyber is their key encapsulation mechanism um a key encapsulation mechanism is similar to encryption but it's a hybrid of public private key encryption and symmetric encryptions so with this you'll be for your message you'll have a um one key that is that uses to encrypt and decrypt it and then you'll use kyber to encrypt that AES that key that encrypts your message um so kyber doesn't on its own encrypt your whole message it it encrypts the AES key that encrypted your message um we do this for performance reasons mostly um and kyber does have some performance issues um compared to elliptic curve Diffy Helman um which is like its equivalent um system that we currently have it's 2.3 times slower and there's 70 times more data overhead so more RAM usage um but it's important to know that there aren't there isn't any hardware acceleration for it yet there is Hardware acceleration for elliptic curve and RSA stuff so um in a couple years when we have Hardware accelerated kyber it will probably be a lot faster um and then dilithium is their signature scheme um also using lotuses um it does have a large key in signature size um the keys are over a kilobyte and this each signature is 2.5 kilobytes whereas RSA signatures are just 256 bytes Um this can be an issue especially for like TLS and like internet stuff when a regular um TLS handshake requires like six signatures and two public Keys per p age um and if you're talking 2.5 kiloby versus 256 bytes that's a huge increase um in size and some research by Cloud flare found that it might double this the time it takes to do a TLS handr um but this is kind of the um where we are it's like it's very new technology for in the like actual real world implementations so I'm sure with um with Hardware acceleration and more optimization we will um get this down make it faster um another signature scheme that might be um chosen is called Falcon and it's based on the ntru luses which is ntru is the system that was made back in 1998 so it's like the OG post crypto stuff um and it might end up being chosen n can choose or can select several signature schemes and they say that these are both um valid for us to use um they don't have to just pick one um Falcon uses smaller Keys um which is nice but it's the signing speed is slower than dilithium because the main sticking point is that it requires double Precision floating Point math port to be done in constant time so you need to be able to do 1 + one in the same amount of time it takes you to do very large numbers with very large decimals times other very large numbers with very large decimals yeah um all cryptographic math has to be constant time to prevent timing attacks yeah um and no CPU currently has double Precision floating Point constant time math support um they do have implementations in software but it only works on like specific CPUs and it only kind of works because they're like kind of hacking it um which is great but not maybe not great for production cryptography stuff um but maybe in a couple years if maybe the um the downsides of dilithium are big enough that people do add these um Hardware support to their CPUs and then we'll go with Falcon it's yet to be seen um for the actual code s side of things there's the open Quantum safe project um this is part of the Linux Foundation is like funded by them they are writing um a system called lib oqs which is open- Source reference implementations of these algorithms in C um they started in started implementing in 2016 which is like way before the nist um things so they have they have implementations of many many many different postquantum um algorithms um including the ones that nist are going to choose which is kyber delium and Falcon um they've also been doing prototype Integrations with OP SSL and open SSH and some other things so in a couple years when we're all using postquantum stuff like if you go down enough levels it it'll probably be Lio Qs at the bottom somewhere um so yeah like I said there's the nist standardization is going to be wrapping up this year we'll get what nist appr proves of um code implementation and deployment is happening in parallel and what you need to actually do um depends on who you are and what you do um if you're in infos SEC you should know that this is happening you're probably going to have to implement this at some point I would not be surprised if um in a year or two we'll get um postquantum requirements in like your um like compliance requirements like sock 2 or PCI um if you're an early adopter if you just like this stuff you can play around with it with it being like in this transition from the academic world to the everywhere else World um there's a lot of cool stuff going on that you can play around with and if you're doing things that an intelligence agency would find interesting um you need to be very careful and take this seriously because of the um Harvest now decrypt later um attack that I mentioned before boring yes um also there's Quantum cryptography which is kind of the other other side of all of this where you can use the quantum effects to make cpog graphic systems um Hardware Hardware random number generators can use quantum effects and and pretty much all of them do at some level a lot of times the there will be other effects that are like the main source of entropy but Quantum is in there somewhere um there's also Quantum key distribution which is very like it's fairly academic still but there's um thoughts of Distributing Keys via um quantum entanglement which would be super cool um but yeah that's I think no so in summary um quantum computers run sh's algorithm which can make factoring prime numbers easier um which is a threat to Current public key cryptography systems it's probably not currently pH feasible to do a Quantum attack um but Harvest now decrypt later is a threat you have to work out for um the standardization and updates are coming soon and cryptographers are Vigilant and diligent and to wrap up with a um personal plug you can hire me um I'm currently looking for a job you can hire me to do postquantum stuff regular crypto applied cryptography stuff backend software stuff I'll leave my email up there or you can just talk to me when you see me around so do you have any questions yeah R sorry how big of an try how big of an RSA key can um the current like 1100 Cubit thing crack and how long does it take um I'm not sure specifically I think it's like very small like I think I saw it was like 128 bits or something like not something that anyone would like actually used for security at this point um and it would probably take a while like most of the actual um like Quantum programs that are run these days that I've seen are more like helping with the research of the computer like especially testing for error rates and error correction and testing for decoherence and stuff like that um so yeah yeah testing okay uh I I feel like I saw some news articles maybe like a couple years ago that um there and I'm I'm wondering if you know any more details about this but there's some like Chinese satellites doing some Quantum key distribution something or other like was that actually a thing or like how like what was that yeah that's the um the key distribution that I was talking about where you can in send keys via um quantum entanglement and that has there have been several satellites um that have done that they do them on satellites because it's I believe the reason is because it's more shielded um there's less interference I saw some attacks on that like way early on that like because of the redundancy like a lot of times they'll do like error correction and stuff and then because of the error correction then you can like slice out the bits and then it's still like without disturbing without it looking like the quantum key distribution is broken or something like I don't know yeah I'm was curious how serious the key distribution is or if that was just like a purely academic test or if that it's like actually like a real thing that that's like um actually happening as far as I know it's still very academic and early early in the life cycle I guess of that technology so I would assume that it gets broken all the time because all cryptography gets broken all the time when it's just getting when it's just starting out um but yeah it's it's really cool though yeah I've been to other talks about Quantum cryptography and I'm interested be in hearing your response to someone from the industry who I don't know if I particularly would call him a Salesman or not but they were arguing that it's a key this is fundamentally a key doubling problem with AES and that or RSA technically that in that if you doubling key strength to from 20 48 standards to 4096 or something would fundamentally solve this problem I don't know if I entirely believe that person but I'm interested to hear how you would respond to that yeah it's um you could do that but then like you're just kind of delaying the problem where like yeah like if you like we double it and then in a couple years we have a paradigm shift and we can make really big quantum computers and then we're here again so it's um yeah I think it'd be better to swap out for lates or other things uh yeah so um you mentioned that quantum computers can solve the traveling salesman problem which is in hard um Can it solve all instances of it or just some with like certain kinds of structures um I'm not really sure sorry about that CU I I would think that would break all cryptog graphy including postquantum yeah I'm I'm not sure about that side of things um yeah I know the mathematicians who do the math stuff have proven that lses are not vulnerable um because they're entirely different they're yeah hello oh hello all right this isn't more of a question but this is more of some answers I think um because like I've looked into some of this stuff too so like if you go from a 20 48 bit RSA to 4096 um it doesn't like double the time it takes to like crack it um it's like super linear so like the more time like it's not going to like double it's going to it's going to go up by some by some Factor that's that's more than like you know twice um so that does push it away but the problem is that like 40 90 bit RSA really sucks for like efficiency um and you start getting into crazy numbers where like eventually um the what you're going to get is like you know RSA 8192 um which is just like on the order of seconds so it's it's just not worth it um also like the in 2010 um researchers were able to crack RSA uh 768 um so that was 2010 I think that's the current record and that was done with the classical computer so hypothetically um like the next the next step is probably RSA uh 1024 we uh in general we should be using like RSA 4096 just because there speculation at the NSA can has the computational power slash their army of mathematicians and and be able to to do something you know um better than our current research um they've been known for example with Log Jam to be ahead of the curve by you know maybe 10 15 years in terms of like what our research is um and log Jam is kind of like the it's kind of like the something that we had to deal with before where um they had uh we used to use the same primes for all our Diffy helmet um and it ends up that you could just solve the problem once and then apply it to everybody's connection um so we've since moved on to everybody generates uh random safe primes themselves uh to prevent them from to force them to do more work per connection and do targeted attacks um so that's just some history on on the current developments that we've been between um uh postquantum and also how the NSA is is handling us yeah my understanding is that when the NSA did their um their interference with nist my understanding is that we still don't really know what was going on there so who knows what their capabilities are um behind the scenes H yeah yeah do you know if we know what that was about or like so they they back doored appear appear and that they inserted into standardize it and they paid rsa's vice president they paid rsa's vice president $10 million um I think he's missing by the way uh they they paid him $10 million uh to uh standardize it in RSA Securities Library like the people who made RSA made a company and their security company who's no longer ran by RSA by the way um they um they actually put the Dual EC drbg into um their library and made it the default so everybody's like connections were using it if you were using their library and B basically um there was a constant it used two um eliptic curve points and because um they're using nist p256 which is a prime order curve there is um provably a connection be uh a a constant between the two curve points that if you knew it you could actually reverse the P andng um and so it became this really like quote subtle but somebody was like Hey wouldn't this be breakable if somebody knew what this number was um and when wiy Wikileaks came out um they both a found out that um the RSA vice president was paid which there was speculation on and B um they did find out that in NSI do NSA documents their actually was they knew this constant even though they said oh no we threw it away which is like yeah I randomly generated this and threw it away trust me is like the worst argument of security I've heard yeah um especially involving the NSA um so I think I think that's what we're probably talking about yeah any others yeah so with with a lot of the um postquantum schemes in the nist competition something I've noticed is the key sizes are really big I remember reading that when Facebook was triing a hybrid with kyber for TLS they bump down to a lower security level than recommended because they couldn't fit it inside an IP packet uh are we just going to have to accept that everything is going to be really massive and terrible or are there any advancements in smaller schemes on the future um yeah that's definitely an issue um and we we kind like we kind of have to deal with it but also like we're kind of just barely starting the transition from like academic Theory work to actual practical stuff so I'm assuming there will be a lot of um a lot of optimizations for that um I'm not sure how that will go yet because I don't think anyone is but yeah that's definitely something um that everyone's looking at is the um yeah and like Long Key sizes isn't something you can really use a hardware accelerator for because it's like that's just data you have to transfer but yeah so it's anything else yeah um yeah I I was trying to record it but I realized halfway through that I didn't actually click it so I'm hoping I can refer people to their uh recording too but yeah well if that's it uh thank you for coming and listening [Applause] [Music]