Feistel Cipher - Computerphile

One of the most elegant solutions for cryptography. Dr Mike Pound explains one of his most favourite ciphers.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottsco...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@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.

[@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

[@adamspihlman9665]

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

[@ilovepudding7873]

Dont we all

[@BulletHellspawn]

Love this dude

[@KanaalMTS]

Man love is real

[@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

[@quibster]

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

[@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!!! 🤯🤯🤯

[@santizdr]

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

[@helloarigato]

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

[@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

[@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

[@Furiends]

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

[@zarmmraz5267]

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

[@issam2901]

Writing with a highlighter like a maniac 😂😂😂

[@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.

[@malikkashifsaeed1938]

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

[@abidhossain8074]

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

[@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.

[@venkoshop4124]

3:04 that "boof" sound is soooooooooooo satisfyinggggggg

[@maryjohansson5542]

Horst Feistel was my dear Uncle. A great man!

[@aliyildirim6134]

Mike brought you here I know, love Mike.

[@bhishmaacharya7535]

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

[@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!

[@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.

[@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

[@DaveWhoa]

why do you still have printing paper with spool-holes

[@ירדןחי-ע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).

[@gaborm4767]

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

[@pdrg]

Damn that's clever

[@zackmack7145]

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

[@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

[@karimabdulahi502]

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

[@scott2495]

I wish i had Mike Pound's brain

[@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"

[@abdelrhmanahmed1378]

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

[@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.

[@parthvasoya3562]

man what an awesome explanation

[@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.

[@Stierguy1]

neat involution

[@dannylarsen635]

so did you crack or create the zodiac cipher?

[@doot2359]

2:56 i literally said: this is madness 🤯

[@dingo_prod]

A link for an Xor explaination video??

[@mheermance]

Wow, that is amazing.

[@DJAlax909]

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

[@ABDULKARIMHOMAIDI]

Thanks Man !!

[@karlfimm]

Excellent. I found some source code for Fiestel Network based encryption 20 years ago and used it when I needed some 'light' encryption ever since, but never knew the underlying structure. Thanks.

[@Harmonikdiskorde]

This looks like a game of hopscotch.

[@jonasgastecker8732]

this is madness

[@stevewilsonraj]

thanks a lot !!!

[@Ko_Zilek]

Could the Feistel Cipher the be divided more than just half; Say Left Middle Right. Or First 1/4 . . . Fourth 1/4. Or Etc. Would, could it still work? Like I am thinking it could, if it's structured the same way, like. For Left Middle Right; First layer would have the middle and right have a function done, then both Middle and Right are both xored with Left, Left is moved to the Right side Middle to the Left side Right to the Middle etc. Hmmm... I have no idea. This is hard to visualize in text lol. Seems like it should work?

[@Tsudico]

I think it might make the cypher more complex, but might be possible. One thing you might be able to do is use a feistel cipher as the functions in the larger feistel cipher, so do it recursively.

[@jaaval]

As long as each step retains what goes in to the round functions then it is reversible in theory. if you want the same network to reverse it you have to think about which block goes where very carefully so that correct blocks get xorred.

[@sebastianzander87]

Does the output size of the F function matter and does its output size has to equal the size of the input blocks? I am asking because of the XOR operation. I don't know if or how you can xor a larger left block with a (possibly) smaller F-processed right block. Say we use "SHA-256" and we receive 256 bits from the F function; would we then loop over the left block in 256 bit increments and perform the XOR and optionally pad the left block input so it is a multiple of 256 bits? Or do you have to have a block size smaller than or equal to the 256 bits in my example? I have not tried it myself but I sure am going to try it soon in C or Python.

[@romajimamulo]

This method only works if they're all the same size, unfortunately he didn't get into how to handle them being different sizes

[@misterhat5823]

@@romajimamulo Why wouldn't it work. You can pad or truncate the output of F. F can be anything. Even F=0 works. (Not very secure, but it works.)

[@romajimamulo]

@@misterhat5823 don't ask me, I don't know

[@flagpoleeip]

Where do you get that paper?

[@AmnonSadeh]

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

[@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.

[@AboveEmAllProduction]

I see Mike i upvote

[@helloarigato]

I love this

[@cornjulio4033]

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

[@fouzaialaa7962]

i knew its the XOR that makes it reversible before he even said it !!!! i have to say !! this Cipher is super cool

[@AmineOnline]

Stunishing

[@dimitriouchemistry2215]

If what you said is true, why can't we use something like this to reverse hash functions, and not have to bother cracking passwords the hard way?

[@Demonslay335]

Because the whole point is how the function is cancelled out when decrypting, meaning the fact of it being a hash function or not is irrelevant. Also, the full input isn't technically put thru the function as one. It's a different concept to how hashes work.

[@baymax1550]

Wow

[@recklessroges]

meme://{surprised pikachu face}/ I'm going to have to write this in Rust because, (sorry Dr Pound) my brain is still incredulous.

[@justdoityourself7134]

This works if the output size of the Hash equals the size of the Block consumed. No Magic here. Conservation of Energy/Entropy.

[@hexawookie8204]

finally

[@AceBanyon]

Just keep the camera on the paper. The constant cuts between paper and face are too distracting.

[@shoutitallloud]

Witchcraft ! Black magic!

[@DrakoonLP]

Almost 2^12 Likes

[@DeusExAstra]

Witch!

[@fieryweasel]

Spare a thought for the poor animator.

[@yup8388]

It should be called ROFL cipher

[@SkinnyCow.]

What is that thing on his forehead?!?!?

[@privateger]

Have you never seen a pimple?

[@doommaker4000]

Where tf do you live if you haven't seen one?

[@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 😱.

[@jonathanblackwell42]

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

[@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?

[@truppelito]

Video was too short for such an interesting concept!

[@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.

[@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.

[@totlyepic]

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

[@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.

[@thenasadude6878]

They HAND you your Ph. D. after all

[@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.

[@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.

[@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.

[@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.

[@empyyrus]

For once I'm actually extremely early

[@johanvandermerwe7687]

😂😂👌same

[@alb6404]

Empyrus same

[@empyyrus]

@MichaelKingsfordGray idk who asked you for your opinion man but I'm pretty sure I am even more literate than you, I just don't take the internet seriously all the time like you do apparently,... big guy

[@Chalisque]

Looking at Ro(Lo(F(k...)) and keep reading it ROFLMFAO

[@ywanhk9895]

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

[@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.

[@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! 😂

[@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!

[@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.

[@danhorus]

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

[@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.

[@kvelez]

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

[@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

[@caw25sha]

Is the verb of XOR xorcise?

[@devotee9606]

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

[@biswajeetbehera2912]

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

[@HarzemTube]

KZbin auto subtitles trying to understand "feistel": firestar five-star fascial hortz feistel (the only time it got right is the name of the inventor) firestore fiesta five society physical firestore visual file so faster cypher faster psychopath

[@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?

[@qmurec]

love this channel, but you guys really need to polish your thumbnails...some rather unflattering image choices on most of your videos IMHO