Inconsistent between C and Rust implementations

[DorianCoding]

Hello,

Sorry if I'm doing something wrong but I have some inconsistent. And if I was indeed doing wrong, I'm wondering why it would not give an error...

Let's say Bob and Alice uses Kyber in Rust and C respectively because they are purist. Bob uses this code after the first part of Alice one (it was for convenient) :

/* Deterministic randombytes by Daniel J. Bernstein */
/* taken from SUPERCOP (https://bench.cr.yp.to)     */

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "kem.h"
#include <fcntl.h>
#include <sys/stat.h>
#include "randombytes.h"
#include <string.h>
#include <errno.h>
static uint8_t* datafromhex(char *string)
{
  //From https://stackoverflow.com/a/35452093
  //Needs the char* and returns an already allocated array
  if (string == NULL)
    return NULL;
  size_t slength = strlen(string);
  if ((slength % 2) != 0) // must be even
    return NULL;

  size_t dlength = slength / 2;

  uint8_t *data = malloc(dlength);
  memset(data, 0, dlength);

  size_t index = 0;
  while (index < slength)
  {
    char c = string[index];
    int value = 0;
    if (c >= '0' && c <= '9')
      value = (c - '0');
    else if (c >= 'A' && c <= 'F')
      value = (10 + (c - 'A'));
    else if (c >= 'a' && c <= 'f')
      value = (10 + (c - 'a'));
    else
    {
      free(data);
      return NULL;
    }

    data[(index / 2)] += value << (((index + 1) % 2) * 4);

    index++;
  }

  return data;
}

int main(void)
{
  unsigned int j;
  uint8_t pk[CRYPTO_PUBLICKEYBYTES]={0};
  uint8_t sk[CRYPTO_SECRETKEYBYTES]={0};
  char pkhex[CRYPTO_PUBLICKEYBYTES*2+1]={0};
  char skhex[CRYPTO_SECRETKEYBYTES*2+1]={0};
  FILE *file;
  FILE *skey;
  FILE *pkey;
  mode_t umode;
  uint8_t ct[CRYPTO_CIPHERTEXTBYTES];
  uint8_t key_a[CRYPTO_BYTES];
  uint8_t key_b[CRYPTO_BYTES];
  pkey = fopen("bobpublickey.pem", "r");
  if (fread(pkhex, sizeof(pkhex[0]), CRYPTO_PUBLICKEYBYTES*2, pkey) != CRYPTO_PUBLICKEYBYTES*2)
  {
    fprintf(stderr, "Cannot extract public key.\n");
    exit(EXIT_FAILURE);
  }
  uint8_t *result;
  printf("Pkhex is %s\n",pkhex);
  result=datafromhex(pkhex);
  if (result==NULL) {
    fprintf(stderr, "Cannot extract public key.\n");
    exit(EXIT_FAILURE);
  }
  *pk=*result;
  free(result);
  fclose(pkey);
    skey = fopen("bobsecretkey.pem", "r");
//  if (fread(skhex, sizeof(skhex[0]), CRYPTO_SECRETKEYBYTES*2, skey) != CRYPTO_SECRETKEYBYTES*2)
  if (fread(skhex, sizeof(skhex[0]), 6336, skey) != 6336)
  {
    fprintf(stderr, "Cannot extract secret key\n");
    exit(EXIT_FAILURE);
  }
  printf("SKhex is : %s\n",skhex);
  result=datafromhex(skhex);
  if (result==NULL) {
    fprintf(stderr, "Cannot decode secret key.\n");
    exit(EXIT_FAILURE);
  }
  *sk=*result;
  free(result);
  fclose(skey);
    // Encapsulation
  crypto_kem_enc(ct, key_b, pk);
  crypto_kem_dec(key_a, ct, sk);
  file = fopen("sharedsecret.pem", "w");
  if (file == NULL)
  {
    fprintf(stderr, "Cannot create file for shared secret.\n");
    exit(EXIT_FAILURE);
  }
  for (j = 0; j < CRYPTO_BYTES; j++)
    fprintf(file, "%02x", key_a[j]);
  fclose(file);
  file = fopen("cipher.pem", "w");
  if (file == NULL)
  {
    fprintf(stderr, "Cannot create file for shared secret.\n");
    exit(EXIT_FAILURE);
  }
  for (j = 0; j < CRYPTO_CIPHERTEXTBYTES; j++)
    fprintf(file,"%02x", ct[j]);
  fclose(file);
  return 0;
}

Bob shares its key to Alice (just to test, we don't do that in real life) so she can try her Rust code :

use hex::{self, FromHexError, decode};
use pqc_kyber::*;
use rand;
use std::fs::{self, File};
use std::io::{Error, Write};
#[cfg(target_family = "unix")]
use std::os::unix::fs::PermissionsExt;
fn encodehex(data: &[u8]) -> String {
    hex::encode(data)
}
fn decodehex(hex: &str) -> Result<Vec<u8>, FromHexError> {
    hex::decode(hex)
}

fn main() -> Result<(), KyberError> {
    let mut rng = rand::thread_rng();
    let mut alice = Ake::new();
    let mut bob = Ake::new();

    let alice_keys = keypair(&mut rng)?;
    let bob_keys = keypair(&mut rng)?;
    fs::write("bobpublickey.pem",hex::encode(bob_keys.public));
    fs::write("bobsecretkey.pem",hex::encode(bob_keys.secret));
    fs::write("alicepublickey.pem",hex::encode(alice_keys.public));
    fs::write("alicesecretkey.pem",hex::encode(alice_keys.secret));
    let bobpkey = fs::read("bobpublickey.pem").unwrap();
    let bobskey = fs::read("bobsecretkey.pem").unwrap();
    let bobpkey: [u8;KYBER_PUBLICKEYBYTES] = bobpkey[..KYBER_PUBLICKEYBYTES].try_into().unwrap();
    let bobskey: [u8;KYBER_SECRETKEYBYTES] = bobskey[..KYBER_SECRETKEYBYTES].try_into().unwrap();
    //let keys_bob = keypair(&mut rng)?;
    let keys_bob=Keypair {
        public: bobpkey,
        secret: bobskey
    };
    //Go to C to get the cipher to verify here.
    let ciphertext=fs::read_to_string("cipher.pem").unwrap();
    println!("Keys would be {}",ciphertext);
    let ciphertext = decodehex(&ciphertext.trim()).unwrap();
    // Alice encapsulates a shared secret using Bob's public key
    //let (ciphertext, shared_secret_alice) = encapsulate(&publickey, &mut rng)?;
    // Bob decapsulates a shared secret using the ciphertext sent by Alice
    let shared_secret_bob = decapsulate(&ciphertext, &keys_bob.secret)?;
    println!("Shared secret is {}",hex::encode(shared_secret_bob));
    Ok(())
}

However at the end, the shared secret is different :

Rust : 12d6dc3e341bb2afd57d7266d898771e6c25db3d28b3d321784dffec5b6f2401
C : fe3f00af8029fdfc22c84eb4f5ece5819ca9e373c94d72430623cc9fe21728fe

I don't know if I'm doing something wrong or if the implementation has some issues but the shared secret should be the same using same keys and same cipher.

[mberry]

I can have a look at it later tomorrow if need be but from initial inspection it is perhaps in novel C implementation of the AKE?

Could you give a try with the kyber reference AKE functions instead? https://github.com/pq-crystals/kyber/blob/main/ref/kex.c

I'm not a fan of the current AKE and UAKE structs, they are inefficient and clunky, but will certainly investigate to make sure of interop if it doesn't work with those.

[mberry]

Actually my mistake, the AKE struct isn't being used at all here.

Can you reduce it to a Minimum Reproducible Example without all the extra parts and we can go from there?

Thanks.

[DorianCoding]

Hello and first of all thanks for your help.

Sure I'II try this evening. I have redefined the C code too as there were some mistakes when converting. Now I have a C code that extracts correctly everything from Rust but still fails (I have changed the C code to indicate the fail so the use of cmov but should not be an issue). It explains why I don't have an error that I was expecting (it's the spec AFAIK). I'm reducing the code and sending you ASAP. I've investigated the code of both libraries yesterday but have not found anything that could explain it.

First, please execute the following rust code (add hex that is not present in this crate), I use the following Cargo.toml :

[package]
name = "kyber"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
hex = "0.4.3"
rand = "0.8.5"
[target.'cfg(target_arch = "x86_64")'.dependencies]
#pqc_kyber = { version = "0.7.1", features = ["std", "kyber1024", "avx", "zeroize", "benchmarking"] }
pqc_kyber = { version = "0.7.1", features = ["std", "kyber1024", "zeroize", "benchmarking"] }
[target.'cfg(not(target_arch = "x86_64"))'.dependencies]
pqc_kyber = { version = "0.7.1", features = ["std", "kyber1024", "zeroize", "benchmarking"] }

The following test was done with avx disabled.

use hex::{self, decode, FromHexError};
use pqc_kyber::*;
use rand;
use std::fs::{self, File};
use std::io::{Error, Write};
#[cfg(target_family = "unix")]
use std::os::unix::fs::PermissionsExt;
fn encodehex(data: &[u8]) -> String {
    hex::encode(data)
}

fn main() -> Result<(), KyberError> {
    let mut rng = rand::thread_rng();
    let keys_bob = keypair(&mut rng)?;
    fs::write("bobpublickey.pem", &keys_bob.public);
    fs::write("bobsecretkey.pem", &keys_bob.secret);
    let (ciphertext, shared_secret_alice) = encapsulate(&keys_bob.public, &mut rng)?;
    let _ = fs::write("cipher.pem", &ciphertext).unwrap();
    println!("Shared secret is {}", hex::encode(shared_secret_alice));
    return Ok(());
}

Then, use the three created files to get the same shared secret from C library in ref folder (not avx but I can try and activate it in Rust too) : I compile as follows :

cc -Wall -Wextra -Wpedantic -Wmissing-prototypes -Wredundant-decls -Wshadow -Wpointer-arith -O3 -fomit-frame-pointer -DKYBER_K=4 kex.c kem.c indcpa.c polyvec.c poly.c ntt.c cbd.c reduce.c verify.c fips202.c symmetric-shake.c randombytes.c test.c -o testing

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "kem.h"
#include <fcntl.h>
#include <sys/stat.h>
#include "randombytes.h"
#include <string.h>
#include <errno.h>

int main(void)
{
  unsigned int j;
  uint8_t pk[CRYPTO_PUBLICKEYBYTES + 1] = {0};
  uint8_t sk[CRYPTO_SECRETKEYBYTES + 1] = {0};
  uint8_t ct[CRYPTO_CIPHERTEXTBYTES + 1] = {0};
  uint8_t key_a[CRYPTO_BYTES + 1] = {0}; // Null terminated (does not change anything without anyway)
  FILE *skey;
  FILE *pkey;
  FILE *cipher;
  mode_t umode;
  //Read files created by Rust 
  pkey = fopen("bobpublickey.pem", "rb");
  if (fread(pk, sizeof(pk[0]), CRYPTO_PUBLICKEYBYTES, pkey) != CRYPTO_PUBLICKEYBYTES)
  {
    fprintf(stderr, "Cannot extract public key.\n");
    exit(EXIT_FAILURE);
  }
  fclose(pkey);
  skey = fopen("bobsecretkey.pem", "rb");
  if (fread(sk, sizeof(sk[0]), CRYPTO_SECRETKEYBYTES, skey) != CRYPTO_SECRETKEYBYTES)
  {
    fprintf(stderr, "Cannot extract secret key\n");
    exit(EXIT_FAILURE);
  }
  fclose(skey);
  cipher = fopen("cipher.pem", "rb");
  if (fread(ct, sizeof(ct[0]), CRYPTO_CIPHERTEXTBYTES, cipher) != CRYPTO_CIPHERTEXTBYTES)
  {
    fprintf(stderr, "Cannot extract cipher\n");
    exit(EXIT_FAILURE);
  }
  fclose(cipher);
  crypto_kem_dec(key_a, ct, sk);
  for (j = 0; j < CRYPTO_BYTES; j++)
    printf("%02x", key_a[j]);
  return 0;
}

I don't achieve to get the same and I get a Fail: 1 (from verify.c that I have edited). I have tried the opposite (generation from C and test from Rust) but unfortunately, I don't achieve to make it work :/ Of course, Rust alone or C alone works well. Maybe there is features different between the both... I don't know if it could matter.

[DorianCoding]

Hello,

I'm sorry. It seems 90-fixslice was activated on the C compilation and therefore result was therefore different. Setting same option solves the problem for unauthentificated and UAKE handshake (I did not try AKE).

Sorry.