Salsa20 Adventure...

37 views
Skip to first unread message

Chris M. Thomasson

unread,
Nov 14, 2021, 8:10:46 PM11/14/21
to
Well, I finally found some time to see if I can integrate Salsa20 into
my HMAC cipher. I just need to get on the same page. Is there a site
that happens to have a bunch of Salsa20 test vectors?


code:
______________
#include <stdio.h>
#include <stdint.h>



void ct_hex_printf(
FILE* fout,
unsigned char const* buf,
size_t buf_sz
) {
for (size_t i = 0; i < buf_sz; i++)
{
fprintf(fout, "%02x", buf[i]);
}
}

void ct_output_uint32(
FILE* fout,
uint32_t const* origin,
uint32_t size
) {
for (uint32_t i = 0; i < size; ++i)
{
fprintf(fout, "%u ", origin[i]);
}
}


// Salsa20, from the Wiki
// https://en.wikipedia.org/wiki/Salsa20
//___________________________________________________

#define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b))))

#define QR(a, b, c, d)( \
b ^= ROTL(a + d, 7), \
c ^= ROTL(b + a, 9), \
d ^= ROTL(c + b,13), \
a ^= ROTL(d + c,18))

#define ROUNDS 20


void salsa20_block(uint32_t out[16], uint32_t const in[16])
{
int i;
uint32_t x[16];

for (i = 0; i < 16; ++i)
x[i] = in[i];

// 10 loops × 2 rounds/loop = 20 rounds
for (i = 0; i < ROUNDS; i += 2) {
// Odd round
QR(x[0], x[4], x[8], x[12]); // column 1
QR(x[5], x[9], x[13], x[1]); // column 2
QR(x[10], x[14], x[2], x[6]); // column 3
QR(x[15], x[3], x[7], x[11]); // column 4
// Even round
QR(x[0], x[1], x[2], x[3]); // row 1
QR(x[5], x[6], x[7], x[4]); // row 2
QR(x[10], x[11], x[8], x[9]); // row 3
QR(x[15], x[12], x[13], x[14]); // row 4
}

for (i = 0; i < 16; ++i)
out[i] = x[i] + in[i];
}


int main(void)
{
printf(
"CT HMAC Cipher Testing 123, Salsa20 anyone? ;^)...\n"
"____________________________________________\n\n\n"
);
fflush(stdout);

{
uint32_t in[16] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13, 14, 15 };
uint32_t out[16] = { 0 };

ct_output_uint32(stdout, in, 16);
printf("\n\n");

salsa20_block(out, in);
ct_output_uint32(stdout, out, 16);
printf("\n\n");

salsa20_block(in, out);
ct_output_uint32(stdout, in, 16);
printf("\n\n");

salsa20_block(out, in);
ct_output_uint32(stdout, out, 16);
printf("\n\n");
}

printf(
"\n\n____________________________________________\n"
"Fin!\n"
);
fflush(stdout);

return 0;
}

______________



output:
______________


CT HMAC Cipher Testing 123, Salsa20 anyone? ;^)...
____________________________________________


0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

3785419744 100870658 516004132 2449453934 2198242101 2814406188
1974745191 3438825854 4129007648 2870708594 3969832950 1199978169
1952306861 2344514093 2714541023 1606880496

2942090003 400673375 3121015620 2872376170 1546450637 990720089
1869951638 3143164770 869781765 3008923581 3398832810 1823120209
463801211 3122388471 729501060 849445191

4173592898 2396994849 1771524128 4213406318 389233207 636291165
2150548507 4037387469 3024770654 692221288 3398289715 2437095621
2757032725 177481557 1965704476 2144468276



____________________________________________
Fin!


______________


Before I go any further, when you get some free time, can you please
verify that my output is correct! Thanks. I just need some test vectors.

Chris M. Thomasson

unread,
Nov 14, 2021, 9:44:03 PM11/14/21
to
On 11/14/2021 5:10 PM, Chris M. Thomasson wrote:
> Well, I finally found some time to see if I can integrate Salsa20 into
> my HMAC cipher. I just need to get on the same page. Is there a site
> that happens to have a bunch of Salsa20 test vectors?
>
>
> code:
> ______________
[...]
> Before I go any further, when you get some free time, can you please
> verify that my output is correct! Thanks. I just need some test vectors.

Disturbing output from 16 unsigned 32 bit integers as all zeros:

CT HMAC Cipher Testing 123, Salsa20 anyone? ;^)...
____________________________________________


0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0



____________________________________________
Fin!

Scary, in a sense. For some stupid reason I thought it would be like a
hash, say hash-512 with 16 zeros:

56d01c4d1a698e26ac99eefdd77b9e98f1b909b407282830e8dffc18fb99f2159a44a1059f08c53e9bba17bc7695f35c720a207643dc8a11f7f93e470936b0f3

Well, now that I think about it some more, I don't see any constants in
the logic. Humm...

Max

unread,
Nov 14, 2021, 10:12:46 PM11/14/21
to
There are lots of test vectors for ChaCha in RFC7539:
https://datatracker.ietf.org/doc/html/rfc7539

I don't know of any for Salsa. Maybe just take DJB's reference
implementation and create your own?
https://cr.yp.to/snuffle.html

Leo

unread,
Nov 15, 2021, 5:43:05 AM11/15/21
to
On Sun, 14 Nov 2021 18:43:56 -0800, Chris M. Thomasson wrote:

>
> Disturbing output from 16 unsigned 32 bit integers as all zeros:
>
> CT HMAC Cipher Testing 123, Salsa20 anyone? ;^)...
> ____________________________________________
>
>
> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>
> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>
> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>
> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>
>
>
> ____________________________________________
> Fin!
>
> Scary, in a sense.

This is expected. Both Salsa20 and ChaCha20 have an output of all
zeros if the input is all zeros.

When you use it as a compression function as in Rumba20, you need to
fill some of the 32-bit integers with constants. Similarly, if you are
using ChaCha20 or Salsa20 as stream ciphers, there are different
constants that you can use. In practice, it is very unlikely that you
will end up with an all-zero state.

> For some stupid reason I thought it would be like a hash, say
> hash-512 with 16 zeros:
>
>
56d01c4d1a698e26ac99eefdd77b9e98f1b909b407282830e8dffc18fb99f2159a44a1059f08c53e9bba17bc7695f35c720a207643dc8a11f7f93e470936b0f3

If you do anything on top of the Salsa20 core; like turning it into a
compression function, a sponge function, an MD hash or an HMAC, this
is indeed what happens.

> Well, now that I think about it some more, I don't see any constants
> in the logic. Humm...

The constants for hashing (and other fields for turning it into a
stream cipher) are added later. As long as you have a working (and
hopefully optimized) Salsa20 core, you can build on top of it to make
the other constructions.

--
Leo

Leo

unread,
Nov 15, 2021, 5:53:52 AM11/15/21
to
On Sun, 14 Nov 2021 17:10:39 -0800, Chris M. Thomasson wrote:

> Well, I finally found some time to see if I can integrate Salsa20
> into my HMAC cipher. I just need to get on the same page. Is there a
> site that happens to have a bunch of Salsa20 test vectors?

I'm sure there are other test vectors available, but this is the
output I get from a quick Python implementation.

Input (hex):
000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f

Output (hex):
3c561d323c15ba1eb897f3ebdb284b5dfbb93822038c6739d0e8b9efc8c801853c9f62090ad37bf7066293aae2e8a758a43a1fd5619c1e8929c9f40c819a44d4

> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
>
> 3785419744 100870658 516004132 2449453934 2198242101 2814406188
> 1974745191 3438825854 4129007648 2870708594 3969832950 1199978169
> 1952306861 2344514093 2714541023 1606880496
>
> 2942090003 400673375 3121015620 2872376170 1546450637 990720089
> 1869951638 3143164770 869781765 3008923581 3398832810 1823120209
> 463801211 3122388471 729501060 849445191
>
> 4173592898 2396994849 1771524128 4213406318 389233207 636291165
> 2150548507 4037387469 3024770654 692221288 3398289715 2437095621
> 2757032725 177481557 1965704476 2144468276
>
> Before I go any further, when you get some free time, can you please
> verify that my output is correct! Thanks. I just need some test vectors.

That looks correct to me. Below is the output I get when I run the
same input (0 to 15).

(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)

(3785419744, 100870658, 516004132, 2449453934, 2198242101, 2814406188,
1974745191, 3438825854, 4129007648, 2870708594, 3969832950,
1199978169, 1952306861, 2344514093, 2714541023, 1606880496)

(2942090003, 400673375, 3121015620, 2872376170, 1546450637, 990720089,
1869951638, 3143164770, 869781765, 3008923581, 3398832810, 1823120209,
463801211, 3122388471, 729501060, 849445191)

(4173592898, 2396994849, 1771524128, 4213406318, 389233207, 636291165,
2150548507, 4037387469, 3024770654, 692221288, 3398289715, 2437095621,
2757032725, 177481557, 1965704476, 2144468276)

--
Leo

Chris M. Thomasson

unread,
Nov 15, 2021, 4:38:47 PM11/15/21
to
On 11/15/2021 2:53 AM, Leo wrote:
> On Sun, 14 Nov 2021 17:10:39 -0800, Chris M. Thomasson wrote:
>
>> Well, I finally found some time to see if I can integrate Salsa20
>> into my HMAC cipher. I just need to get on the same page. Is there a
>> site that happens to have a bunch of Salsa20 test vectors?
>
> I'm sure there are other test vectors available, but this is the
> output I get from a quick Python implementation.
>
> Input (hex):
> 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f
>
> Output (hex):
> 3c561d323c15ba1eb897f3ebdb284b5dfbb93822038c6739d0e8b9efc8c801853c9f62090ad37bf7066293aae2e8a758a43a1fd5619c1e8929c9f40c819a44d4

Please excuse the most likely stupid question... So, I have to construct
16 32-bit words from the 64 raw bytes in order for Salsa20 to work on
it, right? This makes me think of endian'ness. I guess I could say,
well, littleendian is it, period. And work with that. littleendian, and
I am sticking to it. ;^)


>> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
>>
>> 3785419744 100870658 516004132 2449453934 2198242101 2814406188
>> 1974745191 3438825854 4129007648 2870708594 3969832950 1199978169
>> 1952306861 2344514093 2714541023 1606880496
>>
>> 2942090003 400673375 3121015620 2872376170 1546450637 990720089
>> 1869951638 3143164770 869781765 3008923581 3398832810 1823120209
>> 463801211 3122388471 729501060 849445191
>>
>> 4173592898 2396994849 1771524128 4213406318 389233207 636291165
>> 2150548507 4037387469 3024770654 692221288 3398289715 2437095621
>> 2757032725 177481557 1965704476 2144468276
>>
>> Before I go any further, when you get some free time, can you please
>> verify that my output is correct! Thanks. I just need some test vectors.
>
> That looks correct to me. Below is the output I get when I run the
> same input (0 to 15).

Thanks!

Chris M. Thomasson

unread,
Nov 15, 2021, 6:54:07 PM11/15/21
to
On 11/15/2021 2:53 AM, Leo wrote:
> On Sun, 14 Nov 2021 17:10:39 -0800, Chris M. Thomasson wrote:
>
>> Well, I finally found some time to see if I can integrate Salsa20
>> into my HMAC cipher. I just need to get on the same page. Is there a
>> site that happens to have a bunch of Salsa20 test vectors?
>
> I'm sure there are other test vectors available, but this is the
> output I get from a quick Python implementation.
>
> Input (hex):
> 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f
>
> Output (hex):
> 3c561d323c15ba1eb897f3ebdb284b5dfbb93822038c6739d0e8b9efc8c801853c9f62090ad37bf7066293aae2e8a758a43a1fd5619c1e8929c9f40c819a44d4
[...]

Fwiw, I just quickly and crudely coded up a little converter. For your
input hex, I am getting:
________________________________
000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f

00010203 = (0, 1, 2, 3) = 66051
04050607 = (4, 5, 6, 7) = 67438087
08090a0b = (8, 9, 10, 11) = 134810123
0c0d0e0f = (12, 13, 14, 15) = 202182159
10111213 = (16, 17, 18, 19) = 269554195
14151617 = (20, 21, 22, 23) = 336926231
18191a1b = (24, 25, 26, 27) = 404298267
1c1d1e1f = (28, 29, 30, 31) = 471670303
20212223 = (32, 33, 34, 35) = 539042339
24252627 = (36, 37, 38, 39) = 606414375
28292a2b = (40, 41, 42, 43) = 673786411
2c2d2e2f = (44, 45, 46, 47) = 741158447
30313233 = (48, 49, 50, 51) = 808530483
34353637 = (52, 53, 54, 55) = 875902519
38393a3b = (56, 57, 58, 59) = 943274555
3c3d3e3f = (60, 61, 62, 63) = 1010646591
________________________________


I just need to code up the inverse. Should have some more time tonight.
Btw, do my numbers look okay to you? Once finished, I should be able to
produce your output hex.

Thanks a million Leo! :^)

Leo

unread,
Nov 15, 2021, 7:15:24 PM11/15/21
to
> Fwiw, I just quickly and crudely coded up a little converter. I just
> need to code up the inverse. Should have some more time tonight.
> Btw, do my numbers look okay to you?

The numbers in the middle (0, 1, 2, 3 etc.) are correct. This is how I
constructed the input array.

I think your endianness might be flipped. When I decode hex 00010203
as a little endian U32, I get 50462976. Likewise, encoding 50462976 as
a little endian U32 gives me 00010203.

If I do it with big endian, I get your result (66051).

> Once finished, I should be able to produce your output hex. Thanks a
> million Leo! :^)

Great news, from there it's smooth sailing. Even if you don't use it
for anything else, Salsa20 is a good mixer to have. A small
self-contained C function that turns a u32[64] into another u32[64]
comes in handy for a lot of projects.

--
Leo

Chris M. Thomasson

unread,
Nov 15, 2021, 7:50:50 PM11/15/21
to
On 11/15/2021 4:15 PM, Leo wrote:
>> Fwiw, I just quickly and crudely coded up a little converter. I just
>> need to code up the inverse. Should have some more time tonight.
>> Btw, do my numbers look okay to you?
>
> The numbers in the middle (0, 1, 2, 3 etc.) are correct. This is how I
> constructed the input array.
>
> I think your endianness might be flipped. When I decode hex 00010203
> as a little endian U32, I get 50462976. Likewise, encoding 50462976 as
> a little endian U32 gives me 00010203.
>
> If I do it with big endian, I get your result (66051).

Ohhhh... Ouch! Well, does this match your numbers Leo:

00010203 = (0, 1, 2, 3) = 50462976
04050607 = (4, 5, 6, 7) = 117835012
08090a0b = (8, 9, 10, 11) = 185207048
0c0d0e0f = (12, 13, 14, 15) = 252579084
10111213 = (16, 17, 18, 19) = 319951120
14151617 = (20, 21, 22, 23) = 387323156
18191a1b = (24, 25, 26, 27) = 454695192
1c1d1e1f = (28, 29, 30, 31) = 522067228
20212223 = (32, 33, 34, 35) = 589439264
24252627 = (36, 37, 38, 39) = 656811300
28292a2b = (40, 41, 42, 43) = 724183336
2c2d2e2f = (44, 45, 46, 47) = 791555372
30313233 = (48, 49, 50, 51) = 858927408
34353637 = (52, 53, 54, 55) = 926299444
38393a3b = (56, 57, 58, 59) = 993671480
3c3d3e3f = (60, 61, 62, 63) = 1061043516

?

I hope it does! The first number is encouraging. Crossing fingers! ;^)

>
>> Once finished, I should be able to produce your output hex. Thanks a
>> million Leo! :^)
>
> Great news, from there it's smooth sailing. Even if you don't use it
> for anything else, Salsa20 is a good mixer to have. A small
> self-contained C function that turns a u32[64] into another u32[64]
> comes in handy for a lot of projects.
>

Indeed. The end of this "adventure" is to finally create a Salsa20-HMAC
that can be simply "plugged" into my HMAC cipher. Just make it adhere to
the API, and my HMAC cipher should be able to use it, out of the box.

Thanks for your patience and help Sir! :^)

Chris M. Thomasson

unread,
Nov 16, 2021, 4:03:54 PM11/16/21
to
On 11/15/2021 2:53 AM, Leo wrote:
> On Sun, 14 Nov 2021 17:10:39 -0800, Chris M. Thomasson wrote:
>
>> Well, I finally found some time to see if I can integrate Salsa20
>> into my HMAC cipher. I just need to get on the same page. Is there a
>> site that happens to have a bunch of Salsa20 test vectors?
>
> I'm sure there are other test vectors available, but this is the
> output I get from a quick Python implementation.
>
> Input (hex):
> 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f
>
> Output (hex):
> 3c561d323c15ba1eb897f3ebdb284b5dfbb93822038c6739d0e8b9efc8c801853c9f62090ad37bf7066293aae2e8a758a43a1fd5619c1e8929c9f40c819a44d4
[...]

Okay, I am able to reproduce your result Leo! Nice.
_____________________________________
000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f

00010203 = (0, 1, 2, 3) = 50462976 = 00010203
04050607 = (4, 5, 6, 7) = 117835012 = 04050607
08090a0b = (8, 9, 10, 11) = 185207048 = 08090A0B
0c0d0e0f = (12, 13, 14, 15) = 252579084 = 0C0D0E0F
10111213 = (16, 17, 18, 19) = 319951120 = 10111213
14151617 = (20, 21, 22, 23) = 387323156 = 14151617
18191a1b = (24, 25, 26, 27) = 454695192 = 18191A1B
1c1d1e1f = (28, 29, 30, 31) = 522067228 = 1C1D1E1F
20212223 = (32, 33, 34, 35) = 589439264 = 20212223
24252627 = (36, 37, 38, 39) = 656811300 = 24252627
28292a2b = (40, 41, 42, 43) = 724183336 = 28292A2B
2c2d2e2f = (44, 45, 46, 47) = 791555372 = 2C2D2E2F
30313233 = (48, 49, 50, 51) = 858927408 = 30313233
34353637 = (52, 53, 54, 55) = 926299444 = 34353637
38393a3b = (56, 57, 58, 59) = 993671480 = 38393A3B
3c3d3e3f = (60, 61, 62, 63) = 1061043516 = 3C3D3E3F

3C561D323C15BA1EB897F3EBDB284B5DFBB93822038C6739D0E8B9EFC8C801853C9F62090AD37BF7066293AAE2E8A758A43A1FD5619C1E8929C9F40C819A44D4
_____________________________________



Can you check the following input on your end?

Input (hex):
ffffffff424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242

Output (hex):
975AFDE0445EAF7F549FCE1F83905B220D62B1E859A1618A8B09612A420D188AA54B04290FE50ABA3DDE7A01E3479A078B30646CFA832CE53583722104EB2E23


Thanks.

Leo

unread,
Nov 17, 2021, 5:00:26 PM11/17/21
to
> Can you check the following input on your end?
>
> Input (hex):
>
ffffffff424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242
>
> Output (hex):
>
975AFDE0445EAF7F549FCE1F83905B220D62B1E859A1618A8B09612A420D188AA54B04290FE50ABA3DDE7A01E3479A078B30646CFA832CE53583722104EB2E23
>
>
> Thanks.

Hey Chris,

I can confirm that the output I get from your input vector is

975afde0445eaf7f549fce1f83905b220d62b1e859a1618a8b09612a420d188aa54b04290fe50aba3dde7a01e3479a078b30646cfa832ce53583722104eb2e23

It seems to be matching.

--
Leo

Chris M. Thomasson

unread,
Nov 18, 2021, 8:25:19 PM11/18/21
to
Thank you for testing it out. Afaict, we are building some test vectors
here! Now... I need to build a hash out of it that can handle arbitrary
data. Passing in 23841 bytes, gives me a single 512 byte hash. Passing
in a single byte, say (0x00), gives me a 512 byte hash. Trying to avoid
all hashbytes zero, for some reason.

I can see how to create a PRNG out of it now, but I really need to build
an HMAC out of it.

Leo

unread,
Nov 19, 2021, 7:30:14 AM11/19/21
to
On Thu, 18 Nov 2021 17:25:12 -0800, Chris M. Thomasson wrote:

> Thank you for testing it out. Afaict, we are building some test vectors
> here! Now... I need to build a hash out of it that can handle arbitrary
> data. Passing in 23841 bytes, gives me a single 512 byte hash. Passing
> in a single byte, say (0x00), gives me a 512 byte hash. Trying to avoid
> all hashbytes zero, for some reason.
>
> I can see how to create a PRNG out of it now, but I really need to build
> an HMAC out of it.

What you have now is the Salsa20 core, which maps 512 bits to 512 bits. I
can
see two ways to use this.

The first one is to use it as a sponge function. Start with an initial
block,
absorb the message into your state one byte at a time, and then squeeze
as many
bytes as you want as your hash output. I wrote about this before [1] but
I used
MD5 instead of Salsa20.

The second way is to turn this into a compression function (like Rumba20),
and
then turn that into an MD hash, and then turn that into an HMAC. I also
wrote
about this [2], which is what I believe started the discussions about
Salsa20 in
the first place.

The article about the sponge function has some mistakes (like calling CTR
mode a
block cipher), but it should give you some ideas.

[1]: https://www.gkbrk.com/2021/03/md5-sponge/
[2]: https://www.gkbrk.com/2021/10/rumba20-compression-function/

--
Leo

Leo

unread,
Nov 19, 2021, 7:33:17 AM11/19/21
to
Whoops, looks like I messed up the wrapping and used 80 characters
instead of 70.

Should configure Emacs to use 70 by default on Usenet.

--
Leo

Chris M. Thomasson

unread,
Nov 20, 2021, 3:36:26 PM11/20/21
to
Perfect. Complete with test vectors... I have an idea for a sponge like
function. Not sure if its going to work, but it might. Before I do that,
let me try to reproduce some of your test vectors. Humm... Need to think
here... Focusing on [2] now.
Reply all
Reply to author
Forward
0 new messages