Can the Threefish tweak block cipher have its fixed 128 bit tweak size extended to match the block size (256/512/1024)

Question

The Threefish tweak block cipher has a fixed size tweak (128 bits) and three different possible key/block sizes (256/512/1024 bits).

The MCOE on-line authenticated encryption mode presents three different implementations, one of which requires a native tweak block cipher and the other two can be implemented with an ordinary block cipher.

One of the requirements of the native tweak block cipher is that the tweak is the same size as the block, which is not the case for Threefish.

While Threefish as-is can be used in the other two methods (ie: fix tweak to a constant and use as ordinary block cipher), this method is not efficient. Ideally, Threefish would be modified to have its tweak size match the block size, leading to an optimal solution.

After looking at the Threefish sub-key generation, it appears that the tweak can be extended by simply increasing the tweak size to the block size and changing the tweak index modulus to fit the new block size (see code below).

/* NW = Number of 64-bit words for key and block size */

/* Note : Key and tweak array sizes are one 64-bit word larger to accomodate a 'parity' word */

auto subkey (U64 const key [NW+1] , U64 const tweak [3] , unsigned const s , unsigned const i) noexcept -> U64
{
  auto const s_common = key [(s + i) % (NW + 1U)] ;

  switch (i)
    {
      case NW - 1 : [[ unlikely ]] return s_common + s ;

      case NW - 2 : [[ unlikely ]] return s_common + tweak [(s + 1U) % 3U] ;

      case NW - 3 : [[ unlikely ]] return s_common + tweak [(s + 0U) % 3U] ;

      default     : [[ likely   ]] return s_common ;
    }
}

While this appears to generate "nice looking encryption", would this modification be secure or would it open new potential attack vectors?

If this modification is insecure, or if there is a better solution, please elaborate.

EDIT It occured to me after posting this question that simply modifiying the tweak modulus to match the increased tweak size is not enough. Each unique tweak should select a different permutation for the same key and should take into account the size of the tweak as well. Otherwise a 128 bit tweak of all zeroes would lead to the same encryption as 256/512/1024 bit tweak of all zeroes.

I modified the tweak parity to match that of the key parity, except with different constants for each tweak size (zero for 128 bit case to maintain compatibility).

This appears to address the issue, but prompts the question :

Will this modification create unique permutations for a given key and all possible tweak sizes and values?

If yes, how do you show this?

Answer 1

You can extend tweak of Threefish, but that is significant modification and requires analysis. That would no longer be Threefish. It will probably decrease performance.

All subkeys (every key/tweak addition) in Threefish depend on all key and tweak bits. Your modification would need 32 round for Threefish-1024 to use all the bits of tweak just once. I did not make detailed analysis, but I'm pretty sure it would at least need much more rounds to be safe.

I did try to increase tweak size in Threefish myself, but its key schedule is quite fragile. You could increase how much tweak you use in single addition, but then new problems arise since key and tweak interact.

You could implement LED cipher style key schedule. It is simpler and easier to analyze. However, it would also probably require more rounds and counter addition should be replaced with something like TEA cipher delta constant (because there would be no parity constant).

Without changing Threefish you could use its tweak as key and its key as tweak, but that limits key to 128-bit.

Another option for McOE would be SHACAL-2 with 256/512 bit block size and 512/1024 bit key size. It has cheap key schedule so you can use half of key as tweak.