Feistel Cipher - Computerphile
Vložit
- čas přidán 18. 02. 2020
- 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/nottscomputer
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 😱.
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
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.
If you heard a boom...that was my head exploding.
I want someone to talk about me the way Dr. Pound talks about Feistel Ciphers
Dont we all
Video was too short for such an interesting concept!
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 CZcams. Can uploaders choose whether or not to have them?
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.
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.
can't unsee 'rofl' in R⊕F(L
Love this dude
Man love is real
Always excited for a Mike Pound video. Always excited for a crypto video. You've given me a happy morning.
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.
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
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
The one and only video that explains Feistel Networks in a simple but understandable way. Thnx so much
i can listen to this guy talking all day long, amazing video never gets old thanks
A short video so rich with information. I really enjoyed learning about this.
Love Dr. Pound! I would happily watch a video of him reading the Mr. Wimpy menu.
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.
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! 😂
you just saved my cyber security lectures. dude I love you
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
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
Writing with a highlighter like a maniac 😂😂😂
Brilliant work as usual - you always manage to simplify these complex security concepts!
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.
Thanks for the help. Passed my coursework because of this video =)
This channel shares amazing contents.
One thing I can't take from their video is sound of pen against paper.
As always, videos featuring Dr Mike Pound are super duper interesting ! Thank you for your time :)
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.
The crossing x-ors ensure that information can be reversed via what ever algorithm is used in between.
One of the best explanations on the topic feistel ciphers.....😇
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
I always love this stuff.Thanks for making these!
Love his presentations... makes very complex subjects so easy to follow
man what an awesome explanation
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.
Yet another cryptography topic explained flawlessly by Mike.
add a thumb for yourself, Leonhard
Brilliant job 👍
who is the man behind the camera? he listens to the lec very carefully and asks valid and authentic questions.
The Pound function: A video with Dr Mike Pound is posted -> I click it.
Be careful tho - that function isn't CPA secure!
Mike brought you here I know, love Mike.
Wow, that is amazing.
Horst Feistel was my dear Uncle. A great man!
Super helpful. Thank you!
there really should be a computerphile playlist with all the crypto stuff
3:04 that "boof" sound is soooooooooooo satisfyinggggggg
why do you still have printing paper with spool-holes
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.
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.
If we did an extra round, would we still need to switch in the end?
awesome !! I love that
mike: "even if f is not reversible, that still decrypts it"
me: what?
mike: what?
So if I have a hash function and I put it into a Feistel Cipher I can get back the original message?
Can you please make a video about DES? I would like to understand how is 6to4 bit substitution reversible. Thanks.
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
Thanks Man !!
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).
why the final operation in a Feistel cipher is an additional swap operation? can someone explain for me quick
0:21
DES
2:44
Decryption.
3:33
Keys and function.
5:00 --> 5:54
XOR decryption.
thanks a lot !!!
How did you know we had a lecture about this this week?
I love this
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.
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.
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
Very nicely explained. I have worked with DES cryptography earlier in my career.
Round func can be anything right?Iike just simple ceaser cipher?
Damn that's clever
I just had a lecture about this (by one of the inventors of AES) today, what are the odds?
neat involution
Can you please make a video on ROUND FUNCTION? It would be great if you do it
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!
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?
Is the verb of XOR xorcise?
A link for an Xor explaination video??
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
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.
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"
this is madness
why if we use only one round the feistel network is not secure?
Hay Mike Can you please explain the code of this cipher by showing us real example.
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
It's like the butterfly swap of ciphers.
3:01 I was amazed
If this dude was a CS professor, he would be THE BEST ( *NOT one of the best* ) professor in the world
did you get any of that?
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.
Where do you get that paper?
so did you crack or create the zodiac cipher?
MIKEEEEEEEEE
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?
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.
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.
I see Mike i upvote
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.
But why is the the final flip required?
When he did the "what 🤯", that was the reason I came to this video.
can you use cipher to reverse a ratchet?