Prime Numbers are Stranger than You Thought

If you’ve spent any time around prime numbers, you know they’re a pretty odd bunch. (Get it?) But it turns out that they’re even stranger than we knew — until recently. According to this very readable writeup of brand-new research by [Kannan Soundararajan] and [Robert Lemkein], the final digits of prime numbers repel each other.

More straightforwardly stated, if you pick any given prime number, the last digit of the next-largest prime number is disproportionately unlikely to match the final digit of your prime. Even stranger, they seem to have preferences. For instance, if your prime ends in 3, it’s more likely that the next prime will end in 9 than in 1 or 7. Whoah!

Even spookier? The finding holds up in many different bases. It was actually first noticed in base-three. The original paper is up on Arxiv, so go check it out.

This is a brand-new finding that’s been hiding under people’s noses essentially forever. The going assumption was that primes were distributed essentially randomly, and now we have empirical evidence that it’s not true. What this means for cryptology or mathematics? Nobody knows, yet. Anyone up for wild speculation? That’s what the comments section is for.

(Headline photo of researchers Kannan Soundararajan and Robert Lemke: Waheeda Khalfan)

Shmoocon 2016: Computing In A Post Quantum World

There’s nothing more dangerous, so the cryptoheads say, than quantum computing. Instead of using the state of a transistor to hold the value of a bit as in traditional computers, quantum computers use qubits, or quantum information like the polarization of a photon. According to people who know nothing about quantum computers, they are the beginning of the end, the breaking of all cryptography, and the Rise of the Machines. Lucky for us, [Jean-Philippe Aumasson] actually knows a thing or two about quantum computers and was able to teach us a few things at his Shmoocon talk this weekend, “Crypto and Quantum and Post Quantum”

This talk is the continuation of [Jean-Philippe]’s DEF CON 23 talk that covered the basics of quantum computing (PDF) In short, quantum computers are not fast – they’re just coprocessors for very, very specialized algorithms. Quantum computers do not say P=NP, and can not be used on NP-hard problems, anyway. The only thing quantum computers have going for them is the ability to completely destroy public key cryptography. Any form of cryptography that uses RSA, Diffie-Hellman, Elliptic curves is completely and totally broken. With quantum computers, we’re doomed. That’s okay, according to the DEF CON talk – true quantum computers may never be built.

The astute reader would question the fact that quantum computers may never be built. After all, D-Wave is selling quantum computers to Google, Lockheed, and NASA. These are not true quantum computers. Even if they’re 100 Million times faster than a PC, they’re only faster for one very specific algorithm. These computers cannot simulate a universal quantum computer. They cannot execute Shor’s algorithm, an algorithm that finds the prime factors of an integer. They are not scalable, they are not fault-tolerant, and they are not universal quantum computers.

As far as true quantum computers go, the largest that has every been manufactured only contain a handful of qubits. To crack RSA and the rest of cryptography, millions of qubits are needed. Some algorithms require quantum RAM, which nobody knows how to build. Why then is quantum computing so scary? RSA, ECC, Diffie-Hellman, PGP, SSH and Bitcoin would die overnight if quantum computers existed. That’s a far scarier proposition to someone hijacking your self-driving car or changing the display on a smart, Internet-connected thermostat from Fahrenheit to Celsius.

What is the verdict on quantum computers? Not too great, if you ask [Jean-Philippe]. In his opinion, it will be 100 years until we have a quantum computer. Until then, crypto is safe, and the NSA isn’t going to break your codez if you use a long-enough key.

Hacker Uncovers Security Holes at CSL Dualcom

CSL Dualcom, a popular maker of security systems in England, is disputing claims from [Cybergibbons] that their CS2300-R model is riddled with holes. The particular device in question is a communications link that sits in between an alarm system and their monitoring facility. Its job is to allow the two systems to talk to each other via internet, POT lines or cell towers. Needless to say, it has some heavy security features built in to prevent alarm_01tampering. It appears, however, that the security is not very secure. [Cybergibbons] methodically poked and prodded the bits and bytes of the CS2300-R until it gave up its secrets. It turns out that the encryption it uses is just a few baby steps beyond a basic Caesar Cipher.

A Caesar Cipher just shifts data by a numeric value. The value is the cipher key. For example, the code IBDLBEBZ is encrypted with a Caesar Cipher. It doesn’t take very much to see that a shift of “1” would reveal HACKADAY. This…is not security, and is equivalent to a TSA lock, if that. The CS2300-R takes the Caesar Cipher and modifies it so that the cipher key changes as you move down the data string. [Cybergibbons] was able to figure out how the key changed, which revealed, as he put it – ‘the keys to the kingdom’.

There’s a lot more to the story. Be sure to read his detailed report (pdf) and let us know what you think in the comments below.

We mentioned that CSL Dualcom is disputing the findings. Their response can be read here.

Quantum Computing Kills Encryption

Imagine a world where the most widely-used cryptographic methods turn out to be broken: quantum computers allow encrypted Internet data transactions to become readable by anyone who happened to be listening. No more HTTPS, no more PGP. It sounds a little bit sci-fi, but that’s exactly the scenario that cryptographers interested in post-quantum crypto are working to save us from. And although the (potential) threat of quantum computing to cryptography is already well-known, this summer has seen a flurry of activity in the field, so we felt it was time for a recap.

How Bad Is It?

If you take the development of serious quantum computing power as a given, all of the encryption methods based on factoring primes or doing modular exponentials, most notably RSA, elliptic curve cryptography, and Diffie-Hellman are all in trouble. Specifically, Shor’s algorithm, when applied on a quantum computer, will render the previously difficult math problems that underlie these methods trivially easy almost irrespective of chosen key length. That covers most currently used public-key crypto and the key exchange that’s used in negotiating an SSL connection. That is (or will be) bad news as those are what’s used for nearly every important encrypted transaction that touches your daily life.

Continue reading “Quantum Computing Kills Encryption”

Hackaday 10th Anniversary: [1o57] and the Art of Encryption

[Ryan] a.k.a. [1o57] comes from an age before anyone could ask a question, pull out their smartphone, and instantly receive an answer from the great Google mind. He thinks there’s something we have lost with our new portable cybernetic brains – the opportunity to ask a question, think about it, review what we already know, and reason out a solution. There’s a lot to be said about solving a problem all by yourself, and there’s nothing to compare to the ‘ah-ha’ moment that comes with it.

[1o57] started his Mystery Challenges at DEFCON purely by accident; he had won the TCP/IP embedded device competition one year, and the next year was looking to claim his title again. The head of the TCP/IP embedded competition had resigned from his role, and through a few emails, [1o57] took on the role himself. There was a miscommunication, though, and [1o57] was scheduled to run the TCP/IP drinking competition. This eventually morphed into a not-totally-official ‘Mystery Challenge’ that caught fire in email threads and IRC channels. Everyone wanted to beat the mystery challenge, and it was up to [1o57] to pull something out of his bag of tricks.

The first Mystery Challenge was a mechanical device with three locks ready to be picked (one was already unlocked), magnets to grab ferrous picks, and only slightly bomb-like in appearance. The next few years featured similar devices with more locks, better puzzles, and were heavy enough to make a few security officials believe [1o57] was going to blow up the Hoover dam.

With a few years of practice, [1o57] is turning crypto puzzles into an art. His DEFCON 22 badge had different lanyards that needed to be arranged to spell out a code. To solve the puzzle, you’ll need to talk to other people, a great way to meet one of [1o57]’s goals of getting all the natural introverts working together.

Oh. This talk has its own crypto challenge, something [1o57] just can’t get out of his blood:


Reverse Engineering A Bank’s Security Token


[Thiago]’s bank uses a few methods besides passwords and PINs to verify accounts online and at ATMs. One of these is a ‘security card’ with 70 single use codes, while another is an Android app that generates a security token. [Thiago] changes phones and ROMs often enough that activating this app became a chore. This left only one thing to do: reverse engineer his bank’s security token and build a hardware device to replicate the app’s functionality.

After downloading the bank’s app off his phone and turning the .APK into a .JAR, [Thiago] needed to generate an authentication code for himself. He found a method that generates a timestamp which is the number of 36-second intervals since April 1st, 2007. The 36-second interval is how long each token lasts, and the 2007 date means this part of the code was probably developed in late 2007 or 2008. Reverse engineering this code allowed [Thiago] to glean the token generation process: it required a key, and the current timestamp.

[Thiago] found another class that reads his phone’s android_id, and derives the key from that. With the key and timestamp in hand, he figured out the generateToken method and found it was remarkably similar to Google Authenticator’s implementation; the only difference was the timestamp epoch and the period each token lasts.

With the generation of the security token complete, [Thiago] set out to put this code into a hardware device. He used a Stellaris Launchpad with the Criptosuite and RTClib libraries. The hardware doesn’t include a real-time clock, meaning the date and time needs to be reset at each startup. Still, with a few additions, [Thiago] can have a portable device that generates security tokens for his bank account. Great work, and great example of how seriously his bank takes account security.

Google Security Certificates Forged

Recently, Google discovered that a certificate authority (CA) issued forged certificates for Google domains. This compromises the trust provided by Transport Layer Security (TLS) and Secure HTTP (HTTPS), allowing the holder of the forged certificates to perform a man-in-the-middle attack.

To validate that the website you’re visiting is actually who they claim to be, your browser ensures that the certificate presented by the server you’re accessing was signed by a trusted CA. When someone requests a certificate from a CA, they should verify the identity of the person making the request. Your browser, and operating system, have a set of ultimately trusted CAs (called root CAs). If the certificate was issued by one of them, or a intermediate CA that they trust, you will trust the connection. This whole structure of trust is called a Chain of Trust.

With a forged certificate, you can convince a client that your server is actually You can use this to sit between a client’s connection and the actual Google server, eavesdropping their session.

In this case, an intermediate CA did just that. This is scary, because it undermines the security that we all rely on daily for all secure transactions on the internet. Certificate pinning is one tool that can be used to resist this type of attack. It works by associating a host with a specific certificate. If it changes, the connection will not be trusted.

The centralized nature of TLS doesn’t work if you can’t trust the authorities. Unfortunately, we can’t.