Feistel Cipher - Computerphile
HTML-код
- Опубликовано: 13 окт 2024
- 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
mike: "even if f is not reversable, that still decrypts it"
me: WHAT!?
mike: what?
ivan pineda i mean that is because of the bitwise addition (xor). It actually makes quite a lot of sense.
@@martanvanderstraaten8448 how is bitwise xor going to find coprime factors?! that's madness
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.
therealquade Did you watch the video?
The reason is because
a ⊕ b ⊕ b = a
(since XOR is associative and b ⊕ b = 0)
@@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.
Dr. Mike Pound, the man who can make anyone fall in love with Computer Science. Agree?
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!
Don’t pull that “agree” bs please.
Damien Townsend agree
ilovepudding 🤬🤪😖🤮
Have I had this guy on uni, I might have masters right now. Instead, we were learning f@cking wordpress 😱.
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.
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.
@@ehtuanK The thing that surprises people is that the cipher is reversable, even if the hashes themselves are one-way.
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!
As a native English speaker, I need subtitles as well! It's honestly unacceptable for such a large channel to have no subtitles.
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
@@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.
As an Alien, I need subtitles as well !
@@Jamie-st6of Subtitles are automatically generated by RUclips. Can uploaders choose whether or not to have them?
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.
Thank you!
Wow, now it makes sense from a theoretical standpoint as well. Great explanation.
Absoulotly lovly thx for sharing
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.
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 ?
@@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.
Video was too short for such an interesting concept!
Love this dude
Man love is real
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.
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
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.
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
I want someone to talk about me the way Dr. Pound talks about Feistel Ciphers
Dont we all
If you heard a boom...that was my head exploding.
Always excited for a Mike Pound video. Always excited for a crypto video. You've given me a happy morning.
can't unsee 'rofl' in R⊕F(L
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.
I've always seen XOR as selective bit inversion. That makes it very easy to see why it's reversible.
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!!! 🤯🤯🤯
The one and only video that explains Feistel Networks in a simple but understandable way. Thnx so much
Love Dr. Pound! I would happily watch a video of him reading the Mr. Wimpy menu.
1:08 "It's a structure" :)
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.
They HAND you your Ph. D. after all
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
@MichaelKingsfordGray Yes. And what of it? We're proud Pound-groupies! 😂
i can listen to this guy talking all day long, amazing video never gets old thanks
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
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.
Yet another cryptography topic explained flawlessly by Mike.
add a thumb for yourself, Leonhard
you just saved my cyber security lectures. dude I love you
A short video so rich with information. I really enjoyed learning about this.
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.
3:04 kinda random, but that was the best sounding "mind blown" sound I've ever heard.
I loved it too - I've come back just to hear it again
who is the man behind the camera? he listens to the lec very carefully and asks valid and authentic questions.
The crossing x-ors ensure that information can be reversed via what ever algorithm is used in between.
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.
Writing with a highlighter like a maniac 😂😂😂
This channel shares amazing contents.
One thing I can't take from their video is sound of pen against paper.
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
The Pound function: A video with Dr Mike Pound is posted -> I click it.
Be careful tho - that function isn't CPA secure!
One of the best explanations on the topic feistel ciphers.....😇
Mike brought you here I know, love Mike.
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.
0:21
DES
2:44
Decryption.
3:33
Keys and function.
5:00 --> 5:54
XOR decryption.
there really should be a computerphile playlist with all the crypto stuff
Thanks for the help. Passed my coursework because of this video =)
Horst Feistel was my dear Uncle. A great man!
Brilliant work as usual - you always manage to simplify these complex security concepts!
mike: "even if f is not reversible, that still decrypts it"
me: what?
mike: what?
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.
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.
3:04 that "boof" sound is soooooooooooo satisfyinggggggg
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.
man what an awesome explanation
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!
Very nicely explained. I have worked with DES cryptography earlier in my career.
Love his presentations... makes very complex subjects so easy to follow
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)
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).
As always, videos featuring Dr Mike Pound are super duper interesting ! Thank you for your time :)
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.
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.
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.
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.
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
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.
Brilliant job 👍
why do you still have printing paper with spool-holes
It's like the butterfly swap of ciphers.
Damn that's clever
Super helpful. Thank you!
How did you know we had a lecture about this this week?
Can you please make a video on ROUND FUNCTION? It would be great if you do it
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.
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
You can remember xor stand for "exclusive or" mean one or the other, but not both. That's how I do it.
@@ITR You have it the other way around: if they are *not* the same, it outputs True (or 1), otherwise False (0)
@@alimanski7941 Thanks, forgot the not, fixed now.
"or but not both"
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…
Yes it is, not because it uses the same algorithm, but because it uses the same key (or rather set of keys).
@@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. :)
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.
@@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?
@@LemonChieff if the rounds had the exact same F and the exact same key then it would be symmetrical. I think.
If this dude was a CS professor, he would be THE BEST ( *NOT one of the best* ) professor in the world
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?
The XOR is bitwise, not a logical XOR of the "truthiness" of the entire value.
Can you please make a video about DES? I would like to understand how is 6to4 bit substitution reversible. Thanks.
Wow, that is amazing.
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
I always love this stuff.Thanks for making these!
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.
I just had a lecture about this (by one of the inventors of AES) today, what are the odds?
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
This is simple yet confusing at the same time... Bravo Sir
this is madness
Please do this channel alone, Mike ! We don't need the others !
I see Mike i upvote
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 😃
MIKEEEEEEEEE
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.)
How is it reversable, even if f is for example a not reversable hash function?
Because F can be anything. Go back through the analysis with F=0 as a function. It still works just fine.
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?
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.
This method only works if they're all the same size, unfortunately he didn't get into how to handle them being different sizes
@@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.)
@@misterhat5823 don't ask me, I don't know
Thanks Man !!
If we did an extra round, would we still need to switch in the end?
Love the videos but can't help link Mike and James McAvoy in my head.
I wish i had Mike Pound's brain
why the final operation in a Feistel cipher is an additional swap operation? can someone explain for me quick
A link for an Xor explaination video??
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..
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.
@@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.
@@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
When he did the "what 🤯", that was the reason I came to this video.
Why does it seem like this guy has 12 offices. They never seem to record his segments in the same place twice
3:01 I was amazed
Round func can be anything right?Iike just simple ceaser cipher?
2:56 i literally said: this is madness 🤯
Is the verb of XOR xorcise?
I thought his speciality was graphics, seems to me he knows everything!
Yeah, cryptography and computer graphics are completely different fields. I was also astonished...