Researchers can steal data during homomorphic encryption(news.ncsu.edu)
news.ncsu.edu
Researchers can steal data during homomorphic encryption
https://news.ncsu.edu/2022/03/stealing-homomorphic-encryption-data/
22 comments
This is not a great headline. Side-channel attacks are possible on nearly any cryptographic or security-sensitive procedure. The paper doesn’t show some kind of general vulnerability of homomorphic encryption (or lattice-based encryption), just a specific issue with a specific library. A more accurate headline would be “Exploitable side-channel leakage vulnerability in SEAL up to version 3.6”. The cool contribution of the paper is that it does show how to leverage BKZ for this particular kind of leakage (which, over time, will probably occur eventually in other implementations of lattice-based cryptography).
Generally speaking, highly qualified and deeply developed encryption libraries will have much more resistance to side-channel attacks.
This resistance is something that is added to an implementation over time.
The fact that a library implementing a cutting edge method has not matured this much yet is not really a surprise.
Moreover, the fun parts of homomorphic encryption involve sending it to someone else who can process it. That someone else is probably not going to be able to measure your power draw. Though timing attacks can still be a worry.
The fact that a library implementing a cutting edge method has not matured this much yet is not really a surprise.
Moreover, the fun parts of homomorphic encryption involve sending it to someone else who can process it. That someone else is probably not going to be able to measure your power draw. Though timing attacks can still be a worry.
I agree that this is an issue with this specific library. But well-designed cryptography code is written to be resistant to timing or power side channel attacks.
How does homomorphic encryption actually work? I've read the Wikipedia entry but still don't understand the mechanics.
There are some great resources here: https://fhe.org/resources
The fhe.org discord community is also of great help for all things FHE.
Thank you!
It's a side-channel attack on the encryption, not a break of homomorphic encryption:
“We weren’t able to crack homomorphic encryption using mathematical tools,” says Aydin Aysu, senior author of a paper on the work and an assistant professor of computer engineering at North Carolina State University. “Instead, we used side-channel attacks. Basically, by monitoring power consumption in a device that is encoding data for homomorphic encryption, we are able to read the data as it is being encrypted. This demonstrates that even next generation encryption technologies need protection against side-channel attacks.”
“We weren’t able to crack homomorphic encryption using mathematical tools,” says Aydin Aysu, senior author of a paper on the work and an assistant professor of computer engineering at North Carolina State University. “Instead, we used side-channel attacks. Basically, by monitoring power consumption in a device that is encoding data for homomorphic encryption, we are able to read the data as it is being encrypted. This demonstrates that even next generation encryption technologies need protection against side-channel attacks.”
In which case you could also say the same thing about RSA encryption, or really anything. It’s a pretty silly argument to make as rowhammer im sure could also “break” homomorphic encryption.
Homomorphic encryption is really about the utility when it leaves the device, not at the encryption stage.
Homomorphic encryption is really about the utility when it leaves the device, not at the encryption stage.
>It’s a pretty silly argument to make as rowhammer im sure could also “break” homomorphic encryption.
There's no reason rowhammer should be able to break homomorphic encryption. Homomorphic encryption means at no point is the data on the machine unencrypted, so there is nothing to leak from RAM.
>Homomorphic encryption is really about the utility when it leaves the device, not at the encryption stage.
???
This make no sense. Homomorphic encryption is used for a device to do computations on encrypted data without the device knowing what the encrypted data is.
For example, computing the square of an integer that is homorphically encrypted would not tell the device doing the computation what the original number is or what the square is. Encrypted data comes in, stays encrypted at all times, an algorithm does some operations on the encrypted data, and encrypted data is then sent out.
This paper and attack are not about the encryption stage. The attack is on the operating on homomorphic data.
There's no reason rowhammer should be able to break homomorphic encryption. Homomorphic encryption means at no point is the data on the machine unencrypted, so there is nothing to leak from RAM.
>Homomorphic encryption is really about the utility when it leaves the device, not at the encryption stage.
???
This make no sense. Homomorphic encryption is used for a device to do computations on encrypted data without the device knowing what the encrypted data is.
For example, computing the square of an integer that is homorphically encrypted would not tell the device doing the computation what the original number is or what the square is. Encrypted data comes in, stays encrypted at all times, an algorithm does some operations on the encrypted data, and encrypted data is then sent out.
This paper and attack are not about the encryption stage. The attack is on the operating on homomorphic data.
When talking about encryption techniques, I think we usually assume that the machine performing the encryption isn't compromised. I.e., keeping a machine uncompromised is a separate area of study / endeavor.
What NC State achieved is cool, but it seems a bit like saying "Homomorphic encryption is broken when you can blackmail the sysadmin."
What NC State achieved is cool, but it seems a bit like saying "Homomorphic encryption is broken when you can blackmail the sysadmin."
That’s part of the rationale for homomorphic encryption, even if the device performing the operations is completely compromised it never has access to the unencrypted data, so given a theoretical perfect HE system your data would still be safe.
I’m off to read this paper S I don’t understand how they are using a side channel to extract information that the operating device theoretically shouldn’t have. If there’s a measurable power usage difference over the operations that implies that the encrypted bits do leak information about what is encrypted.
I’m off to read this paper S I don’t understand how they are using a side channel to extract information that the operating device theoretically shouldn’t have. If there’s a measurable power usage difference over the operations that implies that the encrypted bits do leak information about what is encrypted.
In a homomorphic scheme, you have a machine A (trusted), which encrypts some data and sends it to machine B (untrusted) and B then does operations on the data and returns the results to A, which decrypts.
This attack is on machine A, not machine B. The "leak" happens as the data is being encrypted. They're sidechanneling a machine that has the plaintext on it.
This attack is on machine A, not machine B. The "leak" happens as the data is being encrypted. They're sidechanneling a machine that has the plaintext on it.
Ah, I was super confused (as I said I hadn’t yet read the paper, I was hoping for TLDR at the time)
[deleted]
FTA:
>Our proposed attack targets the Gaussian sampling in the SEAL’s encryption phase
It's literally about stealing the data from the encryptor, which is usually a trusted machine.
>Our proposed attack targets the Gaussian sampling in the SEAL’s encryption phase
It's literally about stealing the data from the encryptor, which is usually a trusted machine.
Exactly. Power consumption side channel attacks do nothing for devices operating on already encrypted data, because if it did, it would mean homomorphic encryption is fundamentally broken. The side channel attack is on the original encryptor.
As an aside it's worth noting that RSA itself is partially-homomorphic (ciphertext multiplications are preserved in the decrypted plaintext).
The idea of 'homomorphic encryption' was even introduced by another Rivest and Adleman paper, almost immediately after the famous 1977 RSA algorithm ("On Data Banks and Privacy Homomorphisms" by Rivest, Adleman, and Dertouzos 1978).
The idea of 'homomorphic encryption' was even introduced by another Rivest and Adleman paper, almost immediately after the famous 1977 RSA algorithm ("On Data Banks and Privacy Homomorphisms" by Rivest, Adleman, and Dertouzos 1978).
No, not "pretty much anything". Proper encryption code needs to be written so that the timing and power consumption does not depend on the data, to avoid these kinds of side channel attack. That usually means no conditional branches, so the same processor operations occur regardless of the ciphertext or the key.
Whilst that is true, power side channel attacks are an interesting case.
If they become relevant, then your attacker is really quite close to the device. In most scenarios, once the attacker is that close you are probably fucked anyway. There are exceptions of-course. Using in-memory encryption, ingress detection, etc you might be able to remain safe in these cases. Moreover an attacker might be able to do power-analysis without leaving a trace. Whereas pulling out the RAM-sticks after freezing them leaves more of a mark.
However, few of the scenarios involving good reason to use homomorphic encryption really stand up to an attacker having physical access to the encrypting device. Most of these scenarios are about secure shared computation. Where the threat model revolves around 'what if my computational partner is evil', not 'what if Ethan Hunt breaks in'. Generally, if someone has access to the machine, they will have access to the raw data anyway.
If they become relevant, then your attacker is really quite close to the device. In most scenarios, once the attacker is that close you are probably fucked anyway. There are exceptions of-course. Using in-memory encryption, ingress detection, etc you might be able to remain safe in these cases. Moreover an attacker might be able to do power-analysis without leaving a trace. Whereas pulling out the RAM-sticks after freezing them leaves more of a mark.
However, few of the scenarios involving good reason to use homomorphic encryption really stand up to an attacker having physical access to the encrypting device. Most of these scenarios are about secure shared computation. Where the threat model revolves around 'what if my computational partner is evil', not 'what if Ethan Hunt breaks in'. Generally, if someone has access to the machine, they will have access to the raw data anyway.
It feels plausible to me that homomorphic encryption would be especially vulnerable to side-channel attacks because its schemes are so computation-heavy. I don't have a clear mental model for this, but it feels like there would be a lot of opportunities for attackers to detect data dependencies at the beginning of the process (if they have access to observe a relevant channel).
The encryption is data dependent. The homomorphic computation itself cannot be data dependent. Homomorphic encryption says that even if you see all the intermediate encrypted values, you will not know what the encrypted input or output value is. So side-channels do not matter for the computationally heavy evaluation part. In this paper they attacked the encryption part.
Sorry, I meant the initial preparation of the encrypted data. I believe that this step is also typically rather computationally heavy, although maybe less so than the later computation over the encrypted data.