Sam Trenholme's webpage
Support this website or listen to my music

A modest RadioGatún variant

I am proposing a modest RadioGatún variant, which I call RV200 (Radiogatún Variant 200 bytes).

Definition

RV200 is identical to RadioGatún, except:
  • The belt rows are 11 words wide, and the mill is 17 words wide.
  • Only ten (not 12) words are exclusive ored in the mill-to-belt feedforward stage
  • When mapping the input, it’s the final three words of the mill that are altered. In RadioGatún, those are words 17, 18, and 19 of the mill (16-18 if using zero-indexed arrays); the indexes are two less in RV200: 14, 15, and 16, or 13-15 when using zero-indexed arrays.
  • The inner Gamma operation, instead of being (a[(y+1)%m]|~a[(y+2)%m]), is (a[(y+1)%m]-a[(y+2)%m]) (bitwise or/not is replaced with subtraction).
  • The only allowed word sizes are 16 bits, 32 bits, and 64 bits. The 16-bit version is called “RV100”, the 32-bit version is “RV200”, and the 64-bit version is “RV400”. The primary version, and the only version I provide test vectors for, is the 32-bit one: RV200.
  • 32-bit RV200 is suitable for 256-bit hashes and as a stream cipher with 256 bits of key security. RV100 is suitable as a stream cipher with 128 bits of security. RV400 may be suitable for 512-bit hashes or as a stream cipher with 512 bits of security.
  • RV200’s behavior is undefined when the input is not an even number of octets in size. In other words, there is no specification for, say, its output if given a 3-bit input. Only multiples of eight bits are allowed for the input given to RV200.

Rationale

The reason I am making a RadioGatún (RG) variant is because RG is one of the fastest hashes out there, faster than MD5. It also is a very small, efficient stream cipher. However, the original RG design has some “hairline crack” issues which might become a realistic attack in the future; as Schneier has said: “Attacks always gets better, never worse.”

The reason for the changes in the design:

  • The “Gamma” step has bitwise or/not replaced by subtraction. Pretty much all of the attacks against RG out there start off with “since RadioGatún’s Gamma function has a low algebraic degree...” By using a different operation with very different mathematical properties, we thwart those kinds of attacks.

    The disadvantage of using subtraction is that, while it is just as fast when implemented as software (indeed, faster, since we only have to do one, not two operations), at the hardware level, subtraction needs five times (or six times, depending on how it is done) as many gates as or/not.

    However, software implementations are far more common than hardware implementations; for people who are designing hardware and something which is very fast when implemented in silicon, RG’s direct successor, SHA-3 (Keccak), is probably a better choice.

    Subtraction is done instead of addition because it more closely resembles bitwise or/not, and because, like RG’s or/not, a-b != b-a.

  • The belt and mill are made smaller to give RV200 a slight performance boost compared to RG, and to make the algorithm fit better on embedded chipsets. RG32 (RG with 32-bit words) needs 232 bytes to store its state; that leaves too little room on embedded chips with 256 bytes of ram, since we need seven temporary words in addition to the memory the state uses to calculate the mill. By using only 200 bytes, 56 bytes can be used for temporary variables or the stack, which is much more breathing room.

    The mill function for RV200 can be calculated using only 228 bytes, including the 200 bytes used to store its static state. This allows RV200 to fit inside, as just one example, a 68 cent ATTINY45-20MU with 256 bytes of RAM, instead of having to use a ATTINY85-20MU with 522 bytes of RAM which costs 77 cents — a 12% cost savings.

    Since RG has a sponge security claim based on the size of the mill, RV200 gives us 272 bits of claimed securty instead of the 304 bits of security 32-bit RadioGatún claims to have. That’s still over 256 bits of security.

  • The smallest version of RG/RV with usable security is the version using 16-bit words, which gives us 128 bits of security. The only reason to have smaller RV variants is to perform cryptographic research on them. There is no real-world reason to have 21-bit, 22-bit, and so on word sizes; indeed Keccak (RG’s direct sucessor) forces the word size to be a power of two — All modern non-embedded CPUs work with 8-bit, 16-bit, and 32-bit words, with a large number of CPUs also able to work with 64-bit words. Unless you still have a PDP-10 using 36-bit words in your closet, other word sizes just don’t make sense.

    Mathematically, the triangular numbers RV uses to determine the rotation amounts work best when the word size is a power of 2.

  • The reason why the primary word size is 32-bit is because there are still a lot of places where 64-bit words are inconvenient: Javascript’s bitwise operations only work with 32-bit words; and PHP compiled on 32-bit systems can not work with 64-bit words. Even here in the mid-2010s, the majority of smartphones still use 32-bit words.

  • By leaving non-octet-length inputs undefined, we could, in the future, propose RV200 variants by simply changing the final “padding” byte, which is currently hard-coded to one.

  • Looking at the number of cycles in the mill of a reduced word size RV200 variant (2-bit words), the RV200 mill function looks like a random permutation (the number of cycles a N-bit random permutation will normally have is log(2) * N; therefore, we would expect a 34-bit random permutation to have 23 or 24 cycles, and the mill in 2-bit word size RV200 has 23 cycles)

Sample code

Here is a sample implementation of the 32-bit RV200 in C: rv200ref.c

Here is a more readable Python implementation: rv200.py

Test vectors

Some test vectors for RV200:

RV200("") = b8d32785ded8f828b3ba74293dcdf433 a7b6abf40848248c3037c06712a3494b
RV200("1") = 3c619a527f6bcc4f1050b8bcbed7c6e1 c351feacf5379af7644ac51f3bcbf223
RV200("12") = df251c4cb0ec7273af6c072354fa92e2 d0ccbe22f050ad8bbcb90d58db47555a
RV200("1234") = ea5e5b6bbe714b3cede6dbb4ba0835c2 c2fb13945d41f633e0844ce7faa56865
RV200("12345678") = 73b99ad6b76960e868ef99a5f76b4eb2 e0f1c12bd71ab5cf0afb926e76832cab
RV200("123456789") = 230f97664a358286232d35e2953e05a7 9f02a689b4b7196b3891940c20e16393
RV200("12345678901234567890") = 022601dc5cfa0efda12bc0e273456c5d aea35671c49bcf716799cef9d5ca747e