# Achieving sub-block non-malleability

I have a noisy one-way communication channel where data is sent as a series of words of width n bits. Assume n is a constant roughly in the range of 16...48. I don't want bit errors in one word to affect the other words.

To achieve confidentiality in such a scenario, one would use a stream cipher, as that guarantees that a bit error in the ciphertext only causes the corresponding plaintext bit to be flipped. In contrast, a block cipher (of width 128, typically) would operate on several words at once, which would all be affected catastrophically by even a single bit flip.

A stream cipher, being malleable, enables an active attacker to target specific bits of the plaintext. And with a known ciphertext / plaintext pair, the attacker can essentially forge any desired plaintext.

I'm interested in achieving per-word non-malleability. It seems that applying a "mini block cipher" to each word would do that.

The Swap-or-Not shuffle (by Hoang, Morris and Rogaway) looks promising. It is defined as follows:

proc EKF(X)
for i ← 1 to r do
X′ ← Kᵢ ⊕ X
X̂ ← max(X,X′)
if Fᵢ(X̂) = 1 then X ← X′
return X


I need to supply the subkeys Kᵢ and the round functions Fᵢ. Here's what I've come up with: Since I'm intending to use a stream cipher anyway (reasoning below), I have a keystream known to the sender and receiver but noone else. For each round, I therefore consume n bits from the keystream for Kᵢ and one bit for Fᵢ, as follows:

Kᵢ ← {0,1}ⁿ  // from keystream

proc Fᵢ(X)
b ← {0,1}    // from keystream
return parity(X) ⊕ b


Where parity(X) is the boolean parity function: parity(X) = popcount(X) mod 2

After doing r shuffling rounds, I then apply the stream cipher in the usual way. For each word, I therefore consume r(n+1)+n bits from the keystream.

The belt-and-suspenders approach of shuffle-then-cipher is reasonable in my opinion, given that stream ciphers and modes (such as AES-CTR) are well studied, as opposed to my instantiation of the Swap-or-Not shuffle. Secondly, it allows me to be frugal with the keystream by choosing a moderate number of rounds r for the shuffle, because confidentiality is assured by the stream cipher.

I am aware that this scheme does not assure authenticity or integrity. I'm simply interested in frustrating an attacker who intends to tamper with a ciphertext to obtain specific plaintext changes.

I have several questions:

1. Can shuffling the words before applying the stream cipher make any security property worse compared to just applying the stream cipher? I would assume not but would be gladly corrected.

2. Is my assumption correct that with sufficient rounds of a good shuffle procedure, an attacker is prevented from any targeted tampering of specific plaintext bits?

3. Are my methods for obtaining Kᵢ and the procedure Fᵢ sound?

The first revision of the Swap-or-Not paper in section 6 introduced a realization with additional subkeys Lᵢ. In the second revision of the paper, that section (now numbered 7) points out that the function being linear makes the inner-product method breakable. How is that and does my method suffer the same problem?

4. Are there better methods?

For example, would wrapping the Swap-or-Not in Sometimes-Recurse help reduce the required number of rounds for a given security level in this case? I have a hard time getting an intuitive understanding of how Sometimes-Recurse achieves thorough shuffling despite recursing on one half only.

What I'm looking to achieve could be called format-preserving encryption on {0,1} for n < 128. There is some activity at NIST, and I would certainly prefer something endorsed by a standards body, but it looks like FF1 and FF3 are patent-encumbered.