1
$\begingroup$

For a personal project I'm currently tinkering on, I'm looking for a function which has the following properties:

  1. For any number X in the range 0..MAX, there is a 1:1 random mapping with another number Y in that range.
  2. As long as the key/algorithm remains the same, that mapping should not change. For every X, there is one and only one Y, and for every Y there is one and only one X.
  3. Small changes in X should generate massive changes in Y.
  4. Calculating X -> Y should be computationally simple, even for extraordinarily large values of MAX.
  5. Calculating Y -> X should be (effectively) impossible, as should guessing the key.

In non-numerical terms: I'll be encrypting chunks of data (think 4096 bits, maybe more), and expecting an equally-sized unique output chunk for every possible input chunk. Every chunk will always be the same size.

Arbitrary values of X will be converted to Y quite often. End users will be able to choose their value of X at will and see its corresponding Y, across a vast numerical range. Cryptography is not my strong suit, but from my reading this translates as "the algorithm would need to be resistant to chosen-plaintext attacks". The users should never be able to calculate Y -> X, as that would spoil all the fun (to say the least).

A simple visual, for MAX=8:

X Y
0 7
1 6
2 5
3 4
4 1
5 0
6 3
7 2

So it should be criminally easy to start with X=2 and calculate Y=5, but it should be essentially impossible to guess X=6 from Y=3 without brute forcing.

There were several promising answers here, but it was unclear how secure any of them actually would be given the conditions: https://stackoverflow.com/questions/16398843/unique-int-to-int-hash

My strong preference would be to use an existing and battle-tested encryption algorithm for this, and preferably one which exists in OpenSSL or some other library I can just plug into from Rust, but I've had trouble knowing the right vocabulary to search for what I want (I'm far from new to programming, but very very green in cryptography). It seems from my reading that block ciphers are what I'm looking for, but I have been thrown off by all the talk of IVs and counters and am unsure if CBC/CTR/etc actually work for what I'm trying to do (or if what I'm trying to do is even possible).

Any pointers in the right direction would be greatly appreciated!

$\endgroup$
6
  • 1
    $\begingroup$ Should the key-holder be allowed to compute the $Y\to X$ map? Do you need the map to be a permutation or is it sufficient that it's practically impossible to find collisions (i.e. that nobody can exhibit an example violating injectivity)? Is determinsm a feature here, i.e. do you need and want the same $X$ to always be mapped to the same $Y$ under a given key (in normal encryption this is an anti-feature)? Do you need a full-width function here, i.e. that a change in bit 0 in $X$ has a ~50% chance for all bits in $Y$ to be flipped? $\endgroup$ – SEJPM Mar 28 at 11:47
  • $\begingroup$ @SEJPM 1) It's fine if the key-holder can compute Y -> X, but it's not necessary and it's perfectly fine (and maybe more fun) if they can't. 2) The map should be a permutation if at all possible. The primary feature is that all possible values of Y are guaranteed to exist somewhere in the space. If it's necessary, X could be a larger space and there could be duplicates in Y, but it wouldn't be nearly as thematically appropriate (even if the users could search until the heat death of the universe and never find a duplicate, thematically it's preferable if there's only one of each Y). $\endgroup$ – MrAwesome Mar 28 at 12:46
  • $\begingroup$ 3) Determinism for a particular key is definitely a feature. Never thought of how that's normally an anti-feature in encryption, but that makes sense. Within a running instance of this program using a particular key, a given X should always give the same Y. That doesn't have to hold across different instances, but it would be a very nice touch. $\endgroup$ – MrAwesome Mar 28 at 12:47
  • $\begingroup$ 4) Full-width sounds like what I'm looking for, or at least something similar - there should be no predictable change in output among numerically similar values of X, so that someone can't go searching for particular patterns in the values of Y. The effective randomness among values of Y (but guarantee of all values being present) is a primary goal. $\endgroup$ – MrAwesome Mar 28 at 12:48
  • 1
    $\begingroup$ One final clarifying question: What kind of guarantee can you give on the structure of MAX and thus the set size of allowed values $X$? Is the size guaranteed to be a power of 2? A multiple of $2^{128}$? ...? $\endgroup$ – SEJPM Mar 28 at 14:04
1
$\begingroup$

There are three major options available to you, depending on the available preferences and guarantees, ordered in descending order of generality:

  • Format-Preserving Encryption is a class of encryption schemes that can accept arbitrary input spaces and then produce ciphertext from that input space as output. A classical example would be encryption of credit card numbers to encrypted ones that are still accepted by the database solution validating their format.
  • Wide Block Cipher Modes, e.g. EME* take a bit string of arbitrary length and then compute a keyed pseudo-random permutation on them, their original intended use was disk encryption where you can't store additional authentication data but want to maximize your chances of detecting modification by randomizing the data sector if the ciphertext sector is changed.
  • Traditional Symmetric Encryption, e.g. CBC mode with a fixed nonce / IV. Note that these suffer from the isuse that changes at bit position $n$ affect at most a constant amount of bits in front of $n$ and at most all bits following $n$ which seems to not be the avalanche effect you're looking for.

If you're wondering, the recommended baseline block cipher for the above constructions is AES.

$\endgroup$
2
  • $\begingroup$ None of these suggestions address requirement 5; that the permutation be one-way. $\endgroup$ – poncho Mar 30 at 21:18
  • $\begingroup$ @poncho I clarified that in the comments under the question (I probably should have edited them into the main question whoopsie), to quote: "It's fine if the key-holder can compute Y -> X, but it's not necessary and it's perfectly fine (and maybe more fun) if they can't." $\endgroup$ – SEJPM Mar 30 at 21:20

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.