Tai-Danae, you've made an incredible improvement. We collectively went from "who the hell is this chick" to "hey she's awesome!" just because you slowed down a little. Thank you so much! Remind your producers that the math you cover is almost always completely above anything we've seen before. It's way too easy to lose us, even those of us who formally studied modern maths (myself included). Please tell the same thing to Gabe as well! Thank you!
Oh shut up and stop complaining. If you want easier math then watch sesame street. There are tons of less complicated resources but only one at this level. Don't make this channel dumb down too.
Yes, so glad Gabe's back. Yes he talks fast but it hes seriously the best host on any PBS series, and once you get used to it it actually helps. He is sooooo good at explaining very complex issues.
Right. If you had a protocol to safely transmit the key, you could use that same protocol to transmit the message in the first place. A solution to this problem would be to have a protocol to find a common key (like Diffie-Hellman): The protocol defines a (large) number k. And Alice randomly creates a (large) number a, and transmits k^a (k to the power of a) to Bob, who creates himself a large number b and transmits k^b to back to Alice. She can then in turn calculate (k^b)^a, because she retrieved k^b and generated a herself. Likewise, Bob can calculate (k^a)^b for the same reason. As it turns out (k^a)^b = k^ab = (k^b)^a, so they both have the same number k^ab now that they can use as a shared key. Of course any eavesdropper, Eve, could obtain a by calculating the logarithm base k of k^a, but it turns out that this is an NP-hard problem when using modular arithmetic (with a module of the right size, e.g. a prime number). [Edit: I forgot to mention that such a protocol does not help against man-in-the-middle attacks, i.e. attacks where the person called Eve in the above scenario could modify the message. She would simply run the protocol twice, once to agree on a key with Alice and once to agree on a key with Bob. And subsequently "translate" all the messages between Alice and Bob.] But there's another Achilles' heel that is much more subtle. AES, like all other ciphers, rely on a random key. A TRULY random key. We don't use those for practical reasons. It's MUCH more convenient to use pseudo-random keys. Those are keys (numbers) that are generated in a deterministic way using lots of data that cannot be determined by an attacker, like key stroke dynamics, mouse movements, memory page-in's and page-out's, CPU temperature, etc.. But they ARE NOT truly random. And hence the true key space is smaller than the bit length suggests, even if we do not have an algorithm to exclude parts of the search space today. Maybe tomorrow someone comes up with such an algorithm. We usually cope with that problem by making the key longer (i.e. have more bits).
Yep. In order for Alice to send a message encrypted with AES to Bob (And have Bob actually decrypt it), Bob would have to also know the key first. But if Eve is eavesdropping on their conversation, Alice can't tell Bob the key without having Eve know it too.
My naive guess, what the problem with AES is, would be that both parties need to get the key first and since they need the same they need to transmit it somehow at least once, which opens the possibility for a hacker to get the key.
As for the Achilles Heel, it is clear that everyone involved needs to have the key, so we cannot send a message to a new receiver without sending him the key unencrypted first. Moreover since the key must be kept secret and at the same time be in the hands of everyone, preventing it from getting stolen is difficult unless it is only kept on an internal secure network (which is not the case for the internet in general)
The problem with symmetric cryptography schemes is that you can't transfer the key that unlocks the payload in a way that guarantees the key will only be obtained by authorized agents. The first step to circumventing this issue is public key cryptography. As in, you encrypt a payload that can be unlocked if two of three keys are known. The receiving agent sends his public key to the sending agent who then uses it and his private key to create the encrypted payload to be sent back to the receiver, who can unlock it with the public key and their private key. This still doesn't completely prevent the problem of unauthorized unlocking of payloads. In fact, one of the basic theorems of cryptography is that it is impossible to guarantee all intended recipients can read a payload and all unintended recipients cannot read a payload. Thus, attackers fundamentally have the advantage in cryptography.
multiple recipients would be a separate problem. Alternatively, just individually send the payload to every recipient in the same way as the two-agent problem.
Perhaps I'm misunderstanding you, but isn't there a simple solution? Simply double encrypt your message with both the recipient's public key, AND your own secret key. 1) Since you know for a fact the recipient has their secret key AND your public key, you know they will be able to decrypt it 2) Since your public key ONLY decrypts your secret key, they know it came from you 3) Finally, since their public key can ONLY be decrypted by their secret key, you know only they could read it
I love your deck of cards analogy and corresponding visual demonstration! I've known about cryptography for a while, but this makes some aspects of it, so much clearer! Thanks!
Gabe! Thank you so much for your efforts in slowing down too. I can notice a huge difference on your pacing in this show from the earlier PBS Space Time videos. Also thanks PBS Digital.
Achilles heel: How does Alice securely send that unique key to Bob? Bob needs to have the key before they can agree to use it. Does she read off the number over the phone? Send it by mail? Either way, they will have to use a second channel to share that information, and that channel may not be as secure.
That's what I was thinking as well. Also, the key cannot be hardwired into whatever system they use to transmit the message, because then a hacker could use a physical attack to get the key. [Just a guess, not totally sure :^) ]
Yep, you're both exactly right. And that second channel is secured by using asymmetric encryption such as RSA or a key exchange algorithm such as Diffie-Hellman. By using either of those, two people can agree on a secret key without having to transfer it directly. The issue is that both RSA and the Diffie-Hellman key exchange are based on factoring being difficult, thus breakable by quantum computers. However, there are asymmetric encryption systems which are not based on factoring at all. Those would be decent replacements once quantum computers become a reality.
the "how to get the key" problem does exist asymmetric crypto as well: you need a channel where the messages cannot be changed by a third party. otherwhise eve can make a key pair for fake-alice and fake-bob and read (or change) and forward any message. i think the best solution to such an attack is to use the public keys themselves (or their hashes) as adresses. that way, you nessecarily exchange public keys on the initial contact. and if you exchange them face-to-face you cab be sure you have the right key.
the advantage of asymmetric crypto: * key excange dosn't need to be secret. (just reliably transmitted) * you don't need an extra key for every pair of people who want to talk to each other. edit: i previously wrote "symmetric" instead of "asymmetric", sorry.
+sofias. orange - In a way, that is actually how it works. No, the address isn't the public key itself (that would be impossible to navigate because how would your messaging program know where to send it), but you can crosscheck whether the address and the public key match. The concept here is certificates. For example, I trust that my connection to github is secure and that I'm actually talking to github, not Eve in the middle, because they have handed their public key to DigiCert and proved their identity to them. DigiCert trusts github and I trust DigiCert, so I can be reasonably sure about the connection security. When I go on github, it basically shows me a document that says "Yo, github (with this specific public key) is legit." with DigiCert's signature which comes preinstalled with my OS, so I can check it's correct. It's a bit more complicated than that, but that's basically how it works. But when you're just talking individual-to-individual communication instead of client-server, then yeah, you usually exchange your keys face-to-face beforehand. That or there is a trusted third party who can give you Bob's public key. For example, I got a private/public key pair from my university and I can go to a university website (secured through certificates, so that I know it's legit) where I can look up other students' and uni staff's public keys for signing and encrypting my mail.
Could you talk about Fermat's Last Theorem? I just read a book about the advancement of mathematics through the ages that finally led to Andrew Wiles being able to solve it. You and your team always do a great job adding a visual component, so I'd love to see you cover it. Love the show!!!
Integer factorisation would compromise RSA which is used to *authenticate* sites (i.e. prove that UA-cam is really UA-cam), so Eve could just set up a proxy with either UA-cam's private key after it has been recovered from the public key, or her own certificate that has been *apparently* signed by the Certificate Authority (really just signed by Eve after Eve cracks the CA's private key) before passing on traffic to the real UA-cam. In addition to this, if the discrete logarithm problem is made easy, it doesn't matter how secure AES is. You do Diffie-Hellman key exchange to negotiate the shared symmetric session key, which relies on the computational difficulty of the discrete logarithm problem. So if you break DH, you can obtain the session key and decrypt the AES'd data. A failure in *either* key exchange or symmetric encryption compromises the cryptosystem. Quantum computers would weaken BOTH integer factorisation AND the discrete logarithm problem. So, UA-cam's encryption of this video would *definitely* be affected by breaking IntFac. However, if you encrypted files with AES and a passphrase, they would be unaffected by IntFac OR discrete logarihm. Please clarify this when you do the next video on asymmetric encryption. edit: TLS actually has several key exchange methods. What I said refers to DH_RSA and DHE_RSA (and also the DSS and elliptic curve versions. The certificate authority still signs the certificate with RSA though so Eve could make her own 'valid' key with broken IntFac only, meaning EVEN THOUGH UA-cam uses ECDHE_ECDSA/X25519 it could still be MITM-compromised), because I don't think anyone uses bare RSA key exchange anymore (I hope not, from what I can tell the client gets to choose the nonce, so Eve could exploit this to encrypt whatever she wants with the server's private key without knowing the key herself. Um. If that were true surely people smarter than me would have realised this was a bad idea a long time ago?). *If* RSA key exchange is used then breaking IntFac would reveal the session key. Even for past sessions (previously recorded ciphertext). Otherwise, if IntFac is broken but not DLP then Eve can only Man-in-the-Middle *new* connections. By the way, good video. Crypto is hard and it's easy to miss a weak point in a cryptosystem. I hope I haven't made any mistakes in reply...
Looks like a number of other commenters got it: the "Achilles Heel" of AES is the key-exchange. Public-key cryptography, with its prime numbers, is a way of communicating that exchange, though in a less-robust way. That's one of the two reasons why public-key crypto is typically limited to doing the key exchange for a more robust algorithm that is then used for the rest of the communication - if you limit the messages sent via public-key algorithms, you reduce the likelihood of key exposure or other attacks. (The other reason is that prime factorization is slow, so using fast crypto algorithms for most of the work is important.)
Gabe, I was expecting you to go much faster (given your earlier videos on SpaceTime) , but I really liked your pace in this video. Feels a lot more manageable!
Loved the video, Gabe give a great touch (probably because I used to see him on PBS spacetime) and Tai-Danae is also very nice in her method of explaining things and seems to enjoy the topics a lot, the previous host was great two, but the new ones are doing fantastic :)
Achilles heel is the sharing of the key. That's what makes public key algorithms so elegant, they don't need that.
6 років тому
With AES (and all symmetric-key schemes), the private key of all agents must be the same (the "shuffling rule"). So in order for it to work you need to communicate the (first) private key beforehand - presumably without AES, and that's where the practical weakness is.
The handshake is not done in plaintext, you use something called a DH (short for diffie-helmann) group and something called PFS (perfect forward secrecy). Properly configured, PFS is practically unbreakable. PFS based text messaging is a PITA for NSA who has cray supercomputers on the task and they still can't do it reliably.
Interesting video! The reason we need RSA is because both parties need to have the exact same key in order to use AES but they can't just send it online because the attacker will also have the key so both of them need to come up with a way of agreeing on a key without anyone else figuring out what the key might be. This is where public key cryptography comes into play :)
AES’s flaw is that it is private, and uses only a private key for accessing or changing the files. And finding a secure way to hide and transfer that key to everyone who would need access is difficult and a major security risk.
GABE! YOU'RE BACK!!! Welcome! I review your explanation for m = E/c^2 every now and then. You did a great job explaining that. I'm sure you'll do well here too. Question: AES requires the two sides to know the 3-2-1-2-3. Doesn't that make AES vulnerable? All you need is some disgruntled former employee to leak the 3-2-1-2-3 and you're done for. Generalizing, isn't any security schema inherently up-to-a-certain-point-insecure because they all involve some degree of human intervention? Are there solutions to that?
Clever wordplay on symmetrical encryption's Achilles' heel, since the weakest link with just symmetrical encryption is human related. In order for symmetrical encryption to truly work properly, the key must be sent securely. Asymmetrical encryption is a great way to accomplish this task. In the real world things like RSA accomplish this with their public / private key pair -- I'd love to go into more detail but I'm certain the next video will!
Pulled from Wikipedia: In cryptography, Kerckhoffs' principle (also called Kerckhoffs' desideratum, assumption, axiom, doctrine or law) was stated by Dutch cryptographer Auguste Kerckhoffs in the 19th century: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.
I like the playing card analogy. It reminds me of the "Pontifex" cipher, which was used the 52 cards of a deck to offset the 26 letters of the alphabet by a differing amount each time. Weirdly, because of a quirk of maths, analysts found weaknesses in that, too. Really fascinating. :)
The Achilles' Heel is, of course, the secret key. This is for three reasons. First, you need to transmit the key to the recipient. If you encrypt this key, the recipient can't decrypt it. So it must be transmitted in the clear or requires some other exotic (and inconvenient) way to share it. Second, if the secret key is ever learned (say, by Eve the Eavesdropper), then it's no good. Finally, there is the issue of trust. Every time you send a message, you have to trust that person with your secret key. This is where methods like RSA come in handy.
I think this is because physics is his passion so he can let it out really quickly whereas these topics are more foreign to him (though he is clearly able to articulate it) so he has to slow down and think harder about what he is saying. Having said that, I now KNOW the theory of relativity because of Gabe's spacetime videos, quick talker or not, he knows his stuff and is able to convey it in a way that people can understand.
The flaw is the key, which either Alice and Bob must have, or which must be sent from Alice to Bob. Both the existence of two copys of the key and the transfer of the key itself can compromise security.
could you guys do an episode about dynamical systems?, you could explain a lot of neat stuff like equilibrium points, limit sets, lyapunov functions, bifurcations, etc, and the applications are endless, you could go on about how PID controllers work, of how do satelite nonlinear controllers do their thing, etc
No. The key is used in the scrambling and unscrambling but it should *never* be included with the encrypted message. If you put a message in a box and locked the box before putting it in the post, you would not send the key with the box. The answer is: How Do Alice and Bob agree on what the key should be without Eve, (who can hear everything) learning it. (James H. Ellis, Clifford Cocks and Malcolm J. Williamson found an answer.)
Whether it's sent with the message or not, it does have to be sent somehow, and that is the weakness as I see it. (Also, I thought the symmetric key generally _is_ transmitted along with the message, but the key is encrypted using some other mechanism, these days largely symmetric...)
I was somewhat expecting this to be about quantum communication (also known as quantum cryptography)... The issue with AES and symmetric crypto is the ability to securely share keys prior to communication. This was solved by Diffie and Hellman in their key exchange, which gave birth to asymmetric crypto. I would argue that systems like RSA, which are built and deployed outside of security reductions, present more risk than provably secure systems using a reduction (LWE or R-LWE). It's interesting to note that there is a fundamental mathematical structure underlying RSA, which introduces a weakness in terms of post-quantum resilience. My question is whether quantum communications will require any post-quantum cryptography deployed alongside such an infrastructure, if such an infrastructure is even feasible in the near-future.
The weakness is that both people have to have the key, so that requires it be communicated right? And therefore if the hacker can intercept that key somehow, then its game over, right?
It's like intercepting a courier carrying the latest Enigma Codebook all comm officers must get before reestablish communications. You get a logbook copy without getting caught, the entire military is screwed until they make new codebook for dissertation.
It is more subtle than that, key exchange is done through a secure channel using a DH group (diffie helmann) and if you salt it with PFS (perfect forward secrecy) than the key exchange is essentially unbreakable. The problem is when there is a flaw in the vendor implementation of the key exchange protocols that may expose the key or, as is more often the case, it exposes the huge pre-agreed too hashing number which can then be reverse engineered. This isn't a common attack and requires something called an "SSL Stripper" to be in line with the communication which pre-supposes a lot of things going right for the hacker. This is more often done by a LEA who has a warrant and can get into the ISP POP that the target's internet is coming into.
To exchange the private key you can use Diffie-Hellman. If Alice and Bob want to exchange a key, they choose a public prime number, for example p = 23. They also have to chose a primitive root of the field Z_p (i.e. the successive powers of this number generate all the field except 0). g = 5 is valid for p = 23. Alice choose a secret number a = 6, and sends g^(a) mod p ( 5^6 mod 23 = 8 ) to Bob. Bob choose his secret number b = 15 and sends g^(b) mod p ( 5^15 mod 23 = 19 ) to Alice. Now, both can obtain the same private key (that they can use in AES) by raising the received number to its secret number. Alice obtains 19^6 mod 23 = 2. Bob obtains 8^15 mod 23 = 2. The private key has never been send and it's difficult to find the inverse of g^(a) mod p. You have to do it by trial an error so it's quite secure if the used numbers are big enough.
How does Bob know what key Anna used to encrypt the messege? Is it only one particular key for a particular information exchange platform (e.g. Gmail or UA-cam)?
Any chance we can get an episode on Lattice-based Encryption? You can use it as an alternative to RSA, but it's not crackable with quantum computers (yet), since it's related to the subset sum problem rather than prime factorization. There seems to be a lot of talk in the blockchain community about it. There are some techniques for cracking it under very specific circumstances (for example, using the generalized birthday set problem to find solutions. In fact, I discovered a couple weeks ago, to my surprise, that the guy who discovered this method is my second-cousin), but it's easy to avoid them with the right constraints on your public/private key.
I'm not sure if one exists but informationally would it be possible to make an algorithm for a quantum computer to crack AES in polynomial time? Since the idea of quantum computers is you have exponentially increasing computing power as you add qubit, could you turn this exponential time to polynomial too? Or would it be just as hard to guess the key as it would guess the full message like with a one time pad?
Can you talk about why if you have an odd number you follow the expression (3X+1) and if you have an even number you follow the expression (X/2) if you follow this pattern you'll eventually get 1? And if there's a number that doesn't work, how would you find it?
Alice and bob are looking for keys in black holes?? Please do more gr vids i still don't get it. ..and go back to speed of light talk. This is why we all love u :)
The problem with AES: When I want to talk securely to someone I haven't spoken with before (read: someone I don't share a key with); how do I send that person a key securely.
Two problems: 1st How to make sure nobody sniffs the key to begin with? 2nd If you log in with an encrypted password, somebody that sniffs that encrypted password can just use it as it is, without breaking it. That's what comes to my mind first at least...
Well if you know the key for the encoypted message you can decode it. So keeping it secret is very important. But if you have a network of several million clients like youtube that is not really possible. Thats why symmetric encryption is only used when you can trust everyone to keep the key secret.
Hey Kelsey! Why have you guys not covered the basics of Distributed ledger tech and P2P networks?? I think projects within the Web3 Foundation could really shine light on future cryptography - Especially Aragon and Polkadot !!
Of course as others have already said, problem is key exchange ,and we already saw bunch of attacks on different symmetric encryption protocols by five eyes (NSA goons and their little servants) that had been successful. Snowden brought lot of that stuff to public eye , but there has been numerous other leaks post-Snowden that have conferred that key exchange is weak spot of symmetric encryption .
Both people need to have the same key for symmetric encryption to work. How do you send they key to someone without letting a third party know? You can't encrypt it with symmetric encryption without knowing the key, which makes is sort of redundant. The full solution is that you send the symmetric key using RSA, and send everything else using symmetric encryption.
The symmetric key is still sent using methods where a potential factoring algorithm could break it, so please don’t mislead people by saying that such an algorithm wouldn’t break our current security standards
![[UA] Eternal Fire проти NAVI | EPL Season 20 Malta](http://i.ytimg.com/vi/chvlsDygrZM/mqdefault.jpg)
I'm glad the death of the universe was mentioned. Almost like Gabe's back on Space Time.
Thought this was an old spacetime video before remembering Gabe is now doing infinite series videos.
Tai-Danae, you've made an incredible improvement. We collectively went from "who the hell is this chick" to "hey she's awesome!" just because you slowed down a little. Thank you so much! Remind your producers that the math you cover is almost always completely above anything we've seen before. It's way too easy to lose us, even those of us who formally studied modern maths (myself included).
Please tell the same thing to Gabe as well! Thank you!
Oh shut up and stop complaining. If you want easier math then watch sesame street. There are tons of less complicated resources but only one at this level. Don't make this channel dumb down too.
"An eavesdropper, like Eve" i giggled.
Eve S. Dropper
en.m.wikipedia.org/wiki/Alice_and_Bob
This could be your advertisement! They played me like a fiddle!
Rachel Jane Hulsey LIKE A DAMN FIDDLE
Trust your technolust ;)
Woah, it's the dude from Space Time. Welcome back buddy!
Yes, so glad Gabe's back. Yes he talks fast but it hes seriously the best host on any PBS series, and once you get used to it it actually helps. He is sooooo good at explaining very complex issues.
First! :P
And second view!
Also, its "Achilles' heel" (6:26) is when you first transmit the key, right?
Correct, once the key is exposed, there is no undoing that. A new key would have to be distributed.
yup, definitely the key transmission
Or they can transmit the key ahead of time, when they know Eve is not around.
Better yet, they might as well give each other a 1 time pad.
Right. If you had a protocol to safely transmit the key, you could use that same protocol to transmit the message in the first place.
A solution to this problem would be to have a protocol to find a common key (like Diffie-Hellman):
The protocol defines a (large) number k. And Alice randomly creates a (large) number a, and transmits
k^a (k to the power of a) to Bob, who creates himself a large number b and transmits k^b to back to Alice. She can then in turn calculate (k^b)^a, because she retrieved k^b and generated a herself. Likewise, Bob can calculate (k^a)^b for the same reason. As it turns out (k^a)^b = k^ab = (k^b)^a, so they both have the same number k^ab now that they can use as a shared key. Of course any eavesdropper, Eve, could obtain a by calculating the logarithm base k of k^a, but it turns out that this is an NP-hard problem when using modular arithmetic (with a module of the right size, e.g. a prime number).
[Edit: I forgot to mention that such a protocol does not help against man-in-the-middle attacks, i.e. attacks where the person called Eve in the above scenario could modify the message. She would simply run the protocol twice, once to agree on a key with Alice and once to agree on a key with Bob. And subsequently "translate" all the messages between Alice and Bob.]
But there's another Achilles' heel that is much more subtle. AES, like all other ciphers, rely on a random key. A TRULY random key. We don't use those for practical reasons. It's MUCH more convenient to use pseudo-random keys. Those are keys (numbers) that are generated in a deterministic way using lots of data that cannot be determined by an attacker, like key stroke dynamics, mouse movements, memory page-in's and page-out's, CPU temperature, etc.. But they ARE NOT truly random. And hence the true key space is smaller than the bit length suggests, even if we do not have an algorithm to exclude parts of the search space today. Maybe tomorrow someone comes up with such an algorithm. We usually cope with that problem by making the key longer (i.e. have more bits).
Yep. In order for Alice to send a message encrypted with AES to Bob (And have Bob actually decrypt it), Bob would have to also know the key first. But if Eve is eavesdropping on their conversation, Alice can't tell Bob the key without having Eve know it too.
My naive guess, what the problem with AES is, would be that both parties need to get the key first and since they need the same they need to transmit it somehow at least once, which opens the possibility for a hacker to get the key.
Yes!
HES BACK!! HES BACK!!!!!!
WHO'S BACK?? WHO'S BACK????
I'm front.
These hosts are awesome!
DanTheMan I still miss kelsi though
Was'nt this host previously on pbs space time.Nice seeing him back
As noted when the announcement of host change was made.
Yes he was, it's announced in this video ua-cam.com/video/NHucpzbD600/v-deo.html
Yes, this guy I can clearly understand.
Bobby Harper accents are hard
As for the Achilles Heel, it is clear that everyone involved needs to have the key, so we cannot send a message to a new receiver without sending him the key unencrypted first. Moreover since the key must be kept secret and at the same time be in the hands of everyone, preventing it from getting stolen is difficult unless it is only kept on an internal secure network (which is not the case for the internet in general)
The problem with symmetric cryptography schemes is that you can't transfer the key that unlocks the payload in a way that guarantees the key will only be obtained by authorized agents.
The first step to circumventing this issue is public key cryptography. As in, you encrypt a payload that can be unlocked if two of three keys are known. The receiving agent sends his public key to the sending agent who then uses it and his private key to create the encrypted payload to be sent back to the receiver, who can unlock it with the public key and their private key.
This still doesn't completely prevent the problem of unauthorized unlocking of payloads. In fact, one of the basic theorems of cryptography is that it is impossible to guarantee all intended recipients can read a payload and all unintended recipients cannot read a payload. Thus, attackers fundamentally have the advantage in cryptography.
· 0xFFF1 even if you could transmit the key in a perfectly secure way you still have multiple agents that need to know what the key is
multiple recipients would be a separate problem. Alternatively, just individually send the payload to every recipient in the same way as the two-agent problem.
Perhaps I'm misunderstanding you, but isn't there a simple solution? Simply double encrypt your message with both the recipient's public key, AND your own secret key.
1) Since you know for a fact the recipient has their secret key AND your public key, you know they will be able to decrypt it
2) Since your public key ONLY decrypts your secret key, they know it came from you
3) Finally, since their public key can ONLY be decrypted by their secret key, you know only they could read it
QED symmetric cryptography doesn't have public and private keys
QED Congratulations, you've just invented SSL. More accurately, you've invented session keys.
I love your deck of cards analogy and corresponding visual demonstration!
I've known about cryptography for a while, but this makes some aspects of it, so much clearer! Thanks!
(Almost) Understood Everything
You don't need to prove your intelligence to the UA-cam comments. You're already a lot better than average.
But is it associative? Almost (Understood Everything). Hmmmmm...
(almost) understood something
I understood everything, except for finitely much
200% of your holded bitcoins in less than a week. search for 'fast-bitcoin' on google
Gabe! Thank you so much for your efforts in slowing down too. I can notice a huge difference on your pacing in this show from the earlier PBS Space Time videos. Also thanks PBS Digital.
Achilles heel: How does Alice securely send that unique key to Bob? Bob needs to have the key before they can agree to use it. Does she read off the number over the phone? Send it by mail? Either way, they will have to use a second channel to share that information, and that channel may not be as secure.
That's what I was thinking as well. Also, the key cannot be hardwired into whatever system they use to transmit the message, because then a hacker could use a physical attack to get the key. [Just a guess, not totally sure :^) ]
Yep, you're both exactly right. And that second channel is secured by using asymmetric encryption such as RSA or a key exchange algorithm such as Diffie-Hellman. By using either of those, two people can agree on a secret key without having to transfer it directly.
The issue is that both RSA and the Diffie-Hellman key exchange are based on factoring being difficult, thus breakable by quantum computers. However, there are asymmetric encryption systems which are not based on factoring at all. Those would be decent replacements once quantum computers become a reality.
the "how to get the key" problem does exist asymmetric crypto as well: you need a channel where the messages cannot be changed by a third party. otherwhise eve can make a key pair for fake-alice and fake-bob and read (or change) and forward any message.
i think the best solution to such an attack is to use the public keys themselves (or their hashes) as adresses. that way, you nessecarily exchange public keys on the initial contact. and if you exchange them face-to-face you cab be sure you have the right key.
the advantage of asymmetric crypto:
* key excange dosn't need to be secret. (just reliably transmitted)
* you don't need an extra key for every pair of people who want to talk to each other.
edit: i previously wrote "symmetric" instead of "asymmetric", sorry.
+sofias. orange - In a way, that is actually how it works. No, the address isn't the public key itself (that would be impossible to navigate because how would your messaging program know where to send it), but you can crosscheck whether the address and the public key match.
The concept here is certificates. For example, I trust that my connection to github is secure and that I'm actually talking to github, not Eve in the middle, because they have handed their public key to DigiCert and proved their identity to them. DigiCert trusts github and I trust DigiCert, so I can be reasonably sure about the connection security.
When I go on github, it basically shows me a document that says "Yo, github (with this specific public key) is legit." with DigiCert's signature which comes preinstalled with my OS, so I can check it's correct.
It's a bit more complicated than that, but that's basically how it works.
But when you're just talking individual-to-individual communication instead of client-server, then yeah, you usually exchange your keys face-to-face beforehand. That or there is a trusted third party who can give you Bob's public key.
For example, I got a private/public key pair from my university and I can go to a university website (secured through certificates, so that I know it's legit) where I can look up other students' and uni staff's public keys for signing and encrypting my mail.
Yes! Nice to have you back Gabe!
Could you talk about Fermat's Last Theorem? I just read a book about the advancement of mathematics through the ages that finally led to Andrew Wiles being able to solve it. You and your team always do a great job adding a visual component, so I'd love to see you cover it. Love the show!!!
Ooo, the old host of PBS Spacetime! In terms of hosts from that channel, I guess we now can finally have the cake and eat it at the same time!
waaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaattttttttt I feel like a young pbs space time viewer again
Two words (or names rather) predicting what the next video will be about: Diffie Hellman.
Tai Danae: I heard u guys, i'll talk slower now
Gabe: EUROBEAT INTENSIFIES
in any case
WELCOME BACK LORD GABEN
Integer factorisation would compromise RSA which is used to *authenticate* sites (i.e. prove that UA-cam is really UA-cam), so Eve could just set up a proxy with either UA-cam's private key after it has been recovered from the public key, or her own certificate that has been *apparently* signed by the Certificate Authority (really just signed by Eve after Eve cracks the CA's private key) before passing on traffic to the real UA-cam.
In addition to this, if the discrete logarithm problem is made easy, it doesn't matter how secure AES is. You do Diffie-Hellman key exchange to negotiate the shared symmetric session key, which relies on the computational difficulty of the discrete logarithm problem. So if you break DH, you can obtain the session key and decrypt the AES'd data. A failure in *either* key exchange or symmetric encryption compromises the cryptosystem.
Quantum computers would weaken BOTH integer factorisation AND the discrete logarithm problem.
So, UA-cam's encryption of this video would *definitely* be affected by breaking IntFac. However, if you encrypted files with AES and a passphrase, they would be unaffected by IntFac OR discrete logarihm. Please clarify this when you do the next video on asymmetric encryption.
edit: TLS actually has several key exchange methods. What I said refers to DH_RSA and DHE_RSA (and also the DSS and elliptic curve versions. The certificate authority still signs the certificate with RSA though so Eve could make her own 'valid' key with broken IntFac only, meaning EVEN THOUGH UA-cam uses ECDHE_ECDSA/X25519 it could still be MITM-compromised), because I don't think anyone uses bare RSA key exchange anymore (I hope not, from what I can tell the client gets to choose the nonce, so Eve could exploit this to encrypt whatever she wants with the server's private key without knowing the key herself. Um. If that were true surely people smarter than me would have realised this was a bad idea a long time ago?). *If* RSA key exchange is used then breaking IntFac would reveal the session key. Even for past sessions (previously recorded ciphertext). Otherwise, if IntFac is broken but not DLP then Eve can only Man-in-the-Middle *new* connections.
By the way, good video. Crypto is hard and it's easy to miss a weak point in a cryptosystem. I hope I haven't made any mistakes in reply...
I really like Gabe, he explains things in a way that doesn't seem like he's talking down to me. Wish he was back on Spacetime
Looks like a number of other commenters got it: the "Achilles Heel" of AES is the key-exchange. Public-key cryptography, with its prime numbers, is a way of communicating that exchange, though in a less-robust way. That's one of the two reasons why public-key crypto is typically limited to doing the key exchange for a more robust algorithm that is then used for the rest of the communication - if you limit the messages sent via public-key algorithms, you reduce the likelihood of key exposure or other attacks. (The other reason is that prime factorization is slow, so using fast crypto algorithms for most of the work is important.)
The new girl is my favourite!
Nice to see you again, Gabe!
Glad to see you back
Gabe, I was expecting you to go much faster (given your earlier videos on SpaceTime) , but I really liked your pace in this video. Feels a lot more manageable!
Loved the video, Gabe give a great touch (probably because I used to see him on PBS spacetime) and Tai-Danae is also very nice in her method of explaining things and seems to enjoy the topics a lot, the previous host was great two, but the new ones are doing fantastic :)
Achilles heel is the sharing of the key. That's what makes public key algorithms so elegant, they don't need that.
With AES (and all symmetric-key schemes), the private key of all agents must be the same (the "shuffling rule"). So in order for it to work you need to communicate the (first) private key beforehand - presumably without AES, and that's where the practical weakness is.
How is the agreed key sent cryptographically? Wouldn't the initial "handshake" have to be in plain text?
Bingo. You hit the nail on the head here.
The handshake is not done in plaintext, you use something called a DH (short for diffie-helmann) group and something called PFS (perfect forward secrecy). Properly configured, PFS is practically unbreakable. PFS based text messaging is a PITA for NSA who has cray supercomputers on the task and they still can't do it reliably.
Interesting video! The reason we need RSA is because both parties need to have the exact same key in order to use AES but they can't just send it online because the attacker will also have the key so both of them need to come up with a way of agreeing on a key without anyone else figuring out what the key might be. This is where public key cryptography comes into play :)
Just came here from PBS Studios again. I hope you guys come back one day
This is delightfully well done.
AES’s flaw is that it is private, and uses only a private key for accessing or changing the files. And finding a secure way to hide and transfer that key to everyone who would need access is difficult and a major security risk.
GABE! YOU'RE BACK!!! Welcome! I review your explanation for m = E/c^2 every now and then. You did a great job explaining that. I'm sure you'll do well here too. Question: AES requires the two sides to know the 3-2-1-2-3. Doesn't that make AES vulnerable? All you need is some disgruntled former employee to leak the 3-2-1-2-3 and you're done for. Generalizing, isn't any security schema inherently up-to-a-certain-point-insecure because they all involve some degree of human intervention? Are there solutions to that?
Gabe! Welcome back! We miss you on spacetime!
great episode, even greater to see Gabe back - he talks slower now tho!
Welcome back, Gabe!
Welcome back! You're my favorite host
Revenge of the Cypherpunks unleashed. Good content!
Clever wordplay on symmetrical encryption's Achilles' heel, since the weakest link with just symmetrical encryption is human related. In order for symmetrical encryption to truly work properly, the key must be sent securely. Asymmetrical encryption is a great way to accomplish this task. In the real world things like RSA accomplish this with their public / private key pair -- I'd love to go into more detail but I'm certain the next video will!
WHOA... THIS DUDE... YOU BACK!!!
Pulled from Wikipedia:
In cryptography, Kerckhoffs' principle (also called Kerckhoffs' desideratum, assumption, axiom, doctrine or law) was stated by Dutch cryptographer Auguste Kerckhoffs in the 19th century: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.
I like the playing card analogy. It reminds me of the "Pontifex" cipher, which was used the 52 cards of a deck to offset the 26 letters of the alphabet by a differing amount each time.
Weirdly, because of a quirk of maths, analysts found weaknesses in that, too. Really fascinating. :)
The Achilles' Heel is, of course, the secret key. This is for three reasons. First, you need to transmit the key to the recipient. If you encrypt this key, the recipient can't decrypt it. So it must be transmitted in the clear or requires some other exotic (and inconvenient) way to share it. Second, if the secret key is ever learned (say, by Eve the Eavesdropper), then it's no good. Finally, there is the issue of trust. Every time you send a message, you have to trust that person with your secret key. This is where methods like RSA come in handy.
Either that is an uncanny likeness or someone spotted Vanessa in a corridor and dragged her in to do some stellar face acting.
Who needs notification when you are always on youtube
Welcome back Gabe.
Oh god, Gabe is back!
Mr. doyen has arrived. This is going to be quite a ride.
Wow, Gabe has slowed down! Awesome! He was too fast in spacetime
I think this is because physics is his passion so he can let it out really quickly whereas these topics are more foreign to him (though he is clearly able to articulate it) so he has to slow down and think harder about what he is saying. Having said that, I now KNOW the theory of relativity because of Gabe's spacetime videos, quick talker or not, he knows his stuff and is able to convey it in a way that people can understand.
The flaw is the key, which either Alice and Bob must have, or which must be sent from Alice to Bob. Both the existence of two copys of the key and the transfer of the key itself can compromise security.
Whoa he's back!
0:44 Hey there, Vanessa from BrainCraft! Having fun being the sneaky eavesdropper?
Always 👩🏻💻
could you guys do an episode about dynamical systems?, you could explain a lot of neat stuff like equilibrium points, limit sets, lyapunov functions, bifurcations, etc, and the applications are endless, you could go on about how PID controllers work, of how do satelite nonlinear controllers do their thing, etc
+25 points for using the word ' esoteric' :)
Is the achilles heel that Alice has to send the scrambled message along with a key, which while sending could be intercepted?
Yes
No. The key is used in the scrambling and unscrambling but it should *never* be included with the encrypted message. If you put a message in a box and locked the box before putting it in the post, you would not send the key with the box.
The answer is: How Do Alice and Bob agree on what the key should be without Eve, (who can hear everything) learning it. (James H. Ellis, Clifford Cocks and Malcolm J. Williamson found an answer.)
The weakness is indeed that Alice and Bob will have to agree on a key before they can use it to encrypt anything.
Whether it's sent with the message or not, it does have to be sent somehow, and that is the weakness as I see it.
(Also, I thought the symmetric key generally _is_ transmitted along with the message, but the key is encrypted using some other mechanism, these days largely symmetric...)
Thank god you're now speaking at a way slower pace. Now I can actually process what you're saying, keep it up!
I was somewhat expecting this to be about quantum communication (also known as quantum cryptography)...
The issue with AES and symmetric crypto is the ability to securely share keys prior to communication. This was solved by Diffie and Hellman in their key exchange, which gave birth to asymmetric crypto. I would argue that systems like RSA, which are built and deployed outside of security reductions, present more risk than provably secure systems using a reduction (LWE or R-LWE). It's interesting to note that there is a fundamental mathematical structure underlying RSA, which introduces a weakness in terms of post-quantum resilience. My question is whether quantum communications will require any post-quantum cryptography deployed alongside such an infrastructure, if such an infrastructure is even feasible in the near-future.
Finally gabe is back
poor Alice is always having to deal with her data being watched.
Gabe! The sun will not explode..didn't expect such an error from the previous host of Space Time :)
Also I'm guessing the Achilles heel is that both parties need to agree on the order of shuffling beforehand
The weakness is that both people have to have the key, so that requires it be communicated right? And therefore if the hacker can intercept that key somehow, then its game over, right?
exactly
It's like intercepting a courier carrying the latest Enigma Codebook all comm officers must get before reestablish communications.
You get a logbook copy without getting caught, the entire military is screwed until they make new codebook for dissertation.
It is more subtle than that, key exchange is done through a secure channel using a DH group (diffie helmann) and if you salt it with PFS (perfect forward secrecy) than the key exchange is essentially unbreakable. The problem is when there is a flaw in the vendor implementation of the key exchange protocols that may expose the key or, as is more often the case, it exposes the huge pre-agreed too hashing number which can then be reverse engineered. This isn't a common attack and requires something called an "SSL Stripper" to be in line with the communication which pre-supposes a lot of things going right for the hacker. This is more often done by a LEA who has a warrant and can get into the ISP POP that the target's internet is coming into.
Tai, I like the faster talking better. Slow means minds wandering. People can always rewatch.
To exchange the private key you can use Diffie-Hellman. If Alice and Bob want to exchange a key, they choose a public prime number, for example p = 23. They also have to chose a primitive root of the field Z_p (i.e. the successive powers of this number generate all the field except 0). g = 5 is valid for p = 23. Alice choose a secret number a = 6, and sends g^(a) mod p ( 5^6 mod 23 = 8 ) to Bob. Bob choose his secret number b = 15 and sends g^(b) mod p ( 5^15 mod 23 = 19 ) to Alice. Now, both can obtain the same private key (that they can use in AES) by raising the received number to its secret number. Alice obtains 19^6 mod 23 = 2. Bob obtains 8^15 mod 23 = 2. The private key has never been send and it's difficult to find the inverse of g^(a) mod p. You have to do it by trial an error so it's quite secure if the used numbers are big enough.
I miss you from spacetime. New guy's fine, but I still miss you.
How does Bob know what key Anna used to encrypt the messege? Is it only one particular key for a particular information exchange platform (e.g. Gmail or UA-cam)?
Welcome back
20:10 Kerckhoffs's principle
Any chance we can get an episode on Lattice-based Encryption? You can use it as an alternative to RSA, but it's not crackable with quantum computers (yet), since it's related to the subset sum problem rather than prime factorization. There seems to be a lot of talk in the blockchain community about it.
There are some techniques for cracking it under very specific circumstances (for example, using the generalized birthday set problem to find solutions. In fact, I discovered a couple weeks ago, to my surprise, that the guy who discovered this method is my second-cousin), but it's easy to avoid them with the right constraints on your public/private key.
So well explained, I love it.
Wonderful videos! Keep it up.
I'm not sure if one exists but informationally would it be possible to make an algorithm for a quantum computer to crack AES in polynomial time? Since the idea of quantum computers is you have exponentially increasing computing power as you add qubit, could you turn this exponential time to polynomial too? Or would it be just as hard to guess the key as it would guess the full message like with a one time pad?
Fast prime factoring of large numbers would break the encryption of this video because https uses RSA for the initial handshake/key exchange.
I prefer when Gabe talks fast. #FreeGabe
IT'S THE ORIGINAL DUDE FROM SPACETIME!!! I RECOGNISE HIM!!
PBS Braincraft iz in ur internetz, hackin ur Infinite Seriez!
Omfg Gabe's back😍
Can you talk about why if you have an odd number you follow the expression (3X+1) and if you have an even number you follow the expression (X/2) if you follow this pattern you'll eventually get 1? And if there's a number that doesn't work, how would you find it?
lol the bullets shooting "AES" are still in their cases
Alice and bob are looking for keys in black holes?? Please do more gr vids i still don't get it. ..and go back to speed of light talk. This is why we all love u :)
The problem with AES: When I want to talk securely to someone I haven't spoken with before (read: someone I don't share a key with); how do I send that person a key securely.
Two problems:
1st How to make sure nobody sniffs the key to begin with?
2nd If you log in with an encrypted password, somebody that sniffs that encrypted password can just use it as it is, without breaking it.
That's what comes to my mind first at least...
The key is the achilles heel seeing as it has only a single procedure to unlock the cipher.
Well if you know the key for the encoypted message you can decode it. So keeping it secret is very important. But if you have a network of several million clients like youtube that is not really possible. Thats why symmetric encryption is only used when you can trust everyone to keep the key secret.
6:10 subtle pun
Hey Kelsey! Why have you guys not covered the basics of Distributed ledger tech and P2P networks?? I think projects within the Web3 Foundation could really shine light on future cryptography - Especially Aragon and Polkadot !!
How well do (or would) quantum computers deal with breaking AES?
Welcome back! ?
Of course the issue is: how do you exchange keys without already having a key to exchange them securely with?
Of course as others have already said, problem is key exchange ,and we already saw bunch of attacks on different symmetric encryption protocols by five eyes (NSA goons and their little servants) that had been successful. Snowden brought lot of that stuff to public eye , but there has been numerous other leaks post-Snowden that have conferred that key exchange is weak spot of symmetric encryption .
Both people need to have the same key for symmetric encryption to work. How do you send they key to someone without letting a third party know? You can't encrypt it with symmetric encryption without knowing the key, which makes is sort of redundant. The full solution is that you send the symmetric key using RSA, and send everything else using symmetric encryption.
Gabe! Please appear on PBS Space Time as well!
The symmetric key is still sent using methods where a potential factoring algorithm could break it, so please don’t mislead people by saying that such an algorithm wouldn’t break our current security standards
I'm guessing that RSA is used more because it doesn't require you to meet up with another person to exchange an initial key in person.