Lecture 10: Multiple Encryption and Brute-Force Attacks by Christof Paar

Christof, your English is very good! With this naïve thing and so forth. But please, if you don't want to pronounce the "th" correctly, use "t"- and "d"-sounds. Like 'this' -> 'dis' and 'thing -> 'ting'. Because the word 'sink' has its own meaning... Besides, I love you, mr Paar, and the way you gives the material.

Why not just use much longer keys?

You are the best teacher. Thank you :D

I think it's important to mention that double encryption breaks down specifically against known plaintext attacks. I haven't noticed that it was mentioned where "x1" comes from. You only have it if  you have a known plaintext-ciphertext pair ...

These videos are very well done and refreshing....from las vegas

In DES decryption, we use k(16) of encryption in the first round of decryption. When we encrypt the plain-text twice using the same key, how are we getting the plain-text? Won't we be using k(1) in round 1 of second encryption?

Danke schön Professor Paar, are there any videos/book that you would recommend that would help me understand linear cryptanalysis? Thanks!

Hello sir, I have a question which may be stupid. Suppose Oscar tries all 2^56 keys on the cipher text . And for every key he will get some plain text . How will he know the actual plain text ?

I'm sorry to be harsh : a quite terrible presentation of relatively simple concepts. Feels like an W3C specification .. lost in notations, distracted by irrelevant sidetracks, pulling the tables, writing instead of talking..
Sorry again. I hope someone can learn from this how not to teach.

Prof. Paar, can we just reduce the complexity of lookup table by O(1) using hash functions?

I am waiting video lectures from other lessons.Thank you dear Cristof Paar for your free of charge lectures.

Thank you alot.

I feel like I've learned so much so quickly watching your lectures. Thank you

why the 2 ^256 i get the 256 but why 2?

would somone please care to explain this to me: I do not understand how when the attacker tries to bread double DES how does he tell if he hit the correct keys. suppose the attacker tries a bunch of keys of the left store it in a table then tries the keys on the right there is a match from what he tried on the right side to what is found on the left side ( as mentioned...) might that just mean that the attacker just has attempted the same key twice how does that let him know he hit the correct key?

Another brilliant explanation, feel like Im finally getting this, thanks Professor!

so the zr value is the plain text value you get after trying to match your yi against a second set of keys untill you find a corresponding set of cipher text from phase 1 of the attack?

Excellent point just 1 min before the end, about block cipher, being used as a stream cipher ! So obvious ... once you said it.

Search in hashtable is not log(n) it's 1.does not matter whether it RAM/HDD/Punch cards . The worst part is that mr. Paar does not seem to be confused by the fact that in his lecture n*log(n)=2n.

Long explanation:
let's fill our hdd of size 2^64 sectors, so that each sector contain a pointer(an offset) to another sector containing key, that was used for encryption followed by pointer to a next key in case of collision or 0 otherwise. Write complexity is o(1) at best, o(n) at worst (if your cypher gives you same value disregard of the key that suck) so it's o(1). reading is the same. if you've cyphertext you can find correct sector and it's also o(1).
Using 2^64 instead of 2^56 space is not nice, but there are more elaborate workarounds for this I'm too lazy to describe here.

Prof. Paar, wonderful lectures to date (even though I don't speak German, ha)

One nitpick question - in your Theorem 5.2.1, which describes the expected # of false keys, should there be an extra "minus 1" at the end, to account for the one true positive key?

Or to ask with an example, if in AES we have both an input block size of 128 bits, and a key length of 128 bits, and one PT/CT pair, do we on average expect 2^(128-1*128) = 2^0 = 1 false positives, or NO (2^0 - 1) false positives?

Thanks!

Hats off, Prof Paar! Excellent lectures.

Go to sleep but don't talk 😍😍

Thanks a lot.

I think It's important to point out that the reason The Meet-In-The-Middle attack works efficiently is because we are assuming that searching the table is O(1) complexity or at most O(log(n))

It is worth noting that the formula in the end to calculate expected number of keys that will be false positives is not correct. It is just a simplified approximation that only works when you have a large discrepancy between the value of H and the sum of t*n.
For example if you assume t = 1, H = 64 and t = 64 you get a result of 1, which is obviously incorrect as the probability of having a false positive should be about 0.64. You get correct values in that case by using the formula: 1-(1-2^-n)^(2^H-1), note that you need a calculator with variable precision arithmetic to handle the huge exponents and the high precisions in the intermediate steps.

Great explanation. I get the point of the critique of double encryption. However, I wouldn't say it is only "marginally" more secure than DES. Not only does the attacker have to perform 2^57 encrypt/decrypt steps and to obtain something like an exabyte (million terabytes) of storage, he also has to perform 2^56 lookups on a table that takes an exabyte of storage. The NSA and several other intelligence agencies certainly could do that, even Google could probably do that, but it seems like would be prohibitive to any but the most well-funded of evil entities.
I suppose I think like an ordinary engineer rather than a cryptographic computer scientist when thinking about "marginal" improvements.

Came here for learning about 3DES, stayed for learning German :)

I'm not really sold on the idea that storing 1.08 exabytes of intermediate ciphertext and keys is at all reasonable for an attack, but I suppose it isn't impossible.

Actually, "naïve" isn't really an English word. I think it was actually a French word that was just adopted into the language--similarly to "déjà vu," "cliché," and "fiancé."

Double Enc Attack we are talking about exabytes of storage which is A LOT!

Note that the number of phase II 2E56 - 1 because you cannot use the key that was used to encrypt oherwise the X1 would be equal to Y1.

Hello Professor,

I have one question in this lecture. For double and triple encryption, meet in the middle attack, phase 1 is to encrypt X1 for all possible keys. But how does an attacker know whats X1?

Thank you Professor! This is the type of lecture values outstand than reading the textbook by myself!!

If the problem with DES is that takes a key which is too short in length, is there a way to effectively scale DES like using the same network and principles but with more rounds, more s-boxes etc. so it can be fed a larger key?

In the triple des, you can also do the meet in the middle attack because we know all the intermediate values. So using intermediate values first we can try to find first two keys, when we find them then we can pass to find the third key. Can we do that? Is my question clear?

bro's german is very understandable , but huge respect sir , super , Es hat mir viel Spaß gemacht, aber der Vortrag ist okay

Is it still possible to take your course at uni? JB

I don't believe that there is no hardware capable of brute forcing a 128 bits encryption.

Thank you Professor, great lectures