Slashdot Mirror
60 Years of Cryptography, 1949-2009
Dan Jones writes "2009 marks 60 years since the advent of modern cryptography. It was back in October 1949 when mathematician Claude Shannon published a paper on Communication Theory of Secrecy Systems. According to his employer at the time, Bell Labs, the work transformed cryptography from an art to a science and is generally considered the foundation of modern cryptography. Since then significant developments in secure communications have continued, particularly with the advent of the Internet and Web. CIO has a pictorial representation of the past six decades of research and development in encryption technology. Highlights include the design of the first quantum cryptography protocol by Charles Bennett and Gilles Brassard in 1984, and the EFF's 'Deep Crack' DES code breaker of 1998."
Ubbenl gb rapbqvat!
Ad-laden slideshows are not my favorite sources of information.
Didn't Caesar already do this in classic Rome?
I remember reading the book Crypto. They spent all the time describing what they ate for breakfast. Never did get around to describing any of the algorithms. I figure they weren't allowed to. They didn't even have the guts to tell us. Must have been afraid it would affect sales of the book. Or maybe they weren't allowed to tell us they weren't allowed to tell us. Heroes aren't what they used to be.
But none of Alan Turing.
I wish the article spelled Zimmermann with two Ns.
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1.4.9 (GNU/Linux)
mQGiBEq3RpgRBAC32oLUAaR4dFujNcEedZ4Ws1Ky/bKjULLxWNixY0qLAV8EEYSw
-----END PGP PUBLIC KEY BLOCK-----
How come history is written so that "Modern Cryptography" starts when an American writes a paper, some seven years after the British have developed computers to automatically crack Germany's enigma codes? Modern cryptography isn't just the creation of the cipher, but the appreciation of modern techniques to crack it.
If this article can make such an arbitrary assumption about what is modern, I give little credit to how misinformed the rest of the article may be. It's how Americans steal history, so they can define it in their own favor.
I do not mean to flame. I am just skeptical of assumptions, when such a basic assumption is so inherently wrong.
Er... Bletchley Park anyone? Shhhhh - don't mention the war!
Several years ago I visited the National Cryptologic Museum at Ft Meade MD. http://www.nsa.gov/about/cryptologic_heritage/museum/
At the time you had to go through a gate with armed military types then make your way around to the museum parking lot. Once inside, I remembered that I had forgotten to lock my car doors, and mentioned to the guard that I was going to go back out to the parking lot to do this. He looked at me and said, "Don't worry about it, your car is being watched".
In any case, I highly recommend visiting this museum if you are a geek type. from a real Enigma that you can touch, to a Cray II that you can sit on, this place is cryptogeek heaven. A truly interesting experience.
* Carthago Delenda Est *
> Unfortunately this machine ended up on the losing side of the war, so a lot of the
> knowledge will have been lost thanks to that.
Er, the German guy who invented the Enigma was killed in a horse carriage accident in 1929. So, no, the war had no direct effect on cryptographic knowledge in the way you imply. Considering the enormous number of casualties on both sides, however, I'm sure it affected it in a general way.
I have developed my own uncrackable form of encryption, the only downside being that it takes a long time. The process basically involves saving my data to a Linux filesystem, and then waiting until the OS inevitably corrupts itself beyond compare. Hey presto, encrypted data!
In fact, as is well known, A M Turing worked at Bell for a short time during WW2. He also learnt at Princeton the electronics that made the Bombes possible.
Modern cryptanalysis was a US/UK cooperation with information and development coming from both sides The Poles obtained an Enigma and started the mathematical theory of decrypting Enigma messages: the analysts at Bletchley, of whom Turing was only one (remember I J Good, anybody?) too it forward, and then post-Pearl Harbor it became (at least in part) a joint venture. It isn't necessary for the US to pretend that they did it all by themselves; we associate that kind of insecurity with the Soviet Union.
The (US) guy who recently wrote a history of D-Day (sorry, forget his name) writes somewhere that while the perception that in WW2 the British had the ideas and the US provided the productive capacity is not really correct as it stands, there is some truth in it. That should really be good enough for everybody.
From scarped cliff or quarried stone she cries "A thousand types are gone, I care for nothing, no not one."
Seriously, anti-American bitching gets really old. You don't like that America was a major force behind crypto? Too bad, that's how it is, stop whining.
As for why they chose this, well it makes sense. Modern cryptography, as in the crypto we use these days, started with Shannon's paper. This is when things started becoming a real science, making extensive use of number theory and so on. Prior to that, crypto was largely just whatever sort of codes people could come up with that seemed hard. There wasn't any good science behind it.
A good example would be the code talkers, used by the US. The code was never broken during the war, but not because it was unbreakable. All it was was a language that wasn't spoken in Europe, and very dissimilar to European languages. That combined with misleading terminology made it something the Axis couldn't crack. However, there was no good math/science keeping it uncrackable. All they'd have needed to do was get a code talker who was willing to work for them and the thing would have been useless.
While the British worked on code breaking, and some of what was discovered there applies to modern code breaking, they didn't work on modern coding techniques. Their concern was breaking the codes of the day, understandably.
There really is a massive before/after crypto divide with regards to Shannon's paper. All crypto we use these days is traceable back to then. Thus it makes sense as a starting point for modern cryptography.
So seriously, chill with the US hating. To me this chosen starting point doesn't seem at all about the US trying to "steal" history, it seems like a sensible historical fact. You look at how modern codes work and you say "What started this? Where did this come from?" it comes back to that paper.
What about the art of decrypting meaningfull messages out of random sequences?
A stupid question you might think , but unless you know what the output should be , how do you know when you've found it? Unless a computer knows every language on the planet and "reads" ever version of the potential output and decides if it makes sense how can it ever know when the decryption is finished? And what if its not plain text its decrypting but something else entirely such as a binary file? Perhaps I'm just dumb but this is something I've never understodd.
"While the British worked on code breaking, and some of what was discovered there applies to modern code breaking, they didn't work on modern coding techniques. Their concern was breaking the codes of the day, understandably."
Oh right, so conveniently the 1940s don't count as "modern" , but the 1950s do? What a crock of shit. Talk about modifiying meanings to suit your own ends. The german codes were created using a machine and on the british side were partly decoded using electronic computers. If that doesn't count as modern then I don't know what does.
Statistical analysis.
Properly encrypted material with a good pseudo-random number generator should appear essentially statistically identical to random white noise. Decrypt the material and the statistical analysis should show something dramatically different from random white noise.
There is not a "massive divide". A growing body of knowledge got formalised into a useful structure. We don't say modern physics began with Newton, Einstein or Planck. We recognise a continuum. Modern cryptography clearly began in the 1930s when people started formulating mechanical means of encryption and decryption, advanced when mechanical means of codebreaking were developed in the 40s, and then advanced further when Bell Labs (not just Shannon) put this all together to produce a general theory.
I suggest you go off and play with the (minority of) US astronomers who object to the downgrading of Pluto because it was the only planet discovered by a US-born astronomer. The achievements of the US make this kind of thing just plain childish, like a billionaire would be who boasted about winning a few dollars in a crap game.
From scarped cliff or quarried stone she cries "A thousand types are gone, I care for nothing, no not one."
You don't know - and neither does the computer.
Decryption is a mathematical operation. You are given a blob of yunk. You can be fairly certain it is encrypted with a given cipher because it meets certain characteristics - either length, or hash-depth, or there is a header or footer of a given length, or some revealing information about the cipher may have been sent prior to or alongside the encrypted blob.
Then, if you're smart enough, or you have enough money, or time, or computing power, or a lot of luck, the decryption operation might occur. You can check as to whether or not you've successfully decrypted the data mathematically - e.g. does the result set fit with the function I've just run and give me the source data I started with? If so, yes, you've decrypted the data.
It's your responsibility as a researcher to decide what to do with whatever came out the other side. You may have to decrypt it again before proceeding. You may find out that what you just decrypted was nothing more sinister than ICMP_FRAGMENTATION_REQUIRED (Frak!).
The holy grail of cryptography may infact be steganographical encryption - or binary / machine language that reads as Grandmother's Cookie Recipe, but when run as an executable it actually glasses the machine. Who knows?
Informatus Technologicus
Fair enough , but what if something has been encrypted twice? You've successfully decrypted the 2nd stage but the output is still statistically noise because its still encrypted by the 1st encryption stage. How would you solve this problem?
... what a joke!
Users... the only thing keeping 1st level support from being the bottom feeders.
I've recently become rather fascinated by the Enigma machine and the operation of the device. The Wikipedia article is worth a read.
Couple of cool things to know about the Enigma:
I believe it was the first machine to have symmetrical encoding and decoding. Because it had a this property (as a letter was coded through the rotors, there was a rotor that reflected the encoding back through the rotor stages again), an operator could code and decode messages without reconfiguring the device.
Due to the fact above, the Enigma could never encode a letter onto itself. This greatly decreased the permutations allowed and made the device less effective.
The way the Germans used the machine also made the device easy to crack. Operators would encode the rotor setup in the message. This allowed verifying that the right settings were being used. Also, the Germans would include many standard phrases like praise for the Fuhrer.
Though the Enigma machine is the most well known device, there were many rotor based encoders during the WWII and post era.
There are many simulators of the Enigma machine (see the Wikipedia article). Very cool to play with to really understand the operation of the device.
I love the sound of distortion in the morning -- webcommando
Lax crypto discipline was a big factor in helping to break Enigma traffic, but there were fundamental quirks in the operation of the units that prevented it from being as secure as the Germans believed it to be. (also, after more than one investigation that indicated Enigma traffic was being broken, the Germans refused to believe that their design was insecure).
- a letter was never encrypted as itself (the famous example is the message that contained all letters of the alphabet except one, thereby indicating, not only that the plaintext consisted of only the letter missing in the ciphertext, but the sequencing of the rotor changes)
- the reflector rotor never moved, and there were only three (four in some units) rotors.
- there were only six "stecker" jumper wires, so only six pairs of letters could be swapped
Enigma was anything but sound, and more so because it depended so much on the operators. That the Allies were able to break Enigma traffic on a continuing basis is proof of that.
Looking at the SIGABA rotor scheme, you can see immediately that it is a far more complex unit than the Enigma, and (as far has been disclosed) it was never broken. And that's not because the Germans never tried.
I went last year. No guards, it's outside the gate. A very worthwhile visit if you're in the DC area.
In addition to the Enigma and Cray, they have a US Navy Bombe (the Enigma key search machine), a NeXT cube, a USS Liberty memorial and a bunch of other neat stuff.
And a gift shop. Don't forget your NSA logoware. You get an opaque blue shopping bag with nothing printed on it. The receipt is from the "Employee Welfare Fund" or some such. I got a kick (and an NSA coffee mug) out of that.
$5 Wrench.
http://xkcd.com/538/
The problem with encrypting something twice is that you've just created another cipher. So instead of breaking the encryption A, you're trying to break A+A=B. Starting from scratch, the task is just as difficult--you have some bits, mapped to other bits, and you're trying to reverse the mapping.
Now, if you're brute forcing things (which assumes you already know the algorithm, and just need to recover the key), it does add an extra layer of work (unless you're using a weak cipher), and double encryption does tend to change the mathematical properties (although not always for the stronger--see double vs. triple DES), but at a very simple level, they're equivalently hard.
"Encrypted twice" doesn't mean anything. A composed encryption scheme is a single function, same as y = (2x + 1)^2 - 4.
As stated below, steganography is the stopping problem here. Is the secret meaning hidden in typos and word order, or do the words have a second meaning?
ID: the nose did not occur naturally, how would we wear glasses otherwise? (apologies to Voltaire)
And every, single, image in that slide show is ripped directly from Wikipedia. In fact, the entire presentation is little more that a digest of someones Wikitrip.
As Paul Graham(I think) said, "Pay to view content on the internet may as well not exist". Given that information not on the internet is becoming increasingly obsolete, this maxim can be extended to the conclusion that; the only content that will matter is that which is freely available online. People such as journalists or even reviewing researchers are not going to go to the hassle of chasing down sources closeted in dusty libraries or the like, when low hanging fruit such as Wikipedia pages are so easily accessible.
There was a story a few weeks ago about how a copyright black hole is swallowing our culture. Well, it's swallowing more than that. It's swallowing cold hard facts, data, progress and information too. Compound this easily accessible and digestible, though lower quality, alternatives available online at places like Wikipedia, and you are seeing the beginning of a major shift in how our society comes by its information and the truth itself.
For over 5 months Wikipedia had an incorrect start date for World War 2. In the new information regime that is emerging, for a great many (mostly younger) people, for those 5 months, that became the start date for World War 2. The (old) correct date was cloistered away in libraries and pay per view papers or books. The new date was the first hit on a Google search. Which is more likely to become the dominant interpretation?
We have seen it time and again. Cheaper and easier will win out over expensive and difficult. The same is now happening for information. This doesn't necessarily mean that cheap and easy has to be worse, but in the case of finding cold hard facts online, it is. There is no quality control on the internet hive mind. The online or Wikipedia version of the truth is becoming the dominant one, and with the black hole swallowing all the hard facts, how will we ever find the real truth again?
Orwell was right about the outcome, but wrong about the method. You don't need to hide the truth. You just need to make the alternatives easier to find.
May the Maths Be with you!
it actually glasses the machine.
Sigh, who ever used this terminology? Do you really call character terminals glass terminals? None of my computers involve any glass any more; if they do it's quartz glass in an EPROM, and I sincerely doubt I even have anything with a real EPROM in it any more :P
"You're right," Fisheye says. "I should have set it on 'whip' or 'chop.'"
I'd suggest that the author is off by at least 40 years. Check out Riverbank Labs in Geneva, IL. With the onset of World War I, Colonel Fabyan offered the services of his Department of Codes and Ciphers to the Federal Government. Due to the fact that the government had no existing department for this kind of work, they accepted. Riverbank began receiving encoded messages to work on breaking which had been intercepted by the government from unfriendly sources. For many, even today, codes and ciphers are an unknown entity. When the Friedmans began to research sources on codes and ciphers to assist them on the Baconian theory, they realized there was very little written about it. Thus, their work was groundbreaking in developing literature in the field.
Encrypted text is as close to random as can be reasonably designed; plain text is very non-random. For example, printable ASCII is represented by a byte whose first bit is a zero. If you sample every eighth bit in a test decrypt, and they're all zeroes, then the chance your decryption has succeeded is 1-(1/2)^N where N is the number of bytes in the message. After test decrypting a message of any reasonable length (say 100 bytes), and you're still hitting all zeroes, you can be fairly confident the decryption has succeeded. Of course, this only works on encrypted ASCII, but the method can be adapted to any system where the method of representing data has a known pattern. Even binary files have a regular structure that allow them to be used by a computer processor. In fact, a binary file is even easier to decrypt by using a 'known plaintext' attack -- only test decrypts that match the known file format are saved as candidates. (Knowing the pattern of the data comes from other sources, for example from knowing what frequency a particular message was transmitted on, or when it was transmitted.)
And it had a huge impact on History...
I'd say that Auguste Kerckhoffs is the father of modern cryptography. Kerckhoffs' principle is essentially the same as Shannon's maxim but he formulated it 70 years earlier.
The encryption scheme will usually have a MAC, hash, or other check so that it knows when the message was successfully decrypted.
http://en.wikipedia.org/wiki/Message_authentication_code
You could encrypt with one algorithm, then take the output from that and encrypt again with a completely different one.
If something is encrypted twice with two different keys, what you actually have is a new crypto algorithm with a longer key. See:
cryptoA(keyA, plaintext) = ciphertext
cryptoB(keyB, plaintext) = ciphertext
So you propose doing
cryptoA(keyA, cryptoB(keyB, plaintext)) = ciphertext
This could be rewritten as cryptoC(keyA+keyB, plaintext) = ciphertext
A slashdotter who didn't build his own computer is like a Jedi who didn't build his own lightsaber.
1. Set up an arbitrary point in time. (E.g. "the advent of modern cryptography", or "the invention of X by NotActualInventorY"R ...
2. Create an article, celebrating the X years since then.
3. Write up a crappy "history". (The crappier, the more "controversy" [aka. "troll power"] it will create.)
4.
5. PROFIT!
Any sufficiently advanced intelligence is indistinguishable from stupidity.
http://xkcd.com/257/
"Encrypted twice" doesn't mean anything. A composed encryption scheme is a single function, same as y = (2x + 1)^2 - 4.
Technically true, but depending on the cipher(s) you use, you may have no idea at all what the resulting function is, and it is therefore often easier to decrypt in the same steps you used for the encryption.
Some cryptographic functions, RSA for instance, are mathematical groups. In other words, RSA(RSA(plaintext, key1), key2) === RSA(plaintext, key3) for some key3 that you probably don't know. In such cases, if you were trying to break the cipher and had no means to recover keys 1 and 2, it would be easier to discover key3 and decrypt in one step.
That's not true for all ciphers, however. DES is one example of a cipher that is not a mathematical group, which is why "TripleDES" is regarded as being more secure than a single pass of DES -- I believe the assumption is that 3 passes of 56-bit DES are about equivalent to a 112 bit key.
All of that theory, of course, breaks down if you can get at the original keys. Rubber-hose cryptanalysis has the obvious advantages of being fast and computationally cheap.
Where is the wisdom we have lost in knowledge?
Where is the knowledge we have lost in information?
"According to his employer at the time, Bell Labs"
Hmm. What could be less biased than a company writing a press release about its own achievements?
Next you'll be telling us that the press releases about Segways reinventing personal transportation might not be entirely accurate.
Oh right, so conveniently the 1940s don't count as "modern" , but the 1950s do?
No, no, silly. Modern isn't determined by a decade. It's determined by whenever the Americans got involved.
Here's a bit by Schneier on how to recognize plaintext. Basically, plaintext looks like plaintext, either because it's intelligible lanugage, or because it matches the characteristics of a standard document format (headers, layout, etc.)
How one would go about programming a computer to recognize plaintext, I have no idea, but presumably somebody smarter than me has worked it out.
... Someone says: "Oh boy".
If it is like ASCII text (or UTF-8 text with many ASCII characters) then this is easy: you just test how many times a byte representing a character is present. Values 30h to 39h and 61h to, er, 6Ah are lower case characters. Of these characters some are much more present than others, the letter e is most common. Binary data otoh tends to have a lot of bytes with value 00h, e.g. for representing signed positive numbers (and more commonly 32 bit encoded numbers with initial low values), NOP instructions, aligning, null terminated strings, default values etc. etc.. With the file command in Unix you can find many common file formats, XML and ASN.1 BER encoding (commonly used to wrap cryptographic messages) are very easy to identify as well. And sometimes you just know the start of the message anyway, because it has been standardized..
Reasons why people are suckers for lists:
- they split an article up in several evenly sized pieces
- lists look like they contain serious information
- lists are easy to remember than loose information
- humans like to rate things
But:
- but if the list contains elements that are only loosely coupled
- or if the list is very incomplete
- or if the information in the article is wrong or made up
- or if the information in the list is made up of known facts
Then lists suck. The article is one of those lists. My lists have been constructed in a minute or so, so you may count them to the former or mod me informative. As long as you click on the minus sign in front of the summary.
I'm pretty sure construction workers had something to do with the DES code breaker. Some of them display an awful amount of "Deep Crack".
"None of my computers involve any glass any more"
So you're not running an iMac then?
You are not a brain: http://books.google.com/books?id=2oV61CeDx-YC
The constant struggle to hide transactions and data will continue for many more years I imagine.
Its funny talking to a friend working at Pine Gap about just how easily these agencies bypass so-called cryptography. Its scary really. Given, the techniques used don't always involve finding weaknesses in the design of particular algorithm in question. Still, stuff I thought was safe....isn't.
Not particularly heart-warming stuff. =)
Nevertheless, I have great respect for the brilliant cryptographers out there and what they've done for the industry.
Which, as the GP poster noted, is functionally identical to encrypting with a single, third algorithm. The reason you don't do this is that you don't know the cryptographic properties of the third algorithm. It could be more secure than either of the original algorithms, but it just as easily could be less secure.
"They redundantly repeated themselves over and over again incessantly without end ad infinitum" -- ibid.
60 Years of keep-away gone high tech.
Someday we'll hit the human carrying capacity. And the band will just play on.
While f3(x) may well be stronger than f1(x) or f2(x), this is not necessarily the case.
If I seem short sighted, it is because I stand on the shoulders of midgets