Salsa20 test vectors

[Cristiano]

I downloaded the Salsa20 source file:
http://cr.yp.to/snuffle/ecrypt.c
the related include files and test vectors:

http://www.ecrypt.eu.org/stream/svn/viewcvs.cgi/*checkout*/ecrypt/trunk/submissions/salsa20/full/verified.test-vectors?rev=210

I renamed the source file in "Salsa20.cpp".

I tried to compile the code with the VS2008 C++ EE, but I get:
error C2117: 'sigma' : array bounds overflow
error C2117: 'tau' : array bounds overflow

I had to change the lines:
static const char sigma[16] = "expand 32-byte k";
static const char tau[16] = "expand 16-byte k";
in:
static const char sigma[] = "expand 32-byte k";
static const char tau[] = "expand 16-byte k";

Then I wrote this code to compare the output of my program with the test
vectors:

const int kbits= 128, ivbits= 64;
ECRYPT_ctx ctx; u8 key[kbits/8], iv[ivbits/8];
for(int i= 0; i < kbits/8; i++) key[i]= 0;
for(int i= 0; i < ivbits/8; i++) iv[i]= 0;
ECRYPT_keysetup(&ctx, key, kbits, ivbits);
ECRYPT_ivsetup(&ctx, iv);

for(int i= 0; i < 512; i++) {
u8 x= 0; ECRYPT_encrypt_bytes(&ctx, &x, &x, 1);
printf("%02X", x);
}

Only the first x is good; for example, with key= 000... and iv= 000... I
get: 65D0D175..., while the result should be: 6513ADAE...

Where is the problem?

Thanks
Cristiano

[Paul Rubin]

Cristiano <cris...@NSgmail.com> writes:
> static const char sigma[16] = "expand 32-byte k";
> static const char tau[16] = "expand 16-byte k";

This makes a 32-byte block in memory whose contents are
|expand 32-byte kexpand 16-byte k|
where the vertical bars delimit block.

If you look at the ECRYPT_keysetup routine, it relies on the 32-byte
block being contiguous: there is no gap between sigma and tau.

> static const char sigma[] = "expand 32-byte k";
> static const char tau[] = "expand 16-byte k";

I think this instead makes a 34-byte block where there is a null byte
after the first "k", separating the expected contents of sigma and tau.

> Where is the problem?

ECRYPT_keysetup is not getting the stuff it is supposed to.

I'd have to say the code is a bit ugly, and it would have been better to
initialize sigma and tau in a struct or as a single block.

[Cristiano]

On 05/08/2012 18:50, Paul Rubin wrote:
> Cristiano <cris...@NSgmail.com> writes:
>> static const char sigma[16] = "expand 32-byte k";
>> static const char tau[16] = "expand 16-byte k";
>
> This makes a 32-byte block in memory whose contents are
> |expand 32-byte kexpand 16-byte k|
> where the vertical bars delimit block.
>
> If you look at the ECRYPT_keysetup routine, it relies on the 32-byte
> block being contiguous: there is no gap between sigma and tau.

I don't see that. I see that ECRYPT_keysetup uses 'constants = sigma' or
'constants = tau' and 'constants + 0' ... 'constants + 12'. I don't
think that sigma and tau need to be contiguous.
Anyway, I changed the lines in:
static const char sigma[] = "expand 32-byte kexpand 16-byte k";
static const char *tau= sigma+16;
but the result is exactly the same.

Cristiano

[Paul Rubin]

Cristiano <cris...@NSgmail.com> writes:
> Anyway, I changed the lines in:
> static const char sigma[] = "expand 32-byte kexpand 16-byte k";
> static const char *tau= sigma+16;
> but the result is exactly the same.

How about compiling the original version (i.e. with a C compiler rather
than C++) and seeing if that gives the right results. If yes, trace
through both and see where stuff starts differing. If both give wrong
results, post again and I'll try on my system.

[Cristiano]

On 05/08/2012 23:45, Paul Rubin wrote:
> Cristiano <cris...@NSgmail.com> writes:
>> Anyway, I changed the lines in:
>> static const char sigma[] = "expand 32-byte kexpand 16-byte k";
>> static const char *tau= sigma+16;
>> but the result is exactly the same.
>
> How about compiling the original version (i.e. with a C compiler rather
> than C++) and seeing if that gives the right results. If yes, trace
> through both and see where stuff starts differing.

I slightly changed the test code (to use the C) and I get the same wrong
result (I still used VS 2008, but with C source code).

I'll try to compile the program under Linux with GCC...

> If both give wrong results, post again and I'll try on my system.

Thank you.
Cristiano

[Paul Rubin]

Cristiano <cris...@NSgmail.com> writes:
> I'll try to compile the program under Linux with GCC...

In case it's of any use for this, I wrote a simplified implementation of
salsa20 (i.e. same specification but more straightforward, non-optimized
code) a while back:

http://nightsong.com/phr/crypto/salsa20.c

[Cristiano]

On 06/08/2012 0:26, Paul Rubin wrote:
> Cristiano <cris...@NSgmail.com> writes:
>> I'll try to compile the program under Linux with GCC...

Mmmm... Also in this case I always get the wrong result.

Is there any working implementation with an example of usage?

> In case it's of any use for this, I wrote a simplified implementation of
> salsa20 (i.e. same specification but more straightforward, non-optimized
> code) a while back:
>
> http://nightsong.com/phr/crypto/salsa20.c

I get "success", but I don't understand were the key and the IV are.

Cristiano

[Maaartin G]

On Monday, August 6, 2012 12:58:04 AM UTC+2, Cristiano wrote:
> I get "success", but I don't understand were the key and the IV are.

Well hidden. The array test_in contains it all, intermixed as described in
http://cr.yp.to/snuffle/salsafamily-20071225.pdf
on page 9. I've seen a better description but can't find it anymore.

[Cristiano]

Thank you, but I hoped to find a straightforward ready-to-use
implementation.

I'm a bit unlucky with eStream: tried HC-128, got a memory corruption
(?); tried salsa, got that strange output. :-(

Cristiano

[Maaartin G]

On Monday, August 6, 2012 1:51:23 AM UTC+2, Cristiano wrote:
> I'm a bit unlucky with eStream: tried HC-128, got a memory corruption
> (?); tried salsa, got that strange output. :-(

Doesn't VS use 16-bit char or something like this (even RTL wouldn't surprise me)
? Did you try gcc?

I tried to download things from DJB's page, but somehow it didn't work. This link worked for me with gcc
http://www.ecrypt.eu.org/stream/svn/viewcvs.cgi/ecrypt.tar.gz?view=tar

I changed dir into .../ecrypt/trunk/submissions/salsa20/full/ref, downloaded the test vectors into expected.txt, ran

make && ./ecrypt-test -v > actual.txt && diff actual.txt expected.txt && echo OK

and got OK.

[Noob]

[ Adding comp.lang.c so they can correct me ]

Paul Rubin wrote:

> Cristiano wrote:
>
>> static const char sigma[16] = "expand 32-byte k";
>> static const char tau[16] = "expand 16-byte k";
>
> This makes a 32-byte block in memory whose contents are
> |expand 32-byte kexpand 16-byte k|
> where the vertical bars delimit block.

This is incorrect. The compiler has no obligation to store
sigma and tau contiguously.

In other words, assert(tau == sigma + sizeof sigma) may fail.

[Mark Bluemel]

Indeed.

[Cristiano]

On 06/08/2012 2:57, Maaartin G wrote:
> On Monday, August 6, 2012 1:51:23 AM UTC+2, Cristiano wrote:
>> I'm a bit unlucky with eStream: tried HC-128, got a memory corruption
>> (?); tried salsa, got that strange output. :-(
>
> Doesn't VS use 16-bit char or something like this (even RTL wouldn't surprise me)?

You can use unicode chars or "normal" 8-bit chars; I use normal chars.

> Did you try gcc?

Yes, under 32-bit Linux (Ubuntu distro); got the same wrong result.

To get the right result I need to do a single call to
ECRYPT_encrypt_bytes() with a 512-byte plaintext.
If I do multiple calls, the "internal state" seems to change; sounds
like a block cipher... :-)

Cristiano

[Cristiano]

On 06/08/2012 12:28, Cristiano wrote:
> To get the right result I need to do a single call to
> ECRYPT_encrypt_bytes() with a 512-byte plaintext.
> If I do multiple calls, the "internal state" seems to change; sounds
> like a block cipher... :-)

A more efficient version would be:

u8 output[64]; int idx= 63;

for(int i= 0; i < 512; i++) {

if(++idx == 64) {
idx= 0; salsa20_wordtobyte(output, ctx->input);
ctx->input[8] = PLUSONE(ctx->input[8]);
if(!ctx->input[8]) ctx->input[9] = PLUSONE(ctx->input[9]);
}
printf("%02X", output[idx]);
}

In the normal usage you just need to write:
for(int i= 0; i < bytes_to_cipher; i++) {
and the output would be:
ciphered_byte[i]= plaintext[i] ^ output[idx]

Cristiano

[Paul Rubin]

Noob <ro...@127.0.0.1> writes:
>> This makes a 32-byte block in memory whose contents are
>> |expand 32-byte kexpand 16-byte k|
>> where the vertical bars delimit block.
> This is incorrect. The compiler has no obligation to store
> sigma and tau contiguously.

You are right, and of course DJB would not have made such a silly error.
It looks like I read the keysetup function incorrectly for some reason.
It actually chooses between sigma and tau based on the key size, and
doesn't use both or rely on them being contiguous.

So I guess we still don't know why Cristiano's tests are getting wrong
results. I may spend a little time investigating further later, but
have other things going on right now.

[Cristiano]

On 06/08/2012 22:27, Paul Rubin wrote:

> So I guess we still don't know why Cristiano's tests are getting wrong
> results.

But I posted 10 hours ago... I said: "To get the right result I need to

do a single call to ECRYPT_encrypt_bytes() with a 512-byte plaintext."

> I may spend a little time investigating further later, but
> have other things going on right now.

Thank you, but the problem is solved. :-)

Cristiano

[Keith Thompson]

Cristiano <cris...@NSgmail.com> writes:
> On 06/08/2012 22:27, Paul Rubin wrote:
>> So I guess we still don't know why Cristiano's tests are getting wrong
>> results.
>
> But I posted 10 hours ago... I said: "To get the right result I need to
> do a single call to ECRYPT_encrypt_bytes() with a 512-byte plaintext."

You only posted that to sci.crypt.

Your original article was posted only to sci.crypt. "Noob"
cross-posted a followup to sci.crypt and comp.lang.c, which resulted
in comp.lang.c readers seeing only part of the thread (and probably
not being aware of it).

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Paul Rubin]

Cristiano <cris...@NSgmail.com> writes:
> Thank you, but the problem is solved. :-)

Oh good, I see it now. Thanks for the update.

[Maaartin G]

On Monday, August 6, 2012 10:27:37 PM UTC+2, Paul Rubin wrote:
> You are right, and of course DJB would not have made such a silly error.
> It looks like I read the keysetup function incorrectly for some reason.
> It actually chooses between sigma and tau based on the key size, and
> doesn't use both or rely on them being contiguous.

Yes, DJB writes about it:

A 128-bit key is repeated to form a 256-bit key; and “32” is replaced with “16” in the Salsa20 diagonal constants, to eliminate any concerns regarding overlapping keys. An 80-bit key is zero-padded to form a 128-bit key; and “16” is replaced with “10”...

[io_x]

"Noob" <ro...@127.0.0.1> ha scritto nel messaggio
news:jvo0bp$tbo$1...@dont-email.me...

>[ Adding comp.lang.c so they can correct me ]
>
> Paul Rubin wrote:
>
>> Cristiano wrote:
>>
>>> static const char sigma[16] = "expand 32-byte k";
>>> static const char tau[16] = "expand 16-byte k";

because the string is 16 char + \0 it has to be >=17

it has to be
static const char sigma[17] = "expand 32-byte k";

or if that number scare you
static const char sigma[18] = "expand 32-byte k";

>> This makes a 32-byte block in memory whose contents are
>> |expand 32-byte kexpand 16-byte k|
>> where the vertical bars delimit block.
>
> This is incorrect. The compiler has no obligation to store
> sigma and tau contiguously.
>
> In other words, assert(tau == sigma + sizeof sigma) may fail.

if you make wrong 1 char the size of the string
the compiler can do what it want better...

[Barry Schwarz]

On Tue, 7 Aug 2012 10:22:30 +0200, "io_x" <a...@b.c.invalid> wrote:

>
>"Noob" <ro...@127.0.0.1> ha scritto nel messaggio
>news:jvo0bp$tbo$1...@dont-email.me...
>>[ Adding comp.lang.c so they can correct me ]
>>
>> Paul Rubin wrote:
>>
>>> Cristiano wrote:
>>>
>>>> static const char sigma[16] = "expand 32-byte k";
>>>> static const char tau[16] = "expand 16-byte k";
>
>because the string is 16 char + \0 it has to be >=17

The two definitions above define character arrays that do not contain
strings. Unless they need to be strings, there is nothing wrong with
the definitions. They only need to have 17 elements if they are
indeed strings.

--
Remove del for email

[Nick Keighley]

On Aug 7, 9:22 am, "io_x" <a...@b.c.invalid> wrote:
> "Noob" <r...@127.0.0.1> ha scritto nel messaggionews:jvo0bp$tbo$1...@dont-email.me...

> > Paul Rubin wrote:
> >> Cristiano wrote:


> >>>    static const char sigma[16] = "expand 32-byte k";
> >>>    static const char tau[16] = "expand 16-byte k";
>
> because the string is 16 char + \0 it has to be >=17
>
> it has to be
> static const char sigma[17] = "expand 32-byte k";

no. The compiler simply omits the '\0' if the array size is
the same as the number of characters. As Barry remarks it isn't
a string tho'

[C++ behaves differently]

> or if that number scare you
> static const char sigma[18] = "expand 32-byte k";

? why would 17 scare me? Do you have a phobia about prime numbers?

<snip>

[io_x]

"Barry Schwarz" <schw...@dqel.com> ha scritto nel messaggio
news:jl3328pq6a6f3o24u...@4ax.com...

thank you

[io_x]

"Nick Keighley" <nick_keigh...@hotmail.com> ha scritto nel messaggio
news:eb1539c1-32a0-44af...@n13g2000vby.googlegroups.com...

#no i have a 'phobia' about 17 only
#thank you