1
$\begingroup$

I need an algorithm that can take an integer, an arbitrary range, a key of 16/24/32 bytes, and an initialization vector of 16 bytes(ideally), and return an integer in the same range.
My latest attempt at this repeatedly encrypts an integer with AES_OFB until it is in the requested range. I'm using a stream cipher so that the ciphertext can be truncated without ruining the whole thing. The issue is that the decryption process sometimes halts too early.
Pseudocode:

data = 0x7234
range = 0x1000 to 0xa000 inclusive
data = aes_ofb_encrypt(data) // keystream "0x8d7c", data == 0xff48
0xff48 is not in the range, try again
data = aes_ofb_encrypt(data) // keystream "0xe5b7", data == 0x1aff
0x1aff is in the range
return data // 0x1aff

decrypting:
data = 0x1aff
range = 0x1000 to 0xa000 inclusive
data = aes_ofb_decrypt(data) // keystream "0x8d7c", data = 0x9783
0x9783 is in the range // halting too early!!
return 0x9783 // this isn't the right value!

Is there a better way to encrypt integers of an arbitrary range? Ideally I want it to be as strong as the AES algorithm. This example is obviously vulnerable to a brute force attack, but for cases where the integers are of or exceed 128 bits of length, I want the strength of the AES algorithm. Is this possible?

$\endgroup$
  • $\begingroup$ Is the initial integer guaranteed to be inside the arbitrary range - i.e. it would be an error to request encode of 3 or 25 into range 10..20? $\endgroup$ – Neil Slater Sep 29 '15 at 9:56
  • $\begingroup$ @NeilSlater Yes, though I assume it wouldn't throw an error, but rather encrypt it as if it was valid, and decryption would return garbage. But it is to be expected that the initial integer is in the range. $\endgroup$ – Daffy Sep 29 '15 at 10:06
  • $\begingroup$ Yes. $\;$ $\endgroup$ – user991 Sep 29 '15 at 17:51
5
$\begingroup$

What you are asking is a straight application of Format Preserving Encryption, which builds ciphers which input and output are in a constrained format (generically: common to input and output, hence preserved). The FPE field has many articles with proven techniques; and proposed standards, including BPS and SP800-38G Draft.

Note: the method tentatively used in the question is not Cycle-Walking, and I do not see that it can be made to work if the cryptogram is kept of the form aes_ofb_encrypt(data); problem is, if the encryption algorithm made more than one try, the decryption algorithm will first make a decryption attempt that does not match anything that the encryption side made, and will occasionally conclude it reached the original plaintext, when it did not.


Here is a minimal solution (for integers of arbitrary size), using a simple variant of CTR (or OFB) mode.

Let $[A,B]$ be the interval (assumed public), and $k\in\{128,192,256\}$ the bit width of the AES key. Let $W=1+B-A$ be the (positive) number of integers the interval. Let $n=\Big\lceil{\log_2(W)+2k\over128}\Big\rceil$ be the number of 128-bit blocks to encode $W-1$ in binary plus $2k$ extra bits.

We'll define $X\bmod N$ as the unique integer $Y$ with $0\le Y<N$ and $X-Y$ multiple of $N$. We'll assimilate integers and bitstrings using big-endian convention.

From the $IV$, let both encryption and decryption generate a bitstring $S$ of $128n$ bits by enciphering $(IV+j)\bmod2^{128}$ for $j$ growing from $0$ to $n-1$, using the AES block cipher (equivalently: by enciphering $n$ blocks of zeroes in AES-CTR mode; using OFB mode would also work though not equivalently).

Given the plaintext $P$, let the encryption procedure output ciphertext$$C=((S-P)\bmod W)+A$$and given $C$, let the decryption procedure output$$P=((S-C)\bmod W)+A$$ Trivially, ciphertext is in the desired range, and plaintext is recovered by the decryption procedure. $S$ is indistinguishable from uniform on $\{0,\dots,2^{128n}-1\}$, thus $S\bmod W$ is nearly uniform on $\{0,\dots,W-1\}$, with a very slight bias towards values below $2^{128n}\bmod W$, but so low that the adversary gains negligible advantage.

$\endgroup$
  • $\begingroup$ Thank you! This is exactly what I meant. Does the method you described here have a name? $\endgroup$ – Daffy Sep 30 '15 at 7:52
  • $\begingroup$ @user1193112: sorry, I have no name for the whole thing; $S$ is generated just as the keystream in AES-CTR or AES-OFB; $S\bmod W$ is a near-uniform random obtained by modular reduction of a suitably larger value; the rest is like a stream cipher, using elementary modular arithmetic rather than XOR. $\endgroup$ – fgrieu Sep 30 '15 at 8:36
  • $\begingroup$ @user1193112: I have simplified the formulas, and made them identical for encryption and decryption, so that the thing is now even closer to a stream cipher. $\endgroup$ – fgrieu Sep 30 '15 at 11:04
  • $\begingroup$ The previous method actually works better in my case, as it has the property of being commutative. $\endgroup$ – Daffy Oct 2 '15 at 0:21
  • 1
    $\begingroup$ @user1193112: thanks to the magic of this website, it is kept here $\endgroup$ – fgrieu Oct 2 '15 at 6:44

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.