Computer science theory
- What is cryptography?
- The Caesar cipher
- Caesar Cipher Exploration
- Frequency Fingerprint Exploration
- Polyalphabetic cipher
- Polyalphabetic Exploration
- The one-time pad
- Perfect Secrecy Exploration
- Frequency stability property short film
- How uniform are you?
- The Enigma encryption machine
- Perfect secrecy
- Pseudorandom number generators
- Random Walk Exploration
Want to join the conversation?
- Would it be accurate to say that with modern computers, the entire key space could be checked easily and the Enigma technology would be busted even if it didn't have the weaknesses you point out?
Obviously, Enigma is obsolete now, but I'm wondering how easy it would be for modern computers to break it.(191 votes)
- No, without the weaknesses of the enigma machine, a one time pad is perfectly secure, as long as the key is kept secret.
Even brute force methods will not work.
From wikipedia - "In fact, it is possible to "decrypt" out of the ciphertext any message whatsoever with the same number of characters, simply by using a different key, and there is no information in the ciphertext which will allow Eve to choose among the various possible readings of the ciphertext."
So even with infinite computational power, an adversary could at best calculate all the different possibilities of all messages there could be, and therefore not be able to differentiate "Attack the East" from "Attack the West" etc.(199 votes)
- At7:27I don't understand why the operator had to select a random configuration of the rotors before beginning communication? I thought the machines had to be setup in the same initial state before communication?(91 votes)
- Good question
1. Initially the machines are setup according to the random daily key.
2. Then the operator is supposed to transmit a NEW random starting position.
3. Next both operators align to the new random selection.(86 votes)
- In a previous video about Bob and Alice, when their encoded message was shown, it still had spaces between the words. Wouldn't that make the code easier to break? Did codes sent by Enigma include spaces, or perhaps a character to represent them?(38 votes)
- Great question. Engima traffic was generally sent in standard sized blocks and spaces were removed or replaced with X. This removed any information related to word sizes (which is a rich source of clues as you point out).
For example: http://img.groundspeak.com/cache/a418c924-fd4d-4bf4-9611-e6aa7c7950cd.jpg(50 votes)
- So we are glad the German machine couldn't make a letter coded as itself in WWII?(14 votes)
- From the author:Correct, the story of the Engima (in its multiple forms) is a long and fascinating one. I explained this specific (A != A) aspect because it is a key feature that the Bombe depended on to automate codebreaking. It also proved that there was no well defined mathematical notion of what secrecy was at the time (otherwise nobody in their right mind would design a machine this way).(45 votes)
- Why is it always 'Alice' and' Bob'?(5 votes)
- Because you want to get your message from point A(lice) to point B(ob) without letting anyone EaVEsdrop.(30 votes)
- I had an idea for an entirely mechanical based design to automate the one-time pad that is based on the differences in gear ratios. Anyway, my machine only has 99 key settings and around 10-15 possible shifts. It has 2 rotors and 10 gears on each rotor, but due to some similarities in gear ratios between different sized gears, It will give you 100 different possible gear combinations but only like 20 different possible shifts. How big do you think the key space and the amount of possible shift numbers need to be before a machine like this is practically viable?(5 votes)
- Theses videos have a bit more detail about how the engima machine worked, and it's fatal flaw. http://www.youtube.com/watch?v=G2_Q9FoD-oQ(10 votes)
- What would have happened if the Germans had intentionally misspelled words -- especially the most common words? For example you could spell weather like ''veather'' ''weder'' ''weatuur'' or any other way that would be easy to understand ONCE YOU HAD ALREADY DECRYPTED IT, but the word would not "leak" as much.(5 votes)
- As someone said above: "There was no well defined mathematical notion of what secrecy was at the time". If Germans had known perfect secrecy, they would have done what you suggest (intentionally misspelled common words) and the leak of the Enigma machine (Letter A can not encrypted to A again!) would have been fixed from the start.(8 votes)
- Why would it be a big issue that a letter could not encrypt to itself? Say, I'm observing the encryption and I have A E F G. Assuming it can encrypt to itself, there are 26 possibilities for what A actually represents. Likewise for E F and G.
But, if they can't encrypt to themselves, I feel that the possibilities only drop by one to 25. So, it helps but isn't such a game-changing discovery. Or am I missing something here?(5 votes)
- It becomes a huge benefit if you try to attack using an assumed piece of plain text.
e.g. If you assume that the message contains some text e.g. "Nothing to report", but you don't know where exactly in the message it appears, you can quickly narrow down the possibilities of where that text appears in the message by:
Step 1) put the cipher text above the assume plain text
Step 2) start the assumed plain text in the leftmost position
Step 3) check if any letter of the cipher text above matches the plain text below
If any letter matches then this plain text can not be in this position
Step 4) move the plaintext right one letter under the ciphertext
Step 5) Go to Step 3
This technique is known as crib dragging
This technique exploits the weakness of letters not mapping to themselves. This weakness now acts as an oracle that tells us whether a certain piece of plain text can appear at a certain position in the message or not. In an environment like the military where the messages are highly formatted and often use certain words or phrases, this attack is devastating.
Hope this makes sense(7 votes)
- I'm not sure if this question belongs to part 8 or nine 9, but, either way, I'd love it if you could clarify something for me. Is it at all possible to interrupt and correctly translate a code done with the one-time pad, without the aid of human and design error as in the Enigma’s case?
If not, is this the basic idea behind the encryption of most--if not all-- of today's high security operations? I’ve read that the Enigma’s peers, the Typex and SIGABA, did have a higher security level than the German rotor, but were overkills. Why is that?
I apologize if this was answered already. Thanks!
p.s. I have watched the entire video series. Perhaps I need to rewatch some of it again?(5 votes)
- No, it is not possible to interrupt and correctly translate a message encrypted with a one-time pad without the aid of human or design error. In part 9, Brit explains that Claude Shannon proved this mathematically. Even if we could search through all the possible decryptions, we wouldn't know which was the correct one. For example, say we encrypt the message "meet at dawn." When If we attempt all possible decryptions, we get every possible message of that length, such as (ignoring spaces) "attack east" and "retreat now" as well as "meet at dawn." If you have all of these decryptions, you have no way of knowing which of them is the actual message.
Most of today's encryption works at the binary level. For example, from http://www.asciitable.com/, "A" can be represented as "1000001". And we would encrypt at the 1 and 0 level instead of the encrypting the letters. So, for instance, instead of saying "A" is encrypted as "K", we might say "1000001" is encrypted as "1111000".
The comment about overkill might be due to the fact that the Typex and SIGABA had a key space much, much larger than the computer power of the day. As a guess, maybe they had 20 Enigma-like rotors when only 10 would have been sufficient.(7 votes)
- Who invented the Enigma and what were the reasons? Was it because Germany needed encryption in World War I?(3 votes)
- Then Enigma was invented by a german engineer at the end of WWI. Listen to the vid at5:31. And the Germans invented the Enigma so they could encrypt their military commands etc. so the enemy wouldn't find out their plans and such.(3 votes)
- [Voiceover] On August 5th, 1857, a 4,300 kilometer-long cable was laid across the Atlantic Ocean. It provided a link between Britain and the Americas, further strengthening their social and economic alliances. Now information could be represented as a pattern of electrical pulses and sent across the world almost instantaneously. Stock tickers and money transfers - these were commercial applications invented by Western Union which ushered in a new era of global communication. - [Radio] Stand by for this announcement. Germany has invaded Poland and has bombed many times. General mobilization has been ordered in Britain and in France. - [Voiceover] And consequently, this country is at war with Germany. - [Voiceover] ...which is the real cause of the war that today threatens the freedom of mankind. (shouting in Italian) (speaking in Japanese) - [Voiceover] The Japanese have attacked Pearl Harbor, Hawaii by air, President Roosevelt has just announced. (shouting in German) - [Voiceover] During World War Two, Germany, Italy, and Japan were far outnumbered by the allies. Their only conceivable path to victory was the ability to launch widespread surprise attacks. So the goal of encryption technology was to automate the one-time pad using an encryption machine. Ideally, this machine would accept an input letter, apply a random shift, and output the encrypted letter. However, all machines follow the same principle. They begin in some initial configuration known as a state, they accept some input, they do an operation with the input, and then they produce an output. The operation from initial state to final state is always predictable and repeatable. So the goal was to produce identical machines that output a scrambled sequence of shifts, which took a long time to repeat. (mechanical ticking) Therefore, Alice and Bob could generate an identical shift sequence as follows: First they need to share identical machines and agree on an initial position, which is defined as the key setting. Then they align their machines to the same position, and finally cycle through the identical operations to achieve identical sequences. Now the state-of-the-art technology at the time was called a rotor encryption machine. We are all familiar with the mechanical process of an odometer, which takes a long time to finally repeat its cycle. Now imagine we scramble the numbers on the wheels of the odometer. When it ticks forward, a new shift could be generated by adding up each number on the rotors. This is the rough idea behind rotor encryption machines. For example, the message, "Attack Northwest" would be encrypted as follows. Notice how a new shift is used at each position in the message. With three rotors, each with 26 numbers, the length of the sequence before repeating is 26 times 26 times 26. This is equivalent to having a list of shifts 17,576 numbers long. Understand that each rotor position is equivalent to a location in this sequence. The initial machine state is known as the key setting, and the collection of all possible key settings defines the key space. This key space increases if the number of ways to initially configure the machine increases. For example, if the rotors can be rearranged then the order can be selected in six ways. Let's visualize the key space at this point. First we choose from one of six possible rotor orderings, then we select an initial position from the rotor sequence. This give us a key space with over 100,000 key settings. Remember, every machine configuration is a point in this space. When we select a key setting, we are selecting a starting point in this space, which then determines the rest of the shift sequence. Give away the key setting and you give away the entire sequence. The security of rotor machines depends on both the size of this key space and the randomness of the key setting. During World War Two, one of the most important encryption technologies used by the German military was known as the Enigma. It was an eletro-mechanical rotor machine invented by a German engineer at the end of World War One. Each rotor wheel had electrical contacts on either side with a maze of wirings within. So at each rotor position, there was an electrical path from every input letter to every output letter. When the rotor advanced, an entirely new path was defined for each letter. During the war, they continually tried to increase the key space of the Enigma in order to make it stronger. For example, some changes they made were to add a fourth rotor wheel and increase the number of possible rotors you could put in the machine to 60. This had the effect of massively increasing the key space. Near the end of the war, the Enigma could be set up in over 150 million, million, million ways. Guessing the key setting which was used for a given message was about as likely as guessing the outcome of 26 dice rolls. This gave the Germans confidence that the Allies, even if they had a copy of the Enigma, could never check all possible key settings. For two parties to communicate using the Enigma, it required that they first shared the daily key settings. This allowed them to align their machines to the same position. This protocol changed over and over during the war, but generally involved distributing key sheets in advance to all operators. Each day, the operator would cut off the daily settings and this would tell them the daily configuration of their machines, such as what rotors to use and the order of the rotors. This key setting was then to be destroyed after use. However, one vital step was left to the operator. They were to select a random initial position of each rotor before communication began. And a very simple mistake was made by some fatigued operators. We make this exact same mistake every time we set a bike lock combination, because we tend to rotate the cylinders only a few clicks from the initial state, or we reuse a common password. This destroyed the uniform distribution of the initial rotor position, and after repeated observations, it allowed the Allies to reverse engineer the rotor wirings completely. The second major error was a design error, not a procedural one. The Enigma was designed so that an input letter would never encrypt to itself. So given an encrypted letter, such as L, You can now eliminate the possibility that L was the original letter. What they thought was a strength was actually a weakness in design. (water dripping) And this led to a code breaking machine, initially designed by the Poles and later improved by the British-American effort. The Bombe was multiple Enigma rotors chained together, allowing it to rapidly test different key settings. It took advantage of the fact that common words were known to be in the original message, such as weather. And these came to be known as cribs. For a given message in crib, the Bombe could scan through all possible rotor positions and orders in order to find possible key settings in a matter of minutes. This machine allowed the Allies to read German commands within hours of them being issued. It was a fatal blow to their combat strategy, as the Allies could anticipate their next move. One fact remains: This initial attempt at automating the one-time pad failed. If the operators had instead rolled dice to decide their initial rotor positions, the starting point in the sequence could have been uniformly distributed. This would have prevented the reverse engineering of the rotor wirings. And if the Enigma allowed letters to be encrypted to themselves, the bombe could not have taken advantage of cribs. And this would've required the Allies to check the entire key space, which was impossible even with the fastest computer. Repetition reduced the key space. Otherwise, the outcome of World War Two could've been drastically different.