Simon Josefsson <[email protected]> writes:
> Hi! Please find attached a port of DJB's public domain code for Salsa20
> to nettle. The patch is not meant to be applied as-is but to start a
> discussion.
I'm not familiar with this cipher... Could you explain briefly why one
may want to use it?
> While writing this I noticed a sub-optimal design of Nettle, in that it
> overloads the meaning of struct nettle_cipher->block_size as a flag of
> whether the cipher is a stream cipher or not. Before arcfour was the
> only stream cipher in nettle, and using block_size=0 to signal that it
> is a stream cipher worked fine. However, Salsa20 has a block size of 8
> bytes.
If Salsa20 doesn't fit in the nettle_cipher abstraction, then I think we
should start by implementing Salsa20 *without* trying to get it to fit
there. To me, a "stream cipher" with a block size and iv seems a bit
like a contradiction.
In general, I don't think it makes much sense to include algorithms
which behave very differently under the "nettle_cipher" umbrella, since
the point of that abstraction is to collect algorithms which are easily
exchangable. Code accepting a nettle_cipher are not expected to check
flags or behave fundamentally different for different algorithms.
Including the arcfour stream cipher there may well be a mistake. One
annoying problem with the current design is that for block ciphers, the
ctx argument of the encrypt and decrypt functions naturally is const,
but due arcfour being fittted in the same nettle_cipher abstraction, the
function typedef nettle_crypt_func can't use a const ctx.
Anyway, I'd prefer to treat redesign in that area as an independent
problem from adding support for Salsa20.
Then there's also the tentative (nettle-internal.h) nettle_aead
abstraction. Salsa20 could perhaps fit there, if we allow algorithms
with no authentication (NULL digest function pointer).
> What do you think? I'd be happy to propose a patch to implement 2) and
> then a follow-on patch to add support for Salsa20.
I'd prefer the opposite order...
Some quick comments on the code and algorithm below. This is the first
I hear about it, so I may well be misunderstanding how it is supposed to
work.
> --- /dev/null
> +++ b/salsa20.c
> +#define ROTL32(x,n) ((((x))<<(n)) | (((x))>>(32-(n))))
There are several different variants of that macro. It would be nice
with a unified one in macros.h.
> +#define SWAP32(v) \
> + ((ROTL32(v, 8) & 0x00FF00FFUL) | \
> + (ROTL32(v, 24) & 0xFF00FF00UL))
> +
> +#ifdef WORDS_BIGENDIAN
> +#define U32TO32_LITTLE(v) SWAP32(v)
> +#else
> +#define U32TO32_LITTLE(v) (v)
> +#endif
> +
> +#define U8TO32_LITTLE(p) U32TO32_LITTLE(((uint32_t*)(p))[0])
> +#define U32TO8_LITTLE(p, v) (((uint32_t*)(p))[0] = U32TO32_LITTLE(v))
That's a clever byte swapping trick (at least if a true rot instruction
is available). In Nettle conversion between bytes and integers are
usually done with READ_UINT32, LE_READ_UINT32 and friends. It's usually
not very performance critical, and it deals naturally with any
alignment. I suspect U8TO32_LITTLE above breaks if the input is
unaligned but the architecture doesn't allow unaligned word reads.
> +/*
> +salsa20-ref.c version 20051118
> +D. J. Bernstein
> +Public domain.
> +*/
Shouldn't that be moved up closer to the (C) header?
> +#define ROTATE(v,c) (ROTL32(v,c))
> +#define XOR(v,w) ((v) ^ (w))
> +#define PLUS(v,w) ((v) + (w))
> +#define PLUSONE(v) (PLUS((v),1))
I'm not sure these macros improve readability...
> +static void salsa20_wordtobyte(uint8_t output[64],const uint32_t input[16])
Despite the name, this is the main encryption function. Or rather, a
(hopefully) one-way function? "input" is really the context struct,
which contains some mix of the key and the iv?
> + x[ 4] = XOR(x[ 4],ROTATE(PLUS(x[ 0],x[12]), 7));
And what's wrong with writing that as
x[ 4] ^= ROTATE(x[ 0] + x[12], 7)
> +void
> +salsa20_set_key(struct salsa20_ctx *ctx,
> + unsigned length, const uint8_t *key)
> +{
Ok, this initializes the input arrray at indices 0-5, and 10-15.
> +void
> +salsa20_set_iv(struct salsa20_ctx *ctx, unsigned length, const uint8_t *iv)
> +{
> + assert (length == SALSA20_IV_SIZE);
And this initializes indices 6-9. I'd remove the length argument, if
only one value is allowed anyway.
> +void
> +salsa20_crypt(struct salsa20_ctx *ctx,
> + unsigned length,
> + uint8_t *c,
> + const uint8_t *m)
> +{
> + uint8_t output[64];
> + unsigned i;
> +
> + if (!length) return;
> + for (;;) {
> + salsa20_wordtobyte(output,ctx->input);
That's applying a oneway function to the input,
> + ctx->input[8] = PLUSONE(ctx->input[8]);
> + if (!ctx->input[8]) {
> + ctx->input[9] = PLUSONE(ctx->input[9]);
> + /* stopping at 2^70 length per nonce is user's responsibility */
> + }
followed by an increment of the iv, where the second half appearantly is
used as a counter.
> + if (length <= 64) {
> + for (i = 0;i < length;++i) c[i] = m[i] ^ output[i];
> + return;
> + }
> + for (i = 0;i < 64;++i) c[i] = m[i] ^ output[i];
Followed by xoring the generated key stream to get the ciphertext.
Do I understand it correctly that there's nothing really non-linear
anywhere in this cipher? Only a mix of + and ^ which both are linear,
but over different rings. So the security aginst a known plaintext
attack would rest on the carry propagation, together with the large
state space of 512 bits (448 bits of expanded key material, and 64 bits
counter).
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
