The Security Margin in Cryptography

One of the reasons elliptic curves are so popular is that they get us closer to being able to achieve security that is equivalent to 256 bits, but with much faster computation times. An elliptic curve of 256 bits is going to be roughly equivalent to security of 128 bits as it relates to RSA keys. This is significant because RSA keys require a lot more computational power than elliptic curves do.

The length of the key in terms of bits is no longer the determining factor for security. Instead, it's about how many operations are required to brute force through and guess or work out what's going on. So, how good is 128-bit or 192 or 256-bit security? Two to the power of 128 bits is beyond any computer on earth that exists. It's also worth noting that if a quantum computer existed that could break AES using Grover's algorithm, you're looking at a problem. The same issue arises with RSA keys as well.

Grover's algorithm takes this hypothetical scenario from two to 128 bits to just two to the power of 64. This is not ideal because it means that 256-bit security is now within reach for a quantum computer. On the other hand, symmetric encryption like AES is very resistant to quantum computers because all it does is halve the key space. We can simply double the key space right? However, this is not a problem because two to the power of 128 bits is still beyond any current computer.

The main concern with public-key cryptography like this 3000-bit RSA key for example is that Shaw's algorithm will make it as trivial on a quantum computer as just encrypting using RSA would be on a regular computer. This is not what you want right? So, if a giant quantum computer appears that can halve this problem, the same quantum computer could theoretically completely destroy RSA encryption.

There are however cryptographers and mathematicians looking to create quantum-resistant versions of public-key algorithms, and some have already been developed. The chances are by the time such a machine exists, we won't be using these because of the inherent weakness right? However, it's worth noting that even if it is possible for a quantum computer to factor anywhere close to a 3000-bit number, it's not going to happen tomorrow.

Long-term Security and AES

The good news from our point of view is that we're still going to get two to the power of 128 bits of security from AES256. This means that we can use it for long-term security without worrying about the potential impact of quantum computers. For example, if you encrypt your credit card details and send them off to an online shop, it's honestly zero interest to you if the credit card will have expired in two years. The concern should be with top-secret documents that need to last for over 30 years.

In reality, most websites use 128-bit as banks and stuff are using 256. There is no real reason not to use 256 right now, it's just not necessary. However, there is a good argument to be made for why we should all be doing this anyway. The idea is that these qubits can interact with each other and every time we add a qubit, if we were to add another one here let's say we added this fourth qubit right here, notice that every single one of them can now interact with it and we have to draw lots of lines.

"WEBVTTKind: captionsLanguage: entoday we're going to ask a question when is 128 bits of encryption 128 bits of encryption what does that mean is that good right you know will a quantum computer affect this it was only a few years ago it used to say military grade i mean we're all using military grade encryption very much so um if you're using 256 bit as it's slightly more military than than 128 but if you're using 128 don't feel bad you're still doing absolutely fine on a very very simple level for a symmetric cipher that is a cipher where um we use the same key for both encryption and decryption so we're not talking about public key right now what we usually mean when we say 128 bit is the length of the key we don't tend to talk about block size particularly so 128 bit as is aes with 128 bit key you also have 192 and 256 bit variants of aes they have the same block size but the key gets longer right have a number of rounds changes the reason we talk about the key length particularly is because if the cipher is good the key is a bit you don't know the key is a bit you're going to have to guess so for a 128-bit block cipher you might have to brute force through two to the power of 128 different keys that's a lot of keys you might get lucky you might get it halfway through in which case it's two to 127 but either way it's not a picnic like that is years and years and years of work right much too much work even for the world's fastest supercomputer because 2 to 128 is a lot bigger than you think right this only gets harder if we make these keys bigger so 2 to 192 operations or 2 to the 256 which is a number so unimaginably large that let's just not even worry about it if your encryption is using a key that's two to 256 long and there isn't another issue with your cipher right so that the security base is based entirely on the key then that is not brute forceable in in any sense within the next 10 years within the next 30 years it's good for us if that is the case so which of these should we use well i mean intuitively 256 bit right but actually 128 bit is currently out of reach of any attacks but it's always slightly more complicated than this what we also talk about is maybe the security of an algorithm itself maybe there's something in the algorithm that isn't quite as secure as the key itself so maybe it wouldn't take two to 128 operations to solve it let's say i've written a cipher that's got 128-bit key it may not have 128 bits of security which is to say it would take this many operations to solve and that way because my cypher is not very good maybe it doesn't mix up things enough or it doesn't permute enough i don't know i designed it it's not going to be very good so you might find that an attack or a break on something like aes what it's doing is not telling me how to solve that problem it's just reducing this number so maybe there's an attack on aes but brings it from 228 down to two to 125 or something like that now that is many times faster than that but still totally out of reach right so that is what i would call an academic break which is to say um we've technically found a weakness in the underlying argument algorithm but it's not a weakness that affects me in my everyday life which arguably is what i care about most so we want to distinguish between the bit length of the key so when we say we've got 128-bit aes we're referring to the key but actually the level of security could be slightly lower depending on the algorithm i mean to use a really obvious example let's imagine i have an algorithm that just depends the key to the message doesn't do any encryption at all right that has a security of zero bits right because it doesn't encrypt anything but it does have a nice 128 bit key for what it's worth right not a very good example you get the idea if you've got some fundamental weaknesses in your cipher it's not going to take a full brute force to do it brute force is the absolute worst case for an attacker now this is slightly more confusing for public key cryptography so things like rsa and diffie-hellman right because they tend to have much much bigger keys so a typical diffie-hellman or rsa key is going to be somewhere between 2048 3072 or 4096 bits these are your common sizes now to factor and solve the rsa problem for a 3000 bit key it's roughly the same as brute forcing 128-bit good symmetric cipher right so those numbers are obviously not even close to the same so the security margin in some sense of these is lower for a given key length one of the reasons that elliptic curves are so popular is they get us a little bit closer from here to here so an elliptic curve of 256 bits is going to be roughly equivalent to security of 128 bit as or 3072-bit rsa now that's going to be quite a lot faster to compute so it's no longer about the length of the key in terms of bits it's about how many bits of security are we going to get and that means essentially two to the how many operations are we going to have to brute force through to guess or work out what's going on so how good is 128 bit or 192 or 256 bit and their equivalence well two to 128 bits is beyond any computer on earth that exists but what you know it's the obvious question all the comments i know it's coming it's coming what about the new advent of quantum computing quantum computing right so one thing that's meant to make really clear about quantum computers is they are not simply a very fast regular computer you don't just run aes on a quantum computer much faster than you would do on a normal computer right and make your life easier you have specific algorithms that do specific jobs and the algorithm that makes breaking aes easier is called grover's algorithm it takes this hypothetically from two to 128 to 2 to the 64. now 264 is within reach so if a quantum computer exists that can break aes using grover's algorithm you're going to go from 128-bit security to 64-bit security that is a problem right if you go from 256-bit security to 2-128 that's less of a problem because i already just said that was beyond reach of any computer right so symmetric is very resistant to quantum computers because all it does is halves the key space and we can just double the key space right does this quantum computer exist no will it exist soon not for at least 20 25 years is what robert told me when we asked it i mean i have no idea i don't develop these computers but certainly not anytime soon so public key cryptography like this 3000 bit rsa key for example that is much more affected by quantum computers shaw's algorithm will basically make this as trivial on a quantum computer as just encrypting using rsa would be on a regular computer that's not what you want right so if a giant quantum computer appears that can halve this problem that same quantum computer could theoretically completely destroy rsa encryption and then we're falling back on password-based key derivation functions and symmetric encryption right that would be the first thing but there are cryptographers and mathematicians looking to create quantum resistant versions of public key algorithms of which some have been developed right so the chances are by the time such a machine exists we won't be using these because of the fact that they have this inherent weakness right but i mean to be clear the they have not factored anywhere close to a 3000 bit number with a quantum computer yet right there's questions about whether that's possible because of just the scale of the thing but even if it is it's not going to happen tomorrow right i mean it would be quite amusing if it did and my video is panned as being probably out of date a day after release but this isn't going to happen anytime soon but the good news from our point of view is we're still going to get 2 to 128 bits of security from aes256 which is why that's what's recommended for sort of long term security for sort of 30 plus years right let's say i'm encrypting my credit card details and sending them off to an online shop that credit card will have expired in two years so it is a honestly zero interest to me if you break my credit card details after that card has been expired right i mean you're welcome go go if you're a government or the nsa or gchq or someone who has top secret documents that need to last for over 30 years then you should be worrying about whether you use two to 120 or two to 256. you'll find actually if you go online based on my sort of quick looking around most websites use 128 bit as banks and stuff are using 256. i still i mean arguably that isn't necessary right now but there's no real reason for them not to right it's not that much slower the idea is that these qubits can interact this guy can interact with this guy this guy can interact with this guy and these can interact with one another and every time we add a qubit if we were to add a circle here let's say we added this fourth qubit right here we notice that every single one of them can now interact with it we have to draw lots of these linestoday we're going to ask a question when is 128 bits of encryption 128 bits of encryption what does that mean is that good right you know will a quantum computer affect this it was only a few years ago it used to say military grade i mean we're all using military grade encryption very much so um if you're using 256 bit as it's slightly more military than than 128 but if you're using 128 don't feel bad you're still doing absolutely fine on a very very simple level for a symmetric cipher that is a cipher where um we use the same key for both encryption and decryption so we're not talking about public key right now what we usually mean when we say 128 bit is the length of the key we don't tend to talk about block size particularly so 128 bit as is aes with 128 bit key you also have 192 and 256 bit variants of aes they have the same block size but the key gets longer right have a number of rounds changes the reason we talk about the key length particularly is because if the cipher is good the key is a bit you don't know the key is a bit you're going to have to guess so for a 128-bit block cipher you might have to brute force through two to the power of 128 different keys that's a lot of keys you might get lucky you might get it halfway through in which case it's two to 127 but either way it's not a picnic like that is years and years and years of work right much too much work even for the world's fastest supercomputer because 2 to 128 is a lot bigger than you think right this only gets harder if we make these keys bigger so 2 to 192 operations or 2 to the 256 which is a number so unimaginably large that let's just not even worry about it if your encryption is using a key that's two to 256 long and there isn't another issue with your cipher right so that the security base is based entirely on the key then that is not brute forceable in in any sense within the next 10 years within the next 30 years it's good for us if that is the case so which of these should we use well i mean intuitively 256 bit right but actually 128 bit is currently out of reach of any attacks but it's always slightly more complicated than this what we also talk about is maybe the security of an algorithm itself maybe there's something in the algorithm that isn't quite as secure as the key itself so maybe it wouldn't take two to 128 operations to solve it let's say i've written a cipher that's got 128-bit key it may not have 128 bits of security which is to say it would take this many operations to solve and that way because my cypher is not very good maybe it doesn't mix up things enough or it doesn't permute enough i don't know i designed it it's not going to be very good so you might find that an attack or a break on something like aes what it's doing is not telling me how to solve that problem it's just reducing this number so maybe there's an attack on aes but brings it from 228 down to two to 125 or something like that now that is many times faster than that but still totally out of reach right so that is what i would call an academic break which is to say um we've technically found a weakness in the underlying argument algorithm but it's not a weakness that affects me in my everyday life which arguably is what i care about most so we want to distinguish between the bit length of the key so when we say we've got 128-bit aes we're referring to the key but actually the level of security could be slightly lower depending on the algorithm i mean to use a really obvious example let's imagine i have an algorithm that just depends the key to the message doesn't do any encryption at all right that has a security of zero bits right because it doesn't encrypt anything but it does have a nice 128 bit key for what it's worth right not a very good example you get the idea if you've got some fundamental weaknesses in your cipher it's not going to take a full brute force to do it brute force is the absolute worst case for an attacker now this is slightly more confusing for public key cryptography so things like rsa and diffie-hellman right because they tend to have much much bigger keys so a typical diffie-hellman or rsa key is going to be somewhere between 2048 3072 or 4096 bits these are your common sizes now to factor and solve the rsa problem for a 3000 bit key it's roughly the same as brute forcing 128-bit good symmetric cipher right so those numbers are obviously not even close to the same so the security margin in some sense of these is lower for a given key length one of the reasons that elliptic curves are so popular is they get us a little bit closer from here to here so an elliptic curve of 256 bits is going to be roughly equivalent to security of 128 bit as or 3072-bit rsa now that's going to be quite a lot faster to compute so it's no longer about the length of the key in terms of bits it's about how many bits of security are we going to get and that means essentially two to the how many operations are we going to have to brute force through to guess or work out what's going on so how good is 128 bit or 192 or 256 bit and their equivalence well two to 128 bits is beyond any computer on earth that exists but what you know it's the obvious question all the comments i know it's coming it's coming what about the new advent of quantum computing quantum computing right so one thing that's meant to make really clear about quantum computers is they are not simply a very fast regular computer you don't just run aes on a quantum computer much faster than you would do on a normal computer right and make your life easier you have specific algorithms that do specific jobs and the algorithm that makes breaking aes easier is called grover's algorithm it takes this hypothetically from two to 128 to 2 to the 64. now 264 is within reach so if a quantum computer exists that can break aes using grover's algorithm you're going to go from 128-bit security to 64-bit security that is a problem right if you go from 256-bit security to 2-128 that's less of a problem because i already just said that was beyond reach of any computer right so symmetric is very resistant to quantum computers because all it does is halves the key space and we can just double the key space right does this quantum computer exist no will it exist soon not for at least 20 25 years is what robert told me when we asked it i mean i have no idea i don't develop these computers but certainly not anytime soon so public key cryptography like this 3000 bit rsa key for example that is much more affected by quantum computers shaw's algorithm will basically make this as trivial on a quantum computer as just encrypting using rsa would be on a regular computer that's not what you want right so if a giant quantum computer appears that can halve this problem that same quantum computer could theoretically completely destroy rsa encryption and then we're falling back on password-based key derivation functions and symmetric encryption right that would be the first thing but there are cryptographers and mathematicians looking to create quantum resistant versions of public key algorithms of which some have been developed right so the chances are by the time such a machine exists we won't be using these because of the fact that they have this inherent weakness right but i mean to be clear the they have not factored anywhere close to a 3000 bit number with a quantum computer yet right there's questions about whether that's possible because of just the scale of the thing but even if it is it's not going to happen tomorrow right i mean it would be quite amusing if it did and my video is panned as being probably out of date a day after release but this isn't going to happen anytime soon but the good news from our point of view is we're still going to get 2 to 128 bits of security from aes256 which is why that's what's recommended for sort of long term security for sort of 30 plus years right let's say i'm encrypting my credit card details and sending them off to an online shop that credit card will have expired in two years so it is a honestly zero interest to me if you break my credit card details after that card has been expired right i mean you're welcome go go if you're a government or the nsa or gchq or someone who has top secret documents that need to last for over 30 years then you should be worrying about whether you use two to 120 or two to 256. you'll find actually if you go online based on my sort of quick looking around most websites use 128 bit as banks and stuff are using 256. i still i mean arguably that isn't necessary right now but there's no real reason for them not to right it's not that much slower the idea is that these qubits can interact this guy can interact with this guy this guy can interact with this guy and these can interact with one another and every time we add a qubit if we were to add a circle here let's say we added this fourth qubit right here we notice that every single one of them can now interact with it we have to draw lots of these lines\n"