KOS OT uses potentially insecure consistency check

[robinhundt]

In the original version of the KOS15 paper, the security of the consistency check (Fig. 7) relied on Lemma 1 which was not proven. In the paper on SoftSpokenOT, Lemma 1 was proven to be false and an (impractical) attack is given (Appendix Sec. D). They also give a more practical attack, which requires a special case which I think is not present in swanky's implementation.

The authors of KOS15 changed the paper to use a consistency check based on SoftSpokenOT (Sec. 4 in KOS paper). This was implemented in libOTe in osu-crypto/libOTe@90f029d and in cryprot-ot in robinhundt/CryProt#6.

Fixing this in ocelot would require some refactoring. The current consistency check is computed on the transposed rows sent from the receiver to the sender, before the hashing.
In the KosSender:

swanky/ocelot/src/ot/kos.rs

Lines 31 to 69 in 754f659

	impl<OT: OtReceiver<Msg = Block> + Malicious> Sender<OT> {
	pub(super) fn send_setup<C: AbstractChannel, RNG: CryptoRng + Rng>(
	&mut self,
	channel: &mut C,
	m: usize,
	rng: &mut RNG,
	) -> Result<Vec<u8>, Error> {
	let m = if m % 8 != 0 { m + (8 - m % 8) } else { m };
	let ncols = m + 128 + SSP;
	let qs = self.ot.send_setup(channel, ncols)?;
	// Check correlation
	let mut seed = Block::default();
	rng.fill_bytes(seed.as_mut());
	let seed = cointoss::send(channel, &[seed])?;
	let mut rng = AesRng::from_seed(seed[0]);
	let mut check = (Block::default(), Block::default());
	let mut chi = Block::default();
	for j in 0..ncols {
	let q = &qs[j * 16..(j + 1) * 16];
	let q: [u8; 16] = q.try_into().unwrap();
	let q = Block::from(q);
	rng.fill_bytes(chi.as_mut());
	let [lo, hi] = q.carryless_mul_wide(chi);
	check = utils::xor_two_blocks(&check, &(lo, hi));
	}
	let x = channel.read_block()?;
	let t0 = channel.read_block()?;
	let t1 = channel.read_block()?;
	let [lo, hi] = x.carryless_mul_wide(self.ot.s_);
	let check = utils::xor_two_blocks(&check, &(lo, hi));
	if check != (t0, t1) {
	return Err(Error::from(std::io::Error::new(
	ErrorKind::InvalidData,
	"Consistency check failed",
	)));
	}
	Ok(qs)
	}
	}

which uses the AlszSender:

swanky/ocelot/src/ot/alsz.rs

Lines 59 to 79 in 754f659

	impl<OT: OtReceiver<Msg = Block> + SemiHonest> Sender<OT> {
	pub(super) fn send_setup<C: AbstractChannel>(
	&mut self,
	channel: &mut C,
	m: usize,
	) -> Result<Vec<u8>, Error> {
	const nrows: usize = 128;
	let ncols = if m % 8 != 0 { m + (8 - m % 8) } else { m };
	let mut qs = vec![0u8; nrows * ncols / 8];
	let mut u = vec![0u8; ncols / 8];
	let zero = vec![0u8; ncols / 8];
	for (j, (b, rng)) in self.s.iter().zip(self.rngs.iter_mut()).enumerate() {
	let range = j * ncols / 8..(j + 1) * ncols / 8;
	let q = &mut qs[range];
	channel.read_bytes(&mut u)?;
	rng.fill_bytes(q);
	scutils::xor_inplace(q, if *b { &u } else { &zero });
	}
	Ok(utils::transpose(&qs, nrows, ncols))
	}
	}

In contrast, the new consistency check (Fig. 10 in KOS paper) is done on the matrices T and Q. split into blocks of size s, before the transpose. To enable an efficient implementation, s can be set to 128 so that the blocks operated on in the consistency check are swanky's 128-bit Blocks.

The same problem is present in polytune's fork of ocelot (see sine-fdn/polytune#63).