Feistel Cipher - Computerphile

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

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

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

[@adamspihlman9665]

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

[@ilovepudding7873]

Dont we 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.

[@BulletHellspawn]

Love this dude

[@KanaalMTS]

Man love is real

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

[@totlyepic]

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

[@truppelito]

Video was too short for such an interesting concept!

[@santizdr]

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

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

[@zarmmraz5267]

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

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

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

[@anonymousvevo8697]

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

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

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

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

[@danhorus]

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

[@leonhardeuler9839]

Yet another cryptography topic explained flawlessly by Mike.

[@treyquattro]

add a thumb for yourself, Leonhard

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

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

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

[@bhishmaacharya7535]

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

[@gabrielamorim8316]

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

[@issam2901]

Writing with a highlighter like a maniac 😂😂😂

[@Furiends]

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

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

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

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

[@kvelez]

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

[@biswajeetbehera2912]

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

[@robertsedgewick1266]

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

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

[@malikkashifsaeed1938]

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

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

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

[@aliyildirim6134]

Mike brought you here I know, love Mike.

[@Czeckie]

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

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

[@TheSam1902]

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

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

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

[@zackmack7145]

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

[@gaborm4767]

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

[@gregwochlik9233]

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

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

[@abidhossain8074]

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

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

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

[@DaveWhoa]

why do you still have printing paper with spool-holes

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

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

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

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

[@RawPeds]

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

[@rishavtiwari2017]

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

[@parthvasoya3562]

man what an awesome explanation

[@georgelza]

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

[@annagiordano8709]

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

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

[@ywanHK]

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

[@carlosmspk]

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

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

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

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

[@caw25sha]

Is the verb of XOR xorcise?

[@karimabdulahi502]

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

[@LVusaAPI]

Brilliant job 👍

[@dingo_prod]

A link for an Xor explaination video??

[@venkoshop4124]

3:04 that "boof" sound is soooooooooooo satisfyinggggggg

[@maxdemian6312]

But why is the the final flip required?

[@devotee9606]

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

[@Synthetica9]

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

[@JMezzy02]

Super helpful. Thank you!

[@FormulaXFD]

I always love this stuff.Thanks for making these!

[@dannylarsen635]

so did you crack or create the zodiac cipher?

[@hikaroto2791]

can you use cipher to reverse a ratchet?

[@Vogel42]

is the last step necessity ? RL -> LR

[@theohenson7283]

I assume it is needed so that the output can be reversed. If the last step wasn't there you couldn't decrypt by running it again.

[@TheJayCZ]

Not necessarily, but then you'd need to flip a few things around in the decryption algorithm, hence breaking the symmetry.

[@theohenson7283]

@@TheJayCZ yeah that's what I meant. It is needed if you want to directly take the output and put it in the input to decrypt

[@flagpoleeip]

Where do you get that paper?

[@pdrg]

Damn that's clever

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

[@homomorphic]

Thanks for covering feistel networks. I would have expected it to be one of the first things that this channel ever covered, but better late than never 😃

[@scott2495]

I wish i had Mike Pound's brain

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

[@Dj_Alax909]

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

[@mheermance]

Wow, that is amazing.

[@doot2359]

2:56 i literally said: this is madness 🤯

[@heisenmountainb6854]

did you get any of that?