3
\$\begingroup\$

Rolling my own cryptography in order to better understand the subject and came up with implementation of the ChaCha20 algorithm pasted below.

I'm using the test vectors listed in the RFC along with the BouncyCastle library (and assuming its correctness) in order to validate my output and everything looks accurate so far. I've also optimized things as much as I can without resorting to SIMD instructions or parallel processing and tests show that I'm roughly 35-45% faster than BouncyCastle which has me feeling pretty good about the code.

Now that I'm starting to run out of ideas I figure that it's time to reach out to the community in order to help hunt down any accuracy or performance problems that might still need fixing.

Usage:

var chacha = new ChaCha20(
    0X03020100U,
    0X07060504U,
    0X0B0A0908U,
    0X0F0E0D0CU,
    0X13121110U,
    0X17161514U,
    0X1B1A1918U,
    0X1F1E1D1CU,
    0X00000000U,
    0X00000000U,
    0X00000000U,
    0X00000000U
);

// encrypt or decrypt file
chacha.Transform(@"C:\Temp\SomeFile.txt");

// encrypt or decrypt array
var data = new byte[128];

chacha.Transform(data);

Code:

/// <remarks>
/// https://cr.yp.to/chacha/chacha-20080128.pdf
/// https://cr.yp.to/snuffle/spec.pdf
/// https://eprint.iacr.org/2013/759.pdf
/// https://tools.ietf.org/html/rfc7539
/// http://loup-vaillant.fr/tutorials/chacha20-design
/// </remarks>
public class ChaCha20
{
    private const int BLOCK_SIZE_IN_BYTES = (STATE_SIZE_IN_BYTES * 16);
    private const int STATE_SIZE_IN_BYTES = sizeof(uint);

    [CLSCompliant(false)]
    public const uint DEFAULT_STATE0 = 0x61707865U;
    [CLSCompliant(false)]
    public const uint DEFAULT_STATE1 = 0x3320646EU;
    [CLSCompliant(false)]
    public const uint DEFAULT_STATE2 = 0x79622D32U;
    [CLSCompliant(false)]
    public const uint DEFAULT_STATE3 = 0x6B206574U;

    [CLSCompliant(false)]
    protected readonly uint m_state0, m_state1, m_state2, m_state3,
                            m_state4, m_state5, m_state6, m_state7,
                            m_state8, m_state9, m_stateA, m_stateB,
                            m_stateC, m_stateD, m_stateE, m_stateF;

    /// <summary>
    /// Initializes a new instance of the <see cref="ChaCha20"/> class to the initial state indicated by sixteen 32-bit unsigned integers.
    /// </summary>
    [CLSCompliant(false)]
    public ChaCha20(
        uint state0, uint state1, uint state2, uint state3,
        uint state4, uint state5, uint state6, uint state7,
        uint state8, uint state9, uint stateA, uint stateB,
        uint stateC, uint stateD, uint stateE, uint stateF
    ) {
        m_state0 = state0;
        m_state1 = state1;
        m_state2 = state2;
        m_state3 = state3;
        m_state4 = state4;
        m_state5 = state5;
        m_state6 = state6;
        m_state7 = state7;
        m_state8 = state8;
        m_state9 = state9;
        m_stateA = stateA;
        m_stateB = stateB;
        m_stateC = stateC;
        m_stateD = stateD;
        m_stateE = stateE;
        m_stateF = stateF;
    }
    /// <summary>
    /// Initializes a new instance of the <see cref="ChaCha20"/> class to the initial state indicated by twelve 32-bit unsigned integers.
    /// </summary>
    [CLSCompliant(false)]
    public ChaCha20(
        uint state4, uint state5, uint state6, uint state7,
        uint state8, uint state9, uint stateA, uint stateB,
        uint stateC, uint stateD, uint stateE, uint stateF
    ) : this(
        DEFAULT_STATE0, DEFAULT_STATE1, DEFAULT_STATE2, DEFAULT_STATE3,
        state4, state5, state6, state7,
        state8, state9, stateA, stateB,
        stateC, stateD, stateE, stateF
    ) { }

    public void Transform(Stream source, Stream destination) {
        var dataBuffer = new byte[BLOCK_SIZE_IN_BYTES];
        var keyStreamBuffer = new byte[BLOCK_SIZE_IN_BYTES];
        var keyStreamPosition = m_stateD.ToUInt64(m_stateC);
        var numBytesRead = 0;

        while (unchecked(BLOCK_SIZE_IN_BYTES - 1) < (numBytesRead = source.Read(dataBuffer, 0, BLOCK_SIZE_IN_BYTES))) {
            if (source == destination) {
                destination.Position -= BLOCK_SIZE_IN_BYTES;
            }

            BlockRound(this, keyStreamPosition++, keyStreamBuffer, 0UL); // get next key stream chunk
            dataBuffer.VectorXor(keyStreamBuffer, BLOCK_SIZE_IN_BYTES, 0UL, 0UL); // xor data with key stream
            destination.Write(dataBuffer, 0, BLOCK_SIZE_IN_BYTES); // write transformed data to destination
        }

        if (numBytesRead != 0) {
            if (source == destination) {
                destination.Position -= numBytesRead;
            }

            BlockRound(this, keyStreamPosition++, keyStreamBuffer, 0UL); // get next key stream chunk
            dataBuffer.VectorXor(keyStreamBuffer, unchecked((ulong)numBytesRead), 0UL, 0UL); // xor data with key stream
            destination.Write(dataBuffer, 0, numBytesRead); // write transformed data to destination
        }
    }
    public void Transform(Stream stream) {
        Transform(stream, stream);
    }
    public void Transform(byte[] data) {
        using (var memoryStream = new MemoryStream(data, true)) {
            Transform(memoryStream);
        }
    }
    public void Transform(string fileName) {
        using (var fileStream = new FileStream(fileName, FileMode.Open, FileAccess.ReadWrite, FileShare.None)) {
            Transform(fileStream);
        }
    }

    /// <summary>
    /// Fills an array of bytes with the key stream calculated from the specified <see cref="ChaCha20"/> instance and iv.
    /// </summary>
    [CLSCompliant(false)]
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void BlockRound(ChaCha20 chacha20, ulong iv, byte[] destination, ulong destinationOffset) {
        var counterLow = checked((uint)iv.CleaveHigh());
        var counterHigh = checked((uint)iv.CleaveLow());

        var tState0 = chacha20.m_state0;
        var tState1 = chacha20.m_state1;
        var tState2 = chacha20.m_state2;
        var tState3 = chacha20.m_state3;
        var tState4 = chacha20.m_state4;
        var tState5 = chacha20.m_state5;
        var tState6 = chacha20.m_state6;
        var tState7 = chacha20.m_state7;
        var tState8 = chacha20.m_state8;
        var tState9 = chacha20.m_state9;
        var tStateA = chacha20.m_stateA;
        var tStateB = chacha20.m_stateB;
        var tStateC = counterLow;
        var tStateD = counterHigh;
        var tStateE = chacha20.m_stateE;
        var tStateF = chacha20.m_stateF;

        for (var i = 0; i < 10; i++) {
            DoubleRound(
                ref tState0, ref tState1, ref tState2, ref tState3,
                ref tState4, ref tState5, ref tState6, ref tState7,
                ref tState8, ref tState9, ref tStateA, ref tStateB,
                ref tStateC, ref tStateD, ref tStateE, ref tStateF
            );
        }

        unchecked {
            tState0 += chacha20.m_state0;
            tState1 += chacha20.m_state1;
            tState2 += chacha20.m_state2;
            tState3 += chacha20.m_state3;
            tState4 += chacha20.m_state4;
            tState5 += chacha20.m_state5;
            tState6 += chacha20.m_state6;
            tState7 += chacha20.m_state7;
            tState8 += chacha20.m_state8;
            tState9 += chacha20.m_state9;
            tStateA += chacha20.m_stateA;
            tStateB += chacha20.m_stateB;
            tStateC += counterLow;
            tStateD += counterHigh;
            tStateE += chacha20.m_stateE;
            tStateF += chacha20.m_stateF;
        }

        if (BitConverter.IsLittleEndian) {
            tState0.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 0)));
            tState1.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 1)));
            tState2.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 2)));
            tState3.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 3)));
            tState4.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 4)));
            tState5.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 5)));
            tState6.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 6)));
            tState7.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 7)));
            tState8.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 8)));
            tState9.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 9)));
            tStateA.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 10)));
            tStateB.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 11)));
            tStateC.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 12)));
            tStateD.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 13)));
            tStateE.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 14)));
            tStateF.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 15)));
        }
        else {
            tState0.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 0)));
            tState1.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 1)));
            tState2.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 2)));
            tState3.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 3)));
            tState4.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 4)));
            tState5.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 5)));
            tState6.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 6)));
            tState7.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 7)));
            tState8.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 8)));
            tState9.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 9)));
            tStateA.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 10)));
            tStateB.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 11)));
            tStateC.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 12)));
            tStateD.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 13)));
            tStateE.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 14)));
            tStateF.ReverseBytes().GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 15)));
        }
    }
    /// <summary>
    /// Executes eight QuarterRound operations (four "column-rounds" + four "row-rounds") on the specified <see cref="ChaCha20"/> instance.
    /// </summary>
    [CLSCompliant(false)]
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void DoubleRound(
        ref uint state0, ref uint state1, ref uint state2, ref uint state3,
        ref uint state4, ref uint state5, ref uint state6, ref uint state7,
        ref uint state8, ref uint state9, ref uint stateA, ref uint stateB,
        ref uint stateC, ref uint stateD, ref uint stateE, ref uint stateF
    ) {
        QuarterRound(ref state0, ref state4, ref state8, ref stateC);
        QuarterRound(ref state1, ref state5, ref state9, ref stateD);
        QuarterRound(ref state2, ref state6, ref stateA, ref stateE);
        QuarterRound(ref state3, ref state7, ref stateB, ref stateF);
        QuarterRound(ref state0, ref state5, ref stateA, ref stateF);
        QuarterRound(ref state1, ref state6, ref stateB, ref stateC);
        QuarterRound(ref state2, ref state7, ref state8, ref stateD);
        QuarterRound(ref state3, ref state4, ref state9, ref stateE);
    }
    /// <summary>
    /// Executes the basic operation of the ChaCha20 algorithm which "mixes" four state variables per invocation.
    /// </summary>
    [CLSCompliant(false)]
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void QuarterRound(ref uint a, ref uint b, ref uint c, ref uint d) {
        d = (d ^= unchecked(a += b)).RotateLeft(16);
        b = (b ^= unchecked(c += d)).RotateLeft(12);
        d = (d ^= unchecked(a += b)).RotateLeft(8);
        b = (b ^= unchecked(c += d)).RotateLeft(7);
    }
}
\$\endgroup\$
1
\$\begingroup\$

Short answer: use an array instead of multiple parameters and do not try to beat your compiler with optimizations, it's your friend and what you have to do is to help him.


Let's assume performance are enough. Let's talk about readability.

First of all, why class is not sealed and it has protected fields? I do not see any extension point in your class. Let's mark it sealed, change protected to private and make it open if, and only if, you will need it.

I prefer public/internal/protected/private ordering but also opposite is common and good, just pick a sensible ordering and stick to it. I also do not like snake upper-case constants but if it's for private const fields then no problem, just do not use it for public ones! Also: why those two public const fields are public?!

Methods with 16 parameters are a nightmare to write, to test and to call. We're lucky we have the appropriate data structure: array.

public sealed class ChaCha20
{
    private const int NUMBER_OF_STATES = 16;
    private const int MINIMUM_NUMBER_OF_USER_DEFINED_STATES = NUMBER_OF_STATES - 4;
    private const int STATE_SIZE_IN_BYTES = sizeof(uint);
    private const int BLOCK_SIZE_IN_BYTES = STATE_SIZE_IN_BYTES * NUMBER_OF_STATES;

    private static readonly uint[] DEFAULT_STATES
        = new uint[] { 0x61707865U, 0x3320646EU, 0x79622D32U, 0x6B206574U };

    private readonly uint[] _states;

    public ChaCha20(params uint[] states)
    {
        if (states == null)
            throw new ArgumentNullException(nameof(states));

        if (states.Length == NUMBER_OF_STATES)
            _states = states;
        else if (states.Length == MINIMUM_NUMBER_OF_USER_DEFINED_STATES)
            _states = DEFAULT_STATES.Concat(states);
        else
            throw new ArgumentException("Invalid number of...");
    }
}

Just one constructor, easier to write, which you can call using an array (easier if initialization list is persisted somewhere) or with your previous syntax (see params).

Now if we apply the same concept everywhere you will see that your code is greatly reduced and simplified (I'd say also much faster than now).

Just to pick one example, this line:

State0.GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * 0)));

It is repeated 16 times (plus code duplication for little-endian/big-endian) but using an array is reduced to a simple for. Less space for mistakes and the same is true for every other function:

for (int i=0; i < NUMBER_OF_STATES; ++i)
    states[0].GetBytes(destination, (destinationOffset + (STATE_SIZE_IN_BYTES * i));

Is it bad (for performance) to have a loop? Compiler will determine if it's better to unroll the loop for you (after all the number of iterations is known at compile-time).


You're putting [MethodImpl(MethodImplOptions.AggressiveInlining)]. Don't. Compiler is usually much better than us to determine if a method should be inlined or not and which are the implication of that. Inlining a method call which contains a long loop (where you call other methods) is, for example, risky to be counterproductive. Or maybe not? Unless you perform serious benchmarking on different CPU architectures then it's a big guess. Let the compiler do his job.


This line:

d = (d ^= unchecked(a += b)).RotateLeft(16);

It's way too complex! It's doing too many things. Succinct code isn't a synonym of optimized code. Write it down and you will even see that you have a useless assignment in that expression (d ^=), hopefully compiler did elide it.

unchecked
{ 
    a += b;
}

d = (d ^ a).RotateLeft(16);

Is it that bad? Move it to a separate method. Compiler, again, will inline it for you. Well, after you finished translation to arrays then you won't probably have four of these calls because, you will have a loop (that the compiler is free to optimize as required).

\$\endgroup\$
  • \$\begingroup\$ One could've assumed performance is enough but I made a concentrated effort to test thoroughly. The compiler isn't nearly as good as you think it is as here and needs a bit of a nudge in order to "do the right thing." You might noticed that I'm only using MethodImplOptions.AggressiveInlining on the three static methods; this is was not on a whim as removing more than halves the performance of the Transform methods. We're lucky we have the appropriate tooling to confirm this: github.com/dotnet/BenchmarkDotNet. \$\endgroup\$ – Kittoes0124 Jul 25 '17 at 13:51
  • \$\begingroup\$ Totally agree with other concerns though. The way states are passed right now bothers me quite a bit and I've been working on a way to hide them behind a struct that accepts byte[] arrays. My latest attempt is here: github.com/ByteTerrace/ByteTerrace.CSharp.Crypto/blob/master/…. \$\endgroup\$ – Kittoes0124 Jul 25 '17 at 13:54
  • \$\begingroup\$ Hmmmmmm it's honestly still way too much code, IMO! I'm somehow interested, I'll try to compare few benchmarks! \$\endgroup\$ – Adriano Repetti Jul 25 '17 at 14:07
  • \$\begingroup\$ Aye, have tried to reduce it without negatively affecting things but haven't had much success. My first attempt at hoisting the state into a separate struct was actually a simultaneous conversion to arrays; the performance tanked. Entirely possible I messed something up by doing too much at once though so I'll be exploring the array idea again now that I have a working struct. Definitely welcome any ideas you might come up with, good luck. \$\endgroup\$ – Kittoes0124 Jul 25 '17 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.