Feistel Cipher - Computerphile

[@charaniy7786]

Dr. Mike Pound, the man who can make anyone fall in love with Computer Science. Agree?

[@Diggnuts]

Actually, this made me extremely appreciative of the sociopolitical constructs in the late 16th century historical context of agriculture in central Europe.... Dunnu why, but it did!

[@damientownsend269]

Don’t pull that “agree” bs please.

[@ilovepudding7873]

Damien Townsend agree

[@damientownsend269]

ilovepudding 🤬🤪😖🤮

[@ctx4241]

Have I had this guy on uni, I might have masters right now. Instead, we were learning f@cking wordpress 😱.

[@willful759]

mike: "even if f is not reversable, that still decrypts it" me: WHAT!? mike: what?

[@martanvanderstraaten8448]

ivan pineda i mean that is because of the bitwise addition (xor). It actually makes quite a lot of sense.

[@therealquade]

@@martanvanderstraaten8448 how is bitwise xor going to find coprime factors?! that's madness

[@martanvanderstraaten8448]

therealquade that’s not how it works. It would add the hash bitwise to the thing you’d want to encrypt. If you then calculate the hash again and add it bitwise again (x-or) you added the same thing bitwise. Bitwise Adding is mod 2, so adding something 2x is adding something 2 mod 2 = 0 times. That’s why F can be anything.

[@YourMJK]

therealquade Did you watch the video? The reason is because a ⊕ b ⊕ b = a (since XOR is associative and b ⊕ b = 0)

[@therealquade]

@@martanvanderstraaten8448 if I have 2 different 1 way hash functions, which rely on prime numbers and common factors for N-Root, because exponents are faster to calculate than roots, How is, in any system, Running that hash function twice, Ever going to reverse itself? The XOR's are going to be reversed, but the hash functions won't be.

[@desmondbrown5508]

This is a very cool algorithm. I absolutely love Mike's response to the fact it reverses one-way hashes at 2:54 - 3:07.

[@ehtuanK]

It doesn't reverse them, it eliminates them via xor. There's a difference, but for some reason many people in the comments don't seam to get it.

[@ZT1ST]

@@ehtuanK The thing that surprises people is that the cipher is reversable, even if the hashes themselves are one-way.

[@lawrencedoliveiro9104]

2:56 The key lies in observing that each half of the original data block does not go *through* the F-block to get to the next stage. The only use of the output of the F-blocks is to xor with data blocks. And xor is reversible: xoring with the same bitstream twice gives you back the original bitstream. That’s why the same sequence of bit-mashing works for both encryption and decryption. It really is that simple.

[@profdaveb6384]

Thank you!

[@thesvodnik]

Wow, now it makes sense from a theoretical standpoint as well. Great explanation.

[@q_5ta871]

Absoulotly lovly thx for sharing

[@darshanex]

Hi there, non native English speaker here - love this channel - one small suggestion if you can please provide English subtitles that would be awesome thank you!

[@Jamie-st6of]

As a native English speaker, I need subtitles as well! It's honestly unacceptable for such a large channel to have no subtitles.

[@MaxDiscere]

As a non-native speaker I understand everything. It's just a little accent just get better at english then you'll understand it with ease

[@darshanex]

@@MaxDiscere Yes I get that, but it's the content that featured in the videos have some words that you have to listen twice to understand sometimes.

[@lorddraagon]

As an Alien, I need subtitles as well !

[@caw25sha]

@@Jamie-st6of Subtitles are automatically generated by KZbin. Can uploaders choose whether or not to have them?

[@ThisIsAli_Off]

This is the first in my life that my exam preparation for uni leads me to a channel that I already used to watch in my free time and that genuinely excites me. First time I want to "learn" something instead of memorize how it works for the sake of the exam. Damn.. I am shocked

[@perburr]

Same here! My network security exam's next week. I've been binging these computerphile security videos and it's so satisfying how I can now understand what's being explained in these videos, compared to when I watched them at the start of my course.

[@perburr]

Did you end up doing any research/projects after you did your exam? I'm not gonna lie, I want to spend hours poring over RFCs or security mechanisms/protocols like tls/aes/ipsec/802.x authentication etc after I finish my exam

[@truppelito]

Video was too short for such an interesting concept!

[@jensdanielandersen]

I just started learning about the Feistel Cipher structure this week in my bachelor security program for college and was a bit confused reading about it in my textbook. After watching this, it makes a lot more sense. Thanks again Mike, you are a great teacher.

[@fllthdcrb]

IIUC, it doesn't even have to be a single function; you could even use totally different functions for the "rounds", and it would still be reversible. In fact, the same function with different keys can already be seen as different functions from the point of view of the Feistel network.

[@Arwahanoth]

All you need to do is reverse the order of applied functions like the part of the key (k1-F1, k2- F2) => cipher => (k2-F2, k1-F1) right ?

[@fllthdcrb]

@@Arwahanoth Exactly. Not sure how useful it would be, but it should be possible, at least. Heck, even the key is optional. Not that you'd want to leave _that_ out; otherwise, it's no longer a proper cipher, just an obfuscation function, but again, it can be done.

[@adamspihlman9665]

I want someone to talk about me the way Dr. Pound talks about Feistel Ciphers

[@ilovepudding7873]

Dont we all

[@santizdr]

The one and only video that explains Feistel Networks in a simple but understandable way. Thnx so much

[@perburr]

My uni lecturer mentioned the Feistel cipher in passing and brushed it off as extra reading. I'm very glad I came across this video, mind blown!!! 🤯🤯🤯

[@totlyepic]

Always excited for a Mike Pound video. Always excited for a crypto video. You've given me a happy morning.

[@BulletHellspawn]

Love this dude

[@KanaalMTS]

Man love is real

[@jonathanblackwell42]

If you heard a boom...that was my head exploding.

[@anonymousvevo8697]

i can listen to this guy talking all day long, amazing video never gets old thanks

[@XBrainstoneX]

Another cool thing about this IMO is the reason why XOR is reversible: On a single bit, the XOR function is the same as addition mod 2. Therefore, taking XOR of two bitstrings can be seen as addition in the vector space (F_2)^n. This is the reason why the XOR function is associative, commutative and that x XOR x = 0 for all bitstrings x. And that is also why Mike uses the plus symbol for XOR in his drawing.

[@misterhat5823]

I've always seen XOR as selective bit inversion. That makes it very easy to see why it's reversible.

[@helloarigato]

Love Dr. Pound! I would happily watch a video of him reading the Mr. Wimpy menu.

[@treyquattro]

Mike Pound is one of those things in cryptography where you just think, "Wow, he's very clever". It's not often I click like before watching a video, but when I do it's for Dr. Mike

[@HeinusHoratius]

@MichaelKingsfordGray Yes. And what of it? We're proud Pound-groupies! 😂

[@lawrencedoliveiro9104]

OK, here’s a fun thought: how would you generalize this idea to a base other than 2? For example, base-26, using the letters of the (uppercase, unaccented) English alphabet? The obvious answer is to do arithmetic modulo 26, assigning numerical values like A = 0 ... Z = 25. The symmetry of xor would no longer apply, so you would need separate encryption and decryption blocks: the encryption blocks would use addition in place of xor, while the decryption ones would subtract.

[@Demki]

Maybe it's because I've been dealing with group theory a lot lately, but another way to see this, is if we denote applying a single round as r and swapping left and right as s, and using juxtaposition for function composition, we first prove that srsr=id (=the identity function, this is proven directly from the properties of xor), so srs=r^(-1). Now noticing that s=s^(-1) we have that the mapping g(x)=sxs is a group homomorphism. Now we actually have different rounds, so lets denote them r1,r2... and so on, and indeed srk...r2r1 sr1r2...rk=g(rk...r2r1) r1...rk=g(rk)...g(r2)g(r1) r1r2...rk=rk^(-1)...r2^(-1)r1^(-1) r1r2...rk=id

[@zarmmraz5267]

you just saved my cyber security lectures. dude I love you

[@gaius_enceladus]

Amazing stuff! Super elegant! I just *love* elegant algorithms! That's one reason that I love functional programming languages so much. I'm not very good at *coding* in them but I hugely appreciate their elegance.

[@quibster]

can't unsee 'rofl' in R⊕F(L

[@leonhardeuler9839]

Yet another cryptography topic explained flawlessly by Mike.

[@treyquattro]

add a thumb for yourself, Leonhard

[@danhorus]

A short video so rich with information. I really enjoyed learning about this.

[@Furiends]

The crossing x-ors ensure that information can be reversed via what ever algorithm is used in between.

[@preferredimage]

1:08 "It's a structure" :)

[@riccardoorlando2262]

Handwaving when explaining scientific concepts is mandatory. They won't give you a PhD if you can't handwave in a sufficiently cryptic yet empathetic manner.

[@TheNasaDude]

They HAND you your Ph. D. after all

[@Andrew90046zero]

3:04 kinda random, but that was the best sounding "mind blown" sound I've ever heard.

[@jmkyarrow]

I loved it too - I've come back just to hear it again

[@bhishmaacharya7535]

This channel shares amazing contents. One thing I can't take from their video is sound of pen against paper.

[@srividyakrishnakumar6895]

That was such a wonderful video! It's always so fun and interesting watching Dr. Mike Pound's videos. @Computerphile, would love it if you could organize all the crypto videos into a playlist.

[@ForTheNerds]

More and more I'm getting into ciphers to begin with was for cybersecurity research but now its mostly because it's so damn interesting. Love this, thank you. Very clever.

[@MrDeekaph]

I'm doing a cryptography course and was still unclear after the professor's lecture and the textbook so I went to youtube looking for something better, and this is it. All that money spent on instruction and the best instruction is free on youtube. Go figure.

[@kvelez]

0:21 DES 2:44 Decryption. 3:33 Keys and function. 5:00 --> 5:54 XOR decryption.

[@Czeckie]

there really should be a computerphile playlist with all the crypto stuff

[@55cancri_e76]

wow thank you so much it is really amazing how you explain it in a very simple way. Currently Im taking Applied Cryptography in the University it is my third year and I was struggling with this topic but NOW it's my favourite. Thanks again

[@malikkashifsaeed1938]

who is the man behind the camera? he listens to the lec very carefully and asks valid and authentic questions.

[@Demonslay335]

This is so much easier to understand than just reading thru the wiki page, thanks! Been studying a lot of block cipher internals and never quite grasped this simple concept before for some reason - until now.

[@biswajeetbehera2912]

One of the best explanations on the topic feistel ciphers.....😇

[@gabrielamorim8316]

Thanks for the help. Passed my coursework because of this video =)

[@aliyildirim6134]

Mike brought you here I know, love Mike.

[@olamarvin]

The Pound function: A video with Dr Mike Pound is posted -> I click it.

[@dylankrejci9965]

Be careful tho - that function isn't CPA secure!

[@maryjohansson5542]

Horst Feistel was my dear Uncle. A great man!

[@robertsedgewick1266]

Brilliant work as usual - you always manage to simplify these complex security concepts!

[@BytebroUK]

Could we maybe do another vid of this; about cryptanalysis of Feistel networks? Maybe specifically DES and AES256, and see how that pans out :) ? There are some really interesting papers out there.

[@jaredbitz]

When he first said that plugging the cipher text back into the same algorithm decrypted it, I just had to pause the video and go work it out myself on a whiteboard. I think that says something about how well-executed this explanation and the dramatic reveal were!

[@mikerope5785]

The safest encryption keys are not stored on a computer for the purposes of encryption, but blend in to a normal life. And are mutually agreed upon in person. They are never written to disk or on non-edible paper.

[@DaveWhoa]

why do you still have printing paper with spool-holes

[@gregwochlik9233]

Very nicely explained. I have worked with DES cryptography earlier in my career.

[@TheMasonX23]

Amazing video as always! Dr Mike Pound never disappoints (ay-oh) with his enthusiasm for computer science, and the Feistel Cipher is incredible in how it "magically" reverses things. Dr Brailsford really explained XOR well in another video, for anyone lost in the dark.

[@crystalspeed7214]

I kinda wish he did a example with letters and functions cause while this is cool as a high schooler this kinda broke my brain

[@DMan44487]

It's like the butterfly swap of ciphers.

[@MrWylis]

I started a Masters in Computer Systems and Software Engineering at UoY in 1998 (gulp!) and I had no interest whatsoever... But... When you explain it, I can't get enough and now wish I'd completed my degree.

[@ywanhk9895]

If this dude was a CS professor, he would be THE BEST ( *NOT one of the best* ) professor in the world

[@TheSam1902]

As always, videos featuring Dr Mike Pound are super duper interesting ! Thank you for your time :)

[@rishavtiwari2017]

Can you please make a video on ROUND FUNCTION? It would be great if you do it

[@issam2901]

Writing with a highlighter like a maniac 😂😂😂

[@ishanlamsal7504]

i have been trying for 3 days to understand this for exam, and here I go after 3 days and 8 mins I finally understand. Thank you so much

[@gaborm4767]

Can you please make a video about DES? I would like to understand how is 6to4 bit substitution reversible. Thanks.

[@parthvasoya3562]

man what an awesome explanation

[@abidhossain8074]

mike: "even if f is not reversible, that still decrypts it" me: what? mike: what?

[@georgelza]

Love his presentations... makes very complex subjects so easy to follow

[@ירדןחי-ע3ז]

The video in excellent! One question. On DES cipher, there are 16 rounds, which means 16 keys for any round any 16 functions. Are the functions are different between rounds? (The question regards to DES and not to Feistel)

[@stanrogers5613]

No, in DES, the function (an XOR with a rotation of a subkey, then a sub-block substitution box of the output of that, followed by a permutation of the entire block) is the same for each round. The only difference between rounds would be the initial expansion of the data block from 32 bits to 48 bits on encryption (prior to round 1), and the collapse back to 32 bits from 48 bits on decryption (after round 16).

[@alexp4448]

Why does it seem like this guy has 12 offices. They never seem to record his segments in the same place twice

[@zss123456789]

This probably sound silly since it is the first time I'm learning about Feistel Cipher, but I think there might be a problem. It looks like if you know the encryption function and key2 in this example (whichever one gets used first for decryption), you can already know what half of what the original message was without having key1.

[@madhoyen]

This happened because he only did two rounds. Normally ones does many rounds of this, each with a different subkey, which would not expose it like this.

[@misterhat5823]

In addition to Markus said, the message would be split into blocks. So you'd know every other block (assuming just two passes) and that might not be very helpful. Especially if blocks are scrambled before being encrypted. Or if the block size was extremely small. Like one ASCII character. Knowing 4 bits of the 8 that make up one character would be useless.

[@deathtotruthers1]

Could someone explain the role of XOR here? My understanding is that XOR returns true if two inputs are different, and false otherwise. How does it work in this cypher? Wouldn't L ⊕ F(R, k1) just return true? Am I missing how XOR is being used in this context?

[@stanrogers5613]

The XOR is bitwise, not a logical XOR of the "truthiness" of the entire value.

[@caw25sha]

Is the verb of XOR xorcise?

[@karimabdulahi502]

How did you know we had a lecture about this this week?

[@annagiordano8709]

why if we use only one round the feistel network is not secure?

[@maxdemian6312]

But why is the the final flip required?

[@zackmack7145]

why the final operation in a Feistel cipher is an additional swap operation? can someone explain for me quick

[@venkoshop4124]

3:04 that "boof" sound is soooooooooooo satisfyinggggggg

[@mrkrisey4841]

I cant believe that you say that if "f" is not reversable, it still decrypts it. What if I used like SHA256, would it still work?

[@dingo_prod]

A link for an Xor explaination video??

[@Venistro]

How is it reversable, even if f is for example a not reversable hash function?

[@misterhat5823]

Because F can be anything. Go back through the analysis with F=0 as a function. It still works just fine.

[@catcatcatcatcatcatcatcatcatca]

How does XOR-function work? you should add video about it as a card. Or then my cards aren't working, in which case adding it to the description or in comments would be nice.

[@ITR]

Xor takes each bit and compares it to another, if they are not the same, it outputs the bit 1, otherwise 0. So the truth table is something like: 0 xor 0 => 0 0 xor 1 => 1 1 xor 0 => 1 1 xor 1 => 0

[@furrane]

You can remember xor stand for "exclusive or" mean one or the other, but not both. That's how I do it.

[@alimanski7941]

@@ITR You have it the other way around: if they are *not* the same, it outputs True (or 1), otherwise False (0)

[@ITR]

@@alimanski7941 Thanks, forgot the not, fixed now.

[@DavidvanDeijk]

"or but not both"

[@carlosmspk]

If we did an extra round, would we still need to switch in the end?

[@RawPeds]

So if I have a hash function and I put it into a Feistel Cipher I can get back the original message?

[@Synthetica9]

I just had a lecture about this (by one of the inventors of AES) today, what are the odds?

[@abdelrhmanahmed1378]

Round func can be anything right?Iike just simple ceaser cipher?

[@hikaroto2791]

can you use cipher to reverse a ratchet?

[@anorld80]

What are we doing in this Function, F(Rn-1,Kn) are we ANDing or XORing R with key before we XOR function result with Ln-1

[@UntakenNick]

So it makes an irreversible function reversible? If there's any way to get the original data back then it means the function is not irreversible anymore..

[@privateshark5532]

The function itself is irreversible. If you were to take the plaintext and simply put it into the function, you wouldn't be able to get it back out again. What happens here is that you keep the original plaintext and XOR it with irreversibly mutated content. The network is set up in such a way that the irreversible parts cancel out on decryption and the original plaintext comes back out again.

[@UntakenNick]

@@privateshark5532 So you need to keep the original content all along? What's the point of decrypting it then? I know there's something I missing and not something wrong with the method, but with the explanation given here that's an obvious question that comes out.

[@privateshark5532]

@@UntakenNick you don't need to keep the original content. Recall that the final result is something like L (+) ... and R (+) ... so the original strings are still in there, you need to cancel out the stuff you added

[@DavidAspden]

Love the videos but can't help link Mike and James McAvoy in my head.

[@pigboiii]

When he did the "what 🤯", that was the reason I came to this video.

[@dannylarsen635]

so did you crack or create the zodiac cipher?

[@LemonChieff]

Ok I'm not even gonna begin to pretend I understood most of this but. Would it be correct to assume that a Feistel Cipher is a symmetric key algorithm? I mean since the encryption and decryption function use the same exact algorithm…

[@aoe9857]

Yes it is, not because it uses the same algorithm, but because it uses the same key (or rather set of keys).

[@LemonChieff]

@@aoe9857 Bad semantics on my part. I said "algorithm" when what I really meant was "function" in this case "F". Which indeed isn't the same. Thank you for the clarification. :)

[@fchurca]

Not quite; it is if you use the same subkey for each stage, but if you use different subkeys you have to turn the order around, effectively having a different key for decription and encryption. Even if it's trivial to derive each one from the other, they are different keys. For example: You use a 32-bit key 0xDEADBEEF for encrypting 16-bit blocks, with two rounds. K1 would be 0xDEAD and K2 would be 0xBEEF. For decryption, you would use the same algorith but with 0xBEEF for K1 and 0xDEAD for K2. The decryption key would be 0xBEEFDEAD, different to the encryption key, so it would be an asymmetric key. It could be argued that the encryption and decryption keys can be derived from each other trivially, but the key is that they are different keys. This comment clearly not sponsored by PETA.

[@LemonChieff]

@@fchurca I… I really can't focus without my adhd meds but I'm sure this makes sense. " The decryption key would be 0xBEEFDEAD, different to the encryption key, so it would be an asymmetric key." I mean… That's not what I mean. If A encrypts "Hello" with that function F, B can only decrypt it using the same function F and if either A or B were to encrypt "Hello" the output of the encryption scheme would be the same, wouldn't it?

[@g2g591]

@@LemonChieff if the rounds had the exact same F and the exact same key then it would be symmetrical. I think.

[@matthaigh5296]

I thought his speciality was graphics, seems to me he knows everything!

[@Hexanitrobenzene]

Yeah, cryptography and computer graphics are completely different fields. I was also astonished...

[@devotee9606]

Hay Mike Can you please explain the code of this cipher by showing us real example.

[@cornjulio4033]

Please do this channel alone, Mike ! We don't need the others !

[@ChaoticRain1]

I am concerned by his choice of writing materials though... do computer scientists not use sharpies like everyone else?

[@JMezzy02]

Super helpful. Thank you!

[@LVusaAPI]

Brilliant job 👍

[@un4v41l48l3]

I've watched this four times now. Here's the only question I have left... This is a reversible encryption that remains secure as long as the keys are secure. BUT IS IT? That's not a given. Consider, for example, a scheme that simply XOR's the key with the input. If the key is unknown then the output is nonsense... UNLES the input is too long. Then the key can be extracted. If we assume the hashing functions used in the feistel cipher are secure, can we therefore conclude that the entire cipher is secure?? In other words: Where are the limits of this cipher's integrity? (The limit of my brain's integrity is about this time of night.)

[@banquoF]

Am I missing something but if this is reversible isn't that a vulnerability?

[@sly1024]

It means it's decryptable. If it wasn't reversible, you wouldn't be able to decrypt it. As long as you keep the keys secret, it's not more vulnerable than DES or AES.

[@AmnonSadeh]

An example (with a small block of bits and a simple function) could have been nice.

[@scott2495]

I wish i had Mike Pound's brain

[@thounilo]

Is this useful to open your face with a phone?

[@heisenmountainb6854]

did you get any of that?

[@DJAlax909]

This is simple yet confusing at the same time... Bravo Sir