X25519 tests fail with Windows MSVC at /O2

[fscoto]

This is like, worst possible news, but... Apparently nobody's been testing Windows for a while and 3.1.0 fails tests for X25519 (but not EdDSA!) and some related functions. This issue manifests only at /O2, but not /O1.

My crude test methodology missing make(1) goes like this:

monocypher-3.1.0>cl /O2 /Isrc /Isrc/optional src\monocypher.c src\optional\monocypher-ed25519.c tests\test.c tests\utils.c
monocypher-3.1.0>monocypher.exe

Giving this output:

monocypher-3.1.0>cl /O2 /Isrc /Isrc/optional src\monocypher.c src\optional\monocypher-ed25519.c tests\test.c tests\utils.c
Microsoft (R) C/C++ Optimizing Compiler Version 19.25.28611 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

monocypher.c
monocypher-ed25519.c
test.c
utils.c
Generating Code...
Microsoft (R) Incremental Linker Version 14.25.28611.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:monocypher.exe
monocypher.obj
monocypher-ed25519.obj
test.obj
utils.obj

monocypher-3.1.0>monocypher.exe

Random seed: 12345

Test against vectors
--------------------
OK  136 tests: chacha20
OK  128 tests: ietf_chacha20
OK   50 tests: hchacha20
OK  131 tests: xchacha20
OK   48 tests: poly1305
OK  320 tests: aead_ietf
OK  383 tests: blake2b
OK  256 tests: sha512
OK  343 tests: hmac_sha512
OK   14 tests: argon2i
FAILED  623 tests: x25519
FAILED   51 tests: x25519_pk
FAILED    5 tests: key_exchange
OK  256 tests: edDSA
OK  257 tests: edDSA_pk
OK  256 tests: ed_25519
OK  257 tests: ed_25519_pk
OK  133 tests: ed_25519_check
FAILED: x25519 1
FAILED: x25519 1K
OK   78 tests: elligator_dir
OK   72 tests: elligator_inv

Property based tests
--------------------
OK: crypto_verify16
OK: crypto_verify32
OK: crypto_verify64
OK: Chacha20 (ctr)
OK: Chacha20 (nullptr == zeroes)
OK: Chacha20 (output == input)
OK: HChacha20 (overlap)
OK: Poly1305 (incremental)
OK: Poly1305 (overlapping i/o)
OK: Blake2b (incremental)
OK: Blake2b (overlapping i/o)
OK: Sha512 (incremental)
OK: Sha512 (overlapping i/o)
OK: HMAC SHA-512 (incremental)
OK: HMAC SHA-512 (overlapping i/o)
OK: Argon2i (easy interface)
OK: Argon2i (overlapping i/o)
OK: x25519 (overlapping i/o)
OK: key_exchange (overlapping i/o)
OK: EdDSA (roundtrip)
OK: EdDSA (random)
OK: EdDSA (overlap)
OK: EdDSA (incremental)
OK: aead (roundtrip)
OK: elligator direct (msb)
OK: elligator direct (overlapping i/o)
OK: elligator inverse (overlapping i/o)
FAILED: elligator x25519
FAILED: elligator key pair
OK: elligator key pair (overlapping i/o)
FAILED: x25519_inverse
OK: x25519 inverse (overlapping i/o)
FAILED: from_eddsa
FAILED: from_ed25519

SOME TESTS FAILED

---

I'll try to hunt down what the cause might be, but this is important enough that I wanted an issue up now and figure out the details later.

[tankf33der]

MSVC is not free and requires subscription, right? What about Intel compiler, XL C from IBM?

Monocypher tested on big number of platforms and compilers, even IRIX works and latest tcc from git and gcc 3.x.x. If so i would like to test, asap, on Sun Oracle studio version i have, worked several years ago.

Since Monocypher passed TIS, compcert and SANs I am calm. Wellcome to hell of compilers compatibility.

[fscoto]

MSVC is free with the Community edition of Visual Studio Community. VS Community will ask you to register (i.e. give up personal information) after 30 days though; the for-profit editions won't do that (and instead ask you for money).

Also this is MSVC, I'm absolutely not ruling out a compiler bug here.

[fscoto]

Weather update: 3.0.0 doesn't exhibit the issue, so it's some change between 3.0.0 and 3.1.0 that caused MSVC to have a bad hair day.

[fscoto]

git bisect narrows it down to commit 6411aa4.

[fscoto]

Replacing line 1379 COPY(trimmed, scalar, 32); with memcpy(trimmed, scalar, 32); makes the tests pass again. This is obviously a non-starter because it introduces a dependency on the C standard library, but this is either an optimization bug or some kind of really non-intuitive interpretation of... something.

It's also partially not a heisenbug: If I add debug printf() that print both e and your_secret_key in crypto_x25519, the issue doesn't vanish. But it is a heisenbug in the function itself: If I add something that prints every element as it's being copied or that prints every byte of trimmed right before the function returns, the tests pass again.

If I move the COPY() out of trim_scalar() and do the trimming immediately at the calling sites, then it works (which is essentially the same as before 6411aa4).

---

Is there any way to read either the C or C++ standard that the compiler is allowed to somehow break a copy operation between two pointers (i.e. iterating through two arrays and setting every element) except if using memcpy?

[tankf33der]

Monocypher 3.1.0 passed tests on Oracle SPARC under Sun Studio 12.5

cc: Studio 12.5 Sun C 5.14 SunOS_sparc 2018/09/21

[tankf33der]

Monocypher 3.1.0 passed tests on IBM POWER under XL C

IBM XL C/C++ for AIX, V12.0
Version: 12.00.0000.0000

[LoupVaillant]

It appears that the compiler assumes the two pointers cannot alias, and triggers UB on that ground.

I'll revert the patch: it has dubious value: we save like one line of code, at the cost of a copy in some cases, and now this MSVC… oddity.

In any case, I'm not worried about security: the test suite fails fairly loudly, I expect the failures will manifest as clean breaks (the programs will simply fail).

[fscoto]

It appears that the compiler assumes the two pointers cannot alias, and triggers UB on that ground.

The funniest part is that it's breaking on two pointers that don't alias. your_secret_key comes from an outside context and e is on the local stack of crypto_x25519. They never, ever alias, and thus nothing should break. I have no idea why this is happening and I'm about 30% sure it's a compiler bug.

[LoupVaillant]

Okay, that's creepy. I'd personally bet at 90% compiler bug: our test suite is really thorough, @tankf33der tests this on a gazillion machines… Perhaps we should test this (before my latest patch) with older versions of MSVC?

If someone can find the energy to report a bug, that would be great. Thought I wouldn't hold my breath about them responding favourably.