4 ms·
1) computing arbitrary polynomials is all you can do to data. Everything you do is somehow adding two numbers together, subtracting, multiplying, or dividing.
by Groxx 15y ago
1) computing arbitrary polynomials is all you can do to data. Everything you do is somehow adding two numbers together, subtracting, multiplying, or dividing. At the very very worst, this is all your computer is doing - you could implement a computer on top of the encryption scheme. It would be horrendously wasteful, but it would work, and that's what really matters in all this. Improvements will come, or computers will speed up.
2) >The result I get is still encrypted, but since there are only 128 possible values for an ascii character, I can encrypt each of these values and compare the result to the result of my computation.
And that's why keys of one byte are a bad idea. Bad in symmetric, bad in asymmetric, just plain bad. This same attack is true for any block-level encryption - it doesn't make them insecure. And homomorphic encryption needs, if I remember right, enormous relatively-prime numbers. Like, gigabytes worth. We're not talking small keys here.
3) The most dangerous part about using homomorphic encryption is that, necessarily, how you operate on the data reveals something about the data (and the search). Say you're Google, and you repeatedly see sequential access on blocks 123-345, 346-356, and 357-789. You can make a pretty strong claim that those are separate blocks of data that have been encrypted. The more you do to your encrypted data, the more someone else gets a peek at what you're doing. A very obfuscated peek, but a peek nonetheless. Add enough peeks, and you can get quite a bit of information. Or try something like a search through a binary search tree - the early locations you access will be touched by many processes, in a linear fashion, always with branching behavior. What kind of data does it look like?
But there are ways to combat this as well. If you're going to access 123-345, grab pieces out of it and others at random, overlap the edges, and split it across multiple operations. On the receiving edge, just toss out everything extra. All that can be seen is that you accessed a lot of data, but they don't know which ones were important (unless you were truly random, and then statistically the edges of that block can be seen).
- andrewcooke 15y agoam i being dumb? what does the size of the key have to do with knowing that there's only a small range of possible values (and then encoding each and checking for equality)? isn't this more likely addressed by random ivs (or whatever the equivalent is)?
- simcop2387 15y agoA larger key size will mean that you'd have to look at more than just one byte to begin saying anything about what the data could be. This means that even though there are only 128 (normally far far lower for a password) values that each byte COULD be, there would be something like 2keysize-7 possible representations of each of the possible values. This means that an attack like the one described in the blog article would be significantly more difficult.
- andrewcooke 15y agoi don't think so. the attack is extracting a single byte. so without any random iv you will get one of 256 values spread across whatever the block size is. that size doesn't matter - you still have just 256 values to test for. your argument only applies if the rest of the data are appended to the plaintext. [disclaimer: i'm no cryptographer, just using simple logic here]
- tedunangst 15y agoIt's not the key that's one byte, it's the plaintext. But it makes no difference. The author/attacker doesn't have the key. He can encrypt all the letters he likes, but getting identical ciphertexts doesn't mean anything unless he used the same key.
- emily37 15y agoWhy doesn't the attacker have the key? It's a public key cryptosystem, so we should assume the attacker has the public key. The attacker can encrypt all 128 ascii characters under the public key that was used to encrypt the whole string. The fact that the author was missing (which was pointed out later) was that two encryptions of the same byte under the same key will produce different ciphertexts.
- tedunangst 15y agoI think I may have failed to understand something important. :(
- bdhe 15y agoAnd that's why keys of one byte are a bad idea. Bad in symmetric, bad in asymmetric, just plain bad. This same attack is true for any block-level encryption - it doesn't make them insecure. And homomorphic encryption needs, if I remember right, enormous relatively-prime numbers. Like, gigabytes worth. We're not talking small keys here. This is incorrect. The key size has nothing to do with extracting one byte. As mentioned later in the thread, if the encryption is not randomized (and Craig's scheme is, like all "semantically-secure" encryption schemes) then the ciphertext leaks no information about the plaintext even if it were only one bit. However, if the encryption is not randomized then trivially, your encryption is only as secure as your plaintext space. Secondly, you say homomorphic encryption needs enormous relatively-prime numbers. This is not correct. Craig's sceme uses lattice-based cryptography. The keys are long because we don't have efficient reductions to hard problems and the best algorithms to solve lattice problems currently known are better than brute force (so we need to increase parameters to make the best algorithms known today take at least 2^80 time, if not more).
- Groxx 15y agoI'll have to look into lattice-based crypto some time, I know essentially nothing about how it works. Thanks for the corrections!
- tzs 15y ago> computing arbitrary polynomials is all you can do to data. Everything you do is somehow adding two numbers together, subtracting, multiplying, or dividing. What about conditional branching?
- archgoon 15y agoDon't think in terms of assembly instructions, think in terms of logic gates. A nand gate can be represented as a polynomial (over a binary ring) as result = (x+y)*(1-xy) = x+y-xy
- Groxx 15y agoApologies all, replace key size with block size in the 2nd point. Not sure why I was thinking this is key related.