Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Please note: this is purely a thought experiment and not intended for any real-world usage!

I came up with a simple function $\mathrm{OPF}$ to map the integers $[0,C)$ (where $C$ is the "ChunkSize") to $512$-bit hashes such that for any $(a, b)$ $$a < b\iff \mathrm{OPF}(a) < \mathrm{OPF}(b)$$ I'm wondering why this is not as secure as existing schemes out there.

The idea is to choose a random point under a certain minimum 512-bit integer $m$ (the MinVal), and map the numbers $[0, C)$ into $[m,M]$, where $M=16^{128}-1$ (the MaxVal) is the largest integer that can fit in 512-bits. For performance reasons, I arbitrarily chose $m = 5 * 10^{150}$. With these values in hand, we calculate the StepSize $s = (M - m) / C$.

The method then relies on 3 procedures, shown below in pseudo-code:

keyGen procedure:
  S = <input random secret>
  while true
    R = random_bytes
    hmac = HMAC(S, R)
    break if hmac < StartVal
  return hmac

encodeNumber procedure:
  K = <output from keyGen>
  N = <number in 0..4095>
  start = K + StepSize * N
  while true
    R = random_bytes
    hmac = HMAC(K, R)
    break if hmac > start and (hmac - start) < StepSize
  return hmac

(Interestingly, this method can give false positive for equality, but only for adjacent integers and only with 0.5 probability.) This can easily be shown from the code below:

equalTo procedure:
  a, b = <encoded numbers> 
  abs(a - b) / StepSize < 1

Obviously, this scheme is not very "elegant", as it relies on "brute-forcing" our way to the correct results. Nevertheless, it seems easy to understand compared to order-preserving encryption schemes out there (keeping in mind that in this scheme, it is not possible to recover the plaintext.) How does it compare in terms of security?

Intuitively, with a secure order preserving function, we should have that

  1. No adversary can predict the image of a point with more than with a pre-determined accuracy
  2. No adversary can guess the distance between the points (more than with a pre-determined accuracy).

Let's assume, in this case, that the adversary is only allowed to observe the output of the function. That is, the adversary cannot ask for the encryption of a chosen plaintext.

share|improve this question
    
Additionally, assume that the input random secret to the keyGen procedure is kept secret (i.e. the adversary is only allowed to observe the output of the function). –  louism Apr 8 at 15:49
    
@RickyDemer Yes - edited accordingly. To the downvoter, care to explain why this is not a good question? I'm asking specifically why this is NOT secure. –  louism Apr 8 at 15:52
    
"the adversary is only allowed to observe the output of the function" Are you saying he can't make queries to it, just see the output of values you choose to 'encrypt'? Or is he allowed to run any of your 3 procedures? –  figlesquidge Apr 8 at 16:01
    
@figlesquidge Thanks! that makes it much clearer and look more professional. Yes, I am implying that the adversary cannot ask for the "encryption" of a chosen plaintext. –  louism Apr 8 at 16:03
1  
Now I see where this scheme fails. Any of you guys care to put up your comment as an answer? –  louism Apr 8 at 16:29

1 Answer 1

up vote 2 down vote accepted

From what I see from the pseudocode, it would appear that $OPF(n)/stepsize−n \in \{0,1\}$, that is, an attacker can compute $OPF(n)/stepsize$, and rederive $n$ with a maximum error of 1.

It would appear that the function fails in its goal of "the adversary must not be able to guess the location of the points"

share|improve this answer
    
Can this attack be mitigated if the step size is derived from the initial secret, such that it falls within a suitably large random range, and kept away from the adversary? –  louism Apr 8 at 16:40
1  
You asked about a order preserving Message Authentication Code, MACs are assumed to be secure even in chosen text environments; a secret step size would easily be reconstructed if the attacker got one or two valid text/MAC pairs. And, even if the attacker didn't have any valid text/MAC pairs, we can estimate the size of a secret stepsize, by examining the MACs he does have; if they are all restricted to a small region, stepsize is likely tiny; if they span almost the entire range, stepsize must be large. –  poncho Apr 8 at 16:44
    
Excellent, thanks for your help. –  louism Apr 8 at 16:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.