If you can encrypt or generate queries, then you can decrypt any order preserving encryption scheme in log_2(n) probes, regardless of the underlying data distribution.
n is the number of possible values. If you want to decrypt all caps strings, then you can decrypt the first character with log_2(26) queries, then the second with another log_2(26) queries, and so on.
If you can only observe the query stream or the disk reads, then you end up paying a constant factor more than that, but not a very large one.
Even if the attacker only has access to data at rest, if you have multiple OPE columns in a table, or if the database has foreign key relationships that link OPE data, you end up leaking all sorts of information about the underlying database.
It's hard to say anything polite about these schemes or the vendors that push them.
As with any secure system, it depends on your threat model but the early versions of OPE are woefully insecure. The attack you're describing sounds like the one on the Boldyreva scheme from 2009. While all OPE schemes leak some information, the more recent schemes are much more secure and often quite appropriate for many use cases (arguably at least).
ORE has different security properties, particularly Lewi-Wu 2016. There are also now hybrid schemes like the EncodeORE scheme of 2020 which is both more efficient and more secure than previous OPE and practical ORE schemes.
Note that this paper is about the CLWW scheme of 2015. The Lewi-Wu Scheme of 2016 (Block Order Revealing Encryption) has entirely different security properties. Storage of the right ciphertexts (as they describe in the paper) is semantically secure.
n is the number of possible values. If you want to decrypt all caps strings, then you can decrypt the first character with log_2(26) queries, then the second with another log_2(26) queries, and so on.
If you can only observe the query stream or the disk reads, then you end up paying a constant factor more than that, but not a very large one.
Even if the attacker only has access to data at rest, if you have multiple OPE columns in a table, or if the database has foreign key relationships that link OPE data, you end up leaking all sorts of information about the underlying database.
It's hard to say anything polite about these schemes or the vendors that push them.