Zig Zag Decryption - Computerphile
Vložit
- čas přidán 15. 09. 2015
- XOR encryption is flawed. Professor Brailsford explains the zig-zag method that can reveal the precious key stream.
Fishy Codes - Bletchley's Other Secret: • Fishy Codes: Bletchley...
XOR and the Half Adder: • XOR & the Half Adder -...
Colossus & Bletchley Park: • Colossus & Bletchley P...
5 Hole Paper Tape: • 5 Hole Paper Tape - Co...
The Professor's Supporting Documents:
Sean/Dave ZigZag document: bit.ly/computerphileZigZag
C Program to play with: bit.ly/ComputerphileZigZagCprog
The real life decryption: bit.ly/ComputerphileTiltman
Teleprinter codes: bit.ly/computerphile5holetape
/ 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
17 minutes of Prof Brailsford feels like 5 minutes of any other video. The way he explains this stuff is just so engaging. I love it!
His voice is incedibly relaxing. Great job putting everything in understandable terms!
He's voice is like velvet. I can hear him all day
To watch this video is proof that teaching is a gift, and Prof Brailsford has it in bucket loads.
I haven't seen green-bar paper since I was in college on a PDP-11.
Love these series in more way than one.
I could listen to Professor Brailsford all day- his enthusiasm for the subject is captivating and the clarity of his explanations is most welcome. MORE PLEASE!!
Forget Netflix, I am happy isolating and watching Professor Brailsford all day.
Excellent teacher. Wish there were more of these at universities.
More Bletchley Park stuff with the great Professor Brailsford please!
I love this stuff and I love the way he explains and the passion he has telling about it.
The David Attenborough of computer science!
+benaloney
Thank you for the compliment ! I saw Sir David a few nights ago on BBC's "The One Show" . He is 18 years older than me, but I can only say that if I'm still alive in 18 years time, I can only hope I'm as fit, healthy and mentally alert as he seems to be ....
+ProfDaveB Hand calculated decryption will keep anyone mentally alert! Thank you for sharing your insight on computer science, we all look forward to seeing more videos. Cheers
Is there a Brailsfordettes fan club yet??!
+Cassia Crichton Lets start up sign up sheet. One more vote for Brailsford
+oneofspades And the sheet will be typed in Braille!
I recently found this channel, and I've mostly been binging the videos with Professor Brailsford. He's very good at explaining things, a very well-spoken and captivating speaker, and I quite enjoy the topics he covers :) Also, great work with the video editing/animation in this video especially - the visual representation of what he was saying was very helpful as I was trying to understand the concept!
"... then a very special technique could be used,
to try and disentangle what these messages were
without needing to know the key at all.
Now that's an amazing property of XOR,
you could perhaps say that it was a weakness or a flaw.
But, in wanting to explain it to you exactly how this worked,
I thought I'd better do it first of all, with a simple example"
So poetic!
One of my favorite problem sets from college (unfortunately now lost to history) consisted of two ASCII text documents XORed with the same random sequence, each about half a page from different books. Took a couple of hours to work out, including discovering a bunch of neat tricks that apply to D when P1 and P2 are ASCII text which make it a lot easier even when the plaintexts aren't otherwise related.
+iabervon
Very interesting. Thanks for this! How did your ASCII-based system cope with the fact that XOR-ing two ASCII characters can all too often lead to a non-printable result e.g. NUL, NAK or even BEL ?! I'd be interested to hear about your ASCII special tricks because you're quite right in saying that unrelated texts using the same key are much tougher than related ones. Also, there are similarly quite a few properties of teleprinter 5-hole codes that greatly help when tackling same-key (but dissimilar) texts.
The files we were given were plaintext XORed with the same binary file, so we were already dealing with binary files as input (including NUL not meaning the end of the string). IIRC, I just had a big char array, whose length I knew.
The main trick I remember was that most of the characters were lower case letters, and two lower case letters XORed together gives a value less than 32, but a lower case letter XORed with a space gives the letter, upper case. This meant that it was easy to find word breaks. Also, capital letters were pretty obvious from bits 6 and 7, and there were some combinations that were obviously punctuation.
I think I started from a capital letter after a space after punctuation, used the possible word lengths for the first word of that sentence, and tried some until I got something that looked like the middle of an English word in the other text. Then it was zig-zag continuing each sentence based on grammar and possible word lengths, along with the fact that you immediately knew the letter opposite a space. It helped that the documents were made of complete well-formed sentences, rather than headlines or sightings or something.
ProfDaveB In the five level (five bit) Baudot code, the state of the printer, LTRS or FIGS, was used as a sixth bit. While 26 of the 32 possible codes represented letters when the receiver was in LTRS case, and numbers, punctuation symbols, and actions like BELL when the receiver was in FIGS case, the remaining bit codes always represented the SAME action code:
00000 = null, used for tape leaders
11111 = force receiver to LTRS case; also, to correct a typo, use the tape punch backspace button to move the tape 1 or a few (maybe up to 5?) characters backward, overpunch the wrong characters with the RUBOUT key, making them RUBOUT characters, and type the correction.
11011 = force receiver to FIGS case
00100 = space bar
00010 = carriage return (w/o linefeed)
01000 = linefeed (without carriage return
C/R and LF were always used together IN THAT ORDER, so that the first character of the next line would not print in the middle of the carriage movement back to the margin. They could also be used separately, to overprint a line, or to begin typing in the middle of a new line.
The LTRS and FIGS shift codes DO NOT TOGGLE the case of the receiver; this ensures that even if a garbled shift character FAILS to alter the case, the incorrect printing will reset with the next shift character.
The later 8 bit (on some networks, 7 bits with the 8th being used as a parity bit for error checking) ASCII code eliminated case shifting codes, since every printable character (and action code) had its own code. But the C/R and L/F remained separate,
I would love to see more videos on encryption and compression!
To be able to “do” this stuff is human. To be able to teach it coherently is Devine!
Sadly I am unable to do either but I enjoy watching others that can 🤣
y
PP
AH! Another video with Professor Brailsford!
Professor Brailsford is consistently fascinating.
Been waiting ages for this one
Very very cool stuff. The formula was explained well and his decipher example of two messages with the same key was awesome.
I always love your vids professor! Thanks for the great explanation
I took one of Stanford's online Crypto courses. And this was an amazingly easy way to put the method, never realized you could go back and forth like this, though, that's VERY clever!
I would go back to school just to hear this guy talk.
Fantastic series on encryption, juicy as can be
Can I have some more of Prof B please?
I was hoping for something more than just hoping someone sent something right and then guessing and verifying.... that said, that must have been damn hard work.
I hope when sufficient messages were decrypted we could then spot the pattern of how the keys were generated :)
+Fin H
Yes that's quite right. If you look at the "In real life" link (see Info Page for this video) you'll see that in real life John Tiltman they had the lucky break of getting 3800 characters of K from a zig-zag decode of a particularly long depth. But this just prompted the question of "what is the structure of this "Tunny machine" that can generate a 5-bit key sequence like this? ". And answering that question took another flash of genius from a man called Bill Tutte.
ProfDaveB Brilliant. Thanks :) I really have no excuse not to head to bletchley park, living in Milton Keynes. Will make a point of it in the next few weeks.
4:19 ah I get it, so 'T' = 'A' ? So the guy in the plaintext is not David, it's Dtvid
+dasten123
I was hoping that nobody would notice that I accidentally wrote down 'A' on the line-printer paper when I really meant 'T'. Sigh!
+ProfDaveB You are the David Attenborough of the Computational world!!! This should definitely be broadcasted on TV as a documentary/series. Great stuff, David Computerborough.
I wish Professor Brailsford would had been my teacher growing up
Simply amazing.
It's very depressing to have my mathematical inadequacies exposed!
How satisfying, how exciting, to be involved in resolving these intangibles, under such pressures?
Imagine being the person that found the zig zag, would have been a great day
Instead of getting 2 messages with the same key why can't you simply divide one message into two halves and XOR the halves against each other?
No. The cipher key needs to be the same for both pieces. That is why this works on a repeated message. If you split the message in the middle then the cipher key is going to be different and it won't work/
Its a great feeling of accomplishment when you break a cypher. The only cypher I have ever broken was for CATAPILLAR ECM passwords, I was overjoyed when I finally did it... I can only imagine how the people at Bletchley Park must have felt.
I see how this is a shortcut to decrypting the messages, but it doesn't actually give you more power. If you can guess parts of P1, you can use that to determine what the key would need to be to generate the corresponding C1, then try decrypting the same part of C2 using that key and see if it makes sense. It gives you the same result. Of course this technique with the combined key may be more convenient, though not necessarily faster. You still need two xor's per letter.
I wish the titles on these Videos would indicate more about the content because I know watched them in backwards order because I didn't know that they were so related :D
so this may allow us to decrypt one or two messages that use the same key, but once the pseudo random key is reseeded(could it be reseeded?) everything would be back to unintelligible text?
What about finding the most frequent character in the encrypted text and map it to letter "E". Then the key can be obtained by doing K= E + C where C is the encrypted character.
+Amr ElAdawy
Well the designers of the Lorenz/Tunny machine made great efforts to ensure that the frequency distribution of letters could, in principle, be smoothed out and randomized so that the ciphertext wasn't susceptible to statistical attack. However, it often happened that a "bad" choice of patterns and settings for the cipher wheels did allow the statistics to show through - in the way you suggest. Crucially in the Tiltman Break (see link labelled "In Real Life" on the Info Page of this video) not only was there a "depth" of two near-identical messages with the same key but also the poor choice of wheel patterns helped BP enormously.
+ProfDaveB
Thank you Sir for your reply.
One point that is being discussed a lot here, which is using wild guessing to attack the encrypted text.
The Tiltman Break paper depends on the assumption of knowing the first part of the German message "message number ".
We were looking for a way to attack the encrypted message without such assumption nor wild guessing.
I love Prof Brailsford! He always does a great job. However, this is the first video I've seen with him where I felt he didn't do a great job explaining it. I already knew how it worked, and I feel that he missed a couple key points, and if I were a beginner I would have a hard time understanding it. That being said, he's an excellent Professor and I love his videos on Computerphile more than any of the other ones. Some of the other ones are kinda lame.
This is why your choice of mode of operation is so important.
if you were to ask for a 3rd message then that would give you even more information and you would be able to verify the message with the 3rd message too
What a mastermind he is.
How can there be 44 views when the video is 17 minutes long, and it's 3 minutes ago it was uploaded?
+Monticube What's the problem? A "view" means clicking on the video.
+fireluigi12 As far as I know it's a bit more complicated. Until around 311 views or so every click is taken as a view. Further on this is decided by an algorithm, which makes sure that you can't "farm" views. if you click on the video and immediatly switch to another/close the page it won't be counted.
+Monticube CZcams has a new way to count views. It will no longer freeze at 301+ views. Instead it will batch collect views and validate them. If they're validated: it's added to the view count of the video.
+Monticube the video was probably uploaded a few hours or days ago and set on unlisted
+Monticube During the first 3 minutes of the video being live, 44 people clicked on it and started watching.
Imagine having a time machine and introducing spies to base64 encoding or some other variant that changes the number of characters. I guess the 1:1 character ciphers were used to make decoding quicker on paper, but they just seem so easily cracked in retrospect.
why even guess once the streams are out of sync just take what's being revealed and shove it back into the one that's running behind and it generates more and more
If I was trying to be secretive, I would create a cypher that gives false messages when decrypted incorrectly! I wonder if that's even possible.
I guess if you had some sort of ongoing messaging channel (like in a war), you could throw off unwanted listeners by deliberately sending a second message, which turns the first message into something else. I assume that works only for very short messages though and needs to be carefully crafted to not make it look too random or anything. It'll also probably only work a few times until the other party finds out about your bait messages.
But in the general case, no! As soon as you send two messages with the same key, you're basically screwed. If you don't, you're fine, really.
+ericsbuds en.wikipedia.org/wiki/Deniable_encryption
Márton Antoni excellent
Along the same lines, when Will Shortz designed the NYT crossword for the day after Election Day in 1992, several weeks before the election, he had a seven letter Across entry with the clue being “Last night’s winner.” The seven Down entries intersecting that one had clues that could refer to two words, depending on whether the winner was BOBDOLE or CLINTON, and either way would match with the other clues they intersected,
@@Schindlabua k
Damn clever!
what if the "sudo random" generator just used the last cypher character? would that be easier or harder to decipher?
+St0ner1995 That would be mindbogglingly simple to decode. You already have the sequence of cipher characters, so all you need to do is try each letter in the cipher text against the preceding character in the cipher text. The plaintext message then just falls out with almost no work required.
+St0ner1995 It's spelt "pseudo", by the way. A sneaky silent "P" to trip you up there!
@@mandolinic
Though that does suffer from interference - if any character is received wrong all the message from that point onwards will be gibberish.
Couldn't you split the cipher text in two, xor the two halves, and then play the guessing game on them?
+Rick Seiden
No you can't. For zigzag to work, the two ciphertexts must be produced with exactly the same key stream, kept exactly in sync with the two plaintexts. This means the same initial settings and everything. You can't just split a ciphertext in two,at an arbitrary point in the key stream, and expect the un-synced second half to work OK with the first half.
Wow! A reply from the professor himself! That's so awesome! Thank you for taking the time to answer my question!
Give me more !!!!! PLEASE !!!
for any 2 cipher texts and key, I can get a new key K' that is also an acceptable key for BOTH messages.
Correct me if I'm wrong, but once he guesses "Hi Dave" and then gets back "Hello " on the other side, doesn't that more or less confirm that he's cracked it? And then, can't he compare the first six characters of p1 and c1 (the first cypher message and the plain text translation of the first message) to work out the key, and then just use the key? My understanding is that you only need to guess until you have a plausible start to the message, but you wouldn't have to guess the entirety of the message once you're confident you've decrypted part of it.
+Joe Alias Most of the time, however it's possible the apparent solution would be wrong, that the word is just a coincidence. The process is similar to playing Mastermind.
Dan Kelly I guess my thinking is that it would cost little to try out that key, so he might as well try.
Joe Alias Yes, but these days decryption is mostly automated. I even wrote a little program myself years ago to help me with the tedious aspects of decryption.
+Joe Alias
Hi,
As the other replies have pointed out, you have the great advantage nowadays of being able to use personal computers to automate a trial-and-error process. In 1941 every single XOR operation on two 5-bit chars. had to be done "by hand" ! Also in my example I've allowed myself the luxury of always making a correct guess :-) In practice what often happened was that your initial guess of HI DAVE
might produce total garbage like XYCDGBJ - n the other stream after zig-zag - so you'd have to try something else.
And don't forget that the two messages I show you (and this happened in actuality in the Tiltman Break of 1941-- see link on Info page) are two versions of the *same* message . This was a real luxury! Far more often, the two messages using the same key would be about two rather different topics e.g. "meeting with the Greek ambassador" and "shortage of ammunition". When the topics are different it makes zig-zag decryption a lot tougher. But weaknesses in the 5-hole teleprinter code structure shifted this balance back quite a bit and made things possible -- as I hope to cover in a later video.
ProfDaveB Thanks for taking time to reply! :)
I do understand how getting that original guess is very difficult. My question pertains more to after you've actually guessed correctly than to the process of the zig-zag decryption.
If you guess HI DAVE and get back XYCDGBJ, then it's obviously back to the drawing board. My question is, if you were to guess, say, MEETING WITH and get back SHORTAGE OF, then isn't the most efficient use of time thereafter to just assume you've guessed right, work out the key itself, and use the key, rather than to continue to zig-zag guess?
Thanks!
Means: when you have just one full encrypted message - yet know what is written there as plaintext, you can encrypt all other encrypted messages - right?
+Cacalari Bus
It's not quite as simple as that, sadly! At the end of what I described in this video I did P + C = K , to get 21 characters of key. In real life (take a look at the link of that name on the Info Page) they got 3800 characters of key. And before you can decrypt any other message, on a different key, you've got to work backwards and figure out the internal structure of the machine that can generate key streams of this sort.
This seems similar to inverse matrices in D1 Maths.
I don't really have any idea what is he talking about because it's irrelevant to me, but I just love listening to him in the background.
I guess if the guy sent the same message twice you'd just get a whole string of nul. Not a lot you can learn from that, or at least, that sounds like just as hard as a problem as the one you started with
A question that has been on my mind throughout this series is why did everyone use the same 5 hole teleprinter codes? Why couldn't the enemy have used entirely different 5 bit codes to represent their letters? Wouldn't that have made it impossible since the Allies would have had no idea if 11000 = A?
+Jeremy Ratliff The strength of this simple substitution is almost negligible. Experienced cryptologist can break this by frequency analysis in several minutes.
+Jiří Havel Oh! Okay, that makes a lot of sense. Thank you!
I actually kinda got that!
I use sha1 and salt to encrypt is this secure?
Wayne Johnson No.
how could you possibly know a some plausible plaintext in a realistic scenario?
+Andrew Mann
Amazingly easily!! In the example of Sean's top-secret email if you can get hold of the email header info, as well as the body text, then you could start by looking for "To:", "From:" , "Subject:" "Bcc:" and so on. In real life,in 1941 (see the Real Life link on the Info page of this video ) John Tiltman knew that military discipline required every message to be numbered and so the first word to try for was "Spruchnummer" - the German for "message number". As I hope to be able to show in a later video, all sorts of other features/restrictions of the 5-hole teleprinter code gave extra avenues for attack. But it was never totally straightforward. He was totaly fluent in German but the initial break took Tiltman 10 days. However, with practice, one got better and better at doing "ZigZag".
+ProfDaveB What if they didn't use ASCII encoding though, like a compressed bit stream?
+SerBallister In fact, they did NOT use ASCII encoding*, since Professor Brailsford explicitly states that it is a 5-hole teletype code; this points towards either Baudot code, invented in 1870, or more likely the Murray code from 1901, which was an adaptation of the Baudot code. *ASCII code, on the other hand, uses 7 bits to encode the alphabet (upper and lower case), numbers 0-9, and several punctuation characters.
Gert Brink Nielsen Yes I know, but why use a standard encoding ?
@@wingracer16
There was one particular unit BP loved - that unit was in the middle of nowhere and send regular (daily?) reports of "nothing to report". Along with known weather stations where BP also knew the weather.
I want him to read me a bed time story
11:22 :D
📺💬 In symmetric encryption, it required a Key to encrypt and decrypt messages and we could find the weeks of this Cypher by using multiple messages and XOR them together we could read messages from them because it is a symmetric Key algorithm. 📺💬 ( additional conversation they added, Yui what am I wrong⁉🥺💬 Nothing if you are leading to the lessons about security and certificates or communication networks )
📺💬 You must try this with the Psudo random key.
🥺💬 That is because it can be explaining about the algorithm for encryption and the Cypher process, they use it for estimates of how hard it is to break information from each sub-process is because information does not always from a single department.
🧸💬 Do you mean reply messages and logarithms ⁉
🧸💬 The Zig-Zag technique is you read it Zig-Zag but it is not applied to a single symmetric key message.
James C "Sure, why not?"
Wouldn't it be simpler to just try up to 30 different keys?(it can't be the null, or the massage will be readable, and if you know it's not one of 31, it must be the 32nd)
+nir shalmon The number of keys is much higher. It is 32 possible characters times 32 for 2 character key, times 32 for 3 char key etc. It's 32 to the power of key length.
You can't simply try all possible keys for xor cipher since for every ciphertext you can find a key that decripts it to any text you choose. You need some clever way to rule out almost every possible key so only one sensible plaintext remains.
+Jiří Havel yep. That's why you need two messages using the same key, because it lets you narrow the field down.
Complicated. Couldn't follow it first time through.
It's like humanity has created its own type of mathematics.
Huh, interesting...
#ProfessorBrailsfordPhile
12:21 uwu
gwkki slcus
So basically the Germans invented RC4 (or a block cipher in CFB mode). So basically we're still using technology which was broken 70 years ago.
RC4 is broken for a different reason than the one stated in the video, since it's a fatally predictable pseudo random number generator. The "two-time pad" described by this video isn't necessarily the problem there.
Hans-Peter Klett But early versions of Microsoft's PPTP VPN notoriously did the two-time mistake all the time, making it way too easy to crack without even breaking RC4. The biggest sinner in terms of basic mistakes over and over again however is standard WiFi, which is why they have had to rewrite the security part of the standard multiple times in the past 20 years.
First comment.
+张凌寒 Last comment.