Serious Flaw Emerges In Quantum Cryptography
technologyreview.com
technologyreview.com
(Disclosure: haven't bothered to read the arXicle.)
How would you do this with classical cryptography?
Isn't the point about this particular flaw that it is pretty much undetectable (other than inspecting the hardware itself (which is outside the scope of the article that treats it as a black box)). If the same were to be implemented on classical cryptography it would be comparatively trivial to detect if someone tried to sneak in an old message interleaved with a new message (you know the plaintext + key and thus you know exactly what that will generate).
The compelling argument for quantum cryptography is that it is provably secure (well, that's the theory) and it is quite difficult to prove that the hardware has not been tampered with.
The thing you could do with classical cryptography is to in some way "leak" the key (such as what debian inadvertently did with openssl) but the whole point of quantum cryptography is to have a perfect key distribution to combat any known or unknown attacks.
I found the abstract, http://arxiv.org/abs/1201.4407 , shorter and more informative than the article.
Nearly every classical cryptography device uses a source of entropy; if you break that intentionally then you have a side-channel.
Quantum key distribution (QKD) promises security based on the laws of quantum physics, and not on computational assumptions. However, in practice, QKD experiments have been attacked through side channels. One possible side channel comes from a malicious manufacturer. Side-channel attacks also affect classical cryptography, of course, but might be more important for QKD because:
1. Quantum devices are harder to build and test, and less understood, than classical devices, so side-channel attacks might be easier, at least for now.
2. The goal of QKD has always been to reach higher security than is possible classically.
"Device-independent" (DI) QKD solves this problem. DIQKD allows for extracting a secure key even if the crypto devices are manufactured by your enemy. This should be hard to believe; it is completely impossible classically. It is very cool that it is (probably) possible quantumly.
I say "probably" because full DIQKD security proofs do not yet exist; giving a full proof is a major open problem in the field. From the perspective of people in the field, the next step in the DIQKD roadmap would be to deploy a DIQKD experiment. Although standard QKD schemes are even commercially available these days, deploying a DIQKD scheme is another major open problem because the schemes proposed currently are far too inefficient to be practical and require noise rates below current photon detector technology.
The new paper says that we should reconsider this roadmap. Even if we are able to give a DIQKD security proof, there is still a problem, because when you reuse untrusted devices they can leak previously generated keys. I don't have a lot of time to explain this and don't know that it is an especially novel observation. It can probably be worked around with more sophisticated key-generation methods. But that's essentially the current status.
You mean, if you store the encryption key and later reveal it to outside sources, your secure communication is no longer secure? SHOCK AND AWE.
It's complete fluff that has nothing to do with quantum cryptography, just the intrinsic chain-of-trust of whatever hardware you're using. If something you're using is untrustworthy, the whole chain is - this is not a new discovery.
Authentication can be established using a shared secret (which is why purists sometimes refer to QKD as a key expansion protocol). Or, it can be established using signatures and certificate authorities. It is worth pointing out that man-in-the-middle (MITM) attacks must be made online; if you break a signature scheme a year after the QKD protocol finishes, it does not compromise the key.
If I buy two 5-bay DROBOs, 10 2 TB HDs, and a hardware random number generator, I could make a multi-TB One Time Pad, and copy it onto the second DROBO.
I keep DROBO one, and physically carry DROBO two to my intended recipient.
What are the problems with this?
It's cheap. It's as secure as any communication could possibly be. It provides for a whole lot of communication, with relatively little physical effort.
Also you can't prove that someone doesn't sniff the traffic when you copy it to your second DROBO and you can't prove that none of the drives have been copied afterwards.
Not saying that your approach isn't "secure enough" (I'd guess that's what they do on submarines?), but compared to (the theory of) quantum cryptography it has many flaws.
> You can't prove that you can trust the carrier.
I said that I physically carry DROBO two to my intended recipient. I can trust myself.
> Also you can't prove that someone doesn't sniff the traffic when you copy it to your second DROBO and you can't prove that none of the drives have been copied afterwards.
There is no such thing as secure communication. Copying data from one DROBO to another DROBO is about as secure as I could possibly imagine.
Physical security is a failure point in any system. As much as I can trust my sending location, and my receiving location, I can trust this system.
> compared to (the theory of) quantum cryptography it has many flaws.
Compared to quantum cryptography:
I can't prove that I trust the person who set up the quantum cryptography system.
I can't prove that someone doesn't sniff my connection to my quantum key system. I can't prove that someone doesn't sniff the data coming out on the receiving end.
I think this all boils down to physical security - which is a problem in any secure communication system.
And I think my two DROBO, ten HD, one hardware random number generator, one round-trip plane ticket, system is about - mmm - 4 to 6 orders of magnitude cheaper.
Meaning: my proposed system is no more or less vulnerable than any other, in this regard.
But can you trust yourself to not take a large enough bribe? What if someone hold someone special in hostage?
If you only have to convince yourself (quite limiting scenario) I see no, major, problem with your setup. This of course assuming you have eye-contact with the DROBO at all times etc. etc.
Most scenarios however you can't have as much trust in the carrier as you have in yourself.
But I agree. When reading quantum cryptography and its issues I often get the feeling that its all a bit silly. But I totally get the motivation about it, it's extremely enticing. However, I see why some likes to claim that quantum cryptography is just a way for physicists to get paid :P
But there seems to be a market for it and I have no idea how far it can go.
A problem with public keys is that they rely on math that we presume is hard.
One Time Pads do not depend on that.
2) I can flip bits in your message without you detecting it.
3) I can send random messages and get your receiver out of sync with you.
2) I can always have a Message Digest of my message included.
3) If the Message Digest doesn't match, the message will not be accepted as valid. The receiver will not be out of sync.
Magic token, protocol identifier
Location in key to use
Length of message + salt
MESSAGE - XORed against OTP
Some salt is taken from the next bit of OTP.
Hash of plaintext message
If any of that portion of the OTP has been previously used, the message is invalid. If the hash doesn't match, the message is invalid. Under no circumstances is a new message valid if it uses a portion of the OTP that has been used before.
I can't guarantee a message will arrive. I believe I am correct in thinking that all messages that arrive and pass these tests, have not been tampered with. If the keys are physically secure, the message is secure.
I'm serious, not messing with you. What would be some things you would try to do to get the protocol to misbehave?
I would try to change the location in the key to use. Especially to one that had already been used.
I would try to replace the message, salt, and hash entirely.
I would try to fiddle bits.
I would compile all of the messages, looking for when the pad had been re-used.
I would try to decipher messages, I would try to corrupt messages, I would try to inject my own messages, I would try to use a denial-of-service to prevent you from communicating at all, I would try to force you to consume your entire key to transmit your first message. I would re-transmit old messages, and see how you behaved. I would send cleartext messages telling you that the sender had been abducted, and that you couldn't trust any further messages, sending it as a "trusted associate," or sister, or parent. I would try to gain physical access to the hard drive, and copy it. Having gained access, I could inject all of my own messages, and deny you the ability to communicate at all.
I really, honestly, don't think that my proposed system is any more or less secure than any communication system that would rely upon quantum entanglement to deliver a supposedly secure keystream to both ends.
But it would cost many orders of magnitude less.
Think about what happens given any known plaintext.
Think about the difference between a MAC and a simple encrypted hash.
I'm not giving you random political scenarios or whatnot; I'm looking at this like a simple engineering problem; the benchmark is TLS, not "some theoretical thing that the NSA can't break" or whatever.
I shouldn't have made fun of you to begin with (making fun of people who suggest one time pads is a time-honored sci.crypt tradition that doesn't need propagating). So bear with me. I'm just trying to show you how irritating it is to get a simple encrypted transport right.
Since I will never use, or accept, that portion of the OTP again, this doesn't gain you the ability to decypher a message, or fake a message without detection.
If you both know the plain text, and you have prevented transmission of my original message, then you have that many bytes of OTP that you could use to send that many bytes of faked messages.
If there is another cryptography system you would like to use to encrypt the plaintext, before sending it through my proposed system, then knowing just the plaintext would not help you.
Making fun of people who THINK they're using OTP is the time-honored tradition.
I'm proposing to ACTUALLY use OTP. I acknowledge that someone who intercepts all of our messages can prohibit us from communicating. But they can't fake messages. I acknowledge that if someone steals our key, we are compromised - but that is true of any system.
I acknowledge that transport is hard.
You do not accept QC. Okay, I'm not going to win you over.
If you accept QC, then I offer up that physical transport of a OTP is just as secure, and orders of magnitude cheaper.
Whatever MAC / transport systems have been used for QC, can be used by my proposed system. I am no better, or worse, than they are.
A real, sound cryptosystem would use keys in at least two places in the protocol (once to provide confidentiality for the message, and once to provide integrity).
Confidentiality, and integrity.
You see what I mean about "yes-but"-ing ones way into treacherous confidence. Believe me when I say that a lot of systems have been deployed using this same design process, and all of them failed --- it is hard to name a well-designed cryptosystem that didn't succumb to spectacular failures.
And, on another tangent, you can see how your design now begs a pretty big question: between AES and SHA-256, virtually everyone would agree that SHA-256 is the less sound primitive (they're both "sound", but SHA-2 will fall before AES, which is why we're busily selecting SHA-3 right now).
Concern about AES drives you to contemplate OTPs, but forces you to rely on something like SHA-2. An AES design could use AES both for confidentiality and integrity. Either way, you're not getting "perfect" security; you have all the downsides of OTPs and none of the upside.
OTP's are kind of silly.
Unfortunately, all you've done is tell me "it won't work."
When you attempt to inform me why it won't work, your answers boil down to "because."
Why doesn't concatenating "MESSAGE XOR OTP" with "HASH(OTP-SALT, MESSAGE)" both a) provide confidentiality for the message, and B) provide integrity?
It certainly provides confidentially for the message. Without knowing the OTP I use, you will not decipher the message.
And by using another portion of the OTP as a unique, one-time salt for a hashing function (I don't care which hashing function), I am preventing a man in the middle from twiddling bits undetected.
If you want to tell me that I'm wrong - that's great. If you want to explain why I'm wrong, that would actually be useful.
...and Quantum Cryptography boils down to being a fancy way to generate a OTP. Your argument then becomes, "All of the researchers working on Quantum Cryptography are idiots, and they should know better." Extraordinary claims require extraordinary proof. If your claim is that they can't build a physically secure system, because you can't trust a quantum-entagled particle pair to really arrive at both ends uncorrupted, that's one thing. No, your claim is that the underlying math behind OTP is inherently flawed. Message XOR OTP is not secure, even if the man in the middle does not know the OTP.
From the definition on Wikipedia, "A MAC algorithm, sometimes called a keyed (cryptographic) hash function, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC (sometimes known as a tag). The MAC value protects both a message's data integrity as well as its authenticity, by allowing verifiers (who also possess the secret key) to detect any changes to the message content."
The secret key is a sequence of bytes from my OTP. They have never been used before, and they will never be used again.
"While MAC functions are similar to cryptographic hash functions, they possess different security requirements. To be considered secure, a MAC function must resist existential forgery under chosen-plaintext attacks. This means that even if an attacker has access to an oracle which possesses the secret key and generates MACs for messages of the attacker's choosing, the attacker cannot guess the MAC for other messages without performing infeasible amounts of computation."
They cannot guess the MAC for other messages, because they cannot guess the key for other messages, because they do not know the OTP for other messages, because I will never reuse any of my OTP, thus making it a ONE Time Pad.
"MACs differ from digital signatures as MAC values are both generated and verified using the same secret key. This implies that the sender and receiver of a message must agree on the same key before initiating communications, as is the case with symmetric encryption."
No problem. That's what my system does. I tell you what portion of the OTP to use, and you use it. If it's ever been used before, you know the communication channel has been compromised.
http://upload.wikimedia.org/wikipedia/commons/0/08/MAC.svg
The Key (K) is determined by the position in the OTP, specified by the message header.
2. Since the general security of a system is contingent upon its easiest attack (even if that attack is somehow 'rarer'), you might as well use that same hash function to create a stream cipher and once again avoid the huge OTP. (which is why it won't be taken seriously)
3. Security of actual cryptosystems comes from widespread implementation, study, and abuse. While your system may indeed have stronger confidentiality properties, it most likely will have undetected implementation errors due to it not being widely scrutinized.
4. I think the meat of your argument is that BKD (backpack key distribution) is comparable to QKD. I do agree that your comparison is appropriate, but think it says more about QKD than BKD. Quantum key distribution still relies on classical algorithms for authenticating the classical channel (some kind of MAC), and today's QKD products even rely on classical block ciphers, as the QKD-produced keys are quite small.
5. I see no benefits to QKD in general. It only works between prearranged (and physically connected!) pairs of parties. Reimplementing the Internet with QKD means the links are secure, but ISPs still see everything. If quantum computing really does ruin the RSA and DLOG parties, there's certainly other public key algorithms.
That's interesting. I didn't know that a system was considered broken if, knowing plaintext (and breaking a hash function) allows an attacker to rewrite a message. Probably pretty basic stuff to you.
So, for instance, a CBC padding oracle is an attack that allows you to decrypt messages byte-by-byte --- but it's stopped entirely by a proper MAC on the message.
(This is without getting into the fact that a single keystream is not a secure message exchange protocol, and that conventional cryptography has well-tested ways of linking confidentiality secrets to integrity secrets and of marshalling and canonicalizing messages; I'm just answering your question on its own terms).
None of this has much to do with QC, by the way; as I understand it, QC replaces conventional number-theoretic public key crypto, not block and stream ciphers.
I have to build protocols around making sure to not re-use parts of my One Time Pad. Around making sure that I validate messages. Asking for a re-send of a message. Destroy the One Time Pad because it's been compromised, etc.
But at it's core, using a One Time Pad is a secure message exchange protocol. I'm surprised to see you contradict that.
> and that conventional cryptography has well-tested ways of linking confidentiality secrets to integrity secrets and of marshalling and canonicalizing messages
I'm sorry - I don't know what you mean. Can you explain it to me more simply?
Cryptotext = Plaintext XOR OneTimePad.
Plaintext = Cryptotext XOR OneTimePad.
As I said, I have a lot of work to do to handle my One Time Pad... But the fundamental mathematics are secure. And you seem to be saying they are not. What do you mean?
> None of this has much to do with QC,
Agreed - that's why I called it a tangent.
(I don't mean to be offensive. I don't understand bioinformatics, for instance, and probably shouldn't build mission critical things that rely on it.)
And you've genuinely offered no substantive critiques. Sounds like the core mechanic is gold, then.
If there's nothing wrong with the core mechanic, I should be able to buy a commercial system built on it, and know that it has all of the inherent strengths and weaknesses of my core mechanic. And possibly more weaknesses, inherent in the implementation of any security system.
I don't blame you for being frustrated with my responses, but it's my experience that detailed critiques of random crypto schemes on message boards are counterproductive; the designer just "yes, but"'s the critique until all the low-hanging fruit is picked (each of which was a devastating flaw in their original scheme), and the conversation ends with a no- less- fatally- flawed system and a designer who is perversely more confident.
I'm proposing a hard drive and a plane ticket.
Your critique is based upon ego alone.
(It seems like it should be possible to devise a non-algorithmic MAC using a second pad. But now we're back in theory-land.)
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA!