Man in the Middle & Needham-Schroeder Protocol - Computerphile

There's a reason Needham-Schroeder isn't used any more - Tim Muller demonstrates the weakness in the technique.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@Amonimus]

"69 and 42, these are very rare numbers that you'll almost never find."

[@mrxmry3264]

LOL!

[@reedy8585]

He said they would be much larger numbers in reality and these are very rare numbers that you would almost never find

[@smicro6758]

@@reedy8585 you definitely don’t know what these numbers mean :)

[@reedy8585]

@@smicro6758 It depends on what context you are refering to them

[@brandonjones5566]

Lol

[@rmsgrey]

Something that's being glossed over here is how Alice and Bob each get the other's public key in the first place - and why that method can't be used to establish the shared connection.

[@talideon]

Key exchange is an orthogonal issue, which the likes of Needham-Schroeder-Lowe isn't intended to solve. For that, you need something like trust networks, CAs, &c., and it's not a trivial issue. There are also other videos on the channel dealing with those, so it's apt to gloss over that part of the problem. However, the whole point of this is session initiation, so it _can_ be used to establish a shared connection.

[@ElectricGears]

What if every time Bob send out his public key, Pat secretly switches it for his own key? Pat will be able to decrypt everything Alice sends, examine it, and re-encrypt it with Alice's public key and send it to Bob.

[@rmsgrey]

@@ElectricGears I think you meant Bob's public key at the end there. The big limit in Pat only replacing Bob's public key with "Bob" 's public key, but not doing anything with Alice's keys is that Pat's only options with Bob's messages to Alice are to delete them or to pass them on unaltered - for the former, Pat doesn't know what responses Bob is expecting, and can't fake them reliably; for the latter, Pat is limited to tricking Alice into responding in ways that reveal Bob's secrets, without Alice realising that Bob and "Bob" are different.

[@gerdkah6064]

u find the public key like in telephonebooks - but u should check the trustworthyness of the publisher

[@SoulJah876]

PKI & certificates, I believe.

[@duncanw9901]

My favorite subject in school was "encrytion"

[@Computerphile]

Oops, well that fix will have to wait a little while as I'm not at the computer! -Sean

[@Asterism_Desmos]

Relatable.

[@Dong_Harvey]

Maybe that spelling in itself was the encryption

[@KatyaAbc575]

@@Computerphile Writing from a phone? Technically a computer too!

[@sabriath]

Technically, the biggest hurdle is to prove that the public key is in fact for that person.....even an "authorizing server" can be MITM attacked and give out false public keys for anyone on the server, while creating throughput connections. With that, there's absolutely no way to defend against an MITM attack on a single line of communication. It's a rather big find if you can solve it. It goes back to the "2 generals problem" in similarity.

[@EwingTaiwan]

yeah! This is exactly my question! How would they know the public key they're receiving is actually Coming from the person who said he is? The key has to go through the network after all, and anyone in between can intercept and swap that, don't they?

[@CoughSyrup]

Yes there is, its called certificate pinning.

[@sabriath]

​@@CoughSyrup you do realize you completely missed the part where the attacker can intercept the certificate site right? Meaning I can plant my network right outside your home and intercept every single piece of data coming out of it. you: "hey pat, what's bob's public key?" fake pat: my public key returned to you, I request bob's public key for myself you: sends encrypted data with my key thinking it's bob fake pat: decrypts the data and re-encrypts it with bob's key and sends to bob with my address, changing any necessary information. When I receive it back, i decrypt and reencrypt with your key you: "oh, high bob, you are totally bob" nope...not at all, never was. Any event that can happen between your home and the wider network can be intercepted and everything forged for both sides. "I'll just VPN"....same problem, the VPN has to be handshaked for the connection, that handshake still passes through my jumped route, so all the data can be seen. "well what if we both had a authorizing server" then I'll just have an interceptor at both your location AND the recipient's location and jump both of you, so that I'll authorize fake certificates for you both. As I said, this attack can not be defended against using the same line communication. If I were to physically show up at your door and hand you an envelope with a secret code that only you and I know to identify each other, that can defend it....but that's a second line of communication, completely negating the premise I set.

[@wmrieker]

@@sabriath well theoretically it works because the certificate authority public keys are baked into the browser, so that is what holds the big house of cards up. now if you get a hacked browser with bogus ca keys then you are hosed.

[@sabriath]

@@wmrieker you assume that every site in the entire world has their keys stored on every computer in every household on the planet in order to ensure they are the actual correct website....and new registered websites somehow use a singularity pulse to insert their certificate in every browser in every house? That's not how CA works.....when you access a site, it requests a cert from an independent authority site to verify the site I'm accessing is the correct site. If I'm jumping your location, then when you request from the independent authority, you are talking to me, I just give you a fake certificate....and when you request from the other site to verify, it's also me, and I give you the answer key to the fake certificate. The only time this might not work is if your computer has already visited the site in the timeframe the certificate hasn't expired....then it's just a waiting game, or I can force an early retirement of the certificate, pushing you to re-request the certificate from the authority....and guess who you'd be talking to? Me. It's one of the biggest problems in cryptography right now, other than proof-of-time, but that deals more with blockchain tech.

[@Stafford674]

May I suggest a different analogy: The Bank night safe. You can see these on the outside of walls of banks. A local business man is give a key to open a small door to the safe. He then puts his days takings in the safe. The takings, which are in a sack, go down a chute into another safe in the bank basement. This case is deep underground, and can only be accessed inside the bank. It can only be opened by a special key that only the bank manager has. The next morning the bank manager opens the safe and takes charge of the takings. All business men can have the same key to make deposits and put cash into the safe. Only the bank manager has the key to open the safe the next day.

[@Dong_Harvey]

Drastically vulnerable to shitposting

[@benjidaniel5595]

Not bad but isn’t really analogous to *two way* secure communication.

[@absalomdraconis]

@@benjidaniel5595 : _Until_ you mention that all possible recipients have an equivalent safe.

[@olafzijnbuis]

Nice video about an interesting subject! If you ever do a remake, sequel, or similar video please: - Use 3 actual people Alic Bob and the Postman - Let them sit at a long table on one side - Place the camera so that all 3 are in the frame all the time - Replace the envelope with a transparent case so we can see the content all the time (maybe in the corner of the screen)

[@guilhermedantas5067]

Yes, the physical paper envelope was very cumbersome. Something "smarter" like a transparent box would be more practical and visually appealing.

[@satadorus5924]

@@guilhermedantas5067 Sure. I just lost track of the content of the envelope at times.

[@Valvex_]

@@satadorus5924 How do you lose track when they explain everything in pain stacking detail? Also if the box were transparent one could argue that some people might get confused because the postman "can just look inside, since it is transparent".

[@yeetyeet7070]

you seriously need this to be explained even simpler?

[@olafzijnbuis]

@@Valvex_ Right! Make the box half-transparent: the opaque side facing the people and the transparent side facing the camera.

[@Dong_Harvey]

Incidentally, the slow degradation and destruction of the envelope and subsequently the message is effectively a metaphor for the obsoletion of the protocols themselves. Overtime, the message exchange takes a lot of beatings from a lot of sources, which is to be expected, but that just means that plenty of 'Pats' are out their slowly observing this destruction and probing for weaknesses to exploit. Either Alice/Bob or the POST need to find out new protocols to protect themselves (getting a new envelope) , or maybe even the concept of exchange must change medium ( discluding the POST ).. And the band plays on

[@jann5s___]

I'm sorry, the analogy was hurting the story, it was too cumbersome. Maybe I'm just impatient

[@zxuiji]

Another attack vector is when pat has already figured out either party's secret keys and other verification details and just straight up pretends to be them from the outset, no extra connections. This can be mitigated by generating new keys for each connection and checking how long it takes for the target to respond an acknowledgement of the public key, true it doesn't stop fake connections but it outright stops attackers from considering pretending to be either party from the start as a viable attack vector as they would not have enough time to work out the secret key/s before passing it on, spend too long at the start and the connection will be abandoned by the creator, spend too long in the middle and the creator will flag as something fishy going on, most would be able to do is record the message in it's encrypted form and work it out after it's been passed on (don't have any ideas on how to mitigate that though)

[@absalomdraconis]

That can be _slightly_ mitigated by occasionally providing a new secret which requires a time-consuming process (like BitCoin's proof of work stuff) to turn into a usable form, but regretfully such attacks are likely to be targeted enough that such brute-force techniques aren't guaranteed to work. Better is to use out-of-band signalling to provide "unsnoopable" secrets, or some sort of quantum entanglement system to detect snooping, but neither of those things is trivially achievable for most communicators.

[@npexception]

"Nothinng on one, two is binding, click on three, back to one, little counter-rotation, aaand we got this open"

[@Richardincancale]

No one can open the padlock except the key holder - or the Lock Picking Lawyer!

[@cmuller1441]

You forgot Bosnianbill

[@abdallahmanasrah2317]

Behold the mighty plastic bottle shim

[@ornessarhithfaeron3576]

@@cmuller1441 He fell

[@AaronCossey]

Click out of 3, 4 is binding... And we dropped into a deep false set.

[@firehawk128]

Just wanted to chime in that I appreciated the envelope analogy, or at least having a tangible physical object represent the keys.

[@justiniani3585]

I love the ASMR quality of these videos

[@martinseal1987]

I get what they're trying to do here but they've actually made this more convoluted than it is

[@Max-dc7xr]

I would have to disagree, I though them using a kidda real world example made it easier to understand rather than them writing all of this information down. I guess different people just have different ways of learning and this is what works for me.

[@martinseal1987]

@@Max-dc7xr completely agree with your points

[@PushyPawn]

Not only have you guys covered parts of this process in previous videos but this one was rather clumsy, a bit messy and unnecessarily long.

[@jasonc3a]

Really like this guys presentation.

[@berthor0m1]

Great video, simple illustration of something that is actually quite complicated.

[@okuno54]

I lost it at "very rare numbers that you almost never find" XD

[@jackjack3358]

lol but you got what he means by that, right?

[@DM-qm5sc]

42, 69. wait does this mean the meaning of life is 69?

[@baronvonbeandip]

It was right in front of our noses the whole time. ( ͡° ͜ʖ ͡°)

[@sheetalgupta6202]

Great Explanation!! Loved it

[@Hooorse]

Thank you for your videos.

[@Doobiousmaximusable]

For visual learners, this video is a godsend for those who can't wrap their head around the encryption process.

[@BohonChina]

It felt like I was back to university and studied the flaw of protocol with logic analysis

[@RealCadde]

1:00 "No-one can open this lock except the person with the private key" ... "This is the Lockpicking Lawyer ... And it's open!"

[@gerdkah6064]

it would be nice if there was a real person Pat and show his (malicious) thoughts and possibilities whenever he recieves a package.. a well done visualization at all - thanks!

[@pokemettilp8872]

Wait a minute, that video in the end card isn't AES encryption, that is RSA!

[@qzbnyv]

I hope postman Pat’s black-and-white cat is still doing okay after all this time ♥️

[@kaitachi08]

Great video! It would’ve been a great plus to get a real third person involved as Pat, since I found it a tad confusing to follow at times, though.

[@zer001]

Wow, this is a great video.

[@bryanmantle4809]

Is there something in the protocol to say that the name has to match the public key? You may have said it in the video, but I missed it if so.

[@chunfung8934]

How about the public key exchange? Can “Pat” do something funky at the stage? There must be at some point that a plain text is sent over to each other to establish a secret, even though the plain text(s) might not both exist at the same time. But if “Pat” can capture all the messages from the very first beginning, can he reassemble everything and “recover” both public keys?

[@absalomdraconis]

That's really a different subject, though semi-related. How it works is that the software on your computer _already_ has several public keys when you first get it, and _those_ keys are used to communicate with trusted third parties that can provide you with any key that they've issued, and so _prevent_ the need to _ever_ send unencrypted data. However, even those keys are vulnerable to being either broken, or replaced before the software reaches you.

[@RK-ly5qj]

I see some similarities where MiTM is used for decrypt the traffic. Modern Firewalls NGF on layer7.

[@praveernarwelkar]

I think that this was a subtle way of talking about MITM attacks, though it would have been even better if there was a bit more emphasis on them.

[@gaptastic]

OK, now you're teasing me with manuscript paper, c'mon! Happy New Year!

[@mehdireza105]

I think it can be more simpler just to make sure Alice is talking to Bob and there is no MTM. Alice should not be using any lock (public key). Using public key pinning (finger print matching) Alice will make sure that he is using the Bob’s lock and not of the attacker.

[@davidg5898]

I really like Computerphile videos and Mr. Muller usually has great analogies, but this one really dragged on. Acting out the analogy for every single transaction brought the explanation to a painfully slow crawl.

[@MrCJBG]

24 minutes of showing people lock locks to envelopes, love the channel in general, could not deal with this video lol jeeeez

[@symonxd]

he sounds either Dutch or from the Netherlands

[@jetzereitsma1276]

Or from Holland

[@symonxd]

@@jetzereitsma1276 thats the Netherlands

[@lawrencedoliveiro9104]

Holland is in the Netherlands, isn’t it?

[@lawrencedoliveiro9104]

8:03 Why is secret-key (what he calls “symmetric key”) encryption preferred to to key-pair (public/private) encryption for the bulk of confidential communications, instead of using the latter all the time? Because key-pair encryption is on the order of 1000 times slower than secret-key encryption, that’s why.

[@silaspoulson9935]

is that due to more complicated calculations?

[@lawrencedoliveiro9104]

Needing to do arithmetic to hundreds or thousands of digits.

[@voidvector]

@@silaspoulson9935 Symmetric encryptions are mostly just repeated combination of -- key expansion, XORing with data, and shuffling bits around.

[@jaminant9691]

May your cup never run dry.🎉 You just saved an exam😂

[@Saka_Mulia]

This episode of Postman Pat is weirder than I remember the show being.

[@agentgalahad7473]

i cant be the only one who wants to rip that lock off and say "and now i am in possession of the secret"

[@OLLE3770]

Nice

[@stephenbenner4353]

These are two rare numbers that you’ll almost never find…Hitchhiker’s Guide, nice!

[@berzerkskwid]

nice

[@DJDavid98]

10:20 Nice

[@__nog642]

I think the main problem here is having a decryption oracle. There's no reason to send back the decrypted number to prove your identity. You just need to send each other a secret, combine them to make a shared secret, then start communicating with a symmetric tunnel. If they're able to do that, that proves they decrypted your number.

[@autohmae]

This is what Diffie-Hellman key exchange is

[@__nog642]

@@autohmae Sort of. Diffie-Hellman is kind of simpler. This would still involve encrypting and decrypting things, while Diffie-Hellman does not.

[@ZandarKoad]

Instructions unclear. Got papercut and died.

[@tomblitz22]

This isn't unique to Needham-Schroeder, ssh with key-based authentication has the exact same problem if the server doesn't identify itself within the challenge. Thanks for this video!

[@quantenschaum]

Now I know why it's called Patt-lock.

[@jriceblue]

With apologies: this video really should have started at @9:30 ...there was no need to step through those first basic steps five times. That was ... really tedious.

[@NetherFX]

Tim Muller sounds very dutch

[@DantalionNl]

AMA Tim Muller so we can ask him if he likes frikandelbroodjes

[@klaxoncow]

69? Nice.

[@gdclemo]

liked for the Head over Heels profile pic

[@laurendoe168]

All the while during the opening RSA analogy... I could not help thinking of the Lock Picking Lawyer. He'd use the tool that Bosnian Bill and he made.....

[@mikebeatstsb7030]

Y fourty too...?

[@danielg9275]

Hi this is the lock picking lawyer and today we’re going to break a private key

[@pyprogramming599]

lov your 0rtodox explainig videos. but understand 60% b'cause i speak spanish.

[@thebarnold7234]

wait Tim isnt talking about discrete maths and going to the pub? What kind of foul magic is this?

[@michaeljava8736]

Would be usedful to have a diagram of all the different scenarios that shows the steps taken for that scenario.

[@hpekristiansen]

I get is - all postmen are jerks - but surely not all are named Pat!?

[@JamesJohnAgar]

Should have done a man in the middle attack using computer terminals to show realistically that intelligence agencies can see/read people's email contents and not just the meta-data!

[@OcteractSG]

This is great, but we don’t live in a world where we have everyone’s public key.

[@tracyrreed]

Sure we do. Want my key? It's on the public key servers such as the one run by MIT. They can also be looked up in DNS records. I bet there are other ways public keys are being distributed too.

[@OcteractSG]

@@tracyrreed The problem here is that I don't know if I'm talking to the real MIT when I go to get its public key. This is the problem that certificates and certificate authorities address.

[@tracyrreed]

@@OcteractSG This is what the Web of Trust is for.

[@inoone3946]

why did you not use a lock with a 74 digit key a fingerprint sensor a key and a time lock a video could have been 20 times as long

[@talideon]

It would've been quite short: just wave a magnet over the lock to induce a current so the electronics panic and the lock pops open.

[@volkris]

The props did not help explain anything here. They just made it harder to follow especially as the props were not perfectly analogous to what they were trying to explain. Animations would have illustrated it better, but just dropping the props altogether would have improved this video.

[@tobortine]

I didn't think it was possible to make encryption sound even more boring than it usually does but you've exceeded my expectations.

[@kebman]

15:42 It's ok to go to dodgy websites. Don't sue me!

[@MungeParty]

How many masks was the camera man wearing?

[@voodooflux2152]

My dog is missing

[@lolatomroflsinnlos]

encrytion

[@TaliZorahVasectory]

Looks like the camera needs a haircut - its bangs are in the shot

[@thetommantom]

That is very difficult to understand and you said so much that I can't even remember I dont even remember if you said you were going to explain anything I feel like you just started saying a bunch of random stuff

[@BorjaTarraso]

You need 3 people to make properly this video with MITM scenario, instead of 1 pretending to be 2 people.

[@atiqkhaled8851]

Why don't bob just encrypted hello msg using Alice secret key. If Alice decrypt bob msg means key been exchange successful without mitm.

[@Lion_McLionhead]

Make this video with bible paper & whispering.

[@RobinHagg]

Cryptography is always fun but this never got my interest. I tried but ...

[@morpheusft7633]

This is all unnecessarily convoluted imo. Can't be bothered to finish watching it.

[@thenorup]

10:20 Nice!

[@dax86it]

I didn't know that Samwise Gamgee was a computer science expert

[@Zapto]

UwU

[@JaiLuthra]

69, nice

[@roshanthapamagar1318]

Haha 69😁

[@whywouldyouhitme]

First

[@shadmansakib9831]

69 NICE

[@PhoeniXfromNL]

nice video, I figure that even normies would be able to understand the subject, thumps up for that

[@josephwong2832]

Elon would love these codes!

[@BM-jy6cb]

Is this a clumsy attempt to avoid using the traditional "Eve" so as not to upset the wokerati?

[@MRGCProductions20996]

stop clicking your tongue, its infuriating

[@dp6igw977]

Too boring

[@cmuller1441]

Soooo loooong and booooring. Seriously, just use drawings to illustrate that like everyone does on this subject.

[@pokemettilp8872]

Just watch on 1.5x speed if it's too long for you

[@adamjasniewicz5796]

Nice