2
$\begingroup$

I'm curious about an algorithm that would be good for the following scenario:

  1. 32-bit "plaintext" input, taken from a counter
  2. 32 or 64-bit "ciphertext" output
  3. It should be possible to decrypt the output with the key (and possibly a few other hidden parameters, like an offset and current counter), and return the original 32-bit counter value
  4. A user never observes the input, but may receive any number of outputs, possibly sequential. Even so, they should not be able to know which indices they have.
  5. It should be difficult to guess other outputs that correspond to valid counter values.

My untrained intuition is that since the key and outputs are larger than the input space, it should be fairly easy to have "good" results, at least for the first few outputs. However, it also seems logical that with enough samples the key and indices could be computed easily, but I expect most instances to use less than 100 values.

My questions are:

  1. Are there any existing algorithms that work for this scenario?
  2. How hard would it be to crack? I.e., compute values that decrypt to valid indices.
  3. How much does the possession of more samples affect the efficiency of cracking it?
  4. What's wrong with a naive approach like:

    u64 output = input
    repeat 64x
      output = ((output ^ key) + key) rotate-left 37
    

    Assuming addition wraps around 64bit integer boundaries. It seems as though it would thoroughly mix the random key with a single input, but possessing more than one output could quickly increase the information an attacker possesses, though I wouldn't know how. Obviously it's going to be broken, I'm just trying to learn.

  5. Would using a key-dependent value for the left-rotation, like (((key & 0xFFFE)+1) * 37) be better? How much does it help and why?
  6. What approaches, resources, etc. would you use to both analyze the algorithm, and design a better one?
$\endgroup$
  • $\begingroup$ This is very much an XY problem the way you describe it. A CSPRNG (note the S) doesn't seem to be a good solution for this at all. The key size request is a bit weird, why is it not possible to use larger key sizes? $\endgroup$ – Maarten Bodewes May 8 at 12:06
  • $\begingroup$ I suppose the key size is not essential. I was hoping that 64 bit key would be enough to encrypt a 32 bit value. $\endgroup$ – shader May 9 at 10:33
4
$\begingroup$
  1. Are there any existing algorithms that work for this scenario?

Yes, actually, there are a number of 64 bit block ciphers. The standard wisdom is that they aren't encouraged for general use, because standard block cipher modes tend to start leaking information when you get near the birthday bound (in this case, circa 30 Gbytes); however for your use case, that would not be a concern.

Here are some options:

  • 3DES (aka TDES); this is DES applied three times with three different keys; this has the advantage of being very well studied.

  • Speck which has parameter sets with 64 bit block ciphers. This has the advantage of being the fastest alternative, and was designed by people who know that they're doing, and has done through a surprising amount of cryptanalysis.

  • An FPE cipher (such as FF1, which can handle any arbitrary block size (including 64 bits). This has the advantage in that they allow the option for a tweak (which is a convenient place to place the "other hidden parameters", should you decide that is an advantage). It's slower than the alternatives; with FF1, the security comes from the underlying security of AES, plus the provable security of the Feistel structure.

Now, these take keys longer than 64 bits; the common wisdom is that a 64 bit key is just not long enough.

  1. How hard would it be to crack? I.e., compute values that decrypt to valid indices.

For any of the above, the only practical option an adversary would have would be to randomly guess ciphertexts, and hope to stumble on one that decrypts to a valid index.

  1. How much does the possession of more samples affect the efficiency of cracking it?

For any of the above, having vast quantities of samples will still make the attack infeasible.

  1. What's wrong with a naive approach like...

ARX ciphers (actually, any cipher, but especially ARX) are tricky to get right. ARX ciphers in particular tend not to be great at disrupting differential and linear characteristics (which means any such design would really need to be well studied to make sure that it does).

  1. What approaches, resources, etc. would you use to both analyze the algorithm, and design a better one?

I'd suggest you go with a design which has already been analyzed; I list three above.

$\endgroup$
  • 1
    $\begingroup$ I'd prefer e.g. Blowfish over 3DES if there is a change of relatively small key input. The security of 3DES would be doubtful even if the key was expanded to 128 bits (or rather 112 bits, of course). $\endgroup$ – Maarten Bodewes May 8 at 12:09
  • $\begingroup$ @MaartenBodewes: do you have a cite of anyone showing that 3DES with an unknown key being distinguishable from a random even permutation? $\endgroup$ – poncho May 8 at 14:56
  • 1
    $\begingroup$ No, of course not. However, I'd rather not even have to reason if my encryption has ~80 bit or ~112 bit strength when fed a 128 bit or 192 bit key (I've got no doubt that you would be able to do so, but hey, we're not all poncho). And key size does seem to be an issue in the question. Just throwing away the parity bits in that case is wasteful. $\endgroup$ – Maarten Bodewes May 8 at 15:02
  • 1
    $\begingroup$ Could you elaborate on the statement "Now, these take keys longer than 64 bits; the common wisdom is that a 64 bit key is just not long enough."? Which algorithms require keys of which lengths, and 64bit keys are not long enough for what, precisely? $\endgroup$ – shader May 9 at 10:24
  • 2
    $\begingroup$ @shader: keys of only 64 bits are vulnerable from brute force searches from large (well funded) adversaries. Because it generally easy enough to use somewhat larger keys (e.g. 128 bit) which isn't vulnerable to anyone, we generally opt for the more secure option (even if we're not immediately concerned that the NSA will be interested in attacking us, or if Amazon will decide to devote their entire cloud to us... $\endgroup$ – poncho May 9 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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