/*
Shazam is a fast 1024-bit (128B) encryption function. Shazam has the following
attributes— which are required[1] for use in constructing sequential memory-hard
functions¹; and which are not sufficient to make Shazam a secure stream cipher
nor a cryptographic hash function[2]:

  1. The outputs are uniformly distributed.
  2. Per instance computation can’t be significantly accelerated by more
     internal parallelism than can be exploited on CPUs nor by precomputation of
     a limited-space data structure.
  3. Computation of any segment of the output can’t be significantly faster
     than computing the entire output.
  4. Maximizes the ratio of the output length to the execution speed.

For security against the structure around the matrix diagonal which passes
through[3] the Salsa20 and ChaCha block function, the first use of Shazam in a
chain of hashes should employ input constants[4].

ChaCha[5] seems best fit to these requirements; and compared to Salsa20 (and its
impressive visualized diffusion[8]), ChaCha has 50% greater bit diffusion[6],
updating each 32-bit doubleword twice per quarter-round, equivalent security yet
requiring one less round[9], and equivalent or faster per-round execution speed.
Same as for Salsa20, each ChaCha quarter-round is a confusion-and-diffusion[10]
block function that employs (48 per round, i.e. 16 each of) 32-bit
add-rotate-xor (ARX) operations.

Salsa20 alternates row and column rounds which required a slow matrix transpose
between rounds (i.e. swapping rows and columns across the diagonal) for naive
SIMD vector implementations. ChaCha incorporates an optimization[7] first
discovered for Salsa20[11] that instead rotates each column (except the first)
by multiples of the 32-bit doublewords; which is a faster operation on SIMD
registers than swapping. The slow inverse mapping to generate the final
output[11] is eliminated in ChaCha[7].

Rotate operations on SIMD registers are typically only fast for multiples of
8-bits (one byte). Although ChaCha has one each of (multiple of a byte) 16-bit
and 8-bit rotate operations that Salsa20 didn’t, the other two rotate operations
per quarter-round are (12-bit and 7-bit which are) not multiples of a byte. To
maximize the ratio in requirement #4 and enable all rotate operations to be a
multiple of a byte, Shazam widens ChaCha from 512-bit to 1024-bit by increasing
the 32-bit doublewords to 64-bit quadwords. Thus the chosen rotate operations
are 32-bit, 24-bit, 16-bit, and 8-bit per quarter-round. Most recent mobile ARM
processors have the NEON SIMD feature which provides sixteen 128-bit SIMD
registers comprising two 64-bit quadwords. Thus two instances of Shazam per core
(or per hyperthread for Intel CPUs) can be executed in parallel. NEON provides
the VTBL instruction[12] for (multiple of a byte) rotates on 64-bit quadwords.
ARM’s Advanced SIMD doubles the number of 128-bit SIMD registers and Intel’s
AVX2 doubles the SIMD registers’ width to 256-bit; and thus can execute in
parallel four instances of Shazam per core (or per hyperthread).

The widening to 256-bit registers can be implemented on AVX2 for column rotates
(of the four 64-bit quadwords) with a single instruction per column. On ARM NEON
the maximum register size is 128-bit so each column rotate can’t be accomplished
with one instruction because the VTBL instruction has only a 64-bit quadword
output. The third column rotate can be accomplished with a single VSWP
instruction, and the second and fourth columns each with two VSWP instructions.
Note the definition of the terms ‘quadword’ and ‘doubleword’ are different for
AVX2 and NEON; and this document adopts the AVX2 definition where quadwords are
four 16-bit words and doublewords are two 16-bit words.

________________________________________________________________________________
¹ A sequential memory-hard function is typically one-way and has uniformly
  distributed, constant length outputs; and is a non-invertible hash function
  only if the input is variable-length because variable-length input is the
  definition of a hash function.

ARX Security

ARX operations are employed in some block encryption algorithms, because they
are relatively fast in software on general purpose CPUs and reasonable
performance on dedicated hardware circuits, and also because they run in
constant time, and therefore immune to timing attacks.

Rotational cryptanalysis attempts to attack encryption functions that employ ARX
operations. Salsa and ChaCha employ input constants to defeat such attacks[3].

Addition and multiplication modulo (2ⁿ-1) diffuse through high bits but set low
bits to 0. Without shuffles or rotation permutation to diffuse changes from high
to low bits, addition and multiplication modulo (2ⁿ-1) can be broken with low
complexity working from the low to the high bits[13].

The overflow carry bit, i.e. addition modulo ∞ minus addition modulo (2ⁿ-1),
obtains the value 0 or 1 with equal probability, thus addition modulo (2ⁿ-1) is
discontinuous—i.e. defeats linearity over the ring Z/2ⁿ[17]—because the carry
is 1 in half of the instances[14] and defeats linearity over the ring Z/2[16]
because the low bit of both operands is 1 in one-fourth of the instances.

The number of overflow high bits in multiplication modulo ∞ minus multiplication
modulo (2ⁿ-1) depends on the highest set bits of the operands, thus
multiplication modulo (2ⁿ-1) defeats linearity over the range of rings Z/2 to
Z/2ⁿ.

Logical exclusive-or defeats linearity over the ring Z/2ⁿ always[16] because it
is not a linear function operator.

Each multiplication modulo ∞ amplifies the amount diffusion and confusion
provided by each addition. For example, multiplying any number by 23 is
equivalent to the number multiplied by 16 added to the number multiplied by 4
added to the number multiplied by 2 added to the number. This is recursive since
multiplying the number by 4 is equivalent to the number multiplied by 2 added to
the number multiplied by 2. Addition of a number with itself is equivalent to a
1-bit left shift or multiplication by 2. Multiplying any variable number by
another variable number creates additional confusion.

Multiplication defeats rotational cryptoanalysis[15] because unlike for
addition, rotation of the multiplication of two operands never distributes over
the operands, i.e. is not equal to the multiplication of the rotated operands.
A proof is that rotation is equivalent to the exclusive-or of left and right
shifts. Left and right shifts are equivalent to multiplication and division by a
factor of 2, which don’t distribute over multiplication, e.g.
(8 × 8) × 2 ≠ (8 × 2) × (8 × 2) and (8 × 8) ÷ 2 ≠ (8 ÷ 2) × (8 ÷ 2). Addition
modulo ∞ is always distributive over rotation[17] because addition distributes
over multiplication and division e.g. (8 + 8) ÷ 2 = (8 ÷ 2) + (8 ÷ 2). Due to
the aforementioned non-linearity over Z/2ⁿ due to carry, addition modulo (2ⁿ-1)
is only distributive over rotation with a probability 1/4 up to 3/8 depending on
the relative number of bits of rotation[15][18].

However, multiplication modulo (2ⁿ-1) sets all low bits to 0,
orders-of-magnitude more frequently than addition modulo (2ⁿ-1)— a degenerate
result that squashes diffusion and confusion.

References

[1] C. Percival, “Stronger Key Derivation Via Sequential Memory-Hard Functions”,
    pg. 9: http://www.tarsnap.com/scrypt/scrypt.pdf#page=9

[2] Stream cipher security considerations for Salsa20 aren’t required, c.f.
    D. Berstein, “Salsa20 security”: https://cr.yp.to/snuffle/security.pdf

    Cryptographic hash function security considerations aren’t required[1].

[3] D. Berstein, “Salsa20 security”, §4 Notes on the diagonal constants, pg. 4:
    https://cr.yp.to/snuffle/security.pdf#page=4

    J. Hernandez-Castro et al, “On the Salsa20 Core Function”, §4 Conclusions,
    pg. 6: https://www.iacr.org/archive/fse2008/50860470/50860470.pdf#page=6

[4] Y. Nir et al, “ChaCha20 and Poly1305 for IETF Protocols”, IRTF RFC 7539,
    §2.3. The ChaCha20 Block Function, pg. 7:
    https://tools.ietf.org/html/rfc7539#page-7

[5] D. Berstein, “ChaCha, a variant of Salsa20”:
    http://cr.yp.to/chacha/chacha-20080128.pdf

[6] D. Berstein, “ChaCha, a variant of Salsa20”, pg. 3:
    http://cr.yp.to/chacha/chacha-20080128.pdf#page=3

[7] D. Berstein, “ChaCha, a variant of Salsa20”, pg. 5:
    http://cr.yp.to/chacha/chacha-20080128.pdf#page=5

[8] https://cr.yp.to/snuffle/diffusion.html

[9] https://en.wikipedia.org/w/index.php?title=Salsa20&oldid=703900109#ChaCha_variant

[10] http://en.wikipedia.org/wiki/Confusion_and_diffusion

     http://www.theamazingking.com/crypto-block.php

     H. Feistel, “Cryptography and Computer Privacy”, Scientific American,
     Vol. 228, No. 5, 1973:
     http://apprendre-en-ligne.net/crypto/bibliotheque/feistel/

[11] P. Mabin Joseph et al, “Exploiting SIMD Instructions in Modern
     Microprocessors to Optimize the Performance of Stream Ciphers”, IJCNIS
     Vol. 5, No. 6, pp. 56-66, §C. Salsa 20/12, pg. 61:
     http://www.mecs-press.org/ijcnis/ijcnis-v5-n6/IJCNIS-V5-N6-8.pdf#page=6

[12] “ARM Compiler toolchain Assembler Reference”, §4.4.9 VTBL, VTBX, pg. 224:
     http://infocenter.arm.com/help/topic/com.arm.doc.dui0489f/DUI0489F_arm_assembler_reference.pdf#page=224

     T. Terriberry, “SIMD Assembly Tutorial: ARM NEON”,
     §Byte Permute Instructions, pg. 53:
     http://people.xiph.org/~tterribe/daala/neon_tutorial.pdf#page=53

[13] D. Khovratovich et al, “Rotational Cryptanalysis of ARX”,
     §2 Related Work, pg. 2:
     https://www.iacr.org/archive/fse2010/61470339/61470339.pdf#page=2

[14] D. Khovratovich et al, “Rotational Cryptanalysis of ARX”,
     §6 Cryptanalysis of generic AR systems, pg. 10:
     https://www.iacr.org/archive/fse2010/61470339/61470339.pdf#page=10

[15] D. Khovratovich et al, “Rotational Cryptanalysis of ARX”,
     §3 Review of Rotational Cryptanalysis, pg. 3:
     https://www.iacr.org/archive/fse2010/61470339/61470339.pdf#page=3

[16] D. Berstein, “Salsa20 design”, §2 Operations:
     https://cr.yp.to/snuffle/design.pdf

[17] M. Daum, “Cryptanalysis of Hash Functions of the MD4-Family”,
     §4.1 Links between Different Kinds of Operations, pg. 40:
     www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/DaumMagnus/diss.pdf#page=48

[18] M. Daum, “Cryptanalysis of Hash Functions of the MD4-Family”,
     §4.1.3 Modular Additions and Bit Rotations, Corollary 4.12, pg. 47:
     www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/DaumMagnus/diss.pdf#page=55
*/