3 ms·

Impressive work. Especially for producing an implementation. But be very very careful about ever using it ( and really any cryptography that does more than sta

Impressive work. Especially for producing an implementation. But be very very careful about ever using it ( and really any cryptography that does more than standard encryption/ signing) in practice without understanding the security it provides. Revealing element order can in fact reveal most of your data set in some cases. There are cases where leaking order is safe and very useful and there are cases where it is not safe despite there being nothing cryptographically "wrong" with the scheme. (Edited) To give an example: although not the exact same primitive,some Order Preserving Encryption schemes leak square root(n) bits where n is the bit length of your plaintext[0]. For social security numbers, this would mean you loose about 5 bits of entropy and there are only 10 or 11 bits to start with in many cases[1]. And as they say, attacks only get better and people are actively working on attacks using order leakage[2]. Just because something is provably secure doesn't mean it is the right kind of secure for your application. Crypto is not pixie dust. You actually need to understand the exact guarantees something provides. [0]http://www.cc.gatech.edu/~aboldyre/papers/operev.pdf http://www.cc.gatech.edu/~aboldyre/papers/operev.pdf [1]http://www.pnas.org/content/106/27/10975.full.pdf http://www.pnas.org/content/106/27/10975.full.pdf [2]https://twitter.com/hackermath/status/741054948612308992 https://twitter.com/hackermath/status/741054948612308992

schoen 10y ago
> Revealing element order can in fact reveal most of your data set in some cases. A contrived example to demonstrate this is if you published some kind of database about behavior observed from IP addresses, but using ORE-encrypted IP addresses instead of plaintext ones. If the database explicitly contains all 2³² IPv4 addresses, someone can then perform a series of comparisons to sort the entire database (which is an explicit goal of ORE), which then reveals the plaintext values because they're exactly equal to the positions of the entries in the sorted list! A subtler case could arise if the database is complete for some range of IP addresses and an attacker happens to know the plaintext values at the bottom and top of that range. Then the attacker can learn the plaintext values of everyone else in the range. An even subtler case could arise if the attacker simply knows a bunch of specific plaintext values. In that case, the attacker can learn constraints on the numeric values of other database entries, which could mean, for example, learning the first 1-2 bytes of a particular IP address, which could confirm or disconfirm hypotheses about a user's ISP or geographic location. Edit: I'd like to see some of the more subtle attack ideas that the people you linked to are developing!
- ianmiers 10y ago
  In fact, there's a long history of people trying to publish anonymized IP logs in ways that preserve the IP address structure (i.e. anonymized ip's from the same subnet end up in the same anonymous subnet). It turns out that leaking that structure frequently ends up identifying the IP addresses. The bottom line is beware of academics baring leakage functions. Their work often has considerable merit, but one must be very careful about how it's used in practice.
- cvwright 10y ago
  That's me above in Ian's [2]. We're hoping to have something ready to share by the end of the month. I'll post a Show HN when it's available. In the mean time, here's a paper from some folks in Norway that shows attacks against two prefix-preserving IP address anonymization schemes: http://link.springer.com/chapter/10.1007/11767831_12 http://link.springer.com/chapter/10.1007/11767831_12
  - ianmiers 10y ago
    Oh right, it was either you or your advisor who told me the IP address story.
swordswinger12 10y ago
Only the BCLO scheme (http://www.cc.gatech.edu/~aboldyre/papers/bclo.pdf http://www.cc.gatech.edu/~aboldyre/papers/bclo.pdf) has that particular leakage, which is (roughly speaking) the first half of the plaintext bits, not sqrt(n) bits.

schoen 10y ago

> Revealing element order can in fact reveal most of your data set in some cases. A contrived example to demonstrate this is if you published some kind of database about behavior observed from IP addresses, but using ORE-encrypted IP addresses instead of plaintext ones. If the database explicitly contains all 2³² IPv4 addresses, someone can then perform a series of comparisons to sort the entire database (which is an explicit goal of ORE), which then reveals the plaintext values because they're exactly equal to the positions of the entries in the sorted list! A subtler case could arise if the database is complete for some range of IP addresses and an attacker happens to know the plaintext values at the bottom and top of that range. Then the attacker can learn the plaintext values of everyone else in the range. An even subtler case could arise if the attacker simply knows a bunch of specific plaintext values. In that case, the attacker can learn constraints on the numeric values of other database entries, which could mean, for example, learning the first 1-2 bytes of a particular IP address, which could confirm or disconfirm hypotheses about a user's ISP or geographic location. Edit: I'd like to see some of the more subtle attack ideas that the people you linked to are developing!

ianmiers 10y ago
In fact, there's a long history of people trying to publish anonymized IP logs in ways that preserve the IP address structure (i.e. anonymized ip's from the same subnet end up in the same anonymous subnet). It turns out that leaking that structure frequently ends up identifying the IP addresses. The bottom line is beware of academics baring leakage functions. Their work often has considerable merit, but one must be very careful about how it's used in practice.
cvwright 10y ago
That's me above in Ian's [2]. We're hoping to have something ready to share by the end of the month. I'll post a Show HN when it's available. In the mean time, here's a paper from some folks in Norway that shows attacks against two prefix-preserving IP address anonymization schemes: http://link.springer.com/chapter/10.1007/11767831_12 http://link.springer.com/chapter/10.1007/11767831_12
- ianmiers 10y ago
  Oh right, it was either you or your advisor who told me the IP address story.

swordswinger12 10y ago

Only the BCLO scheme (http://www.cc.gatech.edu/~aboldyre/papers/bclo.pdf http://www.cc.gatech.edu/~aboldyre/papers/bclo.pdf) has that particular leakage, which is (roughly speaking) the first half of the plaintext bits, not sqrt(n) bits.