Encaps/decaps failures with SIKE-compressed

[thomwiggers]

I've been seeing encaps/decapsulation failures with SIKE-434-compressed.

I modified test_kem.c to be multithreaded and use NIST-KAT's RNG: https://gist.github.com/thomwiggers/c23e2c4e01971ccfd5496466b72a89c6

SIKE-p434-compressed
Configuration info
==================
Target platform:  x86_64-Linux-5.11.16-arch1-1
Compiler:         gcc (10.2.0)
Compile options:  [-march=native;-Werror;-Wall;-Wextra;-Wpedantic;-Wstrict-prototypes;-Wshadow;-Wformat=2;-Wfloat-equal;-Wwrite-strings;-O3;-fomit-frame-pointer;-fdata-sections;-ffunction-sections;-Wl,--gc-sections;-Wbad-function-cast]
OQS version:      0.6.0-rc1
Git commit:       8f8bb44c2fb8ce4b65aca2889ca2b8c11861f2cb
OpenSSL enabled:  Yes (OpenSSL 1.1.1k  25 Mar 2021)
AES:              OpenSSL
SHA-2:            OpenSSL
SHA-3:            C
CPU exts compile-time:  ADX AES AVX AVX2 AVX512 BMI1 BMI2 POPCNT SSE SSE2 SSE3

ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  8B9E5F79BB0EE397C7DF04C0D6593280ADD0A92CB6F9D046738C7C0846A340529B28F78FC7CFBCE732C0C0E1031114F4
shared_secret_e      (  16 bytes):  119D4BBA6CC7A3196B6CB11EDC2C5331
shared_secret_d      (  16 bytes):  8BBA5DD161F22661502BE27C603B5CE4
ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  6BA56E8703B104A29E1F20D8A3D64FD9EB36CDE9A49E921B462178A86D1D8FB677902F8C61B4C488B11AD879F5FDDA67
shared_secret_e      (  16 bytes):  911A05EA62C8CE15F8E88F107C810284
shared_secret_d      (  16 bytes):  B6B6926F523F575BFE9C4864D6506C57
ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  FCC52CBE74090A719C44655B99623B89DE1D39C09286FCA28F7A21B468CD43A7249166DA370D68E445F1CE7F4FDB365A
shared_secret_e      (  16 bytes):  F717246F5062F3C571A85ED7BB5ACC98
shared_secret_d      (  16 bytes):  B8C0FC2D380DBF78338D7DFD425448AF
ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  BF65977D2084F980670C2BDC36544A486E4394944342DD09EF308D5F004732C4D15D5799F1B34FF730CF76C22BC0865F
shared_secret_e      (  16 bytes):  35B19B9E4B0B8B08ECA644143B917EE7
shared_secret_d      (  16 bytes):  C63B716E1640D7CB9E50099F32727F89
ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  509867683AF7141564E58616740CADEA09E127F3B688E4BC478B82E5BB6D3FFEBA5EB23C086D04098B67477C32725749
shared_secret_e      (  16 bytes):  0028DA44B2E61F170421B97499D1F84B
shared_secret_d      (  16 bytes):  F00B568402CAC17896EAC96F721C9DB4
ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  4C47590C30F81A7F3269B1D84673357300C3FA8C320D7EB5536F35FE90C6E806CCBDCB58F12636DB11AAA5AC18CFC5DA
shared_secret_e      (  16 bytes):  A2DC81A27CB5D52B9E009C1BB0108DB9
shared_secret_d      (  16 bytes):  12A2EECB020B2F36578EA5FA1B975FA0
ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  7AB5700CAF8CAC1616A1D035B8D11BE99FB9F2C86CE59D2B2EF8DBC86487388474AB54A2380D9D18B3A8BACAE1F5D939
shared_secret_e      (  16 bytes):  84F16BEF4CEA85F1D6180558E12F4D75
shared_secret_d      (  16 bytes):  01768B20F51CBCBEAFE00C2389717BB4
ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  62CD496D391D7FE6447A417F4466C2D9424B2DCEC6F8787D0132F33BB97EAE1CC0FF08C63A789433D98DE2BED09855AA
shared_secret_e      (  16 bytes):  16733BB49A09248179772B18FD282DC6
shared_secret_d      (  16 bytes):  2907E88CD3FD5BDF5AE82AC945366318

I've not yet entirely figured out how to feed the seed back in to get a reproducible-every-time version.

See discussion in #981

[thomwiggers]

I'm not able to get it to happen in SIKE-p434 (not compressed), it seems...

[thomwiggers]

ahhhhh of course, the NIST RNG isn't thread-safe, so my seeds are invalid.

[thomwiggers]

single-threaded, 434-compressed:

ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  704D49D5FF145EF5B79043935538BCAC037108179E68BDDB476006119B7F3C683729EB339787BB9309A4485CA4BA2538
shared_secret_e      (  16 bytes):  6F76007D4AAC709A8B2F5E678BC89DD3
shared_secret_d      (  16 bytes):  858562BFDCE318B55596964B4D5F1694

[thomwiggers]

this reliably reproduces it.

[dstebila]

ahhhhh of course, the NIST RNG isn't thread-safe, so my seeds are invalid.

Non-thread-safe RNG shouldn't affect test_kem; while it might produce weird seeds, you should still get equal shared secrets. Multi-threaded kat_kem would produce wrong behaviour, but that's a different story.

[jschanck]

I've confirmed that this affects the upstream code. @thomwiggers care to submit the bug report?

[jschanck]

Here's the code that reproduces it upstream:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "rng/rng.h"
#include "../src/P434/P434_compressed_api.h"

#define KAT_SUCCESS          0
#define KAT_CRYPTO_FAILURE  -4

int
main()
{
    unsigned char       seed[48] = {0x70, 0x4D, 0x49, 0xD5, 0xFF, 0x14, 0x5E, 0xF5, 0xB7, 0x90, 0x43, 0x93, 0x55, 0x38, 0xBC, 0xAC, 0x03, 0x71, 0x08, 0x17, 0x9E, 0x68, 0xBD, 0xDB, 0x47, 0x60, 0x06, 0x11, 0x9B, 0x7F, 0x3C, 0x68, 0x37, 0x29, 0xEB, 0x33, 0x97, 0x87, 0xBB, 0x93, 0x09, 0xA4, 0x48, 0x5C, 0xA4, 0xBA, 0x25, 0x38};
    unsigned char       ct[CRYPTO_CIPHERTEXTBYTES], ss[CRYPTO_BYTES], ss1[CRYPTO_BYTES];
    unsigned char       pk[CRYPTO_PUBLICKEYBYTES], sk[CRYPTO_SECRETKEYBYTES];
    int                 ret_val;

    randombytes_init(seed, NULL, 256);

    // Generate the public/private keypair
    if ( (ret_val = crypto_kem_keypair_SIKEp434_compressed(pk, sk)) != 0) {
        printf("crypto_kem_keypair returned <%d>\n", ret_val);
        return KAT_CRYPTO_FAILURE;
    }

    if ( (ret_val = crypto_kem_enc_SIKEp434_compressed(ct, ss, pk)) != 0) {
        printf("crypto_kem_enc returned <%d>\n", ret_val);
        return KAT_CRYPTO_FAILURE;
    }

    if ( (ret_val = crypto_kem_dec_SIKEp434_compressed(ss1, ct, sk)) != 0) {
        printf("crypto_kem_dec returned <%d>\n", ret_val);
        return KAT_CRYPTO_FAILURE;
    }

    if ( memcmp(ss, ss1, CRYPTO_BYTES) ) {
        printf("crypto_kem_dec returned bad 'ss' value\n");
        return KAT_CRYPTO_FAILURE;
    }

    return KAT_SUCCESS;
}

[thomwiggers]

Thanks for writing that up. I've also found the following seed for p503-compressed:

ERROR: shared secrets are not equal
entropy_input        (  48 bytes):  A82B16560B27B0464522BECECF88B02ADC64B76B564D5E6447AED185C6A2983C99B83ABCC047178D126BD0ABA2CBF60C
shared_secret_e      (  24 bytes):  C27303BFCDDB54FF1EF8CAB6099B7E5A975396E6D00F1D74
shared_secret_d      (  24 bytes):  88B9205EC8E898DA6FA46CD50CDE5F8F6DC456232A1F6417

[thomwiggers]

ahhhhh of course, the NIST RNG isn't thread-safe, so my seeds are invalid.

Non-thread-safe RNG shouldn't affect test_kem; while it might produce weird seeds, you should still get equal shared secrets. Multi-threaded kat_kem would produce wrong behaviour, but that's a different story.

Yeah, my main concern here was that it would not give me the correct seed for the wrong behaviour.

[christianpaquin]

FYI, @patricklonga.

[jschanck]

FYI I reproduced this with the fuzzer sometime yesterday, and I took the opportunity to dig into it a bit further. I understand that the SIKE team is working on a fix, but I think we might want to provide some input on what an acceptable fix might look like.

Here's the backtrace from address sanitizer

==520361==ERROR: AddressSanitizer: global-buffer-overflow on address 0x7fc9fa7db7f8 at pc 0x7fc9fa351cfd bp 0x7ffd915c6430 sp 0x7ffd915c6428
READ of size 8 at 0x7fc9fa7db7f8 thread T0
    #0 0x7f528666ecfc in fpcopy434 src/kem/sike/external/P434/../fpx.c:95:16
    #1 0x7f528668a40f in BuildEntangledXonly src/kem/sike/external/P434/../compression/torsion_basis.c:395:9
    #2 0x7f52866873e3 in BuildOrdinary2nBasis_dual src/kem/sike/external/P434/../compression/torsion_basis.c:423:5
    #3 0x7f528666ac1d in EphemeralKeyGeneration_B_extended src/kem/sike/external/P434/../compression/sidh_compressed.c:630:5
    #4 0x7f528666c958 in OQS_KEM_sike_p434_compressed_encaps src/kem/sike/external/P434/../compression/sike_compressed.c:47:5
    #5 0x7f5286aaab68 in OQS_KEM_encaps src/kem/kem.c:826:10

0x7f7b064667f8 is located 0 bytes to the right of global variable 'table_r_qnr' defined in '../src/kem/sike/external/P434/P434_compressed.c:238:23' (0x7f7b06466440) of size 952
SUMMARY: AddressSanitizer: global-buffer-overflow /home/john/liboqstest/build/../src/kem/sike/external/P434/../fpx.c:95:16 in fpcopy434

table_r_qnr lists T elements of F_p (currently T=17). The BuildEntangledXonly function takes A in F_{p^2} as input. Lines 382-392 of torsion_basis.c find the least i for which -A*table_r_qnr[i] is the x-coordinate of a point on E_A. It does not do a bounds check (i < T) hence the buffer overflow.

As far as I can tell, with probability ~2^-T the table will be exhausted (maybe there's some clever way of choosing the table entries but I don't see how to avoid this). At which point the protocol should either abort or it should generate new table entries on-the-fly. The latter is somewhat computationally expensive.

I think a failure-free protocol / on-the-fly generation of extra table entries is the better option. But I can also see us accepting a sufficiently large table + a bounds check.

How large a table would we want? Would we be comfortable with a 30 entry table and a 1 in a billion chance of failure?

[baentsch]

Would we be comfortable with a 30 entry table and a 1 in a billion chance of failure?

I personally wouldn't consider any algorithm "fit for purpose" (of large-scale deployment, i.e., billions of executions every second assuming world-wide deployment) if it is known to fail "every now and then". Probabilities shouldn't play a role.

[bhess]

I think a failure-free protocol / on-the-fly generation of extra table entries is the better option.

Yes generating extra table entries on the fly would be the preferred way. Extra computations would be limited to those cases.

I personally wouldn't consider any algorithm "fit for purpose" (of large-scale deployment, i.e., billions of executions every second assuming world-wide deployment) if it is known to fail "every now and then". Probabilities shouldn't play a role.

I agree that no failures are a nice property, a property that SIKE actually has. Would failure rates be a useful info for the algorithm data sheets? (#892)

[thomwiggers]

These failures reveal something about either the randomness that went into the secret key or the randomness that went into the encapsulation operation. I'm not sure which of the two, or if it is relevant, but failures may not be good for security...

[baentsch]

no failures are a nice property, which SIKE actually allows.

Interesting... I'd find this property very disturbing in "regular use" -- and a possible "classical", if only side-channel, attack avenue. Do you have a pointer documenting this (hopefully including an argumentation why this is no security problem)?

[bhess]

Interesting... I'd find this property very disturbing in "regular use" -- and a possible "classical", if only side-channel, attack avenue. Do you have a pointer documenting this (hopefully including an argumentation why this is no security problem)?

Perhaps what I wrote was misleading. I meant that SIKE has the property of "No Failures".

[baentsch]

I meant that SIKE has the property of "No Failures".

Now I'm even more confused: Doesn't the above constitute a failure (even if just rarely)? Or are you saying it's "just" the implementation that's wrong/out-of-step with the spec of SIKE?

[bhess]

Or are you saying it's "just" the implementation that's wrong/out-of-step with the spec of SIKE?

Correct.

[jschanck]

failures may not be good for security...

The failure is in encaps and is not a security risk. A constant fraction of the keyspace is not suitable for use with compression, and the subset depends only on the choice of table entries.

Or are you saying it's "just" the implementation that's wrong/out-of-step with the spec of SIKE?

It's not quite true that it is "just" the implementation. Page 83 of the spec says: "Experimentally, less than 20 elements are enough" and Algorithm 47 does not handle the case of exhausting the table. So the spec needs an update.

[jschanck]

Would failure rates be a useful info for the algorithm data sheets? (#892)

+1

[thomwiggers]

How large a table would we want? Would we be comfortable with a 30 entry table and a 1 in a billion chance of failure?

30, 50 or even 128 entries (56 bytes per entry, if I'm calculating this correctly) might be fine, since there are much larger tables for the compressed schemes already... In the upstream repo, libsidh.a for P434 is 1.1M, for P434Compressed it's 2.8M.

[baentsch]

since there are much larger tables for the compressed schemes already

And I was wondering why libcrypto (in openssl, including all classic algs) grows from below 3MB to more than 16MB...

So what about adding large_code (akin large_stack) as another flag to #892?

Further idea: use those flags to exclude such algorithms from a possible future "SIZE_OPTIMIZED" build type.

[geovandro]

Thanks @thomwiggers and everyone else for reporting/debugging this issue. I've submitted a pull request with a fix to avoid running into such failures by performing online computations when tables run out of elements. The online computations are not relatively expensive so haven't added extra elements to the tables so no memory overhead in the fix.

[christianpaquin]

I've submitted a pull request with a fix

SIKE PR #45 has been merged; will start integrating here.