Simson Garfinkel on Spooky Cryptographic Action at a Distance

Excellent read. One example:

Consider the case of basic public key cryptography, in which a person’s public and private key are created together in a single operation. These two keys are entangled, not with quantum physics, but with math.

When I create a virtual machine server in the Amazon cloud, I am prompted for an RSA public key that will be used to control access to the machine. Typically, I create the public and private keypair on my laptop and upload the public key to Amazon, which bakes my public key into the server’s administrator account. My laptop and that remove server are thus entangled, in that the only way to log into the server is using the key on my laptop. And because that administrator account can do anything to that server­—read the sensitivity data, hack the web server to install malware on people who visit its web pages, or anything else I might care to do­—the private key on my laptop represents a security risk for that server.

Here’s why it’s impossible to evaluate a server and know if it is secure: as long that private key exists on my laptop, that server has a vulnerability. But if I delete that private key, the vulnerability goes away. By deleting the data, I have removed a security risk from the server and its security has increased. This is true entanglement! And it is spooky: not a single bit has changed on the server, yet it is more secure.

Read it all.

Tags: ,

Posted on October 30, 2024 at 10:48 AM • 22 Comments

Comments

Royce Williams • October 30, 2024 10:56 AM

Typo: it’s “Simson” (no ‘p’). Maybe this was autocorrect — especially considering it “corrected” me!

(This comment can be deleted once it’s corrected)

Richard H Schwartz • October 30, 2024 11:08 AM

It is more secure, but not necessarily secure unless the private key from your laptop is also entangled with all of its backup copies such that they are all deleted simultaneously.

tfb • October 30, 2024 12:34 PM

No, this is not entanglement. And I really, really wish people would actually make the effort to learn what entanglement is before spouting off about it.

Consider the following case: there is a gun and a knife. A bad person has one, I have the other. The bad person is going to do bad things to some other people. You are the police, and the way you deal with a gun threat is very different than the way you deal with a knife threat (maybe it is not in real life, but for the sake of the story let it be so). In particular the method you will use against a gun threat is completely ineffective against a knife threat & vice versa, while each method is completely effective against the threat is was designed for.

You do not know who has which weapon. So your chance of stopping the bad person is 50%. Or, you can persuade me to tell you which weapon I have. Now your chance of stopping the bad person is 100%.

Does that mean the knife is entangled with the gun? That there was spooky action at a distance of which Einstein would not approve? I mean, do you think Einstein was an idiot? Or do you think that, perhaps, spooky action at a distance is a different thing?

Enough already.

Clive Robinson • October 30, 2024 1:26 PM

Hmm,

“it’s impossible to evaluate a server and know if it is secure: as long that private key exists on my laptop, that server has a vulnerability.”

Not actually true.

If either the private key or a way to reconstruct it, exists then the server is not secure.

The laptop could have had the private key stolen from it or the RNG used to generate the primes could be deficient or backdoored in some way.

Which is why this statement is not actually true either,

“But if I delete that private key, the vulnerability goes away.”

But it’s a bit more subtle than just a Private key being available as data via Communication, Storage, or Processing.

In essence it’s to do with the unproven status of “One Way Functions”(OWFs) with “Back doors” or secret “Trap doors” that enable a “secret holder” to reverse the OWF.

There is an old saying about the fact that only three numbers make sense from a philosophical perspective,

1, Zero : There is none of something.
2, One : Something is unique.
3, Infinity : There is an unknown number of something.

For a true OWF there must be “Zero” back doors.

For a OWF with a Trap Door you hope there is only “One”

But there is no actual proof that OWFs with “Trap Doors” only have one trap door.

Impossibly Stupid • October 30, 2024 1:54 PM

I would argue that this approach is more “security by obscurity” than any useful analogy to quantum mechanics. Whatever vulnerability that remote access presents does not go away when something external to the system changes.

It’s easier to see the flaw in thinking if you consider passwords rather than a complex key pair exchange. If I have a password like ‘sexy123’, anyone who can either guess it or hack my local password database can use it to access the remote system. Deleting it from my local system and acting like the remote system is now secure is extraordinarily short sighted.

as long that private key exists on my laptop, that server has a vulnerability

It is more correct to say that the server shares the laptop’s vulnerabilities any time after that access was set up. Along with all other vulnerabilities that are introduced in the process (e.g., backups, etc.). Nothing “spooky” is happening, and systems will get exploited if they are not properly maintained.

Larry • October 30, 2024 3:46 PM

It isn’t spooky action at a distance until the threat goes away faster than the speed of light. If you delete the key on the server. The key still looks like it is there until that information is available back at the server (and at the abode of the threat actor), until then, the places that have stolen your key from the laptop may still have retrieved the stolen key before you deleted it.

Still not a spooky action at a distance quantum effect. Still quick, but causality and the speed of light are preserved.

Regards,

Larry

dusko pavlovic • October 30, 2024 8:25 PM

“As long that private key exists on my laptop, that server has a vulnerability. But if I delete that private key, the vulnerability goes away.”
The tacit assumption is that it is easier for an attacker to find the private key on the author’s laptop on the network than to factor numbers and break the cipher. The two kinds of hardness are obviously incomparable, but ignoring one and not the other one seems a little tenuous. Also, the claim that the “two keys are entangled, not with quantum physics, but with math”. Suppose that I create a symmetric key, use it to scramble something, and store a sole copy on my laptop. By the same reasoning, the two copies are entangled, and deleting my copy would cause the spooky action of transforming a trapdoor function into a one-way function. With no math involved. The spooky action arises from the assumption that finding a copy stored somewhere on the network is tractable and that recovering deleted data from memory is not.
Genuinely entangled quantum states collapse to the same classical state when one is measured. When reduced to metaphors, math concepts often also collapse.

Paul Sagi • October 30, 2024 9:40 PM

Bruce,
Regarding
https://www.linkedin.com/pulse/spooky-data-distance-simson-garfinkel-nrt9e/
my late father was a university professor demographer/social scientist/statistician/mathematician and used the method described.
He designed anonymized surveys and his design and analysis took participant bias into consideration.

The risk to the cloud server described in the article and your blog I perceive as more minor than the risk to you, the cloud user. Couldn’t malware in the cloud server grab the private key from your browser?
Regarding how much to trust a browser, I say ‘not much’.
Security is relational, or, to make an analogy to Donald J. Trump Sr., transactional.
https://contrachrome.com/ContraChrome_en.pdf

ResearcherZero • October 31, 2024 2:50 AM

@Paul Sagi

There are browser based attacks, but they target cookies using info stealers and other tools (such as backdoors) that assist in attacking the browser. Such attacks usually are targeting cloud storage services, RDP and VPN credentials, rather than targeting SSH.

If an attacker manages to install a backdoor on a system they then could target /.ssh/config, .bash_history, /.ssh/known_hosts, or other locations to look for information.

They could also install a keylogger or attempt to brute force SSH, it has happened. But usually these attacks are against systems that are not up to date and not maintained.
It all depends on how well secured someone’s system is, and if they clean up history.

If you are a government department, larger company or orginisation, the risk increases.

And 0-days are more typically used by APTs or experienced criminal groups looking for juicy targets. But a very determined adversary could theoretically exploit a vulnerability. If the system in question is kept up to date though, it is a lot less likely to take place.

Cyclist • October 31, 2024 4:42 AM

I assume the article was a lighthearted thought experiment to be considered in isolation from any real concerns or strategies about security.

Well, here’s another: I put a padlock on my bicycle and the (unique) key in my pocket. As long as the key exists there is a security risk to the bicycle. Later, I go on holiday and, Frodo-like, lose the key in a volcano. As if by magic, the security risk to the bicycle (on the other side of the planet) instantly goes away without anyone making changes to the bicycle or the padlock.

Spooky action at a distance, with neither quantum physics nor mathematics playing a role.

However it does raise questions about the meaning of the word “risk”.

Gert-Jan • October 31, 2024 8:13 AM

Isn’t the term “vulnerability” misused here?

For me, a vulnerability is an aspect that does not work as intended and/or has flaws in its design.

For example, if there’s an easy way for an attacker to create the private key (without stealing it from the owner), for example because of flaws in the one way function, or the use of a quantum computer, then I would consider that a vulnerability.

Getting access to a cloud server based on a public/private key pair is a documented feature of the system; it is intended fucntionality. The protocols that are used, and the way they are used (the processes) might have vulnerabilities. The way the user stores the private key might be vulnerable to leaking. But claiming that the system is vulnerable if you use its standard functionality is just bad for any serious discussion.

AquaFreak • October 31, 2024 9:25 AM

Here’s why it’s impossible to evaluate a server and know if it is secure: as long that private key exists on my laptop, that server has a vulnerability.

Why does that make evaluating the security of the server impossible? I can easily check authorized_keys to see the vulnerability.

Of course, I do not know where the corresponding private key is. But I can very well see the hole and I can secure my server by simply deleting the key from authorized_keys (which also protects me from copies of the private key and cryptographic attacks).

pattimichelle • October 31, 2024 10:35 AM

Ya, I’ve been aware that this represents true “entanglement” for a while. In fact, the knowledge (data) of what was encrypted, assuming perfect encryption like OTP, disappears from the universe.

Me • October 31, 2024 5:09 PM

Wow, I had to re-read that after I was perplexed what a singing group from the 70s had to do with computer security…

Missing • October 31, 2024 7:58 PM

I must be missing something here?

The anonymity scenarios make sense to me, but the private key deletion doesn’t.

If you delete the private key, there is no longer any way to log into the server to apply security patches. Thus someone may hack the web server to install malware on people who visit its web pages, and your only recourse is to have the cloud provider shut down your virtual machine server after the fact… If you can still verify that you are the rightful owner

Clive Robinson • October 31, 2024 9:17 PM

A thought,

Is it actually “hidden variable rather than “spooky action”?

We know that the major use of PubKey involves generating two random primes.

Mix them together one way and you get the “Public Key” mix them together another way and you get the “Private Key”.

But as with mixing paint of two colours to get a third colour, you should not be easily able to unmix the third colour backwards to get the two original colours. Thus remixing to get the other –fourth– colour should likewise not be easy.

But it can be seen that even though only the third and fourth colour exist –of which you only know one–,

“They both shared the first and second colours.”

That are now “hidden” from ordinary viewing.

JG5 • November 4, 2024 7:52 PM

@Clive – “That are now “hidden” from ordinary viewing.”

I have attempted to post several times in recent weeks, only to have my efforts disappear into the memory hole. The most recent was this gem, which is spot on your point. You can think of those as covert channels.

Cryptanalysis and Protocol Failures
https://dl.acm.org/doi/pdf/10.1145/188280.188298

No results found for “Cryptanalysis and Protocol Failures” site:www.schneier.com

I thought this a good lodging place for however long the rust amd magnetization persist beyond our time:

Gus Simmons’s Memoir – Schneier on Security
https://www.schneier.com/blog/archives2022/03/gus-simmonss-memoir.html

Jelo 117 • November 5, 2024 10:41 AM

“Entanglement” used this way would make any related things entangled, alternatively is a synonym for “relation”. If A is related to B and B is destroyed, A is no longer really related to B. It may or may not be possible to provide B anew and restore the real relation. A itself though never changes in any of its intrinsic characteristics. When related A and B are both in existence they may provide potential for other effects. E.g., a piece of metal and a piece of wood suitably related through quantity provide the potential for a chisel and chiseling.

Public key A and private key B are related. It seems not feasible to generate B from only A but it may turn out there is a good way to do this.

jmp • November 15, 2024 9:17 AM

This is a solved problem with Yubikeys. I’ve implemented this at my current employer.

Generating an RSA keypair on a Yubikey removes the private key from the internet-connected laptop. Yubikey attestation allows me to enforce this company wide, e.g. “show me your Yubikey attestation certification to prove to me this is a Yubikey keypair before I grant you AWS access.”

The residual risk is the known unknown of remote key extraction from a Yubikey, but there is no known research that shows this is possible. So while we could have a philosophical conversation about the remaining “spookiness”, from a practical risk management perspective this is about as good as it gets today.

Leave a comment

Blog moderation policy

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.