[Cryptography] Introducing Chicha stream cipher

dj at deadhat.com dj at deadhat.com
Thu Jun 4 17:26:01 EDT 2015


> Dear cryptography list 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?
>

Thing #1:

What makes you think Chi-Square T.O.R. is the right algorithm to test for
randomness? I don't see the logic. It's not even easy to judge the output
of that test because what you are looking for is the uniformity of the
metric over many tests. No individual test tells you anything, nor is it
sensitive to correlation between the data.

In addition to base statistics like you get out of ent, I would look at
things like the Markov-Renye min entropy test and run it over a few
megabytes of data with group lengths > 7. It's described in draft
SP800-90B. Also distinguishability tests (dieharder, SP800-22 etc), if you
can get enough data.

Thing #2:
It reminds of meta-AES which is a lunatic cipher I dreamt up that has
similar goals. Implement AES, but replace the key expansion algorithm with
a reversible mode of AES that over 10 rounds is strongly indistinguishable
from random, specifically AES-CTR. Inefficient as heck, but it works. If
you want 256 bit keys, just make key[128:255] = the CTR IV rather than
using the nasty 256 bit key schedule of normal-AES. For this I probably
deserve shooting.







More information about the cryptography mailing list