Constant-time GroupElement.cmov() by ivmaykov · Pull Request #31

Constant-time GroupElement.cmov() by ivmaykov · Pull Request #31 · str4d/ed25519-java

Bumped the pom version to 0.2.0-SNAPSHOT and implemented GroupElement.cmov() in true constant time for Ed25519 curve.

Thanks for the PR @ivmaykov! Existing tests are indeed passing (the Travis failures are a separate test issue caused by the looped random GroupElement tests timing out). Could you please also add the following test of FieldElement.cmov() itself:

index a342f60..adb27ac 100644
--- a/test/net/i2p/crypto/eddsa/math/AbstractFieldElementTest.java
+++ b/test/net/i2p/crypto/eddsa/math/AbstractFieldElementTest.java
@@ -190,6 +190,23 @@ public abstract class AbstractFieldElementTest {
 
     // endregion
 
+    // region cmov
+
+    @Test
+    public void cmovReturnsCorrectResult() {
+        final FieldElement zero = getZeroFieldElement();
+        final FieldElement nz = getNonZeroFieldElement();
+        final FieldElement f = getRandomFieldElement();
+
+        assertThat(zero.cmov(nz, 0), is(equalTo(zero)));
+        assertThat(zero.cmov(nz, 1), is(equalTo(nz)));
+
+        assertThat(f.cmov(nz, 0), is(equalTo(f)));
+        assertThat(f.cmov(nz, 1), is(equalTo(nz)));
+    }
+
+    // endregion
+
     // region hashCode / equals
 
     @Test

I'm guessing that the existing code was not in fact constant-time because the Java compiler is more intelligent that I was giving it credit for? Lovely 😂 As annoying as a 35% decrease in speed is, the faster cmov was implemented when the underlying FieldElement code was all BigInteger-based and very slow (3d12a25, de84365), so signing is still faster than it was then. And I do lean towards constant-time-ness 😃

@str4d added test and rebased to master

@str4d yeah, when trying to implement constant-time operations, CPU branch predictor is your enemy. A for loop is basically syntactic sugar for if checks and jumps, so the branch predictor will try to optimize it and get in the way. Compiler may try to do something clever too, but I'm not sure - I haven't looked at the generated byte code.

@str4d any chance this will get merged soon?

Speed tests via the I2P test harness:

Before

Testing EdDSA_SHA512_Ed25519
EdDSA_SHA512_Ed25519 key gen 1000 times: 0.259003929 ms each
EdDSA_SHA512_Ed25519 private-to-public test PASSED
EdDSA_SHA512_Ed25519 sign/verify 1000 times: 714 ms = 0.187 each sign, 0.527 each verify, 0.714 s+v

After

Testing EdDSA_SHA512_Ed25519
EdDSA_SHA512_Ed25519 key gen 1000 times: 0.338187675 ms each
EdDSA_SHA512_Ed25519 private-to-public test PASSED
EdDSA_SHA512_Ed25519 sign/verify 1000 times: 828 ms = 0.296 each sign, 0.532 each verify, 0.828 s+v

So this results in a 58% increase in time per signature, or a 36% decrease in signing speed, matching @ivmaykov's observations.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK. A few nice-to-have comments, but I'll merge this beginning of next week if there are no further changes.

		int g6 = that.t[6];
		int g7 = that.t[7];
		int g8 = that.t[8];
		int g9 = that.t[9];

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Non-blocking: the individual copies are probably unnecessary.

		int x6 = f6 ^ g6;
		int x7 = f7 ^ g7;
		int x8 = f8 ^ g8;
		int x9 = f9 ^ g9;

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Non-blocking: each of these steps could possibly be rolled up, e.g.

for (int i = 0; i < 10; i++) {
    x[i] = t[i] ^ g[i];
}

See the equivalent handling in add(), subtract() and negate(). We'd need to check whether the branch predictor would interfere with the multiple sequential for loops, even though they would be fixed-length (unlike the for loop that this PR replaces, which conditionally ended on the secret b).

Even more concisely:

b = -b;
for (int i = 0; i < 10; i++) {
    x[i] = t[i] ^ g[i];
    x[i] &= b;
    f[i] ^= x[i];
}

But I'm less confident that the re-ordering of b = -b doesn't enable the compiler to make any optimisations.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This actually makes the code a few percent faster. My guess is this is thanks to the JIT auto-vectorization of tight loops (i.e. it's able to translate the loop into SSE instructions). But I haven't confirmed it by looking at the assembly or anything like that.


		public abstract FieldElement pow22523();

		public abstract FieldElement cmov(FieldElement g, final int b);

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

s/g/val for consistency.

		return pow(f.getQm5d8());
		}

		@Override

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

s/g/val for consistency.

		* @return a copy of this if b == 0, or a copy of g if b == 1.
		*/
		@Override
		public FieldElement cmov(FieldElement g, int b) {

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

s/g/val for consistency (and ditto in the comments).

@str4d made changes you requested

Java bytecode for the rolled-up cmov looks sensible (definitely only doing a jump on i). Benchmark shows a 30% decrease in signing speed:

Testing EdDSA_SHA512_Ed25519
EdDSA_SHA512_Ed25519 key gen 1000 times: 0.298437416 ms each
EdDSA_SHA512_Ed25519 private-to-public test PASSED
EdDSA_SHA512_Ed25519 sign/verify 1000 times: 752 ms = 0.265 each sign, 0.487 each verify, 0.752 s+v

Looks great to me. Thanks @ivmaykov!

str4d mentioned this pull request

Jan 28, 2019