GHASH multiplication result

[makavity]

Hello. I have two words:
u: 34904055 11BE3297 1343724C 5AB793E9
v: 22481783 8761A9D6 E3EC9689 110FB0F3

u * v is defined: 𝑤(𝑥) = 𝑢(𝑥)𝑣(𝑥) mod 𝑥 ^ 128 + 𝑥 ^ 7 + 𝑥 ^ 2 + 𝑥 + 1

u * v should be: 0001D107 FC67DE40 04DC2C80 3DFD95C3

As i suggest, code should be like this:

let a = hex!("34904055 11BE3297 1343724C 5AB793E9");
let mut b = hex!("22481783 8761A9D6 E3EC9689 110FB0F3");
b.reverse();
let a_block = Block::from(a);
let b_block = Block::from(b);
let b_block = crate::mulx(&b_block);

let u = U64x2::from(&a_block);
let v = U64x2::from(&b_block);
let w = u * v;

But result is like: [43, EF, 88, F0, CA, C0, 21, F9, D1, BD, 33, 94, A0, E4, C0, DE]

Also, tried to reverse output bytes, but no luck with that. Any ideas how to deal with that?
Thank you.

[tarcieri]

Are you trying to use polyval directly, or ghash? You should probably use ghash to have it handle the conversions for you.

[makavity]

In GHash, there are no direct mul operation. But as I see, I can do multiplication in terms of Polyval, by mulx and reverse byte order.

[tarcieri]

Okay, that's not going to make things easy. It looks like you're not reversing the inputs or outputs, for starters.

[makavity]

let mut a = hex!("34904055 11BE3297 1343724C 5AB793E9");
let mut b = hex!("22481783 8761A9D6 E3EC9689 110FB0F3");
let mut c = hex!("0001D107 FC67DE40 04DC2C80 3DFD95C3");

let a_block = Block::from(a);
let b_block = Block::from(b);
let b_block = crate::mulx(&b_block);

let u = U64x2::from(&a_block);
let v = U64x2::from(&b_block);
let w = u * v;
let w_bytes = [w.0.to_le_bytes(), w.1.to_le_bytes()].concat();

println!("w: {:02X?}", w_bytes);

w: [F9, 21, C0, CA, F0, 88, EF, 43, DE, C0, E4, A0, 94, 33, BD, D1]

let mut a = hex!("34904055 11BE3297 1343724C 5AB793E9");
a.reverse();
let mut b = hex!("22481783 8761A9D6 E3EC9689 110FB0F3");
b.reverse();
let mut c = hex!("0001D107 FC67DE40 04DC2C80 3DFD95C3");

w: [5F, 27, A5, B8, 67, AA, E8, 07, 79, 9E, E7, 90, 6F, 7B, 67, 08]

Looks like, im doing something wrong :)

[tarcieri]

It still seems like you aren't reversing the inputs. Perhaps you should try to get the basic GHASH working before you move on?

[makavity]

I have already tried. But for * operation, I have test values.
What you mean, about "aren't reversing the inputs? I've done a.reverse and b.reverse :)

[tarcieri]

GHASH has test vectors. The ghash crate works. You should probably start by trying to reproduce those test vectors in your own code before moving on.

I've done a.reverse and b.reverse :)

Do you mean that the lower code example in the latest comment replaces the top? It's very confusing.

You need to reverse both of the inputs before multiplying, then reverse the output.

[makavity]

let mut u = hex!("34904055 11BE3297 1343724C 5AB793E9");
let mut v = hex!("22481783 8761A9D6 E3EC9689 110FB0F3");

let mut ghash = GHash::new(&Key::<GHash>::from(v));
ghash.update_padded(&u);
let r = ghash.finalize();
println!("{:02X?}", r);

[D1, BD, 33, 94, A0, E4, C0, DE, 43, EF, 88, F0, CA, C0, 21, F9]

Is that correct, to perform multiply u * v in terms of polyval?

[tarcieri]

I meant that you should try to implement GHASH itself in terms of the polyval crate, and get it to where it's matching the GHASH test vectors, before trying to pull it apart and change the arithmetic operations it's doing

[makavity]

Okay. But we have already correct GHash crate :)
If GHash is correct, so, in my example, i have (s + x) * h where h is v and s is 0. When i do s + x, I have x in self.s. So, it performs multiplication u*v. Right?
Maybe I don't need to implement ghash myself?

[tarcieri]

There's a bug somewhere in your code, and since your examples aren't complete / runnable I can't tell where.

That's why I was suggesting you at least get GHASH right, since that should be easy to compare to the working ghash crate.

[makavity]

Hm.
u * v is u(x) * v (x) mod x^128 + x ^ 7 + x ^ 2 + x + 1
Can't find this bug :(

[newpavlov]

The following test added to mgm/src/gf128_soft64.rs passes:

#[test]
fn belt_test() {
    use hex_literal::hex;

    let mut a = Block::clone_from_slice(&hex!("34904055 11BE3297 1343724C 5AB793E9"));
    a.reverse();
    let mut b = Block::clone_from_slice(&hex!("22481783 8761A9D6 E3EC9689 110FB0F3"));
    b.reverse();

    let mut res = Block::clone_from_slice(&hex!("0001D107 FC67DE40 04DC2C80 3DFD95C3"));
    res.reverse();

    let mut val = Element::new();
    val.mul_sum(&a, &b);
    assert_eq!(res, val.into_bytes());
}

MGM uses big endian order, thus the need for reverses. So the issue is with order of bits. It should be possible to do it with polyval, but ordering differences made it annoying enough for me to (I thought temporarily, heh) fork multiplication backends.

[tarcieri]

We could potentially add a polyval::hazmat module which exposes an abstraction over the low-level operations, and then wrap that up in an additional ghash::hazmat module to make it easier to implement GHASH-based protocols

[newpavlov]

For now, I think the easiest solution for belt-dwp will be to copy the 64-bit soft backend from the mgm crate with from_be_bytes replaced with from_le_bytes. After that, we can create a separate issue for porting MGM and DWP to polyval/ghash.

[makavity]

For now, I think the easiest solution for belt-dwp will be to copy the 64-bit soft backend from the mgm crate with from_be_bytes replaced with from_le_bytes. After that, we can create a separate issue for porting MGM and DWP to polyval/ghash.

I think this should be fine solution. Thank you so much for helping. And you, @tarcieri.
I struggled with the problem for a very long time