Entries Tagged "cryptanalysis"

Page 13 of 22

New WWII Cryptanalysis

I’d sure like to know more about this:

Government code-breakers are working on deciphering a message that has remained a secret for 70 years.

It was found on the remains of a carrier pigeon that was discovered in a chimney, in Surrey, having been there for decades.

It is thought the contents of the note, once decoded, could provide fresh information from World War II.

It was a British pigeon, presumed to have died while heading back to Bletchley Park.

Some more articles. Additional video.

ETA (11/5): Another article, and Bletchley Park news release.

ETA (11/6): And another.

I look forward to seeing the decryption.

EDITED TO ADD (11/25): GCHQ can’t decrypt it. They think that it’s either a one-time pad or a unique codebook.

Posted on November 5, 2012 at 1:26 PM • View Comments

When Will We See Collisions for SHA-1?

On a NIST-sponsored hash function mailing list, Jesse Walker (from Intel; also a member of the Skein team) did some back-of-the-envelope calculations to estimate how long it will be before we see a practical collision attack against SHA-1. I’m reprinting his analysis here, so it reaches a broader audience.

According to E-BASH, the cost of one block of a SHA-1 operation on already deployed commodity microprocessors is about 214 cycles. If Stevens’ attack of 260 SHA-1 operations serves as the baseline, then finding a collision costs about 214 * 260 ~ 274 cycles.

A core today provides about 231 cycles/sec; the state of the art is 8 = 23 cores per processor for a total of 23 * 231 = 234 cycles/sec. A server typically has 4 processors, increasing the total to 22 * 234 = 236 cycles/sec. Since there are about 225 sec/year, this means one server delivers about 225 * 236 = 261 cycles per year, which we can call a “server year.”

There is ample evidence that Moore’s law will continue through the mid 2020s. Hence the number of doublings in processor power we can expect between now and 2021 is:

3/1.5 = 2 times by 2015 (3 = 2015 – 2012)

6/1.5 = 4 times by 2018 (6 = 2018 – 2012)

9/1.5 = 6 times by 2021 (9 = 2021 – 2012)

So a commodity server year should be about:

261 cycles/year in 2012

22 * 261 = 263 cycles/year by 2015

24 * 261 = 265 cycles/year by 2018

26 * 261 = 267 cycles/year by 2021

Therefore, on commodity hardware, Stevens’ attack should cost approximately:

274 / 261 = 213 server years in 2012

274 / 263 = 211 server years by 2015

274 / 265 = 29 server years by 2018

274 / 267 = 27 server years by 2021

Today Amazon rents compute time on commodity servers for about $0.04 / hour ~ $350 /year. Assume compute rental fees remain fixed while server capacity keeps pace with Moore’s law. Then, since log2(350) ~ 8.4 the cost of the attack will be approximately:

213 * 28.4 = 221.4 ~ $2.77M in 2012

211 * 28.4 = 219.4 ~ $700K by 2015

29 * 28.4 = 217.4 ~ $173K by 2018

27 * 28.4 = 215.4 ~ $43K by 2021

A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021.

Since this argument only takes into account commodity hardware and not instruction set improvements (e.g., ARM 8 specifies a SHA-1 instruction), other commodity computing devices with even greater processing power (e.g., GPUs), and custom hardware, the need to transition from SHA-1 for collision resistance functions is probably more urgent than this back-of-the-envelope analysis suggests.

Any increase in the number of cores per CPU, or the number of CPUs per server, also affects these calculations. Also, any improvements in cryptanalysis will further reduce the complexity of this attack.

The point is that we in the community need to start the migration away from SHA-1 and to SHA-2/SHA-3 now.

Posted on October 5, 2012 at 1:24 PM • View Comments

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.

Posted on September 5, 2012 at 6:06 AM • View Comments

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.

Posted on August 6, 2012 at 11:22 AM • View Comments

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.

Posted on July 5, 2012 at 6:17 AM • View Comments

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.

Posted on April 23, 2012 at 6:18 AM • View Comments

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.

Posted on March 22, 2012 at 7:17 AM • View Comments

1 … 11 12 13 14 15 … 22

Sidebar photo of Bruce Schneier by Joe MacInnis.