[HN Gopher] Cryptographers achieve perfect secrecy with imperfec...
___________________________________________________________________
Cryptographers achieve perfect secrecy with imperfect devices
Author : theafh
Score : 69 points
Date : 2022-02-25 16:13 UTC (6 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| NateLawson wrote:
| QKD relies on many underlying assumptions, which researchers
| conveniently sweep under the rug while continuing to build
| castles ever higher on the theoretically "perfect" but insecure
| foundation. It is unclear how the underlying implementation for
| QKD can be made as secure as modern silicon countermeasures are
| against attacks like fault injection.
|
| A while back, I summarized all the ways I could think of where
| the layer under QKD fall apart. I think the list is still valid:
|
| https://rdist.root.org/2008/10/24/quantum-cryptography-is-us...
| motohagiography wrote:
| > The universe hadn't decided what the value would be before it
| was measured," said Colbeck. "That's the origin of the security."
|
| My naive security architect view is, I get the impression the
| people doing quantum engineering and those working as
| cryptographers have a very narrow overlap.
|
| Reading about quantum key agreement/distribution (QKD), it's
| different from cryptographic functions where you have things like
| convolution and substitution functions, or using hashing to to
| distribute the information over a very large finite field. The
| security in quantum appears inseparable from the encoding and
| implementation itself, which implies there is a proof and
| description of entropy-in vs. entropy-out that I haven't gone
| deep enough to locate and read yet.
|
| I'd speculate there would be some interesting unification of the
| Shannon information entropy of a plaintext with physical state
| thermodynamic entropy of the "enciphered" Qbits, given
| transmitting quantum keys like this sounds more like encoding
| bits into a physical quantum function than a keyed "encryption"
| scheme for data for the purposes of security.
|
| To do the data exchange, it's not _encrypted_ to a key per se,
| but it sounds more like a lookup table (LUT) over a field of qbit
| state probabilities. Doing certification of the security of such
| a system is different from a normal NIST algorithm candidate
| because it reads like you could write and evaluate the encoding
| scheme as a proof.
| Moodles wrote:
| > My naive security architect view is, I get the impression the
| people doing quantum engineering and those working as
| cryptographers have a very narrow overlap.
|
| Correct. It's also the difference between theoretical security
| for infinite time vs security for something like 10^30 years.
| Is it really worth changing tried and tested algorithms and
| implementations already in place?
| CodesInChaos wrote:
| The asymmetric encryption/key-exchange algorithms that
| survive large quantum computers are all quite experimental
| and each has at least one major downside compared to RSA and
| (EC)DH. Still I'd prefer them over QKD.
| klickverbot wrote:
| > My naive security architect view is, I get the impression the
| people doing quantum engineering and those working as
| cryptographers have a very narrow overlap.
|
| You probably aren't wrong, but also note that popular science
| articles are probably not the best basis for judging this. :) A
| number of people working on QKD have done serious work on
| classical cryptosystems as well, although the overlap of that
| set with people working "in the trenches" of practical IT
| security is of course yet another topic.
|
| > To do the data exchange, it's not encrypted to a key per se
| [...]
|
| I'm not sure whether this is what you are wondering about, but
| the actual data exchange is completely separate from the key
| distribution. Particularly for the entanglement-based protocols
| like used in device-independent scenarios, there isn't really
| any data exchange between the parties during the key
| distribution stage at all (apart from the classical post-
| processing steps such as error correction after the fact).
| Rather, the quantum resource provides random, but correlated
| bit strings at the two nodes. Only after the QKD protocol has
| finished is there actual data exchange using the secret key
| material, probably using the key as a one-time pad to keep the
| information-theoretic security guarantees.
|
| Thus, trying to think about these protocols in terms of data
| transfer doesn't strike me as particularly natural; in fact, if
| the entangled state shared between Alice and Bob is maximally
| entangled, the raw bits obtained from the quantum devices are
| always going to be completely random.
|
| The security proofs are indeed based on careful entropy
| considerations. You mentioned implementation details of
| classical cryptosystems. These primitives - S-boxes, etc. -
| motivate why we should reasonably expect cryptanalysis on such
| algorithms to be hard in practice, even though we know that
| they can't be secure considering information theory only. In
| the QKD case, however, we can make information-theoretic
| security statements without any reference to computational
| power. Thus, a security analysis will look at quite a different
| set of things: on one hand, whether the entropy accounting is
| correct, and on the other hand, whether the practical
| implementation actually corresponds to what that accounting
| assumes.
| klickverbot wrote:
| First author of one of the preprints mentioned in the article
| here (theory in Paris/Geneva/Zurich/Lausanne, experiment in
| Oxford) - happy to answer any questions! I obviously speak only
| for myself, not for any of my colleagues, and as a matter of
| course, I should also mention that publication in a peer-reviewed
| journal is still pending for these results.
|
| One point to mention -- which I feel quite strongly about, and I
| think my collaborators do as well - is that sweeping
| generalisations like "perfect security" are really not the point,
| and, if anything, have mostly done the field a disservice. Such
| statements do make for catchy headlines, and while there is a
| solid technical meaning attached to them (information-theoretic
| security), to a wider audience they might suggest that QKD
| replaces the need for careful security engineering, which is
| definitely not the case: if your processing nodes, say, leak out
| the generated key material via a classical side channel, no
| amount of theoretical security guarantees will save you!
|
| Rather, device-independent quantum key distribution allows you to
| scale back the assumptions on your implementation to a well-
| motivated, minimal set. To me, this is already intriguing enough
| without the need for hyperbole!
| Vervious wrote:
| can you link the preprint by chance? I can never find the
| actual papers from quanta...
| NoKnowledge wrote:
| > Rather, device-independent quantum key distribution allows
| you to scale back the assumptions on your implementation to a
| well-motivated, minimal set. To me, this is already intriguing
| enough without the need for hyperbole!
|
| Would it be accurate to say it is scaled back to the level
| achieved by classical (non-quantum) cryptography?
| klickverbot wrote:
| > Would it be accurate to say it is scaled back to the level
| achieved by classical (non-quantum) cryptography?
|
| Not quite. Classical cryptography of course requires the
| additional assumption that the computational capacity of the
| attacker is limited (at least if the amount of key material
| available is less than the length of the messages to be
| exchanged). QKD does not need any such computational
| assumptions. Looking at this purely from a theoretical
| perspective, I hope you'll agree that the ability to create
| new shared randomness "out of thin air" by drawing on quantum
| correlations, and to do so an information-theoretically
| secure fashion, is a pretty neat trick.
|
| Now, if you asked me how likely it is _in practice_ that
| $THREE_LETTER_AGENCY has broken your cryptosystem to the
| point where they can feasibly attack it/have backdoored it,
| compared to the likelihood that they've bugged your devices
| in a supply chain attack or found any number of other ways to
| compromise the practical implementation, I suspect my answer
| wouldn't be much different to yours. Nevertheless, I still
| think it is interesting to explore additions to the
| cryptographer's toolbox that, in a very practical sense, have
| a rather different profile of assumptions and tradeoffs.
| NoKnowledge wrote:
| Oh absolutely, the theory behind QKD is fascinating! And I
| do think that some day there may be actually secure
| practical implementations, maybe even ones that are
| practical for more than a few niche applications.
|
| But you mentioned the assumptions on the _implementation_ ,
| not on the underlying mathematics. The thing that concerns
| me is that QKD introduces additional hardware to operate,
| and there have been many demonstrations of weaknesses in
| that hardware that threaten the overall security of the
| system. With DIQKD you ensure that those issues no longer
| affect security (again it is absolutely remarkable that
| this is possible at all), but now you still have to concern
| yourself with all the implementation vulnerabilities that
| also plague classical cryptography. In that sense I mean
| that the _implementation assumptions_ are now the same.
| cryptonector wrote:
| QKD continues to be cryptography snake oil. Interesting for
| research, useless for actual real-life use.
| fsh wrote:
| The first sentence of your paper abstract is:
|
| _Cryptographic key exchange protocols traditionally rely on
| computational conjectures such as the hardness of prime
| factorisation to provide security against eavesdropping
| attacks. Remarkably, quantum key distribution protocols like
| the one proposed by Bennett and Brassard provide information-
| theoretic security against such attacks, a much stronger form
| of security unreachable by classical means._
|
| This is not wrong, but in my opinion quite misleading. QKD is
| no replacement for asymmetric cryptography since it requires
| exchanging a secret key before the communication can take
| place. This makes it functionally equivalent to a symmetric
| stream cipher. So why do you mention prime factorization and
| cite RSA? The security of QKD should be compared to that of the
| best symmetric algorithms, not that of asymmetric ones.
|
| I have seen this pattern in many talks and papers from the
| field. Maybe the issue is that the QKD community seems to have
| almost no overlap with the IT security community. In my
| experience, QKD people almost never talk about how you would
| actually use and/or attack a system _in practice_.
| CodesInChaos wrote:
| I believe you can achieve secure communication by combining
| QKD with an asymmetric signature algorithm (hash signatures
| being a particularly interesting choice), while that's not
| possible by combining a stream cipher with a signature
| algorithm.
| klickverbot wrote:
| > QKD is no replacement for asymmetric cryptography since it
| requires exchanging a secret key before the communication can
| take place.
|
| Your general point about QKD "promises" vs. practical IT
| security is well taken, particularly as I am much more of a
| general quantum physicist and spare-time compiler/infosec
| geek than a QKD person myself.
|
| However, note that asymmetric cryptography doesn't really
| solve the authentication problem you mention either. If you
| don't want to place your trust in some sort of PKI, you are
| back to Alice and Bob having to meet first to exchange some
| sort of key material (e.g. their public keys) to later avoid
| impersonation. Given an authenticated channel, both QKD and
| classical public-key cryptography can construct a secure
| channel for messages of arbitrary length, but the latter only
| for computationally bounded attackers. Of course, this is not
| to say that a trusted PKI can't be a sensible assumption in
| practice.
| fsh wrote:
| All of this is correct. But I still think it is misleading
| to create the impression that QKD could be a replacement
| for RSA. Especially, since asymmetric cryptography and PKI
| are cornerstones of the modern internet. Why don't you
| change the abstract and cite Rijndael or something like
| that? Your work is a very impressive achievement, I am sure
| Nature will publish it either way.
| hannob wrote:
| QKD advocates have been doing this for ages, it's been
| pointed out repeatedly that they make dishonest claims and
| they continue to do so. Here's a paper from 2004(!) pointing
| this out: https://eprint.iacr.org/2004/156
|
| It's not an accident, it's deliberate deception.
| lanstin wrote:
| I always read perfect secrecy as a term of art with some
| technical meaning.
|
| This protocol seems to solve the communication at a distance
| problem for which asymmetric encryption was developed but since
| then a lot of other uses for public key, e.g. signing and
| multi-party decryption and so on have come out of public key.
| Do you think there will be entanglement based replacements for
| these?
| klickverbot wrote:
| > I always read perfect secrecy as a term of art with some
| technical meaning.
|
| That's indeed the case, but I fear the subtle technical
| definition here is usually one of the first things to go in
| the cycle of press releases and news articles, entirely too
| quickly giving rise to headlines that speak of "unhackable
| cryptography" or things like that. I've slightly edited my
| above post to clarify this, thanks.
|
| > Do you think there will be entanglement based replacements
| for these [other protocols]?
|
| One thing to note is that QKD is fundamentally a primitive to
| create shared, private randomness, not a communication
| channel - of course, the output can be used as the key for
| one-time pad encryption, but you might as well use it some
| different way.
|
| For applications beyond that, I am really not an expert, but
| from what I know, people are looking into a variety of
| protocols, such as for leader election. There was a review
| article a few years back by Wehner et al., "Quantum internet:
| A vision for the road ahead"
| (https://www.science.org/doi/10.1126/science.aam9288), which
| highlights some proposals.
|
| As for applications like signing, one aspect to consider is
| that quantum entanglement will, at least for another decade
| or two, always be much shorter-lived than classical data at
| rest. Thus, most practical quantum protocols will boil down
| to creating and making use of entanglement in a short amount
| of time, e.g. to initially establish some sort of shared
| secret, make a coordinated decision, etc.
| eiejejr wrote:
| WallyFunk wrote:
| Worth reading this:
|
| > Quantum Theory Demonstrated: Observation Affects Reality
|
| https://www.sciencedaily.com/releases/1998/02/980227055013.h...
|
| Would like to see this applied in a cryptographic system (if it
| hasn't already been done). The cryptosystem gets destroyed upon
| observation or an attempt to measure it is in place. Caveat
| being: the secret(s) gets destroyed upon someone attempting to
| crack them.
| lisper wrote:
| This article is very misleading, which is typical of QM
| material of this era (early 90s).
|
| > Strange as it may sound, interference can only occur when no
| one is watching.
|
| This is not true. The correct statement is that interference
| only manifest itself in isolated systems, i.e. systems that are
| not entangled with anything outside of themselves. Systems that
| are being "measured" or "watched" are entangled, but they are
| not the only such systems. _Any_ entanglement outside of the
| system under consideration is enough to stop interference
| effects from manifesting themselves.
|
| The reason I say "outside of the system under consideration" is
| because the ability to observe interference depends on where
| you draw the line between the system you are measuring and
| everything else. For example, in an EPR pair you can choose to
| either consider a single member of the pair, in which case you
| cannot observe any interference, or you can consider the pair
| as a whole, in which case you can.
| cryptonector wrote:
| If there's a non-political topic that HN should consider banning,
| it's QKD. It has been, is, and will continue to be crypto snake-
| oil.
| NoKnowledge wrote:
| The article suggests that quantum key distribution (QKD) is a
| replacement for a courier, but that is not true. Distributing an
| initial small secret key (which allows authenticity of the post-
| processing of the quantum measurements) is still required.
|
| Also I think the added value of device-independence is
| overstated. While it does indeed prevent loss of security by
| faulty quantum hardware (even if constructed maliciously), there
| is still a lot of classical post-processing required. That device
| still needs to be trusted. For example, when the device is
| outputting the shared key, it still needs to be trusted that it
| isn't also delivering that key back to Eve.
| mikeiz404 wrote:
| > The article suggests that quantum key distribution (QKD) is a
| replacement for a courier, but that is not true. Distributing
| an initial small secret key (which allows authenticity of the
| post-processing of the quantum measurements) is still required.
|
| Is checking authenticity needed if you're communicating with
| just one party?
|
| From what I understood from the article the data received can
| be assumed to be random and private between two parties if a
| high enough win rate is achieved.
|
| Or is checking authenticity to guard against another party
| taking the entangled particles but not the key used for
| authenticating?
|
| FYI I don't have very strong knowledge in this area.
| fsh wrote:
| Without authentication, _any_ form of communication is
| susceptible to a man-in-the-middle attack. You simply don 't
| know who you are communicating with.
|
| This makes using QKD very hard to justify in practice. If you
| have exchanged a pre-shared key (which is required for
| authentication anyway), you can just use a symmetric stream
| cipher like AES for encrypting the communication. This is
| many orders of magnitude cheaper and faster than QKD and
| works independently of the communication medium. Also it
| doesn't look like AES is going to be broken anytime soon.
| NoKnowledge wrote:
| Yes, otherwise how would you know you are indeed
| communicating with that party?
|
| Otherwise the standard Person-in-the-Middle attack would
| apply: Eve (claiming to be Bob) first runs a full protocol
| session (quantum + classical communication) with Alice,
| resulting in a shared key X. Then she does the same to Bob,
| resulting in a key Y. When Alice wants to encrypt a message
| to Bob, she encrypts with X. Eve can decrypt (and optionally
| re-encrypt with Y and forward the message to Bob).
___________________________________________________________________
(page generated 2022-02-25 23:00 UTC)