Slashdot Mirror

How is this different from the commercial solution that ID Quantique offers now already for several years?

http://www.idquantique.com/

The NSA has apparently compromised random number hardware and software packages throughout the industry.

Could this be fixed by using an entropy server?

Suppose some group hosted a random number server. A verified source of true randomness which can be trusted by the reputation of the people involved, in the same way that we trust the people who make Tor, Mozilla, and linux.

It would be a single point of failure, but also a single point of defense. We could put all the best practices and best ideas of security into one place, by means of technology, software and legalities. It could be hosted in a privacy-friendly country, it could be monitored and defended by the EFF using legal means, it could use the best technology for generating randomness and have open and easily-inspected software and procedures.

To use the system, a client would:

• Generate a public/private key using whatever entropy is on hand
• Encrypt the private key using the server's public key and send it to the server
• The server returns a packet of random numbers, encrypted using the client's key
• The client generates a new key pair using the returned entropy
• The client uses that key pair from then on

This is slightly weak because the NSA could record the conversation and "simulate" the client computer to recover the generated keys, but doing this is much harder than cracking weak keys. In the server model the weak key is used once, instead of being used all the time. Also, simulating a computer (including nuances of software version and hardware quirks) is much harder than finding weak keys.

(To find weak keys, gather all the keys you can find and calculate GCD on pairs of keys. In practice, about 1 percent of all keys on the net have common factors. Most of these come from systems with low entropy - headless systems (routers, firewalls, servers) with no user interaction for randomness.)

In one action we could fix the security of much of the software used in the internet.

Any volunteers?

(I'd love to, but it has to be outside the US. I'll donate $1000 towards costs if the idea is viable.)

In response to the current situation, I've been researching random number generators - especially the builtin one in Intel processors.

It's impossible to tell in general whether there's a vulnerability in a random number generator. It's a "computationally infeasible" problem, the best we can do is check for known deviations from randomness. If you know how it deviates, it's easy to check but beyond that there's no way to tell.

If the NSA has modified devices to reduce the entropy of random keys, then eventually two keys will have the same factors. This is easy to determine: The GCD algorithm will very quickly tell you what factors two keys have in common. ...and this is exactly what is seen in practice! Some 0.3% of keys tested had common factors: statistically, a *huge* percentage.

With a very large number of keys, you don't need to try N*(N-1) pairs of keys: partition the keys into two sets, multiply all the keys in the first set together, multiply all the keys in the second set together, then calculate GCD(Set1,Set2). In one calculation, you've determined whether any single key in the first set has factors in common with the any key from the second set.

Bruce Schneier believes that the algorithms are robust, and that the NSA is using other methods to break the encryption. Here's one likely way that they are doing it - they weaken the random number generator on a class of devices, harvest all the encryption keys they can find, then look for common factors.

From this article talking about the study: "[Researchers from the linked paper found] “vulnerable devices from 27 manufacturers. These include enterprise-grade routers from Cisco; server management cards from Dell, Hewlett-Packard, and IBM; VPN devices; building security systems; network attached storage devices; and several kinds of consumer routers and VoIP products [1]."

The upshot is this: even locally-generated RSA keys are not guaranteed to be safe, nor will they ever be. When you can't trust the hardware, all bets are off.

Clavis

I came across this site a long while back

http://www.idquantique.com/true-random-number-generator/quantis-usb-pcie-pci.html

They sell hardware that sends a single photon at a time. The photon's polarity is random. It hits a mirror/prism or something, and if it's one polarity, it goes to sensor A, if it's the other polarity, to goes to sensor B.

Truly random. About $2.1k for the PCIe card.

Note that you can readily buy your own USB or PCI quantum number generator generator: http://www.idquantique.com/true-random-number-generator/products-overview.html

• Random.org provides random data generated by radio noise. You can get as much random data as you'd like. Gaming websites download their random data in 5MB chunks to use for card shuffles and dice rolls.
• HotBits is a similar idea, but uses radioactive decay instead of radio waves
• If you want to do it in house, you can do so with a smoke detector and a webcam. This was submitted to slashdot in 2006
• Finally, if you need a ton of random numbers, and they must be random, you can buy RNG hardware

What do i do? if I don't really care if it's random, I use the RPG from the programming language I'm using, or /dev/random. If I really, really care that it's random, I download a chunk of data off random.org, and either use that for the numbers, or use it to seed my RNG. For the most part, anything more than that is overkill.

I still think (from my fuzzy understanding of this attack) that it uses a specific implementation detail that depends upon the system used, and might be relatively easy to patch. Maybe they can use different wavelengths of photons, one for a test and one not--I don't have the expertise to say how much of a redesign is necessary. The article makes it sound like it's not a huge deal, and the Toshiba guys say in one of the other articles that their system isn't susceptible to these attacks when properly operated.

Currently the problem is quite general, because most quantum cryptosystems today use detectors of the vulnerable type. We think it is patchable, just not by the approach the Toshiba group practices, but patchable. (We dislike Toshiba's approach for not being general and thorough, but more of a quick band-aid.) During the past 20 years there were a couple problems of similar magnitude in quantum crypto, and they were solved. Note that similar problems periodically show in implementations of classical crypto.

The future of quantum crypto will now be decided, from one side, by the market, and from another side, by publicly disclosed mathematical developments on various classical ciphers (which can be cracked overnight, but can also be proven more secure... I'm not a mathematician so I won't venture a guess for the odds of either). In quantum cryptography there is at least one well-engineered commercial system, several advanced commercial prototypes (Toshiba has one), and the hacking efforts are going to eliminate all easy loopholes in a reasonable time. It is also important how well quantum cryptography can be meshed into networks with many nodes and links. There have been several demonstrations of quantum crypto networks, the latest in Japan last year.

The current commercial systems (like ID Quantique's Cerberis) use quantum cryptography as an extra security layer on top of classical crypto. To get to the master key used to encrypt the data, one needs to crack both quantum key distribution and classical key distribution at the same tme. We temporarily compromised the quantum layer in this work, but in a commercial installation the data security would hang on the classical crypto, until the quantum layer is patched. Of course the security of the symmetric ciphers (normally AES with frequent key changes) used for high-speed data encryption is another question, but I think there is also an option to establish a low-bandwidth highly-secure channel encrypted by one-time-pad. The whole reason AES is offered with quantum crypto is that the performance of the classical crypto has spoiled everybody, and the users do not want to separate communication into high-security and low-security categories. They just want to encrypt the whole 10 Gbps link, so this is the default option.

I would expect the government to use something like this for something as important as this green card lottery. At around $2k, it seems worth it to avoid relying on system entropy to seed the random number generator. As impressive as pseudo-random generators are, seeding them introduces an attack vector that physical random number generators avoid.

Even telecommunication wavelengths APD have been available for a long time. They are mostly used for single photon detection.

http://www.idquantique.com/products/id200.htm

I guess the price drop is news, although my guess (the intro screen discouraged me from RTFA) is that the real real news, since they are talking about it in the context of photonic, is that they have integrated the device on a chip.

• id Quantique (Switserland)
• MagiQ Technologies (USA)
• SmartQuantu

• id Quantique (Switserland)
• MagiQ Technologies (USA)
• SmartQuantu

I have been there, and can give my impresson. I think, this is a big milestone for quantum cryptography. This has been the most massive and convincing demonstration of the technology up to the date, nothing like any before. Yet, it seems to have received relatively little press attention.

The demonstration was a conclusion of an European project in which several tens of research groups collaborated. The main thing it produced are network protocols for a quantum cryptography network. Several months ago, the plan for this demo was four quantum cryptographic links. However, it was easy to plug any quantum crypto link into the network, so six research groups and one commercial company ended up bringing their systems to Vienna (the latter, idQuantique, actually contributed three links to the network).

Out of these nine systems, seven performed flawlessly for several days, one worked for half an hour and then died (the secure key produced in the first half an hour was still used by the network; the failure was blamed on a software problem in that system), and one prototype did not quite survive the flight to Vienna (hard disk was trashed by baggage handlers). Given that most of the systems were research prototypes, the statistics actually looks good to me.

Since the network topology allowed for redundant paths between most of the nodes, the actual failure of one link and simulated failure of another did not prevent the network from operating. (The network topology on the picture as not quite complete: at the last moment, eighth link and one more node were added off the topmost node.) During the demo, there were shown securely encrypted video links between the nodes, and telephone calls. The video links were encrypted with AES with session keys provided by the network. The telephone calls were encrypted with one-time-pad provided by the network. Resiliency to failures was demonstrated: one link was broken on purpose (eavesdropping was simulated by inserting a polarizer), and a key store in another was exhausted during one of the one-time-pad encrypted calls. In both cases, the key distribution was automatically re-routed through other paths and nodes.

The network software implemented so far requires all nodes be trusted and secure. However, I know that algorithms are under development that would allow secure key distribution in a bigger network where up to a certain percentage of nodes might have been compromised.

The demo was on the first day of the meeting. The other two days were just a very good research conference, with no press attending. I apologize if I got some details above not fully correct.

Most of these implementations (like http://www.idquantique.com/products/vectis.htm) use quantum mechanics only for key exchange and not for generating a one time pad.

The Group of Applied Physics at the university of Geneva, Switzerland is playing with quantum teleportation for some time already, visit

http://www.gap-optique.unige.ch/ for more information.

A spin-off also sells products based on this technology:

http://www.idquantique.com/

We already have commercial quantum cryptography systems http://www.idquantique.com/ http://www.magiqtech.com/. And yes, those implementations are probably breakable in theory (they have no security proof covering the particuar implementations and they may be vulnerable to certain side channel attacks). However, by identifying side channels and bounding the information leaked through them and carefully monitoring that the devices are behaving as expected it should be possible to implement quantum cryptography which is unbreakable by any adversary bounded by the laws of quantum mechanics.

The Kish scheme on the other hand is secure against an adversary bounded by the circuit model. Now, the circuit model is not a fundamental theory of nature -- quantum mechancs is.

Although it's rather belated, I did find this.

http://www.idquantique.com/products/quantis.htm

This is possibly the most impressively elegant solution for computer RNG that I've seen. High bitrate, and doesn't contain nasty radioisotopes.

I'm sure you could, but why do that when you can buy an off-the-shelf quantum RNG? It's so much easier, and probably much more reliable. Furthermore, since it relies on quantum effects, it is 100% random. (Actually, manufacturing irregularities probably bias it slightly in favor of one state. Even if that's the case, it's still non-deterministic, unlike all software implementations.)

If you need only a few random numbers, I'd suggest using this website, which relies on the aforementioned product. To prove that determinism is wrong, I've been using it for months as a sort of "quantum coin flip."

Don't downgrade your CPU for a thermal noise based RNG. Just drop one of these in your machine of choice and enjoy the Quantum derived random numbers :-D

Aren't they already doing this with Cryptography? I agree with your point totally, and see alot of potential there!

Jho

The Vectis link encryptor is a hardware Quantum Cryptography appliance for point-to-point wire-speed link encryption. It combines Quantum Key Distribution (QKD) and Advanced Encryption Standard (AES) encryption engines in a stand-alone unit. Vectis is a Layer 2 network transparent encryption device that securely bridges two Fast Ethernet (IEEE 802.3u) fiber optic networks.

Simply put, fail-safe encryption does not and will not exist. Due to increases in computer processing power, encryption is by definition a temporary safeguard.

Safe encryption exists, it's called One-Time Pad. And you can actually buy devices that use it to securely transmit data. ID Quantique has implemented a quantum key distribution system that uses one-time pads. No amount of computer processing power can break it, not even a quantum computer. You can't use this implementation of a one-time pad for WiFi devices though.

Simply put, fail-safe encryption does not and will not exist. Due to increases in computer processing power, encryption is by definition a temporary safeguard.

Safe encryption exists, it's called One-Time Pad. And you can actually buy devices that use it to securely transmit data. ID Quantique has implemented a quantum key distribution system that uses one-time pads. No amount of computer processing power can break it, not even a quantum computer. You can't use this implementation of a one-time pad for WiFi devices though.

You're absolutely right. Except for the "very hard" part.

It costs about a hundred bucks to buy a good (secure) random number generator. Noisy diodes, for instance, work great. Hell, taking photos of lava lamps works, too.

QRNG

SafeXcel

VIA C3 RNG

When used properly, One Time Pad is impossible to break. Of course, carrying around enough truely random characters/bytes for all of your encrypting needs without getting caught is another story

Yes, the OTP is the way to go -- sequence of random bytes, which you simply XOR with your message. Dump out /dev/random to a CD-R or DVD-R, make a copy for your friend, and you've both got nice one-time-pads that will probably last you quite some time.

What's interesting is that quantum physics offers several new things that will help implement excellent OTP systems... over existing fiberoptic telecom systems, no less! This is really exciting stuff.

First, quantum physics offers us a new way to generate truly random numbers for your OTP. Your rand() function sucks, I guarantee you. /dev/random is very good, but slow... /dev/urandom uses hash mixing so isn't nearly as random. Both rely on physical events, time intervals, and possibly thermal noise. In comparison, a quantum random number generator in theory gives you random bits that are totally un-influencable.

So now you've got your random bitstream... what do you do with it? Well, you hook up the OTP stream to a laser-based system that sends essentially single photons down an optical fiber. The idea being that single photons are either received by your friend or intercepted (absorbed) by your enemy. They can't be copied. Anyway several factors complicate this process but the basic idea remains. It's for real.

So your computer can generate a random OTP, securely send it to your friend (without fear of interception), and now you can both exchange classical data encrypted with your OTP. Repeat as necessary. If the physics behind this is sound, we shouldn't have to worry about algorithmic attacks in the future. Here's a rather complete article describing everything.

MagiQ is NOT the first company to sell a quantum encryption system, ID Quantique was, last year.

Yes, you are perfectly right. These guys (see http://www.idquantique.com/ have been seeling QC hardware for a while now (since 2002, at least), and other cool stuff as well (like true random generators based on QM).

I think slashdot had even news about this, but it's no surprise they forget.

These guys in Switzerland even sell devices to do quantum crypto.

>But, you still have to distribute the pad.

How about using Quantum Key Exchange? Seems like the perfect solution.

Off the top of my head (I know real cryptologists can do better) here's what a secure system employing currently available quantum woo woo might look like in a world of quantum cryptography:

Quantum transmission of a bitstream can detect interception. This can be used to distribute pads, as interception destroys a message. If subsequent transmission of an encrypted message succeeds, then it has been transmitted securely. Man-in-the-middle attacks can be detected by monitoring response times, as even quantum computers will introduce statistically detectable delays in message transmission.

For "quantum transmission of a bitstream", you need single-photon optics. Here's a turnkey quantum transmission system or if you'd like to build your own, do a google search for "single photon LED".

Now if we could just get everybody to actually use encrypted email as a matter of course, than all of this encryption falderol wouldn't be a moot point in terms of privacy and security of regular folks.

Um, knowing the mood swings of some people I know, I would have to say that humans are quite good at randomness...

And you don't need quantum computers to do real randomness, all you need is this box from Id quantique.

To state the obvious, there's no question that computers, given enough processor power, can produce really good random numbers. But it's getting them produced efficiently en masse that is the problem...

One comment: even if you need to cool your detector to cryogenic temperatures, you don't have to have your customer pour liquid nitrogen (or did they say liquid helium?) into the commercial device. This is what compact no-maintenance closed-cycle coolers are for.

Plug #1: idQuantique
Plug #2: Magiq Technologies
Plug #3: Los Alamos lab (yes there used to be a site there)
Plug #4: Our own research (not commercially-oriented yet)

It's an interesting article that outlines many of the considerations and hurdles one encounters in this field, but there's no breakthrough here. We haven't had a breakthrough since December, 2000 when researchers at UCSB built their latest prototype capable of consistently detecting such photons. We're bound to make some more breakthroughs soon, it's premature to say we already have recently.

If you're still not clear on the whole quantum cryptography deal, idquantique.com has a good introduction (pdf, of course).

Home Page here:

www.idquantique.com/index.html

The conclusion of the article states that the system is currently commercially available. Here is a link to the QKD System.