Subject: [Cfrg] Introducing Chicha stream cipher

From: EddyHawk <[email-masked]>
Date: Thu, 28 May 2015 20:36:28 -0700

Dear CFRG members,

Here I propose my variant of Chacha stream cipher by D. J. Bernstein that may be stronger than the original, measured by a simple metric, without performance penalty under plain IA-32 implementations. However, certain optimizations which are considered in Chacha design, such as vectorized implementations for improved performance, are ignored here. Therefore such optimizations may or may not be applicable.

As I am not the original designer of Chacha, I can not and should not name it Chacha2. So I pick the name 'Chicha' for the modified Chacha proposed here.

Chicha is identical in every respect to Chacha except in these:
  -its quarterround function
  -its even (diagonal) round
While Chacha uses this quarterround function:
  a:=a+b; 	d:=d xor a; 	d:=rot32l(d,16);
  c:=c+d; 	b:=b xor c; 	b:=rot32l(b,12);
  a:=a+b; 	d:=d xor a; 	d:=rot32l(d, 8);
  c:=c+d; 	b:=b xor c; 	b:=rot32l(b, 7);
Chica uses this quarterround function:
  a:=a+d; 	a:=rot32l(a,17); 	b:=b xor a;
  c:=c+b; 	c:=rot32l(c,11); 	d:=d xor c;
  a:=a+d; 	a:=rot32l(a, 7); 	b:=b xor a;
  c:=c+b; 	c:=rot32l(c,23); 	d:=d xor c;
So Chicha-qrf uses 'xor rotated sum' as Salsa20's, starts with a:=a+d, and replaces rotation constants to 17,11,7,23 (all prime numbers).

And while Chacha uses this even round:
  chacha-qrf( 0, 5,10,15);
  chacha-qrf( 1, 6,11,12);
  chacha-qrf( 2, 7, 8,13);
  chacha-qrf( 3, 4, 9,14);
Chicha uses this even round:
  chicha-qrf( 0, 9, 6,15);
  chicha-qrf( 1,11, 4,14);
  chicha-qrf( 2, 8, 7,13);
  chicha-qrf( 3,10, 5,12);

How these changes improve over Chacha? I ascertain the improvement simply by measuring the randomness of its keystreams against Chacha's and Salsa20's. More specifically, I implement and/or adapt XSalsa20, XChacha, and XChicha to allow variable rounds and to apply feed-forwarding after the last chosen round, and I use randomly generated keys & IVs to produce their respective keystreams, several tenths of them and about 3 Mb each.

Then I measure their chi-square distributions using John Walker's ENT program on byte-level (ENT's default setting):
  Salsa20	keystreams attain good    	randomness after 4 rounds
  Chacha 	keystreams attain good  	randomness after 3 rounds
    (chi-square distribution range: 202-311)
  Chicha 	keystreams attain decent 	randomness after 2 rounds
    (chi-square distribution range: 237-666)
Afterwards, we look at the best known attack on Salsa20 & Chacha so far:
  Salsa20	best known attack is on 	8 rounds
  Chacha 	best known attack is on 	7 rounds

>From these, it's easy to generalize that Chicha best known attack is on 6 rounds (or unattackable on 7 rounds by such/similar attack), naively assuming that its increased randomness will translate to better attack resistance on higher rounds in the same degree as its predecessors.

Note that eventhough Chicha doesn't attain good randomness after 2 rounds, suggesting that its hypothetical best attack will reach more than 6 rounds, my experiment show that Chicha does attain such randomness after hypothetical 2.25 rounds (ie, applying an additional quarterround on word 12,13,14,15 after odd round and before even round, but not after even round) which should result in hypothetical best attack on 6.25 rounds, which are still below 7 rounds.

In other words, I rely on earlier randomness of Chicha to back up its higher security claim against Chacha. So a way to disqualify Chicha as such is by showing an attack better than brute-force against Chicha on 7+ rounds.

Questions? Comments? Feedback?

Thank you for reading.

Best regards,
EddyHawk