Quantum Cryptography
Long article on quantum cryptography and cryptanalysis.
Entries Tagged "cryptanalysis"
Page 13 of 22
Hacking Brain-Computer Interfaces
In this fascinating piece of research, the question is asked: can we surreptitiously collect secret information from the brains of people using brain-computer interface devices? One article:
A team of security researchers from Oxford, UC Berkeley, and the University of Geneva say that they were able to deduce digits of PIN numbers, birth months, areas of residence and other personal information by presenting 30 headset-wearing subjects with images of ATM machines, debit cards, maps, people, and random numbers in a series of experiments. The paper, titled “On the Feasibility of Side-Channel Attacks with Brain Computer Interfaces,” represents the first major attempt to uncover potential security risks in the use of the headsets.
This is a new development in spyware.
EDITED TO ADD (9/6): More articles. And here’s a discussion of the pros and cons of this sort of technology.
Help Cryptanalyze Gauss
Kaspersky is looking for help decrypting the Gauss payload.
Breaking Microsoft's PPTP Protocol
Some things never change. Thirteen years ago, Mudge and I published a paper breaking Microsoft’s PPTP protocol and the MS-CHAP authentication system. I haven’t been paying attention, but I presume it’s been fixed and improved over the years. Well, it’s been broken again.
ChapCrack can take captured network traffic that contains a MS-CHAPv2 network handshake (PPTP VPN or WPA2 Enterprise handshake) and reduce the handshake’s security to a single DES (Data Encryption Standard) key.
This DES key can then be submitted to CloudCracker.com—a commercial online password cracking service that runs on a special FPGA cracking box developed by David Hulton of Pico Computing—where it will be decrypted in under a day.
The CloudCracker output can then be used with ChapCrack to decrypt an entire session captured with WireShark or other similar network sniffing tools.
Cryptanalyze the Agrippa Code
William Gibson’s Agrippa Code is available for cryptanalysis. Break the code, win a prize.
EDITED TO ADD (7/17): The code has been broken.
So You Want to Be a Security Expert
I regularly receive e-mail from people who want advice on how to learn more about computer security, either as a course of study in college or as an IT person considering it as a career choice.
First, know that there are many subspecialties in computer security. You can be an expert in keeping systems from being hacked, or in creating unhackable software. You can be an expert in finding security problems in software, or in networks. You can be an expert in viruses, or policies, or cryptography. There are many, many opportunities for many different skill sets. You don’t have to be a coder to be a security expert.
In general, though, I have three pieces of advice to anyone who wants to learn computer security.
- Study. Studying can take many forms. It can be classwork, either at universities or at training conferences like SANS and Offensive Security. (These are good self-starter resources.) It can be reading; there are a lot of excellent books out there—and blogs—that teach different aspects of computer security out there. Don’t limit yourself to computer science, either. You can learn a lot by studying other areas of security, and soft sciences like economics, psychology, and sociology.
- Do. Computer security is fundamentally a practitioner’s art, and that requires practice. This means using what you’ve learned to configure security systems, design new security systems, and—yes—break existing security systems. This is why many courses have strong hands-on components; you won’t learn much without it.
- Show. It doesn’t matter what you know or what you can do if you can’t demonstrate it to someone who might want to hire you. This doesn’t just mean sounding good in an interview. It means sounding good on mailing lists and in blog comments. You can show your expertise by making podcasts and writing your own blog. You can teach seminars at your local user group meetings. You can write papers for conferences, or books.
I am a fan of security certifications, which can often demonstrate all of these things to a potential employer quickly and easily.
I’ve really said nothing here that isn’t also true for a gazillion other areas of study, but security also requires a particular mindset—one I consider essential for success in this field. I’m not sure it can be taught, but it certainly can be encouraged. “This kind of thinking is not natural for most people. It’s not natural for engineers. Good engineering involves thinking about how things can be made to work; the security mindset involves thinking about how things can be made to fail. It involves thinking like an attacker, an adversary or a criminal. You don’t have to exploit the vulnerabilities you find, but if you don’t see the world that way, you’ll never notice most security problems.” This is especially true if you want to design security systems and not just implement them. Remember Schneier’s Law: “Any person can invent a security system so clever that she or he can’t think of how to break it.” The only way your designs are going to be trusted is if you’ve made a name for yourself breaking other people’s designs.
One final word about cryptography. Modern cryptography is particularly hard to learn. In addition to everything above, it requires graduate-level knowledge in mathematics. And, as in computer security in general, your prowess is demonstrated by what you can break. The field has progressed a lot since I wrote this guide and self-study cryptanalysis course a dozen years ago, but they’re not bad places to start.
This essay originally appeared on “Krebs on Security,” the second in a series of answers to the question. This is the first. There will be more.
Alan Turing Cryptanalysis Papers
GCHQ, the UK government’s communications headquarters, has released two new—well, 70 years old, but new to us—cryptanalysis documents by Alan Turing.
The papers, one entitled The Applications of Probability to Crypt, and the other entitled Paper on the Statistics of Repetitions, discuss mathematical approaches to code breaking.
[…]
According to the GCHQ mathematician, who identified himself only as Richard, the papers detailed using “mathematical analysis to try and determine which are the more likely settings so that they can be tried as quickly as possible.”
The papers don’t seem to be online yet, but here’s their National Archives data.
EDITED TO ADD (5/12): The papers are available for download at GBP 3.50 each.
Can the NSA Break AES?
In an excellent article in Wired, James Bamford talks about the NSA’s codebreaking capability.
According to another top official also involved with the program, the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or break, unfathomably complex encryption systems employed by not only governments around the world but also many average computer users in the US. The upshot, according to this official: “Everybody’s a target; everybody with communication is a target.”
Bamford has been writing about the NSA for decades, and people tell him all sorts of confidential things. Reading the above, the obvious question to ask is: can the NSA break AES?
My guess is that they can’t. That is, they don’t have a cryptanalytic attack against the AES algorithm that allows them to recover a key from known or chosen ciphertext with a reasonable time and memory complexity. I believe that what the “top official” was referring to is attacks that focus on the implementation and bypass the encryption algorithm: side-channel attacks, attacks against the key generation systems (either exploiting bad random number generators or sloppy password creation habits), attacks that target the endpoints of the communication system and not the wire, attacks that exploit key leakage, attacks against buggy implementations of the algorithm, and so on. These attacks are likely to be much more effective against computer encryption.
EDITED TO ADD (3/22): Another option is that the NSA has built dedicated hardware capable of factoring 1024-bit numbers. There’s quite a lot of RSA-1024 out there, so that would be a fruitful project. So, maybe.
EDITED TO ADD (4/13): The NSA denies everything.
Cryptanalysis of Satellite Phone Encryption Algorithms
From the abstract of the paper:
In this paper, we analyze the encryption systems used in the two existing (and competing) satphone standards, GMR-1 and GMR-2. The first main contribution is that we were able to completely reverse engineer the encryption algorithms employed. Both ciphers had not been publicly known previously. We describe the details of the recovery of the two algorithms from freely available DSP-firmware updates for satphones, which included the development of a custom disassembler and tools to analyze the code, and extending prior work on binary analysis to efficiently identify cryptographic code. We note that these steps had to be repeated for both systems, because the available binaries were from two entirely different DSP processors. Perhaps somewhat surprisingly, we found that the GMR-1 cipher can be considered a proprietary variant of the GSM A5/2 algorithm, whereas the GMR-2 cipher is an entirely new design. The second main contribution lies in the cryptanalysis of the two proprietary stream ciphers. We were able to adopt known A5/2 ciphertext-only attacks to the GMR-1 algorithm with an average case complexity of 232 steps. With respect to the GMR-2 cipher, we developed a new attack which is powerful in a known-plaintext setting. In this situation, the encryption key for one session, i.e., one phone call, can be recovered with approximately 5065 bytes of key stream and a moderate computational complexity. A major finding of our work is that the stream ciphers of the two existing satellite phone systems are considerably weaker than what is state-oft-he-art in symmetric cryptography.
Lousy Random Numbers Cause Insecure Public Keys
There’s some excellent research (paper, news articles) surveying public keys in the wild. Basically, the researchers found that a small fraction of them (27,000 out of 7.1 million, or 0.38%) share a common factor and are inherently weak. The researchers can break those public keys, and anyone who duplicates their research can as well.
The cause of this is almost certainly a lousy random number generator used to create those public keys in the first place. This shouldn’t come as a surprise. One of the hardest parts of cryptography is random number generation. It’s really easy to write a lousy random number generator, and it’s not at all obvious that it is lousy. Randomness is a non-functional requirement, and unless you specifically test for it—and know how to test for it—you’re going to think your cryptosystem is working just fine. (One of the reporters who called me about this story said that the researchers told him about a real-world random number generator that produced just seven different random numbers.) So it’s likely these weak keys are accidental.
It’s certainly possible, though, that some random number generators have been deliberately weakened. The obvious culprits are national intelligence services like the NSA. I have no evidence that this happened, but if I were in charge of weakening cryptosystems in the real world, the first thing I would target is random number generators. They’re easy to weaken, and it’s hard to detect that you’ve done anything. Much safer than tweaking the algorithms, which can be tested against known test vectors and alternate implementations. But again, I’m just speculating here.
What is the security risk? There’s some, but it’s hard to know how much. We can assume that the bad guys can replicate this experiment and find the weak keys. But they’re random, so it’s hard to know how to monetize this attack. Maybe the bad guys will get lucky and one of the weak keys will lead to some obvious way to steal money, or trade secrets, or national intelligence. Maybe.
And what happens now? My hope is that the researchers know which implementations of public-key systems are susceptible to these bad random numbers—they didn’t name names in the paper—and alerted them, and that those companies will fix their systems. (I recommend my own Fortuna, from Cryptography Engineering.) I hope that everyone who implements a home-grown random number generator will rip it out and put in something better. But I don’t hold out much hope. Bad random numbers have broken a lot of cryptosystems in the past, and will continue to do so in the future.
From the introduction to the paper:
In this paper we complement previous studies by concentrating on computational and randomness properties of actual public keys, issues that are usually taken for granted. Compared to the collection of certificates considered in [12], where shared RSA moduli are “not very frequent”, we found a much higher fraction of duplicates. More worrisome is that among the 4.7 million distinct 1024-bit RSA moduli that we had originally collected, more than 12500 have a single prime factor in common. That this happens may be crypto-folklore, but it was new to us, and it does not seem to be a disappearing trend: in our current collection of 7.1 million 1024-bit RSA moduli, almost 27000 are vulnerable and 2048-bit RSA moduli are affected as well. When exploited, it could act the expectation of security that the public key infrastructure is intended to achieve.
And the conclusion:
We checked the computational properties of millions of public keys that we collected on the web. The majority does not seem to suffer from obvious weaknesses and can be expected to provide the expected level of security. We found that on the order of 0.003% of public keys is incorrect, which does not seem to be unacceptable. We were surprised, however, by the extent to which public keys are shared among unrelated parties. For ElGamal and DSA sharing is rare, but for RSA the frequency of sharing may be a cause for concern. What surprised us most is that many thousands of 1024-bit RSA moduli, including thousands that are contained in still valid X.509 certificates, offer no security at all. This may indicate that proper seeding of random number generators is still a problematic issue….
EDITED TO ADD (3/14): The title of the paper, “Ron was wrong, Whit is right” refers to the fact that RSA is inherently less secure because it needs two large random primes. Discrete log based algorithms, like DSA and ElGamal, are less susceptible to this vulnerability because they only need one random prime.
Sidebar photo of Bruce Schneier by Joe MacInnis.