Why is the tweak length 64bit in BPS FPE algorithm?

In the algorithm for BPS Format Preserving Encryption

Is this tweak always the same length (64bit)?

Why did they choose the length 64bit for the tweak?

• I see not leak left by: " the 64-bit tweak value $T$ ". In short a tweak is an extension of the key, only not assumed secret. – fgrieu Sep 29 '15 at 17:57
• @fgrieu why they choose that particular length 64 bit tweak? – erotavlas Sep 29 '15 at 18:09
• 64-bit is fine for a character index, a session number.. – fgrieu Sep 29 '15 at 18:21
• @fgrieu I don't understand is this value independent of the internal calculations of the algorithm (like block lengths) I guess i was just wondering if the length has any significance, or is it an arbitrary number they used that is good enough for this. – erotavlas Sep 29 '15 at 18:25

From the paper:

We denote by $f$ the number of output bits of the internal function $F$

and

We first divide the 64-bit tweak $T$ into two 32-bit sub-tweaks $T_L$ and $T_R$

plus

We denote by $L_i$ (resp. $R_i$) the left (resp. right) branch value after application of round $i$.

with the note

Note that because of our restriction on the number of input $s$-integers, we always ensure that each branch can be coded on a $(f − 32)$-bit word.

Right, so now look at part of the definition of the cipher:

...

$L_{i+1} = L_i \boxplus F_K ((T_R \oplus i) \times 2^{f −32} + R_i) \mod s^l;$

...

although multiplication is represented by a dot instead of $\times$. Similarly for the calculation of the state $R_{i+1}$ of course.

Basically, this shifts the tweak to the most significant 32 bits, leaving the rest for the state. Now $F$ can be AES, HMAC-SHA-2 or TDES. TDES has a block size of 64 bit. If the tweak size was 128 bit then there would not be any space left for $R$ or $L$ that make up the internal state.

So the tweak size is such that repetition of the tweak is unlikely and it can still be used efficiently when the encryption uses a 64 bit block cipher. If the tweak would be larger the construction would become less efficient, up to the point that the scheme would not work at all.

• Disclaimer: I got interested in the paper and just decided to read it... – Maarten Bodewes Sep 29 '15 at 23:24
• I guess that if you would encrypt more than $2^{32}$ plaintext and you would use AES or HMAC that a larger tweak could be an idea. Or you could use a modern tweakable block cipher of course. – Maarten Bodewes Sep 29 '15 at 23:35
• The value that gets passed into the AES function E is TR or TL XOR with round count i, multiply by 2^96. Does this value now have 2^128 after multiplication (since TR or TL each is 2^32)? – erotavlas Sep 30 '15 at 13:00
• If you mean that it should now consist of 128 bits, the block / output size of AES then: yes. – Maarten Bodewes Sep 30 '15 at 13:42
• No necause the multiplication with 2 to the power x means that x lower order bits are set to 0. If you add any value of x bits to that then you will of course not overflow. It's identical to shifting x to the left and then OR or XOR R_i into the value. – Maarten Bodewes Sep 30 '15 at 14:58