I need a deterministic encryption scheme. Objectives:

  • Same plaintext is always encrypted to the same ciphertext.
  • Related plaintexts are encrypted to unrelated ciphertexts. (For example, attacker that knows two ciphertexts cannot learn whether corresponsing plaintexts start with the same prefix.)
  • Minimum space overhead.
  • Authenticated encryption, of course.

There are also some conditions that can make it easier:

  • I will encrypt small chunks of data (few dozens of bytes). It is OK to store them in RAM and then start the encryption.
  • The data will be padded to the same length all the time. So, we can conclude that the length of the data is some constant.
  • Not high performance requirements.

My first idea was to derive IV from plaintext using HMAC and then use some authenticated encryption that requires just unique (potentially predicable) IV, like AES-GCM. This requires both IV and authentication tag to be stored alongside the encryption.

But I have an idea how to reduce the space overhead even more: Use (H)MAC of plaintext as both IV and authentication of the message. I know this is generally dangerous scheme close to encrypt-and-mac, so I specify further requirements for primitives to mitigate its risks:

  • The encryption will not leak anything when decrypting attacker-manipulated data. Stream ciphers like AES-CTR look suitable here, because there are no risks related to padding oracle. It just “decrypts” any attacker-provided garbage to another garbage (rejected by MAC check later) without any side channel if the AES-CTR implementation is correct.
  • The encryption requires just unique IV, but it does not have any other requirements. Thill, AES-CTR looks suitable here.
  • The MAC does not leak any data. HMAC (potentially truncated to 128b) looks suitable there, because failing to do so would at least weaken preimage resistance of the underlying hash function.
  • Encryption uses a key completely unrelated to authentication key, of course. (This requirement might not be strictly needed when using, say, AES-CTR with HMAC-SHA256. However the requirement makes reasoning about security easier.)

The whole schema looks somewhat exotic to me, but I believe that I have resolved risks arising from the unusual design.

Is there any existing work that aims to do the same? Is there any research that would tell me anything about security of this scheme?

  • $\begingroup$ @DiscobarMolokai Good point. After a brief look, it looks much like my design, but with some CMAC-based construction instead of HMAC. The only issue I see there is that it seems to be hard to find usable implementations of SIV. I've seen some that have their own AES implementation in C, apparently not relying on AES-NI. I am afraid that many such implementations will be vulnerable to side channels. $\endgroup$
    – v6ak
    Feb 9 '17 at 11:59
  • $\begingroup$ @IlmariKaronen Thank you for the link, I was unable to find it. (I googled for “hmac as iv”, with no suitable result.) $\endgroup$
    – v6ak
    Feb 10 '17 at 20:11

Let L be your constant data length, choose a non-negative integer $\sigma$, choose a
FPE scheme over strings of length $\sigma$+L, and have $s$ range over strings of length $\sigma$.

encrypt$\hspace{-0.02 in}\big(\hspace{-0.04 in}\langle k\hspace{.02 in},\hspace{-0.03 in}s\rangle ,\hspace{-0.02 in}m\hspace{-0.03 in}\big) \;\;\;\; = \;\;\;\; $ FPenc ( ​ k ​ , ​ s || m ​ )

Decryption of c with $\langle k\hspace{.02 in},\hspace{-0.03 in}s\rangle$ is as follows:

if ​ length(c) ≠ $\sigma$+L ​ then output $\bot$, else set ​ d = FPdec(k,c)
if the left $\sigma$ bits of d are s then output the right L bits of d, else output $\bot$

Security should hold even if the adversary chooses $s$; you making it part of the key (in particular, random and secret) might reduce the impact of an attack on the underlying FPE scheme.

Depending on your use-case, you may be able to support a tweak. ​ The right FPE scheme depends on how 2$^{\sigma+L}$ compares to your upper bound the number of distinct [queries which are not just the opposite direction to an earlier query] (for any single tweak, if applicable).
The ​ low-query , medium-query , high-query ​ regimes are handled by
Generalized Feistel , swap-or-not , sometimes-recurse shuffle ​ respectively.
(I don't know whether-or-not they mention tweakability, but there's a simple generic
way to make any encryption scheme tweakable, which I can describe if you'd like.)

The main reason for using FPE rather than just a MAC is that
it essentially removes the adversary's control over the effects
of a successful forgery (thus perhaps allowing a shorter tag).
For example, with AES-CTR on a known plaintext, the adversary can
choose exactly what the decryption result will be if they guess the right tag.
A much-less-important reason is that forgery probability is in
fact slightly lower, since the guesses are nearly-independent.

Should I formalize either of those things?

If your scheme can be stateful, then you can further make it so that after any
attempted altering of what's sent (whether it's a replay or a re-ordering or just
a fresh cipher-block, and whether-or-not the attempt succeeds at forging),
[decryptions after the decryption of the initial tampering]
are indistinguishable from being independent with
$\big[\big[$probability ​ $1\hspace{-0.05 in}-\hspace{-0.03 in}\left(1/\hspace{-0.03 in}\left(2^{\sigma}\right)\right)$ ​ of outputting $\bot \big]$ ​ ​ ​ and
$\big[$probability $1/\hspace{-0.03 in}\left(2^{\sigma}\right)$ of outputting a random L-bit string$\big]\big]$ .

Should I explain how to do that?

  • $\begingroup$ “The main reason for using FPE rather than just a MAC is that it essentially removes the adversary's control over the effects of a successful forgery (thus perhaps allowing a shorter tag).” – IIUC, the probability of generating a correct random tag is the same, but (unlike CTR) the attacker will unlikely generate the plaintext she wants. $\endgroup$
    – v6ak
    Feb 10 '17 at 20:01
  • $\begingroup$ That's correct. ​ ​ $\endgroup$
    – user991
    Feb 10 '17 at 20:03
  • $\begingroup$ The scheme looks interesting, but I might have hard time with 1. finding a suitable FPE and 2. finding a suitable (ideally well-reviewed) implementation of the FPE. $\endgroup$
    – v6ak
    Feb 10 '17 at 20:05

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